11–20 of 79 posts
Earlier 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.
>they almost always perform (much) worse. 'Much worse' relative to what exactly?
Earlier 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.
The context here is of course persistent data structures. Linked-lists permit very efficient structural sharing.
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.
Could someone give an example where this data structure would be useful?
You can create a persistent ordered container that has both prepend and append in amortised constant time; and concatenate in log time.
Pagetables are a trie, so it's max log log log time to prepend, append, or concatenate, and usually constant small for two of them (but admittedly: you usually have to pick if you don't know how many arrays you want).
Earlier 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.
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.
You can also map memory before an existing mapping, but it's a bit system-and-platform dependent. (But an entirely feasible thing to do).
Naively you can also grow-and-shift or copy ... the first one is actually incredibly fast due to perfect locality, and also very simple to implement. It's still, technically, O(n^2) when building a list, so it's usually a better idea to go for append-and-reverse (which works outside the actual list implementation). Normally that's not a problem at all, and often no reversal has to be materialized.
Earlier 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.
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.
If you have frequent reads, you can also consider writing your data to a file (or a memfd), and then using mmap to construct the memory layout you want. You will then see that prepend is worse-case log^3 (depth of the pagetable, assuming you have to keep moving the whole thing) time, which is much better than finger trees, and if you prepend often you can make it constant time (by choosing a high start virtual address: remember, there's 64 bits of address but only 48 bits of memory, so you can have 64k big objects without much work) which makes it faster than linked lists.
Another idea: use VMX extensions and collaborate between each layer to trade a lower constant mean and coefficient to parameterise max to log^k. Gains here might require very big data sets though.
interesting...how can this be implemented in a db table queriable with sql?
Earlier 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.
I am not sure if anyone has evaluated using alternatives, but my understanding of why has generally been 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 couldn't find any confirmation (with actual numbers) for this intuition, but this is what I could find:
A 2005 explanation of how intrusive lists work in the Linux kernel: "Linux Kernel Linked List Explained", https://isis.poly.edu/kulesh/stuff/src/klist/
HN submission on intrusive lists in Doom 3: https://news.ycombinator.com/item?id=8795745
And that points to technical note on the optimizations to Doom 3's BFG Edition to get it to perform well on PS3, XBox 360 and PC: http://fabiensanglard.net/doom3_documentation/DOOM-3-BFG-Tec... One of the optimizations was moving from intrusive lists.
I'm quite aware of how inappropriate linked lists are for most applications because of their poor cache locality. I thought the Linux kernel may be a case where linked lists are actually better, but I can't find any numbers or even arguments why they would be.