쓰레드 비용과 테이블 스캔 비용
2018/08/30
간단한 실험을 했다. 간단한 실험이라 실제 어떤 식으로 오차가 전개될지는 모른다.
궁금한 점은 이렇다. 테이블 n칸이 있다. 각 칸에는 검색키가 들어있고, 대형 파일을 검색할 예정이다. 별다른 알고리즘을 쓰지 않는다고 가정하면 파일을 1바이트씩 전진하며 테이블 n을 루핑하며 키를 검색한다. 아호코라식이니 KMP등등은 일단 제껴놓자.
이때 테이블 n칸을 루핑하는 비용이 크다고 할 수 있다.
이제 이것을 n개의 쓰레드로 나누자. 그런데 CPU는 코어가 4개다. 하이퍼쓰레드로는 8개다. 일단 4개로 나눠서 작업하면 빨라질 것이다. 테이블 스캔 비용이 n에서 n/4가 된다. 쓰레드 전환 비용이 있긴 하지만 아직까지는 물리 코어를 다 쓸 수 있다.
이제 쓰레드를 8개로 나누자. 이제 하이퍼쓰레드로서 8코어를 쓴다. 어쨌든 인텔도 머리써서 만든 아키텍쳐이므로 빨라진다. 테이블 스캔 비용은 n/8이 되었다.
이제 쓰레드를 16개로 나누자. 8 쓰레드에서 물리코어를 완전히 다 썼으므로 쓰레드 끼리도 본격 코어 경쟁에 들어간다. 쓰레드 스위칭 비용이 테이블 스캔 비용을 넘어설 것인가? 이제 고민을 해야 할 때다.
실험 결과는 이렇다. 4코어 (하이퍼 8코어) 머신이다.
- 4 쓰레드 : 1분 47초
- 8 쓰레드 : 1분 21초
- 16 쓰레드 : 1분 13초
8쓰레드에서 16쓰레드로 넘어오면서 물리 코어에 대한 쓰레드간 점유 경쟁이 일어나고 스위칭 비용 증가가 테이블 스캔 비용 감소분 보다 크지 않을까 했는데 소폭이긴 하지만 일단 빨라지긴 했다. IO 비용이 큰 놈들이야 쓰레드가 많아도 괜찮다. CPU가 놀 수 있는 구멍이 사방에 있다. 아파치 띄우면서 백쓰레드 천쓰레드 띄워도 괜찮다. 그래야 예쁘다. 그런데 이 실험(SSD 상에서) 처럼 IO 비용이 작은 애들은 컴퓨터를 거의 풀로 쓴다. 이렇게 빡빡하게 쓰는 와중에 쓰레드 스위칭이 일어나도 테이블 스캔 많이 하는 것 보다 비용이 작을 수 있다는 것이다. 게다가 이 실험은 테이블의 키가 겨우 16개 짜리다. 큰 테이블이라면 격차는 더 커질 수도 있것따. 테이블 루핑 스캔이라는 것이 좀 그렇다. 무식한 루프다. 요즘 컴파일러 좋고 씨퓨들 예측 분기 잘한다고 해도 그게 들어맞는 케이스에서 그런거지 파이프 다 깨먹고 뭐 그런것 같다. 루프만 풀어줘도 시간이 단축되는 걸 보면 대충 맞는 추정인 것 같다. 매번 하는 말인데 용처가 한정적이라면 트리 등을 이용한 것보다는 벡터를 선호한다. O(n)이 확 늘어나도 캐시와 빠이프의 화력이 있으니.. 결정적으로 코드가 쉬워요 핳핳하하...
문제는 있다. 기계를 풀로 땡겨쓰니 이 일 말고는 다른 일을 할 수가 없다... 사천만 땡겨줘요..~
뭐.. 그렇다는 거시다.. 리눅스 한정. 끗..