MOD(%) 연산의 AND(&) 연산으로의 처리

1. MOD(%) 연산의 AND(&) 연산으로의 처리
 다음의 글은 일반적으로 프로그램 시에 나머지를 구하기 위해 사용하는 MOD(%) 연산을 AND(&) 연산으로 처리하는 방법과 그 효율에 대한 테스트 결과입니다.

※ 전제 조건

2의 배수를 몫으로 갖는 MOD(%) 연산 처리의 적용

 다음의 [표 1]은 해당 연산자들의 성능 테스트 결과입니다.

 

연산/회수	100회	1,000회	5,000회	10,000회	50,000회
MOD(%)	0 ms	15 ms	94 ms	156 ms	797 ms
AND(&)	0 ms	0 ms	15 ms	47 ms	219 ms

                                             [표 1] 각 연산별 수행 시간

 위의 [표 1]에서와 같이 각 연산의 처리 시간을 보면, 그 성능 차이를 확인할 수 있을 것입니다. 서버의 경우 쉼 없이 동작하기 때문에 만약 해당 연산 처리가 적용된다면 약간이나마 성능을 높이지 않을까 합니다.

 

1.1    연산 처리 예

 다음의 예는 몫을 4로 나눈 나머지를 구하는 연산처리로 각각 MOD(%)와 AND(&) 연산을 사용한 예입니다.

7 % 4 = 3

7 & 3 = 3

 위의 결과가 같게 나오는데 이는 다음과 같은 원리를 갖기 때문입니다.

7 % 4 = 3

 여기서 %를 하는 4는 2^2 인데, 이를 AND 연산으로 처리하기 위해서는 다음과 같은 공식이 적용됩니다.

2^2(=4) – 1 = 3

※ 참고사항

 AND 연산을 할 몫은 원래 나누려고 했던 4 즉, 2^2-1 로 나오게 되었으므로, 2^n-1 이란 공식이 도출됩니다.

 이를 좀더 자세히 설명하자면, 7을 3으로 AND 하면 다음과 같이 처리됩니다. 다들 알다시피 AND 연산은 두 값이 모두 1일 때만 1을 출력하는 원리를 이용한 것입니다.

[그림 1] AND 연산

2. 성능 테스트 프로그램

다음은 각 연산의 성능을 테스트하기 위해 작성한 간단한 함수들을 갖고 있는 프로그램입니다.

 

2.1 테스트 프로그램

 프로그램은 간단한 함수로 이루어져있습니다. 원리는 각각의 연산을 처리하는데 있어서, 모든 요청에 대해 해당 요청 인덱스의 맨 첫번째 인덱스 값을 확인하는 것입니다. 이 때 4개의 묶음 단위의 처리하여, 맨 처음 값을 알아내기 위해 MOD와 AND 연산을 사용한 것입니다. 

(1) 상수 및 변수

 다음은 프로그램에서 사용된 상수와 변수로 값을 관리하는 배열과 요청 회수 체크를 위해 선언되었습니다. 여기서 MAX_CYCLE 상수의 경우에는 서버로 들어오는 요청이라 가정하여 루프에서 사용되는 값이며, 이 값을 증가시켜 프로그램의 성능을 테스트 합니다.

//----------------------------------------------------------------------------------//

// 상수 정의

//----------------------------------------------------------------------------------//

#define MAX_BLOCK                        1024

#define MAX_CYCLE                       10000                                // 루프 회수

#define BLOCK_UNIT                        4

//----------------------------------------------------------------------------------//

// 멤버 변수

//----------------------------------------------------------------------------------//

TCHAR                 m_szCheckBlcoks[MAX_BLOCK];                  // 블록 정보 저장

(2) 배열 초기화 함수

//----------------------------------------------------------------------------------//

// FUNCTION        :            InitCheckBlock

// PARAMETER    :            None

// RETURN           :            None

// NOTE               :            배열 초기화와 함께 4개의 인덱스 묶음 단위의 첫번째 인덱스에 값이 있음을 체크한다.

//----------------------------------------------------------------------------------//

void InitCheckBlock()

