자동화된 정수 해시 함수 탐색 기술

 (github.com/skeeto)
3P by GN⁺ | ★ favorite | 댓글 1개
  • Hash Function Prospector는 정수 해시 함수를 무작위로 대량 생성하고 JIT 컴파일해 avalanche 동작을 평가한 뒤, 현재 최적 함수를 C 문법으로 출력하는 도구임
  • 평가는 단일 입력 비트를 뒤집었을 때 평균적으로 고정된 채 남는 출력 비트 수인 avalanche score를 사용하며, 낮을수록 좋고 이상적인 값은 0임
  • 탐색 대상은 32비트와 64비트 정수 해시 함수이며, JIT 컴파일러 때문에 도구 실행은 x86-64만 지원하지만 발견된 함수는 다른 환경에서도 사용할 수 있음
  • 발견된 주요 함수들은 xorshift-multiply-xorshift 구성을 쓰며, 2라운드 lowbias32는 MurmurHash3 32-bit finalizer보다 작은 차이로 낮은 bias를 보이고 3라운드 triple32는 이론적 bias 한계에 가까움
  • 정확한 bias 측정은 32비트 함수에 대해 -E와 -e로 수행할 수 있고, 16비트 해시는 별도 도구 hp16이 담당하며 C 정수 승격 규칙에 주의해야 함

Hash Function Prospector의 역할

  • Hash Function Prospector는 자동화된 정수 해시 함수 발견 도구임
  • 무작위로 수십억 개의 정수 해시 함수를 생성하고, 이를 JIT 컴파일한 뒤 avalanche 동작을 평가함
  • 생성된 함수 중 현재 가장 좋은 함수는 C 문법으로 출력됨
  • 관련 글로 Prospecting for Hash Functions가 연결되어 있음

평가 기준과 지원 범위

  • avalanche score는 입력 비트 하나를 뒤집었을 때 평균적으로 고정된 채 남는 출력 비트 수임
    • 점수가 낮을수록 좋음
    • 이상적으로는 모든 출력 비트가 50% 확률로 뒤집혀 score가 0이 됨
  • Prospector는 32비트와 64비트 정수 해시 함수를 생성할 수 있음
  • 전체 옵션은 -h 사용법에서 확인하도록 되어 있음
  • JIT 컴파일러 때문에 도구 자체는 x86-64만 지원함
    • 다만 발견된 해시 함수는 어디서든 사용할 수 있음

탐색에 쓰는 가역 연산

  • 생성기는 선택된 9가지 가역 연산에서 함수를 무작위 구성함
  • 연산 목록은 다음과 같음
    • x = ~x
    • x ^= constant
    • x *= constant | 1
    • x += constant
    • x ^= x >> constant
    • x ^= x << constant
    • x += x << constant
    • x -= x << constant
    • x <<<= constant
    • x = bswap(x)
  • 기술적으로 x = ~x는 x ^= constant로 표현 가능하지만, 해당 XOR 상수를 생성기가 우연히 고를 가능성이 낮아 별도 연산으로 취급함

발견된 32비트 해시 함수

  • 2라운드 함수

    • 유용한 발견 함수군 중 하나는 2라운드 xorshift-multiply-xorshift 구성임
    • TheIronBorn은 조합 최적화를 사용해 이 구성의 알려진 최적 파라미터를 찾았고, 결과는 [16 21f0aaad 15 d35a2d97 15] = 0.10760229515479501임
    • lowbias32는 32비트 2라운드 순열로, bias가 낮고 MurmurHash3 32-bit finalizer보다 아주 작은 차이로 더 낮은 bias를 보임
    • lowbias32의 exact bias는 0.17353355999581582
    • 구성은 Prospector가 발견했고, 파라미터는 hill climbing과 유전 알고리듬으로 조정됨
    • 역함수 lowbias32_r도 제공됨
    • prospector32는 Prospector만 사용해 발견된 함수임
    • exact bias는 0.34968228323361017
    • 앞의 lowbias32보다 bias가 더 큼
    • 대체 곱셈 상수를 무작위 탐색하려면 다음처럼 패턴을 지정함
    • ./prospector -p xorr:15,mul,xorr:12,mul,xorr:15

  • 3라운드 함수

    • 같은 구성에 multiply-xorshift 라운드를 하나 더 추가하면 신중히 고른 파라미터로 이론적 bias 한계에 도달할 수 있음
    • triple32는 exact bias가 0.020888578919738908임
    • README는 이를 모든 32비트 정수의 무작위 순열 같은 완전한 PRF와 구분할 수 없다고 설명함
    • 역함수 triple32_r도 제공됨
    • 3라운드 상수 목록에는 0.020888578919738908부터 약 0.022984943828687553까지 낮은 bias 결과들이 포함됨
    • triple32 앞에 증가 연산을 붙인 triple32inc는 hash(0) = 0 문제를 깨고 bias도 조금 더 낮춤
    • exact bias는 0.020829410544597495
    • 역함수 triple32inc_r는 마지막에 x--를 수행함

