Posted in: 프로그래밍

프로그램을 조금 더 빠르게 #1 – AoS와 SoA

CPU가 메모리에 접근하는데는 생각보다 긴 시간이 필요하다

CPU는 매우 빠르게 작동한다. 내 노트북만 해도 CPU가 3Ghz 돌아가고 있다. 이는 초당 3 000 000 000번 동작한다는것을 뜻한다. CPU는 이렇게 빠르지만 메모리는 그렇지 못하다. 물론 메모리가 HDD, SSD등 보다는 빠르다. 하지만 저 속도에는 못따라 가고 있다.

몇가지 실제 자료를 찾아봤는데 (7-cpu.com – 인텔 Skylake 메모리 속도, Redhat – Reducing Memory Access Times with Caches) 어쨋든 CPU에 비해서 많~~이 느리다. Redhat에 따르면 CPU는 0.5ns에 하나의 연산을 하는데 CPU가 메모리를 받아오려면 50ns가 걸린다고 한다. 단순 계산시 100배 차이 수준이다. (물론, 대역폭과 상황에 따라서 달라질 수 있다)

7-cpu의 자료에 따르면 봐도 메모리를 읽으려면 42개의 CPU 처리(사이클)와 51ns가 추가로 걸린다고 한다. L1 캐시 메모리는 4사이클(복잡한 주소 계신시 5사이클), L2 캐시에는 12사이클, L3 캐시에서는 38~42 사이클내로 가능하다는것과 크게 차이난다. (마찬가지로 대역폭과 상황에 따라서 달라질 수 있다)

어쨋든 하고픈 말은, CPU에서 메인 메모리를 접근하는것은 생각보다 느리다는것이다. 이게 아무것도 아니라고 보일수도 있다. 그러나 메인 메모리로의 접근 횟수와 비례해서 차이가 벌어진다. 조금의 CPU라도 아까운 대용량 처리 시스템에서는 아까울 수 밖에 없다. 특히 특수한 조건에서는 2배 이상의 속도 차이를 보여주기도 한다. 메모리를 많이 접근하는 프로그램일수록 더욱 크게 차이날 수도 있다.

결과적으로는 메모리를 어떻게 해야 더 빠르게 쓸 수 있냐? 라는 물음이 나오게 된다. 알고리즘·코드단에서 메모리 접근자체를 줄일수 있다면 좋겠지만.. 솔직히 쉽지 않다. 그렇다면 메모리를 접근하는 방법을 바꿔보는것은 어떨까? 그런점에서 나온것이 AoS(Array of Struct, Struct들을 Array로 묶은것)와 SoA(Struct of Array, Struct내에 Array를 두어서 데이터 저장)이다.

CPU는 한번에 64byte씩 읽는다

CPU는 메인 메모리를 읽으려면 상당한 시간이 걸린다는것을 알고있다. 캐시 메모리에서 데이터를 읽는것은 빠른 속도로 가능하다는것도 알고있다. 빠르게 작동하려면 필요한 메모리 영역을 통째로 CPU내의 캐시 메모리에 올려놓는것이 매우 중요하다는것을 아는것이다.

매 변수를 읽고 쓸때마다 메모리에 접근하는것은 비효율적이기에, CPU는 한번에 64byte씩 메모리를 접근해서 캐시 메모리에 올려둔다. a라는 변수를 읽으면 그 뒤에 있는 데이터도 접근하겠지? 라는 기대를 안고 a변수 부터 해서 64바이트를 통으로 접근하고 캐싱하는 것이다.

int main() {
	int a, b, c, d;

	a = 1;
	b = 2;
	c = 3;
	d = 4;
}

위와 같은 프로그램이 있다고 생각해 보자. a = 1 이라는 코드가 실행되면 이미 CPU에서는 b, c, d 에 대한 메모리를 읽어온 상태이다. CPU <-> 메모리 사이 통신이 비교적 느리다보니 64byte씩 미리 불러와서 캐싱하니 생기는 일이다. 실제 필요한 데이터가 4byte라고 해도 시작 지점으로 부터 64byte를 캐싱한다. 그 뒤에 무슨 데이터가 있던간에(아무런 데이터가 없더라도!) 일단 64byte씩 캐싱한다.

