LC

Pad Structs to Avoid False Sharing Between Threads

medium6/8

Implement Cache-Friendly BFS Using Level-by-Level Traversal Use __builtin_prefetch to Manually Prefetch Memory

Language

Compiler

2.0s Limit 256MB

Implementation

Pad structures to cache line size to prevent false sharing.

Requirements:

Define unpadded structure (causes false sharing)
Define padded structure with cache line alignment
Use attribute((aligned(64))) for alignment
Benchmark with 2 threads updating adjacent fields
Show performance difference (5-10x speedup)
Measure with perf (cache-misses)
Explain cache line layout
Demonstrate proper padding technique

Why This Matters

The `std::hardware_destructive_interference_size` constant added to C++17 exists purely so library authors can pad structs like this one without guessing the cache line size, and Linux kernel per-CPU data structures use `____cacheline_aligned` for the identical reason. Getting this padding wrong is a routine cause of mysterious 5-10x slowdowns in multithreaded counters that show up only under real concurrent load, never in single-threaded testing.

Hints

0 / 3 revealed

Validation Suite

main.c

Workspace 1.0