False data independency: a look at cache line and write combining

Modern CPUs operate significantly faster than memories. A 4.5 GHz x64 CPU operates 30 times faster than a 6000 MHz DDR5 memory of CAS Latency 36. Adding latencies incurred by the bus and memory coherency protocols, memory could be 100 times slower than registers. To mitigate the speed gap, CPU uses layers of caches, starting with cache line, typically 64 bytes. However, at the programming language level, the unit of memory is one byte. This difference in memory unit, byte vs cache line, can lead programmers to a false sense of data independence. In this post, I examine two examples that illustrate data dependencies caused by two CPU techniques: cache line and write combining.

Cache Line

A cache line is the unit of data transferred between CPU caches and memory. In modern architectures, there are three layers of caches, L1, L2 and L3. Each CPU core has its own L1 and L2 caches, while all cores share the L3 cache. Cache coherency protocols ensures that cores maintain a consistent view of memory. When two cores read and write different memory addresses from the same cache line, cache line contention happens.

Experiment 1: Two go routines write two 64-bit integers. Each go routine performs one billion writes. In the control group, the two integers are on the same cache line. In the feature group, the two integers are on different cache lines.

 1// control group: cacheline/shared-write/main.go
 2func main() {
 3  t := time.Now()
 4  // Using array to allocate continuous memory.
 5  var a [2]A
 6  cnt := 1_000_000_000
 7
 8  var wg sync.WaitGroup
 9  wg.Add(2)
10  for i := 0; i < 2; i++ {
11    go func(p *A) {
12      defer wg.Done()
13      for j := 0; j < cnt; j++ {
14        p.x += int64(j) // concurrent write
15      }
16    }(&a[i])
17  }
18  wg.Wait()
19  fmt.Printf("takes %d ns\n", time.Since(t).Nanoseconds())
20}
21
22type A struct {
23  x int64
24}

1// feature group: cacheline/independent-write/main.go
2type A struct {
3  x   int64
4  // padding 56 bytes so that two consecutive A have their x in two different cache lines.
5  padding [7]int64 
6}

Run the two programs five times. Consistently, the control group is 40% slower than the feature group. Latency is measured in microseconds.

Padding is used to mitigate cache line contention in real-world scenarios. For example, the lmax/disruptor/RingBuffer.java from Disruptor pads 56 bytes.

 1abstract class RingBufferPad {
 2  // 56 bytes. Same size as the [7]int64 in the feature group.
 3  protected byte
 4    p10, p11, p12, p13, p14, p15, p16, p17,
 5    p20, p21, p22, p23, p24, p25, p26, p27,
 6    p30, p31, p32, p33, p34, p35, p36, p37,
 7    p40, p41, p42, p43, p44, p45, p46, p47,
 8    p50, p51, p52, p53, p54, p55, p56, p57,
 9    p60, p61, p62, p63, p64, p65, p66, p67,
10    p70, p71, p72, p73, p74, p75, p76, p77;
11}

Write Combining

Write Combining (WC) buffers multiple writes on the same cache line to one write. According to Intel,

Write combining (WC) improves performance in two ways:

1. On a write miss to the first-level cache, it allows multiple stores to the same cache line to occur before that cache line is read for ownership (RFO) from further out in the cache/memory hierarchy. Then the rest of line is read, and the bytes that have not been written are combined with the unmodified bytes in the returned line.
2. Write combining allows multiple writes to be assembled and written further out in the cache hierarchy as a unit. This saves port and bus traffic. Saving traffic is particularly important for avoiding partial writes to uncached memory.

Assembly/Compiler Coding Rule 51. (High impact, Low generality) If an inner loop writes to more than four arrays (four distinct cache lines), apply loop fission to break up the body of the loop so only four arrays are being written to in each iteration of each of the resulting loops.

