C를 좀더 빠르게 짜기위한 기법이다.
주로 사용할일은 없지만, 알고리즘풀이 사이트에서 극한의 속도를 내기위한
기법들을 소개한다.
1.cache 적중률을 극대화 하라.
cache 메모리는 CPU가 주메모리와의 속도차이에 의한 병목현상을 완화하기 위해
사용된다.
속도는 빠르지만, 용량은 작다. 캐시 메모리는 보통 하나만 있지 않고
요즘은 거의 두개의 캐시를 달고있다.
CPU -> L1 cahce -> L2 cache -> main memory
의 순으로 접근하며, 당연 CPU에 가까울수록 접근 속도가 빠르다.
L 은 레벨을 뜻하며, L1 캐시에서 데이터를 찾지못하면 L2 로 넘어가고 그래도 없으면
주메모리에서 데이터를 찾는다.
L1 캐시메모리는 8~64Kb 정도의 크기를 갖고 L2 캐시메모리는 64Kb~4Mb의 크기를
가진다.
당연 프로그래밍을 할때 캐시적중률이 높으면 그만큼 속도가 빠르며, 그이상도
그 이하도 아니다. 다만 빠를 뿐이다.
여기서 짚고 넘어가야 할점이 사실 가장 빠른건 CPU 안에 있는 register 이다.
C언어 에서도 레지스터를 사용할수 있게 register 키워드가 있는데,
register int i; 와 같이 선언하면 , 빈 레지스터가 있으면 변수 i 를 레지스터에 만들어라.
라는 뜻인데, 절대 사용하면 안된다.
참고로 volatile 변수와 전역변수는 register 에 만들어질수 없다.
왜냐하면, 정말 변수 i 를 레지스터로 놓는게 전체 프로세스 입장에서 봤을때 최적화인지
우리는 모른다. 너보다 컴파일러가 훨씬더 똑똑하다.
즉, 이는 컴파일러최적화를 방해하는 요인이되며, 최적화시 속도 저하의 요인이 된다.
cache 메모리는 다음에 사용될꺼 같은 메모리를 가져와서 저장한다.
배열을 사용하게 되면, 실제로 메모리가 인접해있기때문에 cache 적중률이 증가한다.
반면에 list 같은 자료구조는 그렇지 못하다.
연관이 없는 변수들이라도 자료형이 같다면 배열로 묶는것도 cache 적중률 향상에 영향을
미친다.
2.pipe line 재구성 방지
파이프라인은 컴퓨터구조론 수업을 들었으면 다 아는 내용이다.
분기 명령을 보고 미리 명령어 연산을 해놓는 놈이다.
다음 예를 보자
p=(int*)malloc(4);
if(p==NULL){
abort();
}
else{
//do something...
}malloc 함수는 할당에 실패할경우 NULL 을 반환한다.
그러나 과연 malloc 함수가 할당에 실패할경우가 몇이나 될까?
아마 1%도 안될것이다. 그러나 저렇게 코드를 짜면, 컴퓨터는 if 문안에 abort() 함수를
파이프라인에 집어넣는다. 즉 할당에 성공할때마다 파이프라인이 재구성된다는 뜻이다.
이는 속도저하를 뜻하며, 위의 코드는 다음과 같이 고치는것이 이득이다.
p=(int*)malloc(4);
if(p!=NULL){
//do something...
}
else{
abort();
}리눅스 C에서는 __builtin_except 라는 키워드가 있으며
</include/linux/compiler.h> 에 사용하기 쉽게 likely , unlikely 키워드가 있다.
