An access pattern is the sequence of locations a computation reads or writes. In concurrent code, it matters which thread touches each location: nearby accesses can use cache effectively, but writes by different threads to nearby data can cause false sharing. section 8.3.1
Dividing matrix multiplication
Suppose each thread computes several columns of a result matrix whose rows are contiguous in memory. Assign adjacent columns to the same thread so its writes within each row stay together. If each thread’s assigned space occupies whole, separate cache lines, those writes avoid false sharing. Rows and rectangular regions are also possible work divisions; the choice must account for where each thread reads and writes. section 8.3.1
For other structures, give nearby data to the same thread, limit how much data each thread needs, and keep data used by different threads far enough apart to avoid false sharing. Trees complicate this: subtrees may be uneven, and dynamically allocated nodes may be scattered across the heap. A mutex placed beside its protected data can help the lock holder’s cache access, but competing threads also need to touch the mutex. section 8.3.2
struct protected_data
{
std::mutex m;
char padding[std::hardware_destructive_interference_size]; #1
my_data data_to_protect;
};
The protected-data layout inserts padding between a mutex and its data. It illustrates a deliberate separation of locations that different threads may access. section 8.3.2
Access patterns also determine when work can stop. A parallel std::find need not examine every element once a match is found. Workers can check an atomic completion flag and stop rather than finish their assigned ranges; without that interruption, a sequential search may return sooner when the match appears early. section 8.5.2
