빠른 해시 함수 JS로 포팅하기

https://github.com/cgiosy/xxh32

JS 최적화 상식

정수 vs. 실수

JS는 기본적으로는 정수와 실수 구분이 없다. 사실상 모든 연산이 64비트 실수형 위에서 돌아간다고 보면 편하다.

그래도 비트 연산을 사용하면 32비트 정수라도 쓸 수 있게끔 되어 있다. 아래에서 두 번째가 첫 번째보다 두 배 가까이 빠르다.

const N = 16384;
const arr = new Uint32Array(N);
for (let i = 0; i < N; i += 1) arr[i] = i;

let s = 0;
// Case #1
for (let i = 0; i < N; i += 1) s += arr[i] + 1;
// Case #2
for (let i = 0; i < N; i = i + 1 | 0) s = s + (arr[i] + 1 | 0) | 0;

따라서, 성능이 중요한 부분엔 | 0 같은 비트 연산을 덕지덕지 발라가며 짜야 한다. ReScript같은 일부 파생 언어가 이런 최적화를 지원은 하는데, 완벽하진 않다.

signed vs. unsigned

또한 대부분의 비트 연산은 반환 값이 signed이며, 2의 보수 특성 상 unsigned와 동일한 값인 게 보장된다. 단, 우측 시프트 >> (signed) / >>> (unsigned)만 빼고. >>는 시프트 후 남는 상위 비트를 sign bit로 채우고, >>>는 0으로 채운다. 참고로 unsigned보다 signed 연산이 빠른데, 왠진 모르겠다.

기본 비트 연산을 제외하고 자주 사용되는 연산으론 Math.imul이 있는데, 32비트 정수 두 개를 곱했을 때의 하위 32비트를 반환한다. 마찬가지로 입력에 signed를 넣든 unsigned를 넣든 둘 다 넣든 결과값은 signed이다. 하위 32비트라서 unsigned와 동일한 값인 게 보장된다. 참고

해시 종류 선택

내가 생각한 요구사항을 중요한 순서대로 나열했다.

1. 32비트 연산만 사용
2. 작은 코드 크기
3. 최대한 빠른 속도
4. 적당한 품질

1이 가장 중요한 이유는 물론 JS는 32비트 정수밖에 다루지 못하기 때문이다. 64비트 연산을 직접 시뮬레이션하는 식으로 구현은 가능하지만, 그 경우 2와 3을 어느정도 희생해야 했다. 하여튼 AES-NI같은 명령어셋은 커녕 32비트 곱셈 결과의 상위 32비트를 가져오는 연산(umulh)조차 JS에는 없기에, 쓸만한 해시 함수의 종류가 훨씬 줄어들었다.

2가 3과 4보다 높은 이유는, 유명 프론트 라이브러리에서 h = h * 33 ^ s[i]같은 구석기시대에나 나올 법한 해시 함수를 쓰는 충격적인 광경을 목도했기 때문이다. 품질이 낮고, 속도가 느려도 이쪽 생태계는 그냥 코드가 짧고 간단한 게 최고임을 깨달았다. 아무리 그래도 저건 좀 심한 것 같아서 이렇게 따로 해시를 짜게 되긴 했지만...

우선은 주로 SMHasher #1 #2 #3와 More Hash Function Tests 블로그를 참고해서, 최종적으로 xxHash32를 선택했다. 고려했던 후보들은 다음과 같다.

1. wyhash32는 꽤 괜찮아 보이고 코드가 간단하지만, _wymix32에서 64비트 연산을 요구해서 32비트로 시뮬레이션을 해야 하나 고민하다가 결국 보내주었다.
2. Farmhash32는 꽤 괜찮아 보였으나, SIMD가 없으면 성능이 떡락한다는 걸 보고 버렸다.
3. Cityhash는 bswap이나 permute 등 JS에서 지원하지 않는 연산을 많이 사용해서 걸러졌다.
4. aHash는 메인 알고리즘이 AES-NI 명령어셋이 필요하고, fallback 알고리즘 역시 64비트 연산이 필요해 JS로 포팅이 불가능했다. 이외에 성능이 과장되었다는 주장이 존재하며 실제로 M1 맥북에서 테스트 시 문자열이 256바이트 이상으로 큰 경우에는 XXH3에 비해 느렸고, 작은 경우에도 큰 차이를 보이진 못했다. (내장 벤치마크가 twox-hash 기준이라 xxh3로 바꾸고 테스트했다.)
5. nmhash32x는 꽤 괜찮아 보이는데 당시 찾아볼 때 눈에 안 띄어서 지나쳐버렸다(...) 나중에 한 번 짜볼 듯.
6. komihash, waterhash, mx3, pengyhash 등 코드도 간단하고 그럭저럭 빠른 함수들이 많았지만 전부 64비트 대상이었다. 근데 사실 64비트면 XXH3나 wyhash 쓰지 저걸 쓸 이유가 없다.

