7 ms·

The context here is of course persistent data structures. Linked-lists permit very efficient structural sharing.

by willtim 10y ago

geocar 10y ago
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.
- chii 10y ago
  except when you want fast prepending.
  - dom0 10y ago
    There are many strategies to deal with that efficiently. Eg. negative indices (having memory before index 0), append-and-reverse. 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.
  - geocar 10y ago
    If you know the format you want, and read infrequently, just implement it as an append and read it backwards. 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.
  - gpderetta 10y ago
    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.
- willtim 10y ago
  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.
  - geocar 10y ago
    Give up sequential! :) If you want queues, and you can give up sequential, then you can get huge gains[1] in performance. Specific use cases will have better specific solutions. [1]: e.g. https://github.com/cameron314/concurrentqueue https://github.com/cameron314/concurrentqueue
  - hedora 10y ago
    You can reduce some linked list operations (including multi-element ones) to a single CAS, which is often good enough.
- scott_s 10y ago
  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 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/ https://isis.poly.edu/kulesh/stuff/src/klist/ HN submission on intrusive lists in Doom 3: https://news.ycombinator.com/item?id=8795745 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-Technical-Note.pdf 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.
  - geocar 10y ago
    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.
    - DanWaterworth 10y ago
      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.
      - 10y ago
- mamcx 10y ago
  Where I can find info about pagetable trie?
  - zerofan 10y ago
    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.
    - geocar 10y ago
      No need for /dev/zero: Linux has memfd[1] and OSX has vm_remap[2]. You only need one file descriptor per heap because Linux lets you poke holes with fallocate[3]. I'll define objects with a header that looks roughly like this: struct header { off_t phys; size_t len; int localrefs; short flags; char mstrategy, type; }; phys is the offset in the heap file descriptor. len is the number of units and type is indexed into an array of unit sizes. mstrategy is used to select the bucket size (allocated range is a power of two, so 1<<(mstrategy&31)) and the heap number. localrefs is an optimisation which I'll get to. If I want to allocate an array of type t, size n, I can use a BSR[4] to identify the bucket that it needs, and see if there's anything on the free list. If there isn't, I can see if I can split a larger bucket into two parts (this is effectively Knuth's buddy allocator). I know that (mstrategy&31) < BSR(page size) needs to be moved just like the classical allocator for appending or prepending, but when (mstrategy&31) >= BSR(page size) I can take a virtual address of a bigger region, then either mmap the memfd (using phys) or vm_remap the region into the bigger region. Instead of copying the contents of the pages, the operating system will simply copy the page table (which is 3 levels deep[5], hence the log log log, although using 1G pages means log log with a lower coefficient). This is a tremendous win for problems that need to deal with several large arrays. Now localrefs gives me a further optimisation: In-process, I can track the reference count of objects, and if my functions always consume their arguments I know inside the grow/append/prepend routine if this is the only holder of the object. If it is, I can potentially reuse this virtual address immediately, saving 3-4 syscalls. When it's time to deallocate, I can put small objects on my free list, and garbage collect any big objects by calling fallocate() on the physical address to poke a hole (freeing system memory). OSX doesn't need fallocate() because mach has vm_unmap. [1]: https://dvdhrm.wordpress.com/2014/06/10/memfd_create2/ https://dvdhrm.wordpress.com/2014/06/10/memfd_create2/ [2]: http://web.mit.edu/darwin/src/modules/xnu/osfmk/man/vm_remap.html http://web.mit.edu/darwin/src/modules/xnu/osfmk/man/vm_remap... because the osx manual page is pants [3]: http://man7.org/linux/man-pages/man2/fallocate.2.html http://man7.org/linux/man-pages/man2/fallocate.2.html [4]: http://x86.renejeschke.de/html/file_module_x86_id_20.html http://x86.renejeschke.de/html/file_module_x86_id_20.html [5]: http://wiki.osdev.org/Page_Tables#Long_mode_.2864-bit.29_page_map http://wiki.osdev.org/Page_Tables#Long_mode_.2864-bit.29_pag... > It also seems like you're trading cache misses for system calls if you have to re-map pages a lot Cache misses aren't the dominant force here. The real trade off is illustrated with benchmarking: memcpy one page, versus 8 bytes (page table entry). How many pages do you need to copy before it is faster to pay the fixed (<100ns) cost of the system call and just copy the page table entries? Memory streams at a rate of around 10GB/sec, but the TLB flush is ~100ns and the memory latency is only around 10ns, so it's easy to see how quick the gains add up when you're using 1GB pages.

The context here is of course persistent data structures. Linked-lists permit very efficient structural sharing.

by willtim 10y ago

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.

chii 10y ago
except when you want fast prepending.
- dom0 10y ago
  There are many strategies to deal with that efficiently. Eg. negative indices (having memory before index 0), append-and-reverse. 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.
- geocar 10y ago
  If you know the format you want, and read infrequently, just implement it as an append and read it backwards. 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.
- gpderetta 10y ago
  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.
willtim 10y ago
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.
- geocar 10y ago
  Give up sequential! :) If you want queues, and you can give up sequential, then you can get huge gains[1] in performance. Specific use cases will have better specific solutions. [1]: e.g. https://github.com/cameron314/concurrentqueue https://github.com/cameron314/concurrentqueue
