News for hackers. Stuff that matters.
Re:Zip Trees by benbenolson on Wednesday October 24, 2018 @04:40PM (#18296152)
Any links to the implementation of this? The paper says that there's a concurrent implementation in the author's thesis, but Princeton charges $5 per copy of theses, so I can't view the actual implementation:

https://dataspace.princeton.edu/jspui/handle/88435/dsp01gh93...

Re:Zip Trees by jibal on Thursday October 25, 2018 @08:16AM (#18300297)
An implementation of zip tree insertion and deletion is in the paper. concurrent zip trees is another matter. I don't know why you can't view something that Princeton charges $5 for, but in any case I think you would find the thesis disappointing ... the arxiv paper says "The third author developed a preliminary, lock-based implementation of concurrent zip trees in his senior thesis [12]. We are currently developing a non-blocking implementation." -- I would wait for the latter.
Re:Zip Trees by jpap on Friday October 26, 2018 @12:45AM (#18306842)
I'd also love to read the thesis, especially to see how they structured the lock.

I recently wrote a readers-writers (subtree) lock for a K-ary tree and it was quite a challenge with a nontrivial implementation. It was much easier to start with a single mutex-like (subtree) lock (one reader or writer), and then extend it to the general multi-reader/writer case.

I can only imagine that a lock-free version (of even a single reader/writer) must be even more of a challenge. I hope it's not a terribly long wait, but there could be much to learn from the simpler lock-based scheme in the meantime. :)

On the topic of access to the research, I found a talk by the first author [1] a helpful companion to the paper, with slides for what appears to be the same talk elsewhere [2]. I haven't seen any implementations outside of pseudocode in the paper -- it would be nice to see if there are any tricks to generating the random ranks cheaply, or the alternative that uses a pseudo-random function of the key.

Thanks to the OP for sharing this. I'm keen to try it on another project where I was hesitant to use red-black trees due to their complexity.

[1] https://www.youtube.com/watch?v=NxRXhBur6Xs

[2] http://knuth80.elfbrink.se/wp-content/uploads/2018/01/Tarjan...