6 ms·

It has also been pointed out that these problems are not intrinsic to C++, but rather due to the way he was using it: http://www.codeofhonor.com/blog/avoiding-g

It has also been pointed out that these problems are not intrinsic to C++, but rather due to the way he was using it: http://www.codeofhonor.com/blog/avoiding-game-crashes-related-to-linked-lists http://www.codeofhonor.com/blog/avoiding-game-crashes-relate...

rumcajz 13y ago
The above is a great post BTW. I recommend reading it.
willvarfar 13y ago
Aha, you mean that he should have written idiomatic C code and compiled it with a C++ compiler?
- _pmf_ 13y ago
  > Aha, you mean that he should have written idiomatic C code and compiled it with a C++ compiler? Henceforth, I'll be using this quip whenever debating C++ fan boys; thanks!
- mhd 13y ago
  Even the code in the article makes heavy use of C++ features (templates, resource management) and that's not even talking about the Boost intrusive library that gets mentioned, which is knee-deep in template effluvial... Never mind that I've seen plenty of C code with wrapping structs for data structures, too. Intrusive vs. non-intrusive is a design choice in both languages.
- 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 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 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 ago
        Ever tried removing element from a middle of vector?
        alexchamberlain 13y ago
        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.
        burstmode 13y ago
        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)
        mihai_ionic 13y ago
        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.
alexchamberlain 13y ago
The post is interesting, but is there anything stopping you using the following... template<typename T> struct Link { T obj; Link *link; } That looks pretty much like the intrusive version in memory, right?
- mihai_ionic 13y ago
  The point of intrusive lists is to allow access to the link when you provide only the contained object. The way you're thinking of would theoretically work, but you'd have to make sure the compiler isn't adding fancy padding that would break your pointer manipulation and type casting. boost::intrusive::list on the other hand, works in a type-safe manner by having your class either inherit a list hook, or provide it as member and then pass the list implementation a member pointer as template parameter so that it can be accessed.

rumcajz 13y ago

The above is a great post BTW. I recommend reading it.

willvarfar 13y ago

Aha, you mean that he should have written idiomatic C code and compiled it with a C++ compiler?

_pmf_ 13y ago
> Aha, you mean that he should have written idiomatic C code and compiled it with a C++ compiler? Henceforth, I'll be using this quip whenever debating C++ fan boys; thanks!
mhd 13y ago
Even the code in the article makes heavy use of C++ features (templates, resource management) and that's not even talking about the Boost intrusive library that gets mentioned, which is knee-deep in template effluvial... Never mind that I've seen plenty of C code with wrapping structs for data structures, too. Intrusive vs. non-intrusive is a design choice in both languages.
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 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 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 ago
      Ever tried removing element from a middle of vector?
      - alexchamberlain 13y ago
        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.
        burstmode 13y ago
        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)
        mihai_ionic 13y ago
        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.

alexchamberlain 13y ago

The post is interesting, but is there anything stopping you using the following... template<typename T> struct Link { T obj; Link *link; } That looks pretty much like the intrusive version in memory, right?

mihai_ionic 13y ago
The point of intrusive lists is to allow access to the link when you provide only the contained object. The way you're thinking of would theoretically work, but you'd have to make sure the compiler isn't adding fancy padding that would break your pointer manipulation and type casting. boost::intrusive::list on the other hand, works in a type-safe manner by having your class either inherit a list hook, or provide it as member and then pass the list implementation a member pointer as template parameter so that it can be accessed.