Optimizations (상수 커팅)

1. 로그 자료구조의 속도 비교

BIT (Fenwick Tree) < PQ < Set / Map (STL BBST) < Segment Tree < Lazy Segment Tree < Persistent Segment Tree

단, Set/Map은 삽입되는 자료의 양이 커질 때 급격히 느려진다.

 

2. Locality

다차원 배열의 인덱싱 순서는 반복문 순회 순서와 같게 하는 것이 제일 빠르다.

 

실제로 실행 시간의 대부분을 차지하는 것은 덧셈, 곱셈 등의 연산이 아니라, 메모리에 접근하고 값을 저장하는 연산이다. 메모리 접근 연산을 할 때에는 최대한 접근하는 위치들이 서로 인접해 있는 것이 좋다.

stackoverflow.com/questions/16699247/what-is-a-cache-friendly-code

 

다차원 배열 A[x][y][z]는 실제로 일차원 상으로 펴져서 구현되며, (x, y, z)의 lexicographical 순서에 따라 칸이 배정된다. 따라서 x, y, z의 순서대로 반복문을 순회하면 일차원 배열 상에서 거의 항상 인접한 칸으로만 이동하기 때문에 가장 효율적이다.

 

예시로는, LCA나 RMQ등에 사용되는 Sparse Table 구성이 있다.

Sparse Table을 구성하는 과정에서 다음과 같은 반복문을 수행한다.

for(int i=1; i<=20; i++) for(int j=1; j<=N; j++) SP[j][i]=SP[SP[j][i-1]][i-1];
for(int i=1; i<=20; i++) for(int j=1; j<=N; j++) SP[i][j]=SP[i-1][SP[i-1][j]];

첫번째 반복문의 경우, 반복문의 수행 순서와 인덱싱 순서가 일치하지 않아 캐시 미스가 많이 발생한다. 하지만, 두번째 반복문의 경우 반복문의 수행 순서와 인덱싱 순서가 일치하고, 그 뿐만 아니라 SP[i-1][SP[j][i-1]] 또한 SP[i][j]와 최대 2N칸의 차이가 발생하여 효율적인 코드이다.

즉, 스파스 테이블의 경우 SP[LOGN][MAXN]이 가장 바람직하다.

 

3. Pragma

#pragma GCC optimize ("O3")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("avx,avx2,fma")

 

4. Register

접근 속도가 매우 빠르지만 그 개수가 제한되어 있는 Register 변수를 이용하여, 시간을 단축시킨다.

보통, 접근이 매우 많이 필요한 for문 안의 변수들에 이용한다.

 

5. Inline

함수를 함수에 접근하는 메모리와 비용을 절약하기 위하여 코드에 풀어 쓰도록 만들어 준다. 이는 특히 스택 메모리 제한이 위험할 때나 재귀함수의 성능을 향상시킬 때 사용한다.