곱셈과 나눗셈의 최적화

작성자
조재혁(minzkn@minzkn.com)
고친과정
2007년 5월 5일 : 처음씀

1.1. 개요
1.2. 참고: 정수를 다루는데 있어서 알아둘 점

1.1. 개요

2진법에서의 곱셈/나눗셈의 한가지 관점에 대해서 소개하고자 합니다.
물론 CPU가 이렇게 한다는 것은 보장할수 없지만 이렇게도 할수 있다는 것을 설명하기 위한 취지로 적었습니다.

근본적으로 이건 이미 널리 쓰이는 방법이며 원리는 간단합니다.
곱셈을 쉬프트와 덧셈으로 어떻게 바꿀수 있는가를 고려한 이야기 입니다.

우리 간단히 이런거 하죠?

a = a * 2;

이것을 쉬프트로 바꾸면 a = a << 1;
일단 이것은 다들 아는 내용이라서 구차 설명하진 않겠습니다. 그러면 이건 어떻게 바꿀까요?

a = a * 3;

a = (a * 2) + a;

즉,

a = (a << 1) + a;

이렇게 바꾸면 되겠군요.
근데 여기까지는 누구라도 생각하겠지요?
근데 만약 이런거면 어떻게 하실런지요?

a = a * 640;

숫자가 너무 높아서 뒷머리가 뻐근하게 아파오는것이 한편으로는 궁굼하죠? ....
(무언가 규칙이 있을법 한데 ... 그게 뭘까요?)

여기서 제가 말하고자 하는 꽁수는 조건이 있습니다.

첫째: 곱셈의 숫자중 1개는 반드시 상수다!

둘째: 또는 가변적이지만 한번 값이 결정되면 많은 루프를 수행한다.

이게 조건입니다. 이경우 제가 설명하는 것을 써먹어보세요.
그럼 위의 640의 곱을 제가 어떻게 할수 있다는 예기가 되겠죠?
일단 2진수 형태로 만들면 그것이 해답입니다.

2 | 640 
  +--------- 
2 | 320 >>> 0 
  +--------- 
2 | 160 >>> 0 
  +--------- 
2 | 80 >>> 0 
  +--------- 
2 | 40 >>> 0 
  +--------- 
2 | 20 >>> 0 
  +--------- 
2 | 10 >>> 0 
  +--------- 
2 | 5 >>> 0 
  +--------- 
2 | 2 >>> 1 
  +--------- 
     1 >>> 0

요렇게 2진수로 바꾸는거 아시죠?

0000 0010 1000 0000

이렇게 되겠네요.
일단 요기서 1이라는 숫자가 2개뿐이 없네요.
이건 즉, 쉬프트 두번과 그에 합으로 곱을 나타낸다는 말이죠. (왜 그럴까요?)

왼쪽에서 첫번째 1은 다음과 같이 바꿀수 있습니다.

1 << 9

왼쪽에서 두번째 1은 다음과 같이 바꿀수 있습니다.

1 << 7

이제 되었습니다.
a = a * 640 이라는 식은 다음과 같이 바꿀수 있겠네요.

a = (a << 9) + (a << 7);

하하하 드디어 뭔가 감이 오지 않나요? (안온다면 그냥 곱셈 계속 쓰시고요...)
근데 C언어로 해석한다면 오히려 길어졌는데 왜 빨라지냐고요?

근데 이거 어디다가 쓰면 가장 좋을까요?
점하나 찍는 frame buffer 를 다룬다고 합시다.

*(VideoRam + (y * xRESOLUTION) + x) = Color;

어디서 많이 본 공식이죠?
여기서 xRESOLUTION이 640 이라면?

*(VideoRam + ( (y << 9) + (y << 7) ) + x) = Color;

요렇게 바꾸어보면 무지(쬐금) 빠른 그래픽 처리가 되겠네요.

아주 흥미로운 관심사이어서 Linux 에서 직접 테스트 코드를 짜봤습니다.

실제로는 완전한 Test 를 고려한다면 RealTime OS 환경이 필요한듯 싶다는 생각이 들었습니다.
(아래와 같이 TEST COUNT 한번의 clock 수가 다른 COUNT의 clock과 너무 차이 나는 경우는 Context switch가 일어난것으로 보이므로 결과를 신뢰할수 없는 경우겠지요.)

