최적화 도중에 난제를 만났습니다.(지역성 관련)
글쓴이: Samuro / 작성시간: 금, 2016/04/29 - 12:20오후
while(likely(i<count)){
map[randome_index()]++;
i++;
}현재 count는 약 150만번 정도, 맵의 전체 크기는 800만 정도이고 unsigned char 타입이니 800만 바이트정도 됩니다.
여기서 0~800만 사이의 랜덤 넘버가 발생해서 랜덤 넘버를 인덱스로 맵에 접근해서 값을 1씩 증가시켜 줍니다.
제가 만들고 있는 프로그램의 가장 큰 성능요인이 이부분인데, 맵의 인덱스를 0부터 순차적으로 접근할때와 비교해서
정확히 측정이 안될정도로 엄청난 성능 감소가 발생합니다. random넘버를 생성하는 함수는 더이상 건드릴 수 없습니다.
도대체 어떻게 해야 지역성을 살릴 수 있을까요?
Forums:
이러면 어떨까요? 먼저 150만개에 대한 random
이러면 어떨까요?
먼저 150만개에 대한 random 숫자를 미리 계산해 놓고 그 후에 map[] 연산을 하는 것으로요.
while(likely(i<count)){ temp[i] = random_index(); i++; } i=0; while(likely(i<count)){ map[temp[i]]++; i++; }감사합니다.. 제가 한가지 놓치고 있었네요.
나름 지역성 신경쓰면서 짠다고 생각했는데, 크게 반성했습니다. 저는 랜덤 인덱스를 모아서 맵 array를 순차적으로 접근하는 방법만 생각했는데, 랜덤 인덱스를 받아오는 작업때문에 맵에 대한 지역성이 깨지는걸 생각못했었네요. 덕분에 크게 개선되었습니다. 저부분에서 소모하는 시간이 거의 반으로 줄어들었어요. 정말 감사합니다!
다행이네요. 만약 실시간 random 연산 결과가
다행이네요. 만약 실시간 random 연산 결과가 필요하지 않다면 먼저 random() 배열을 한 100개 정도 set을 만들어 놓고 실제 맵 계산에는 그 중에 하나를 불러서 쓸수도 있습니다.
적용가능한 상황인지는 모르겠습니다만, 라스코니님
적용가능한 상황인지는 모르겠습니다만,
라스코니님 코드에서 temp를 sort한 후에 map에 적용하는 방법은 사용할 수 없는 건가요? 적용가능하다면 말씁하신 map에 순차적으로 접근하게 되는 걸로 보입니다.
간단히 테스트해보았는데, 소트 오버헤드가 temp가
간단히 테스트해보았는데, 소트 오버헤드가 temp가 정렬되었을 때 얻는 이득보다 너무 크기 때문에 오히려 가장 성능이 떨어지네요.
저도 고려해봤던 부분인데
100만개가 넘는 숫자의 정렬 오버헤드가 굉장히 클거같아서 제외했던 방법인데 직접 테스트 해주셨네요 감사합니다 ㅎㅎ. 현재는 라스코니님 방법대로 사용중입니다.
공부가 되네요. 감사합니다.
공부가 되네요. 감사합니다.
심심해서 잠깐 샘플 프로그램을 만들어봤는데 재밌는
심심해서 잠깐 샘플 프로그램을 만들어봤는데 재밌는 결과가 나왔네요.
이미 사용중이실지도 모르겠지만.. 최적화 옵션도 함께 사용해 보세요. 정말 빨라 집니다. :)
without mapper
#include <stdio.h> #include <stdlib.h> #include <time.h> int main(int argc, char** argv) { int random; int *arr_buf; int i; time_t t; arr_buf = calloc(sizeof(int), 50000000); srand((unsigned) time(&t)); for(i = 0 ; i < 15000000; i++) { random = rand() % 50000000; arr_buf[random]++; } return 0; } $ gcc -O3 -o main main.c $ time ./main real 0m0.660s user 0m0.612s sys 0m0.048swith map[er
#include <stdio.h> #include <stdlib.h> #include <time.h> int main(int argc, char** argv) { int random; int *arr_buf; int *arr_ran; int i; time_t t; arr_buf = calloc(sizeof(int), 50000000); arr_ran = calloc(sizeof(int), 15000000); srand((unsigned) time(&t)); for(i = 0; i < 15000000; i++) { random = rand() % 50000000; arr_ran[i] = random; } for(i = 0; i < 15000000; i++) { arr_buf[arr_ran[i]]++; } return 0; } $ gcc -o main2 -O3 main2.c $ time ./main2 real 0m0.148s user 0m0.140s sys 0m0.008s---------------------------------
제일 왼쪽이 저입니다 :)
저도 놀랐습니다.
생각보다 굉장히 빨라져서 놀랐습니다ㅎㅎ. 루프를 도는 횟수를 줄이는게 좋다고만 생각했었는데 루프를 늘리더라도 지역성을 살리는게 중요하네요
저도 심심해서 잠깐 돌려 봤는데, 결과가 다르네요.
제가 코드를 아무리 봐도 with_mapper 코드가 왜 지역성이 더 좋은지 이해가 안되네요.
혹시 설명해 주실수 있으세요.
그리고 without_mapp와 with_mapper 코드를 실행하면,
매번 실행 할 때 마다 조금씩 다른 결과가 나오긴 하지만, 의미 있는 결과는 아니네요.
시스템의 차이나, 컴파일러의 차이라고 보기도 어렵고....
[ ~/src]$ free total used free shared buffers cached Mem: 132002928 55296016 76706912 1720 335032 39023888 -/+ buffers/cache: 15937096 116065832 Swap: 10485756 0 10485756cpu정보 - 24 core
CPU는 꾸준히 클럭을 높이는 것에 투자를 했지만 곧
CPU는 꾸준히 클럭을 높이는 것에 투자를 했지만 곧 성능상 한계에 도달했습니다. 그래서 소프트웨어 실행 성능을 가능한 높이기 위해서 나온게 파이프라인 처리, 캐쉬 확장, 분기 예측 처리 등입니다.
결론적으로 본다면 CPU는 캐쉬 등과 결합해서 가장 최근에 했던 일을 다시 할 때 (시스템 지연을 최소화하는 과정을 통해) 제일 빨리 수행이 됩니다.
제일 최악은 하드 디스크에서 다른 코드/데이터를 로드해서 불러들이는 상황입니다. 이것은 1차 캐쉬, 2차 캐쉬에서도 못찾고 심지어 램에 로딩조차 안되었을 때 발생합니다.
어느 정도 코드가 완성되고 마지막 단계에서 최적화를 할 때 이런 지역성(locality)을 고려하면 좋은 효과를 볼수 있는 경우가 많습니다.
저는 gcc-4.8 쓰는 Ubuntu-14.04
저는 gcc-4.8 쓰는 Ubuntu-14.04 quad-core 환경에서 해 봤는데,
최적화옵션 없이 컴파일하면 아래와 같이 나오고
gcc -O3 옵션으로 빌드하면 더 눈에 띄는 차이가 납니다.
이렇게 실행해보면 차이가 나기는 하는데,
이런 차이가 지역성이 높아지기 때문이라는 것은 저도 이해가 안 됩니다.
with_mapper는 랜덤인덱스 임시저장용으로 정수 1500만개짜리 메모리가 추가할당되고
이 메모리에 순차쓰기/순차읽기 동작이 추가되었을 뿐
without_mapper와 마찬가지로 정수 5000만개의 메모리에 대한 랜덤 접근은 그대로 유지되고 있는데
어떤 면에서 지역성이 높아지고 성능이 좋아지는지 감을 못잡겠네요.
with, without 코드에서 눈에 보이는
with, without 코드에서 눈에 보이는 차이는
(1) 케이스 for(i = 0 ; i < 15000000; i++) { random = rand() % 50000000; arr_buf[random]++; }와
(2) 케이스 for(i = 0; i < 15000000; i++) { random = rand() % 50000000; arr_ran[i] = random; } for(i = 0; i < 15000000; i++) { arr_buf[arr_ran[i]]++; }와 같이 똑같은 일을 하는 루프를 하나로 하느냐 여러개로 나누느냐의 차이입니다.
얼핏 아래의 코드(케이스 (2))가 복잡해 보이나 실제 수행시간은 더 짧은 이유는
(가정컨대) 케이스 (1)에서는 rand() 함수가 호출되면서 결과적으로 현재 사용되어지고 있는 캐시 영역에서 벗어날 경우가 발생한다는 것입니다.
이 상황이 매번 1500만번 반복됨으로써 캐시가 재사용될 수 있는 가능성을 최악으로 가져가고 있습니다.
케이스 (2)에서는 루프를 두번으로 나누고 심지어 첫번째 루프에서 arr_ran[i]에 방금 만들어진 랜덤값을 임시 보관하는 잉여짓(?)을 하고 있음에도 불구하고 전체적인 속도가 더 빠른 것은 두번째 루프에서 (캐시 hit이 발생할 확률이 많은) 비슷한 영역을 액세스하도록 구조화하였기 때문이라고 생각됩니다.
예를 들어 케이스 (1), (2)에서 arr_buf[random]++;, arr_buf[arr_ran[i]]++; 부분을 제거하고 실행하면 오히려 케이스 (1)이 좀더 빨리 실행될 것이라고 생각됩니다. 케이스 (2)가 arr_ran[i]에 방금 만들어진 랜덤값을 임시 보관하는 잉여짓(?)을 하고 있기 때문입니다.
설명 고맙습니다. 지금도 잘 이해는 못하고 있는
설명 고맙습니다.
지금도 잘 이해는 못하고 있는 상태입니다만..
(1) 그 자체로서 CPU 캐시 활용에 유리한 코드
(2) 컴파일러가 최적화하기에 유리한 코드
이렇게 두 가지가 머리속에서 뒤섞이는 느낌입니다.
with_mapper는 (2)에 해당하는 코드임은 확실한 것 같은데
(1)에도 해당되는지는 실감하지 못한다고 하면 비슷할 것 같네요.
(1)과 (2)가 어차피 같은 얘기인가 싶기도 하고,
시간을 두고 더 생각해봐야겠습니다.
음 ..
with_mapper 의 경우 without 에 비해 cache miss 가 상당히 적게 나고 있던데..
이게 결과에 큰 영향을 미치고 있는게 아닐까 싶네요.
특히 with_mapper 의 arr_buf[arr_ran[i]]++; 부분에서 cache miss 가 없는게...;;;
$ cg_annotate --auto=yes wom.cache -------------------------------------------------------------------------------- I1 cache: 32768 B, 64 B, 8-way associative D1 cache: 32768 B, 64 B, 8-way associative LL cache: 31457280 B, 64 B, 30-way associative Command: ./without_mapper Data file: wom.cache Events recorded: Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw Events shown: Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw Event sort order: Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw Thresholds: 0.1 100 100 100 100 100 100 100 100 Include dirs: User annotated: Auto-annotation: on -------------------------------------------------------------------------------- Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw -------------------------------------------------------------------------------- 936,564,664 795 790 255,043,282 14,999,970 12,642,952 117,515,227 3,125,560 3,125,528 PROGRAM TOTALS -------------------------------------------------------------------------------- Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw file:function -------------------------------------------------------------------------------- 389,524,179 2 2 120,002,480 0 0 60,001,240 0 0 /build/eglibc-3GlaMS/eglibc-2.19/stdlib/random_r.c:random_r 255,000,000 3 3 90,000,000 0 0 15,000,000 0 0 /build/eglibc-3GlaMS/eglibc-2.19/stdlib/random.c:random 195,000,021 1 1 15,000,004 14,997,528 12,640,870 15,000,006 0 0 /home/ymir/prog/testc/wom.c:main 60,000,000 1 1 15,000,000 0 0 15,000,000 0 0 /build/eglibc-3GlaMS/eglibc-2.19/stdlib/rand.c:rand 21,875,016 4 4 1 1 1 12,500,004 3,125,001 3,125,001 /build/eglibc-3GlaMS/eglibc-2.19/string/../sysdeps/x86_64/memset.S:memset 15,000,210 21 18 15,000,104 6 5 33 1 1 ???:??? -------------------------------------------------------------------------------- -- Auto-annotated source: /home/ymir/prog/testc/wom.c -------------------------------------------------------------------------------- Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw . . . . . . . . . #include <stdio.h> . . . . . . . . . #include <stdlib.h> . . . . . . . . . #include <time.h> . . . . . . . . . . . . . . . . . . int main(int argc, char** argv) 4 1 1 0 0 0 3 0 0 { . . . . . . . . . int random; . . . . . . . . . int *arr_buf; . . . . . . . . . int i; . . . . . . . . . time_t t; . . . . . . . . . 4 0 0 0 0 0 1 0 0 arr_buf = calloc(sizeof(int), 50000000); . . . . . . . . . 6 0 0 0 0 0 2 0 0 srand((unsigned) time(&t)); . . . . . . . . . 30,000,000 0 0 0 0 0 0 0 0 for(i = 0 ; i < 15000000; i++) { 135,000,001 0 0 0 0 0 15,000,000 0 0 random = rand() % 50000000; 30,000,000 0 0 15,000,000 14,997,527 12,640,869 0 0 0 arr_buf[random]++; . . . . . . . . . } . . . . . . . . . . . . . . . . . . return 0; 6 0 0 4 1 1 0 0 0 } -------------------------------------------------------------------------------- The following files chosen for auto-annotation could not be found: -------------------------------------------------------------------------------- /build/eglibc-3GlaMS/eglibc-2.19/stdlib/rand.c /build/eglibc-3GlaMS/eglibc-2.19/stdlib/random_r.c /build/eglibc-3GlaMS/eglibc-2.19/stdlib/random.c /build/eglibc-3GlaMS/eglibc-2.19/string/../sysdeps/x86_64/memset.S -------------------------------------------------------------------------------- Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw -------------------------------------------------------------------------------- 21 0 0 6 100 100 13 0 0 percentage of events annotated$ cg_annotate --auto=yes wm.cache -------------------------------------------------------------------------------- I1 cache: 32768 B, 64 B, 8-way associative D1 cache: 32768 B, 64 B, 8-way associative LL cache: 31457280 B, 64 B, 30-way associative Command: ./with_mapper Data file: wm.cache Events recorded: Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw Events shown: Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw Event sort order: Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw Thresholds: 0.1 100 100 100 100 100 100 100 100 Include dirs: User annotated: Auto-annotation: on -------------------------------------------------------------------------------- Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw -------------------------------------------------------------------------------- 921,252,128 793 788 240,043,278 2,442 2,083 123,765,229 1,875,561 1,875,529 PROGRAM TOTALS -------------------------------------------------------------------------------- Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw file:function -------------------------------------------------------------------------------- 389,524,179 2 2 120,002,480 0 0 60,001,240 0 0 /build/eglibc-3GlaMS/eglibc-2.19/stdlib/random_r.c:random_r 255,000,000 3 3 90,000,000 0 0 15,000,000 0 0 /build/eglibc-3GlaMS/eglibc-2.19/stdlib/random.c:random 195,000,020 1 1 4 1 1 30,000,006 937,501 937,501 /home/ymir/prog/testc/wm.c:main 60,000,000 1 1 15,000,000 0 0 15,000,000 0 0 /build/eglibc-3GlaMS/eglibc-2.19/stdlib/rand.c:rand 15,000,210 21 18 15,000,104 6 5 33 1 1 ???:??? 6,562,516 4 4 1 1 1 3,750,004 937,501 937,501 /build/eglibc-3GlaMS/eglibc-2.19/string/../sysdeps/x86_64/memset.S:memset -------------------------------------------------------------------------------- -- Auto-annotated source: /home/ymir/prog/testc/wm.c -------------------------------------------------------------------------------- Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw . . . . . . . . . #include <stdio.h> . . . . . . . . . #include <stdlib.h> . . . . . . . . . #include <time.h> . . . . . . . . . . . . . . . . . . int main(int argc, char** argv) 4 1 1 0 0 0 3 0 0 { . . . . . . . . . int random; . . . . . . . . . int *arr_buf; . . . . . . . . . int *arr_ran; . . . . . . . . . int i; . . . . . . . . . time_t t; . . . . . . . . . . . . . . . . . . arr_buf = calloc(sizeof(int), 50000000); 4 0 0 0 0 0 1 0 0 arr_ran = calloc(sizeof(int), 15000000); . . . . . . . . . 5 0 0 0 0 0 2 0 0 srand((unsigned) time(&t)); . . . . . . . . . 30,000,000 0 0 0 0 0 0 0 0 for(i = 0; i < 15000000; i++) { 165,000,001 0 0 0 0 0 30,000,000 937,501 937,501 random = rand() % 50000000; . . . . . . . . . arr_ran[i] = random; . . . . . . . . . } . . . . . . . . . . . . . . . . . . . . . . . . . . . for(i = 0; i < 15000000; i++) { . . . . . . . . . arr_buf[arr_ran[i]]++; . . . . . . . . . } . . . . . . . . . . . . . . . . . . . . . . . . . . . return 0; 6 0 0 4 1 1 0 0 0 } -------------------------------------------------------------------------------- The following files chosen for auto-annotation could not be found: -------------------------------------------------------------------------------- /build/eglibc-3GlaMS/eglibc-2.19/string/../sysdeps/x86_64/memset.S /build/eglibc-3GlaMS/eglibc-2.19/stdlib/random_r.c /build/eglibc-3GlaMS/eglibc-2.19/stdlib/rand.c /build/eglibc-3GlaMS/eglibc-2.19/stdlib/random.c -------------------------------------------------------------------------------- Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw -------------------------------------------------------------------------------- 21 0 0 0 0 0 24 50 50 percentage of events annotated되면 한다! / feel no sorrow, feel no pain, feel no hurt, there's nothing gained.. only love will then remain.. 『 Ｍｉｚｚ 』
헉.. valgrind로 cache miss까지 볼수
헉.. valgrind로 cache miss까지 볼수 있군요. 또 좋은 것 배웠습니다. 감사합니다.
동감입니다. 저도 좋은것 배워갑니다. 글 보면서 엄청
동감입니다. 저도 좋은것 배워갑니다. 글 보면서 엄청 놀랬네요. ㄷ ㄷ ㄷ
감사합니다. :)
---------------------------------
제일 왼쪽이 저입니다 :)
arr_buf[arr_ran[i]]++; 캐시 미스가 없는게 이해가 안되네요.
arr_buf[arr_ran[i]]++; 이 라인에서 어째서 캐시 미스가 없는 걸까요?
arr_ran 배열에는 50,000,000 범위내의 숫자가 15,000,000개 들어 있고,
arr_ran 배열을 i값에 따라 순차 접근하기 때문에 캐시 미스가 적은 것(없을수가 있나요?)은 이해가 됩니다.
그러나 만일 arr_ran[1]=1이고, arr_ran[2]=50,000,000이라면, arr_buf[1]++, arr_buf[50,000,000]++ 이렇게 연산을 할텐데,
이때는 캐시 미스 발생 할 거라고 예상 됩니다.
즉 arr_ran[] 값이 정말 랜덤하다면, arr_buf[] 접근은 캐시 미스가 발생 할거라고 예상 되는데, 왜 캐시 미시가 없다고 나올까요?
혹시 램덤 값이 덜 램덤하거나, 캐쉬 라인 범위내에서 랜덤 한 걸까요?
음 ..
저도 그 부분이 아직 이해가 안 가고 있습니다만.. 최적화 옵션에 무슨 트릭이 있는 것 같네요.
일단, with_mapper 를 최적화 옵션 없이 빌드해서 보면, without 에 비해 80~90% 정도의 시간이 소요되는데..
전체 D reference 횟수가 363M 에서 612M 정도로 증가하고, 해당 라인에서 cache miss 가 충분히 많이 발생하네요.
그러고 보니, -O3 로 빌드한 경우에 with 와 without 의 D refs 횟수가 비슷한 걸로 봐서..
오히려 그 루프는 호출 되지 않고 다르게 처리된 게 아닐까 싶은데.. 어셈 쪽은 까막눈이라..;;
$ cg_annotate --auto=yes wm_no_opt.cache -------------------------------------------------------------------------------- I1 cache: 32768 B, 64 B, 8-way associative D1 cache: 32768 B, 64 B, 8-way associative LL cache: 31457280 B, 64 B, 30-way associative Command: ./with_mapper_no_opt Data file: wm_no_opt.cache Events recorded: Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw Events shown: Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw Event sort order: Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw Thresholds: 0.1 100 100 100 100 100 100 100 100 Include dirs: User annotated: Auto-annotation: on -------------------------------------------------------------------------------- Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw -------------------------------------------------------------------------------- 1,371,564,933 801 796 435,043,339 15,937,665 13,770,168 177,515,267 4,063,067 4,063,031 PROGRAM TOTALS -------------------------------------------------------------------------------- Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw file:function -------------------------------------------------------------------------------- 630,000,029 3 3 195,000,004 15,935,209 13,768,072 75,000,011 937,500 937,500 /home/ymir/prog/testc/wm.c:main 389,524,179 2 2 120,002,480 0 0 60,001,240 0 0 /build/eglibc-3GlaMS/eglibc-2.19/stdlib/random_r.c:random_r 255,000,000 3 3 90,000,000 0 0 15,000,000 0 0 /build/eglibc-3GlaMS/eglibc-2.19/stdlib/random.c:random 60,000,000 1 1 15,000,000 0 0 15,000,000 0 0 /build/eglibc-3GlaMS/eglibc-2.19/stdlib/rand.c:rand 21,875,016 4 4 1 1 1 12,500,004 3,125,001 3,125,001 /build/eglibc-3GlaMS/eglibc-2.19/string/../sysdeps/x86_64/memset.S:memset 15,000,211 21 18 15,000,105 7 6 33 1 1 ???:??? -------------------------------------------------------------------------------- -- Auto-annotated source: /home/ymir/prog/testc/wm.c -------------------------------------------------------------------------------- Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw . . . . . . . . . #include <stdio.h> . . . . . . . . . #include <stdlib.h> . . . . . . . . . #include <time.h> . . . . . . . . . . . . . . . . . . int main(int argc, char** argv) 5 1 1 0 0 0 3 0 0 { . . . . . . . . . int random; . . . . . . . . . int *arr_buf; . . . . . . . . . int *arr_ran; . . . . . . . . . int i; . . . . . . . . . time_t t; . . . . . . . . . 4 0 0 0 0 0 2 0 0 arr_buf = calloc(sizeof(int), 50000000); 4 0 0 0 0 0 2 0 0 arr_ran = calloc(sizeof(int), 15000000); . . . . . . . . . 5 1 1 0 0 0 2 0 0 srand((unsigned) time(&t)); . . . . . . . . . 45,000,004 1 1 30,000,001 0 0 1 0 0 for(i = 0; i < 15000000; i++) { 240,000,000 0 0 15,000,000 0 0 45,000,000 0 0 random = rand() % 50000000; 105,000,000 0 0 45,000,000 0 0 15,000,000 937,500 937,500 arr_ran[i] = random; . . . . . . . . . } . . . . . . . . . . . . . . . . . . 45,000,004 0 0 30,000,001 0 0 1 0 0 for(i = 0; i < 15000000; i++) { 195,000,000 0 0 75,000,000 15,935,208 13,768,071 15,000,000 0 0 arr_buf[arr_ran[i]]++; . . . . . . . . . } . . . . . . . . . . . . . . . . . . 1 0 0 0 0 0 0 0 0 return 0; 2 0 0 2 1 1 0 0 0 } -------------------------------------------------------------------------------- The following files chosen for auto-annotation could not be found: -------------------------------------------------------------------------------- /build/eglibc-3GlaMS/eglibc-2.19/stdlib/random_r.c /build/eglibc-3GlaMS/eglibc-2.19/stdlib/rand.c /build/eglibc-3GlaMS/eglibc-2.19/stdlib/random.c /build/eglibc-3GlaMS/eglibc-2.19/string/../sysdeps/x86_64/memset.S -------------------------------------------------------------------------------- Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw -------------------------------------------------------------------------------- 46 0 0 45 100 100 42 23 23 percentage of events annotated되면 한다! / feel no sorrow, feel no pain, feel no hurt, there's nothing gained.. only love will then remain.. 『 Ｍｉｚｚ 』
지역성을 고려해서 코딩하기가....
참 어려운듯해요. 나름 고민을 해서 알고리즘을 구현했은데, -O3 한방에 예상치 못한 결과가 나오기도하고, 가끔은 -O3에서 paaaaanic !도 발생하고....
이럴때는 어셈을 해야 되나 싶기도 하고.... C만으로를 부족할때로 있는듯 하고...
10G 트래픽을 처리하려면, 초당 14.88M PPS의 속도로 연산을 해야 하는데, 지역성을 고려해서 코딩해보려해도 원하는대로 잘 동작을 안하더라구요....
어째든 다시 한번 최적화/지역성을 중요성을 알고 갑니다...
이렇게 캐시관련 분석을 하는 방법이 있군요. 많이
이렇게 캐시관련 분석을 하는 방법이 있군요.
많이 배웁니다 ^^
-O3 옵션으로 최적화된 경우 with_mapper의 캐시미스 비율이 뚝 떨어지면서
실행시간도 크게 단축되는 모습이 뚜렷이 드러나네요.
컴파일러가 어떤 식으로 캐시미스를 줄인 것인지는 모릅니다만
어쨌든 이 경우의 성능차이는 캐시미스 차이 덕분이라는 실감이 듭니다.
그런데, 최적화하지 않고 그냥 컴파일한 경우에는 아래와 같이
명령어캐시와 데이터캐시, L3 캐시 모두에서 총 레퍼런스 횟수 및 캐시미스 횟수가
with_mapper쪽이 without_mapper보다 더 크게 나옵니다.
캐시미스 비율만 봐서는 서로 옥신각신하는 모습이지만
총 레퍼런스 횟수와 캐시미스 횟수는 읽기든 쓰기든 with_mapper 쪽이 더 높습니다.
결국 with_mapper 실행시 더 많은 메모리참조가 일어나고 캐시미스도 더 많이 발생한다는 뜻 같은데
막상 실행시간을 재보면 with_mapper가 without_mapper의 2/3 정도밖에 안 걸립니다.
이 경우엔 캐시미스가 아닌 다른 요인이 실행시간을 가름하고 있는 것 아닐까요?
gcc에 -O3 옵션을 주면 캐시미스 비율이 뚝
gcc에 -O3 옵션을 주면 with_mapper의 캐시미스 비율이 뚝 떨어지는 이유는
최적화 과정에서 과감한 코드생략이 일어났기 때문인 것 같습니다.
arr_buf에 대한 calloc()도 생략되고,
arr_buf의 값들을 증가시키는 두 번째 for 루프도 통째로 생략되어
마치 arr_buf 관련된 코드는 존재하지 않는 것처럼 컴파일되네요.
하지만 main()의 마지막 부분을 아래와 같이 수정해서 arr_buf의 쓰임새를 만들면
이런 과감한 생략이 불가능해지고 컴파일 결과도 달라집니다.
//return 0; return arr_buf[rand()%50000000];실행시간도 without_mapper는 수정전과 거의 같은 0.71s 수준이지만,
with_mapper는 0.190s --> 0.415s 수준으로 올라갑니다.
valgrind, cg_annotate 결과는 아래에 첨부했습니다.
한 가지 눈에 띄는 점은,
코드 수정 전에는 with_mapper가 캐시미스 빈도가 현저히 적었지만
지금은 with_mapper가 without_mapper보다 전체 메모리 레퍼런스 횟수도 더 많고
캐시미스 횟수도 더 많은 것으로 나온다는 것입니다.
gcc 최적화를 끈 상태로 컴파일했을 때와 같아진 것이죠.
그럼에도 실행시간은 더 짧다는 점도 같습니다.
결국, gcc 최적화를 하든 하지 않든
메모리 레퍼런스 횟수도 with_mapper 쪽이 더 많고 캐시미스 휫수도 더 많은 셈인데,
with_mapper에서 for 루프를 분리함으로써 얻은 성능향상의 이유가 뭔지
저는 아직 머리에 그려지지 않는군요. 어렵네요..
chanik@dev-ubuntu:~/test/locality$ gcc -g -W -Wall -O3 -o with_mapper with_mapper.c ... chanik@dev-ubuntu:~/test/locality$ gcc -g -W -Wall -O3 -o without_mapper without_mapper.c ... chanik@dev-ubuntu:~/test/locality$ valgrind --tool=cachegrind --cachegrind-out-file=wm.cache ./with_mapper ==9668== Cachegrind, a cache and branch-prediction profiler ==9668== Copyright (C) 2002-2013, and GNU GPL'd, by Nicholas Nethercote et al. ==9668== Using Valgrind-3.10.1 and LibVEX; rerun with -h for copyright info ==9668== Command: ./with_mapper ==9668== --9668-- warning: L3 cache found, using its data for the LL simulation. ==9668== ==9668== I refs: 1,011,564,948 ==9668== I1 misses: 800 ==9668== LLi misses: 788 ==9668== I1 miss rate: 0.00% ==9668== LLi miss rate: 0.00% ==9668== ==9668== D refs: 402,558,599 (270,043,326 rd + 132,515,273 wr) ==9668== D1 misses: 20,000,686 ( 15,937,619 rd + 4,063,067 wr) ==9668== LLd misses: 19,415,805 ( 15,352,774 rd + 4,063,031 wr) ==9668== D1 miss rate: 4.9% ( 5.9% + 3.0% ) ==9668== LLd miss rate: 4.8% ( 5.6% + 3.0% ) ==9668== ==9668== LL refs: 20,001,486 ( 15,938,419 rd + 4,063,067 wr) ==9668== LL misses: 19,416,593 ( 15,353,562 rd + 4,063,031 wr) ==9668== LL miss rate: 1.3% ( 1.1% + 3.0% ) chanik@dev-ubuntu:~/test/locality$ valgrind --tool=cachegrind --cachegrind-out-file=wom.cache ./without_mapper ==9670== Cachegrind, a cache and branch-prediction profiler ==9670== Copyright (C) 2002-2013, and GNU GPL'd, by Nicholas Nethercote et al. ==9670== Using Valgrind-3.10.1 and LibVEX; rerun with -h for copyright info ==9670== Command: ./without_mapper ==9670== --9670-- warning: L3 cache found, using its data for the LL simulation. ==9670== ==9670== I refs: 936,564,713 ==9670== I1 misses: 797 ==9670== LLi misses: 785 ==9670== I1 miss rate: 0.00% ==9670== LLi miss rate: 0.00% ==9670== ==9670== D refs: 372,558,514 (255,043,277 rd + 117,515,237 wr) ==9670== D1 misses: 18,125,547 ( 14,999,983 rd + 3,125,564 wr) ==9670== LLd misses: 17,498,539 ( 14,373,011 rd + 3,125,528 wr) ==9670== D1 miss rate: 4.8% ( 5.8% + 2.6% ) ==9670== LLd miss rate: 4.6% ( 5.6% + 2.6% ) ==9670== ==9670== LL refs: 18,126,344 ( 15,000,780 rd + 3,125,564 wr) ==9670== LL misses: 17,499,324 ( 14,373,796 rd + 3,125,528 wr) ==9670== LL miss rate: 1.3% ( 1.2% + 2.6% ) chanik@dev-ubuntu:~/test/locality$ cg_annotate --auto=yes wm.cache -------------------------------------------------------------------------------- I1 cache: 32768 B, 64 B, 4-way associative D1 cache: 32768 B, 64 B, 8-way associative LL cache: 8388608 B, 64 B, 16-way associative Command: ./with_mapper Data file: wm.cache Events recorded: Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw Events shown: Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw Event sort order: Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw Thresholds: 0.1 100 100 100 100 100 100 100 100 Include dirs: User annotated: Auto-annotation: on -------------------------------------------------------------------------------- Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw -------------------------------------------------------------------------------- 1,011,564,948 800 788 270,043,326 15,937,619 15,352,774 132,515,273 4,063,067 4,063,031 PROGRAM TOTALS -------------------------------------------------------------------------------- Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw file:function -------------------------------------------------------------------------------- 389,524,205 2 2 120,002,488 4 4 60,001,244 0 0 /build/eglibc-3GlaMS/eglibc-2.19/stdlib/random_r.c:random_r 270,000,040 3 3 30,000,006 15,935,170 15,350,678 30,000,009 937,501 937,501 /home/chanik/test/locality/with_mapper.c:main 255,000,017 3 3 90,000,006 2 2 15,000,001 1 1 /build/eglibc-3GlaMS/eglibc-2.19/stdlib/random.c:random 60,000,004 1 1 15,000,001 0 0 15,000,001 0 0 /build/eglibc-3GlaMS/eglibc-2.19/stdlib/rand.c:rand 21,875,016 4 4 1 1 1 12,500,004 3,125,001 3,125,001 /build/eglibc-3GlaMS/eglibc-2.19/string/../sysdeps/x86_64/memset.S:memset 15,000,212 22 19 15,000,106 8 6 33 1 1 ???:??? -------------------------------------------------------------------------------- -- Auto-annotated source: /home/chanik/test/locality/with_mapper.c -------------------------------------------------------------------------------- Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw . . . . . . . . . #include <stdio.h> . . . . . . . . . #include <stdlib.h> . . . . . . . . . #include <time.h> . . . . . . . . . . . . . . . . . . int main(int argc, char** argv) 5 1 1 0 0 0 4 0 0 { . . . . . . . . . int random; . . . . . . . . . int *arr_buf; . . . . . . . . . int *arr_ran; . . . . . . . . . int i; . . . . . . . . . time_t t; . . . . . . . . . 4 0 0 0 0 0 1 0 0 arr_buf = calloc(sizeof(int), 50000000); 4 1 1 0 0 0 1 0 0 arr_ran = calloc(sizeof(int), 15000000); . . . . . . . . . 6 0 0 0 0 0 2 0 0 srand((unsigned) time(&t)); . . . . . . . . . 30,000,002 0 0 0 0 0 0 0 0 for(i = 0; i < 15000000; i++) { 165,000,001 1 1 0 0 0 30,000,000 937,500 937,500 random = rand() % 50000000; . . . . . . . . . arr_ran[i] = random; . . . . . . . . . } . . . . . . . . . . . . . . . . . . 30,000,000 0 0 0 0 0 0 0 0 for(i = 0; i < 15000000; i++) { 45,000,000 0 0 30,000,000 15,935,168 15,350,676 0 0 0 arr_buf[arr_ran[i]]++; . . . . . . . . . } . . . . . . . . . . . . . . . . . . . . . . . . . . . //return 0; 12 0 0 1 1 1 1 1 1 return arr_buf[rand()%50000000]; 6 0 0 5 1 1 0 0 0 } -------------------------------------------------------------------------------- The following files chosen for auto-annotation could not be found: -------------------------------------------------------------------------------- /build/eglibc-3GlaMS/eglibc-2.19/stdlib/random.c /build/eglibc-3GlaMS/eglibc-2.19/stdlib/rand.c /build/eglibc-3GlaMS/eglibc-2.19/stdlib/random_r.c /build/eglibc-3GlaMS/eglibc-2.19/string/../sysdeps/x86_64/memset.S -------------------------------------------------------------------------------- Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw -------------------------------------------------------------------------------- 27 0 0 11 100 100 23 23 23 percentage of events annotated chanik@dev-ubuntu:~/test/locality$ cg_annotate --auto=yes wom.cache -------------------------------------------------------------------------------- I1 cache: 32768 B, 64 B, 4-way associative D1 cache: 32768 B, 64 B, 8-way associative LL cache: 8388608 B, 64 B, 16-way associative Command: ./without_mapper Data file: wom.cache Events recorded: Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw Events shown: Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw Event sort order: Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw Thresholds: 0.1 100 100 100 100 100 100 100 100 Include dirs: User annotated: Auto-annotation: on -------------------------------------------------------------------------------- Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw -------------------------------------------------------------------------------- 936,564,713 797 785 255,043,277 14,999,983 14,373,011 117,515,237 3,125,564 3,125,528 PROGRAM TOTALS -------------------------------------------------------------------------------- Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw file:function -------------------------------------------------------------------------------- 389,524,205 2 2 120,002,488 0 0 60,001,244 0 0 /build/eglibc-3GlaMS/eglibc-2.19/stdlib/random_r.c:random_r 255,000,017 3 3 90,000,006 0 0 15,000,001 0 0 /build/eglibc-3GlaMS/eglibc-2.19/stdlib/random.c:random 195,000,032 2 2 15,000,005 14,997,552 14,370,934 15,000,007 0 0 /home/chanik/test/locality/without_mapper.c:main 60,000,004 1 1 15,000,001 0 0 15,000,001 0 0 /build/eglibc-3GlaMS/eglibc-2.19/stdlib/rand.c:rand 21,875,016 4 4 1 1 1 12,500,004 3,125,001 3,125,001 /build/eglibc-3GlaMS/eglibc-2.19/string/../sysdeps/x86_64/memset.S:memset 15,000,211 21 18 15,000,105 7 5 33 2 2 ???:??? -------------------------------------------------------------------------------- -- Auto-annotated source: /home/chanik/test/locality/without_mapper.c -------------------------------------------------------------------------------- Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw . . . . . . . . . #include <stdio.h> . . . . . . . . . #include <stdlib.h> . . . . . . . . . #include <time.h> . . . . . . . . . . . . . . . . . . int main(int argc, char** argv) 4 1 1 0 0 0 3 0 0 { . . . . . . . . . int random; . . . . . . . . . int *arr_buf; . . . . . . . . . int i; . . . . . . . . . time_t t; . . . . . . . . . 4 0 0 0 0 0 1 0 0 arr_buf = calloc(sizeof(int), 50000000); . . . . . . . . . 6 1 1 0 0 0 2 0 0 srand((unsigned) time(&t)); . . . . . . . . . 30,000,000 0 0 0 0 0 0 0 0 for(i = 0 ; i < 15000000; i++) { 135,000,001 0 0 0 0 0 15,000,000 0 0 random = rand() % 50000000; 30,000,000 0 0 15,000,000 14,997,550 14,370,932 0 0 0 arr_buf[random]++; . . . . . . . . . } . . . . . . . . . . . . . . . . . . //return 0; 12 0 0 1 1 1 1 0 0 return arr_buf[rand()%50000000]; 5 0 0 4 1 1 0 0 0 } -------------------------------------------------------------------------------- The following files chosen for auto-annotation could not be found: -------------------------------------------------------------------------------- /build/eglibc-3GlaMS/eglibc-2.19/string/../sysdeps/x86_64/memset.S /build/eglibc-3GlaMS/eglibc-2.19/stdlib/random.c /build/eglibc-3GlaMS/eglibc-2.19/stdlib/random_r.c /build/eglibc-3GlaMS/eglibc-2.19/stdlib/rand.c -------------------------------------------------------------------------------- Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw -------------------------------------------------------------------------------- 21 0 0 6 100 100 13 0 0 percentage of events annotated음 ..
역시 with_mapper 의 두번째 loop 가 최적화 되면서 날아간 것이네요.
그럼에도 여전히 with_mapper 가 대략 10~40% 정도의 이득을 보이고 있다는게 특이합니다.
차이점이라면 without_mapper 의 경우 loop 내에서 function call + cache miss 조합이라는 것인데..;;
그래서 혹시나 해서 다음과 같이 without_mapper 의 rand 를 inline 으로 바꿔봤습니다.
http://opensource.apple.com/source/Libc/Libc-594.9.4/stdlib/FreeBSD/rand.c
#include <stdio.h> #include <stdlib.h> #include <time.h> static unsigned long next = 1; static void mysrand(unsigned long seed) { next = seed; } static inline int myrand(void) { long hi, lo, x; /* Can't be initialized with 0, so use another value. */ if (next == 0) next = 123459876; hi = next / 127773; lo = next % 127773; x = 16807 * lo - 2836 * hi; if (x < 0) x += 0x7fffffff; return ((next = x) % ((u_long) RAND_MAX + 1)); } int main(int argc, char **argv) { int random; int *arr_buf; int i; time_t t; arr_buf = calloc(sizeof(int), 50000000); mysrand((unsigned)time(&t)); for (i = 0; i < 15000000; i++) { random = myrand() % 50000000; arr_buf[random]++; } return arr_buf[0] ^ arr_buf[50000000 - 1]; }나머지 다른 소스들도 마지막의 return 을 동일하게 해서 비교해 봤는데..
without_mapper 의 rand 를 inline 시켜서 -O3 를 주고 빌드한게 with_mapper 에 비해 근소하게 이득을 보여주네요.
(wm_* -> with_mapper, wom_* -> without_mapper)
되면 한다! / feel no sorrow, feel no pain, feel no hurt, there's nothing gained.. only love will then remain.. 『 Ｍｉｚｚ 』
http://www.pixelbeat.org/prog
http://www.pixelbeat.org/programming/profiling/
위 사이트 참조해서 해 본 perf stat 데이터입니다. 바이너리는 모두 -O3 컴파일했습니다.
with_mapper / without_mapper / without_mapper_inline 순서로 봤을 때,
실행시간은 각각 0.415초 / 0.717초 / 0.371초로, inline rand를 쓴 코드가 가장 짧았는데
수치들을 좀 살펴볼 필요가 있는 것 같습니다.
$ perf stat --repeat 10 -e cycles:u -e instructions:u -e cache-references:u \ -e cache-misses:u -e stalled-cycles-frontend:u -e stalled-cycles-backend:u \ -e ref-cycles:u -e branch-instructions:u -e branch-misses:u ./with_mapper Performance counter stats for './with_mapper' (10 runs): 1,009,341,377 cycles:u ( +- 0.33% ) [54.13%] 1,010,293,714 instructions:u # 1.00 insns per cycle # 0.60 stalled cycles per insn ( +- 0.38% ) [66.54%] 18,696,250 cache-references:u ( +- 0.27% ) [66.96%] 15,270,571 cache-misses:u # 81.677 % of all cache refs ( +- 0.98% ) [56.91%] 610,438,568 stalled-cycles-frontend:u # 60.48% frontend cycles idle ( +- 0.60% ) [57.38%] 351,559,539 stalled-cycles-backend:u # 34.83% backend cycles idle ( +- 1.18% ) [57.00%] 1,014,845,040 ref-cycles:u ( +- 0.35% ) [67.68%] 256,720,772 branch-instructions:u ( +- 0.59% ) [55.15%] 19,306 branch-misses:u # 0.01% of all branches ( +- 1.36% ) [54.19%] 0.415446892 seconds time elapsed ( +- 0.33% ) $ perf stat --repeat 10 -e cycles:u -e instructions:u -e cache-references:u \ -e cache-misses:u -e stalled-cycles-frontend:u -e stalled-cycles-backend:u \ -e ref-cycles:u -e branch-instructions:u -e branch-misses:u ./without_mapper Performance counter stats for './without_mapper' (10 runs): 1,832,974,537 cycles:u ( +- 0.26% ) [55.35%] 935,441,846 instructions:u # 0.51 insns per cycle # 1.59 stalled cycles per insn ( +- 0.02% ) [66.53%] 18,088,004 cache-references:u ( +- 0.14% ) [66.52%] 14,311,287 cache-misses:u # 79.120 % of all cache refs ( +- 0.17% ) [55.79%] 1,485,845,774 stalled-cycles-frontend:u # 81.06% frontend cycles idle ( +- 0.60% ) [56.21%] 818,067,628 stalled-cycles-backend:u # 44.63% backend cycles idle ( +- 4.21% ) [56.08%] 1,830,705,887 ref-cycles:u ( +- 0.23% ) [67.31%] 242,321,864 branch-instructions:u ( +- 0.19% ) [55.88%] 82,702 branch-misses:u # 0.03% of all branches ( +- 1.59% ) [55.44%] 0.717499118 seconds time elapsed ( +- 0.24% ) $ perf stat --repeat 10 -e cycles:u -e instructions:u -e cache-references:u \ -e cache-misses:u -e stalled-cycles-frontend:u -e stalled-cycles-backend:u \ -e ref-cycles:u -e branch-instructions:u -e branch-misses:u ./without_mapper_inline Performance counter stats for './without_mapper_inline' (10 runs): 891,972,105 cycles:u ( +- 0.12% ) [55.82%] 392,815,782 instructions:u # 0.44 insns per cycle # 2.10 stalled cycles per insn ( +- 0.11% ) [67.23%] 18,030,489 cache-references:u ( +- 0.08% ) [67.56%] 14,348,891 cache-misses:u # 79.581 % of all cache refs ( +- 0.10% ) [56.82%] 826,690,163 stalled-cycles-frontend:u # 92.68% frontend cycles idle ( +- 0.25% ) [56.82%] 531,608,389 stalled-cycles-backend:u # 59.60% backend cycles idle ( +- 1.48% ) [56.24%] 915,501,055 ref-cycles:u ( +- 0.15% ) [67.04%] 48,201,080 branch-instructions:u ( +- 0.15% ) [54.27%] 233,098 branch-misses:u # 0.48% of all branches ( +- 0.49% ) [54.57%] 0.371133445 seconds time elapsed ( +- 0.13% )[1] with_mapper와 without_mapper 비교
실행해야 하는 명령의 갯수는 1,010,293,714개와 935,441,846개로 with_mapper 쪽이 8%정도 더 많고
캐시미스 비율도 81.677%와 79.120%로 with_mapper 쪽이 약간 큰 편이지만
실행에 걸린 시간은 with_mapper 쪽이 더 짧았습니다.
수치중에 눈에 띄는 점은 stalled-cycles인 것 같습니다.
stalled-cycles-frontend와 stalled-cycles-backend 퍼센티지가 with_mapper 쪽이 더 작습니다.
그 결과가, with_mapper에서 1.00 insns per cycle / 0.60 stalled cycles per insn 으로 나오고
without_mapper에서는 0.51 insns per cycle / 1.59 stalled cycles per insn 으로 나옵니다.
with_mapper는 한 사이클당 1.00개의 명령을 실행하는 효율이 나왔고,
without_mapper는 한 사이클당 0.51개의 명령을 실행하는 효율이 나왔다는 말 같습니다.
stalled-cycles는 idle-cycles라고도 부르는 것 같고, CPU 파이프라인이 진행되지 못하는 상태를 가리키는 모양입니다.
( http://stackoverflow.com/questions/22165299/what-are-stalled-cycles-frontend-and-stalled-cycles-backend-in-perf-stat-resul )
메모리로부터의 명령어/데이터 페치를 기다린다든지, 페치된 명령어가 복잡해서 미처 디코딩되지 못해서
그걸 기다린다든지 하면서 CPU 사이클을 흘려보내는 상황을 말하는 것 같습니다.
대표적인 경우로, 캐시미스가 나면 stall 상태가 길어지겠지만, 캐시미스 말고도 stall이 발생하는 상황은 더 있을 것입니다.
with_mapper는 without_mapper에 비해 더 많은 명령을 실행해야 하고 캐시미스도 더 많이 발생하면서도 실행시간은 더 빨랐으므로,
without_mapper는 캐시미스 말고 다른 원인에 의한 stall을 많이 겪었다는 말이 될 겁니다.
with_mapper에서 stall 발생이 줄어든 이유만 머리에 그릴 수 있으면 제 궁금증은 풀릴 것 같습니다.
아직은 안 풀리지만요.
[2] without_mapper_inline이 빠른 이유
이 코드가 빨리 동작한 것은 좀 다른 이유 같습니다.
무슨 이유인지 이 코드의 stall-cycles 비율이 매우 높아서
0.44 insns per cycle 로 세 샘플 가운데 가장 낮은 효율로 동작했는데도 실행시간은 더 짧았는데
그 이유는 실행해야 하는 명령의 갯수가 392,815,782 instructions로
위의 non-inline 샘플들의 40% 수준으로 줄어들었기 때문인 것 같습니다.
음 ..
with_mapper 의 효율이 1 insns per cycle 이상 나오는 걸로 봐서..
두 개의 loop 가 파이프라인에서 동시 처리되고 있는 건 아닐까 하는 생각도 듭니다. (추측)
어차피 두 loop 의 종속 변수는 arr_ran[i] 뿐이니, 두 번째 loop 가 첫 번째 loop 의 결과를 받아서 동시에 처리되어도 별 문제는 없어 보이고..
그렇다면 실제 수행 시간은 두 개의 loop 중, 가장 오래 시간이 걸리는 loop 정도 만큼만 되지 않을까 생각되네요.
그래서 loop 에 있는 rand 를 inline 시켜서 loop 내에서 걸리는 시간을 최대한 줄여 버리면..
오히려 두 개의 loop 를 동시 컨트롤 하는 쪽이 좀 더 부담이 되는 상황이 되는게 아닐까 싶습니다.
거기에 with_mapper 쪽에는 arr_ran[i] = random; + calloc() 하는 부분도 추가되어 있는 상태고 말이죠.
myrand 에서 쓸데 없는 if 문 없애고, with_mapper 와 without_mapper 에 inline 시켜서..
with_mapper 쪽에 추가된 코드 외에는 완전히 동일한 상태로 -O3 를 주고 빌드해서 비교해 보면..
약간의 instruction 과 branch-instruction 에서 차이를 보이는 것을 감안하면 큰 차이가 없어 보입니다.
제 서버에서는 stalled-cycles 가 안 나오네요.. O.o
static inline int myrand(void) { /* * Compute x = (7^5 * x) mod (2^31 - 1) * wihout overflowing 31 bits: * (2^31 - 1) = 127773 * (7^5) + 2836 * From "Random number generators: good ones are hard to find", * Park and Miller, Communications of the ACM, vol. 31, no. 10, * October 1988, p. 1195. */ unsigned long hi, lo, x; /* Can't be initialized with 0, so use another value. */ hi = next / 127773; lo = next % 127773; x = 16807 * lo - 2836 * hi; return ((next = x) % ((u_long) RAND_MAX + 1)); }$ sudo perf stat --repeat 10 -e cycles:u -e instructions:u -e cache-references:u -e cache-misses:u -e stalled-cycles-frontend:u \ -e stalled-cycles-backend:u -e ref-cycles:u -e branch-instructions:u -e branch-misses:u ./wm_inline_O3_more_opt.out Performance counter stats for './wm_inline_O3_more_opt.out' (10 runs): 606,035,620 cycles:u ( +- 1.55% ) [71.27%] 382,126,474 instructions:u # 0.63 insns per cycle ( +- 0.21% ) [85.71%] 18,835,984 cache-references:u ( +- 0.41% ) [85.71%] 13,540,466 cache-misses:u # 71.886 % of all cache refs ( +- 0.32% ) [71.81%] 0 stalled-cycles-frontend:u # 0.00% frontend cycles idle 0 stalled-cycles-backend:u # 0.00% backend cycles idle 544,799,854 ref-cycles:u ( +- 2.51% ) [86.02%] 33,062,894 branch-instructions:u ( +- 0.07% ) [86.14%] 81 branch-misses:u # 0.00% of all branches ( +- 19.29% ) [85.39%] 0.367230920 seconds time elapsed ( +- 2.57% ) $ sudo perf stat --repeat 10 -e cycles:u -e instructions:u -e cache-references:u -e cache-misses:u -e stalled-cycles-frontend:u \ -e stalled-cycles-backend:u -e ref-cycles:u -e branch-instructions:u -e branch-misses:u ./wom_inline_O3_more_opt.out Performance counter stats for './wom_inline_O3_more_opt.out' (10 runs): 570,731,104 cycles:u ( +- 2.67% ) [71.12%] 307,509,395 instructions:u # 0.54 insns per cycle ( +- 0.09% ) [85.57%] 17,639,758 cache-references:u ( +- 0.59% ) [85.78%] 12,520,675 cache-misses:u # 70.980 % of all cache refs ( +- 0.37% ) [71.71%] 0 stalled-cycles-frontend:u # 0.00% frontend cycles idle 0 stalled-cycles-backend:u # 0.00% backend cycles idle 515,833,420 ref-cycles:u ( +- 1.92% ) [85.91%] 18,117,146 branch-instructions:u ( +- 0.11% ) [86.25%] 403 branch-misses:u # 0.00% of all branches ( +- 85.13% ) [85.67%] 0.338563809 seconds time elapsed ( +- 1.87% )되면 한다! / feel no sorrow, feel no pain, feel no hurt, there's nothing gained.. only love will then remain.. 『 Ｍｉｚｚ 』
덕분에 새로운 툴도 알게 되고 평소 안 하던 공부도
덕분에 새로운 툴도 알게 되고 평소 안 하던 공부도 조금 하는 계기가 생기네요.
고맙습니다.
[1] 기존의 rand()를 쓰는 버전 변경
기존의 rand()를 쓰는 without_mapper.c를 좀 수정해서
for 루프의 한 사이클에서 복수개의 작업을 처리하도록 했습니다.
아래 코드는 4개짜리이고, 2개/4개/8개/16개 식으로 만들어서 해 봤습니다.
#include <stdio.h> #include <stdlib.h> #include <time.h> int main(int argc, char** argv) { int r1, r2, r3, r4; int *arr_buf; int i; time_t t; arr_buf = calloc(sizeof(int), 50000000); srand((unsigned) time(&t)); for(i = 0 ; i < 15000000; i+=4) { r1 = rand() % 50000000; r2 = rand() % 50000000; r3 = rand() % 50000000; r4 = rand() % 50000000; arr_buf[r1]++; arr_buf[r2]++; arr_buf[r3]++; arr_buf[r4]++; } return arr_buf[0] ^ arr_buf[50000000 - 1]; }2개를 한 번에 처리할 때는 오히려 성능저하가 왔는데 그 이유는 잘 모르겠습니다.
하지만 4개/8개/16개 식으로 늘려가면 점차 with_mapper의 성능에 근접해가는 경향이 보입니다.
stall_cycles 비율이 점차 낮아지고, insns per cycle 도 점차 높아져 갑니다.
캐시미스 빈도에 별 변화가 일어나지 않으면서도 실행시간이 크게 변하는 패턴이 느껴집니다.
아마도, rand()호출 직후에 arr_buf[...]++; 이 실행되면
rand() 실행중에 동작하던 CPU 파이프라인이 arr_buf[...]++; 처리하면서
그 연속성을 잃는(?) 식의 동작이 1500만번 반복되고 있었는데
이런 빈도를 낮춰주니 파이프라인의 동작효율이 올라갔다든지 하는 이유가 아닐까 끼워맞춰 봅니다.
(사실 이 부분을 잘 이해하고 싶은데 적으면서도 무슨 말인지 잘 분간이 되지는 않네요)
어쨌든 1500만번을 한 방에 모아서 새로운 for loop을 만드는 대신
8번이나 16번씩만 모아서 처리하는 정도만으로도 꽤 큰 변화가 나왔습니다.
힙에 메모리 60MB를 할당하지 않는 대신 약간의 속도 패널티를 감수하는 선택이 되겠네요.
$ perf stat --repeat 10 -e cycles:u -e instructions:u -e cache-references:u -e cache-misses:u -e stalled-cycles-frontend:u \ -e stalled-cycles-backend:u -e ref-cycles:u -e branch-instructions:u -e branch-misses:u ./without_mapper Performance counter stats for './without_mapper' (10 runs): 1,825,721,556 cycles:u ( +- 0.27% ) [55.19%] 935,473,944 instructions:u # 0.51 insns per cycle # 1.58 stalled cycles per insn ( +- 0.02% ) [66.41%] 18,072,653 cache-references:u ( +- 0.05% ) [66.41%] 14,303,511 cache-misses:u # 79.145 % of all cache refs ( +- 0.23% ) [55.88%] 1,478,126,689 stalled-cycles-frontend:u # 80.96% frontend cycles idle ( +- 0.60% ) [56.43%] 799,678,068 stalled-cycles-backend:u # 43.80% backend cycles idle ( +- 3.06% ) [56.32%] 1,827,287,712 ref-cycles:u ( +- 0.24% ) [67.44%] 242,952,894 branch-instructions:u ( +- 0.13% ) [55.72%] 81,489 branch-misses:u # 0.03% of all branches ( +- 1.07% ) [55.32%] 0.715057517 seconds time elapsed ( +- 0.26% ) $ perf stat --repeat 10 -e cycles:u -e instructions:u -e cache-references:u -e cache-misses:u -e stalled-cycles-frontend:u \ -e stalled-cycles-backend:u -e ref-cycles:u -e branch-instructions:u -e branch-misses:u ./without_mapper_2 Performance counter stats for './without_mapper_2' (10 runs): 1,949,759,335 cycles:u ( +- 0.07% ) [55.72%] 935,728,013 instructions:u # 0.48 insns per cycle # 1.70 stalled cycles per insn ( +- 0.02% ) [66.88%] 18,061,828 cache-references:u ( +- 0.03% ) [66.89%] 14,368,562 cache-misses:u # 79.552 % of all cache refs ( +- 0.03% ) [55.85%] 1,594,239,233 stalled-cycles-frontend:u # 81.77% frontend cycles idle ( +- 0.12% ) [55.84%] 819,889,874 stalled-cycles-backend:u # 42.05% backend cycles idle ( +- 3.96% ) [55.54%] 1,950,135,410 ref-cycles:u ( +- 0.22% ) [66.73%] 233,605,477 branch-instructions:u ( +- 0.16% ) [55.76%] 82,210 branch-misses:u # 0.04% of all branches ( +- 1.37% ) [55.65%] 0.761584206 seconds time elapsed ( +- 0.05% ) $ perf stat --repeat 10 -e cycles:u -e instructions:u -e cache-references:u -e cache-misses:u -e stalled-cycles-frontend:u \ -e stalled-cycles-backend:u -e ref-cycles:u -e branch-instructions:u -e branch-misses:u ./without_mapper_4 Performance counter stats for './without_mapper_4' (10 runs): 1,373,832,807 cycles:u ( +- 0.11% ) [55.79%] 927,985,963 instructions:u # 0.68 insns per cycle # 1.11 stalled cycles per insn ( +- 0.03% ) [67.00%] 18,075,798 cache-references:u ( +- 0.07% ) [67.02%] 14,353,558 cache-misses:u # 79.408 % of all cache refs ( +- 0.10% ) [56.03%] 1,027,458,036 stalled-cycles-frontend:u # 74.79% frontend cycles idle ( +- 0.29% ) [56.02%] 596,735,475 stalled-cycles-backend:u # 43.44% backend cycles idle ( +- 1.55% ) [55.51%] 1,382,613,152 ref-cycles:u ( +- 0.13% ) [66.50%] 229,977,176 branch-instructions:u ( +- 0.33% ) [55.60%] 91,040 branch-misses:u # 0.04% of all branches ( +- 1.81% ) [55.68%] 0.546357758 seconds time elapsed ( +- 0.10% ) $ perf stat --repeat 10 -e cycles:u -e instructions:u -e cache-references:u -e cache-misses:u -e stalled-cycles-frontend:u \ -e stalled-cycles-backend:u -e ref-cycles:u -e branch-instructions:u -e branch-misses:u ./without_mapper_8 Performance counter stats for './without_mapper_8' (10 runs): 1,081,261,209 cycles:u ( +- 0.10% ) [55.79%] 930,883,868 instructions:u # 0.86 insns per cycle # 0.77 stalled cycles per insn ( +- 0.05% ) [66.93%] 18,074,531 cache-references:u ( +- 0.06% ) [66.94%] 14,327,671 cache-misses:u # 79.270 % of all cache refs ( +- 0.12% ) [55.91%] 720,231,078 stalled-cycles-frontend:u # 66.61% frontend cycles idle ( +- 0.33% ) [55.91%] 380,316,630 stalled-cycles-backend:u # 35.17% backend cycles idle ( +- 2.54% ) [55.48%] 1,080,774,483 ref-cycles:u ( +- 0.45% ) [66.94%] 227,013,489 branch-instructions:u ( +- 0.28% ) [56.12%] 86,250 branch-misses:u # 0.04% of all branches ( +- 1.97% ) [55.76%] 0.436093327 seconds time elapsed ( +- 0.19% ) $ perf stat --repeat 10 -e cycles:u -e instructions:u -e cache-references:u -e cache-misses:u -e stalled-cycles-frontend:u \ -e stalled-cycles-backend:u -e ref-cycles:u -e branch-instructions:u -e branch-misses:u ./without_mapper_16 Performance counter stats for './without_mapper_16' (10 runs): 1,070,899,223 cycles:u ( +- 0.33% ) [55.31%] 936,217,366 instructions:u # 0.87 insns per cycle # 0.75 stalled cycles per insn ( +- 0.11% ) [66.58%] 18,075,646 cache-references:u ( +- 0.05% ) [66.65%] 14,336,845 cache-misses:u # 79.316 % of all cache refs ( +- 0.10% ) [55.67%] 697,665,709 stalled-cycles-frontend:u # 65.15% frontend cycles idle ( +- 1.16% ) [56.42%] 373,719,648 stalled-cycles-backend:u # 34.90% backend cycles idle ( +- 2.68% ) [56.95%] 1,072,645,482 ref-cycles:u ( +- 0.66% ) [67.78%] 228,912,035 branch-instructions:u ( +- 0.05% ) [55.73%] 58,469 branch-misses:u # 0.03% of all branches ( +- 2.03% ) [55.42%] 0.432491119 seconds time elapsed ( +- 0.50% ) $ perf stat --repeat 10 -e cycles:u -e instructions:u -e cache-references:u -e cache-misses:u -e stalled-cycles-frontend:u \ -e stalled-cycles-backend:u -e ref-cycles:u -e branch-instructions:u -e branch-misses:u ./with_mapper Performance counter stats for './with_mapper' (10 runs): 1,004,047,400 cycles:u ( +- 0.11% ) [54.06%] 1,009,905,210 instructions:u # 1.01 insns per cycle # 0.61 stalled cycles per insn ( +- 0.38% ) [66.82%] 18,723,027 cache-references:u ( +- 0.27% ) [67.52%] 15,532,368 cache-misses:u # 82.959 % of all cache refs ( +- 0.37% ) [57.11%] 613,255,791 stalled-cycles-frontend:u # 61.08% frontend cycles idle ( +- 0.39% ) [57.36%] 352,630,774 stalled-cycles-backend:u # 35.12% backend cycles idle ( +- 0.76% ) [56.80%] 1,010,029,873 ref-cycles:u ( +- 0.14% ) [67.46%] 259,216,495 branch-instructions:u ( +- 0.17% ) [54.87%] 21,538 branch-misses:u # 0.01% of all branches ( +- 2.34% ) [53.90%] 0.413563407 seconds time elapsed ( +- 0.13% )[2] inline rand 쓰는 버전
올려주신 대로, inline rand를 with_mapper와 without_mapper 모두에 사용하고 비교해보면
둘 사이의 차이가 거의 사라지네요. stalled-cycles 비율도 모두 높게 나오고요.
$ perf stat --repeat 10 -e cycles:u -e instructions:u -e cache-references:u -e cache-misses:u -e stalled-cycles-frontend:u \ -e stalled-cycles-backend:u -e ref-cycles:u -e branch-instructions:u -e branch-misses:u ./without_mapper_inline Performance counter stats for './without_mapper_inline' (10 runs): 893,623,726 cycles:u ( +- 0.18% ) [55.81%] 393,678,644 instructions:u # 0.44 insns per cycle # 2.10 stalled cycles per insn ( +- 0.19% ) [67.22%] 18,041,045 cache-references:u ( +- 0.05% ) [67.51%] 14,358,471 cache-misses:u # 79.588 % of all cache refs ( +- 0.11% ) [56.75%] 827,340,969 stalled-cycles-frontend:u # 92.58% frontend cycles idle ( +- 0.28% ) [56.76%] 522,380,655 stalled-cycles-backend:u # 58.46% backend cycles idle ( +- 1.69% ) [56.20%] 914,053,314 ref-cycles:u ( +- 0.16% ) [67.00%] 48,055,032 branch-instructions:u ( +- 0.15% ) [54.45%] 231,622 branch-misses:u # 0.48% of all branches ( +- 0.50% ) [55.12%] 0.370563294 seconds time elapsed ( +- 0.15% ) $ perf stat --repeat 10 -e cycles:u -e instructions:u -e cache-references:u -e cache-misses:u -e stalled-cycles-frontend:u \ -e stalled-cycles-backend:u -e ref-cycles:u -e branch-instructions:u -e branch-misses:u ./with_mapper_inline Performance counter stats for './with_mapper_inline' (10 runs): 877,123,249 cycles:u ( +- 0.16% ) [55.91%] 459,367,498 instructions:u # 0.52 insns per cycle # 1.75 stalled cycles per insn ( +- 0.05% ) [67.26%] 19,425,139 cache-references:u ( +- 0.10% ) [67.33%] 15,689,671 cache-misses:u # 80.770 % of all cache refs ( +- 0.23% ) [56.44%] 803,009,992 stalled-cycles-frontend:u # 91.55% frontend cycles idle ( +- 0.29% ) [56.44%] 409,585,810 stalled-cycles-backend:u # 46.70% backend cycles idle ( +- 0.75% ) [55.68%] 887,674,187 ref-cycles:u ( +- 0.19% ) [66.57%] 64,749,082 branch-instructions:u ( +- 0.73% ) [54.99%] 225,872 branch-misses:u # 0.35% of all branches ( +- 0.98% ) [55.56%] 0.367955193 seconds time elapsed ( +- 0.19% )아래와 같이 1500만개의 랜덤넘버만 만들고 종료하도록 만들어서 비교해 봤습니다.
rand()호출 버전과 inline rand 호출버전을 만들어 각각 rand_orig.c와 rand_inline.c라고 했습니다.
#include <stdio.h> #include <stdlib.h> #include <time.h> int main(int argc, char** argv) { int random; int *arr_ran; int i; time_t t; arr_ran = calloc(sizeof(int), 15000000); srand((unsigned) time(&t)); for(i = 0; i < 15000000; i++) { random = rand() % 50000000; arr_ran[i] = random; } return arr_ran[0] ^ arr_ran[15000000 - 1]; }CRT의 rand()는 1.92 insns per cycle 로 동작하고
인라인 버전은 1.06 insns per cycle 로 동작했습니다 (stalled-cycles-frontend가 높게 나오네요)
CRT의 rand()는 자체의 stalled-cycles 비율이 낮아서 단속적 동작시보다 연속동작시 효율이 좋고
인라인 버전은 자체의 stalled-cycles 비율이 높은 상태라서 단속적/연속적 동작에 따른
차이가 부각되지 않는 것이 아닌가 싶습니다.
다만, CRT의 rand()보다 인라인 버전이 더 가볍게 구현되어 있어서,
1500만번 동작시 0.189초 - 0.142초 == 0.057초의 이득이 있고
이 차이가 inline 버전 적용시 반영되고 있는 것 같습니다.
$ perf stat --repeat 10 -e cycles:u -e instructions:u -e cache-references:u -e cache-misses:u -e stalled-cycles-frontend:u \ -e stalled-cycles-backend:u -e ref-cycles:u -e branch-instructions:u -e branch-misses:u ./rand_orig Performance counter stats for './rand_orig' (10 runs): 480,047,206 cycles:u ( +- 0.65% ) [55.63%] 923,966,244 instructions:u # 1.92 insns per cycle # 0.09 stalled cycles per insn ( +- 0.67% ) [67.67%] 1,103,477 cache-references:u ( +- 5.10% ) [68.08%] 40,533 cache-misses:u # 3.673 % of all cache refs ( +- 3.21% ) [57.51%] 80,052,747 stalled-cycles-frontend:u # 16.68% frontend cycles idle ( +- 4.24% ) [57.57%] 42,084,682 stalled-cycles-backend:u # 8.77% backend cycles idle ( +- 6.47% ) [56.65%] 473,706,509 ref-cycles:u ( +- 0.88% ) [67.25%] 245,546,964 branch-instructions:u ( +- 0.52% ) [54.48%] 1,697 branch-misses:u # 0.00% of all branches ( +- 9.82% ) [55.47%] 0.189132362 seconds time elapsed ( +- 0.65% ) $ perf stat --repeat 10 -e cycles:u -e instructions:u -e cache-references:u -e cache-misses:u -e stalled-cycles-frontend:u \ -e stalled-cycles-backend:u -e ref-cycles:u -e branch-instructions:u -e branch-misses:u ./rand_inline Performance counter stats for './rand_inline' (10 runs): 368,634,885 cycles:u ( +- 0.27% ) [54.92%] 389,587,457 instructions:u # 1.06 insns per cycle # 0.67 stalled cycles per insn ( +- 0.27% ) [66.19%] 1,146,982 cache-references:u ( +- 4.10% ) [66.18%] 34,301 cache-misses:u # 2.991 % of all cache refs ( +- 1.45% ) [54.88%] 262,137,999 stalled-cycles-frontend:u # 71.11% frontend cycles idle ( +- 0.90% ) [55.50%] 92,545,908 stalled-cycles-backend:u # 25.11% backend cycles idle ( +- 3.62% ) [58.37%] 331,094,640 ref-cycles:u ( +- 0.49% ) [71.72%] 46,788,130 branch-instructions:u ( +- 0.54% ) [58.05%] 229,719 branch-misses:u # 0.49% of all branches ( +- 0.37% ) [56.27%] 0.142456257 seconds time elapsed ( +- 0.42% )아래와 같이 prefetch를 활용해보니 꽤
아래와 같이 prefetch를 활용해보니 꽤 빨라집니다.
2개/4개/8개/16개/32개까지 단계적으로 성능 향상이 이뤄졌습니다.
stalled-cycles 비율도 매우 낮아지고, insns per cycle도 1.48 정도까지 올라갑니다.
처음엔 공연히 할 줄도 모르는 인라인 어셈블리 삽질을 했는데
그냥 gcc의 _mm_prefetch() intrinsic을 쓰면 간단히 되네요.
prefetch 힌트로는 _MM_HINT_NTA말고 다른 걸 줘도 별 차이 없는 것 같은데 다 해보지는 않았습니다.
without_mapper 코드를 수정했고, 빌드는 -O3로 했습니다.
#include <stdio.h> #include <stdlib.h> #include <time.h> #include <xmmintrin.h> int main(int argc, char** argv) { int r1, r2, r3, r4; int *arr_buf; int i; time_t t; arr_buf = calloc(sizeof(int), 50000000); srand((unsigned) time(&t)); for(i = 0 ; i < 15000000; i+=4) { r1 = rand() % 50000000; _mm_prefetch(&arr_buf[r1], _MM_HINT_NTA); r2 = rand() % 50000000; _mm_prefetch(&arr_buf[r2], _MM_HINT_NTA); r3 = rand() % 50000000; _mm_prefetch(&arr_buf[r3], _MM_HINT_NTA); r4 = rand() % 50000000; _mm_prefetch(&arr_buf[r4], _MM_HINT_NTA); arr_buf[r1]++; arr_buf[r2]++; arr_buf[r3]++; arr_buf[r4]++; } return arr_buf[0] ^ arr_buf[50000000 - 1]; }$ for f in without_mapper_prefetch_*.c; do perf stat --repeat 10 -e cycles:u -e instructions:u \ -e cache-references:u -e cache-misses:u -e stalled-cycles-frontend:u -e stalled-cycles-backend:u \ -e ref-cycles:u -e branch-instructions:u -e branch-misses:u ./${f/.c/}; done Performance counter stats for './without_mapper_prefetch_16' (10 runs): 726,541,992 cycles:u ( +- 0.44% ) [54.10%] 933,747,786 instructions:u # 1.29 insns per cycle # 0.36 stalled cycles per insn ( +- 0.30% ) [66.93%] 17,792,041 cache-references:u ( +- 0.23% ) [67.87%] 14,309,179 cache-misses:u # 80.425 % of all cache refs ( +- 0.43% ) [57.68%] 338,537,993 stalled-cycles-frontend:u # 46.60% frontend cycles idle ( +- 0.78% ) [57.91%] 195,352,393 stalled-cycles-backend:u # 26.89% backend cycles idle ( +- 3.14% ) [57.06%] 741,780,626 ref-cycles:u ( +- 0.36% ) [67.56%] 229,569,735 branch-instructions:u ( +- 0.30% ) [54.44%] 85,869 branch-misses:u # 0.04% of all branches ( +- 1.14% ) [53.27%] 0.305120851 seconds time elapsed ( +- 0.32% ) Performance counter stats for './without_mapper_prefetch_2' (10 runs): 1,735,629,152 cycles:u ( +- 0.08% ) [55.34%] 950,181,255 instructions:u # 0.55 insns per cycle # 1.44 stalled cycles per insn ( +- 0.03% ) [66.50%] 18,065,196 cache-references:u ( +- 0.06% ) [66.50%] 14,357,221 cache-misses:u # 79.474 % of all cache refs ( +- 0.07% ) [55.33%] 1,364,984,396 stalled-cycles-frontend:u # 78.64% frontend cycles idle ( +- 0.19% ) [55.71%] 741,373,997 stalled-cycles-backend:u # 42.72% backend cycles idle ( +- 4.35% ) [56.48%] 1,728,683,303 ref-cycles:u ( +- 0.07% ) [67.62%] 235,655,153 branch-instructions:u ( +- 0.08% ) [56.02%] 112,175 branch-misses:u # 0.05% of all branches ( +- 1.63% ) [55.57%] 0.681133384 seconds time elapsed ( +- 0.11% ) Performance counter stats for './without_mapper_prefetch_32' (10 runs): 633,353,864 cycles:u ( +- 0.60% ) [53.84%] 934,344,151 instructions:u # 1.48 insns per cycle # 0.26 stalled cycles per insn ( +- 0.42% ) [66.67%] 17,677,551 cache-references:u ( +- 0.24% ) [68.02%] 14,257,453 cache-misses:u # 80.653 % of all cache refs ( +- 0.52% ) [57.97%] 242,246,260 stalled-cycles-frontend:u # 38.25% frontend cycles idle ( +- 1.53% ) [58.36%] 136,105,473 stalled-cycles-backend:u # 21.49% backend cycles idle ( +- 2.64% ) [57.45%] 648,066,038 ref-cycles:u ( +- 0.33% ) [67.83%] 228,958,158 branch-instructions:u ( +- 0.38% ) [54.48%] 75,998 branch-misses:u # 0.03% of all branches ( +- 1.10% ) [53.19%] 0.270096171 seconds time elapsed ( +- 0.34% ) Performance counter stats for './without_mapper_prefetch_4' (10 runs): 1,244,297,895 cycles:u ( +- 0.06% ) [54.93%] 941,506,944 instructions:u # 0.76 insns per cycle # 0.91 stalled cycles per insn ( +- 0.05% ) [66.20%] 18,070,571 cache-references:u ( +- 0.16% ) [66.20%] 14,244,420 cache-misses:u # 78.827 % of all cache refs ( +- 0.28% ) [55.91%] 857,720,914 stalled-cycles-frontend:u # 68.93% frontend cycles idle ( +- 0.22% ) [57.04%] 465,451,830 stalled-cycles-backend:u # 37.41% backend cycles idle ( +- 4.17% ) [56.98%] 1,249,892,180 ref-cycles:u ( +- 0.09% ) [67.81%] 232,498,836 branch-instructions:u ( +- 0.16% ) [55.84%] 108,098 branch-misses:u # 0.05% of all branches ( +- 0.90% ) [55.06%] 0.497561365 seconds time elapsed ( +- 0.16% ) Performance counter stats for './without_mapper_prefetch_8' (10 runs): 893,874,637 cycles:u ( +- 0.11% ) [55.69%] 949,267,656 instructions:u # 1.06 insns per cycle # 0.55 stalled cycles per insn ( +- 0.07% ) [67.08%] 18,603,191 cache-references:u ( +- 0.17% ) [67.17%] 14,906,123 cache-misses:u # 80.127 % of all cache refs ( +- 0.20% ) [56.37%] 520,774,599 stalled-cycles-frontend:u # 58.26% frontend cycles idle ( +- 0.31% ) [56.37%] 287,098,246 stalled-cycles-backend:u # 32.12% backend cycles idle ( +- 3.46% ) [55.95%] 906,059,725 ref-cycles:u ( +- 0.17% ) [66.85%] 227,831,537 branch-instructions:u ( +- 0.37% ) [55.31%] 98,301 branch-misses:u # 0.04% of all branches ( +- 1.11% ) [55.88%] 0.367310223 seconds time elapsed ( +- 0.14% )우연히 들어왔다 많이 배우네요.
우연히 들어왔다 많이 배우네요.
우선 짚고 넘어가야 할
우선 짚고 넘어가야 할 것은,
map[random_index(i)]++; 나 map[temp[i]]++; 둘다 캐쉬 지역성을 깨뜨리는 데는 동일합니다. 어차피 map에 인덱스되는 값이 랜덤이기 때문이죠.
위에서 테스트하신 결과들을 살펴봐도 모두 캐쉬 미스 비율이 대동소이한 것을 보면 알 수 있습니다.
map[temp[i]]++;의 경우 이 시점에 이미 temp는 결정된 값이기 때문에 CPU가 내부적으로 인스트럭션을 최적화하는 데 유리합니다.
하지만 temp 용량만큼 메모리를 더 잡아야 한다는 단점이 있습니다.
살짝 개선해서 아래와 같은 코드를 생각해 보았습니다. 개념 확인 정도로만 봐아주십시오.
static int myrand(void) { static int count = 0; static int buffer[100]; if (count > 0) { return buffer[--count]; } while (count < sizeof(buffer)/sizeof(buffer[0])) { buffer[count++] = rand(); } return rand(); }테스트해 보니까 map[myrand()]++; 식으로 쓸 경우에도 map[temp[i]]++; 과 유사한 결과가 나왔습니다.
buffer 사이즈를 10과 100으로 테스트했는데, 10에서는 조금 느렸고 100으로 바꾸니까 비슷하게 나오더군요.
댓글 달기