가장 빠른 FizzBuzz는 무엇입니까?

This post is also summarized as a video.

나는 a video by Nick White을 봤는데, 낯선 사람들이 간단한 코딩 비디오를 풀 수 있다면 100달러를 주었고 그 중 하나는 FizzBuzz였습니다.

FizzBuzz를 볼 때마다 저는 항상 가장 빠른 것이 무엇인지 알고 싶습니다. 일반적으로 사람들은 인쇄 또는 순차적 FizzBuzz 계산을 최적화하지만 임의의 숫자에 대해 인쇄할 단어를 찾는 가장 빠른 방법은 무엇입니까?

내 테스트에서는 실제로 콘솔에 인쇄하는 것이 느리기 때문에 각 함수가 fizzbuzzality에 따라 숫자를 반환해야 한다고 결정했습니다. 0은 숫자 자체가 인쇄되어야 함을 의미하고, 1은 Fizz를, 2는 Buzz를, 3은 FizzBuzz를 의미합니다.

이를 테스트하기 위해 QuickBench 에서 여러 가지 방법을 설정했습니다. 벤치마크 루프 내부에 증가하는 카운터를 사용하여 함수가 최적화되는 것을 방지했습니다.
args -std=++2a -O3 와 함께 Clang 11.0.0을 사용하여 컴파일합니다.

먼저 간단한 FizzBuzz 구현을 시도해 보겠습니다.

if(n % 15 == 0){
    return 3;
}
if(n % 3 == 0){
    return 1;
}
if(n % 5 == 0){
    return 2;
}
return 0;

QuickBench에서 이것을 실행하면 ~5.41 cpu_time을 얻을 수 있으며, 대부분은 3개의 modulos/if 테스트에서 나올 것입니다. 분기는 매우 느리기로 악명이 높지만 좋은 컴파일러라면 대신 if 테스트를 조건부 연산자로 대체할 수 있어야 합니다.

즉, 모듈로/if 테스트가 두 개뿐인 거의 동일한 코드를 가질 수 있습니다.

int v = 0;

if(n % 3 == 0){
    v += 1;
}

if(n % 5 == 0){
    v += 2;
}

return v;

이것은 ~4.21 cpu_time에서만 실행되며 분명히 조건부 추가 작업을 사용합니다. 간혹 이전 기능의 속도를 높이는 마법의 부작용이 있지만 나중에 재현하지 못했습니다.

단 두 개의 모듈로와 함께 또 다른 간단한 FizzBuzz 구현이 있습니다.

if(n % 3 == 0){
    if(n % 5 == 0){
        return 3;
    }
    return 1;
}
if(n % 5 == 0){
    return 2;
}
return 0;

이것은 중첩된 if 문을 사용하지만 ~4.20 cpu_time에서만 실행됩니다. 즉, 컴파일러가 이를 아주 잘 최적화합니다.

그러나 두 개의 모듈로 연산만 얻는 더 많은 방법이 있습니다. 예를 들어:

bool a = (n % 3) == 0;
bool b = (n % 5) == 0;

if(a&&b) return 3;
if(b) return 2;
if(a) return 1;
return 0;

그러나 이것은 ~5.00 cpu_time에서 실행되며 연결된 if를 사용하는 첫 번째 함수보다 약간 빠릅니다. 여기에 제대로 최적화되지 않은 분기가 있다고 생각합니다.

하지만 우리는 더 잘할 수 있습니다!

bool a = (n % 3) == 0;
bool b = (n % 5) == 0;

return b*2+a;

이것은 지금까지 가장 빠른 ~4.17 cpu_time으로 실행됩니다! 이것은 false가 0이고 true가 1인 경우에만 작동하므로 ==가 다르게 작동하면 큰 문제가 됩니다.

모듈로 연산의 두 번째 피연산자는 항상 알려진 컴파일 타임이기 때문에 모듈로 연산자가 적다고 해서 반드시 속도가 크게 향상되는 것은 아닙니다. 즉, 우리는 얻을 수 있는 모든 속도 향상을 원하므로:

int a = n%15;
if(a==0) return 3;
if(a==5||a==10) return 2;
if(a==3||a==6||a==9||a==12) return 1;
return 0;

이것은 ~4.68 cpu_time으로 우리의 다른 분기 방법보다 빠르지만 나머지를 능가할 만큼 빠르지는 않습니다.

가지가 없게 만들기:

int a = n%15;
int fiv = a==0 || a==5 || a==10;
int thr = a==0 || a==3 || a==6 ||a==9 || a==12;

return fiv*2+thr;

~5.59 cpu_time으로 실제로 더 느립니다. 나는 이것이 a==0을 한 번이 아니라 두 번 수행해야 하기 때문이라고 가정합니다.

또한 ==를 많이 줄일 수 있습니다.

int a = n%15;
int fiv = (a-5)*(a-10)*a == 0;
int thr = (a-3)*(a-6)*(a-9)*(a-12)*a == 0;

return fiv*2+thr;

그러나 이것은 ~9.00 cpu_time에 앉아 훨씬 더 느립니다.

이제 우리는 이러한 테스트가 얼마나 빨리 진행될 수 있는지 꽤 명확하게 이해했지만 마지막으로 시도하지 않은 것이 있습니다.

static int answers[] = {3, 0, 0, 1, 0, 2, 1, 0, 0, 1, 2, 0, 1, 0, 0};
static int FizzBuzzArray(int n){
    return answers[n % 15];
}

그리고 이것은 ~2.23 cpu_time에 앉아 있는 진정한 게임 체인저입니다. 시간 트레이드오프에 대한 메모리는 거의 항상 가치가 있으므로 가능하면 기본적으로 캐싱을 사용합니다.

마지막으로 모든 테스트에 대한 그래프는 다음과 같습니다. 먼저 -O3을 사용한 다음 __attribute__((noinline)) 로 표시된 모든 기능을 사용하고 마지막으로 전혀 최적화하지 않았습니다.

내가 놓친 FizzBuzz가 있었나요? 아니면 다른 실수? 자유롭게 의견을 말하고 수정하십시오. 실제로 어떤 기능이 제대로 작동하는지 확인하지 않고 그냥 작동한다고 가정합니다.