Could someone give an example where this data structure would be useful?
They're used in a distributed hash table implementation called chord (https://en.wikipedia.org/wiki/Chord_(peer-to-peer)
Finger Trees: A Simple General-Purpose Data Structure (2006)
21–30 of 79 posts
Re: Finger Trees: A Simple General-Purpose Data Structure (2006)
#22Could someone give an example where this data structure would be useful?
There are several use-case examples in the Readme for this Clojure finger tree implementation:
Re: Finger Trees: A Simple General-Purpose Data Structure (2006)
#23Earlier quoted context omitted.
So do real arrays on real hardware (pagetable trie). Small arrays are contiguous so memcpy is fast. For large arrays, if you create a dummy file (or uses a memfd) you can mmap a region, and then copy it by mmaping the same region with the appropriate flags. You can resize (grow) it almost as easily. They're so much faster than linked lists, that there's no (performance) reason to use linked-lists on real hardware.
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.
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.
Re: Finger Trees: A Simple General-Purpose Data Structure (2006)
#24Finger trees are an example of a truly elegant functional data structure that can be used for just about everything. The problem is they don't match the memory model of real hardware so for all of their elegance and theoretical performance in reality they're too slow to be useful.
Is this true? How is this more true for finger trees than for red-black trees, etc?
Red-black trees are pretty much terrible for performance as well. I spend most of my work days trying to eradicate std::map and std::set for performance reasons.
Academics are always concerned about bounds, but practitioners are always concerned about cache misses.
Re: Finger Trees: A Simple General-Purpose Data Structure (2006)
#25Finger trees are an example of a truly elegant functional data structure that can be used for just about everything. The problem is they don't match the memory model of real hardware so for all of their elegance and theoretical performance in reality they're too slow to be useful.
Firstly, let me say you're most likely correct. I do find finger trees useful in functional languages as well and for creating immutable structures with them.
I want to add some general comments about anyone thinking about using a finger tree or anything else.
Give any potential data structure a try with real data, not contrived stuff and benchmark on the actual target hardware and in a real code path if possible. Further, try it with real-world access patterns like adding, removing, ordering, etc. at different times at different sizes - the results can be interesting. Even if something does well for one use-case, the other use-cases you need it for it may perform awful, so sometimes it's a compromise. Data structure performance is quite often not performance for a single operation, but a function of several operations. This makes it even more important to test it with real data when possible and access it different ways.
Moreover, too many times I see positive or negative benchmarks where someone is filling a data structure with exactly the same integer, or the same instance of an object or something like that. In practice, the underlying data can introduce other considerations based on the size, pointer chasing, memory allocations (especially if the data structure can dynamically resize) and so on in just about every language. Factor in hardware, and the results can change even further. Also ensure your benchmarking itself isn't flawed - we've been there and discussed it ad-nauseam and yet I continue to see bad benchmarking in the wild (particularly on the JVM or CLR).
As a related example, I've found that even the famed link list can suck in real-world. I've always been a "choose the right data structure for the job" kind of guy, and yet sometimes it's more deceptive than it seems. You might say, oh, my access patterns are exactly a linked list, and yet a simple array with lots of helper cruft code will smoke it in practice. Likewise, I've seen shocking results replacing something with a skip list or other data structure that seems like it should perform worse, but depending on the data, size, hardware, and implementation, I get interesting results. I've seen plenty of stupid things like someone who picked a hashtable for fast lookups, only to iterate through it in some other code path for some other use-case accessing the same data, completely murdering overall application performance due to selecting based on a single criterion. If you're using a language where you can create your own allocators, it can become even more interesting than you think - i.e. there are gains or losses to be had.
The moral is simple: "just try it." This comes up a lot in game programming for example and I've seen it in embedding programming have huge effects as well. I can't even begin to explain how much faster I've made things just by changing a data structure because of real-world conditions vs. lab conditions. Don't just assume that picking what the textbook says in the Big O table is what actually will dictate performance, positive or negative. There's a reason most good data structure books also contain explanation regarding behavior and performance, though even books don't and can't explain the real-world nuances when working with non-contrived data.
Re: Finger Trees: A Simple General-Purpose Data Structure (2006)
#26The problem with using lazy data structures for storing things is that deletes don't necessarily free up storage. Fingertrees are fine when you need to store a collection in order to implement some algorithm (and being persistent makes it useful if this algorithm has to backtrack), but they aren't so good for backing a collection that changes over time, like the set of currently connected sockets in a network service.
Re: Finger Trees: A Simple General-Purpose Data Structure (2006)
#27Earlier quoted context omitted.
So do real arrays on real hardware (pagetable trie). Small arrays are contiguous so memcpy is fast. For large arrays, if you create a dummy file (or uses a memfd) you can mmap a region, and then copy it by mmaping the same region with the appropriate flags. You can resize (grow) it almost as easily. They're so much faster than linked lists, that there's no (performance) reason to use linked-lists on real hardware.
The Linux kernel uses intrusive linked lists extensively. Container based linked lists contain a copy of the data item. Intrusive linked lists force the data structures in the list to contain list pointers inside of the actual data structure, and the list operations manipulate those list-specific pointers in the data structure. I am not sure if anyone has evaluated using alternatives, but my understanding of why has…
Linux uses linked lists because it is simple to code. That linked lists are slow doesn't matter very much because there are lots of slow parts in Linux that are a better use of attention.
Doom moved to vectors (arrays) because linked lists are slow, and because there wasn't enough other slow parts that needed attention.
Re: Finger Trees: A Simple General-Purpose Data Structure (2006)
#28Earlier quoted context omitted.
Is this true? How is this more true for finger trees than for red-black trees, etc?
Red-black trees are pretty much terrible for performance as well. I spend most of my work days trying to eradicate std::map and std::set for performance reasons. Academics are always concerned about bounds, but practitioners are always concerned about cache misses.
I generally agree with this and most of the time it's hard to justify using a red-black tree if you care about performance. You can use one if you have other concerns perhaps or performance isn't one of them.
I also concur cache misses are vital and sometimes don't get enough attention since people pass hand wave them away as micro-benchmarking which isn't true often for critical code paths. I'll add that again, this is why testing on your target hardware is important. You may think you know, but often you don't. I've seen too much stupid stuff where someone wrote code that performs great on their development desktop and awful on a server or a game console because of different CPU architecture and cache design or sizes.
Maybe someone can dig it up, but I've seen some of the sub-variants of red-black trees have dramatically better performance than I thought possible (or worse, ex: left-leaning), and the results can vary across runtimes. In addition to cache misses, there can be some other considerations for wanting to use a red-black tree like concurrent or parallel programming. In these cases, some of the cousin data structures like AVL trees can swing you for or against a red-black tree or other backing structure. I had this come up recently when selecting an interval tree that needed to be accessed between threads for instance.
Selecting a data structure is harder than most people make it out to be. There's just a lot of considerations at work, so you need to balance use-cases, performance (against those cases and raw), access patterns, allocations, and so on to come to a decision. Sometimes if you add up the total cost of doing something like replacing a red-black tree with other methods that are more cache friendly or have some other characteristic that is better, the overall performance cost can end up being worse in aggregate. So the answer is the same as always, "it depends" and the follow-up, "try it."
Parent is definitely right that academic and practical concerns of those of us in the trenches being different. That's why arguing with pure textbook evidence is stupid and you should challenge anyone who does it. Textbooks are a starting point for making and justifying a conclusion, not a shortcut.
Re: Finger Trees: A Simple General-Purpose Data Structure (2006)
#29Earlier quoted context omitted.
The Linux kernel uses intrusive linked lists extensively. Container based linked lists contain a copy of the data item. Intrusive linked lists force the data structures in the list to contain list pointers inside of the actual data structure, and the list operations manipulate those list-specific pointers in the data structure. I am not sure if anyone has evaluated using alternatives, but my understanding of why has…
Linux uses linked lists because it is simple to code. That linked lists are slow doesn't matter very much because there are lots of slow parts in Linux that are a better use of attention. Doom moved to vectors (arrays) because linked lists are slow, and because there wasn't enough other slow parts that needed attention.
You can't necessarily replace intrusive linked lists with arrays. They have more operations. You can traverse so far in one list then switch to traversing in another.
Re: Finger Trees: A Simple General-Purpose Data Structure (2006)
#30Earlier quoted context omitted.
The Linux kernel uses intrusive linked lists extensively. Container based linked lists contain a copy of the data item. Intrusive linked lists force the data structures in the list to contain list pointers inside of the actual data structure, and the list operations manipulate those list-specific pointers in the data structure. I am not sure if anyone has evaluated using alternatives, but my understanding of why has…
Linux uses linked lists because it is simple to code. That linked lists are slow doesn't matter very much because there are lots of slow parts in Linux that are a better use of attention. Doom moved to vectors (arrays) because linked lists are slow, and because there wasn't enough other slow parts that needed attention.
Is this your understanding from intuition, or are you aware of kernel developers who have made this same argument?