Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

staff.city.ac.uk

Post reply on HN
Print view View original

61–70 of 79 posts

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

#61

Post by scott_s »

stuckagain wrote: post #24
jstimpfle wrote: post #4

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

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.

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

#62

Post by raphlinus »

I looked at finger trees as a possible basis for the string representation in xi-editor, but ended up going with a simpler b-tree based approach. The better asymptotic bounds for doing manipulations at the ends are appealing in theory, but I never saw an actual problem with the O(log n) cost in practice, and it is possible to optimize the common append-only case a lot (I have a "builder" API but the current implementation is not as heavily optimized as it might be).

I _believe_ that the polymorphic recursive type, easily expressible in Haskell, cannot be expressed in Rust. You'd fake it by just using trees and having the shape as an invariant maintained by the library (just as the min and max child count constraint is maintained in a B-tree). I personally think that's fine, Rust wouldn't be a better language if its type system was made even more rich, but it's interesting to have examples so you know where the edges are. (there's also the possibility someone will find a way to encode it anyway)

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

#63

Post by rbehrends »

jstimpfle wrote: post #4
traviswatkins wrote: post #2

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.

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

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

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

#64

Post by gpderetta »

chii wrote: post #14
geocar wrote: post #12

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

except when you want fast prepending.

deques support fast prepending. You can implement them on top of shared memory, although as the canonical implementation is block based and uses indirection for access, the dynamic resizing capability is less useful.

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

#65

Post by gpderetta »

wyager wrote: post #50
traviswatkins wrote: post #2

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.

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 structu…

> Spending a microsecond waiting on memory

that's an eternity!

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

#66

Post by keith_analog »

A few years ago, our research group published a data structure, called Chunked Sequence, that is similar to the Finger Tree. In short, Chunked Sequence features the same asymptotic profile as does Finger Tree (neglecting persistence) and, in addition, offers strong guarantees with respect to constant factors. Very roughly speaking, Chunked Sequence is to Finger Tree what b-tree is to red-black tree.

We've implemented Chunked Sequences as a package of C++ header files and provided source code on github. To the client, Chunked Sequence looks like STL deque, but with additional methods to allow split at a specified position and concatenate, both in logarithmic time. The operations which push and pop on the ends of the Chunked Sequence are approximately as fast as those of STL deque, and in certain use patterns much faster.

http://deepsea.inria.fr/chunkedseq/

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

#67

Post by osivertsson »

keith_analog wrote: post #66

A few years ago, our research group published a data structure, called Chunked Sequence, that is similar to the Finger Tree. In short, Chunked Sequence features the same asymptotic profile as does Finger Tree (neglecting persistence) and, in addition, offers strong guarantees with respect to constant factors. Very roughly speaking, Chunked Sequence is to Finger Tree what b-tree is to red-black tree. We've implemented…

Cool.

But please provide clear licensing information (preferably a permissive free software license). Right now I can't find anything at all about what terms you are releasing this source code under.

Therefore most people will be unable to use it, which is a shame.

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

#68

Post by IgorPartola »

scott_s wrote: post #60
dom0 wrote: post #51

Earlier quoted context omitted.

> An OS kernel has no business maintaining, and even less business accessing in bulk, large data structures that are performance-critical enough to worry about coherent memory access File systems are usually part of the kernel.

File systems tend not to have large data structures. They are relatively modest data structures which manage bulk access to large blocks of data. A subtle distinction, but important in this context.

Really? Even huge volumes with loads of tiny files? Mail and Usenet servers? Build servers? What is your definition of large and modest here?

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

#69

Post by wyager »

gpderetta wrote: post #65
wyager wrote: post #50

Earlier quoted context omitted.

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 structu…

> Spending a microsecond waiting on memory that's an eternity!

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.

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

#70

Post by zerofan »

mamcx wrote: post #45
geocar wrote: post #12

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

Where I can find info about pagetable trie?

I'm interested too. I've been thinking about the idea, and it seems like you'd have to be sure to re-use the hell out of your file descriptor on /dev/zero (otherwise, you could easily run out of file descriptors). It also seems like you're trading cache misses for system calls if you have to re-map pages a lot. Maybe it's a clear win, but I'd like to understand it better.
Post reply on HN