쉽게 보시도록 /* !! */ 로 붙인 부분이 각 테스트 항목마다 다른 부분입니다.
그리고 소스에서 volatile 변수를 사용하여 일부 원치않는(C 로 계산하는 부분) 최적화를 방지하기 위해서 사용한 것입니다.

아래의 결과화면은 완성도를 높이기 위해서 Linux에서 모든 서비스를 중지하고 커널과 init 프로세스 그리고 getty 만 살려둔채 아무 영향을 받지 않도록 최소의 프로세스를 띄우고 실행한 결과입니다.

그리고 결과수치를 통계를 내보면 거의 동일한 성능을 보였습니다.

참고로 아래의 결과는 Intel pentium III mobile CPU 1.06GHz 에서 테스트하였습니다.
여기서 약 39211 clock 을 소모한 TESTCOUNT만이 테스트에 유효성을 갖는다고 할수 있을거 같군요. (왜냐하면 RealTime OS가 아니기 때문에...)

TEST START !
=== TEST [1] === -------------------------------------- ( 436005 clock)
test_0 : 158249 (result=153920) /* C source */
test_1 : 70457 (result=153920) /* LEA + SHL */
test_2 : 66659 (result=153920) /* IMUL */
test_3 : 140021 (result=153920) /* LEA + ADDx7 */

=== TEST [2] === -------------------------------------- ( 39809 clock)
test_0 : 10365 (result=153920) /* C source */
test_1 : 6719 (result=153920) /* LEA + SHL */
test_2 : 6685 (result=153920) /* IMUL */
test_3 : 15738 (result=153920) /* LEA + ADDx7 */

=== TEST [3] === -------------------------------------- ( 39232 clock)
test_0 : 10308 (result=153920) /* C source */
test_1 : 6433 (result=153920) /* LEA + SHL */
test_2 : 6527 (result=153920) /* IMUL */
test_3 : 15715 (result=153920) /* LEA + ADDx7 */

=== TEST [4] === -------------------------------------- ( 39211 clock)
test_0 : 10288 (result=153920) /* C source */
test_1 : 6432 (result=153920) /* LEA + SHL */
test_2 : 6527 (result=153920) /* IMUL */
test_3 : 15715 (result=153920) /* LEA + ADDx7 */

=== TEST [5] === -------------------------------------- ( 52870 clock)
test_0 : 10288 (result=153920) /* C source */
test_1 : 6432 (result=153920) /* LEA + SHL */
test_2 : 6527 (result=153920) /* IMUL */
test_3 : 29374 (result=153920) /* LEA + ADDx7 */

=== TEST [6] === -------------------------------------- ( 39262 clock)
test_0 : 10288 (result=153920) /* C source */
test_1 : 6423 (result=153920) /* LEA + SHL */
test_2 : 6527 (result=153920) /* IMUL */
test_3 : 15751 (result=153920) /* LEA + ADDx7 */

=== TEST [7] === -------------------------------------- ( 39211 clock)
test_0 : 10288 (result=153920) /* C source */
test_1 : 6432 (result=153920) /* LEA + SHL */
test_2 : 6527 (result=153920) /* IMUL */
test_3 : 15715 (result=153920) /* LEA + ADDx7 */

=== TEST [8] === -------------------------------------- ( 39211 clock)
test_0 : 10288 (result=153920) /* C source */
test_1 : 6432 (result=153920) /* LEA + SHL */
test_2 : 6527 (result=153920) /* IMUL */
test_3 : 15715 (result=153920) /* LEA + ADDx7 */

=== TEST [9] === -------------------------------------- ( 39211 clock)
test_0 : 10288 (result=153920) /* C source */
test_1 : 6432 (result=153920) /* LEA + SHL */
test_2 : 6527 (result=153920) /* IMUL */
test_3 : 15715 (result=153920) /* LEA + ADDx7 */

