3 ms·

std::map will often have better cache coherence, especially if you're using a custom allocator or have a small data set. Also not sure what you mean when you s

std::map will often have better cache coherence, especially if you're using a custom allocator or have a small data set. Also not sure what you mean when you say operator new never overflows. Can you elaborate? It would be nice if C++ gave an operator new/allocator that put the object on the end of a page boundary so that the hardware could catch any overflows. Sort of like how the atomic operators are cross platform but hardware specific.

kllrnohj 9y ago
> std::map will often have better cache coherence std::map is a red-black tree. It will have among the worst cache coherence of anything. Do you have any supporting benchmarks? And if you have a small enough data set then std::vector will run circles around any map anyway. > Also not sure what you mean when you say operator new never overflows. Can you elaborate? size_t mySize = ...; int* myptr = (int*) malloc(mySize * sizeof(int)); int* myptr2 = new int[mySize]; What happens when mySize is >= 1073741824 on a 32-bit system? Hint: the malloc version has a security bug, the new one doesn't.
- nzmsv 9y ago
  If mySize is computed at runtime, that computation should most likely be checking for overflow. If it is a constant, declare it constexpr and get a compile-time warning for the overflow. In any case, it's the multiplication that has a bug, not malloc (though I agree that the usage you mention is unfortunately common).
  - kllrnohj 9y ago
    Yes it's the multiplication that has the bug, but malloc makes that error common as you said. An API whose usage commonly has trivial security bugs is not a good API. new just wholesale avoids that common category of bugs, so why would you avoid it in favor of malloc? They do the same thing, one just does it safer.
- eco 9y ago
  Boost, loki, and I'm sure others have a "flat" map which is just an array backed ordered map. Slower insertions than the red-black map but because of the cache locality it's much faster overall.

kllrnohj 9y ago

> std::map will often have better cache coherence std::map is a red-black tree. It will have among the worst cache coherence of anything. Do you have any supporting benchmarks? And if you have a small enough data set then std::vector will run circles around any map anyway. > Also not sure what you mean when you say operator new never overflows. Can you elaborate? size_t mySize = ...; int* myptr = (int*) malloc(mySize * sizeof(int)); int* myptr2 = new int[mySize]; What happens when mySize is >= 1073741824 on a 32-bit system? Hint: the malloc version has a security bug, the new one doesn't.

nzmsv 9y ago
If mySize is computed at runtime, that computation should most likely be checking for overflow. If it is a constant, declare it constexpr and get a compile-time warning for the overflow. In any case, it's the multiplication that has a bug, not malloc (though I agree that the usage you mention is unfortunately common).
- kllrnohj 9y ago
  Yes it's the multiplication that has the bug, but malloc makes that error common as you said. An API whose usage commonly has trivial security bugs is not a good API. new just wholesale avoids that common category of bugs, so why would you avoid it in favor of malloc? They do the same thing, one just does it safer.
eco 9y ago
Boost, loki, and I'm sure others have a "flat" map which is just an array backed ordered map. Slower insertions than the red-black map but because of the cache locality it's much faster overall.