Struct of Array, Array of Struct

위의 개념에서 이어진다. 필요한 데이터들을 모아서 저장한다면 메모리 캐시를 효율적으로 (무수한 Hit 세례가!) 사용할 수 있지 않을까? 라는 생각인 것이다.

struct Server {
	int server_id;

	int tx_bytes;
	int rx_bytes;

	int conn;

	char padding[48];
}

위와 같은 구조체가 있다고 생각해 보자. 이 구조체는 극단적인 예를 들기위해서 64byte를 가지도록 만들었다. 이 Server 구조체를 배열에 수천개, 수만개 저장한다고 생각해 보자. CPU입장에서는 Server 구조체를 접근할 때 마다 새로 메모리를 캐싱해야 할 것이다.  이걸 한번 읽으면 64 바이트가 꽉 차기 때문이다.

그렇다면 Server 구조체를 배열에 저장하는게 아니라, Server의 각 필드를 배열로 저장하면 어떨까? 각 필드마다 연속적으로 저장되어 있기에 필드를 순차적으로 접근한다면 보다 나은 속도를 기대할 수 있다.

struct Server {
	int* server_id = malloc(sizeof(int) * 1024);

	int* tx_bytes = malloc(sizeof(int) * 1024);
	int* rx_bytes = malloc(sizeof(int) * 1024);

	int* conn = malloc(sizeof(int) * 1024);
}
// Pseudo 코드로 작성해 보았다. Struct이 Array를 담고 있다.

예를 들어, 특정 server_id가 배열에 있는지 확인하는 작업을 한다고 해보자. 기존 코드에서는 메모리 캐싱이 struct 1개만 저장하면 꽉 차서 매번 struct을 읽기 위해 메모리를 기다려야 했다. 하지만 이제는 server_id를 16개씩(캐시크기 / int 크기 = 64 / 4) 캐싱할 수 있게되어 저번 보다 더욱 효율적으로 메모리 접근이 가능해 졌다. 단순히 생각해서 메모리를 읽는데 1초가 걸린다고 하자. server_id를 16개 읽을때 구조체가 모여있는 배열에서 조회할 때는 16초가 걸린다. 하지만 구조체에서 각 필드를 저장하는 배열속에서 조회할 때는 1초면 된다. (여러 Optimization을 생략했다)

사실 둘 중 뭐가 더 좋다라고 할 수는 없다. 아래에서 보겠지만 AoS (=Array of Struct)가 유리한 구조가 있고 SoA (=Struct of Array)가 유리한 구조가 있다. 프로그램의 구조에 따라서 같이 쓰는 변수들의 메모리 공간을 모아두면 프로그램을 보더 더 빨리 돌릴수 있다는게 핵심이다. 바로 최인접은 안되더라도 64byte내에 존재하면 될 것이다.

속도를 실측해 보자!

실제 속도를 측정해 보았다. 테스트는 메모리 구조가 하드웨어에 직관적으로 그려지는 C언어로 진행했다. 모두 리눅스(라이젠7 4750U, 메모리 16GB, 하모니카 ME, 커널 5.8.9)에서 gcc로 -O3 옵션을 통해 (GCC 버전 Ubuntu 7.5.0-3ubuntu1~18.04) 컴파일 및 실행 하였다. 테스트는 번갈아가며 각 3회씩 실시하였고, 각 테스트마다 1초씩 sleep을 부여하였다.

테스트 케이스 1

struct내의 tx와 rx를 접근하는 상황을 그려보았다.

// AOS, ESukmean
#include <stdlib.h>
#include <stdio.h>
#include <time.h>