결국 선택지가 없어져서, SMHasher 기준 품질이 POOR인 게 좀 찝찝했지만 32비트 연산만 사용하고 코드도 작고 꽤 빠른 xxHash32를 선택했다. nmhash32x는... ㅠㅠ

구현

C++ 구현을 보고 열심히 짰다. 코드가 좀 정리가 안 되어있고 각종 최적화나 매크로 분기가 눈을 어지럽히는데, 딱 기본적인 부분만 보면 생각보다 짧다.

XXH_FORCE_INLINE XXH_PUREF xxh_u32
XXH32_endian_align(const xxh_u8* input, size_t len, xxh_u32 seed, XXH_alignment align)
{
    xxh_u32 h32;

    if (input==NULL) XXH_ASSERT(len == 0);

    if (len>=16) {
        const xxh_u8* const bEnd = input + len;
        const xxh_u8* const limit = bEnd - 15;
        xxh_u32 v1 = seed + XXH_PRIME32_1 + XXH_PRIME32_2;
        xxh_u32 v2 = seed + XXH_PRIME32_2;
        xxh_u32 v3 = seed + 0;
        xxh_u32 v4 = seed - XXH_PRIME32_1;

        do {
            v1 = XXH32_round(v1, XXH_get32bits(input)); input += 4;
            v2 = XXH32_round(v2, XXH_get32bits(input)); input += 4;
            v3 = XXH32_round(v3, XXH_get32bits(input)); input += 4;
            v4 = XXH32_round(v4, XXH_get32bits(input)); input += 4;
        } while (input < limit);

        h32 = XXH_rotl32(v1, 1)  + XXH_rotl32(v2, 7)
            + XXH_rotl32(v3, 12) + XXH_rotl32(v4, 18);
    } else {
        h32  = seed + XXH_PRIME32_5;
    }

    h32 += (xxh_u32)len;

    return XXH32_finalize(h32, input, len&15, align);
}

대략 이정도. 그래서 구현은 생각보다 어렵지 않았다.

const getUint32 = (arr, i) => (
    arr[i] | arr[i + 1 | 0] << 8 | arr[i + 2 | 0] << 16 | arr[i + 3 | 0] << 24
);

const rotl32 = (x, r) => (x << r) | (x >>> 32 - r);
const round1 = (v, x) => {
    v = v + Math.imul(x, 0x85EBCA77) | 0;
    return Math.imul(v << 13 | v >>> 19, 0x9E3779B1);
};
const round2 = (v, x) => {
    v = v + Math.imul(x, 0xC2B2AE3D) | 0;
    return Math.imul(v << 17 | v >>> 15, 0x27D4EB2F);
};
const round3 = (v, x) => {
    v = v + Math.imul(x, 0x165667B1) | 0;
    return Math.imul(v << 11 | v >>> 21, 0x9E3779B1);
};

const xxh32 = (buf, seed = 0) => {
    seed |= 0;
    const len = buf.length | 0;
    let i = 0;
    let h = (seed + len | 0) + 0x165667B1 | 0;

    if (len < 16) {
        for (; (i + 3 | 0) < len; i = i + 4 | 0)
            h = round2(h, getUint32(buf, i));
    } else {
        let v0 = seed + 0x24234428 | 0;
        let v1 = seed + 0x85EBCA77 | 0;
        let v2 = seed;
        let v3 = seed - 0x9E3779B1 | 0;

        if (len < 256) {
            for (; (i + 15 | 0) < len; i = i + 16 | 0) {
                v0 = round1(v0, getUint32(buf, i + 0 | 0));
                v1 = round1(v1, getUint32(buf, i + 4 | 0));
                v2 = round1(v2, getUint32(buf, i + 8 | 0));
                v3 = round1(v3, getUint32(buf, i + 12 | 0));
            }

            h = (((rotl32(v0, 1) + rotl32(v1, 7) | 0) + rotl32(v2, 12) | 0) + rotl32(v3, 18) | 0) + len | 0;
            for (; (i + 3 | 0) < len; i = i + 4 | 0)
                h = round2(h, getUint32(buf, i));
        } else {
            const view = new DataView(buf.buffer);
            for (; (i + 15 | 0) < len; i = i + 16 | 0) {
                v0 = round1(v0, view.getUint32(i + 0 | 0, true));
                v1 = round1(v1, view.getUint32(i + 4 | 0, true));
                v2 = round1(v2, view.getUint32(i + 8 | 0, true));
                v3 = round1(v3, view.getUint32(i + 12 | 0, true));
            }

            h = (((rotl32(v0, 1) + rotl32(v1, 7) | 0) + rotl32(v2, 12) | 0) + rotl32(v3, 18) | 0) + len | 0;
            for (; (i + 3 | 0) < len; i = i + 4 | 0)
                h = round2(h, view.getUint32(i, true));
        }
    }

    for (; i < len; i = i + 1 | 0)
        h = round3(h, buf[i]);
    h = Math.imul(h ^ h >>> 15, 0x85EBCA77);
    h = Math.imul(h ^ h >>> 13, 0xC2B2AE3D);
    return (h ^ h >>> 16) >>> 0;
};

