A howl on the wind…

(Old version from 2010-04-02)

A performance comparison of the speed of operations on the various set implementations used in C++. There are 16383 unique elements across which 1000000 insert, lookup, iterate, and erase operations are performed.

The raw tick numbers are shown and table sorting is enabled so you can compare for yourself. Just be aware that the Mac OS X, Linux, and Windows numbers cannot be compared against each other.

The full source is available in svn as a CMake project for easy cross-platform testing.

Sources

• Containers:
  • std::set, std::unordered_set, boost::unordered_set – the usual general purpose suspects.
  • CG3::sorted_vector, std::vector based replacement for std::set. Suitable for small amounts of cheap objects, such as integers.
  • CG3::sorted_deque, rubbish version of sorted_vector.
  • CG3::interval_vector, specialized for storing integers that form intervals.
  • sti::sset, skip-list based std::set replacement. Wouldn’t compile with g++ or clang++.
• Ticks counted via cycle.h (local mirror)
• Source: CMake Project: benchmarks, primary source set.cpp

Mac OS X: XCode 4.3, clang++ 3.1

• Compiler: XCode 4.3, clang++ 3.1 -std=c++0x -stdlib=libc++ -O3
• Arch: OS X 10.7.3, 2.3 GHz Core i5, 8 GiB RAM

Key: uint32_t

	Insert	Lookup	Iterate	Erase
std::set	263377455	280869275	629193	24794998
std::unordered_set	69234450	52675799	185231	34318200
boost::unordered_set	49441452	32667162	225394	16729997
CG3::interval_vector	40434068	8892613	33479	36881367
CG3::sorted_vector	262565585	228177623	22030	41777348
CG3::sorted_deque	403703304	407397083	42919	57932190

Key: std::string

	Insert	Lookup	Iterate	Erase
std::set	710009400	623014613	710719	66799492
std::unordered_set	184303900	177911933	392600	58224362
boost::unordered_set	169343324	156496891	413544	25611101
CG3::sorted_vector	2035974542	672658549	42854	1478839543
CG3::sorted_deque	1526059111	881353234	66730	820882673

Windows: MSVC++ 2010

• Compiler: MSVC++ 2010 _SECURE_SCL=0
• Arch: Windows 7 64 bit, 1.60GHz Core i7 Q720, 8 GiB RAM

Key: uint32_t

	Insert	Lookup	Iterate	Erase
std::set	308429302	304766618	792654	52157740
std::unordered_set	211156528	77160207	103594	75309750
boost::unordered_set	50913566	29416608	231071	8599725
CG3::interval_vector	58368478	5381654	43992	54982686
CG3::sorted_vector	420581376	194377831	18774	49828559
CG3::sorted_deque	1504499129	447390205	236772	709469976
sti::sset	198637236	182523436	56072	33885912

Key: std::string

	Insert	Lookup	Iterate	Erase
std::set	729799112	723706519	822293	103106061
std::unordered_set	284964030	126582958	326229	90685117
boost::unordered_set	171111019	158247330	505998	15771730
CG3::sorted_vector	1531939079	759340481	40570	1318279702
CG3::sorted_deque	2119973384	1096972945	245567	1162315971
sti::sset	491187944	478022190	87020	90344926

Linux: GNU g++ 4.6.2

• Compiler: GNU g++ 4.6.2 -std=c++0x -O3
• Arch: VirtualBox on the Windows machine, VT-x, Arch Linux, kernel 3.2.6-2-ARCH, 1 GiB RAM

Key: uint32_t

	Insert	Lookup	Iterate	Erase
std::set	292122486	268873033	856301	26172092
std::unordered_set	25526100	21605752	161217	19461025
boost::unordered_set	40030522	33341628	170637	5748189
CG3::interval_vector	39249255	5226395	34244	40209203
CG3::sorted_vector	195784144	173578001	11908	34183587
CG3::sorted_deque	301030888	279937870	24960	46249722

Key: std::string

	Insert	Lookup	Iterate	Erase
std::set	920886561	923209106	929793	82456296
std::unordered_set	156828854	149179589	465402	65240381
boost::unordered_set	157720131	161853426	386127	14208955
CG3::sorted_vector	1457335009	1002124880	97574	788909210
CG3::sorted_deque	1470338616	1119832233	107800	485375053

Subscribe to the comments through RSS Feed