Bentley Rules for Optimizing Work

[MIT OpenCourseWare] Bently Rules for Optimizing Work

 

https://youtu.be/H-1-X9bkop8?si=XwVJWkN_mL2Pk0LG

 

 

Work

Definition.

The work of a program (on a give input) is the sum total of all the operations executed by the program.

프로그램의 work라는 것은 어떠한 입력이 주어졌을 때, 실행되는 모든 연산의 합.

 

Optimizing Work

알고리즘 설계는 문제 해결에 필요한 작업량을 드라마틱하게 줄일 수 있는데, 정렬 알고리즘의 O(n^2)와 O(n lg n)의 차이가 대표적인 예시이다.

 

하지만, 아래와 같은 컴퓨터 하드웨어의 복잡한 특성때문에 프로그램의 작업량을 줄인다고 해서 실행 시간이 자동으로 단축되는 것은 아님.

- instruction-level parallelism (ILP)

- caching

- vectorization

- speculation and branch prediction

 

그럼에도 불구하고, 작업량을 줄이는 것은 전체 실행 시간을 줄이는데 유용한 휴리스틱으로 활용 가능.

 

New "Bentley" Rules

1982년에 Charles Leiserson의 지도 교수이기도 했던 Bentley가 쓴 'Writing efficient programs'라는 책이 있었음.

이를 현대 하드웨어에 맞게 재구성한 것이 이번 강의의 요지.

22개의 최적화를 다룬 New Bentley Rules.

 

Data structures

- 1) Packing and encoding

- 2) Augmentation

- 3) Precomputation

- 4) Compile-time intialization

- 5) Caching

- 6) Lazy evaluation

- 7) Sparsity

 

Loops

- 8) Hoisting

- 9) Sentinels

- 10) Loop unrolling

- 11) Loop fusion

- 12) Eliminating wasted iterations

 

Logic

- 13) Constant folding and propagation

- 14) Common-subexpression elimination

- 15) Algebraic identities

- 16) Short-circuiting

- 17) Ordering tests

- 18) Creating a fast path

- 19) Combining tests

 

Functions

- 20) Inlining

- 21) Tail-recursion elimination

- 22) Coarsening recursion

 

[ Data Structures ]

1) Packing and Encoding

packing : 하나의 word 안에 1개의 데이터 초과하여 저장.

encoding : 더 적은 비트를 사용하도록 데이터 값을 변환.

 

→ 비트 압축을 의미 하는듯.

example : bit fields in C

각각의 값이 가질 수 있는 최댓값에 대한 lg를 취한뒤 올림해서, 필요한 비트를 계산 가능.

ex) month는 최대 12이므로, lg (rounded up of 12) → 2^4

 

*값을 encoding하고 나서 다시 unpacking/decoding 자체로도 작업량이 클 수 있으므로, 실제로 이득이 되는지는 직접 확인해봐야 함.

 

2) Augmentation

ex) single linked list에서, 가장 마지막 node에 대한 접근은 항상 리스트의 길이만큼의 비용이 든다.

→ 마지막 node에 대한 포인터를 tail에 추가 저장하여 상수 시간안에 접근 가능(double linked list)

이러한 방식이 바로 Augmentation에 대한 기본 아이디어에 해당.

3) Precomputation

Binomial Coefficients (이항 계수)

계산 공식은 위와 같은데, 이를 런타임에 계산하기에는 매우 비싼 연산이다. (가장 비싼 팩토리얼 연산이기 때문)

또한 overflow가 발생할 수도 있음.

 

Idea : 한 번만 계산해두면 변하지 않는 값이므로, 프로그램을 초기화할 때 사전에 계산(precompute)해두고, 런타임에는 기록된 테이블을 조회(lookup).

→ 이항 계수에 대한 Table은 그 유명한 Pascal's Triangle

ex) 런타임 binomial coefficient 계산 함수 (재귀 방식)

- choose(n, k)의 결과가 56이라면, choose(n-1, k-1)은 21, coose(n-1, k)는 35에 해당.

 

