why boost does not have skip list implementation?
On Thu, Mar 1, 2018 at 7:22 AM, David Frank via Boost wrote: like java concurrentSkipListSet for example.
Thanks,
David I can't recall anyone ever proposing a skiplist.
Have you implemented one in modern C++? And run comparative timings versus
other map-like data structures on modern CPUs?
Skiplists were wicked fast in the 1990's, but with today's CPUs an
in-memory BTree may be faster because of hardware caches.
--Beman
Have you implemented one in modern C++? And run comparative timings versus other map-like data structures on modern CPUs?
Skiplists were wicked fast in the 1990's, but with today's CPUs an in-memory BTree may be faster because of hardware caches. Very true. https://www.usenix.org/system/files/conference/fast18/fast18-hwang.pdf shows how poorly skip lists perform on modern CPUs.
Niall -- ned Productions Limited Consulting http://www.nedproductions.biz/ http://ie.linkedin.com/in/nialldouglas/
participants (3)
-
Beman Dawes -
David Frank -
Niall Douglas