Hacker News Reader

Comment by alexchamberlain | Hacker News Reader

Unfortunately, the complexity argument is generally bullshit and you really need to profile. It turns out multiple very respected authors have found under a typical work load, `vector` performs very well on a lot of machines.

View on HN

Never traversing the list. Removal every time a peer disconnects.

Removal with intrusive containers: flip two pointers.

Removal with std::vector<>: copy all the subsequent items in the vector one position backwards.

Since you never traverse the list, the order of elements obviously doesn't matter. In that case, you can just swap the element to remove with the last element.

A vector will still give you better cache-locality and also amortize the number of allocations.

Yes, that's exaclty what ZeroMQ is doing. Then check how the code looks like. It's a mess. Intrusive containers deliver same performance characteristics and the code actually looks clean.

And what stops you using an intrusive datastructure in C++?

Nothing. But if he is going to write C in C++, then what is the point of writing C++? Especially sticking to C gives substantially increased flexibility in terms of language bindings, embedded usage etc.

I've probably spent more years writing C++ code than C code, but I'm all with him on this - if what you need to do for whatever reason don't need/benefit all that much from C++ when accounting for all constraints, then choosing C as being the lowest common denominator between other languages is a very good choice for a library.

Ever tried removing element from a middle of vector?

Yes, the world does not end. For small objects and `vector`s, it's probably quicker, because 1) you found it quicker due to cache locality and 2) there were no system calls to release memory.

So, what you say is: I don't care to implement an efficient solution, because the CPU cache will fix it anyway. That way of thinking is well known as "The Java way of problem solving" (TM)

That's not what he said, and his solution is not "inefficient." CPUs have no emotions; if it runs faster due to cache, it's simply the better solution.

For the use case required by ZeroMQ, it's faster in all cases, because swap-with-last and shrink is O(1). Sure, if CPUs didn't have caches, a list might be faster.

Do you see where this is going? The C way of solving problems consists of adding one more level of indirection (ever heard of 3-star C programmers?), because it becomes more efficient asymptotically that way. Nevermind the hidden factor of 100-1000 due to pipeline stalls and cache misses.

Fortunately not all C programmers think that way.

My solution is more efficient in the normal case, ignoring the asymptotic case that never happens.

Reply on news.ycombinator.com