exact bias 측정

  • -E 모드는 주어진 해시 함수의 bias를 평가함
  • 기본적으로 Prospector는 bias를 빠르게 평가하기 위해 추정치를 사용함
    • 이 추정은 비결정적이며 결과에 노이즈가 많음
  • 완전 탐색으로 exact bias를 측정하려면 -e 옵션을 사용함
  • 검사할 함수는 두 방식으로 정의할 수 있음
    • -p와 패턴으로 정의
    • -l과 hash() 함수를 포함한 공유 라이브러리로 정의
  • 공유 라이브러리 방식은 Prospector의 제한된 함수 표현으로 나타낼 수 없는 해시 함수도 테스트할 수 있게 함
  • 기본 입력은 32비트 해시 함수로 취급됨
  • -8 스위치는 64비트 함수를 추정 방식으로 테스트함
    • 64비트 해시 함수는 시간이 너무 오래 걸려 exact exhaustive test가 없음

16비트 해시용 hp16

  • 16비트 해시는 제약이 달라 별도 도구 hp16 이 제공됨
  • hp16은 32비트·64비트 Prospector와 달리 완전히 이식 가능하며 거의 모든 시스템에서 실행될 수 있음
  • hp16은 128KiB s-box 생성과 평가도 가능함
  • 16비트 해시가 빠른 곱셈 명령이 없는 기계에서 필요할 수 있기 때문에, 탐색 중 특정 연산을 생략하는 옵션도 있음
    • -m
    • -r

16비트 결과와 C 구현 주의점

  • 현재까지의 16비트 결과 예시는 다음과 같음
    • 2라운드 xorshift-multiply hash16_xm2: bias 0.0085905051336723701
    • 3라운드 xorshift-multiply hash16_xm3: bias 0.0045976709018820602
    • 곱셈 없는 hash16_s6: bias 0.023840118344741465
  • 곱셈 없는 hash16_s6는 특정 xorshift-multiply 형태와 동일하다고 제시됨
  • hp16 -Xn3로 짧게 탐색한 좋은 3라운드 xorshift 해시는 hp16 -S의 좋은 s-box에 가까운 근사임
  • 16비트 연산을 C로 작성할 때는 정수 승격 규칙에 주의해야 함
    • 예를 들어 32비트 구현에서는 unsigned 16비트 피연산자가 signed 32비트 정수로 승격될 수 있음
    • 이 경우 특정 상황에서 잘못된 결과가 나올 수 있음
    • 이 프로그램이 출력하는 C 코드는 필요한 곳에서 16비트 연산을 unsigned int로 승격하도록 주의함

함께 보면 좋은 글 β

