Hacker News Reader

Comment by Negitivefrags | Hacker News Reader

Before you consider intrusive lists, in fact, before you consider almost any other data structure, try a vector.

People grossly overestimate the cost of vector relocation while underestimating the benefits of cache coherency. Vector relocation is so cheap because all the bits are in the cache. You can relocate all the elements in a reasonably sized vector faster than you can dereference a pointer to somewhere in memory that isn't in cache.

If you want log(n) lookup like a set/map you can keep the vector sorted. If you want fast erase (and don't care about order) you can move the last element to the middle and resize down by one (no memory allocation).

The <algorithm> header makes these operations trivial.

C++11 move semantics mean that there are a lot of types you can keep by value in a vector that you wouldn't have before and they stay fast.

View on HN

Vector is a fine data structure, but doesn't do the same job.

The purpose of intrusive linked lists is to provide constant time, allocation-free insert/remove from multiple sequences that all refer to the same object (identity, not value), given only a pointer to the object.

Multiple vectors obviously don't provide this, since vectors contain objects by value. Multiple vectors of pointers can work, but then removal requires either an iterator or a linear scan for each vector. If your object is in many lists at once, that gets pretty messy.

In particular the way that game engines use this, with objects packed in preallocated arrays, gives constant time insertion and deletion from multiple sequences with absolutely zero allocation or copying at any time. Vectors simply do not provide this functionality.

The only problem with std::vector is that you can only belong to one (unless you have a vector of pointers, but that almost negates the whole point).

The way I've typically done this is by having one global "all entities" std::vector and then lists, maps or whatever for specific subsets.

Usually, my "entity" object is little more than a container for behaviours so in reality its a little more complicated than that...

Traversing a vector of pointers isn't much less efficient than traversing an intrusive linked list, and is significantly more efficient than traversing a normal linked list. With a vector of pointers, you need to do an arithmetic operation (usually on a register), a dereference to L1 cache (to fetch the pointer), and a dereference to main memory (to fetch the object). With an intrusive linked list, it's just a dereference to main memory. With a normal linked list, it's 2 dereferences to main memory, one for the link and one for the object. On most processors, accessing cache and performing address arithmetic takes a tiny fraction of the time that accessing RAM does, so for practical purposes your vector-of-pointers and intrusive linked list implementations should be pretty similar in performance.

If you can own the objects in one by-value vector, that's even better, then traversing over them involves only address arithmetic on objects that are already probably in the cache.

You forgot insertion and removal, which intrusive lists provide in constant time and vectors do not.

If you can own the objects, linked list (of any kind) is usually not appropriate. The essence of the efficiency of an intrusive linked list is that the same indirection that must point at an object that is not owned is reused to give the list structure. Without this trick, linked lists are not much good.

Again, you're not getting the point. Constant time != "fast", it just has to do with how the operation scales with N. The point, though counter intuitive, is that the constant time of the list operation is larger than the linear time of the vector operation for many values of N.

> The point, though counter intuitive, is that the constant time of the list operation is larger than the linear time of the vector operation for many values of N.

Citation needed. The kernel guys in particular would probably be interested in a faster alternative to intrusive linked lists.

Keep in mind that we're talking about vectors of pointers due to the problem domain (multiple lists of potentially large or polymorphic objects), so using vectors won't really help locality.

Given a pointer to an object, remove from an intrusive list is three memory accesses: only tiny vectors will give faster operations than that.

Insertion favors intrusive lists even more: allocation and copy free!

Sure, but an ordered list with O(1) removal by an element reference is pretty damn useful (as indirectly confirmed by an abundance of lists in the Linux kernel).

Excellent response, and it's also why the standard class called "List" in many toolkits (Delphi and .Net for e.g.) are equivalent to a C++ vector - essentially a smart array with capacity management ( http://msdn.microsoft.com/en-us/library/y52x03h2.aspx ).

I agree, although I have never had a performance bottleneck related to std::list that required a move to std::vector. Do you know at what point std::set becomes more optimal (in some dimension) than std::vector?

Bjarne Stroustrop showed in a presentation a while back that std::list never becomes more optimal than std::vector regardless of size.

Edit: Sorry, I read your comment incorrectly. Instead of std::set I would use a sorted vector without thought for anything up a thousand elements or so. After that it's probably worth profiling. Vector is probably still good even quite a good way after that depending on your use case.

> Bjarne Stroustrop showed in a presentation a while back that std::list never becomes more optimal than std::vector regardless of size.

Until memory fragments and you can't allocate a contiguous block for a big vector.

64bit memory spaces are pretty hard to fragment to that degree, but it could be a concern on smaller embedded systems still.

If memory serves me right, even on 64bit, the standard malloc won't allow you to grab a chunk larger than about 2G. You can still have as many chunks as you like, but you can't have a single chunk larger than that. Of course, you can always use a different memory manager.

Depends on your platform, libc version, compiler, etc. Anything recent should default to just passing through to mmap for allocations that are a small multiple of page size or larger, and on 64bit systems you can happily mmap huge regions.

It's the physical memory that fragments, not the virtual address space. So it's about the amount of physical memory available, not address sizes.

He said big vectors. You're talking about sub-page fragmentation.

Big vectors inherently avoid sub-page fragmentation because they're allocated directly via mmap. The only thing that matters is having unreserved address space, and 64bit gives you a lot.

What you say is true for a worst case load of millions of vectors that are larger than half of the mmap threshold size (typically roughly page size or a small multiple of it). So this might just be a semantic disagreement, but I don't think of millions of 3KB vectors as 'big' vs a smaller number of MB or GB vectors.

Reply on news.ycombinator.com