Finger Trees: A Simple General-Purpose Data Structure (2006)

Re:Finger Trees: A Simple General-Purpose Data Structure (2006) by willtim on Tuesday December 27, 2016 @10:23AM (#13263620)

My example would probably be the work of Phil Bagwell. IMHO the biggest issue with Linked-lists is they do not support parallelism, they are inherently sequential.

[ Parent | on HN ]

Re:Finger Trees: A Simple General-Purpose Data Structure (2006) by geocar on Tuesday December 27, 2016 @10:31AM (#13263658)

Give up sequential! :)

If you want queues, and you can give up sequential, then you can get huge gains[1] in performance. Specific use cases will have better specific solutions.

[1]: e.g. https://github.com/cameron314/concurrentqueue

[ Parent | on HN ]

Re:Finger Trees: A Simple General-Purpose Data Structure (2006) by hedora on Tuesday December 27, 2016 @12:35PM (#13264517)

You can reduce some linked list operations (including multi-element ones) to a single CAS, which is often good enough.

[ Parent | on HN ]