Double Buffering

• 26/01/2023
• 3-minute read

Là một kỹ thuật lập trình dùng 2 buffer để lưu trữ dữ liệu, mục đích để giảm thời gian chờ giữa lúc chuẩn bị và lúc sử dụng dữ liệu. Được biết nhiều ở lĩnh vực đồ họa máy tính, game, hệ điều hành. Bài viết minh họa kỹ thuật Double Buffering trong lập trình song song sử dụng ngôn ngữ Go.

Minh họa

Một chương trình có bước chuẩn bị và sau đó xử lý dữ liệu với 2 cách bình thường và dùng kỹ thuật double-buffering. Full source code https://github.com/thanhfphan/fun-stuffs-with-go/tree/master/double-buffering

Giả lập 2 bước này bằng 2 hàm như bên dưới.

// Giả lập bước chuẩn bị dữ liệu
func generateData(data []int) {
	for i := range data {
		data[i] = rand.Intn(100)
	}
}

// Giả lập bước xử lý dữ liệu
func processData(data []int) {
	// dummy work
	for i := 0; i < 5; i++ {
		for i := range data {
			data[i] %= data[i] + 1
		}
	}
}

Cách lập trình bình thường

package main

// Giả lập bước chuẩn bị dữ liệu
func generateData(data []int) {
	...
}

func processData(data []int) {
	...
}

// the main thing
func run() {
	interation := 100
	// tạo 1 slice có 2^20 elements
	data := make([]int, 1<<20)
	for i := 0; i < interation; i++ {
		generateData(data)
		processData(data)
	}
}

func main() {
	run()
}

Chạy 1 vòng for 100 lần xử lý tuần tự chuẩn bị đến xử lý dữ liệu. Với cách làm này thì ta thử đo thời gian chạy mất bao nhiêu giây nhé.

go build .
time ./baseline

Figure 1

Tốn khoảng 6.2s

Sử dụng kỹ thuật double-buffering

package main

import (
	...
	"github.com/thanhfphan/fun-stuff-with-go/double-buffering/double-buffer/semaphore"
)

func generateData(data []int) {
	...
}

func processData(data []int) {
	...
}

// the main thing
func run() {
	interation := 100
	data1 := make([]int, 1<<20)
	data2 := make([]int, 1<<20)
	bs := semaphore.NewBinarySemaphore()
	var w sync.WaitGroup
	w.Add(2)
	// generate data
	go func() {
		defer w.Done()
		for i := 0; i < interation; i++ {
			generateData(data1)

			// wait until processing work is done
			bs.Wait()

			// swap data
			copy(data2, data1)

			// signal to [processing data] goroutine
			bs.Signal()
		}
	}()

	// processing data
	go func() {
		defer w.Done()
		for i := 0; i < interation; i++ {
			// wait signal from [generate data] goroutine
			bs.Wait()

			processData(data2)

			// signal to [generate data] goroutine to begin the work
			bs.Signal()
		}
	}()

	w.Wait()
}

func main() {
	run()
}

Ở lần này mình sử dụng 2 goroutine, 1 cái để chuẩn bị dữ liệu gọi là A, 1 cái để xử lý dữ liệu gọi là B.

Khi A chuẩn bị dữ liệu xong thì bắn tín hiệu qua B ở đoạn bs.Signal rồi tiếp tục chuẩn bị dữ liệu cho vòng lặp kế tiếp. Lúc B nhận được tín hiệu bs.Wait thì bắt đầu xử lý dữ liệu rồi tiếp tục chờ tín hiệu từ A.

Và thử đo thời gian chạy với cách này

go build .
time ./double-buffer

Figure 2

Thời gian chạy mất khoảng 5.8s

Nhận xét

• Dùng kỹ thuật double-buffering có thể làm tăng performance của chương trình lên khá đáng kể, nhưng bù lại CPU lại phải xử lý nhiều hơn(xem phần thời gian user ở 2 hình Figure 1, Figure 2)

• Mình đang dùng hàm copy để copy dữ liệu từ slice này qua slice khác

// swap data
copy(data2, data1)

một cách tối ưu hơn là dùng 2 pointer(1 trỏ vào slice chuẩn bị dữ liệu, 1 cái trỏ vào slice xủ lý) lúc chuẩn bị dữ liệu xong thì chỉ cần swap 2 pointer.