=== TEST [10] === -------------------------------------- ( 39211 clock)
test_0 : 10288 (result=153920) /* C source */
test_1 : 6432 (result=153920) /* LEA + SHL */
test_2 : 6527 (result=153920) /* IMUL */
test_3 : 15715 (result=153920) /* LEA + ADDx7 */

End of test.

/* 
  Copyright (C) JAEHYUK CHO
  All rights reserved.
  Author: JAEHYUK CHO <mailto:minzkn@minzkn.com>
*/ 

#include <stdio.h> 

#define DEF_TESTCOUNT (10) 

typedef unsigned long long t_mz_qword; 
#define DEF_ASM __asm__ volatile 
#define DEF_RDTSC(m_X) DEF_ASM("rdtsc\n\t" : "=A"(m_X)) 

#define __emit_x8__(m_X)  do{ {m_X}{m_X}{m_X}{m_X} {m_X}{m_X}{m_X}{m_X} }while(0) 
#define __emit_x32__(m_X) do{ __emit_x8__(m_X); __emit_x8__(m_X); __emit_x8__(m_X); __emit_x8__(m_X); }while(0) 
#define __emit_x128__(m_X) do{ __emit_x32__(m_X); __emit_x32__(m_X); __emit_x32__(m_X); __emit_x32__(m_X); }while(0) 
#define __emit_x512__(m_X) do{ __emit_x128__(m_X); __emit_x128__(m_X); __emit_x128__(m_X); __emit_x128__(m_X); }while(0) 
#define __emit_x2048__(m_X) do{ __emit_x512__(m_X); __emit_x512__(m_X); __emit_x512__(m_X); __emit_x512__(m_X); }while(0) 

/* Inline loop code */ 
#define __emit_code__(m_X) __emit_x2048__(m_X) 

/* Volatile var */ 
volatile unsigned int g_resx   = 640; 
volatile unsigned int g_resy   = 480; 
volatile unsigned int g_x      = 640 >> 1; 
volatile unsigned int g_y      = 480 >> 1; 
volatile unsigned int g_result = 0; 

t_mz_qword test0(void) 
{ 
    /* ** */ t_mz_qword s_p_start, s_p_end; 
    /* ** */ DEF_RDTSC(s_p_start); 
    /* ** */ __emit_code__( 
    /* !! */  g_result = (g_y * 640) + g_x; 
    /* ** */ ); 
    /* ** */ DEF_RDTSC(s_p_end); 
    /* ** */ return(s_p_end - s_p_start); 
} 

t_mz_qword test1(void) 
{ 
    /* ** */ t_mz_qword s_p_start, s_p_end; 
    /* ** */ DEF_RDTSC(s_p_start); 
    /* ** */ DEF_ASM("\n\t":: "d"(g_x), "c"(g_y)); 
    /* ** */ __emit_code__( 
    /* ** */  DEF_ASM( 
    /* ** */   "movl %%ecx, %%eax\n\t" 
    /* !! */   "leal (%%eax,%%eax,4),%%eax\n\t" 
    /* !! */   "shll $0x07, %%eax\n\t" 
    /* ** */   "addl %%edx, %%eax\n\t" 
    /* ** */   ::);  
    /* ** */ ); 
    /* ** */ DEF_ASM("\n\t": "=a"(g_result)); 
    /* ** */ DEF_RDTSC(s_p_end); 
    /* ** */ return(s_p_end - s_p_start); 
} 

t_mz_qword test2(void) 
{ 
    /* ** */ t_mz_qword s_p_start, s_p_end; 
    /* ** */ DEF_RDTSC(s_p_start); 
    /* ** */ DEF_ASM("\n\t":: "d"(g_x), "c"(g_y)); 
    /* ** */ __emit_code__( 
    /* ** */  DEF_ASM( 
    /* ** */   "movl %%ecx, %%eax\n\t" 
    /* !! */   "imul $640, %%eax, %%eax\n\t" 
    /* ** */   "addl %%edx, %%eax\n\t" 
    /* ** */   ::); 
    /* ** */ ); 
    /* ** */ DEF_ASM("\n\t": "=a"(g_result)); 
    /* ** */ DEF_RDTSC(s_p_end); 
    /* ** */ return(s_p_end - s_p_start); 
} 