Experiment 2. Write to eight arrays one billion times. Each array contains one million elements, and each element of eight bytes. The control group uses a single loop for writing. The feature group uses two loops, with each loop writing to four arrays.

 1// control group: one-byte-one-loop/main.go
 2type A [1]uint8
 3
 4func main() {
 5  arraySize := 1 << 20
 6  d0 := make([]A, arraySize)
 7  d1 := make([]A, arraySize)
 8  d2 := make([]A, arraySize)
 9  d3 := make([]A, arraySize)
10  d4 := make([]A, arraySize)
11  d5 := make([]A, arraySize)
12  d6 := make([]A, arraySize)
13  d7 := make([]A, arraySize)
14
15  // writes a constant, 2.
16  var value A = [1]uint8{2}
17  loopCount := 1_000_000_000
18
19  mask := arraySize - 1
20  t := time.Now()
21  for i := 0; i < loopCount; i++ {
22    j := i & mask
23    d0[j] = value
24    d1[j] = value
25    d2[j] = value
26    d3[j] = value
27    d4[j] = value
28    d5[j] = value
29    d6[j] = value
30    d7[j] = value
31  }
32  fmt.Printf("takes %d ns\n", time.Since(t).Nanoseconds())
33}

 1//one-byte-two-loops/main.go 
 2  for i := 0; i < loopCount; i++ {
 3    j := i & mask
 4    d0[j] = value
 5    d1[j] = value
 6    d2[j] = value
 7    d3[j] = value
 8  }
 9  for i := 0; i < loopCount; i++ {
10    j := i & mask
11    d4[j] = value
12    d5[j] = value
13    d6[j] = value
14    d7[j] = value
15  }

Run the two programs five times. Consistently, the control group is 51% slower than the feature group. Latency is measured in milliseconds.

Because there are not enough WC buffer for eight arrays, the one-loop incurs partial writes. A partial write is a write of less than 64 bytes of modified data. The number of WC buffers is quite small, ranging from six to eight. And one process may not use all available WC buffers. You may have noticed that, the experiment demonstrates the "Assembly/Compiler Coding Rule 51" from the Intel guide. The rule suggests compilers to break up a loop that writes to more than four arrays to multiple loops that write to four arrays each. The Go compiler does not implement the rule, as shown in the assembly code below.

 1// go build -gcflags="-S" one-byte-one-loop/main.go 
 2XORL	R13, R13
 3JMP	337
 4MOVQ	R13, R15
 5ANDL	$1048575, R15
 6MOVB	$1, (SI)(R15*1)
 7MOVB	$1, (R12)(R15*1)
 8MOVB	$1, (R11)(R15*1)
 9MOVB	$1, (R10)(R15*1)
10MOVB	$1, (R9)(R15*1)
11MOVB	$1, (R8)(R15*1)
12MOVB	$1, (DI)(R15*1)
13MOVB	$1, (DX)(R15*1)
14INCQ	R13
15CMPQ	R13, $1000000000
16JLT	284
17
18// go build -gcflags="-S" one-byte-two-loops/main.go 
19XORL	R9, R9
20JMP	297
21MOVQ	R9, R10
22ANDL	$1048575, R10
23MOVB	$1, (SI)(R10*1)
24MOVB	$1, (R8)(R10*1)
25MOVB	$1, (DI)(R10*1)
26MOVB	$1, (DX)(R10*1)
27INCQ	R9
28CMPQ	R9, $1000000000
29JLT	264
30...
31XORL	R9, R9
32JMP	364
33MOVQ	R9, R10
34ANDL	$1048575, R10
35MOVB	$1, (SI)(R10*1)
36MOVB	$1, (R8)(R10*1)
37MOVB	$1, (DI)(R10*1)
38MOVB	$1, (DX)(R10*1)
39INCQ	R9
40CMPQ	R9, $1000000000
41JLT	331

Since WC combines writes to a cache line, it does not provide benefits if each write is 64 bytes. After changing type A from [1]uint8 to [64]uint8, both the one-loop and two-loops take almost the same amount of time.

Conclusion

High-level programming languages abstract away computer architectures. The two examples show that lack of awareness of this abstraction can lead to a false sense of data independence and result in performance hit, especially when the compilers cannot do the optimization for us.

Further reading

1. Intel® 64 and IA-32 Architectures Optimization Reference Manual: Volume 1 3.6.9 Write Combining
2. Intel® 64 and IA-32 Architectures Software Developer’s Manual Volume 3A: System Programming Guide, Part 1 12.3 Methods Of Caching Available

Thank you for reading! Your feedback is greatly appreciated, feel free to comment.