A better hash table: GCC

As a continuation of our previous entry in the performance of various implementations of C++ unordered associative containers, Thomas Goyne has run the measurement test suite in GCC 4.8.2 for Mac with the default standard library libstdc++-v3 and release settings -O3 -std=c++11. The machine used was a OS X 10.9.1 box with an Intel Core i7-3720QM running at 2.6GHz with Turbo Boost and SpeedStep disabled. Results are depicted below.

Insertion without rehashing, unique elements.

Insertion with rehashing, unique elements.

Insertion without rehashing, duplicate elements, F_max = 1, G = 5.

Insertion without rehashing, duplicate elements, F_max = 5, G = 5.

Insertion with rehashing, duplicate elements, F_max = 1, G = 5.

Insertion with rehashing, duplicate elements, F_max = 5, G = 5.

Erasure, unique elements.

Erasure, duplicate elements, F_max = 1, G = 5.

Erasure, duplicate elements, F_max = 5, G = 5.

Successful lookup, unique elements.

Unsuccessful lookup, unique elements.

Successful lookup, duplicate elements, F_max = 1, G = 5.

Unsuccessful lookup, duplicate elements, F_max = 1, G = 5.

Successful lookup, duplicate elements, F_max = 5, G = 5.

Unsuccessful lookup, duplicate elements, F_max = 5, G = 5.

Some general insights:

• Insertion times are very similar among the three libs for unique elements. As for the case of duplicate elements, the group skipping capabilities of Boost.Unordered and Boost.MultiIndex, while greatly improving lookup performance, do have a noticeable negative impact on insertion times.
• On the other hand, libstdc++-v3 performs surprisingly well in erasure with duplicate elements, despite its having to do bucket traversal to locate the node preceding the one to be erased. I don't have a clear explanation for this fact besides attributing it to a better CPU cache behavior due to element nodes in libstdc++-v3 being smaller (as this lib does not store hash values if these can be calculated on the fly): maybe readers can propose alternative interpretations.
• Boost.Multiindex highest locality shows up very clearly in its excellent lookup performance for unique elements.

At a later entry we will study libstdc++-v3, libc++, Boost.Unordered and Boost.MultiIndex in Clang.