모듈로 최적화

Question

커다란 배열에 대해 광범위한 스와핑 연산을 수행하는 C 프로그램이 있습니다. 그것은 단단한 루프에서 모듈러스 연산을합니다. 실제로 [-N -N [N의 제곱의 힘을 가진 정수가 있고 [0, N [. -4 => 0, -3 => 1, -2 => (2) -1 => 3, 0 => 0, ..., 3 => 3

: N = 4

예

처음에는 아래의 버전 1을 시도했지만 조건부 표현이 있어도 버전 2가 실제로 더 빠르다는 사실에 놀랐습니다.

이 특수한 경우 버전 2가 버전 1보다 빠른 이유를 설명 할 수 있습니까?

버전 1 :

#define N (1<<(3*5)) 

inline int modBitAnd(int x) 
{ 
    return (x & (N-1)); 
} 

런타임 (전체 프로그램) 17.1 초

버전 2

inline int modNeg1(int x) 
{ 
    return (x < 0 ? x + N : x); 
} 

런타임 : 전체 14.6 초 (프로그램)

프로그램은 GCC 4.8.2에서 컴파일됩니다. -std = c99 -O3.

편집 :

int en(uint16_t* p, uint16_t i, uint16_t v) 
{ 
    uint16_t n1 = p[modNeg1((int)i - 1)]; 
    uint16_t n2 = p[modBitAnd((int)i + 1)]; 
    uint16_t n3 = p[modNeg1((int)i - C_WIDTH)]; 
    uint16_t n4 = p[modBitAnd((int)i + C_WIDTH)]; 
    return d(n1,v) + d(n2,v) + d(n3,v) + d(n4,v); 
} 

void arrange(uint16_t* p) 
{ 
    for(size_t i=0; i<10000000; i++) { 
     uint16_t ia = random(); // random integer [0|2^15[ 
     uint16_t va = p[ia]; 
     uint16_t ib = random(); // random integer [0|2^15[ 
     uint16_t vb = p[ib]; 
     if(en(p,ia,vb) + en(p,ib,va) < en(p,ia,va) + en(p,ib,vb)) { 
      p[ia] = vb; 
      p[ib] = va; 
     } 
    } 
} 

int d(uint16_t a, uint16_t b) 예컨대 거리 함수이다 : 여기

내 프로그램의 메인 루프 abs((int)a-(int)b).

이것은 p 초기화 방법은 다음과 같습니다

uint16_t* p = malloc(sizeof(uint16_t)*N); 
for(unsigned i=0; i<N; i++) *p++ = i; 

먼저 나는 사방 modBitAnd을 사용하지만, modNeg1이 acutally 빠르게 사용할 수 있습니다 두 경우에 대한 것을 알아 냈다.

Answer 1

처음으로 take a few stackshots 어디로 시간이 실제로 가고 있는지 알아보십시오. mod 함수는 일부 샘플을 채우지 만 random에 두 번의 호출과 더불어 적절한 양의 배열 인덱싱을 제공합니다. 또한 동일한 인수를 사용하여 en을 네 번 호출 한 것처럼 보이므로 모듈성이 mod 함수에 대한 호출을 반복하도록 유도 할 수 있습니다.