6 ms·

This isn't a linked list issue at all, but a problem with constructing the nodes. If you construct list nodes in a contiguous location cache misses are a non i

This isn't a linked list issue at all, but a problem with constructing the nodes. If you construct list nodes in a contiguous location cache misses are a non issue.

estebank 7y ago
That's no longer a linked list, it's a vector.
- deleted 7y ago
  [deleted]
- mikepurvis 7y ago
  I think the argument is that if the nodes are fixed size then you can preallocate a big block of them slab-style, and for the pointers you just use indexes into that array rather than "real" pointers. Potentially there's a small memory savings as well if you can use 2 or 4 bytes for the index instead of a full 8 byte pointer. But you're taking on a lot of complexity and tuning by going this route so you'd really have to test and make sure the gains were worth it.
  - viraptor 7y ago
    A bigger saving is in the allocation metadata. Every time you allocate something on the heap, you also need to save information about the size, maybe some flags and padding to align on a page. And if the entries are small, you also get better cache locality. Putting things in an array works around all of that (unless you need to handle tombstones)
    - Dylan16807 7y ago
      A reasonable allocator should already be grouping allocations of similar size together. In a whole lot of cases this means your metadata is no more than a single byte per object, and the padding is no more than you'd have inside an array.
      - viraptor 7y ago
        True, it really depends on the allocator.
mikepurvis 7y ago
But that's fundamentally a function of the usage pattern. If the usage is "construct a bunch of nodes" and then nothing, then you should be using a vector-type structure anyway. The promise of a linked list is being able to iterate and make constant-time insertions/deletions wherever you want. But the more such mutations occur, the more fragmented your memory will end up, and the more you'll get hit by the cache issues—especially if your list is large, exactly where the purported benefits of a linked list are strongest.
- Jasper_ 7y ago
  > If the usage is "construct a bunch of nodes" and then nothing, then you should be using a vector-type structure anyway. Not if the nodes are variable-sized.
  - mikepurvis 7y ago
    Again it depends a lot on the usage pattern. If you're going to be dereferencing a pointer off to some allocated-elsewhere object on every little operation or comparison then sure. But if there are sorts or searches or other operations that can take place against a fixed-size "index" object, then it may still make sense to have a vector-like or pre-allocated pool of those objects and only pay the cache hit cost when you do major operations on a particular instance. Which is really just the cache doing its job. The linked-list anti-pattern is when you're constantly paging in big speculative chunks of memory only to access a single pointer and then move on.

This isn't a linked list issue at all, but a problem with constructing the nodes. If you construct list nodes in a contiguous location cache misses are a non issue.

estebank 7y ago

That's no longer a linked list, it's a vector.

deleted 7y ago
[deleted]
mikepurvis 7y ago
I think the argument is that if the nodes are fixed size then you can preallocate a big block of them slab-style, and for the pointers you just use indexes into that array rather than "real" pointers. Potentially there's a small memory savings as well if you can use 2 or 4 bytes for the index instead of a full 8 byte pointer. But you're taking on a lot of complexity and tuning by going this route so you'd really have to test and make sure the gains were worth it.
- viraptor 7y ago
  A bigger saving is in the allocation metadata. Every time you allocate something on the heap, you also need to save information about the size, maybe some flags and padding to align on a page. And if the entries are small, you also get better cache locality. Putting things in an array works around all of that (unless you need to handle tombstones)
  - Dylan16807 7y ago
    A reasonable allocator should already be grouping allocations of similar size together. In a whole lot of cases this means your metadata is no more than a single byte per object, and the padding is no more than you'd have inside an array.
    - viraptor 7y ago
      True, it really depends on the allocator.

mikepurvis 7y ago

But that's fundamentally a function of the usage pattern. If the usage is "construct a bunch of nodes" and then nothing, then you should be using a vector-type structure anyway. The promise of a linked list is being able to iterate and make constant-time insertions/deletions wherever you want. But the more such mutations occur, the more fragmented your memory will end up, and the more you'll get hit by the cache issues—especially if your list is large, exactly where the purported benefits of a linked list are strongest.

Jasper_ 7y ago
> If the usage is "construct a bunch of nodes" and then nothing, then you should be using a vector-type structure anyway. Not if the nodes are variable-sized.
- mikepurvis 7y ago
  Again it depends a lot on the usage pattern. If you're going to be dereferencing a pointer off to some allocated-elsewhere object on every little operation or comparison then sure. But if there are sorts or searches or other operations that can take place against a fixed-size "index" object, then it may still make sense to have a vector-like or pre-allocated pool of those objects and only pay the cache hit cost when you do major operations on a particular instance. Which is really just the cache doing its job. The linked-list anti-pattern is when you're constantly paging in big speculative chunks of memory only to access a single pointer and then move on.