구현 포인트

아마 위 코드를 본 순간 'rotl32 함수 멀쩡히 만들어 놓고 왜 round에선 안 쓰냐'는 감상이 들지 않았을까 싶다. 이유는 V8의 특이한 인라이닝 휴리스틱으로 인해, 동일 함수를 여러 함수에서 쓰면서 콜스택 깊이가 5를 넘는 경우 인라이닝이 제대로 안 될 수 있다. 후자의 조건은 현실에선 만족하기 쉬운데, 벤치마크 환경에선 잘 만족을 안 해서 7배씩 느려졌다 빨라졌다 하는 걸 보고 한참 헤맸다...

그 외에 따로 신경쓴 구현 포인트는 다음과 같다.

• 편집증적인 | 0 사용: 솔직히 여긴 안 붙여도 되지 않을까? 하고 뗀 순간 약간씩이지만 확실하게 성능이 떨어졌다.
• 길이가 256 미만일 때를 분리: new DataView()의 비용이 생각보다 커서, 저 크기보다 작을 땐 getUint32가 좀 더 느려지는 걸 감수하고 DataView를 생성 안 하는 게 나았다.
  • new TypedArray(otherTyped.buffer, offset)도 시도해 보았는데, 엄청나게 느려졌었다.(offset이 0이거나 4의 배수여도 관계없이)
• 함수를 반환하는 함수 미사용: 일반 함수 선언까지는 어느정도 인라이닝이 되는데, 코드 중복을 없애려고 추상화를 시도한 순간 성능이 떨어졌다. 위에서 말한 인라이닝 문제와 어느정도 중복.

비교

내 코드와 웹어셈블리 해시 라이브러리 중 가장 빠른 것으로 보이는 hash-wasm을 M1 맥북에서 벤치마크했다. 또한 해당 라이브러리에서 xxHash32 파트의 번들 크기는 gzip 압축 시 3kb, 내 코드는 0.5kb다.

# Throughput - 16 bytes
xxh32.js: 503.013 MB/s
hash-wasm.xxhash32: 40.957 MB/s
hash-wasm.xxhash64: 20.713 MB/s
hash-wasm.xxhash3: 19.955 MB/s
hash-wasm.crc32: 36.426 MB/s
hash-wasm.blake3: 15.988 MB/s
hash-wasm.sha256: 14.345 MB/s
hash-wasm.sha512: 9.491 MB/s
hash-wasm.sha3: 9.532 MB/s

# Throughput - 256 bytes
xxh32.js: 1522.584 MB/s
hash-wasm.xxhash32: 640.131 MB/s
hash-wasm.xxhash64: 340.317 MB/s
hash-wasm.xxhash3: 316.822 MB/s
hash-wasm.crc32: 490.829 MB/s
hash-wasm.blake3: 211.076 MB/s
hash-wasm.sha256: 138.229 MB/s
hash-wasm.sha512: 118.164 MB/s
hash-wasm.sha3: 107.931 MB/s

# Throughput - 4096 bytes
xxh32.js: 5593.867 MB/s
hash-wasm.xxhash32: 4032.488 MB/s
hash-wasm.xxhash64: 3859.344 MB/s
hash-wasm.xxhash3: 3155.710 MB/s
hash-wasm.crc32: 1571.842 MB/s
hash-wasm.blake3: 688.633 MB/s
hash-wasm.sha256: 301.666 MB/s
hash-wasm.sha512: 432.367 MB/s
hash-wasm.sha3: 286.119 MB/s

# Throughput - 65536 bytes
xxh32.js: 6725.478 MB/s
hash-wasm.xxhash32: 5521.466 MB/s
hash-wasm.xxhash64: 9151.555 MB/s
hash-wasm.xxhash3: 6397.267 MB/s
hash-wasm.crc32: 1779.452 MB/s
hash-wasm.blake3: 760.854 MB/s
hash-wasm.sha256: 320.870 MB/s
hash-wasm.sha512: 506.873 MB/s
hash-wasm.sha3: 309.703 MB/s

작은 크기에서 속도 차이가 크게 나는 건 WASM과 JS 간 데이터 전달로 인한 병목으로 추측되고, 입력이 꽤 큰 경우에는 그래도 64비트 연산을 사용 가능한 hash-wasm.xxhash64이 크게 빨라진다.