8 ms·

Finger 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

Finger 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.

jstimpfle 10y ago
Is this true? How is this more true for finger trees than for red-black trees, etc?
- stuckagain 10y ago
  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.
  - optionalparens 10y ago
    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.
  - catnaroek 10y ago
    When you don't need persistence, a search tree data structure with fatter nodes (e.g., B-trees) is almost guaranteed to perform better on real hardware. But when you do need persistence, red-black trees become competitive again.
    - detrino 10y ago
      I would expect B-trees to outperform binary trees even in a persistent data structure. The necessity of binary trees comes when you need stable iterators/references.
  - scott_s 10y ago
    Theory academics are primarily concerned with bounds, but systems academics are very much concerned with cache misses. I've done work with colleagues where we were very concerned with both.
- rbehrends 10y ago
  As a rule, pointer-based data structures tend to be slower than array-based data structures (though, as with any general rule, there are exceptions). This is a simple consequence of how caching and prefetching works in modern CPUs. And this performance difference can easily amount to several (!) orders of magnitude. However, there are a few caveats: 1. A garbage collector with a bump allocator can reduce these overheads significantly. So can a custom implementation (e.g. emulating pointers as offsets within an array). 2. The overhead often does not matter for performance due to the 90/10 law or because the application is not performance-critical to begin with. 3. Pointer-based data structures may support a richer set of operations than array-based data structures (or have significantly more efficient implementations for some operations). 4. Pointer-based data structures can have better worst-case or per-operation costs where array-based data structures rely on amortized or average performance to pull ahead. This can matter in soft real-time situations or when dealing with user-supplied data. 5. Certain types of data structures do not have good array-based implementations to begin with and some algorithms demand pointer-based implementations. (Think of spatial queries, for example.) 6. Performance cost is not always dominated by operations on the container, but can also be dominated by cost of operations on the items within the container. For example, there are algorithms where the most expensive operation (by far) is comparison between elements (e.g. for a priority queue implementing an expensive heuristic); in this case, you want to minimize the number of comparisons more than the cache behavior of the data structure itself (note that this may still result in you picking the array-based implementation). 7. Pointer-based data structures allow for the sharing of substructures, potentially reducing the memory footprint of an application. Binary decision diagrams are a popular example. 8. Some array-based data structures require a much larger working set than their corresponding pointer-based implementations and take a performance nosedive when the size of the working set exceeds the size of the cache. Especially when you have several such data structures in use at once. (This is where relying on microbenchmarks for performance comparison can be dangerous.)
