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

51–60 of 79 posts

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

#51

Post by dom0 »

HelloNurse wrote: post #48
cjwoodall wrote: post #34

Earlier quoted context omitted.

Linked-Lists often get used in low-level code and embedded systems in situations where you might need multiple statically allocated entries to be turned into a list of unknown length. There certainly are times where this comes in useful, but it is also a memory constrained space with an emphasis on determinism, where malloc and new can be bad ideas. There is a time and a place for them, but if you need speed I agree.…

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. It is also an infrastructure-deprived environment in which swapping around pointers to implement a linked list with correct locking is relatively easy to get right but allocating vectors is out of the question.

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

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

#52

Post by KingMob »

markc wrote: post #22
rohmbus wrote: post #3

Could 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: https://github.com/clojure/data.finger-tree

Just want to add that the data structure behind all of Clojure's default data types are finger trees.

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

#53

Post by qwertyuiop924 »

dom0 wrote: post #47
qwertyuiop924 wrote: post #31

Earlier quoted context omitted.

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…

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

...sounds about right.

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

#54

Post by KingMob »

rohmbus wrote: post #3

Could someone give an example where this data structure would be useful?

They're excellent general purpose structures for data sharing of immutable data (e.g., a slightly-changed copy shares much of the same data as the original). Clojure uses them extensively, since immutable data has the nice property of being thread-safe by default.

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

#55

Post by skishore »

harpocrates wrote: post #33

This is a fun data structure to implement in Haskell, and I've always been curious about how one would do it in C++, largely due to the fact that data FingerTree a = Empty | Single a | Deep (Digit a) (FingerTree (Node a)) (Digit a) Has polymorphic recursion in the last case. What would be the C++ approach for dealing with this sort of thing? Pass in a compile time integer to represent the level of nesting?

The polymorphic recursion allows for compile-time checking of the invariant that "the left and right wings at depth n are 2-3 trees of depth n". In C++, I think you would forgo a compile-time check of that invariant and just write code that maintains it instead.

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

#56

Post by zbuf »

scott_s wrote: post #20
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.

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…

> memory efficiency. If you allocate a Foo, you also allocate everything you need for Foo to be on all of the lists it may appear on.

I can't speak for the kernel developers, but for the same line of reasoning it may be more significant that there is the lack of error paths.

When you allocate an 'object', further changes of state (eg. added or removal to other lists) in its lifetime can be done without the possibility of running out of memory or address space. This can be a huge benefit to overall program structure in certain types of application.

In contrast, addition or removal to a vector or flat list can ultimately require various actions to happen.

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

#57

Post by catnaroek »

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.

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.

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

#58

Post by catnaroek »

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.

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.

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

#59

Post by detrino »

catnaroek wrote: post #58
stuckagain wrote: post #24

Earlier quoted context omitted.

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.

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.

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.

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

#60

Post by scott_s »

dom0 wrote: post #51
HelloNurse wrote: post #48

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. It is also an infrastructure-deprived environment in which swapping around pointers to implement a linked list with correct locking is relatively easy to get right but allocating vectors is out of the question.

> 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.
Post reply on HN