나눗셈은 어렵지만, 꼭 그럴 필요는 없다

2024년 8월 24일 Reddit

개발자는 평소에 숫자를 계속 나누지는 않지만, 해시맵은 종종 어떤 소수에 대한 나머지를 계산해야 한다. 해시맵은 아주 흔하고, 그래서 빠른 나눗셈은 유용하다.

예를 들어, 롤링 해시는 고정된 제수로 u128 % u64를 계산할 수 있다. 그런데 컴파일러는 여기서 그냥 공을 떨어뜨린다:

fn modulo(n: u128) -> u64 {
    (n % 0xffffffffffffffc5) as u64
}

modulo:
    push    rax
    mov     rdx, -59
    xor     ecx, ecx
    call    qword ptr [rip + __umodti3@GOTPCREL]
    pop     rcx
    ret

__umodti3는 범용 긴 나눗셈 구현이라 느리고 보기 안 좋다.

나는 느리고 못생긴 코드의 정반대를 선호한다.

0xffffffffffffffc5는 2^64−59이다. 사실 2^64보다 작은 가장 큰 소수이기도 하지만, 내가 정말로 중요하게 보는 건 2^64에 아주 가깝다는 점이다.

그래서 트릭을 쓸 것이다. n에서 2^64−59의 어떤 배수를 빼자. 그러면 나머지는 변하지 않는다. 구체적으로, n을 n − ⌊n/2^64⌋ ⋅ (2^64−59)로 바꾸고 싶은데, 이는 (n mod 2^64) + ⌊n/2^64⌋ ⋅ 59로 단순화된다.

fn modulo(mut n: u128) -> u64 {
    n = n % (1 << 64) + (n >> 64) * 59;
    (n % 0xffffffffffffffc5) as u64
}

컴퓨터는 2^64로 나누는 일을 늘 한다. 이 연산은 거의 공짜다. 따라서 59로 한 번 곱하는 대가만 치르면, 최대 2^128−1 범위의 n을 (2^64−1)⋅60 범위의 동치 값으로 바꿀 수 있다.

여기에 같은 연산을 두 번 적용하면, 범위가 더 줄어들어서 n이 2^64 + 59^2 − 1 이하가 된다. 이 나머지는 if 한 번으로 계산할 수 있다.

fn modulo(mut n: u128) -> u64 {
    n = n % (1 << 64) + (n >> 64) * 59;
    n = n % (1 << 64) + (n >> 64) * 59;
    if n >= 0xffffffffffffffc5 {
        n -= 0xffffffffffffffc5;
    }
    n as u64
}

modulo:
    mov     rax, rsi
    mov     esi, 59
    mul     rsi
    mov     rcx, rax
    add     rcx, rdi
    adc     rdx, 0
    mov     rax, rdx
    mul     rsi
    add     rax, rcx
    adc     rdx, 0
    xor     ecx, ecx
    mov     rsi, -60
    cmp     rsi, rax
    sbb     rcx, rdx
    lea     rcx, [rax + 59]
    cmovb   rax, rcx
    ret

---

아, 그리고 2^64−59를 하드코딩해야만 하는 것도 아니다. 반복 두 번이면 임의의 제수 d가 d ≥ 2^64 − 2^32 + 1인 경우 모두 충분하다. 더 많은 소수가 필요하다면? 2^32 길이의 구간 안에 소수가 잔뜩 있으니 마음껏 고르면 된다.

더 작은 제수가 필요하다면? 반복을 세 번 하면 제수가 d ≥ 2^64 − 6,981,461,082,631(두 번일 때의 32비트 대비 42.667비트)에 대해 동작하고, 네 번이면 d ≥ 2^64 − 281,472,113,362,716(48비트)까지 된다. 많아 보이는가? 그래도 __umodti3보다는 낫다. 물론 보편적이지는 않지만 중요한 용례들은 여전히 충분히 포괄한다.

그리고 이 방법은 모듈로만이 아니라 나눗셈에도 통한다:

fn divide(mut n: u128) -> u128 {
    let mut quotient = n >> 64;
    n = n % (1 << 64) + (n >> 64) * 59;
    quotient += n >> 64;
    n = n % (1 << 64) + (n >> 64) * 59;
    if n >= 0xffffffffffffffc5 {
        quotient += 1;
    }
    quotient
}

큰 소수가 꼭 필요하지 않다면? 단지 2의 거듭제곱이 아닌 큰 수면 된다면? 이를테면 2^64−1 같은. 다시 시작해 보자:

