Graphics Reference
In-Depth Information
in the first place, that it is not being stored redundantly, and whether it can be
stored using a smaller data type. Simple run-length encoding schemes may also be
effective.
Data locality can be improved by redesigning algorithms and data structures to
allow data to be accessed in a more predictable, often linear or partially linear, fashion.
Improving data locality may also involve a process often referred to as blocking :
breaking large data into smaller chunks that each fit into cache.
At a lower level, the idea is to touch as few cache lines as possible, and therefore
to arrange data such that all or most words on touched cache lines are being used
at the same time. An example would be the separation of collision detection data
from rendering data to avoid having RGB colors, texture coordinates, and other data
irrelevant to collision detection reduce data locality by being interleaved with ver-
tices and other relevant data. The following subsections discuss these issues in more
detail.
13.3.1 Structure Optimizations
A starting point for improving data cache use is to look at how structures and classes
can be optimized in this respect. Three options present themselves.
Decrease the overall size of the structure. By not using more bits than necessary
to represent member fields, more data fit into a cache line and the number of
memory fetches required to access structure fields is reduced.
Reorder fields within the structure. Fields within a structure are usually grouped
conceptually, but should really be grouped on access patterns so that those
typically accessed together are stored together.
Split structures into hot and cold parts. Often a few structure fields are being
accessed much more frequently than the other fields. By moving the infre-
quently accessed fields (the cold part) into a separate structure, cache coherency
increases among the frequently accessed ones (the hot part), in particular
when the structure is part of an array or some similar conglomerate data
structure.
Alignment requirements on many platforms enforce compilers to pad structures
so that any N -byte fields are N -byte aligned (for example, 32-bit integers aligned
to memory addresses evenly divisible by four). The structures are padded to align
their size to be a multiple of their largest N -byte field, wasting even more memory.
Sorting the member variables by decreasing size reduces the memory waste due
to padding. To aid in detecting space waste, some compilers can provide warnings
whenever a class or structure is padded (in gcc , for example, through the -Wpadded
option).
Search WWH ::




Custom Search