Q) 이를 어떻게 사전 계산할 수 있을까?

 

위 방식의 문제점은, 아직 해당 계산을 프로그램의 Init 단계에서 하더라도 Runtime에 계산하긴 해야 한다는 것이다.

→ 컴파일 타임에 얻어 보자, 즉 소스 코드 자체에 해당 테이블 값을 넣자.

4) Compile-Time Initialization

Q) 만약 1,000 x 1,000 크기가 필요하다면?

A) Metaprogramming.

 

→ static table을 생성할 때는 반드시 런타임 프로그래밍 언어와 통일할 필요는 없다. python script로 작성하여 생성한 뒤에 이를 읽어들이기만 해도 됨.

 

5) Caching

현대 컴퓨터에서 덧셈, 곱셈보다 sqrt()는 더 비싼 연산이므로, 동일한 A, B input이 들어왔다면 캐싱한 값을 반환함으로써 sqrt() 연산을 회피.

위 예제는 캐시가 1개 뿐이므로 현실적이진 않지만, 필요하다면 1,000개로 늘리는 등 바꿀 수 있음.

→ hardware-caching이 아닌 software-caching

→ 위 hypotenuse(빗변)을 구하는 함수 방식의 경우(아마도 캐시 크기도 늘렸을 때), cache hit일 때 30% 더 빠르다는 것이 밝혀져 있습니다.

6) Lazy evaluation

 

7) Sparsity

 

"가장 빠르게 계산하는 방법은 계산하지 않는 것이다."

 

위 Matrix-vector multiplication에서, 6x1 이므로 총 36번의 연산을 행해야 한다.

하지만, 대부분 행렬의 요소가 0이므로 0이 아닌 요소는 14개뿐이다.

 

더 빠르게 계산하는 방법은 각 요소가 0인지 확인하고 0이 아닐 때만 곱하는건데, 이는 여전히 느린 속도를 가지게 됨.

이를 위해 Compressed Sparse Row(CSR) 방식을 알아보자.

Compressed Sparse Column(CSC)도 존재하는데, 여기서는 CSR만 알아볼 예정.

 

rows : 0 2 6 8 10 11 14(<- overflow 방지)

cols :  0 4 1 2 4 5 3 5 0 3 0 4 3 4

vals :  3 1 4 1 5 9 2 6 5 3 5 8 9 7

 

Storage : O(n + nnz) instead of n^2 (n : row num)

nnz : number of non-zero

 

n + nnz인 이유

- n : rows 크기 (n + 1)

- nnz : cols, vals 크기

 

극단적으로 0인 entry가 존재하지 않는 경우, overflow를 방지하기 위한 추가적인 공간 1칸이 rows array에 추가된다.

scalar multiplication 횟수는 nnz인데, non-zero entry에 대해서만 연산하기 때문 (직관적)

 

이전 CSR(Compressed Sparse Row) Representation에서,

Offsets = Rows

Edges = Columns 로 대응해서 동일한 개념으로 이해하면 된다.

 

ex)

Vertex ID : 0

Offsets : 0

Edges : 1, 3

→ Edges[Offsets]로 가봐, 그러면 Vertex ID가 가리키는 간선들의 목록이 일렬로 있어. 그 간선의 개수는 (Offsets[VertexIDs + 1] - Offsets[VertexIDs])에 해당돼.

 

★ :

1) CSR Representation에서 values array처럼, Edges와 동일한 크기의 additinoal array를 둬서 Weights를 기록할 수도 있다.

2) 또는, Edges 내부에서 어떤 노드에 연결되어 있는지에 대한 정보의 바로 뒤에 교차(interleaved) 해서 Weights를 기록해도 된다.

2)이 더 효율적인데, 그 이유는 더 효율적인 cache locality를 제공하기 때문이다. 어차피 Edges에 접근할 때 한 번에 weight 정보까지 가져오기 때문에 동일한 Cache Line에 존재하기 때문.

 

