BigFloat로 Pi를 구해보자-8. 어셈블리어로 최적화하기

요즘 컴파일러들은 매우 똑똑합니다. 어지간한 코드는 알아서 최적화시켜주지요. 그래서 대부분의 경우에는, 힘들여 어셈블리어 코드를 써서 최적화해놔도 컴파일러에 의한 최적화보다 못한 경우가 많습니다.

하지만! 이렇게 큰 수끼리 연산을 하는 코드는 최적화할 가능성이 많습니다.

우리가 예전에 덧셈과 뺄셈을 어떻게 구현했는지 한번 떠올려볼까요?(2. 덧셈, 뺄셈 구현하기)

긴 정수의 덧셈을 다음과 같이 구현했었죠.

1. 먼저 두 정수를 더한다.

2. 더한 결과가 원래 정수보다 작으면 받아올림이 발생한거다.

3. 윗 자리를 더할때 받아올림된 1도 같이 더해준다.

이를 위해서 n자리의 정수라면 총 n번의 덧셈과 n번의 비교와, 받아올림이 있다면 n번의 추가적인 덧셈이 필요했습니다. 즉 최악의 경우 3n번의 덧셈/비교 연산이 필요했다는 얘기지요.

하지만 x86 CPU에는 받아올림 플래그(carry flag, CF)라는 것이 있습니다. 두 수끼리 더해서(혹은 빼서) 그 결과가 오버플로우(overflow)가 발생하면 세트가 되고, 그렇지 않으면 클리어되는 플래그이지요.

또한 두 수끼리 더할 때 CF가 세트되어있으면 1을 더 더해주는 adc instruction도 있습니다. 이를 이용하면 굳이 위의 방법처럼 복잡하게 받아올림을 구현하지 않고도 간단하게 연산을 할수 있지요.

(설명이 장황해지는 것을 막기위해서 매우매우 기초적인 CPU구조와 어셈블리어는 알고 있다고 가정하겠습니다.)

자 이제 한 번 코드를 볼까요? (편의상 MSVC 스타일의 인라인 어셈블리 문법을 사용했습니다. 제가 딱히 마소빠라서 그런게 아니라, 그냥 익숙해서... )

몇가지 x86 instruction 소개가 있어야겠네요.

lodsd : esi 레지스터가 가리키는 지점에서 dword(4바이트)를 읽어와 eax에 넣는다. (c스타일로 쓰자면 eax = *esi;인셈)

명령어를 수행한 후에는 esi를 4바이트 뒤로 이동한다.(esi = 4)

stosd : edi 레지스터가 가리키는 곳으로 eax에서 dword(4바이트)를 읽어와 넣는다. (c스타일로 쓰자면 *edi = eax;인셈)

명렁어를 수행한 후에는 edi를 4바이트 뒤로 이동한다. (edi = 4)

adc : CF를 반영하여 덧셈 연산을 한다. (adc dest, src; 는 dest = src (CF ? 1 : 0) 의 의미인셈.)

pushf : 스택에 플래그 상태를 저장한다.

popf : 스택에 저장해뒀던 플래그 상태를 가져온다.

std : DF(방향 플래그)를 설정한다. 이게 설정되면 lodsd, stosd 명령어에서 edi, esi가 뒤로 이동하는게 아니라 앞으로 이동한다.

cld : DF를 해제한다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54

