42 ms·

Skip lists are so simple conceptually, I'm managing to make them concurrent, verifiable and even persistent. For reference this is a concurrent skip list that

Skip lists are so simple conceptually, I'm managing to make them concurrent, verifiable and even persistent. For reference this is a concurrent skip list that a high school student could implement. It's beautiful. https://people.csail.mit.edu/shanir/publications/LazySkipList.pdf https://people.csail.mit.edu/shanir/publications/LazySkipLis...

sadiq 5y ago
If anyone wants one based on Herlihy et al's "The Art of Multiprocessor Programming" there's a well reviewed, tested and heavily commented concurrent lock-free one in OCaml's runtime now: https://github.com/ocaml/ocaml/blob/trunk/runtime/lf_skiplist.c https://github.com/ocaml/ocaml/blob/trunk/runtime/lf_skiplis... It's used to manage code fragments that need to be accessed in signal handlers.
- ignoramous 5y ago
  Thanks, I used that neat knuth coin-flip trick from your code. Why does the comment on the file say that its lock-free implementation is half as slow as compared to 'sequential' one? Where does the slowness come from? Is it all those while(1) loops waiting to race atomic operations?
  - sadiq 5y ago
    So that was in some quick benchmarks against the sequential one in the runtime: https://github.com/ocaml/ocaml/blob/trunk/runtime/skiplist.c https://github.com/ocaml/ocaml/blob/trunk/runtime/skiplist.c I haven't done a huge amount of investigation but I suspect the cost comes from the extra indirection in the lock-free one.
vanderZwan 5y ago
> a high school student could implement I agree it's a beautiful data structure, but this imagined high school student would be one who is comfortable with (learning about) pointers and locks. Those exist of course, in fact we probably both qualified back in the day. My point however is that that implies some major selection bias towards high school students who love programming for programming's sake, not some average high-school student who learned a bit of Python and JavaScript in their introduction to computer science class or because they want to write a game (which is a totally valid reason to learn programming). I don't really see why B-trees as a data structure would be that much more difficult to grok if we're already talking about that type of student?

sadiq 5y ago

If anyone wants one based on Herlihy et al's "The Art of Multiprocessor Programming" there's a well reviewed, tested and heavily commented concurrent lock-free one in OCaml's runtime now: https://github.com/ocaml/ocaml/blob/trunk/runtime/lf_skiplist.c https://github.com/ocaml/ocaml/blob/trunk/runtime/lf_skiplis... It's used to manage code fragments that need to be accessed in signal handlers.

ignoramous 5y ago
Thanks, I used that neat knuth coin-flip trick from your code. Why does the comment on the file say that its lock-free implementation is half as slow as compared to 'sequential' one? Where does the slowness come from? Is it all those while(1) loops waiting to race atomic operations?
- sadiq 5y ago
  So that was in some quick benchmarks against the sequential one in the runtime: https://github.com/ocaml/ocaml/blob/trunk/runtime/skiplist.c https://github.com/ocaml/ocaml/blob/trunk/runtime/skiplist.c I haven't done a huge amount of investigation but I suspect the cost comes from the extra indirection in the lock-free one.

vanderZwan 5y ago

> a high school student could implement I agree it's a beautiful data structure, but this imagined high school student would be one who is comfortable with (learning about) pointers and locks. Those exist of course, in fact we probably both qualified back in the day. My point however is that that implies some major selection bias towards high school students who love programming for programming's sake, not some average high-school student who learned a bit of Python and JavaScript in their introduction to computer science class or because they want to write a game (which is a totally valid reason to learn programming). I don't really see why B-trees as a data structure would be that much more difficult to grok if we're already talking about that type of student?