C++ Appendices

Back to C++ Optimization Techniques
Appendix A: STL Container Efficiency

Container	Stores	Overhead	[ ]	Iterators	Insert	Erase	Find	Sort
list	T	8	n/a	Bidirect'l	C	C	N	N log N
deque	T	12	C	Random	C at begin or end; else N/2	C at begin or end; else N	N	N log N
vector	T	0	C	Random	C at end; else N	C at end; else N	N	N log N
set	T, Key	12	n/a	Bidirect'l	log N	log N	log N	C
multiset	T, Key	12	n/a	Bidirect'l	log N	d log (N+d)	log N	C
map	Pair, Key	16	log N	Bidirect'l	log N	log N	log N	C
multimap	Pair, Key	16	n/a	Bidirect'l	log N	d log (N+d)	log N	C
stack	T	n/a	n/a	n/a	C	C	n/a	n/a
queue	T	n/a	n/a	n/a	C	C	n/a	n/a
priority_ queue	T	n/a	n/a	n/a	log N	log N	n/a	n/a
slist	T	4	n/a	Forward	C	C	N	N log N

C = amortized constant time

Overhead indicates approximate per-element additional heap space required in bytes. Based on the version of the STL that shipped with Visual Studio 6.0.

Inserting at the end of a vector may cause the vector to be resized; resizing a vector is O(N). However, the amortized time complexity for vector insertions at the end is constant.

slist included for comparison only. Singly-linked lists are not standard STL containers.

Appendix B: Relative Costs of Common Programming Operations

The following table was calculated on an Xbox (PIII-733). The nice thing about profiling on the Xbox is that an application is guaranteed to be running in kernel mode with no other tasks interfering with sampling. This table shows performance relative to a standard 32-bit assignment operation (value 1.00). Larger numbers indicate better performance. A value of 2.0 would be twice as fast as 32-bit assignment. A value of 0.5 would be twice as slow. Statistical error is +/-0.1

Relative Performance of Common Operations (PIII-733)
	8-bit (char)		16-bit (short)		32-bit (long)		64-bit (__int64)		floating-point
Operation	signed	unsigned	signed	unsigned	signed	unsigned	signed	unsigned	float	double	ldouble
a = b	0.6	0.5	0.5	0.6	1.0	1.0	0.8	0.8	1.0	0.8	0.8
a + b	1.0	1.0	1.0	1.0	1.0	1.0	0.9	0.8	1.0	1.0	0.6
a - b	1.0	1.0	1.0	1.0	1.0	1.0	0.8	0.8	1.0	0.6	1.0
-a	1.0	1.0	1.2	1.0	1.0	1.2	0.9	0.9	1.0	1.0	0.6
++a	0.5	0.5	0.5	0.5	1.0	0.9	0.8	0.8	0.9	0.6	0.6
--a	0.5	0.6	0.5	0.5	1.0	1.0	0.8	0.8	0.9	0.3	0.6
a * b	1.0	1.0	1.0	1.0	1.0	1.0	0.5	0.5	1.0	1.0	0.5
a / b	0.4	0.4	0.4	0.4	0.4	0.3	0.1	0.1	0.4	0.3	0.4
a % b	0.4	0.4	0.4	0.4	0.4	0.3	0.1	0.1	n/a	n/a	n/a
a == b	0.6	0.6	0.6	0.6	0.6	0.6	0.5	0.5	0.5	0.5	0.3
a != b	0.6	0.6	0.6	0.6	0.6	0.6	0.5	0.5	0.5	0.4	0.5
a > b	0.6	0.6	0.6	0.6	0.6	0.6	0.5	0.5	0.5	0.5	0.4
a < b	0.6	0.6	0.6	0.6	0.6	0.6	0.5	0.5	0.5	0.4	0.5
a >= b	0.6	0.6	0.6	0.6	0.6	0.5	0.5	0.5	0.5	0.5	0.4
a <= b	0.6	0.6	0.6	0.6	0.6	0.6	0.5	0.5	0.5	0.4	0.5
a && b	0.6	0.6	0.6	0.6	0.6	0.6	0.5	0.5	n/a	n/a	n/a
a \|\| b	0.6	0.5	0.5	0.6	0.5	0.6	0.5	0.6	n/a	n/a	n/a
!a	0.6	0.6	0.6	0.6	0.6	0.6	0.6	0.5	0.5	0.5	0.5
a >> b	1.0	1.0	1.0	1.0	1.0	1.0	0.7	0.7	n/a	n/a	n/a
a << b	1.0	1.0	1.0	1.0	1.0	1.0	0.7	0.7	n/a	n/a	n/a
a & b	1.0	1.0	1.0	1.0	1.0	1.0	0.8	0.8	n/a	n/a	n/a
a \| b	1.0	1.0	1.0	1.0	1.0	1.0	0.9	0.8	n/a	n/a	n/a
a ^ b	1.2	1.0	1.0	1.0	1.0	1.0	0.8	0.8	n/a	n/a	n/a
~a	1.0	1.0	1.0	1.0	1.2	1.0	0.9	0.9	n/a	n/a	n/a

