[golang] 메모리 지역성을 고려한 2차원 슬라이스 순회

서론

2차원 슬라이스를 순회할 때 성능에 큰 영향을 미치는 요소 중 하나는 메모리 지역성이다. 메모리 지역성이란 CPU가 데이터를 빠르게 접근하기 위해 메모리에서 데이터를 어떻게 참조하는지에 대한 패턴을 의미한다. CPU 캐시는 메모리의 연속적인 데이터를 빠르게 읽을 수 있는 공간적 지역성 특성을 갖고 있다. 공간적 지역성은 연속된 메모리 주소의 데이터가 자주 참조되는 특성으로 하나의 데이터가 참조되면 그 인접한 데이터도 순차적으로 참조될 확률이 높다는 것이다. 이러한 특성으로 연속적인 메모리 접근은 성능상 유리하다. 반대로 불연속적인 메모리 접근은 캐시 미스를 유발하고 이로 인해 성능 저하를 초래할 수 있다.

이 글에서는 메모리 지역성을 고려하여 2차원 슬라이스를 순회할 때 행 우선 순회와 열 우선 순회의 성능 차이를 비교하고 메모리 지역성에 최적화된 순회 방식을 알아본다.

 

2차원 슬라이스 순회 예제

package main

import (
	"fmt"
	"time"
)

const size = 10000

func main() {
	// 2차원 슬라이스 초기화
	data := make([][]int, size)
	for i := range data {
		data[i] = make([]int, size)
	}

	// 행 우선 순회
	start := time.Now()
	for i := 0; i < size; i++ {
		for j := 0; j < size; j++ {
			data[i][j]++
		}
	}
	fmt.Println("Row-first iteration:", time.Since(start))

	// 열 우선 순회
	start = time.Now()
	for j := 0; j < size; j++ {
		for i := 0; i < size; i++ {
			data[i][j]++
		}
	}
	fmt.Println("Column-first iteration:", time.Since(start))
}

이 예제는 10,000X10,000 크기의 2차원 슬라이스에 대해 행 우선 순회와 열 우선 순회 방식의 성능 차이를 비교하는 코드이다. 각 방식에 대한 소요 시간을 측정하여 메모리 지역성을 고려한 성능 차이를 살펴본다.

• 행 우선 순회: 각 행을 먼저 순회하고 그 안에서 각 열을 순차적으로 접근한다. 이 방식은 메모리에서 연속적인 데이터를 참조하므로, CPU 캐시의 효율을 높이는 데 유리하다.

• 열 우선 순회: 각 열을 먼저 순회하고 그 안에서 각 행을 순차적으로 접근한다. 이 방식은 메모리 상에서 불연속적인 데이터를 참조하게 되어 캐시 미스를 유발할 수 있다.

 

성능 비교

Row-first iteration: 120.70775ms
Column-first iteration: 830.409208ms

예제 코드를 실행해보면 행 우선 순회가 열 우선 순회보다 훨씬 빠르다는 것을 알 수 있다. 이는 메모리 지역성을 고려한 캐시 효율성에 따라 성능 차이가 발생하기 때문이다. 열 우선 순회는 메모리 상에서 불연속적인 위치를 읽게 되어 캐시 미스를 유발하고 성능을 저하시킬 수 있으므로 성능이 중요한 경우에는 행 우선 순회 방식을 사용하는 것이 좋다.