cpp module 09.
Ford-Johnson 정렬 알고리즘 다 짜서
시간 측정 시작….
어… 이상함.
컨테이너가 vector나 deque일 때 두 경우를 테스트 했는데,
deque가 이상하게 느림. 속도가 똑같아야 맞음.
일단 캐시 때문이라고 판단.
둘이 테스트하는 순서를 바꿔봄.
ok. 테스트 순서를 바꾸니 vector가 deque보다 느려짐.
앞에 오는 순서의 컨테이너가 무조건 느림.
작은 사이즈에서 더 이러한 경향이 큰 것을 확인. 이러면 확실함
원인이 캐시라고 확정.
먼저 캐시를 의도적으로 flush하기 위해
1024 * 1024 * 128 사이즈를 할당하고 해당 배열에 0을 채우는 작업을
각각의 sort 사이에 끼워넣음.
(쓰기 작업을 위해 배열을 캐시로 가져와야해서 기존 캐시 내용을 축출할거임)
→ 해결 안됨.
→ Cache prefetcher가 0을 채우는 작업을 보고
단순한 일회성 작업임을 예측해 기존 캐시라인을 flush하지 않는 판단을 했을거라 판단됨. (어셈에서 prefetch 하는 코드는 없었음)
음…
vector랑 deque랑 각자 다른 메모리를 써서 겹칠 일은 없는데….
argv를 같이 써서 그런가.
x86 sse2 에는 캐시 관련 기능이 있어서 캐시를 flush하는 명령어가 따로 있음.
clang에서 해당하는 인트린직인 __builtin___clear_cache() 을 사용해서 argv를 flush.
→ 해결 안됨.
음… Instruction Cache일 가능성?
template 함수라 그러진 않음.
아니… 그럴 수도 있음… vector랑 deque가 동일한 deque구현을 사용하면 그럴 수 있음.
아니면 heap 메모리 쪽이 caching되는거일 수도 있음,.
→ 그래서 delete 빼봤는데 똑같음. heap 쪽이 caching 되는건 아님
아.. 귀찮아짐..
원인 특정이 안되니 프로파일러를 사용해야함.
Cache까지 다 트래킹 되는걸 써야됨.
vs는 없고..
Intel VTune → 아… MAC에서 지원 안 해줌
qcachegrind → brew로 깔아봤는데 안 깔림…
Intel
Performance Counter Monitor → 아 클러스터 맥에서 초기화가 안돼서 실행을 못함
아오
집 윈도우 컴 키고 나올 걸
Performance Counter Monitor → 아 클러스터 맥에서 초기화가 안돼서 실행을 못함
아오
집 윈도우 컴 키고 나올 걸
밥먹고 다시 생각 시작…
__builtin_cache_clear()
이거 매개변수부터 하.. 이상해서 아마 clang이 제대로 안 넣어줬을 거 같음.
어셈 깜.
역시나 clang이 clflush 어셈 안 넣어줌.
__builtin_ia32_clflush로 변경.
→ 약간 나아짐.
ok. argc랑 argv flush 시키니까 조금 나아짐.
근데 clflush로 모든 캐시를 비울 순 없음.
왜냐면 정확한 주소를 알아야 되는데 어디가 캐싱되는지 알 수 없는 상태고
모든 주소에 대해 clflush 하자니 그건 좀 애매…
그리고 i-cache를 flush 하는 건 좀 위험함.
그래서 아까 시도한 큰 배열을 0으로 채워서 cache를 비우는 걸 다시 할건데
cache prefetcher가 0을 일정하게 채우면 step 패턴이 똑같아서 무조건 예측할 것이므로
random하게 접근해서 predictor를 회피한다.
→ 많이 나아짐.
random 접근이라 배열에 0을 안 적는 부분이 있는듯
iteration 횟수를 4~8배 더 늘리자.
→ 해결됨. 이제 속도 똑같음
근데 캐시 비우는 속도가 너무 느려서 문제.
어차피 캐시라인 중 하나만 건드려도 해당 캐시라인을 fetch 해야하니
캐시라인 경계에만 0을 적도록 바꿈
→ 이제 테스트도 빠름
// Flush the cache
__builtin_ia32_mfence();
{
for (int i = 0; i < argc; i++)
for (size_t j = 0; j < std::strlen(argv[i]); j += CACHE_LINE)
__builtin_ia32_clflush((char*)&argv[i][j]);
for (int i = 0; i < argc; i += CACHE_LINE / sizeof(char*))
__builtin_ia32_clflush((char*)&argv[i]);
enum { N = 1024 * 1024 * 64 };
volatile char* arr = new char[N];
for (int i = 0; i < N; i++)
arr[std::rand() % (N / CACHE_LINE) * CACHE_LINE] = 0;
delete[] arr;
}
C++
복사
