6.3. Optimize Data Layout
After making sure the program is algorithmically optimal, we
turn to memory related optimization areas. The first such area is
to ensure that data is laid out in memory in an optimal way.
Generally speaking, data needs to be packed to utilize memory
well. It also needs to be sorted in such a way as to utilize
spatial reuse. With spatial reuse, we mean that data being used in
the same code context should be placed next to each other.
The following situations are but some that can cause wasted space
in cache lines:
-
Internal alignment gaps. The compiler needs to obey rules that tell
which addresses certain data types can reside on. This can cause
subsequent variables or fields in a record to be allocated with
unused data in between. Sorting fields by their alignment
requirements will minimize this waste.
-
External alignment gaps. Alignment problems can also occur between
records in an array, due to alignment requirements of the first
field in a record. Make sure the record has a size which is a
multiple of the largest sub-field size.
-
Using too wide data types. Applicable both to bit fields, numeric
types and over-sized partially used fixed size arrays.
-
Dynamical memory allocation adds housekeeping structures, which are
used much less often than data in the allocated region.
-
Fields sorted in an suboptimal way. Not all fields being used in
every situation.
-
Incorrect padding causes records to be split between cache lines in
an adverse way.
-
Dynamic memory allocation allocates subsequent blocks
non-contiguously.
-
Certain data structures tend to destroy locality when placing
data. (Hash tables, trees).
-
Indirections instead of directly storing data
-
Linked lists trade-offs: dynamic memory allocation spreads memory
accesses, extra space required for pointers.
![[Tip]](images/tip.png) | Tip |
|---|
| Use correct data types |
| Tip |
|---|
| Sort record fields according to size and usage
pattern. |
| Tip |
|---|
| Organize data to avoid mixing read-only and write fields in
the same cache line. If many fields needs to be updated at the
same time, place them in the same cache line. |
| Tip |
|---|
| Avoid dynamic allocation of small objects, and
consider using custom allocators |
| Tip |
|---|
| Use data structures that pack data efficiently |
| Tip |
|---|
| Avoid "pointer chasing" and indirections |
