Graphics Reference
In-Depth Information
Chapter
13
Optimization
It is widely acknowledged that the most important optimizations to be made are
high-level algorithmic changes. However, selecting the most appropriate algorithms
for a task is but one thing. Algorithms rely on good underlying data structures whose
efficiencies, in turn, are dependent on the target machine architecture. To complete
the coverage of efficient data structures and algorithms, this chapter deals with a
number of remaining issues related to tuning for target architectures, vital to making
a production-quality collision detection system.
Recently, program efficiency could be effectively measured by counting the num-
ber of arithmetic operations performed and multiplying these by the execution time
of each operator. Nonalgorithmic code optimizations therefore tended to focus on
reducing the number of instructions executed or replacing instructions with equiva-
lent but faster instructions. Although these optimizations still have some value, today
two entirely different types of optimizations clearly stand out from the rest:
memory
optimization
and optimizations utilizing
parallelism
.
Over the last several generations of CPUs, processor speeds have increased faster
than memory access times have decreased. It is expected that this trend will continue.
As such, if processes are not already, the likelihood of their becoming memory access
bound is increasing at a rapid pace.
To help reduce this problem, CPU manufacturers are incorporating one or more
levels of fast cache memory to sit between main memory and the CPU. These effec-
tively implement a memory hierarchy in which higher but slower levels are only
accessed if data cannot be found in the faster but smaller lower levels.
The introduction of cache memory greatly improves the situation, but alone does
not serve to fully bridge the speed gap; it is still important that performance-sensitive
code be written specifically to take advantage of this memory hierarchy. Because
compilers have no or limited knowledge of the memory hierarchy, it is up to pro-
grammers to take advantage of it by explicitly implementing memory optimizations.
511
