False Sharing Alignment

False Sharing Alignment | Monoidal Tranformation Table of ContentsWhat is false sharing What to do BenchmarkDigital Ocean Amazon Web Services, c5d (Skylake) Results Amazon Web Services, c6i (Ice Lake) Apple Silicon M1

Conclusion Reading list Disclaimer

What is false sharing# What is false sharing? When CPUs and their cores read and update atomic variables, special hardware protocols make it correct and efficient, while keeping each core’s caches consistent. The coordination doesn’t happen per-address: these protocols work on cache-line-sized chunks. What happens when two atomic variables happen to reside on the same cache line? For example: an array of atomics where each atomic is used by a separate thread (e.g. per-thread counters); a queue with two atomic pointers where a writer updates the tail and a reader updates the head. Of course, you declare both pointers in the same struct and they have adjacent addresses! Each update operation makes the cache line dirty and requires coordination between CPUs. The CPUs are essentially playing ping pong with the chunk of memory. What to do# The solution is simple: separate the atomics by making them reside in different cache lines. It is done with some language-dependent alignment directive, though it is not the alignment but the spacing that matters. Rust#[repr(align(N))] on the type declaration (or use a type wrapper)C11_Alignas(N) on type or variable declarationC++11alignas(N) on type, field or variable declarationGCC/Clang__attribute__((aligned(N)))Both Rust Atomics and Locks by Mara Bos and Performance Analysis and Tuning on Modern CPUs by Denis Bakhvalov recommend using cache line size, which is 64 bytes for x86_64. However, libraries (crossbeam-utils, Facebook’s folly) use 128 bytes here. Why? The reason is that since the Intel Sandy Bridge architecture, the spatial prefetcher may load cache lines in pairs. It doesn’t make the effective cache line size equal to 128 bytes, but still has its side-effects. Moreover, this behavior is controlled by a per-core MSR setting called either “Adjacent Cache Line Prefetcher Disable” or “L2 Adjacent Cache Line Prefetcher Disable”. Check it before benchmarking! If you can. Benchmark# I tried to reproduce the 128-byte alignment improvement on a real benchmark. It wasn’t easy! Just starting 2 threads updating an atomic each is not enough: once the atomics are in the respective CPU caches, no MESI interaction seems to be done. Let’s try something more involved: a vector of atomics should do the trick. Let’s imitate a classical two-pointer atomic queue: an atomic for head being incremented by reader, and an atomic for tail incremented by writer. Using either #[repr(align(64))] or #[repr(align(128))] in the Rust code below for a wrapper type similar to crossbeam-utils will place the atomics either 64 or 128 bytes apart. Single pair of atomics may be not enough to create a pressure to the memory; let’s get a vector of records of length SIZE. Each thread of two modifies either add or sub field of each record in loop. The thread body looks bit odd: for _ in 0..(N / SIZE) { for elt in addsub { elt.add.fetch_add(1u64, ORDERING);

You may notice that number of operations is SIZE*floor(N/SIZE) which is not equal to N. It makes comparing different SIZE harder&mldr; until we notice that difference is really negligible, because our SIZE are small and N is large. But the inner loop is very simple, and it makes the benchmark more reliable. You can get the runnable code at https://github.com/monoid/junk/tree/master/false_sharing, but for your convenience, simplified code is below. Source codeuse std::ops::Deref; use std::sync::atomic::{AtomicU64, Ordering};

// Number of steps. const N: usize = 1_000_000_000; const ORDERING: Ordering = Ordering::AcqRel; // The length of vector of AddSubs. const SIZE: usize = 8;

// Uncomment any of these lines. // #[repr(align(64))] // #[repr(align(128))] #[derive(Default, Debug)] struct CachePaddedT> { value: T,

implT> Deref for CachePaddedT> { type Target = T;

fn deref(&self) -> &Self::Target { &self.value

// Two atomics side-by-side separated by cache padding configured above. #[derive(Default, Debug)] struct AddSub { // Updated by the first thread. add: CachePaddedAtomicU64>, // Updated by the second thread. sub: CachePaddedAtomicU64>,

impl AddSub { fn get_value(&self) -> u64 { let add = self.add.load(Ordering::Relaxed); let sub = self.sub.load(Ordering::Relaxed); add.wrapping_sub(sub)

fn main() { let data = Vec::from_iter(std::iter::repeat_with(|| AddSub::default()).take(SIZE)); let addsub: Box[AddSub]> = data.into(); let addsub = &*Box::leak(addsub);

let t1 = std::thread::spawn(move || { #[cfg(target_arch = "x86_64")] affinity::set_thread_affinity(&[0]).unwrap();

for _ in 0..(N / SIZE) { for elt in addsub { elt.add.fetch_add(1u64, ORDERING); }); let t2 = std::thread::spawn(move || { #[cfg(target_arch = "x86_64")] // Not...

False Sharing Alignment

Related Articles

(no title)

Scientists reverse brain aging, with a nasal spray

AI has torched the market for junior programmers

Al Vigier: Canada's AI strategy shouldn't include secret Palantir bills

The Anatomy of an AI-Native Org