ECL 개발자 다니엘 코흐만스키(Daniel Kochmański)는 Common Lisp의 EQUALP 해시 테이블에서 서로 다른 표현의 같은 숫자가 동일한 해시를 갖도록 숫자 해싱을 개선했다. 새 방식은 특정 혼합 숫자 벤치마크에서 기존 방식보다 최대 600배 빨랐지만, EQUALP를 해시 테스트로 쓰는 경우가 드물어 일반적인 판도 변화를 뜻하지는 않는다고 설명한다.
Common Lisp 표준은 해시 테이블 테스트로 EQ, EQL, EQUAL, EQUALP를 지원한다. 숫자에 적용되는 EQUALP는 표현 형식이 달라도 수학적으로 같은 값이면 참이다. 예를 들어 1과 1.0, 1/2와 0.5, 42와 #C(42.0 0.0)은 EQUALP다. 반면 1/3과 (float 1/3)은 같지 않다.
해시 함수는 충돌을 허용하지만, EQUALP로 같은 두 객체에는 반드시 같은 해시를 내야 한다. 반대는 성립하지 않는다. 같은 해시를 가진다고 해서 두 객체가 EQUALP인 것은 아니다. 모든 값을 상수 해시로 보내도 규칙에는 맞지만 충돌이 너무 많아 해시 테이블의 목적을 살리지 못한다.
숫자 표현과 첫 번째 방식
Common Lisp 숫자에는 정수, 비율, 부동소수점 수, 복소수가 있다. 이 글은 ECL에서 쓰는 2진 부동소수점(radix 2)을 전제로 한다. 정수와 비율은 유리수로 표현되고, 유한한 2진 부동소수점 수는 sign × mantissa × 2^exponent 형태로 볼 수 있다. 따라서 비율과 부동소수점 수가 같은 값이 되려면 비율의 분모가 2의 거듭제곱이어야 한다.
복소수는 실수부와 허수부가 각각 같으면 같은 값이다. 부동소수점 수에서는 -0.0과 +0.0이 EQL은 아니지만 =로 같으므로 해시 전에 0을 정규화해야 한다. 정수와 부동소수점 수는 부동소수점 수에 소수부가 없고 값이 일치할 때 같다.
가장 단순한 기준 방식은 모든 실수를 부동소수점 수로 바꿔 해시하는 것이다. 정밀도 범위를 벗어난 유리수는 근삿값을 해시하고, 오버플로와 언더플로에 따른 부동소수점 예외를 막는다. 이 방식은 구현이 단순하고 통상적인 입력에서는 충돌이 비교적 적지만, 큰 정수와 정밀한 비율에서는 충돌이 늘어난다. 예컨대 260과 260+1이 같은 해시를 가질 수 있어 64비트 ID나 타임스탬프 같은 값에는 문제가 된다. 정수와 유리수를 부동소수점 형식으로 변환하는 비용도 든다.
첫 번째 개선안은 숫자 유형에 따라 정규화하는 방식이다. 정수는 정수로 해시하고, 정수 값인 유한 부동소수점 수는 정수와 같은 방식으로 처리한다. 정수가 아닌 부동소수점 수는 DOUBLE-FLOAT로 바꿔 해시하고, 2의 거듭제곱을 분모로 갖는 비율도 DOUBLE-FLOAT로 처리해 같은 부동소수점 값과 해시를 맞춘다. 나머지 비율은 분자와 분모를 따로 해시한다. 허수부가 0인 복소수는 실수부만 해시하고, 그 밖의 복소수는 두 부분을 각각 해시한다. 긴 부동소수점 수를 DOUBLE-FLOAT로 줄이면 정밀도를 잃을 수 있고, 큰 부동소수점 수를 정수로 바꾸면 큰 정수를 새로 만들 수 있다는 단점이 있다.
첫 구현에서는 모든 부동소수점 수를 정수로 바꿨다. 무작위 키 (random 20.0)가 해시 20개로만 뭉치는 문제를 발견해 정수가 아닌 부동소수점 수에 서로 다른 해시를 부여하자 HTABLE-MIXBAG 벤치마크에서 새 버전이 이전 버전보다 100배 빨라졌다.
테스트 과정에서는 DOUBLE-FLOAT를 정수로 변환할 때의 경계 버그도 발견했다. x86-64에서 MOST-POSITIVE-FIXNUM은 2^61-1이지만, 이를 DOUBLE-FLOAT로 바꾸면 유효 정밀도가 53비트뿐이라 2^61로 반올림된다. 이 값을 고정 크기 정수로 변환하면 표현 범위를 벗어난다. 수정안은 정확한 경계인 ldexp(1.0, ECL_FIXNUM_BITS-ECL_TAG_BITS-1)를 사용해 경계보다 작은 값만 고정 크기 정수로 바꾸는 것이다.
2의 거듭제곱 분모를 이용한 정규형
첫 번째 개선안에도 큰 정수 값의 부동소수점 수를 처리할 때 최악의 경우 수치당 2KB를 할당하고, LONG-FLOAT 범위를 벗어나는 2진 비율이 있으며, 긴 부동소수점 수를 DOUBLE-FLOAT로 바꾸면 매우 크거나 작은 값이 무한대나 0으로 뭉치는 문제가 있었다.
두 번째 방식은 모든 2진 유리수를 (부호, 가수, 지수) 튜플로 정규화한다. 부호는 유한한 수에서 -1, 0, +1이고, 가수는 양의 홀수 정수 또는 0이며, 지수는 정수다. 값은 부호 × 가수 × 2^지수로 나타낸다. 이렇게 하면 정수·부동소수점 수·2진 비율 사이에서 형식을 변환하지 않고 같은 값을 같은 형태로 해시할 수 있다. 2진이 아닌 비율은 유형 태그를 붙인 뒤 분자와 분모를 해시한다. 허수부가 0이 아닌 복소수도 유형 태그를 붙이고 두 부분을 해시한다.
정수는 뒤에 붙은 0 비트 수만큼 지수를 올려 가수를 홀수로 만든다. 부동소수점 수는 INTEGER-DECODE-FLOAT로 가수·지수·부호를 얻고, -0.0과 +0.0은 같은 형태로 정규화한다. 비율은 분모가 2의 거듭제곱일 때만 2진 비율로 처리한다. 글의 의사코드는 설명을 위해 단순화됐으며 NAN-P와 INFINITY-P는 구현체 확장이나 내부 함수에 의존한다고 밝힌다.
이 정규형은 부동소수점 수를 큰 정수로 바꾸지 않고 불필요한 충돌을 줄이지만, 이를 그대로 쓰면 정규화 비용이 생긴다. ECL의 실제 구현은 정밀도를 희생하지 않는 범위에서 빠른 경로를 추가했다.
- 정규형의 가수나 지수가
LONG-FLOAT정밀도를 넘으면 정규화하지 않고 해당 숫자 유형에 맞춰 해시한다. - 고정 크기 정수로 표현할 수 있는 2진 값은 고정 크기 정수 경로를 쓴다.
- 범위 안의 2진 비율은
LONG-FLOAT로 바꿔 해시해 같은 부동소수점 값과 해시를 맞춘다. - 정수 값인 부동소수점 수와 범위 안의 큰 정수는 불필요한 큰 정수 할당을 피하면서 2진 형태로 해시한다.
DOUBLE-FLOAT정밀도를 넘는 긴 부동소수점 수는 손실이 있는 변환 대신 2진 형태로 해시한다. x87 부동소수점 표현의 패딩 비트가 같은 값에서도 달라질 수 있어 메모리를 그대로 해시하지 않는다.
글에서 든 x86/GCC의 예시는 FIXNUM 62비트, LONG-FLOAT 가수 64비트·지수 15비트·부호 1비트를 가정한다. 예를 들어 3/8은 (1 3 -3), 42는 (1 21 1)로 나타낸다. most-positive-fixnum은 (1 most-positive-fixnum 0), most-negative-fixnum은 (-1 1 61)이다. (/ (1+ (expt 2 40)) 2)는 DOUBLE-FLOAT로 처리할 수 있지만, 같은 형태에서 40을 53으로 바꾸면 LONG-FLOAT 경로가 필요하다. 지수가 -32768인 값은 LONG-FLOAT에서 너무 작고, 2^32768은 예시의 정밀도 범위를 넘는다. (expt 2.0l0 16383)은 LONG-FLOAT 범위에 가까스로 들어가며, 지수 16384인 값은 무한대가 되고 조건을 알릴 수 있다.
구현과 벤치마크
구현에서는 고정 크기 정수는 한 워드로, 큰 정수는 부호와 정수의 각 limb로 해시한다. 큰 정수의 가수가 LONG-FLOAT 범위에 들어오는지 확인한 뒤, 필요한 경우 ECL의 스레드별 임시 레지스터에서 가수를 처리하고 해시 후 해제한다. 이 경로는 큰 정수를 불필요하게 할당하지 않도록 한다. 2진 비율인지 확인할 때도 정수 연산을 피하는 경로를 둔다.
부동소수점 수 처리가 가장 까다롭다. DOUBLE-FLOAT는 정수 값이면 고정 크기 정수나 2진 형태로, 분수 값이면 부동소수점 형식으로 해시해 대응하는 정수·비율과 해시를 맞춘다. LONG-FLOAT는 정밀도 손실 없이 DOUBLE-FLOAT로 표현될 수 있는지 먼저 확인하고, 그렇지 않으면 고정 크기 정수 또는 2진 형태를 쓴다. 처음에는 가수와 지수를 추출하는 별도 함수를 만들었지만, 관련 프로필에서 작은 메모리 할당이 시간과 할당량을 좌우해 디코딩과 해싱을 합치고 미리 할당한 레지스터를 사용했다. 글은 이 차이가 해당 벤치마크에서 1위와 3위의 차이를 만들었다고 설명한다.
벤치마크는 :AVERAGE, :TYPICAL, :DYADIC, :COLLIDE, :BEYOND와 :FIXNUM, :BIGNUM, :RATIO, :DOUBLE 유형별 프로필로 구성했다. 각 프로필은 키 2^16개를 생성해 해시 테이블을 미리 채운 뒤 실행했고, 테스트마다 무작위 키를 사용했으며 8회 실행 결과를 평균냈다. 각 키에 대해 SETHASH와 GETHASH를 실행하고 실행 시간과 할당된 바이트를 측정했다. 해시 테이블 구현도 비교 결과에 영향을 주지만, 반복되는 해시 충돌을 드러내기도 한다.
ECL의 세 변형은 모든 수를 DOUBLE-FLOAT로 바꾸는 warmup, 유형별 해시를 쓰는 round one, 2진 정규형을 활용하는 round two다. 모두 새 해시 함수 xxhash와 해시 테이블 swiss를 사용했다. 비교 대상은 CCL, ECL, LispWorks, SBCL이다. ABCL과 CLASP는 사전 점검에서 EQUALP 아래 숫자 해시가 올바르지 않은 문제를 발견해 제외했다(ABCL#763, CLASP#1876). LispWorks는 부동소수점 수가 포함된 일부 그래프에서 제외했고, CCL도 비율이 포함된 일부 그래프에서 제외했다. LONG-FLOAT와 DOUBLE-FLOAT를 별도 유형으로 갖지 않는 구현에는 :COLLIDE 테스트 대신 :TYPICAL을 썼다.
측정은 X86-64 Intel(R) Core(TM) i9-9900K CPU @ 3.60GHz에서 했다. 그래프의 결과는 각 패널에서 가장 느리거나 할당량이 가장 큰 변형을 기준으로 0과 1 사이로 정규화했다. 따라서 0.00은 0이 아니라 최대값의 0.005 미만을 뜻한다. 결과 원자료는 raw data, 숫자 생성기는 number generator에서 볼 수 있다.
한 가지 중요한 측정상 주의점도 있다. ECL-round2는 :DYADIC, :TYPICAL, :AVERAGE에서 메모리를 할당하는 것으로 보였지만, 조사 결과 해시 함수가 아니라 EQUALP로 부동소수점 키와 유리수 키를 비교하는 해시 테이블이 할당한 메모리였다. 해싱 자체는 메모리를 할당하지 않았다고 설명한다.
ECL 변형끼리 비교하면 각 변형은 특정 유형에서 강점을 보인다. warmup은 DOUBLE-FLOAT 해시가 가장 빠르고 메모리를 할당하지 않는다. round one은 큰 부동소수점 수를 큰 정수로 만들면서 할당 비용이 커질 수 있다. 비율에서는 개선 단계마다 시간과 할당량이 나아졌다. 큰 정수에서는 round one이 강하고 round two는 비슷한 성능을 보였다. 고정 크기 정수는 세 변형 모두 빠르고 할당이 없다.
혼합 숫자 프로필에서는 round two의 차이가 더 컸다. :BEYOND는 부동소수점으로 표현할 수 없지만 가수와 지수 모양이 부동소수점 수와 비슷한 큰 정수·비율을 시험한다. 이 테스트에서 round two는 0.3초로 warmup의 125초보다 400배 빨랐고, 할당은 없었다. warmup은 2GB를 할당했다. :COLLIDE는 DOUBLE-FLOAT로는 표현할 수 없지만 x86의 binary80 LONG-FLOAT로 표현할 수 있는 값을 다룬다. round two는 0.2초로 warmup의 118초보다 600배 빨랐고 할당도 없었다. warmup은 833MB를 할당했다. round two는 큰 정수를 정확히 해시해 충돌도 줄였다.
다른 구현과의 비교는 해시 테이블 자체와 주변 연산의 차이 때문에 직접적인 결론을 내리기 어렵다고 전제한다. 기본 유형에서는 SBCL이 고정 크기 정수·큰 정수·배정밀도 부동소수점 수에서 앞섰고 메모리를 할당하지 않았다. 비율에서는 느리고 155MB를 할당했다. ECL은 비율에서 가장 빨랐으며 기본 유형 비교에서 나머지는 대체로 2위였다. CCL은 부동소수점 수에는 강했지만 비율에서 약했고, LispWorks는 비율에서는 경쟁력이 있었지만 부동소수점 수 프로필에서 매우 느려 일부 비교에서 제외됐다. 혼합 숫자 테스트에서는 ECL이 가장 빨랐고 할당도 가장 적었다. 코흐만스키는 각 구현이 부동소수점 수나 비율에 특화된 해싱을 추가하면 차이를 줄일 수 있다고 본다.
적용 범위
글의 결론은 2진 유리수에는 EQUALP 해시에 쓸 수 있는 정규형이 있으며, 이를 바탕으로 최적화하면 정밀도를 잃지 않으면서 충돌과 메모리 할당을 줄일 수 있다는 것이다. 다만 해시가 다르다고 값이 반드시 다르다는 뜻은 아니다. EQUALP를 해시 테이블 테스트로 쓰는 일이 흔하지 않아 새 방식이 판도를 바꾸는 것은 아니라고도 덧붙인다. 이 방식이 실용적으로 쓰이려면 구현이 충분히 빨라야 한다는 설명이다.
코흐만스키는 이 작업을 단순한 기준 구현에서 출발해 모델을 다듬고, 최적화와 검증을 거쳐 실제 구현으로 옮긴 과정으로 소개한다. 현재 진행 상황은 ECL 저장소의 xxhash, swiss-ht, improve-gf-cache 브랜치에서 확인할 수 있다. 새 해시 테이블과 제네릭 함수 구현을 다룰 후속 글, 성능 및 표준 적합성 개선을 포함할 다음 릴리스도 예고했지만, 구체적인 출시 시점은 제시하지 않았다.
부록: 원문 예시
#define hash_single_float(h,v) hash_float((h), (double)(v)) #define hash_double_float(h,v) hash_float((h), (double)(v)) static inline void hash_float(cl_hashstate *h, double v) { if (v==-0.0) v=0.0; hash_data(h, &v, sizeof(v)); } static inline void hash_long_float(cl_hashstate *h, long double v) { ECL_WITHOUT_FPE_BEGIN { hash_float(h, (double)(v)); } ECL_WITHOUT_FPE_END; } #define hash_fixnum(h,x) hash_float((h),(double)ecl_fixnum(x)) #define hash_bignum(h,x) hash_rational((h),(x)) #define hash_ratio(h,x) hash_rational((h),(x)) static inline void hash_rational(cl_hashstate *h, cl_object x) { ECL_WITHOUT_FPE_BEGIN { double v = ecl_to_double(x); hash_float(h, v); } ECL_WITHOUT_FPE_END; }
/* INV value is guaranteed to be finite and != 0. */ #define DECODE_SIGNUM(value,signum) \ do { if (signbit(value)) { signum=-1; value=-value; } } while(0) /* ... hash_dfloat(cl_hashstate *h, double value) ... */ static inline void hash_lfloat(cl_hashstate *h, long double value) { #if LDBL_MANT_DIG <= ECL_FIXNUM_BITS int ctz, exponent, signum=1; cl_index mantissa; DECODE_SIGNUM(value, signum); value = ldexpl(frexpl(value, &exponent), LDBL_MANT_DIG); exponent -= LDBL_MANT_DIG; mantissa = (cl_index)value; ctz = ecl_ctz(mantissa); exponent += ctz; mantissa >>= ctz; /* binary80 mantissa is 64 bits so it can falsify <= MOST_POSITIVE_FIXNUM. */ if (mantissa <= MOST_POSITIVE_FIXNUM) { hash_word(h, 8*exponent+signum); hash_word(h, mantissa); } else { cl_object reg = _ecl_big_register2(); _ecl_big_set_idx(reg, mantissa); hash_word(h, 8*exponent+signum); hash_bignum_data(h, reg); _ecl_big_register_free(reg); } #else /* Happens for 128bit floats (i.e aarch64). */ const int fixnum_bits = ECL_FIXNUM_BITS-ECL_TAG_BITS-1; int ctz=0, exponent, signum=1; cl_object mantissa = _ecl_big_register2(); cl_fixnum helper, iterator; DECODE_SIGNUM(value, signum); value = frexpl(value, &exponent); _ecl_big_set_ui(mantissa, 0); for(iterator=0; iterator<LDBL_MANT_DIG && value; iterator+=fixnum_bits) { value = ldexpl(value, fixnum_bits); helper = (cl_fixnum)value; value -= helper; _ecl_big_mul_2exp(mantissa, mantissa, fixnum_bits); _ecl_big_add_ui(mantissa, mantissa, helper); /* When this chunk contains only 0s, then we extend trailing zeros by fixnum_bits (chunk's size). Otherwise we start counting again. */ ctz = !helper ? ctz+fixnum_bits : ecl_ctz(helper); } /* ctz is a trailing 0 count for the whole mantissa. iterator denotes how many bits we have shifted the mantissa. */ exponent += ctz - iterator; _ecl_big_div_2exp(mantissa, mantissa, ctz); hash_word(h, 8*exponent+signum); hash_and_free_bignum_register(h, mantissa); #endif } #undef DECODE_SIGNUM
#define hash_single_float(h,v) hash_double_float((h),(double)(v)) static void hash_double_float(cl_hashstate *h, double value) { if (isfinite(value) && (value==trunc(value))) { const double limit = ldexp(1.0, ECL_FIXNUM_BITS-ECL_TAG_BITS-1); if (value < limit && value >= -limit) { hash_word(h, (cl_fixnum)value); return; } hash_dfloat(h, value); return; } /* Fall-through. */ hash_data(h, &value, sizeof(value)); } /* We need to ensure, that when long double can be represented as double without loss of precision, that is value == (double)value, to hash it as double. */ static void hash_long_float(cl_hashstate *h, long double value) { /* Hash as double. */ if (!isfinite(value) || (fabsl(value) <= DBL_MAX && value==(double)value) ) { hash_double_float(h, (double)value); return; } /* Hash as fixnum. */ { const long double limit = ldexpl(1.0L, ECL_FIXNUM_BITS-ECL_TAG_BITS-1); if ((value==truncl(value)) && (value < limit) && value >= -limit) { hash_word(h, (cl_fixnum)value); return; } } /* Hash as long double in dyadic form -- this is both for compatibility with bignums and to avoid hashing padding bits on x87. */ hash_lfloat(h, value); }
댓글 (0)
로그인하면 이 기사에 내 생각을 남길 수 있어요