EQUALP에서 숫자를 해싱하는 천상의 즐거움

AI 요약

ECL의 범용 함수 디스패치 성능을 비교하려고 해시 테이블을 먼저 최적화하던 중, 숫자를 EQUALP로 비교할 때 해시 일관성을 보장하는 문제가 드러났습니다. 글은 간단한 해시 방식에서 출발해 정규화 모델을 만들고, 벤치마크와 C 구현 최적화를 거쳐 최종 방식에 이르는 과정을 설명합니다.

EQUALP 해시의 조건

Common Lisp의 해시 테이블은 EQ, EQL, EQUAL, EQUALP 테스트를 지원합니다. 숫자에 대한 EQUALP는 값이 수학적으로 같으면 참이므로, 정수 1과 부동소수점 1.0, 비율 1/2와 0.5, 허수부가 0인 복소수와 실수도 같은 해시를 받아야 합니다. 반대로 해시가 같다고 두 값이 EQUALP라는 뜻은 아닙니다. 단순히 모든 실수에 같은 값을 주면 조건은 만족하지만 충돌이 많아져 해시 테이블 성능이 나빠집니다.

처음 검토한 방식은 모든 숫자를 double-float로 바꿔 해시하는 것입니다. 구현이 간단하고 합리적인 작업량에서는 충돌도 적지만, 큰 정수나 정밀한 비율을 부동소수점 근사값으로 바꾸면서 서로 다른 값이 같은 해시를 받습니다. 예를 들어 큰 정수와 그 다음 정수가 모두 같은 double 값으로 반올림될 수 있습니다. 형식 변환에 따른 메모리 할당과 시간 비용도 발생합니다.

첫 번째 개선과 정규화 모델

첫 개선안은 숫자 종류별로 처리합니다. 정수는 정수로 해시하고, 정수값인 유한 부동소수점 수는 정수와 같은 경로를 탑니다. 정수가 아닌 부동소수점 수는 double-float로 변환하며, 2의 거듭제곱을 분모로 갖는 이진 비율(dyadic ratio)은 부동소수점 수와 같은 방식으로 처리합니다. 그 밖의 비율은 분자와 분모를 따로 해시합니다. 허수부가 0인 복소수는 실수부만 해시하고, 나머지 복소수는 실수부와 허수부를 각각 해시합니다.

이 방식은 무작위 실수 키를 20개 값으로만 합쳐 버리던 구현 오류를 고쳤고, HTABLE-MIXBAG 벤치마크에서 이전 버전보다 100배 빨라졌습니다. 그러나 정수값인 큰 부동소수점 수를 정수로 바꾸면 최악의 경우 부동소수점 수마다 2KB를 할당할 수 있습니다. double-float의 정밀도를 넘는 long-float는 double로 바꾸는 과정에서 값이 0이나 무한대로 뭉칠 수도 있습니다. 구현자는 double-float를 정수로 바꾸는 경계 조건도 수정했습니다. x86-64에서 최대 fixnum은 double로 정확히 표현되지 않으므로, 반올림된 경계값을 fixnum으로 잘못 변환하지 않도록 정확히 표현 가능한 2의 거듭제곱을 경계로 사용합니다.

두 번째 방식은 이진 유리수(dyadic rational)를 부호, 홀수 가수, 2의 지수로 표현합니다. 값은 부호 × 가수 × 2의 지수이며, 0은 부호와 가수를 0으로 정규화합니다. 정수와 유한 부동소수점 수, 이진 비율이 같은 수학적 값을 나타내면 같은 튜플을 얻습니다. 이 방식은 큰 정수로 변환하지 않고도 정밀도를 보존하며, 2진 부동소수점 수로 표현할 수 없는 비율은 자료형 태그와 분자·분모로 해시합니다. NaN과 양·음의 무한대는 별도 부호값을 사용합니다.

실제 구현의 최적화

튜플 모델을 그대로 적용하면 정규화 비용이 들기 때문에 ECL 구현은 값의 범위에 따라 경로를 나눕니다. fixnum 범위의 값은 바로 해시하고, long-float 정밀도 안에 드는 이진 비율은 long-float로 변환합니다. 정밀도가 범위를 넘는 값은 튜플 형태로 처리하거나 원래 자료형으로 해시합니다. 특히 long-float를 double-float로 바꿀 때 정밀도를 잃는 값은 이진 표현으로 해시해 충돌을 줄입니다. x87 long double에 남는 패딩 비트도 값 비교와 해시 결과를 어긋나게 할 수 있어 메모리 내용을 그대로 해시하지 않습니다.

구현에서는 가수 추출과 해시를 합쳐 임시 할당을 줄이고, 큰 정수의 비트 길이와 끝의 0 개수를 이용해 범위를 판별합니다. 부호와 지수도 한 워드에 결합해 해시 상태 갱신 횟수를 줄입니다. 복소수는 허수부가 0이면 실수부만 처리하고, 그렇지 않으면 두 성분을 나눠 해시합니다.

벤치마크 결과와 범위

벤치마크는 키 2^16개를 미리 생성해 해시 테이블을 채운 뒤 실행했으며, 각 프로필을 8회 측정해 시간과 할당량을 비교했습니다. ECL의 세 방식은 모든 것을 double로 바꾸는 초기안, 자료형별 해시를 쓰는 1차안, 이진 정규화와 범위별 최적화를 적용한 2차안입니다. ECL의 새 해시 함수와 Swiss 해시 테이블을 사용했고, 비교 대상은 CCL, ECL, LispWorks, SBCL입니다.

ECL 2차안은 일반 숫자 유형에서도 비율 처리 성능이 개선됐고, 혼합 키에서는 대체로 가장 빠르며 할당량도 가장 적었습니다. 특히 long-float 범위를 넘는 값이 섞인 BEYOND 프로필에서는 초기안의 125초와 2GB 할당에 비해 0.3초를 기록했다고 보고합니다. LONG-FLOAT를 DOUBLE-FLOAT로 정확히 표현할 수 없는 COLLIDE 프로필에서는 초기안이 118초와 833MB를 쓴 반면 2차안은 0.2초를 기록했습니다. 다만 부동소수점 수와 비율 키를 서로 비교할 때 EQUALP가 메모리를 할당해, 2차안의 일부 측정에서 나타난 할당은 해시 함수가 아니라 키 비교에서 비롯됐다고 설명합니다.

구현체별 결과는 유형에 따라 다릅니다. SBCL은 fixnum, bignum, double-float에서 강했지만 비율이 섞이면 느려지고 할당량이 늘었습니다. CCL은 부동소수점 수에 강하고 비율에서 약했으며, LispWorks는 반대로 부동소수점 수 처리에서 크게 느렸습니다. 다른 구현체를 포함한 비교는 해시 테이블 구현과 관련 연산 비용도 함께 측정하므로 해시 함수만의 순위로 볼 수 없다고 글은 덧붙입니다. 작성자는 EQUALP를 해시 테스트로 쓰는 경우가 흔하지 않아 이번 개선이 전반적인 성능을 바꾸지는 않지만, 서로 다른 표현의 같은 숫자를 묶는 기능이 빨라지면 실제 사용도 늘 수 있다고 주장합니다.

원문: Turtleware / 번역·요약: Trawling