GN⁺   [-]
Hacker News 의견들

  • 개인적으로는 모르지만 그의 코드가 마음에 듦
    특히 JSON 라이브러리 https://github.com/skeeto/pdjson, 옵션 파싱 라이브러리 https://github.com/skeeto/optparse와 https://github.com/skeeto/getopt, 분기 없는 UTF-8 디코더 https://github.com/skeeto/branchless-utf8, 잠금 없는 스택 https://github.com/skeeto/lstack, 트라이 라이브러리 https://github.com/skeeto/trie가 좋음
    위 프로젝트들이 모두 The Unlicense로 배포된다는 라이선스 취향도 마음에 듦

    • Skeeto는 전설급임. 내 기준으로는 Fabrice Bellard와 같은 급에 있음
      GitHub에서 몇 년째 팔로우 중인데, 늘 흥미로운 작고 기묘한 틈새 도구들을 툭툭 내놓음. 예를 들면 Branchless UTF-8이 유명함
    • 그는 elfeed https://github.com/skeeto/elfeed의 작성자이기도 함. “An Emacs web feeds client”인데, 그 미니멀한 구현에서 많은 영감을 받았음

  • 안녕하세요, 제가 MurmurHash 만든 사람임. 흥미로운 작업이고, 곱셈-시프트-XOR 방식이 이렇게 오래 잘 버틴 게 재미있음

    • XOR-시프트는 곱셈의 두 약점을 상쇄함. 높은 비트는 그 위에서 영향을 줄 비트가 없고, 낮은 비트는 그 아래에서 영향을 받을 비트가 없다는 점임
    • MurmurHash처럼 이것들도 비암호학적 해시를 의도한 것으로 보임
      다만 avalanche + bias 아이디어는 꽤 빠진 부분이 있어 보임. 예를 들어 마지막에 나열된 triple32 함수는 정확한 bias가 0.020888578919738908인데, FabriceNeyret2가 ShaderToy에 구현하면 이런 이미지가 나옴: https://www.shadertoy.com/view/WttXWX 또는 https://i.imgur.com/qU2P5rx.png
      그런데 단순한 노멀 맵 기울기 미분을 해보면 눈에 띄는 “결정” 선들이 꽤 많이 보임. 이런 능선 형태를 부르는 기술 용어가 아마 있을 것임: https://i.imgur.com/IHWT1GM.png
      덧붙이면, 이 전체 아이디어는 이미 5년쯤 된 것 아닌가 싶음: https://nullprogram.com/blog/2018/07/31/

  • 좋은 해시 함수를 개발해본 경험 때문에 자동 해시 탐색 아이디어를 자주 생각했음
    이런 작업을 보니 멋짐. Frank J. T. Wojcik이 만든 오래된 해시 테스트 스위트의 훨씬 개선되고 빠른 변형인 SMHasher3와 연결해서 출력 결과를 자동 평가하면 좋겠음. 속도를 위해 테스트 일부만 쓰고 빠르게 실패 처리할 수도 있음
    64비트와 128비트 해시로 확장해도 좋겠지만, 당연히 탐색 공간은 더 커짐. 관련해서 Rain에 쓸 값을 고르려고 64비트 소수의 곱셈에서 avalanche를 측정하는 NodeJS 코드도 만든 적 있음
    [Rain]: https://github.com/dosyago/rain
    [SMHasher3]: https://gitlab.com/fwojcik/smhasher3

  • 이걸 RISC-V 비트 조작 확장에서 사용할 수 있는 연산들로 일반화하면 흥미로울 것 같음. 나중에 그 명령들이 더 널리 보급됐을 때 쓸 수 있는 강한 함수들을 발견할지도 모름
    캐리 없는 곱셈도 가역 연산 집합을 확장할 수 있고, 일부 기존 하드웨어에서는 빠름. CRC도 어느 정도 관련되지만 더 넓은 하드웨어 집합에서 가능하고, CLMUL이 찾을 수 있는 것의 엄격한 부분집합이어야 함
    해시의 많은 용도는 해시값의 최하위 비트나 최상위 비트만 신경 쓰므로, 최상위/최하위 비트 구간의 bias나 여러 수로 나눈 나머지를 평가해보는 것도 흥미로움. 전체 출력 기준으로는 편향이 없어 보이는 함수도 전체 출력을 보지 않는 지표나 ASCII 텍스트 같은 비균등 입력에서는 더 좋아지거나 나빠질 수 있음

  • 왜 이게 멋지고 어디에 쓰이는지 설명해줄 수 있음?

    • 해시 함수를 만들기 위한 명령열을 생성하고, 그 해시 함수가 얼마나 좋은지 평가하는 도구로 보임
      목표 지표는 입력 비트 하나가 바뀔 때 가능한 많은 출력 비트가 가능한 한 무작위처럼 바뀌는지로 잡은 듯함. 생성한 것 중 가장 좋은 해시 함수의 C 코드를 출력함
      그래서 해시 함수가 필요한데 기존 함수들이 충분히 좋지 않다고 생각하거나, 해시 함수를 연구하면서 새로운 구조 아이디어가 필요할 때 유용함. 코드 생성 자체도 멋지고, 무작위로 하는 건 더 멋진 유전 프로그래밍으로 가는 첫걸음임. 그리고 인간은 약 15년 전부터 컴퓨터가 CPU 사이클을 태워 대부분 쓰이지 않을 해시를 계산하게 만드는 일을 좋아하는 듯함
    • 이런 함수들은 해시 테이블에 필수적임. 관련 이름으로 해시 맵, 해시 집합도 있음
      해시 테이블은 많은 알고리즘을 단순하고 효율적으로 구현할 수 있게 해주는 훌륭한 자료구조임. 이 효율은 데이터에 대해 작고, 예를 들어 32비트나 64비트이며, 거의 고유한 해시를 만들 수 있느냐에 달려 있음
      예를 들어 사용자 이름을 해시할 때 이름의 첫 글자 ASCII 코드만 쓰면 많은 사용자명이 같은 숫자로 매핑되어 잘 동작하지 않음. 이것을 충돌이라고 하고, 충돌이 많으면 해시 테이블은 매우 비효율적이 됨
      더 나은 방식은 사용자명 전체에서 비트를 가져와 어떻게든 섞어서 throwaway_1237과 throwaway_12373이 서로 다른 숫자가 되게 하는 것임. 해시 함수가 이 매핑을 수행하고, avalanche 성질은 충돌을 피하는 일을 얼마나 잘하는지 설명함
      보통 실제 해시 함수가 얼마나 빠른지와 충돌 회피를 얼마나 잘하는지 사이에 절충이 있음. 세계적인 수준의 해시 함수는 이상한 상수로 곱하고 XOR하고 시프트하는 등 상당히 기묘해 보이며, 사람이 이런 난해한 함수를 보고 성능을 추측하기는 매우 어려움
      이 코드는 무작위로 여러 해시 함수를 시도하고 서로 겨루게 함. 성공하면 여러 언어와 라이브러리 전반에서 쓰이는 핵심 자료구조의 실제 성능을 개선할 수 있어서 멋짐
    • 정수용 해시 함수이므로 집합이나 맵에서 빠른 정수 해시가 필요할 때 쓸 수 있음. 함수들이 충분히 다르게 갈라진다면 Bloom 필터용 빠른 해시도 제공함

  • 몇 주 전에 Go로 1brc를 구현했는데 https://github.com/infogulch/1brc-go, 이 저장소를 보고 각 관측소가 충돌 없이 자기 버킷에 들어가도록 맞춤형 완전 해시 함수를 찾아보려는 영감을 받았음
    그러다 프로그램 시작 전에 데이터에 맞춰 해시 함수를 커스터마이즈하면 안 된다는 규칙을 보고 아이디어를 접었음
    임의 상수, 시작값, 곱셈 상수, 시프트/회전량 등을 확인하고 충돌 버킷 수와 충돌 수 기준으로 지금까지 찾은 최고 상수를 출력하는 테스트 장치를 만들었음. 채움률 약 40%에서 단 하나의 버킷에 두 값만 충돌하는 수준까지 줄였던 것 같음. 흥미롭게도 가장 성능 좋은 상수들은 다른 상수와 무관하게 비슷한 시프트 위치 수를 포함해서, 결국 그 값들은 하드코딩했음

  • 직접 입력 데이터 생성기를 넣을 수 있다면 정말 흥미로울 것 같음. 실제로는 무작위 바이너리 데이터가 아니라 어떤 식으로든 구조화된 데이터가 많고, 그 구조 덕분에 아주 좋은 해시 함수를 얻을 수 있을지도 모름

  • 가역 연산으로 제한하면 수학적으로 좋은 점은 있지만, 동시에 많은 것을 배제하게 됨
    비슷한 걸 했을 때는 입력 집합을 미리 아는 완전 해싱을 생각하고 있었음. 일반적인 접근은 상수 배열을 쓰지만, 특히 입력이 이미 작은 정수라면 더 압축할 수 있는지 보고 싶었음. 당연히 hash -= hash >> gap_index 같은 식으로 가능함
    그래서 아마 100개쯤 되는 원시 연산 목록을 써봤음. 일부는 서로 중복되지만 따로 생각하면 유용한 것들이었음. 그러다 지루해져서 프로젝트로는 아무것도 하지 않았음

    • “가역 연산으로 제한하면 수학적으로 좋은 점”이라는 게 무엇이고, 이 맥락에서 가역 연산이 왜 바람직한가?

  • 정확히 뭘 하는지 잘 모르겠음. 역대 최고를 찾는 건가? 아니라면 실행할 때마다 최고값이 왜 바뀌는지 궁금함
    또 특정 범위의 정수값, 예를 들어 10,000부터 200,000 사이만 나온다는 걸 알고 있을 때, 그 값을 최적 개수의 해시 버킷으로 넣을 좋은 해시 함수를 발견하는 메커니즘을 아는 사람이 있는지도 궁금함

    • 그 실행에서 시도한 값들 중 최고를 찾기 위해 값을 무작위로 시도하는 방식임
      한 번의 실행으로 탐색 공간을 전부 훑어 절대적인 최적값을 찾는 건 현실적으로 불가능하고, 시도 순서도 무작위라 실행마다 값이 달라질 수 있음
      그냥 “좋은” 해시가 필요하다면 거의 항상 일반적인 해시 함수를 쓰는 게 최선임. 숫자가 극도로 크고 범위가 아주 작다면 최솟값이 다시 0이 되도록 오프셋을 적용해 더 작고 빠른 해시를 쓸 수 있음. 정확한 범위에 대한 “완벽한 선택”을 찾고 싶다면, 이런 무작위 접근이 가장 가까울 것 같고 테스트를 해당 구간에서 수행하도록 바꾸면 됨

  • 두 번의 곱셈에 같은 상수를 쓰면 코드 크기가 줄어서 계산도 약간 빨라질 수 있지 않을까 궁금함
    StackOverflow 답변도 업데이트했음: https://stackoverflow.com/questions/664014/what-integer-hash...

답변달기