3 ms·

Intrusive lists are better, sure, but pointer-jumping will still throw away the (absolutely astonishingly large) benefits of the cache, unless you’re careful. A

Intrusive lists are better, sure, but pointer-jumping will still throw away the (absolutely astonishingly large) benefits of the cache, unless you’re careful. And avoiding pointer-jumping is not an automatic win from using intrusive lists — you still need to allocate/lay out your stack conscientiously. And a very similar argument can be made for bounded arrays as an alternative to std::vector. Also, I only skimmed it, but the article seems to ignore the fact that even for an unbounded/growing array like std::vector, the growth strategy does not free+malloc/realloc on each insertion in practice, as the growth strategy will leave unused capacity for future insertions, and in such cases the cost is just memmove (for simple types at least). Maybe I missed that part, but it seems like an important point worth highlighting.

dahart 4y ago
> pointer-jumping will throw away the (absolutely astonishingly large) benefits of the cache, unless you’re careful. Right! Yes, that’s part of my point, STL::list isn’t being careful with cache, or with allocations. Really it just rarely makes sense to even compare STL::list to STL::vector as if they’re otherwise equal choice. Usually the choice is (or should be) driven by constraints, not by which has a slight perf edge, right? Inside a memory manager, use of a vector isn’t usually considered a choice. Maybe it’s possible to build a free page vector, but I think isn’t common, and people usually pay the costs of pointer chasing on the free list because there aren’t practical alternatives. > the <vector> growth strategy does not free+malloc/reallocate on each insertion Yeah very good point. Does STL::list do the same for the container of pointers? I don’t even know, but maybe it can’t, and maybe the primary perf advantage of STL::vector over STL::list is due to vector’s amortized mallocs?
- rhdunn 4y ago
  IIRC, the Borland C++ STL implementation made use of buckets of consecutively allocated entries so you would generally find consecutively inserted items next to each other in memory. You can also define your own allocator that does something similar.
- dundarious 4y ago
  I’d heavily bet against std::list having any kind of “extra capacity” logic, as it would have to be some kind of free list of Node types — best leave that to the general purpose allocator. I think the list vs vector comparison is fair, as most people are taught to “just use the standard library, don’t be a hero, don’t commit a NIH crime”. I have done this myself at times, but in fairness, mostly when discussing adaptations of existing code, where there were bigger structural issues. And it cannot be repeated enough, that vector is far better than list, even at prepends or random insertions, for a surprisingly large number of elements (it was at least thousands of int32-s when I checked it about a decade ago). Typically the justification for a list is that the workload is prepend/random insert heavy, but in my experience there is more often than not a bound on the size that strongly favors vector.
- verall 4y ago
  > Does STL::list do the same for the container of pointers? No, if you want a list with amortized malloc, that's a std::deque
jcranberry 4y ago
It seemed like this person was talking about an intrusive linked list with an arena allocator of some sort, which isn't ideal but still fairly cache friendly.

dahart 4y ago

> pointer-jumping will throw away the (absolutely astonishingly large) benefits of the cache, unless you’re careful. Right! Yes, that’s part of my point, STL::list isn’t being careful with cache, or with allocations. Really it just rarely makes sense to even compare STL::list to STL::vector as if they’re otherwise equal choice. Usually the choice is (or should be) driven by constraints, not by which has a slight perf edge, right? Inside a memory manager, use of a vector isn’t usually considered a choice. Maybe it’s possible to build a free page vector, but I think isn’t common, and people usually pay the costs of pointer chasing on the free list because there aren’t practical alternatives. > the <vector> growth strategy does not free+malloc/reallocate on each insertion Yeah very good point. Does STL::list do the same for the container of pointers? I don’t even know, but maybe it can’t, and maybe the primary perf advantage of STL::vector over STL::list is due to vector’s amortized mallocs?

rhdunn 4y ago
IIRC, the Borland C++ STL implementation made use of buckets of consecutively allocated entries so you would generally find consecutively inserted items next to each other in memory. You can also define your own allocator that does something similar.
dundarious 4y ago
I’d heavily bet against std::list having any kind of “extra capacity” logic, as it would have to be some kind of free list of Node types — best leave that to the general purpose allocator. I think the list vs vector comparison is fair, as most people are taught to “just use the standard library, don’t be a hero, don’t commit a NIH crime”. I have done this myself at times, but in fairness, mostly when discussing adaptations of existing code, where there were bigger structural issues. And it cannot be repeated enough, that vector is far better than list, even at prepends or random insertions, for a surprisingly large number of elements (it was at least thousands of int32-s when I checked it about a decade ago). Typically the justification for a list is that the workload is prepend/random insert heavy, but in my experience there is more often than not a bound on the size that strongly favors vector.
verall 4y ago
> Does STL::list do the same for the container of pointers? No, if you want a list with amortized malloc, that's a std::deque

jcranberry 4y ago

It seemed like this person was talking about an intrusive linked list with an arena allocator of some sort, which isn't ideal but still fairly cache friendly.