루프 내에서 반복 모듈러스 최적화

Question

이 C 프로그램에이 문장이 있으므로 최적화하고 싶습니다. 최적화에 의해 특히 비트 연산자를 참조하고 싶습니다 (그러나 다른 제안도 괜찮습니다).

uint64_t h_one = hash[0]; 
uint64_t h_two = hash[1]; 
for (int i=0; i<k; ++i) 
{ 
    (uint64_t *) k_hash[i] = (h_one + i * h_two) % size; //suggest some optimization for this line. 
} 

어떤 제안이 큰 도움이 될 것입니다.

편집 : 은 지금부터 size는 int 수 있지만 그것은 문제가되지 않습니다 그리고 우리는 다음 소수로 반올림 할 수 있습니다 (그러나 급속이 개 증가 힘을 더 큰 값 등이 아닌 전력이 될 수 있습니다 많은 메모리 낭비를 초래할 것입니다.)

h_two은 64 비트 int (기본적으로 64 바이트의 척)입니다.

Answer 1

본질적으로 오버 플로우에 따라

k_0 = h_1 mod s 
k_1 = h_1 + h_2 mod s = k_0 + h_2 mod s 
k_2 = h_1 + h_2 + h_2 mod s = k_1 + h_2 mod s 
.. 
k_n = k_(n-1) + h_2 mod s 

을하고있는 (크기가 2**64의 절반보다 작 으면 원본과 다르지 않아야합니다.)이 경우 더 빠르지 만 (병렬 처리는 쉽지 않음)

uint64_t h_one = hash[0]; 
uint64_t h_two = hash[1]; 
k_hash[0] = h_one % size; 
for (int i=1; i<k; ++i) 
{ 
    (uint64_t *) k_hash[i] = (k_hash[i-1] + h_two) % size; 
} 

참고 : 사용하는 최적화 플래그에 따라 컴파일러가 이미이 형식을 사용했을 가능성이 있습니다.

물론 이것은 하나의 곱셈 만 제거했습니다. 당신이 제거 또는 모듈을 줄이려면,이 같은, 당신은 당신이 명시 적으로 %size를 호출해야하는 단계를 미리 결정할 수 h_1%size 뭔가를 h_two%size에 따라 추측과 :

uint64_t h_one = hash[0]%size; 
uint64_t h_two = hash[1]%size; 
k_hash[0] = h_one; 
step = (size-(h_one))/(h_two)-1; 
for (int i=1; i<k; ++i) 
{ 
    (uint64_t *) k_hash[i] = (k_hash[i-1] + h_two); 
    if(i==step) 
    { 
     k_hash[i] %= size; 
    } 
} 

주 나는 확실하지 않다 공식 (테스트하지 않았다), 그것은 더 일반적인 생각이다. 이것은 분기 예측이 얼마나 좋은지 (그리고 예측 실패가 얼마나 큰지)에 달려 있습니다. 또한 단계가 큰 경우에만 도움이 될 수 있습니다.

편집 : 이상 간단한 (그리고 아마도 같은 성능)은 신비로운에 고마워요 :

uint64_t h_one = hash[0]%size; 
uint64_t h_two = hash[1]%size; 
k_hash[0] = h_one; 
for (int i=1; i<k; ++i) 
{ 
    (uint64_t *) k_hash[i] = (k_hash[i-1] + h_two); 
    if(k_hash[i] > size) 
    { 
     k_hash[i] -= size; 
    } 
} 

Answer 2

크기가 다음 비트와 크기를 적용, 2의 거듭 제곱 인 경우는 - 1 최적화 "% 크기"그래서

(uint64_t *)k_hash[i] = (h_one + i * h_two) & (size - 1)