False sharing

In computer science, false sharing is a performance-degrading usage pattern that can arise in systems with distributed, coherent caches at the size of the smallest resource block managed by the caching mechanism. When a system participant attempts to periodically access data that will never be altered by another party, but that data shares a cache block with data that is altered, the caching protocol may force the first participant to reload the whole unit despite a lack of logical necessity. The caching system is unaware of activity within this block and forces the first participant to bear the caching system overhead required by true shared access of a resource.

By far the most common usage of this term is in modern multiprocessor CPU caches, where memory is cached in lines of some small power of two word size (e.g., 64 aligned, contiguous bytes). If two processors operate on independent data in the same memory address region storable in a single line, the cache coherency mechanisms in the system may force the whole line across the bus or interconnect with every data write, forcing memory stalls in addition to wasting system bandwidth. False sharing is an inherent artifact of automatically synchronized cache protocols and can also exist in environments such as distributed file system or databases, but current prevalence is limited to RAM caches.

Example

struct foo {
    int x;
    int y; 
};

static struct foo f;

/* The two following functions are running concurrently: */

int sum_a(void)
{
    int s = 0;
    int i;
    for (i = 0; i < 1000000; ++i)
        s += f.x;
    return s;
}

void inc_b(void)
{
    int i;
    for (i = 0; i < 1000000; ++i)
        ++f.y;
}

Here, sum_a may need to continually re-read x from main memory (instead of from cache) even though inc_b's concurrent modification of y should be irrelevant.

External links

• C++ today blog on the subject
• Dr Dobbs article: Eliminate False Sharing
• Be careful when trying to eliminate false sharing in Java

References

• Bolosky, W. J. and Scott, M. L. 1993. False sharing and its effect on shared memory performance In 4th USENIX Symposium on Experiences with Distributed and Multiprocessor Systems, San Diego, California, September 22–23, 1993. USENIX Association, Berkeley, CA, 3-3.