typedef struct server {
	unsigned long server_id; //8-byte
	
	unsigned long tx; //8-byte
	unsigned long rx; //8-byte
	unsigned long conn; // 8-byte
} Server;

inline long rnd(){
	return rand();
}
void assign(Server* list, int size) {
	for(int i = 0; i < size; i++) {
		list[i].conn = i;
		list[i].rx = rnd();
		list[i].tx = rnd();
		list[i].conn = rnd();
	}
}

int main(int argc, char* argv[]) {
	int size = atoi(argv[1]);

	Server* list = malloc(sizeof(Server) * size);
	assign(list, size);

	unsigned long long sum = 0;
	unsigned long max = 0;

	clock_t end;
	clock_t start = clock();
	for(int i = 0; i < size; i++){
		sum = list[i].tx + list[i].rx;
	}
	end = clock();

	printf("%d -> %ld ms ==> %lld", size, end - start, sum);
}
// SOA, ESukmean
#include <stdlib.h>
#include <stdio.h>
#include <time.h>

typedef struct server {
	unsigned long* server_id;

	unsigned long* tx;
	unsigned long* rx;
	unsigned long* conn;
} Server;

inline long rnd(){
	return rand();
}
void assign(Server* list, int size) {
	for(int i = 0; i < size; i++) {
		list->conn[i] = i;
		list->rx[i] = rnd();
		list->tx[i] = rnd();
		list->conn[i] = rnd();
	}
}

int main(int argc, char* argv[]) {
	int size = atoi(argv[1]);

	Server list;
	list.server_id = malloc(sizeof(unsigned long) * size);
	list.tx = malloc(sizeof(unsigned long) * size);
	list.rx = malloc(sizeof(unsigned long) * size);
	list.conn = malloc(sizeof(unsigned long) * size);
	assign(&list, size);

	unsigned long long sum = 0;
	unsigned long max = 0;

	clock_t end;
	clock_t start = clock();
	for(int i = 0; i < size; i++){
		sum = list.tx[i] + list.rx[i];
	}
	end = clock();

	printf("%d -> %ld ms ==> %lld", size, end - start, sum);
}

결과는 SoA가 AoS보다 2.2배 정도 빠르게 나왔다.

SoA – (Struct내에 Array를 여러개 둘 경우)일때의 결과:
배열의 크기1회 (ms)2회 (ms)3회 (ms)실행 평균 (ms)
12322.3
22242.7
42222.0
82222.0
162322.3
321221.7
642211.7
1281211.3
2561332.3
5122222.0
10243333.0
20484444.0
40965555.0
81926887.3
1638417151616.0
3276829303029.7
6553654525252.7
13107299114118110.3
262144238234213228.3
524288421401437419.7
1048576793825744787.3
20971521420140314331,418.7
41943042689289729552,847.0
83886085766573854985,667.3
1677721613745139741384213,853.7
3355443226709265882668826,661.7
6710886453840543135419054,114.3
134217728108667110983108770109,473.3
268435456219824219360218956219,380.0
AoS – (Array를 만들고 그 안에 Struct을 담는 방식) 일때의 결과:
배열의 크기1회 (ms)2회 (ms)3회 (ms)실행 평균 (ms)
13333.0
22121.7
42232.3
82332.7
162232.3
322222.0
641322.0
1282322.3
2562232.3
5122322.3
10244343.7
20484655.0
40967887.7
819214151414.3
1638428272727.3
3276852456855.0
65536124117150130.3
131072314317280303.7
262144706593526608.3
5242881047106311901,100.0
10485762031206118151,969.0
20971523728372037073,718.3
41943047064713669087,036.0
838860814093141251406114,093.0
1677721627279271882745827,308.3
3355443256105560305637056,168.3
67108864109954113090113524112,189.3
134217728226385220107225664224,052.0
268435456450575452140444382449,032.3

테스트 케이스 2

