Unit 7.3 · about 5 h
44 / 324Struct layout, alignment, strides and locality
A dtype or stride mismatch changes which bytes native code reads. The same layout choices also decide how much useful data each memory access brings into the computation.
- derive
- measure
You can now
- Compute field offsets, padding and array strides for a measured native layout.
- Derive a byte offset from a base address, index, stride and field offset.
- Compare AoS and SoA for a controlled access pattern without assuming either layout must be faster.
Covers
- Struct and class layout, padding, alignment and strides
- Contiguous layout, locality, array of structures and structure of arrays
Study, in this order
4 steps
- Objects, representation and alignmentcppreference
Object representation and value representation; Size; Alignment, including the
SandXexamplesDepth · Skip implicit object creation and polymorphic layout. Use simple standard-layout structs for offset checks.
- Predictable memory accessC++ Core Guidelines
Per.19: Access memory predictably, including the two matrix traversal orders
- AoS and SoA trade-offsMemory Layout Transformations
Overview; Topics; AOS Form (Array of Structs); SOA Form (Struct of Arrays)
Depth · Read the layouts, not the Intel-specific array-notation syntax. Stop before AOSOA and the LIBOR example. Treat performance statements as hypotheses for your own access pattern.
- When AoS wins: whole-record accessAlgorithmica - AoS and SoA
AoS and SoA: Experiment
Depth · Read the Experiment section only; the associativity and huge-page effects after it are beyond this unit. Its pointer chase reads every field of a randomly chosen record, the opposite of the Reproduce's single-field scan.
Focus on
sizeofincludes padding. Alignment constrains legal object addresses, and trailing padding keeps successive array elements suitably aligned.- For a standard-layout record array, a field's byte offset is
index * sizeof(record) + offsetof(record, field). For a strided view, use the supplied byte strides instead. - AoS groups fields of one record; SoA groups one field across records. Field-wise scans and whole-record access can favor different layouts.
- Keep allocation, initialization and layout conversion outside a kernel-only timing. Preserve results so the compiler cannot discard the work, and do not infer cache misses from wall time alone.
Reproduce closed-book
-std=c++20 -O0, define struct Row { char tag; std::int32_t count; char flag; }; print offsetof for all fields, sizeof and alignof. The observed values are offsets 0, 4, 8, size 12 and alignment 4. Thus rows[2].flag is at byte offset 2 * 12 + 8 = 32 from a three-element array's base. These are observations for that toolchain, not universal layout constants. Then compare summing x in vector<Point> where Point has uint64_t x,y,z against a separate vector<uint64_t> x: initialize both with x[i] = i % 100, use 1,048,576 records, g++ 15.2 -std=c++20 -O2, one warmup and seven timed scans per layout in alternating order, and consume each checksum. On your machine, record all timings and their medians with the CPU model, sizeof(Point) and allocated bytes. Python is not involved. Both checksums must be 51,903,600; no speed ranking is promised.Traps
- Summing member sizes misses internal and trailing padding. Packing a struct is not a free optimization and can create unaligned accesses.
- Assuming an array of pointers stores the pointed-to objects contiguously.
- Declaring SoA faster from one timing, or comparing different data, access patterns or conversion costs.
Practice
The section mini-project covers this: document field offsets and strides, then preserve a controlled AoS/SoA comparison with equal checksums and a reproducible measurement setup.
Self-test
-
Why can
sizeof(Row)exceed the sum of its members' sizes?Padding aligns members and successive array elements. The exact amount depends on the implementation and ABI. -
A view has byte strides
(40, 8). What is the offset of element[2,3]?2 * 40 + 3 * 8 = 104 bytes from that view's base, assuming the indices are valid. -
Why might SoA help a scan that reads only
x, but not a workload consuming every field of scattered records?SoA puts successivexvalues together. Scattered whole-record access instead benefits from keeping each record's fields close, as AoS does. Measure the actual workload.
Completion criterion
Stop when
Your offset predictions match the measured layout, both scan checksums match, and your seven-repeat report separates measured timings from untested cache explanations.
Mark passed, then open 7.4 Only mark this when you can do it without notes.Leads to
- 7.8 Python and native code: dtype, stride, ownership and GIL contracts Validate dtype, shape and byte strides at the extension boundary.
Comes after
- 7.2 Integer representation, pointers, references and spansTurn element offsets into byte-address calculations.
Resources for this unit
- C++ Core Guidelines Use the Philosophy, Interfaces, Resource management, Expressions, Containers and concurrency rule groups to review ownership and safety decisions in the native component.
- cppreference Consult language lifetime, object model, value categories, memory model, atomics, containers and iterator invalidation while reading or modifying code.
- Algorithmica - AoS and SoA Read the AoS and SoA experiment for a measured case where keeping each record together wins, the counterpart to a single-field scan.
- Memory Layout Transformations Read Overview and Topics through AOS Form and SOA Form for field-wise access and locality trade-offs. Skip Intel array-notation syntax and the LIBOR example.
Also in this section
- AlgoMaster C++ Use the sections on compilation, pointers and references, memory, RAII and smart pointers, copy and move, STL containers, templates, errors, concurrency and paired exercises. Skip competitive-programming breadth already covered in Algorithms.
- Clang AddressSanitizer and UndefinedBehaviorSanitizer Compile seeded memory defects with AddressSanitizer and UndefinedBehaviorSanitizer, preserve the reports, repair the root cause and keep regression tests.
- pybind11 documentation Follow First steps and NumPy support to expose one small native function with explicit shape, dtype, stride, ownership, GIL and exception behavior.
- CMake tutorial Use the introductory steps for targets, libraries, testing and install rules. Produce one clean debug build and one optimized build without copied one-off commands.
- `ld.so`: dynamic linker/loader Read DESCRIPTION, Dynamic string tokens and
LD_DEBUGto distinguish link-time symbols from runtime shared-library discovery on Linux. - GDB manual: Backtraces Use section 8.2 for frame numbers,
bt,bt -fulland optimized-out arguments when inspecting a native failure.