fn modulo(mut n: u128) -> u64 {
    n = n % (1 << 64) + (n >> 64) * 1;
    (n % u64::MAX as u128) as u64
}

이제 첫 줄은 숫자의 상위 절반과 하위 절반을 그냥 더하는 꼴이다! 여기서부터 최적의 코드를 얻는 건 사실 어렵지 않다. 심지어 컴파일러도 이건 즉시 눈치챈다:

fn modulo(n: u128) -> u64 {
    (n % u64::MAX as u128) as u64
}

modulo:
    add     rdi, rsi
    adc     rdi, 0
    xor     eax, eax
    cmp     rdi, -1
    cmovne  rax, rdi
    ret

특히 롤링 해시는 ‘그’ 나머지 자체가 필요하지 않다. 필요한 건 어떤 수의 ‘표현’이다. 2^64−59로 나누어떨어지는 수가 해시 계산 도중에 0으로 표현되든 2^64−59로 표현되든 상관없다. 맨 마지막에 전부 0으로 매핑되기만 하면 된다.

그래서 코드를 이렇게 바꿀 수 있다:

fn reduce(mut n: u128) -> u64 {
    n = n % (1 << 64) + (n >> 64) * 59;
    n = n % (1 << 64) + (n >> 64) * 59;
    if n >= 0x10000000000000000 /* n >= 0xffffffffffffffc5 */ {
        n -= 0xffffffffffffffc5;
    }
    n as u64
}

…그러면 어셈블리가 조금 더 줄어든다. 이 효과는 2^64−1에서 가장 두드러진다:

fn reduce(mut n: u128) -> u64 {
    n = n % (1 << 64) + (n >> 64);
    if n >= 1 << 64 {
        // 사실은 n - ((1 << 64) - 1)이지만, 그건 최적화가 충분치 않다.
        (n + 1) as u64
    } else {
        n as u64
    }
}

reduce:
    mov     rax, rdi
    add     rax, rsi
    adc     rax, 0
    ret

이 구현들을 비교해 보겠다:

fn modulo_naive(n: u128) -> u64 {
    (n % 0xffffffffffffffc5) as u64
}

fn modulo_optimized(mut n: u128) -> u64 {
    n = n % (1 << 64) + (n >> 64) * 59;
    n = n % (1 << 64) + (n >> 64) * 59;
    if n >= 0xffffffffffffffc5 {
        n -= 0xffffffffffffffc5;
    }
    n as u64
}

fn reduce(mut n: u128) -> u64 {
    n = n % (1 << 64) + (n >> 64) * 59;
    n = n % (1 << 64) + (n >> 64) * 59;
    if n >= 0x10000000000000000 {
        n -= 0xffffffffffffffc5;
    }
    n as u64
}

fn divide_naive(n: u128) -> u128 {
    n / 0xffffffffffffffc5
}

fn divide_optimized(mut n: u128) -> u128 {
    let mut quotient = n >> 64;
    n = n % (1 << 64) + (n >> 64) * 59;
    quotient += n >> 64;
    n = n % (1 << 64) + (n >> 64) * 59;
    if n >= 0xffffffffffffffc5 {
        quotient += 1;
    }
    quotient
}

strength_reduce 크레이트와도 비교해 보겠다. 이는 컴파일러가 u64 % u32에서 수행하는 것과 같은 최적화를 흉내 낸다. 컴파일은 -C target-cpu=native로 했다.

솔직히, 이것을 롤링 해시에 바로 적용하면 즉각적인 이점이 있는 건 아니다. reduce가 여전히 u64 % u32 두 번보다 약간 느리다. 그러니 64비트 소수 하나 대신 32비트 소수 두 개로 해시를 계산해도 충분하다면 그게 낫다. 그래도 최상의 충돌 확률 보장을 가능한 한 빠르게 얻고 싶다면, 이 방법이 정답이다.

이 트릭은 32비트 플랫폼에서의 u64 % u32 계산에도 적용 가능하다. 어쩌면 이쪽이 좀 더 흔한 용례일지도 모른다.

마지막으로, 이것은 컴파일러가 수행할 수 있는 공짜(조건부지만) 최적화이기도 하다. 내가 실무 적용에 밝지 않아서 몰랐을 수도 있다. 어쨌든, 이제 이 글을 본 이상 다른 곳에도 써먹을 수 있는 트릭이 하나 더 생겼다.