[ Logic ]

8) Constant Folidng and Propagation

상수 표현식을 컴파일 타임에 평가.

 

9) Common-Subexpression Elimination

b = a - d;

d = a - d;

위 2개는 Common-Subexpression에 해당된다. 중복해서 동일한 값을 계산할 필요가 없기 때문에 d = b로 대체하여 연산을 제거할 수 있음.

단, 

a = b + c;

b = a - d;

c = b + c;

d = b;

위 볼드체로된 2개 식은 Common-Subexpression Elmination을 수행할 수 없는데, 중간에 b의 값이 변경되기 때문.

 

현대 컴파일러는 이러한 최적화는 자동으로 수행할정도로 똑똑하지만, 항상 수행하는 것은 아니므로 이런 최적화 방식을 알아둔다면 수동으로 시도해볼 수 있다(빌드된 바이너리또는 어셈블리 코드를 확인하면 최적화 수행여부를 확인할 수 있을듯 함).

10) Algebraic Identities

비싼 대수적 표현을 대수적으로 동등하면서도 값싼 연산으로 대체하는 것.

→ 거리를 구할 때, 굳이 sqrt연산까지 양변에 취해서 비교할 필요가 없음.

Unreal Engine에서, NetCullDistanceSquared와 동일한 개념으로 보임.

 

주의해야할 점은, float point를 사용할 경우 over flow, rounding 문제점을 고려해야 한다는 것.

 

11) Short-Circuiting

for loop 내부에서 이미 조건을 만족했다면 loop를 끊어버리고 바로 리턴하면 됨.

 

이 최적화 방식을 사용하면 loop 내에서 조건을 만족했는지 매번 확인하는 코드가 추가되어야 하므로, 실제로 최적화를 했을때 더 빨라졌는지, 오히려 더 느려졌는지 확인해야 한다.

 

★ : logical and, or 또한 short-circuiting에 해당된다.

반면에, bitwise and, or은 해당되지 않음.

 → short-circuiting이라는 용어 자체가 "조기 종료"를 의미하는 듯함.

12) Ordering Tests

Short-Circuiting에서 확장되는 주제.

 

더 자주 성공하거나 더 일찍 성공하는 테스트를 앞에 두고, 드물게 성공하는 테스트는 뒤에 둔다.

유사하게, 값싼 테스트는 비싼 테스트보다 앞에 둔다.

 

is_whitespace 함수의 경우, 텍스트 중에서 가장 많이 출현하는 빈도 순서대로 조건을 나열함.

(space > newline > tab > carriage return(현대에 거의 미사용))

13) Creating a Fast Path

9) Algebraic Identities를 이용하여 sqrt 연산없이 3차원 유클리드 거리를 구한다고 하더라도,

x, y, z 각각의 좌표 델타를 개별적으로 반지름보다 큰지 확인하는 것이 덧셈/뺄셈만 사용하므로 저렴하다.

→ 넓은 3차원 공간에서 2개의 공이 충돌할 확률은 희박하고, Fast Path에 해당되지 않아 실제 충돌을 확인해야 할 때만 곱셈을 수행하게 됨.

 

위 예제는 작은 단위의 함수이기 때문에 성능 상의 큰 이점이 없지만, 일반적으로 그래픽스 프로그램에서 Fast Path를 사용하는 것은 성능적으로 큰 이점이 존재함.

 

★ : Common-Subexeression Elimination을 적용하여 추가적인 최적화도 가능한데,

1) b1, b2의 반지름 합을 4번 계산(b1->r + b2->r).

2) b1, b2 개별 축 좌표의 차를 2번 계산(b1->x - b2->x, b1->y - b2->y, b1->z - b2->z).

14) Combining Tests

Full adder(전가산기) 예제.

a, b, c의 개별 케이스를 전부 if statement로 분기하면 branch prediction에도 안좋고, 가독성도 좋지 않다.

c, b, a 각각의 상태 비트를 LSB부터 차례대로 비트에 저장.

