Performance of Sequence Types Relative to vtkCollection

Win32 MSVS 7.1 2003

	Insert Front (10000)¹	Insert Back (10000)¹	Insert Index (5000)¹	Replace Index (10000)¹	Remove Front (5000)¹	Remove Back (5000)¹	Remove Index (5000)¹	Remove Range (5000)¹	Remove Object (5000)¹	Remove Duplicates (1000×10)²	Remove All (5000)¹
Collection	na	1.000	na	1.000	1.000	1.000	1.000	1.000	1.000	1.000	1.000
Deque	1.000	1.244	10.966	0.015	0.402	0.005	22.141	0.040	15.502	6.642	0.602
List	1.714	1.890	1.000	2.544	1.327	0.019	2.320	0.068	4.117	1.168	0.674
Vector	5710.008	2.473	17.311	0.014	1042.698	0.006	45.041	0.132	18.619	6.226	0.122
Set ³	4.384	4.736	0.042	10.944	1.697	9.730	9.535	0.107	0.027	0.006	0.643

Linux i386 gcc 3.3.3

	Insert Front (10000)¹	Insert Back (10000)¹	Insert Index (5000)¹	Replace Index (10000)¹	Remove Front (5000)¹	Remove Back (5000)¹	Remove Index (5000)¹	Remove Range (5000)¹	Remove Object (5000)¹	Remove Duplicates (1000×10)²	Remove All (5000)¹
Collection	na	1.000	na	1.0000	1.0000	1.0000	1.000	1.000	1.000	1.000	1.000
Deque	2.200	1.429	3.657	0.004	1.0000	0.004	9.453	0.010	8.704	2.038	0.000
List	1.000	0.714	1.000	2.691	0.666	0.002	3.091	0.010	1.165	1.153	0.500
Vector	3439.168	0.857	3.030	0.003	476.927	0.001	7.570	0.020	3.522	1.580	0.000
Set ³	4.400	3.286	0.756	1.735	0.667	1.465	1.463	0.010	0.008	0.003	0.500

Note: Lower numbers ≡ less CPU time ≡ higher performance. All numbers are relative.

slowest	slower	slow	≅	fast	faster	fastest

Highlights

• Sequences (list, deque, and vector) allow random access insertion.
• 50 - 1000 times faster removal of items from the end of the sequence.
• 50 - 300 times faster assignment (replacement) of items to deque and vector sequences.
• 10 - 100 times faster removal of subranges.
• Sets are optimized for fast searching of objects and allow access by object 30 - 300 times faster than other types.
• Use of the Reserve() method can increase the performance of initial object addition to vectors.
• Performance of all other operations is nearly equivalent to vtkCollection (except front operations on vectors).
• The higher perfomance of vtkContainers types on Linux versus Win32 platforms is likely due to the default allocator implementations of their respective C++ STL libraries. This disparity may be addressable in the future by use of an optimized custom allocator.