5 ms·
No, the ZeroMQ author should be writing idiomatic code in whatever language he is using. In his blog post, he complains that std::list<widget* > causes 2 alloc
by mihai_ionic 13y ago
No, the ZeroMQ author should be writing idiomatic code in whatever language he is using.
In his blog post, he complains that std::list<widget* > causes 2 allocations per insertion.
Fine, because that's not idiomatic C++. The C++ way would be to use std::list<widget>, since there's no need for the extra indirection.
Note that this would only be a good choice if you for some reason really need a list, std::vector is mostly preferred due to its better cache behaviour and requires even fewer allocations.
Secondly, if he needs to remove list items by their address, there's no reason he couldn't use an intrusive list in C++. The article I linked shows an implementation of one, and there's always boost::intrusive::list if you don't want to roll your own (and you shouldn't).
- rumcajz 13y agoExtra 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)