[c] % 연산자보다 빠른 분할 성 테스트?

Program / 글쓴이

컴퓨터에서 궁금한 것을 발견했습니다. * 필기 분할 성 테스트는 %작업자 보다 훨씬 빠릅니다 . 최소한의 예를 고려하십시오.

* AMD Ryzen Threadripper 2990WX, GCC 9.2.0 

static int divisible_ui_p(unsigned int m, unsigned int a)
{
    if (m <= a) {
        if (m == a) {
            return 1;
        }

        return 0;
    }

    m += a;

    m >>= __builtin_ctz(m);

    return divisible_ui_p(m, a);
}

이 예는 홀수 a및 로 제한됩니다 m > 0. 그러나, 그것은 쉽게 모든 일반화 될 수 a와 m. 이 코드는 나누기를 일련의 추가로 변환합니다.

이제 다음으로 컴파일 된 테스트 프로그램을 고려하십시오 -std=c99 -march=native -O3.

    for (unsigned int a = 1; a < 100000; a += 2) {
        for (unsigned int m = 1; m < 100000; m += 1) {
#if 1
            volatile int r = divisible_ui_p(m, a);
#else
            volatile int r = (m % a == 0);
#endif
        }
    }

… 내 컴퓨터의 결과 :

| implementation     | time [secs] |
|--------------------|-------------|
| divisible_ui_p     |    8.52user |
| builtin % operator |   17.61user |

따라서 2 배 이상 빠릅니다.

질문 : 코드가 컴퓨터에서 어떻게 동작하는지 알려줄 수 있습니까? GCC에서 최적화 기회를 놓쳤습니까? 이 시험을 더 빨리 할 수 ​​있습니까?

업데이트 :
요청에 따라 최소한의 재현 가능한 예는 다음과 같습니다.

#include <assert.h>

static int divisible_ui_p(unsigned int m, unsigned int a)
{
    if (m <= a) {
        if (m == a) {
            return 1;
        }

        return 0;
    }

    m += a;

    m >>= __builtin_ctz(m);

    return divisible_ui_p(m, a);
}

int main()
{
    for (unsigned int a = 1; a < 100000; a += 2) {
        for (unsigned int m = 1; m < 100000; m += 1) {
            assert(divisible_ui_p(m, a) == (m % a == 0));
#if 1
            volatile int r = divisible_ui_p(m, a);
#else
            volatile int r = (m % a == 0);
#endif
        }
    }

    return 0;
}

gcc -std=c99 -march=native -O3 -DNDEBUGAMD Ryzen Threadripper 2990WX에서 컴파일

gcc --version
gcc (Gentoo 9.2.0-r2 p3) 9.2.0

UPDATE2 : 같이, 어떤 처리 할 수있는 버전 요청 a과 m(테스트 입력 정수로 두 배 긴 정수 유형으로 구현 될 필요가 있습니다 당신은 또한 오버 플로우 정수 피하려면를)

int divisible_ui_p(unsigned int m, unsigned int a)
{
#if 1
    /* handles even a */
    int alpha = __builtin_ctz(a);

    if (alpha) {
        if (__builtin_ctz(m) < alpha) {
            return 0;
        }

        a >>= alpha;
    }
#endif

    while (m > a) {
        m += a;
        m >>= __builtin_ctz(m);
    }

    if (m == a) {
        return 1;
    }

#if 1
    /* ensures that 0 is divisible by anything */
    if (m == 0) {
        return 1;
    }
#endif

    return 0;
}

답변

고가의 작업을 일련의 저렴한 작업으로 교체하는 것을 힘 감소라고합니다.

많은 CPU의 mod 명령어는 역사적으로 몇 가지 일반적인 벤치 마크에서 테스트되지 않았기 때문에 디자이너가 다른 명령어를 대신 최적화했기 때문에 속도가 느립니다. 이 알고리즘은 많은 반복을 수행해야하는 경우 성능이 저하됩니다.% 수행해야하는 클럭 사이클이 2 개만 필요한 CPU에서는 성능이 향상됩니다.

마지막으로, 특정 상수로 나눈 나머지를 가져 오는 많은 지름길이 있음에 유의하십시오. (컴파일러가 일반적으로이를 처리하지만)

답변

나는 내 질문에 스스로 대답 할 것이다. 내가 지점 예측의 희생자가 된 것 같습니다. 피연산자의 상호 크기는 중요하지 않으며 순서 만 중요합니다.

다음 구현을 고려하십시오

int divisible_ui_p(unsigned int m, unsigned int a)
{
    while (m > a) {
        m += a;
        m >>= __builtin_ctz(m);
    }

    if (m == a) {
        return 1;
    }

    return 0;
}

그리고 배열

unsigned int A[100000/2];
unsigned int M[100000-1];

for (unsigned int a = 1; a < 100000; a += 2) {
    A[a/2] = a;
}
for (unsigned int m = 1; m < 100000; m += 1) {
    M[m-1] = m;
}

셔플 기능을 사용하여 셔플 되지 않습니다 .

셔플 링 없이도 결과는 여전히

| implementation     | time [secs] |
|--------------------|-------------|
| divisible_ui_p     |    8.56user |
| builtin % operator |   17.59user |

그러나 일단 이러한 배열을 섞으면 결과가 다릅니다.

| implementation     | time [secs] |
|--------------------|-------------|
| divisible_ui_p     |   31.34user |
| builtin % operator |   17.53user |

답변