switch statement를 통해 단 한번의 branch로 연산한다.

 

코드 가독성뿐만 아니라 branch prediction으로 인해 성능도 좋아짐.

 

사실 위 예시는 설명을 위한 것이고,

좌측의 Full adder 표를 precomputed table에 저장한 뒤, 런타임에 조회(look-up)하는 방식이 더 빠르다.

 

Q) would coming up with logic gates for this be better or no?

이 방식을 위해 논리 게이트를 작성해보는게 더 낫지않나요?
A) Maybe, I encourage you to see if you can write a faster program for this.

아마도요, 실제로 더 빠른지 작성해보면 좋을거 같습니다.

: 그냥 bitwise 연산으로 런타임에 계산하는게 precompute보다 더 빠를 수도 있다?

 

답변 추측) 어딘가에 멀리 저장되어 있는 precomputed table을 조회하려면 결국 한 번의 TLB miss, cache miss, paging fault를 동반하지만, bitwise는 동일한 스택 메모리내에서 컴퓨터가 할 수 있는 가장 빠른 연산을 수행하므로?, 해당 최적화가 필요한 머신에서 실제로 측정해보면 좋을 것 같다.

[ Loop ]

대부분의 오래 실행되는 프로그램은 Loop로 이루어져 있기 때문에 Performance Egineering의 핵심 대상에 속한다.

게임 엔진도 결국 내부에서 while(true)로 돌고 있잖아?

15) Hoisting

loop내에서 반복 계산되지만, 값이 변하지 않는 invairant code는 loop 외부로 꺼내어 단 한번만 연산.

 

이 예제에서는 컴파일러가 아마도 자동으로 hoisting할 수 있습니다. 하지만 어떤 경우에는 함수(exp(sqrt(M_PI/2)))가 프로그램 중간에 달라질 수 있다거나 side effect가 있을 수 있다고 판단해 컴파일러가 최적화하지 못할 수 있습니다. 따라서 이 최적화를 알고 있으면 컴파일러가 하지 못하는 경우 직접 적용할 수 있습니다.

16) Sentinels

1) 좌측 예제

loop 돌 때 마다 2번의 branch 존재.

 

2) 우측 예제 (sentinel value 사용)

while loop를 돌 때 1번의 branch만 존재.

A[n+1]에다가 추가적인 positive number를 할당하는 이유는, A[0] ~ A[n-1] 모든 값이 0일 경우 overflow가 발생하지 않기 때문. 따라서 해당 케이스를 핸들링.

17) Loop Unrolling

Loop unrolling은 루프의 여러 개의 연속되는 iteration을 하나의 iteration으로 합쳐 work를 줄이는 기법입니다. 이렇게 하면 전체 iteration 횟수가 줄고, loop control instruction이 실행되는 횟수도 줄어듭니다.

Loop unrolling에는 두 종류가 있습니다.

1) full loop unrolling입니다. 루프의 모든 반복을 전부 펼쳐서 control-flow logic을 완전히 제거합니다. 예를 들어 10번만 도는 작은 루프라면, 오른쪽 코드처럼 10개의 명령을 straight-line code로 모두 써버릴 수 있습니다. 그러면 매 반복마다 루프 종료 조건을 검사할 필요가 없습니다.

하지만 full unrolling은 흔하지 않습니다. 대부분의 루프는 10번보다 훨씬 많이 돌고, loop bound가 컴파일 타임이 아니라 런타임에 결정되는 경우가 많습니다. 작은 루프는 컴파일러가 알아서 unroll할 수 있습니다. 큰 루프를 완전히 unroll하면 명령어 수가 너무 많아져 instruction cache를 오염시킬 수 있습니다.

 더 일반적인 방식은,

2) partial loop unrolling입니다. 예제에서는 루프를 4배 unroll합니다. 반복 횟수를 4분의 1로 줄이고, 각 반복의 body 안에 원래 반복 4개에 해당하는 명령을 넣습니다. 따라서 loop variable j는 1씩 증가하는 대신 4씩 증가합니다.