inline int i_adds(RRU32* dest, const RRU32* src, RRU32 len) { #ifdef _ASM_     __asm     {         std; // DF를 세트한다         mov ebx, [src]; // ebx = &src[0]         mov edi, [dest]; // edi = &dest[0]         mov ecx, [len]; // ecx = len         dec ecx; // ecx = len - 1         shl ecx, 2; // 주소는 byte단위이므로 4를 곱해야함.         add ebx, ecx; // ebx = &src[len - 1]         add edi, ecx; // edi = &dest[len - 1]         mov esi, edi; // esi = edi         mov ecx, [len];         clc; // CF를 클리어한다         pushf; loopstart:         popf;         lodsd; // 4바이트를 불러아서         adc eax, [ebx]; // 더하고         stosd; // 다시 저장함         pushf;         sub ebx, 04h; // ebx에서 4를 빼주어 ;// ebx가 다음 더할 곳을 가리키도록 해야함. ;// esi, edi는 자동으로 움직이므로 그럴필요없음. ;// sub는 CF를 변경하므로 이 연산 전에 ;// 플래그 상태를 저장해야함.         loop loopstart; // ecx횟수만큼 반복         popf;         cld; //DF를 클리어한다. 빼먹으면 큰일남.         jc ret1; // CF가 세트되어있으면 ret1로 점프.     };     return 0; ret1:     return 1; #else     int carry = 0;     for(RRU32 i = len - 1; i != (RRU32)(-1); --i)     {         dest[i]  = src[i];         if(carry)         {             dest[i]  ;             carry = dest[i] <= src[i];         }         else         {             carry = dest[i] < src[i];         }     }     return carry; #endif }

연재2 에서 구현했던 두 RRU32배열을 더해주는 함수입니다.

제일 앞에서 std를 하는 이유는, 우리가 처음에 정의내리기를 배열에서 뒤로 갈수록 아래자리를 표현한다고 그랬기 때문이지요. 덧셈은 제일 아랫자리에서부터 위로 올라오면서 해야하므로, DF를 세트하여, esi, edi가 거꾸로 움직이도록해야합니다.

불행히도 sub 명령어는 CF를 변경시키므로, 만약 pushf, popf를 하지 않는다면 CF가 맘대로 바뀌어 원하는 결과가 안나오겠지요.

이건 실은 최적화가 전혀 안된 코드라고 할 수 있습니다. 매번 반복할때마다 sub도 해야하고, pushf, popf까지... 이는 엄청난 비용입니다. 고전적인 최적화 방법중에 루프문 풀기(Loop Unrolling)이 있는데, 이는 반복문을 반복하는 대신 이를 풀어써서 반복하는데 사용되는 연산을 최소화하는 것입니다. 지금은 이를 사용하기에 딱 좋은 상황이죠. 먼저 최적화시킨 코드를 볼까요?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292

inline int i_adds(RRU32* dest, const RRU32* src, RRU32 len) { #ifdef _ASM_     __asm     {         std;         mov ebx, [src];         mov edi, [dest];         mov ecx, [len];         dec ecx;         shl ecx, 2;         add ebx, ecx;         add edi, ecx;         mov esi, edi;         mov ecx, [len];         clc;         pushf;   loopstart: // 몇 번 더 반복해야하는지 확인해서 점프한다.         test ecx, 00001b; //접미사 b는 이진수임을 뜻한다.         jnz add1;         test ecx, 00010b;         jnz add2;         test ecx, 00100b;         jnz add4;         test ecx, 01000b;         jnz add8;         test ecx, 10000b;         jnz add16; loopstart2: //여기서는 32번을 세트로 반복한다. //여기 들어왔을때는 이미 ecx는 32의 배수이다.         sub ecx, 20h;         jge add32;         jmp end_fun; add1: // 1번 반복하는 부분         popf;         lodsd;         adc eax, [ebx];         stosd;         pushf;         sub ebx, 04h;         dec ecx;         jmp loopstart;   add2: // 2번 반복하는 부분         popf;         lodsd;         adc eax, [ebx];         stosd;         lodsd;         adc eax, [ebx-04h];         stosd;         pushf;         sub ebx, 08h;         sub ecx, 2h;         jmp loopstart;   add4: // 4번 반복하는 부분         popf;         lodsd;         adc eax, [ebx];         stosd;         lodsd;         adc eax, [ebx-04h];         stosd;         lodsd;         adc eax, [ebx-08h];         stosd;         lodsd;         adc eax, [ebx-0Ch];         stosd;         pushf;         sub ebx, 10h;         sub ecx, 4h;         jmp loopstart;   add8: // 8번 반복하는 부분         popf;         lodsd;         adc eax, [ebx];         stosd;         lodsd;         adc eax, [ebx-04h];         stosd;         lodsd;         adc eax, [ebx-08h];         stosd;         lodsd;         adc eax, [ebx-0Ch];         stosd;         lodsd;         adc eax, [ebx-10h];         stosd;         lodsd;         adc eax, [ebx-14h];         stosd;         lodsd;         adc eax, [ebx-18h];         stosd;         lodsd;         adc eax, [ebx-1Ch];         stosd;         pushf;         sub ebx, 20h;         sub ecx, 8h;         jmp loopstart;   add16: // 16번 반복하는 부분         popf;         lodsd;         adc eax, [ebx];         stosd;         lodsd;         adc eax, [ebx-04h];         stosd;         lodsd;         adc eax, [ebx-08h];         stosd;         lodsd;         adc eax, [ebx-0Ch];         stosd;         lodsd;         adc eax, [ebx-10h];         stosd;         lodsd;         adc eax, [ebx-14h];         stosd;         lodsd;         adc eax, [ebx-18h];         stosd;         lodsd;         adc eax, [ebx-1Ch];         stosd;         lodsd;         adc eax, [ebx-20h];         stosd;         lodsd;         adc eax, [ebx-24h];         stosd;         lodsd;         adc eax, [ebx-28h];         stosd;         lodsd;         adc eax, [ebx-2Ch];         stosd;         lodsd;         adc eax, [ebx-30h];         stosd;         lodsd;         adc eax, [ebx-34h];         stosd;         lodsd;         adc eax, [ebx-38h];         stosd;         lodsd;         adc eax, [ebx-3Ch];         stosd;         pushf;         sub ebx, 40h;         sub ecx, 10h;         jmp loopstart;   add32: // 32번 반복하는 부분         popf;         lodsd;         adc eax, [ebx];         stosd;         lodsd;         adc eax, [ebx-04h];         stosd;         lodsd;         adc eax, [ebx-08h];         stosd;         lodsd;         adc eax, [ebx-0Ch];         stosd;         lodsd;         adc eax, [ebx-10h];         stosd;         lodsd;         adc eax, [ebx-14h];         stosd;         lodsd;         adc eax, [ebx-18h];         stosd;         lodsd;         adc eax, [ebx-1Ch];         stosd;         lodsd;         adc eax, [ebx-20h];         stosd;         lodsd;         adc eax, [ebx-24h];         stosd;         lodsd;         adc eax, [ebx-28h];         stosd;         lodsd;         adc eax, [ebx-2Ch];         stosd;         lodsd;         adc eax, [ebx-30h];         stosd;         lodsd;         adc eax, [ebx-34h];         stosd;         lodsd;         adc eax, [ebx-38h];         stosd;         lodsd;         adc eax, [ebx-3Ch];         stosd;         lodsd;         adc eax, [ebx-40h];         stosd;         lodsd;         adc eax, [ebx-44h];         stosd;         lodsd;         adc eax, [ebx-48h];         stosd;         lodsd;         adc eax, [ebx-4Ch];         stosd;         lodsd;         adc eax, [ebx-50h];         stosd;         lodsd;         adc eax, [ebx-54h];         stosd;         lodsd;         adc eax, [ebx-58h];         stosd;         lodsd;         adc eax, [ebx-5Ch];         stosd;         lodsd;         adc eax, [ebx-60h];         stosd;         lodsd;         adc eax, [ebx-64h];         stosd;         lodsd;         adc eax, [ebx-68h];         stosd;         lodsd;         adc eax, [ebx-6Ch];         stosd;         lodsd;         adc eax, [ebx-70h];         stosd;         lodsd;         adc eax, [ebx-74h];         stosd;         lodsd;         adc eax, [ebx-78h];         stosd;         lodsd;         adc eax, [ebx-7Ch];         stosd;         pushf;         sub ebx, 80h;         jmp loopstart2;   end_fun:         popf;         cld;         jc ret1;     };     return 0; ret1:     return 1; #else     int carry = 0;     for(RRU32 i = len - 1; i != (RRU32)(-1); --i)     {         dest[i]  = src[i];         if(carry)         {             dest[i]  ;             carry = dest[i] <= src[i];         }         else         {             carry = dest[i] < src[i];         }     }     return carry; #endif }

코드가 매우 길어졌지요... 개략적인 구조는 다음과 같습니다.

큰 줄기는 32번을 한 단위로 반복하는 것입니다. 그러면 32번 덧셈할 동안, popf 한번, pushf 한번, sub 한두번 하면 되니깐요. 단순 명령어 수로 비교해도 최적화 이전에 루프문 32번 도는것은 명령어수가 7*32 = 224개인데 비해, 32번을 한 세트로 실행하는 코드는 명령어수가 100개 밖에 되지 않습니다.

게다가 현대 CPU의 파이프라인 구조 상 분기예측이 실패할 경우에는 IPC(사이클 당 명령어 실행수)가 급격하게 떨어지므로, 분기가 적어야 효율이 높아집니다.

근데 문제는 len이 32의 배수가 아닐 경우는 처리할 수가 없다는 것이지요. 그래서 1,2,4,8,16번 반복하는 경우를 작성해두고, 32로 나누어 떨어지지 않을 경우는 1,2,4,8,16을 조합하여 사용하는 것입니다. (32미만의 자연수는 1,2,4,8,16을 조합하여 표현할 수 있지요.)

test 명령어는 레지스터가 특정 비트를 가지고 있는지 확일할때 사용합니다. 이 명령을 이용해 먼저 len의 아래 5비트를 조사하고, 1,2,4,8,16번 중 적당한 곳으로 점프합니다. 그리고 그 다음부터는 32번을 세트로 반복하는 것이지요.

마찬가지 방법을 뺄셈에서도 적용할 수 있습니다. 받아내림을 고려하여 뺄셈을 수행하는 명령어는 sbb입니다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290

inline int i_subs(RRU32* dest, const RRU32* src, RRU32 len) { #ifdef _ASM_     __asm     {         std;         mov ebx, [src];         mov edi, [dest];         mov ecx, [len];         dec ecx;         shl ecx, 2;         add ebx, ecx;         add edi, ecx;         mov esi, edi;         mov ecx, [len];         clc;         pushf;   loopstart:         test ecx, 00001b;         jnz add1;         test ecx, 00010b;         jnz add2;         test ecx, 00100b;         jnz add4;         test ecx, 01000b;         jnz add8;         test ecx, 10000b;         jnz add16; loopstart2:         sub ecx, 20h;         jge add32;         jmp end_fun; add1:         popf;         lodsd;         sbb eax, [ebx];         stosd;         pushf;         sub ebx, 04h;         dec ecx;         jmp loopstart;   add2:         popf;         lodsd;         sbb eax, [ebx];         stosd;         lodsd;         sbb eax, [ebx-04h];         stosd;         pushf;         sub ebx, 08h;         sub ecx, 2h;         jmp loopstart;   add4:         popf;         lodsd;         sbb eax, [ebx];         stosd;         lodsd;         sbb eax, [ebx-04h];         stosd;         lodsd;         sbb eax, [ebx-08h];         stosd;         lodsd;         sbb eax, [ebx-0Ch];         stosd;         pushf;         sub ebx, 10h;         sub ecx, 4h;         jmp loopstart;   add8:         popf;         lodsd;         sbb eax, [ebx];         stosd;         lodsd;         sbb eax, [ebx-04h];         stosd;         lodsd;         sbb eax, [ebx-08h];         stosd;         lodsd;         sbb eax, [ebx-0Ch];         stosd;         lodsd;         sbb eax, [ebx-10h];         stosd;         lodsd;         sbb eax, [ebx-14h];         stosd;         lodsd;         sbb eax, [ebx-18h];         stosd;         lodsd;         sbb eax, [ebx-1Ch];         stosd;         pushf;         sub ebx, 20h;         sub ecx, 8h;         jmp loopstart;   add16:         popf;         lodsd;         sbb eax, [ebx];         stosd;         lodsd;         sbb eax, [ebx-04h];         stosd;         lodsd;         sbb eax, [ebx-08h];         stosd;         lodsd;         sbb eax, [ebx-0Ch];         stosd;         lodsd;         sbb eax, [ebx-10h];         stosd;         lodsd;         sbb eax, [ebx-14h];         stosd;         lodsd;         sbb eax, [ebx-18h];         stosd;         lodsd;         sbb eax, [ebx-1Ch];         stosd;         lodsd;         sbb eax, [ebx-20h];         stosd;         lodsd;         sbb eax, [ebx-24h];         stosd;         lodsd;         sbb eax, [ebx-28h];         stosd;         lodsd;         sbb eax, [ebx-2Ch];         stosd;         lodsd;         sbb eax, [ebx-30h];         stosd;         lodsd;         sbb eax, [ebx-34h];         stosd;         lodsd;         sbb eax, [ebx-38h];         stosd;         lodsd;         sbb eax, [ebx-3Ch];         stosd;         pushf;         sub ebx, 40h;         sub ecx, 10h;         jmp loopstart;   add32:         popf;         lodsd;         sbb eax, [ebx];         stosd;         lodsd;         sbb eax, [ebx-04h];         stosd;         lodsd;         sbb eax, [ebx-08h];         stosd;         lodsd;         sbb eax, [ebx-0Ch];         stosd;         lodsd;         sbb eax, [ebx-10h];         stosd;         lodsd;         sbb eax, [ebx-14h];         stosd;         lodsd;         sbb eax, [ebx-18h];         stosd;         lodsd;         sbb eax, [ebx-1Ch];         stosd;         lodsd;         sbb eax, [ebx-20h];         stosd;         lodsd;         sbb eax, [ebx-24h];         stosd;         lodsd;         sbb eax, [ebx-28h];         stosd;         lodsd;         sbb eax, [ebx-2Ch];         stosd;         lodsd;         sbb eax, [ebx-30h];         stosd;         lodsd;         sbb eax, [ebx-34h];         stosd;         lodsd;         sbb eax, [ebx-38h];         stosd;         lodsd;         sbb eax, [ebx-3Ch];         stosd;         lodsd;         sbb eax, [ebx-40h];         stosd;         lodsd;         sbb eax, [ebx-44h];         stosd;         lodsd;         sbb eax, [ebx-48h];         stosd;         lodsd;         sbb eax, [ebx-4Ch];         stosd;         lodsd;         sbb eax, [ebx-50h];         stosd;         lodsd;         sbb eax, [ebx-54h];         stosd;         lodsd;         sbb eax, [ebx-58h];         stosd;         lodsd;         sbb eax, [ebx-5Ch];         stosd;         lodsd;         sbb eax, [ebx-60h];         stosd;         lodsd;         sbb eax, [ebx-64h];         stosd;         lodsd;         sbb eax, [ebx-68h];         stosd;         lodsd;         sbb eax, [ebx-6Ch];         stosd;         lodsd;         sbb eax, [ebx-70h];         stosd;         lodsd;         sbb eax, [ebx-74h];         stosd;         lodsd;         sbb eax, [ebx-78h];         stosd;         lodsd;         sbb eax, [ebx-7Ch];         stosd;         pushf;         sub ebx, 80h;         jmp loopstart2;   end_fun:         popf;         cld;         jc ret1;     };     return 0; ret1:     return 1; #else       int carry = 0;     for(RRU32 i = len - 1; i != (RRU32)(-1); --i)     {         if(carry)         {             carry = dest[i] <= src[i];             dest[i]--;         }         else         {             carry = dest[i] < src[i];         }         dest[i] -= src[i];     }     return carry; #endif }

i_adds함수에서 adc를 sbb로 바꾼 정도입니다.ㅋ

글이 길어지는 관계로 시프트 연산 최적화는 다음으로 패-스.