t_mz_qword test3(void) 
{ 
    /* ** */ t_mz_qword s_p_start, s_p_end; 
    /* ** */ DEF_RDTSC(s_p_start); 
    /* ** */ DEF_ASM("\n\t":: "d"(g_x), "c"(g_y)); 
    /* ** */ __emit_code__( 
    /* ** */  DEF_ASM( 
    /* ** */   "movl %%ecx, %%eax\n\t" 
    /* !! */   "leal (%%eax,%%eax,4),%%eax\n\t" 
    /* !! */   "addl %%eax, %%eax\n\t" /* 1 */ 
    /* !! */   "addl %%eax, %%eax\n\t" /* 2 */ 
    /* !! */   "addl %%eax, %%eax\n\t" /* 3 */ 
    /* !! */   "addl %%eax, %%eax\n\t" /* 4 */ 
    /* !! */   "addl %%eax, %%eax\n\t" /* 5 */ 
    /* !! */   "addl %%eax, %%eax\n\t" /* 6 */ 
    /* !! */   "addl %%eax, %%eax\n\t" /* 7 */ 
    /* ** */   "addl %%edx, %%eax\n\t" 
    /* ** */   ::); 
    /* ** */ ); 
    /* ** */ DEF_ASM("\n\t": "=a"(g_result)); 
    /* ** */ DEF_RDTSC(s_p_end); 
    /* ** */ return(s_p_end - s_p_start); 
} 

void test(int s_TestCount) 
{ 
    t_mz_qword s_p_start, s_p_end; 
    t_mz_qword s_p_test_0, s_p_test_1, s_p_test_2, s_p_test_3; 
    unsigned int s_result_0, s_result_1, s_result_2, s_result_3; 

    /* start */ 
    DEF_RDTSC(s_p_start); 
    g_result = 0; s_p_test_0 = test0(); s_result_0 = g_result; 
    g_result = 0; s_p_test_1 = test1(); s_result_1 = g_result; 
    g_result = 0; s_p_test_2 = test2(); s_result_2 = g_result; 
    g_result = 0; s_p_test_3 = test3(); s_result_3 = g_result; 
    DEF_RDTSC(s_p_end); 

    /* report */ 
    fprintf(stdout, 
      "=== TEST [%d] === -------------------------------------- (%8llu clock)\n" 
      "test_0      : %8llu (result=%u) /* C source    */\n" 
      "test_1      : %8llu (result=%u) /* LEA + SHL   */\n" 
      "test_2      : %8llu (result=%u) /* IMUL        */\n" 
      "test_3      : %8llu (result=%u) /* LEA + ADDx7 */\n" 
      "\n", 
      s_TestCount, s_p_end - s_p_start, 
      s_p_test_0, s_result_0, 
      s_p_test_1, s_result_1, 
      s_p_test_2, s_result_2, 
      s_p_test_3, s_result_3); 
} 

int main(void) 
{ 
    int s_TestCount; 
    fprintf(stdout, "TEST START !\n"); 
    for(s_TestCount = 1;s_TestCount <= DEF_TESTCOUNT;s_TestCount++)test(s_TestCount); 
    fprintf(stdout, "\nEnd of test.\n"); 
    return(0); 
} 

/* End of source */

1.2. 참고: 정수를 다루는데 있어서 알아둘 점

질문

하기와 같은 singed int와 unsigned int을 비교했을 때 상황에 따라서 어떤게 효율적일까요?

int i;
unsigned int j;

i = i / 3;
j = j / 3;

답변(해설)

결국 답은 아래의 어셈블리 코드를 참시면 이해될겁니다.

극적인 예를 위한 어셈블리지만 정말 잘 만든 코드들 보면요런 특징을 유념하고 있는게 많이 보입니다.

즉, 부호를 다뤄야 하는지 그렇지 않아도 되는지는 컴파일러가 판단할 수 없다는 것입니다.

/* i = i / 3; */
mov ecx, i
mov eax, 1431655766 ; 55555556H
imul ecx
mov eax, edx
shr eax, 31 ; 0000001fH
add eax, edx

/* j = j / 3; */
mov eax, -1431655765 ; aaaaaaabH
mul i
shr edx, 1