{

             memset(m_szCheckBlcoks, 0x00, MAX_BLOCK);

 

             for( ULONG           ulIndex = 0; ulIndex < MAX_BLOCK; ulIndex++ )

             {

                           if( (ulIndex % BLOCK_UNIT) == 0 )

                                        m_szCheckBlcoks[ulIndex] = '1';

                           else

                                        m_szCheckBlcoks[ulIndex] = '0';

             }

}

(3) MOD 연산 성능 체크 함

//----------------------------------------------------------------------------------//

// FUNCTION        :            CheckModPerformance

// PARAMETER    :            None

// RETURN           :            None

// NOTE               :            MOD(%) 연산의 성능 체크

//----------------------------------------------------------------------------------//

void CheckModPerformance()

{

             DWORD   dwStartTime = GetTickCount();

             ULONG   ulStartBlockNum = 0;          

 

             for( ULONG ulCycle = 0; ulCycle < MAX_CYCLE; ulCycle++ )

             {

                           for( ULONG ulIndex = 0; ulIndex < MAX_BLOCK; ulIndex++ )

                           {

                                        ulStartBlockNum = ulIndex - (ulIndex % 4);

 

                                        TRACE("[%04u][%04u] %c\n", ulIndex, ulStartBlockNum, m_szCheckBlcoks[ulStartBlockNum]);

                           }

             }

 

             TRACE(_T("- [TIME] MOD : %u\n"), GetTickCount()-dwStartTime);

}

(4) AND 연산 성능 체크 함수

//----------------------------------------------------------------------------------//

// FUNCTION        :            CheckAndPerformance

// PARAMETER    :            None

// RETURN           :            None

// NOTE               :            AND(&) 연산의 성능 체크

//----------------------------------------------------------------------------------//

void CheckAndPerformance()

{

             ULONG   ulStartBlockNum = 0;

             DWORD   dwStartTime = GetTickCount();

 

             for( ULONG ulCycle = 0; ulCycle < MAX_CYCLE; ulCycle++ )

             {

                           for( ULONG ulIndex = 0; ulIndex < MAX_BLOCK; ulIndex ++ )

                           {

                                        ulStartBlockNum = ulIndex - (ulIndex & 3);

 

                                        TRACE(_T("[%04u][%04u] %c\n"), ulIndex, ulStartBlockNum, m_szCheckBlcoks[ulStartBlockNum]);

                           }

             }

 

             TRACE(_T("- [TIME] AND : %u\n"), GetTickCount()-dwStartTime);

}

2.2 테스트

(1) 예상 결과

각 함수의 내부 루프에 존재하는 TRACE에 나타나는 모든 인덱스의 값은 1로 나와야 합니다. 이는 4개의 묶음의 첫번째 인덱스 값이 1 이면 4개의 묶음 내 값이 모두 있다고 가정하여 처리했기 때문입니다.

 

(2) 전제 조건

각 함수의 성능 테스트 시에는 성능 체크에 영향을 미칠 수 있는 함수 안의 TRACE 문을 찍지 않고, 시간 결과를 나타내는 TRACE문만을 출력하도록 합니다.

 

(3) 테스트 시스템 사양

운영체제	Windows XP Professional Version 2002 Service Pack 2
CPU	Intel(R) Pentium(R) 4 3.00Hz
RAM	2 GB

                                              [표 2] 테스트 시스템 사양

3. 결과

다음은 성능 체크 결과로 각각 MAX_CYCLE 100부터 50,000 회까지 증가시키면서 걸린 시간을 테스트한 것입니다.

 

연산/회수	100회	1,000회	5,000회	10,000회	50,000회
MOD(%)	0 ms	15 ms	94 ms	156 ms	797 ms
AND(&)	0 ms	0 ms	15 ms	47 ms	219 ms

[표 3] 테스트 결과

 위의 결과로 보면, 계속해서 MOD(%) 연산을 처리해야 하는 서버의 경우라면, % 연산보다는 AND(&) 연산을 사용하여 처리하는 것이 좀더 좋은 효율을 얻을 수 있을 것이라 판단됩니다.

출처 : 포기를 모르는 남자 블로그