n이 반드시 4로 나누어떨어지는 것은 아니므로, 남은 원소를 처리하는 별도의 루프가 필요합니다.

Loop unrolling의 첫 번째 장점은 loop exit condition check 횟수가 줄어든다는 것입니다. 네 번마다 한 번만 검사하면 됩니다.

하지만 더 큰 장점은 compiler optimization의 기회를 늘린다는 것입니다. loop body가 커지면 컴파일러가 코드를 재배치하거나 최적화할 여지가 더 많아집니다. 보통 이 두 번째 장점이 더 중요합니다.

물론 너무 많이 unroll하면 좋지 않습니다. instruction cache를 오염시킬 수 있고, instruction fetch가 cache miss를 자주 일으켜 성능이 떨어질 수 있습니다. 또한 원래 loop body가 이미 크다면 컴파일러가 최적화할 코드가 충분하므로, 더 많은 코드를 제공해도 이득이 크지 않을 수 있습니다.

18) Loop Fusion

 

다음 최적화는 loop fusion입니다. 다른 이름으로는 jamming이라고도 합니다.

아이디어는 같은 index range를 순회하는 여러 loop를 하나의 loop로 합치는 것입니다. 이렇게 하면 loop control overhead를 줄일 수 있습니다.

예를 들어 두 개의 루프가 있습니다. 둘 다 i = 0부터 n-1까지 돕니다. 첫 번째 루프는 A[i]와 B[i] 중 작은 값을 C[i]에 저장합니다. 두 번째 루프는 A[i]와 B[i] 중 큰 값을 D[i]에 저장합니다.

두 루프가 같은 index range를 순회하므로, 하나의 루프로 합칠 수 있습니다. 그러면 loop exit condition check를 2n번 하는 대신 n번만 하면 됩니다.

또한 cache locality도 좋아집니다. C[i]를 계산할 때 A[i]와 B[i]를 cache로 가져왔다면, 곧바로 D[i]를 계산할 때도 그 값들이 cache에 있을 가능성이 큽니다. 반면 원래 코드에서는 두 번째 루프에 도달할 때 A[i]와 B[i]가 이미 cache에서 밀려났을 수 있습니다.

이 예제에도 9) common subexpression elimination을 적용할 수 있습니다. A[i] <= B[i]라는 표현을 두 번 계산한다면, 한 번만 계산해 재사용할 수 있습니다.

19) Eliminating Wasted Iterations

아이디어는 loop bound를 바꿔서, 사실상 empty body를 실행하는 반복을 피하는 것입니다.

예제로 Matrix Transpose 코드.

기본 코드는 i = 0..n-1, j = 0..n-1 전체를 순회하면서 i > j일 때만 A[i][j]와 A[j][i]를 swap합니다.

i > j 조건이 필요한 이유는 swap을 두 번 하면 원래 행렬로 되돌아가기 때문입니다. 따라서 대각선 아래쪽 절반만 swap해야 합니다.

하지만 이 코드는 여전히 n^2번 반복합니다. 그중 절반 정도는 i > j 조건을 통과하지 못해 아무 일도 하지 않습니다.

개선된 코드는 loop bound를 바꿉니다. i는 1부터 n-1까지 돌고, j는 0부터 i-1까지만 돕니다. 이렇게 하면 애초에 i > j인 경우만 순회합니다. 즉 조건 검사를 loop body 안에서 하는 대신 loop control code에 녹여 넣은 것입니다.

 

Q) 그럼 여전히 loop control에서 검사는 하는 것 아닌가요?

A) 네, loop control에는 여전히 검사가 있습니다. 하지만 원래 코드도 loop control 검사는 있었고, 추가로 body 안에서 i > j 검사를 또 했습니다. 개선된 코드는 body 내부 검사를 제거합니다.

 

Q) branch prediction이 잘 맞는 경우에는 원래 코드도 충분히 빠르지 않나요?

