Go: when pointers hide the benefits of CPU caching
Abstract: Using small-sized variables by value can be faster than using pointers due to CPU value caching.
Disclaimer: Beware of premature optimizations; this article provides you with a more comprehensive understanding of the tool you are working with, rather than a silver bullet.
Often we use pointers when working with structures. For example, here is a code snippet that is quite familiar to you:
type User struct {
name string
age uint
}
func (u *User) Name() string {
return u.name
}We often use the (*Struct) syntax for receivers, as in this example, even though in this case, we don’t need a pointer since we aren’t planning to modify the User structure. So why do we do it? Because we’ve been taught that working with pointers is much faster than working with values, which is true in most cases. But not always.
You’ve probably heard about processor cache lines. This is a small-sized memory that is orders (even tens of times) faster than main memory. Any data you work with is cached by the processor to optimize operations.
Here are the cache lines (different levels of processor cache) on my Mac:
sudo sysctl -a | grep cache
...
hw.l1icachesize: 32768
hw.l1dcachesize: 32768
hw.l2cachesize: 262144
hw.l3cachesize: 12582912These are byte values. Now let’s imagine that our structure fits into L1 cache. Does it make sense to cache the pointer? If the cache contains the pointer, caching doesn’t provide much benefit when accessing a field of the structure that the pointer points to. After fetching the pointer that points to a location in main memory, you’ll still need to access the main memory to retrieve the data. Consequently, it’s much more advantageous to pass small structures by value.
For instance, consider having the following structure:
type Small struct {
str string // 16 bytes
i int // 8 bytes
b bool // 1 byte + 7 padding bytes
}This structure occupies only 32 bytes in memory. And it will fit into L1! Consequently, it’s advantageous to access it without using a pointer. Let’s verify this.
func BenchmarkValue_L1(b *testing.B) {
s := Small{"str", 1, true} // 32 bytes, fits L1 cache
println(unsafe.Sizeof(s), unsafe.Offsetof(s.str), unsafe.Offsetof(s.i), unsafe.Offsetof(s.b))
// prepare data
items := make([]Small, 0, 100)
for j := 0; j < 100; j++ {
items = append(items, s)
}
// bench
for i := 0; i < b.N; i++ {
processSmallByVal(items)
}
}
func BenchmarkPointer_L1(b *testing.B) {
s := &Small{"str", 1, true} // 32 bytes, fits L1 cache
// prepare data
items := make([]*Small, 0, 100)
for j := 0; j < 100; j++ {
items = append(items, s)
}
// bench
for i := 0; i < b.N; i++ {
processSmallByPointer(items)
}
}
/* data manipulation */
func processSmallByVal(items []Small) {
for _, item := range items { // get item value, item var reused to store values from slice
for i := 0; i < 10000; i++ {
item.i = i // access item's field from cache, mutate field, store in cache line directly
item.str = "123" // same
someint, somestr, somebool := item.i, item.str, item.b // read item's fields from cache
_, _, _ = someint, somestr, somebool // stub
}
}
}
func processSmallByPointer(items []*Small) {
for _, item := range items { // get pointer, store in 'item'
for i := 0; i < 10000; i++ {
item.i = i // go to the main mem
item.str = "123" // go to the main mem again
someint, somestr, somebool := item.i, item.str, item.b // go to the main mem again
_, _, _ = someint, somestr, somebool // stub
}
}
}Results:
go test -bench=. -benchtime=10s
goos: darwin
goarch: amd64
pkg: module05/fibonachi
cpu: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
BenchmarkValue_L1-12 44923 257923 ns/op
BenchmarkPointer_L1-12 15602 775480 ns/opDirectly accessing the value without using a pointer is three times faster.
Get Vadim Inshakov’s stories in your inbox
Join Medium for free to get updates from this writer.
If we increase the size of our structure to be larger than 32kb but smaller than 262,144kb, then we will be working with values from L2.
type Big struct {
arr [5000]int // 40kb
}This structure is too large for L1 on my machine but fits into L2. Let’s write a similar benchmark:
func BenchmarkValue_L2(b *testing.B) {
a := [5000]int{} // 40kb, fits L2 cache
for i := 0; i < 5000; i++ {
a[i] = i // fill array with values
}
s := Big{arr: a}
// bench
for i := 0; i < b.N; i++ {
processBigByVal(s)
}
}
func BenchmarkPointer_L2(b *testing.B) {
a := [5000]int{} // 40kb, fits L2 cache
for i := 0; i < 5000; i++ {
a[i] = i
}
s := &Big{arr: a}
// bench
for i := 0; i < b.N; i++ {
processBigByPointer(s)
}
}
/* data manipulation */
func processBigByVal(item Big) {
for i := 0; i < 5000; i++ {
item.arr[i] = i
somearr := item.arr
_ = somearr
}
}
func processBigByPointer(item *Big) {
for i := 0; i < 5000; i++ {
item.arr[i] = i
somearr := item.arr
_ = somearr
}
}Results:
go test -bench=. -benchtime=1s
BenchmarkValue_L2-12 502042 2396 ns/op
BenchmarkPointer_L2-12 468314 2855 ns/opThe results are nearly identical. As you may have noticed, this time I used -benchtime=1s instead of 10s, as before, because the longer the benchmark time, the more iterations with the function call processBigByVal(s) will occur. Now that we have a relatively large structure, copying it when passing to the function starts to overshadow all the benefits of accessing the value from the cache (what happens inside the function). Copying a pointer is easier than copying a structure because it's smaller. The larger the size of the structures we use, the less efficient the cache becomes for our values, and the more expensive it becomes to pass such values to functions and methods.
Finally, let’s see what happens when the structure is larger than L3.
type VeryBig struct {
arr [500000]int
}In this case, accessing main memory through a pointer is much cheaper (98 times faster):
BenchmarkValue_MainMem-12 318 3207093 ns/op
BenchmarkPointer_MainMem-12 35938 32765 ns/opTherefore, if you are dealing with small-sized entities, you can consider removing pointers. Besides the potential performance gain from efficient CPU cache utilization, you will also reduce the load on the garbage collector, which will have to clean up fewer objects in the heap.
Full source code of benchmarks:
https://gist.github.com/vadimInshakov/c938a913628e21cb282080f6c190ef06
You can support my work here: https://www.buymeacoffee.com/insh
Thank you for reading until the end. Please consider following the writer and this publication. Visit Stackademic to find out more about how we are democratizing free programming education around the world.