이번에는 여러 데이터를 비교해 봐야하는 경우로 예제를 만들어 보았다. 예제로 만든것이어서 따로 integer overflow등은 고려하지 않았다. (경험상 각 서버의 사용 리소스 총 합을 구하는 경우가 많아서 꾸역꾸역 집어넣었다.)

// SOA, ESukmean
#include <stdlib.h>
#include <stdio.h>
#include <time.h>

typedef struct server {
	unsigned long* server_id;

	unsigned long* tx;
	unsigned long* rx;
	unsigned long* conn;
} Server;

inline long rnd(){
	return rand() >> 1;
}
void assign(Server* list, int size) {
	for(int i = 0; i < size; i++) {
		list->conn[i] = i;
		list->rx[i] = rnd();
		list->tx[i] = rnd();
		list->conn[i] = rnd();
	}
}

int main(int argc, char* argv[]) {
	int size = atoi(argv[1]);

	Server list;
	list.server_id = malloc(sizeof(unsigned long) * size);
	list.tx = malloc(sizeof(unsigned long) * size);
	list.rx = malloc(sizeof(unsigned long) * size);
	list.conn = malloc(sizeof(unsigned long) * size);
	assign(&list, size);

	unsigned long long sum = 0;
	unsigned long max = 0;

	clock_t end;
	// rnd()는 2^31까지만 표현함. 찾는값이 100% 없을테니 배열 전체를 탐색해야함.
	unsigned long find_sid = ~0; 
	unsigned long max_tx = 0;
	unsigned long max_rx = 0;
	clock_t start = clock();

	for(int i = 0; i < size; i++){
		if (list.server_id[i] == find_sid) break;
	}
	for(int i = 0; i < size; i++){
		if (list.tx[i] > max_tx) max_tx = list.tx[i];
	}
	for(int i = 0; i < size; i++){
		if (list.tx[i] > max_rx) max_rx = list.tx[i];
	}
	end = clock();

	printf("%d -> %ld ms ==> %ld", size, end - start, find_sid + max_tx + max_tx);
}
// AOS, ESukmean
#include <stdlib.h>
#include <stdio.h>
#include <time.h>

typedef struct server {
	unsigned long server_id; //8-byte
	
	unsigned long tx; //8-byte
	unsigned long rx; //8-byte
	unsigned long conn; // 8-byte
} Server;

inline long rnd(){
	return rand() >> 1;
}
void assign(Server* list, int size) {
	for(int i = 0; i < size; i++) {
		list[i].conn = i;
		list[i].rx = rnd();
		list[i].tx = rnd();
		list[i].conn = rnd();
	}
}

int main(int argc, char* argv[]) {
	int size = atoi(argv[1]);

	Server* list = malloc(sizeof(Server) * size);
	assign(list, size);

	unsigned long max = 0;

	clock_t end;
	// rnd()는 2^31까지만 표현함. 찾는값이 100% 없을테니 배열 전체를 탐색해야함.
	unsigned long find_sid = ~0; 
	unsigned long max_tx = 0;
	unsigned long max_rx = 0;
	clock_t start = clock();

	for(int i = 0; i < size; i++){
		if (list[i].server_id == find_sid) break;
	}
	for(int i = 0; i < size; i++){
		if (list[i].tx > max_tx) max_tx = list[i].tx;
	}
	for(int i = 0; i < size; i++){
		if (list[i].tx > max_rx) max_rx = list[i].tx;
	}
	end = clock();

	printf("%d -> %ld ms ==> %ld", size, end - start, find_sid + max_tx + max_tx);
}

for과 if문이 늘어난 만큼, 결과는 더더욱 벌어졌다.

