False Sharing

• 27/01/2023
• 4-minute read

Khi CPU truy cập memory ở một địa chỉ cụ thể để lấy dữ liệu thì CPU sẽ tự động sao chép các dữ liệu liền kề với địa chỉ đó(cache line) vào CPU cache để tối ưu lần truy cập sau, tuy nhiên việc cập nhật các phần tử khác nhau(multiprocessor) ở trong cache line sẽ dẫn đến cache line được đánh dấu là invalid, từ đó buộc CPU phải gửi yêu cầu lấy dữ liệu đến memory hoặc các nơi khác thay vì lấy trong CPU cache, tình huống này được gọi là false sharing

Bài viết này minh hoạ trường hợp xảy ra false sharing bằng chương trình đếm số trong parallel programming và cách giải quyết. Source code https://github.com/thanhfphan/fun-stuffs-with-go/tree/master/false-sharing

Cách viết bình thường

package main

import (
	"fmt"
	"sync"
	"sync/atomic"
)

func main() {
	var sum atomic.Int64
	var wg sync.WaitGroup
	n := (1 << 25) // 2^25
	threads := 4
	for i := 0; i < threads; i++ {
		wg.Add(1)

		go func() {
			defer wg.Done()

			for j := 0; j < n; j++ {
				sum.Add(1)
			}
		}()
	}

	wg.Wait()

	fmt.Println("Sum: ", sum.Load())
}

Figure 1

Thời gian chạy chương trình loanh quanh 2.5s.

False Sharing

Từ cách viết bên trên mình để ý chúng ta đang cập nhật giá trị vào 1 biến sum duy nhất khi chạy 4 goroutine, nên mình nãy ra ý tưởng nếu ở mỗi goroutine mình cập nhật 1 biến khác nhau thì sao? Hi vọng nó sẽ nhanh hơn :D

package main

import (
	"fmt"
	"sync"
	"sync/atomic"
)

func main() {
	var sum atomic.Int64
	var wg sync.WaitGroup
	n := (1 << 25) // 2^25
	threads := 4
	counters := make([]atomic.Int64, threads)
	for i := 0; i < threads; i++ {
		wg.Add(1)

		go func(idx int) {
			defer wg.Done()

			for j := 0; j < n; j++ {
				counters[idx].Add(1)
			}

			chunk := counters[idx].Load()
			sum.Add(chunk)
		}(i)
	}

	wg.Wait()

	fmt.Println("Sum: ", sum.Load())
}

Lần này mình tạo 1 slice có 4 phần tử, mỗi goroutine sẽ chỉ update giá trị 1 phần tử trong slice này và sau đó cộng tất cả giá trị trong slice lại với nhau. Chúng ta cùng xem kết quả

Figure 2

Thời gian chạy chuơng trình không thay đổi nhiều, vẫn còn rất lớn vì nếu các bạn thử code chương trình này đếm số này ở trên 1 thread thì chạy rất nhanh, chưa đến 0,1s nữa :)))))) Chúng ta thử debug xem 2 chương trình này nó chậm ở chỗ nào nhé !!

Figure 3

Các bạn để ý ở chỗ màu đỏ thể hiện 2 chương trình mình viết phía trên bị cache miss rất nhiều. Ở chương trình đầu tiên cache miss là dễ hiểu thì chúng ta update 1 biến liên tục(cùng 1 địa chỉ trong memory), ở chương trình thứ 2 chúng ta không cập nhật trên một địa chỉ memory nữa nhưng vẫn update 4 địa chỉ sát nhau vẫn nằm trong cache line nên cache line bị invalid liên tục. Và tình huống này chính là false sharing

Xử lý False Sharing

Vậy để xử lý vấn đề này thì ta chỉ cần làm sao 4 goroutine chạy không có share chung 1 cache line nữa, và cách thường dùng là chúng ta thêm padding ở giữa các biến counter.

package main

import (
	"fmt"
	"sync"
	"sync/atomic"
)

type S struct {
	_       [56]int64 // the place where magic happens
	Counter atomic.Int64
}

func main() {
	var sum atomic.Int64
	var wg sync.WaitGroup
	n := (1 << 25) // 2^25
	threads := 4
	counters := make([]S, threads)
	for i := 0; i < threads; i++ {
		wg.Add(1)

		go func(idx int) {
			defer wg.Done()

			for j := 0; j < n; j++ {
				counters[idx].Counter.Add(1)
			}

			chunk := counters[idx].Counter.Load()
			sum.Add(chunk)
		}(i)
	}

	wg.Wait()

	fmt.Println("Sum: ", sum.Load())
}

Cùng xem thử thời gian chạy của chương trình này nhé :D

Figure 4

Và tỉ lệ cache miss gần như bằng 0.

Figure 5