massive allocation perf difference between Win8, Win7 and linux.

That's right. I'm aware that Win8 has many improvements at kernel level, and maybe it is just a cognitive bias, but it seems that it is palpable at user level. better scheduling reactivity notably.

But here, we're talking about allocating 30k integers, this is exactly the kind of things malloc does, and not the OS. malloc reserves blocks from the system in huge chunks, using virtual alloc, or NT heap manager. Then it uses its famous binning/ordered freelist stuff to return the small blocks to the caller never issuing a system call, or the least as possible.

Therefore, if difference there is, it should be in the CRT. That was my reasoning.

edit: AllEightUp (you posted while I wrote). Yes I'm sure, you can check on the topic I linked the crazy difference between O0 and O3.

But here, we're talking about allocating 30k integers, this is exactly the kind of things malloc does, and not the OS.

Without seeing the test's code is hard to draw any conclussion.

Most benchmarks out there are completely useless.

Why? Because implementations are very different (it's not just the compilers). For example MS' vector implementation grows the vector by 1.5x every time it reaches the capacity. Default GCC's implementation grows the vector by 2.0x. So, if you didn't reserve all the space beforehand, a test where lots of pushes are made to a vector, GCC will always be the clear winner because it overestimates compared to MS' implementation, and therefore will perform less reallocations. That doesn't mean it will perform as well on a real world case.

Likewise, map implementations are optimized for different things (lookup, traversal, erasures, insertions, runtime error correction / safety checks). But even if we compare all that, implementations can be optimized for large structures or short structures.

An implementation optimized for short structures means std::map will perform faster; while an implementation optimized for large structures means std::map where sizeof(MyStruct) and/or sizeof(AnotherStruct) is large (i.e. bigger than 64 bytes) will perform faster.

Last, but not least; yes, it's not hard to make an implementation that beats the one provided by your compiler tool suite that solve your particular need. These implementations are first coded for correctness and safety. Then, if there's time or if a lot of devs are demanding it, it gets optimized.

Until recently GCC's std::shared_ptr was a using a big fat mutex. The latest version uses atomic/interlocked instructions. It's really hard to get the latter correct, so it needs a lot of planning, and a lot of testing. Likewise, MS std::chrono implementation leaves much to be desired. All of this because, like everything else, standard library writers are hit by time constraints and meeting deadlines; and their libraries are generic that have to work for everybody without crashing or exhibiting incorrect behavior.

This goes against the general knowledge that the STL is unbeatable and you can always trust it. Trust it? Yes. Fastest? Well most game developers sooner or later learn it the hard way this is not always true. There's a reason EA created the EASTL library many years ago.

Well, you can easily look directly at the allocation and see if that's the issue.

Allocation is pretty slow and deletion even slower, on many OSes. But I think there is more going on than that. The STL implementation on windows vista is particularly pathetic. I got some dumb flames here in the past showing similar benchmarks.

The STL implementation on windows vista is particularly pathetic. I got some dumb flames here in the past showing similar benchmarks.

Maybe you got flamed because there is no such thing as the "STL implementation on windows vista"?

The STL implementation on windows vista is particularly pathetic. I got some dumb flames here in the past showing similar benchmarks.

Maybe you got flamed because there is no such thing as the "STL implementation on windows vista"?

Not to pedants anyway.

Actually, the issue is that there really is no such thing as the Vista STL (or standard library). The STL ships with the compiler so if you install VS2005 on Vista you get the VS2005 STL and if you install VS2013 you get the VS2013 STL.

Without seeing the test's code is hard to draw any conclussion.

All the code is available http://sourceforge.net/p/cgenericopenaddresshashmap/code/ci/master/tree/

But its true it was in the other thread sorry.

Beginning with Windows XP, the low fragmentation heap (LFH) is available, and beginning with Vista it is the default. To mitigate against buffer overrun attacks, it has been made "non-deterministic" with Windows 8.

Which means that the memory locations returned by the allocator under Windows 8 follow a considerably different pattern compared to Windows 7 (see e.g. this writeup). Also, on every Windows version, the same program can be made to perform significantly differently by calling one API function (enabling or disabling the LFH, and playing with the serialization flag, etc.).

So, to answer your question, yes, the allocator is significantly different. Now why is it 5-20 times faster? We can only guess, but factors of 5 to 20 smell of cache or VM effects (doing one test in debug build and the other in release is another common reason, but you said you used the very same executable on two machines -- so that's not it). My gut feeling is that your "random deletes" just happen to play better, by coincidence, with the "random addresses" that the allocator gave you for consecutive elements. As compared to the strictly linear addresses for consecutive elements that the Windows 7 allocator would give you.

So maybe, on the average, this turns out in 10-20% fewer cache misses and 1-2% fewer page faults, but since these have such a huge impact compared to everything else, you see them as 5-20x speedup.

Actually, the issue is that there really is no such thing as the Vista STL (or standard library). The STL ships with the compiler so if you install VS2005 on Vista you get the VS2005 STL and if you install VS2013 you get the VS2013 STL.

The problem with that theory is that since at least Windows 2000, Windows has shipped with multiple implementations of the C standard library. Of the one's that are officially documented, there's the version implemented in msvcrt.dll, which is actually the Visual C++ 6 C standard library implementation, and there's the version implemented in the POSIX subsystem/Windows services for Unix. They are definitely different implementations, as the way they handle file names are different. However the chances are pretty good that any program that you ran would end up using none of them in favor the the C standard library implementation of the compiler, which was usually specific to the compiler version. So MSVC 7 had it's own C standard library implementation, and so did MSVC 7.1, and so on.

(I understand that, officially, since Windows 8, you can no longer assume that any copy of the C runtime is distributed along with the OS, and you must distribute your own. However, a clean installation of Windows 8 still seems to have that msvcrt.dll file. This may be prep work for a later version of Windows, where they deprecate it but don't actually remove it until later.)

mscrt.dll version 7.0.10130.0 is still present on Windows 10 10130... I don't think MS want to screw gazillions of enterprise system due a single dll removal.. Starting with MSVC 14 however they re-organized (again) the VC-CRT implementation http://blogs.msdn.com/b/vcblog/archive/2014/06/10/the-great-crt-refactoring.aspx

mscrt.dll version 7.0.10130.0 is still present on Windows 10 10130... I don't think MS want to screw gazillions of enterprise system due a single dll removal

No Sir, not going to happen.

Can you believe iterating over a map is 170 times slower on gcc/linux than on VS12/Win8.1 ? 'the heck ?? (actually for this one I suspect an optimizer joke)

new episode in the weirdness, I counted the blocks allocated on the linux version of the test, and here it is:

std vector: 21
reserved vector: 1
*open address: 44
*reserved openaddr: 2
std unordered: 999788
std map: 999771

== 1 million int pushes ==
std vector:             7.99805 ms
reserved vector:        4.16898 ms
*open address:          16.5275 ms
*reserved openaddr:     14.9709 ms
std unordered:          22.5586 ms
std map:                145.302 ms


== 100k random erasures ==
*openaddr:              5040.85 ms
std unordered:          2.38067 ms
std map:                14.1778 ms


== 1M iteration ==
*openaddr:              4.60644 ms
std unordered:          2.55456 ms
std map:                13.0115 ms


== 50k random finds among 1M contenance ==
*openaddr:              0.584305 ms
std unordered:          0.712742 ms
std map:                6.75083 ms

Which is all of a sudden looks very similar to the Win8 figures. I guess I'll have to re-run the whole thing again everywhere now.

Also, we can see the monstrous impact of the dumb fix I provided for the "anti clumps orphaning" using the "delete" flag per entry (the 5040.85ms figure). Without maintenance the hash map becomes polluted with deleted flags and all find operations become O(N). This is very unlikely to happen in real life scenario, but still I'll work on a "garbage collection" technique, like google did in their dense map.

clang++ gives almost equivalent results, all proportions are conserved, only 5% slower in all tests or something. so it wasn't much due to an optimizer or stdlib difference, but rather a benchmark bug, due to rand() implementation differences.

Now that we brought linux to the level of Win8, and apparently even faster; will the rand() stuff explain the Win7 behavior too ? I'll check that when I can. to be continued