Arrays of per-thread data.

A typical programming pattern that causes false sharing is creating an array with one element per thread, such as an array of per-thread counters. Consider this example:

int sums[NUM_THREADS];

void threaded_sum(int thread_num, int v[], int v_count) {
    sum[thread_num] = 0;
    for (int i = 0; i < v_count; i++)
        sum[thread_num] += v[i];
}
              

This is a function that would be called by multiple threads, each summing the elements of some array into a per-thread sum in an array indexed by thread number. This creates a situation similar to the example with the sum1 and sum2 variables above. Since the per-thread data is allocated in array it will allocated together in memory, most likely in the same cache line, causing false sharing.

Avoid creating such per-thread arrays for frequently accessed data. Use function local variables for frequently accessed data, or assure that the data of each thread is allocated to a separate cache line in some other way, for example, using cache line alignment or padding.

Access patterns in parallelized matrix operations.

Another common cause of false sharing is parallelizations of algorithms that work on matrices or multi-dimensional arrays.

If such parallelizations make a fine grained division of the matrix between the threads, it can cause threads to write to elements adjacent to elements being accessed by other threads. Adjacent elements are likely allocated in the same cache line, making the writes likely to cause false sharing. For example, assume the elements marked in blue and yellow in this example are written by two different threads:

Figure 5.19. Matrix Accesses with False Sharing

In this case each write by the two threads will invalidate the cache line in the cache of the other thread, causing lots of coherence misses.

A more coarse grained division of the matrix between the threads will allow the threads to work on different cache lines to a greater degree, avoiding false sharing:

Figure 5.20. Matrix Accesses without False Sharing

If you get problems with false sharing running parallel matrix operations, it is therefore often a good idea to make division of the matrix between the threads more coarse grained.

Accesses to different fields in a structure from different threads.

Accesses to different fields in a structure from different threads can also cause false sharing problems. Consider this example in C:

struct ab {
    int a;
    int b;
    struct ab *next;
};

struct ab *abs;

void inc_a(void) {
    struct ab *this_ab = abs;
    while (this_ab != NULL) {
        this_ab->a++;
        this_ab = this_ab->next;
    }
}

int sum_b(void) {
    int sum = 0;
    struct ab *this_ab = abs;
    while (this_ab != NULL) {
        sum += this_ab->b;
        this_ab = this_ab->next;
    }
    return sum;
}
              

The function inc_a increments the value of the a field of each element in the abs linked list, while the function sum_b sums the values of the b field of each element in the list.

If the functions are run concurrently or alternatingly by different threads, the writes to the a field of each element in the list by the inc_a function will invalidate the list elements in the cache of the thread running the sum_b function. Similarly, the read of the b field of each element in the list by the sum_b function will downgrade the corresponding cache line in the cache of the thread running the inc_a function.

In a case like this it is probably best to split the structure into two structures containing the data accessed by each thread. If memory consumption is not a concern, you could also add enough padding between the fields to make sure they end up in different cache lines.

Statically allocated variables.

The example at the beginning of this section about false sharing showed how the statically allocated variables in this program can cause false sharing:

int sum1;
int sum2;

void thread1(int v[], int v_count) {
    sum1 = 0;
    for (int i = 0; i < v_count; i++)
        sum1 += v[i];
}

void thread2(int v[], int v_count) {
    sum2 = 0;
    for (int i = 0; i < v_count; i++)
        sum2 += v[i];
}
              

In cases like this, if the variables do not need to be statically allocated and are not excessively large you can make them function local variables instead. This causes them to be allocated on the threads' stacks, where they will most likely be safe from false sharing.

If it is not possible to make the variables thread local, you have to change their allocation in memory. One way to make sure that two variables are not allocated to the same cache line is to specify that both should be aligned to the start of a cache line.

Another way is be collect all variables accessed by a thread in a structure, and then add enough padding to the end of the structure to make sure no other variables can be allocated to the same cache line. This is a way to avoid false sharing if the compiler does not allow you to specify the alignment of data.

Dynamically memory allocation.

If your program uses dynamic memory allocation and allocates small data objects, data objects used by different threads may be allocated in the same cache line, causing false sharing.

Trying to allocate larger chunks of memory for use by one thread is probably the best fix in this case. For example, instead of allocating data objects for use by one thread individually you can allocate an array of data objects at once. This may reduce the interleaving of data objects used by different threads and thereby also false sharing.

Otherwise, aligning the data objects causing false sharing to the beginning of a cache lines is again a way to avoid false sharing. Depending on the operating system you are using there may be memory allocation functions you can use to do this.