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


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

Benchmark result


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.

Copyright (C) 2012 Hitoshi Yamauchi
Most recent update : :