5 ms·
Unfortunately, the complexity argument is generally bullshit and you really need to profile. It turns out multiple very respected authors have found under a typ
by alexchamberlain 13y ago
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.
- rumcajz 13y agoEver tried removing element from a middle of vector?
- alexchamberlain 13y agoYes, 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.
- burstmode 13y agoSo, 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)
- mihai_ionic 13y agoThat'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.
- alexchamberlain 13y agoMy solution is more efficient in the normal case, ignoring the asymptotic case that never happens.
- deleted 13y ago[deleted]
- rumcajz 13y agoNever 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.
- mihai_ionic 13y agoSince 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.
- rumcajz 13y agoYes, 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.
- alexchamberlain 13y agoAnd what stops you using an intrusive datastructure in C++?
- vidarh 13y agoNothing. 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.