interesting...how can this be implemented in a db table queriable with sql?
This account has been posting a lot of unsubstantive, off-topic comments. Please stop and read the guidelines:
Finger Trees: A Simple General-Purpose Data Structure (2006)
41–50 of 79 posts
Re: Finger Trees: A Simple General-Purpose Data Structure (2006)
#42Earlier quoted context omitted.
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 performa…
You provided a reason for why the kernel does a certain thing (easier to code; performance in those places doesn't matter). I was asking if this was your understanding based on inference (your understanding of the performance trade offs in general combined with the fact things are done a certain way) or from fact (claims made directly by kernel developers, or experiments).
Re: Finger Trees: A Simple General-Purpose Data Structure (2006)
#43Earlier quoted context omitted.
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.
When you need that kind of behaviour, you can't replace it with something flat (without doing binary searches or similiar at each crossing). Sometimes intrusive lists are the right thing.
I built something once that used intrusive skiplists because it needed to expire elements using one ordering and search them by another. It would have been much less efficient if I'd have broken it up into multiple flat representations.
(Actually, it was flat, but explaining that aspect of it is quite difficult).
Re: Finger Trees: A Simple General-Purpose Data Structure (2006)
#44This 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?
When traversing the tree, I think you'll need at least one branch/virtual method dispatch to determine the type of the child node.
Given that, you could create a templated subclass for each type in the grammar, then instantiate it with the number of children. Eg:
template class Node : TODO { type 'N'; int const count N; Node a[N]; }
Allocating Node is a single malloc. You can add static asserts to get things like Node to fail at compile time, change the c style array to std::array to get bounds checks, and so on.
At that point, you can get arbitrarily fancy with custom allocators, inlining the type to be stored in the tree, etc.
[edit: Note that my solution kinda sucks, because you need to pay for a virtual method dispatch to run code that has N compiled in, and I also rolled my own reflection with instance variables, so I'm bloating each node by two words instead of one, and also breaking constant propagation in the caller code.
Removing the implicit vtable or the extra instance variables is an exercise left to the reader.]
Re: Finger Trees: A Simple General-Purpose Data Structure (2006)
#45Earlier quoted context omitted.
The context here is of course persistent data structures. Linked-lists permit very efficient structural sharing.
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?
Re: Finger Trees: A Simple General-Purpose Data Structure (2006)
#46Earlier 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.
You can reduce some linked list operations (including multi-element ones) to a single CAS, which is often good enough.
Re: Finger Trees: A Simple General-Purpose Data Structure (2006)
#47Earlier quoted context omitted.
> 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…
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.
Re: Finger Trees: A Simple General-Purpose Data Structure (2006)
#48Earlier 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.
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.
Re: Finger Trees: A Simple General-Purpose Data Structure (2006)
#49The 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…
Looking at Haskell's Data.Sequence, it looks like it's strict in its elements. So a delete does free up memory as long as the deleted object isn't being used somewhere else.
Re: Finger Trees: A Simple General-Purpose Data Structure (2006)
#50Finger 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 structures where it's more convenient.