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

 

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

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