SoA로 실행시
배열의 갯수1회 실행2회 실행3회 실행평균 실행시간 (ms)
11232.0
22232.3
42222.0
82232.3
161211.3
322222.0
642222.0
1282222.0
2562222.0
5122232.3
10244333.3
20486655.7
40969898.7
819215141213.7
1638427252826.7
3276849494547.7
655368910010497.7
13107217718178145.3
262144375153346291.3
524288388383374381.7
1048576653705807721.7
20971521349131514271,363.7
41943042705271727722,731.3
83886085222516450985,161.3
1677721610163102551022210,213.3
3355443220839205162028520,546.7
6710886440349406254019240,388.7
13421772880114800538050780,224.7
268435456159693160088160033159,938.0
AoS로 실행시
배열 크기1회 실행2회 실행3회 실행평균 실행시간 (ms)
13333.0
22222.0
42322.3
82121.7
162222.0
322222.0
642121.7
1282232.3
2562211.7
5123222.3
10243433.3
20486444.7
40967787.3
819215141314.0
1638422272524.7
3276845434444.0
65536107104120110.3
131072229293227249.7
262144560547570559.0
5242881020111310471,060.0
10485762006185719911,951.3
20971523706362736323,655.0
41943046997708071097,062.0
838860813628140931373813,819.7
1677721627326269852766727,326.0
3355443255055552455526355,187.7
67108864111401110261110215110,625.7
134217728221639221538224644222,607.0
268435456435305446244443533441,694.0

최적화 옵션을 다르게 하면?

위의 코드는 -O3 옵션으로 컴파일 했을때의 결과이다. -O3에는 Auto Vectorization등의 옵션이 섞여 있어서 CPU캐싱만 보기에는 조금 애매하다. 컴파일러가 개입할 수 있는 상황이라면 위와 같은 추세로 실행시간이 나오겠지만, 그렇지 않다면 얼마나 차이날까? 그래서 -O0로 배열 크기가 268,435,456일때를 기준으로 빠르게 돌려보았다. 

테스트 케이스 1: AoS 725347ms, SoA 671128ms
테스트 케이스 2: AoS 2578004ms, SoA 1670109ms

결론

여러 상황과 구조에 따라서 적합한 메모리 구조는 다를 수 있다. 적절한 메모리 구조를 사용하는것은 그렇지 않을때와 비교했을때 위와같이 큰 차이를 만들수도 있다. 특히 대용량 처리 시스템이거나 상당한 양의 메모리를 접근해야 할 때 자신의 코드를 열어보고 좀 더 적합한 – 캐시 히트율이 높은 – 방법을 찾아보자.

후기

사실 테스트 케이스1은 AoS(Array속에 Struct을 저장하는식)이 더 나을것이라 생각했습니다. SoA으로 접근하려면 두개의 배열을 번갈아가며 읽어야 하니까 오히려 비효율적일것이라 생각했습니다. 근데 결과를 보니까 제 추측이 틀렸네요. 한번에 저장하는 캐시의 크기는 64kb이지만 8개의 캐시 라인을 가지고 있는 만큼, 두 배열 모두 캐싱이 된 것 같습니다. 두 배열 모두 캐싱이 되었다면 더 빠르겠네요.

테스트 케이스1에서 결과가 이상해서 혹시나 GCC의 -O3 플레그가 영향을 끼치지 않았을까? 생각이 들었습니다. -O3 플레그를 빼고 컴파일을 해도 결과는 둘 다 시간이 늘었긴 하지만 추세는 비슷하다는것을 확인할 수 있었습니다. 한편, -O3가 적용이 되면 GCC에서 자동 벡터라이징 (SIMD화)을 진행하기에 SoA에서 더욱 파워풀한 컴퓨팅을 느낄 수도 있을겁니다.

AoS와 SoA모두 적합한 케이스가 따로있을거라 봤는데.. 왠만해선 SoA가 더 나을것 같다~ 가 제 결론입니다.

C, C++, Rust등이 아닌 다른언어에서는 데이터가 넓게넓게 퍼저있을 가능성이 있습니다. 이것들을 제대로 사용하고 싶으면 저 수준의 언어를 사용하는것이 더 효과적일것이라 생각합니다.

답글 남기기

이메일 주소는 공개되지 않습니다.

댓글을 작성하기 위해 아래의 숫자를 입력해 주세요. *Captcha loading...