A mini STL performance Benchmark

A mini STL performance benchmark (Nihongo, In Japanese)

Sometimes a measured STL performance is needed in addition to big O notation information. This page has a few of such result. I hope this is a good starting point. Hitoshi

Each class of C++ STL (Standard template library) has big O notation for the performance indicator, but the real implementation sometimes affected by the invisible constant factor. Still big O notation helps when we choose the algorithm a lot, I was sometimes surprised how large this constant factor (e.g., random access performance of dqueue).
Therefore I sometimes measured some code performance under a specific environment and a specific circumstances. The effect of constant factor is depends on problem size and environment. Before, I just made such programs and trash them. However, even its depends on the problem and environment, I found those results are useful and put this to somewhere on the Web space. If you want to use this, you need to compare your problem and environment, and adjust, or re-measure the performance when you needed. This benchmark is just a starting point. If you didn't aware the difference between your problem and this code, this only generate garbage. Although, I hope this measurement shown here would be useful to start with. All the source code are also available in this page for your adjustment. Hitoshi

License

New BSD License. http://en.wikipedia.org/wiki/BSD_licenses

Benchmark result

Environment

CPU: Intel(R) Core(TM) i7-2720QM CPU @ 2.20GHz
OS: 3.2.0-29-generic #46-Ubuntu SMP Fri Jul 27 17:03:23 UTC 2012 x86_64 x86_64 x86_64 GNU/Linux
Compiler: gcc (Ubuntu/Linaro 4.6.3-1ubuntu5) 4.6.3
Compiler option: -O6 -DNDEBUG -fomit-frame-pointer -fexpensive-optimizations -fschedule-insns2 -finline-functions -funroll-loops -fPIC -march=native
Elapsed time is measured by gettimeofday() system call. The source code is StopWatch.hh
The resulting numbers may of course differ depends on various reasons. For instance, if your CPU is faster, the result may differ. These are just indicators.

`std::map` creation and copy (`perf_map_copy.cpp`)

Number of iterations = 100000 and averaged elapsed times are shown.

Key size
50 keys	14 micro seconds (1.4x10^-6 sec)
100 keys	33 micro seconds (3.3x10^-6 sec)

Comment: I have a function that consumes a few millisecond. I use std::map to report the resulting status. Now I know the status report doesn't cost too much. I was afraid this copy took most of the time. I also bind this creation and copy to boost::python. The overhead is one more copy and creation to get information to python interpreter. (boost 1.48)

Median computation: nth_element() vs sort() (`perf_nth_element.cpp`)

Number of iterations = 100000. (each operation is performed 100000 times the elapsed times are shown.)

Array size	sort	nth_element
4096	4.20 sec	1.18 sec
8192	8.98 sec	2.30 sec
16384	19.2 sec	4.59 sec
32768	40.9 sec	9.32 sec
65536	88.1 sec	18.7 sec

Comment: I need to compute median for a rather small array. The nth_element is faster as expected.

Performance comparison between `set` and `hash_set`. (`perf_set_hash_set.cpp`)

Number of items = 1000000. (One million insertion, then one million find test, then remove test.) The elapsed times are shown.

Method	set	hash_set
insert()	7.31 sec	922 millisec
find()	4.95 sec	255 millisec
erase()	2.12 sec	301 millisec

Comment: If you see the input sequence in the code, it is just a continuous sequence. This is quite artificial sequence. You should test on your typical input sequence. My preference is set() although all the result is slower than hash_set. Since you can fool any hash function and you can find quite pathetic case, even randomized method. Instead of that, set has less surprise. Actually, our customer is good at to find the pathetic case. We can fix somehow the pathetic case of hash function, but, we don't know our customer could find another unexpected pathetic case. If our software has a similar bug many times, then, our relationship between customer becomes worse.