Hacker News Reader

Comment by dahart | Hacker News Reader

> STL list […] the mallocs cost will still be greater.

This is a narrow view of the costs of the STL::list container class, not of linked lists in general.

Linked lists are at their best when they are internal storage, meaning the links are part of the class being stored, in order to prevent unnecessary mallocs. STL::list is an external storage container, which automatically compromises some of the potential benefits of a linked list. Linked lists are also best when you don’t malloc to build the list at all, but maintain things already in memory. Linked lists are best used in places where using vectors is impractical or impossible, like the insides of a memory manager.

I don’t feel like timing many inserts using STL::list says a lot about linked lists at all, and what it does say is mostly focusing on the wrong things. Definitely use vector when you can, especially if you’re just comparing container classes.

View on HN

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.

> 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?

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.

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.

> 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

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.

Yeah I was taken aback when they talked about “linked lists” and instead of banging out a simple linked list they used an STL container that isn’t necessarily optimized for the use case. It’s malloc-heavy and uses full sized pointers instead of indices. There’s a lot more to the array vs list argument than this.

STL list is great because it the only STL structure you can insert into without potentially invalidating iterators and references since it doesn't call resize. If you want a performant list-alike, you use a deque.

Reply on news.ycombinator.com