willtim 10y ago
It's true that they have a high constant factor, but I think it's too harsh to say they are not useful. One could also say that linked-lists don't match the memory model of real hardware.
- dom0 10y ago
  > One could also say that linked-lists don't match the memory model of real hardware. They don't, and they almost always perform (much) worse.
  - qwertyuiop924 10y ago
    True. But they're also very simple. It's okay to lean on the hardware a bit, provided you're careful: most programmers don't have to squeeze maximal performace out of the hardware, just good enough performance. The extra code you need to make arrays work may not be worth the speed boost. Also, if you're working in an HLL, investigate your implementation details. In Common Lisp, for example, a lot of work has been put into making LLs as fast as possible: If you create a list with QUOTE (such lists are immutable), then thanks to an optimization called CDR-coding, you'll get a data layout very similar to an array under the hood. OTOH, it is important to understand why LL perf isn't actually what the textbooks claim, and to consider using a different structure in contexts where performance matters. Just don't go too far the other way, either: LLs aren't dead just yet.
    - dom0 10y ago
      I believe (intrusive, as they usually are) LLs are so prevalent in C applications mainly because they are the simplest-ever list structure where insertion and deletion of items is just a no-brainer to implement in a couple lines of C macros. They are also inherently self-describing (ie. you don't need to pass around anything except one pointer). And this is totally fine in many places. However, when the list is frequently (ie. performance is relevant) used, then it's likely that a LL is not the right choice. And usually one notices that in these cases no LL is used. For example, one might use a LL for a list of drivers, while eg. directory entries will be kept in a hash-table, tree or trie.
optionalparens 10y ago
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.
wyager 10y ago
Sure, if you need to do hundreds of millions of insertions per second. In the vast majority of real-world use cases, most of your time is going to be spent elsewhere. Spending a microsecond waiting on memory lookups for a cold finger tree isn't going to do much. Drop to using less convenient array-backed structures in the few places you need really fast operations, and use slightly slower (constant-wise) data structures where it's more convenient.
- gpderetta 10y ago
  > Spending a microsecond waiting on memory that's an eternity!
  - wyager 10y ago
    Not if you're writing UI code, networking code, most IO-related code, etc. A microsecond is very small compared to the time penalty you are likely to incur doing any sort of syscall. For the vast majority of code, it's negligible. For tight, fast, repetitive code it is far too slow.
catnaroek 10y ago
Even ignoring real hardware, finger trees are only efficient in an amortized sense where more specialized purely functional data structures offer better real-time guarantees. (0) Asymptotically optimal heaps: Worst-case O(1) insert, merge and findMin. Worst-case O(log n) delete. (1) Asymptotically optimal search trees: Worst-case O(log n) lookup, insert, update, delete. (2) Asymptotically optimal deques: Worst-case O(1) cons, head, tail, snoc, init, last. etc. Another downside is that they require somewhat fancy language features (namely, polymorphic recursion) to implement in a type-safe way.

jstimpfle 10y ago

Is this true? How is this more true for finger trees than for red-black trees, etc?

stuckagain 10y ago
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.
- optionalparens 10y ago
  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.
- catnaroek 10y ago
  When you don't need persistence, a search tree data structure with fatter nodes (e.g., B-trees) is almost guaranteed to perform better on real hardware. But when you do need persistence, red-black trees become competitive again.
  - detrino 10y ago
    I would expect B-trees to outperform binary trees even in a persistent data structure. The necessity of binary trees comes when you need stable iterators/references.
- scott_s 10y ago
  Theory academics are primarily concerned with bounds, but systems academics are very much concerned with cache misses. I've done work with colleagues where we were very concerned with both.
rbehrends 10y ago
As a rule, pointer-based data structures tend to be slower than array-based data structures (though, as with any general rule, there are exceptions). This is a simple consequence of how caching and prefetching works in modern CPUs. And this performance difference can easily amount to several (!) orders of magnitude. However, there are a few caveats: 1. A garbage collector with a bump allocator can reduce these overheads significantly. So can a custom implementation (e.g. emulating pointers as offsets within an array). 2. The overhead often does not matter for performance due to the 90/10 law or because the application is not performance-critical to begin with. 3. Pointer-based data structures may support a richer set of operations than array-based data structures (or have significantly more efficient implementations for some operations). 4. Pointer-based data structures can have better worst-case or per-operation costs where array-based data structures rely on amortized or average performance to pull ahead. This can matter in soft real-time situations or when dealing with user-supplied data. 5. Certain types of data structures do not have good array-based implementations to begin with and some algorithms demand pointer-based implementations. (Think of spatial queries, for example.) 6. Performance cost is not always dominated by operations on the container, but can also be dominated by cost of operations on the items within the container. For example, there are algorithms where the most expensive operation (by far) is comparison between elements (e.g. for a priority queue implementing an expensive heuristic); in this case, you want to minimize the number of comparisons more than the cache behavior of the data structure itself (note that this may still result in you picking the array-based implementation). 7. Pointer-based data structures allow for the sharing of substructures, potentially reducing the memory footprint of an application. Binary decision diagrams are a popular example. 8. Some array-based data structures require a much larger working set than their corresponding pointer-based implementations and take a performance nosedive when the size of the working set exceeds the size of the cache. Especially when you have several such data structures in use at once. (This is where relying on microbenchmarks for performance comparison can be dangerous.)

willtim 10y ago

It's true that they have a high constant factor, but I think it's too harsh to say they are not useful. One could also say that linked-lists don't match the memory model of real hardware.

dom0 10y ago
> One could also say that linked-lists don't match the memory model of real hardware. They don't, and they almost always perform (much) worse.
- qwertyuiop924 10y ago
  True. But they're also very simple. It's okay to lean on the hardware a bit, provided you're careful: most programmers don't have to squeeze maximal performace out of the hardware, just good enough performance. The extra code you need to make arrays work may not be worth the speed boost. Also, if you're working in an HLL, investigate your implementation details. In Common Lisp, for example, a lot of work has been put into making LLs as fast as possible: If you create a list with QUOTE (such lists are immutable), then thanks to an optimization called CDR-coding, you'll get a data layout very similar to an array under the hood. OTOH, it is important to understand why LL perf isn't actually what the textbooks claim, and to consider using a different structure in contexts where performance matters. Just don't go too far the other way, either: LLs aren't dead just yet.
  - dom0 10y ago
    I believe (intrusive, as they usually are) LLs are so prevalent in C applications mainly because they are the simplest-ever list structure where insertion and deletion of items is just a no-brainer to implement in a couple lines of C macros. They are also inherently self-describing (ie. you don't need to pass around anything except one pointer). And this is totally fine in many places. However, when the list is frequently (ie. performance is relevant) used, then it's likely that a LL is not the right choice. And usually one notices that in these cases no LL is used. For example, one might use a LL for a list of drivers, while eg. directory entries will be kept in a hash-table, tree or trie.

optionalparens 10y ago

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.

wyager 10y ago

Sure, if you need to do hundreds of millions of insertions per second. In the vast majority of real-world use cases, most of your time is going to be spent elsewhere. Spending a microsecond waiting on memory lookups for a cold finger tree isn't going to do much. Drop to using less convenient array-backed structures in the few places you need really fast operations, and use slightly slower (constant-wise) data structures where it's more convenient.

gpderetta 10y ago
> Spending a microsecond waiting on memory that's an eternity!
- wyager 10y ago
  Not if you're writing UI code, networking code, most IO-related code, etc. A microsecond is very small compared to the time penalty you are likely to incur doing any sort of syscall. For the vast majority of code, it's negligible. For tight, fast, repetitive code it is far too slow.

catnaroek 10y ago

Even ignoring real hardware, finger trees are only efficient in an amortized sense where more specialized purely functional data structures offer better real-time guarantees. (0) Asymptotically optimal heaps: Worst-case O(1) insert, merge and findMin. Worst-case O(log n) delete. (1) Asymptotically optimal search trees: Worst-case O(log n) lookup, insert, update, delete. (2) Asymptotically optimal deques: Worst-case O(1) cons, head, tail, snoc, init, last. etc. Another downside is that they require somewhat fancy language features (namely, polymorphic recursion) to implement in a type-safe way.