A) 네, 대부분 branch hit가 될 수 있어 꽤 빠를 수 있습니다. 그래도 검사를 아예 하지 않는 편이 더 빠를 수 있습니다. 런타임에 성능 향상이 존재하는지 여러분의 코드에서 실제로 측정해보는 것이 좋습니다.

[ Functions ]

20) Inlining

Inlining은 함수 호출의 overhead를 피하기 위해, 함수 호출을 함수 본문 자체로 바꾸는 것입니다.

예를 들어 배열 A의 원소들의 제곱합을 계산하는 코드가 있다고 해봅시다. 루프 안에서 매 반복마다 square 함수를 호출합니다. square(x)는 단순히 x * x를 반환합니다.

함수 호출에는 실제로 overhead가 있습니다. 따라서 함수 호출 대신 호출 위치에 함수 본문을 직접 넣을 수 있습니다. 즉 square(A[i])를 호출하지 않고, temp = A[i]를 둔 뒤 sum += temp * temp를 수행합니다.

 

→ 프로그래머가 수동으로 inlining을 시도하는 예시.

이 작업을 반드시 수동으로 할 필요는 없습니다. 함수를 static inline으로 선언하면 컴파일러가 그 함수를 inline하려고 시도합니다. 현대 컴파일러는 상당히 잘해주기 때문에 static inline을 쓰지 않아도 inline할 가능성이 큽니다. 그래도 inline을 원한다는 의도를 명확히 하려면 static inline을 사용할 수 있습니다.

그렇다면 macro(전처리)를 쓰면 되지 않을까요? 현대의 inline function은 macro만큼 효율적일 수 있고, 구조적으로는 더 낫습니다.

(→ 매크로는 전처리 단계에 바꿔치기 하므로 디버깅하기 힘들기 때문인듯)

 

inline function은 인자를 한 번 평가합니다. 반면 macro는 단순한 textual substitution입니다. 만약 macro 인자로 비싼 표현식을 넣으면, macro 확장 결과에서 그 표현식이 여러 번 복사될 수 있습니다. 컴파일러가 common subexpression elimination을 잘하지 못하면 work를 낭비하게 됩니다.

21) Tail-Recursion Elimination

 

첫째는 tail-recursion elimination입니다. 꼬리 재귀 호출을 실제 함수 호출 대신 jump나 loop 형태로 바꿔 call stack 증가와 함수 호출 overhead를 줄이는 기법입니다.

22) Coarsening recursion

둘째는 coarsening recursion입니다. 재귀 호출을 너무 작은 단위까지 계속하지 않고, 작은 문제에서는 더 단순한 직접 계산 방식으로 전환하는 기법입니다. 예를 들어 quicksort에서 작은 subarray는 insertion sort로 처리하는 방식이 여기에 해당합니다.

 

→ std::sort, Algo::sort in UE5의 경우 Intro Sort로 되어 있는데,

정렬해야할 아이템 수에 따라 동적으로 정렬 방식을 변경하는 것이 여기에 해당되는 듯함.

[ Closing Advice ]

Premature optimization을 피해야 합니다. 오늘 이야기한 모든 기법은 성능을 높일 수 있지만, 먼저 프로그램이 올바르게 동작해야 합니다. 올바른 일을 하지 않는 프로그램을 더 빠르게 만들어봐야 의미가 없습니다.

Correctness를 유지하기 위해서는 regression testing을 해야 합니다. 즉 프로그램을 바꿀 때마다 correctness를 확인할 수 있는 suite of test를 만들어야 합니다.

또 앞에서 말했듯이, 프로그램의 work를 줄인다고 해서 반드시 실행 시간이 줄어드는 것은 아닙니다. 하지만 work 감소는 좋은 휴리스틱입니다.

마지막으로, 컴파일러는 많은 low-level optimization을 자동화합니다. 컴파일러가 어떤 최적화를 했는지 확인하려면 assembly code를 보면 됩니다.