- hedora 10y ago
  You can reduce some linked list operations (including multi-element ones) to a single CAS, which is often good enough.
scott_s 10y ago
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 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/ https://isis.poly.edu/kulesh/stuff/src/klist/ HN submission on intrusive lists in Doom 3: https://news.ycombinator.com/item?id=8795745 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-Technical-Note.pdf 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.
- geocar 10y ago
  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.
  - DanWaterworth 10y ago
    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.
    - 10y ago
mamcx 10y ago
Where I can find info about pagetable trie?
- zerofan 10y ago
  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.
  - geocar 10y ago
    No need for /dev/zero: Linux has memfd[1] and OSX has vm_remap[2]. You only need one file descriptor per heap because Linux lets you poke holes with fallocate[3]. I'll define objects with a header that looks roughly like this: struct header { off_t phys; size_t len; int localrefs; short flags; char mstrategy, type; }; phys is the offset in the heap file descriptor. len is the number of units and type is indexed into an array of unit sizes. mstrategy is used to select the bucket size (allocated range is a power of two, so 1<<(mstrategy&31)) and the heap number. localrefs is an optimisation which I'll get to. If I want to allocate an array of type t, size n, I can use a BSR[4] to identify the bucket that it needs, and see if there's anything on the free list. If there isn't, I can see if I can split a larger bucket into two parts (this is effectively Knuth's buddy allocator). I know that (mstrategy&31) < BSR(page size) needs to be moved just like the classical allocator for appending or prepending, but when (mstrategy&31) >= BSR(page size) I can take a virtual address of a bigger region, then either mmap the memfd (using phys) or vm_remap the region into the bigger region. Instead of copying the contents of the pages, the operating system will simply copy the page table (which is 3 levels deep[5], hence the log log log, although using 1G pages means log log with a lower coefficient). This is a tremendous win for problems that need to deal with several large arrays. Now localrefs gives me a further optimisation: In-process, I can track the reference count of objects, and if my functions always consume their arguments I know inside the grow/append/prepend routine if this is the only holder of the object. If it is, I can potentially reuse this virtual address immediately, saving 3-4 syscalls. When it's time to deallocate, I can put small objects on my free list, and garbage collect any big objects by calling fallocate() on the physical address to poke a hole (freeing system memory). OSX doesn't need fallocate() because mach has vm_unmap. [1]: https://dvdhrm.wordpress.com/2014/06/10/memfd_create2/ https://dvdhrm.wordpress.com/2014/06/10/memfd_create2/ [2]: http://web.mit.edu/darwin/src/modules/xnu/osfmk/man/vm_remap.html http://web.mit.edu/darwin/src/modules/xnu/osfmk/man/vm_remap... because the osx manual page is pants [3]: http://man7.org/linux/man-pages/man2/fallocate.2.html http://man7.org/linux/man-pages/man2/fallocate.2.html [4]: http://x86.renejeschke.de/html/file_module_x86_id_20.html http://x86.renejeschke.de/html/file_module_x86_id_20.html [5]: http://wiki.osdev.org/Page_Tables#Long_mode_.2864-bit.29_page_map http://wiki.osdev.org/Page_Tables#Long_mode_.2864-bit.29_pag... > It also seems like you're trading cache misses for system calls if you have to re-map pages a lot Cache misses aren't the dominant force here. The real trade off is illustrated with benchmarking: memcpy one page, versus 8 bytes (page table entry). How many pages do you need to copy before it is faster to pay the fixed (<100ns) cost of the system call and just copy the page table entries? Memory streams at a rate of around 10GB/sec, but the TLB flush is ~100ns and the memory latency is only around 10ns, so it's easy to see how quick the gains add up when you're using 1GB pages.