kldp 사이트 ( http://kldp.org/node/138750 )에서 "나누기 1000을 효과적으로 하는 방법"이라는 논의가 있어서 테스트를 해 보았습니다.



어떤 수가 8의 배수인지를 알아 내는 함수가 있다라고 가정을 합시다. 일반적으로 x86 machine에서는 나누기 명령어(DIV)는 클럭 수를 많이 잡아 먹기 때문에 최적화 과정에서 DIV op code를 사용하지 않고 가급적이면 다른 op code를 사용하도록 최적화 과정이 이루어 집니다.

bool isMultipleBy8(unsigned int i) { return i % 8 == 0; }
	test	cl, 7
	mov	eax, 0
	sete	al
	ret	0


위의 코드를 보면 알겠지만 인자(ecx)의 값에서 하위 3비트(CL register)가 전부 0인지 아닌지를 가지고 8의 배수 여부를 판단하는 로직이 적용되는 것을 확인할 수 있습니다(return 값은 EAX혹은 AL 레지스터를 통해 반환됨).




이왕 하는 김에 1의 배수~10의 배수를 알아 내는 함수들의 컴파일 결과를 정리해 보았습니다.


  • 1~10의 배수 및 1000의 배수 확인 함수 작성.
  • 컴파일 옵션 : Visual Studio 2012 Release mode - Maximize Speed (/O2).
  • signed int보다는 unsigned int가 일단 간단하기 때문에 parameter의 type을 unsigned int로 함.


bool isMultipleBy1(unsigned int i) { return i % 1 == 0; }
	mov	al, 1  // 무조건 참
	
bool isMultipleBy2(unsigned int i) { return i % 2 == 0; }
	not	ecx    // 1. bitwise not
	and	ecx, 1 // 2. ecx가 짝수이면 1, 홀수이면 0 
	mov	al, cl // 3. 1과 2가 합혀 져서 결과 도출

bool isMultipleBy3(unsigned int i) { return i % 3 == 0; }
	mov	eax, -1431655765			; aaaaaaabH
	mul	ecx
	shr	edx, 1
	lea	eax, DWORD PTR [edx+edx*2]
	sub	ecx, eax
	neg	ecx
	sbb	ecx, ecx
	lea	eax, DWORD PTR [ecx+1]

bool isMultipleBy4(unsigned int i) { return i % 4 == 0; }
	test	cl, 3
	mov	eax, 0
	sete	al

bool isMultipleBy5(unsigned int i) { return i % 5 == 0; }
	mov	eax, -858993459				; cccccccdH
	mul	ecx
	shr	edx, 2
	lea	eax, DWORD PTR [edx+edx*4]
	sub	ecx, eax
	neg	ecx
	sbb	ecx, ecx
	lea	eax, DWORD PTR [ecx+1]
	
bool isMultipleBy6(unsigned int i) { return i % 6 == 0; }
	mov	eax, -1431655765			; aaaaaaabH
	mul	ecx
	shr	edx, 2
	lea	eax, DWORD PTR [edx+edx*2]
	add	eax, eax
	sub	ecx, eax
	neg	ecx
	sbb	ecx, ecx
	lea	eax, DWORD PTR [ecx+1]
	
bool isMultipleBy7(unsigned int i) { return i % 7 == 0; }
	mov	eax, 613566757				; 24924925H
	mul	ecx
	push	esi
	mov	esi, ecx
	sub	esi, edx
	shr	esi, 1
	add	esi, edx
	shr	esi, 2
	lea	eax, DWORD PTR [esi*8]
	sub	eax, esi
	sub	ecx, eax
	neg	ecx
	sbb	ecx, ecx
	pop	esi
	lea	eax, DWORD PTR [ecx+1]

bool isMultipleBy8(unsigned int i) { return i % 8 == 0; }
	test	cl, 7
	mov	eax, 0
	sete	al

	
bool isMultipleBy9(unsigned int i) { return i % 9 == 0; }
	mov	eax, 954437177				; 38e38e39H
	mul	ecx
	shr	edx, 1
	lea	eax, DWORD PTR [edx+edx*8]
	sub	ecx, eax
	neg	ecx
	sbb	ecx, ecx
	lea	eax, DWORD PTR [ecx+1]
	
bool isMultipleBy10(unsigned int i) { return i % 10 == 0; }
	mov	eax, -858993459				; cccccccdH
	mul	ecx
	shr	edx, 3
	lea	eax, DWORD PTR [edx+edx*4]
	add	eax, eax
	sub	ecx, eax
	neg	ecx
	sbb	ecx, ecx
	lea	eax, DWORD PTR [ecx+1]

	
bool isMultipleBy1000(unsigned int i) { return i % 1000 == 0; }
	mov	eax, 274877907				; 10624dd3H
	mul	ecx
	shr	edx, 6
	imul	edx, 1000				; 000003e8H
	sub	ecx, edx
	neg	ecx
	sbb	ecx, ecx
	lea	eax, DWORD PTR [ecx+1]


divisor의 값에 따라서 컴파일러가 알아서 최적화를 자동으로 해 주는 것을 확인할 수 있습니다.



결론 : 대충 알아서 코딩을 해도 C++ 컴파일러가 알아서 최적화를 해 준다.



Download : mod_test.zip
You would..