AccessSpreader arranges access to a striped data structure in such a way that concurrently executing threads are likely to be accessing different stripes. It does NOT guarantee uncontended access. Your underlying algorithm must be thread‐safe without spreading, this is merely an optimization. AccessSpreader::current(n) is typically much faster than a cache miss (12 nanos on my dev box, tested fast in both 2.6 and 3.2 kernels).
Synopsis
Declared in <folly/concurrency/CacheLocality.h>
template<template<typename> typename Atom = atomic>
struct AccessSpreader;Description
If available (and not using the deterministic testing implementation) AccessSpreader uses the getcpu system call via VDSO and the precise locality information retrieved from sysfs by CacheLocality. This provides optimal anti‐sharing at a fraction of the cost of a cache miss.
When there are not as many stripes as processors, we try to optimally place the cache sharing boundaries. This means that if you have 2 stripes and run on a dual‐socket system, your 2 stripes will each get all of the cores from a single socket. If you have 16 stripes on a 16 core system plus hyperthreading (32 cpus), each core will get its own stripe and there will be no cache sharing at all.
AccessSpreader has a fallback mechanism for when __vdso_getcpu can't be loaded, or for use during deterministic testing. Using sched_getcpu or the getcpu syscall would negate the performance advantages of access spreading, so we use a thread‐local value and a shared atomic counter to spread access out. On systems lacking both a fast getcpu() and TLS, we hash the thread id to spread accesses.
AccessSpreader is templated on the template type that is used to implement atomics, as a way to instantiate the underlying heuristics differently for production use and deterministic unit testing. See DeterministicScheduler for more. If you aren't using DeterministicScheduler, you can just use the default template parameter all of the time.
Static Member Functions
Name |
Description |
Returns the stripe associated with the current CPU. The returned value will be < numStripes. This function caches the current cpu in a thread‐local variable for a certain small number of calls, which can make the result imprecise, but it is more efficient (amortized 2 ns on my dev box, compared to 12 ns for current()). |
|
Returns the stripe associated with the current CPU. The returned value will be < numStripes. |
|
Forces the next cachedCurrent() call in this thread to re‐probe the current CPU. |
|
Returns a canonical index in [0, maxLocalityIndexValue()) for each] stripe. This can be used to share global data structures accessed with different stripings. For optimal spread, it is best for numStripes to be a divisor of the number of L1 caches. |
|
Returns the maximum locality index value that can be returned under any dynamic configuration, based on the current compile‐time platform |
|
Returns the maximum stripe value that can be returned under any dynamic configuration, based on the current compile‐time platform |
|
Returns the lazily initialized global state for this Atom. |
Created with MrDocs