Talk:Hash tree (persistent data structure)
|WikiProject Computer science|
Merge in Hash array mapped trie and Ctrie
Since HAMTs and Ctries are hash trie implemented using particular types of underlying tries, those articles can be merged into this one to get something of an overview article. QVVERTYVS (hm?) 11:26, 15 May 2013 (UTC)
Well, I would have to strongly disagree on two grounds.
- First, although it is true that the design of the ctrie initially began based on the successful HAMT, it was explicit in the goals of the effort, from the outset that the ctrie address a very different use-case that otherwise successful HAMT had been seen to be very unsuitable for. Specifically,HAMT is a persistent immutable functional datastructure, and this type of model, while broadly effective for in-memory (GC supported) applications was very space-inefficient, for example, when applied to situations requiring the structure to be allocated on-disk. The architecture of CTrie diverged to the extent that IMHO it barely recognizable as much similarity at all with that of its forebears. Most importantly, it is a mutable, concurrent index based extensively on the use of atomic CAS and a unique new variant of RDCSS called. GCAS that permitted the implementation to be accomplished using only single compare and swap instruction primitive which are widely ubiquitous on almost all current consumer-grade hardware. I don't have an interest in engaging Ina much longer explication on these fundamental architectural differences, but if you are interested, please have a look at my implementation http://github.com/danlentz/cl-ctrie and I would be happy to debate he matter more fully.
- Information on this remarkable structure is extremely sparse, difficult to find, and inconsistent and I am quite certain that a dedicated Wikipedia page on the topic is both appropriate and helpful for those that are looking to learn more about the topic. I, personally, have on many occasion directed people to this page to lean more of the general background during conversations on the matter. It would be tragic to bury it in the HAMT article. — Preceding unsigned comment added by Danlentz (talk • contribs) 14:43, 14 August 2013 (UTC)