Talk:Ctrie

Latest comment: 9 years ago by Zikad

It is the first known concurrent data-structure that supports O(1), atomic, lock-free snapshots.

This claim is inaccurate. TransactionKit is a lockless concurrent reader and writer hash table that provides O(1), atomic, lock-free snapshots. The first release date of 2008/04/21 (from the web page) would seem to pre-date Ctries by a number of years.


From its description, TransactionKit keeps timestamps associated with each key, and retains the history between the lowest known timestamp that is used, and the latest. Items with the timestamps in between cannot be recycled, so the memory usage is unbounded.

It would be more accurate to say that Ctrie is the first known data structure that supports O(1) lock-free atomic snapshots and does not use an unbounded amount of memory. — Preceding unsigned comment added by Zikad (talkcontribs) 21:46, 4 April 2015 (UTC)Reply