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

31–40 of 79 posts

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

#31

Post by qwertyuiop924 »

dom0 wrote: post #7
willtim wrote: post #5

Earlier quoted context omitted.

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.

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

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.

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

#32

Post by geocar »

DanWaterworth wrote: post #29
geocar wrote: post #27

Earlier quoted context omitted.

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.

No, but you also don't have to do that.

One list is traversed when committing blocks, so a linked list was never necessary - just a commit-list (vector of pointers).

Another list is traversed when dequeueing the next lock, so again: a linked list isn't necessary, just a dequeue (which might not have to be serialised).

Another list is traversed when finding the next blocked reader, but again serialisation wasn't required here.

And so on.

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

#33

Post by harpocrates »

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?

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

#34

Post by cjwoodall »

geocar wrote: post #27
scott_s wrote: post #20

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

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... there are better solutions

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

#35

Post by DanWaterworth »

geocar wrote: post #32
DanWaterworth wrote: post #29

Earlier quoted context omitted.

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.

No, but you also don't have to do that. One list is traversed when committing blocks, so a linked list was never necessary - just a commit-list (vector of pointers). Another list is traversed when dequeueing the next lock, so again: a linked list isn't necessary, just a dequeue (which might not have to be serialised). Another list is traversed when finding the next blocked reader, but again serialisation wasn't requi…

I don't know how the kernel is using intrusive lists, but that kind of traversing and switching is occasionally useful.

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

#36

Post by paulgb »

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?

I think you'd have to use a pointer and allocate on the heap. Under the hood I think that's essentially what the compiled Haskell code would do.

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

#37

Post by harpocrates »

Given the number of comments about the inefficiency of finger trees: yes they usually have a high constant factor (for their otherwise reasonable asymptotic complexity) due to cache misses. However, they are immutable and persistent, which means they have efficient sharing, which in turn makes them good candidates for

   * use in multiple threads at once
   * code that needs to be proven correct (I believe the Haskell Data.Sequence implementation is a translated from Coq)

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

#38

Post by geocar »

scott_s wrote: post #30
geocar wrote: post #27

Earlier quoted context omitted.

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?

Not sure exactly what you're asking.

We can evaluate the Linux kernel developers' priorities by benchmarking[1] and assuming they aren't stupid, because if they are stupid, then their opinion doesn't matter, and if they're not and they're not making things faster, then it's because they have other priorities.

That being said, there are a few[2] notable[3] moves away from linked lists that were ostensibly for performance reasons.

[1]: Even crap benchmarks: http://www.phoronix.com/scan.php?page=article&item=linux-44-...

[2]: https://lkml.org/lkml/2016/8/1/164

[3]: https://lkml.org/lkml/2008/4/1/458

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

#39

Post by [deleted] »

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?

[deleted]

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

#40

Post by geocar »

DanWaterworth wrote: post #35
geocar wrote: post #32

Earlier quoted context omitted.

No, but you also don't have to do that. One list is traversed when committing blocks, so a linked list was never necessary - just a commit-list (vector of pointers). Another list is traversed when dequeueing the next lock, so again: a linked list isn't necessary, just a dequeue (which might not have to be serialised). Another list is traversed when finding the next blocked reader, but again serialisation wasn't requi…

I don't know how the kernel is using intrusive lists, but that kind of traversing and switching is occasionally useful.

Yes. It is occasionally useful.

However when you have the right data structure, you'll find you won't need it.

Benchmarking is important because searching for the right data structure is time consuming (expensive for the programmer) and it's usually not necessary.

Post reply on HN