3 ms·

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 th

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/dsp01gh93h214f https://dataspace.princeton.edu/jspui/handle/88435/dsp01gh93...

jibal 8y ago
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.
- jpap 8y ago
  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 https://www.youtube.com/watch?v=NxRXhBur6Xs [2] http://knuth80.elfbrink.se/wp-content/uploads/2018/01/Tarjan_Zip_Trees_Knuth80.pdf http://knuth80.elfbrink.se/wp-content/uploads/2018/01/Tarjan...

jibal 8y ago

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.

jpap 8y ago
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 https://www.youtube.com/watch?v=NxRXhBur6Xs [2] http://knuth80.elfbrink.se/wp-content/uploads/2018/01/Tarjan_Zip_Trees_Knuth80.pdf http://knuth80.elfbrink.se/wp-content/uploads/2018/01/Tarjan...