In general, 32-bit values give the fastest times. That's why it makes sense to use int or long as your standard integer type.

The slowest operations are division and modulus. In fact, floating-point division is as fast or faster than integer division.

Float operations are typically 1.5 to 2 times faster than double operations. If you can afford the loss of precision, float is the best floating-point type.

Another thing to be aware of is the cost of converting between types. The baseline case is the "conversion" from a 32-bit signed int to another 32-bit signed int.

	int32 to int32	int8 to int32	int32 to int8	double to int32	int32 to double	int32 to int64
PII	1.0	1.0	1.0	0.1	0.8	0.7
Pentium	1.0	0.8	0.7	0.2	0.6	0.7

Most conversions are reasonable. But beware the conversion of floating-point to integer! It's five to ten times slower than the base case. Interestingly enough, it's also significantly slower on the Pentium-II compared to the Pentium.

Appendix C: Code Tuning and C++ Efficiency Resources
C.1: Books

Effective C++ and More Effective C++, Scott Meyers (www.aristeia.com) Superb tips from a C++ guru, from basic techniques to copy-on-write and multiple dispatch. The chapter on efficiency in More Effective C++ is a gem.

Code Complete, Steve McConnell (www.construx.com) General purpose code-tuning strategies, with examples and results.

Graphics Programming Black Book Special Edition, Michael Abrash (www.amazon.com) The bible on x86 assembly optimization, especially for 3D graphics.

Graphics Gems I - V, Glassner, et al. (www.graphicsgems.org) Efficient algorithms designed by graphics programmers and researchers.

C.2: Websites

SGI STL extensions (www.sgi.com/tech/stl)

SGI Singly-linked lists A non-standard list class. The SGI implementation has half the overhead and is considerably faster than the standard list class.

SGI Rope strings A highly efficient implementation of long strings. Useful for e-mail text, word processing, etc.

SGI Hashed containers Hashed containers are not included in the STL. These SGI hashed containers can be just what the doctor ordered.

Todd Veldhuizen articles (extreme.indiana.edu/~tveldhui)

Todd has been on the leading edge of the use of C++ templates for the sake of efficiency, especially Template Metaprogramming. He's also the lead programmer for Blitz++, a computing library that makes use of many of his techniques.

Nathan Myers articles (www.cantrip.org)

Nathan is a prolific writer on many C++ topics. Be sure to see his article on the Empty Member optimization.

Guru of the Week (www.gotw.ca)

Problems and solutions to many common C++ issues, as presented by one of the lead programmers of PeerDirect, Inc, including Avoiding Temporaries, Inline, Reference Counting and Copy On Write.

Object-Oriented System Development (gee.cs.oswego.edu/dl/oosdw3/ch25.html) The Performance Optimization chapter from Dennis de Champeaux's book.

NULLSTONE Compiler Optimization Categories (www.nullstone.com/htmls/category.htm) A good list and description of C/C++ compiler optimization techniques.

Back to C++ Optimization Techniques