8 ms·
Extra indirection is needed when the objects are non-assignable, e.g. if there's a thread running inside the object, if it owns a fd or similar. std::vector has
by rumcajz 13y ago
Extra indirection is needed when the objects are non-assignable, e.g. if there's a thread running inside the object, if it owns a fd or similar. std::vector has O(n) complexity for a lot of operations, so it's not an option.
- alexchamberlain 13y agoUnfortunately, 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.
- mihai_ionic 13y agoIf you can use C++11, this becomes a non-issue with move semantics. Ownership of internal resources can be transferred, and emplace_back even allows constructing your object in place. As others said, the O(n) really becomes more like pseudo-O(1) due to cache effects unless you have elements the size of your cache lines (in which case prefetching still helps) or you're only fetching one element at a time and then triggering a context switch (as in a scheduler). I'm not bashing your library, and if you prefer to use C then that's great, but it's kind of unfair to blame it on the language in the first place.
- rumcajz 13y agoLanguages are designed for specific purposes. I am claiming that C++ is not the best language for system development. The fact that most OSes are not written in C++ is a good indication of the fact. Still, C++ is great for rapid development & corporate development.
- pjmlp 13y ago> The fact that most OSes are not written in C++ is a good indication of the fact. This is just inertia and only true on UNIX world due to how C is tied to UNIX. BeOS, Symbian, Genode -> C++ Mac OS X -> drivers are done in C++ (IOKit) Windows -> C is now official deprecated and C++ is the way to go. (http://herbsutter.com/2012/05/03/reader-qa-what-about-vc-and-c99/ http://herbsutter.com/2012/05/03/reader-qa-what-about-vc-and... && Herb's remarks at BUILD 2012)