Rust와 C++보다 빠른 완벽한 해시 테이블 만들기

이 영상은 Rust와 C++의 표준 해시 테이블보다 10배 이상 빠른 '완벽한 해시 테이블(Perfect Hash Table)'을 구현하기 위한 여정과 그 과정에서 얻은 10가지 성능 최적화 팁을 상세히 다룹니다.

• 해시 테이블의 중요성과 기본 원리

  • 해시 테이블은 소프트웨어에서 가장 중요한 자료구조 중 하나로, 언어마다 딕셔너리, 연관 배열, 오브젝트 등 다양한 이름으로 불립니다.
  • 대중적인 해시 테이블은 범용적으로 설계되어 최적화되어 있으나, 특정 상황에서는 성능이 부족할 수 있습니다.
  • 요일 이름을 숫자로 매핑하는 예시에서, 첫 글자를 인덱스로 사용하는 간단한 해시 함수를 생각할 수 있습니다.
  • 하지만 'Thursday'와 'Tuesday'처럼 첫 글자가 같은 경우 '충돌(Collision)'이 발생하며, 이는 해시 테이블의 성능을 저하시키는 주요 원인이 됩니다.

• 완벽한 해시 함수(Perfect Hash Function)의 개념

  • 데이터 세트를 미리 알고 있다면 충돌이 전혀 발생하지 않도록 해시 함수를 설계할 수 있습니다.
  • 예: (두 번째 문자 * 2) + 첫 번째 문자 값을 사용하여 고유한 인덱스를 생성합니다.
  • 이러한 함수를 '완벽한 해시 함수'라고 하며, 데이터 세트가 고정된 경우(예: 프로그래밍 언어의 예약어)에 매우 효율적입니다.

• 실전 문제: 타입스크립트 파서의 키워드 인식

  • 작성 중인 타입스크립트 파서에서 키워드를 숫자로 매핑해야 하는 과제가 발생했습니다.
  • 가장 나이브한 해결책인 '선형 탐색(Linear Search)'은 초당 600만 번의 조회를 수행했습니다.
  • '이진 탐색(Binary Search)'을 시도했으나, 데이터가 정렬되어 있음에도 불구하고 선형 탐색보다 오히려 느린 결과가 나왔습니다.
  • C++ 표준인 std::unordered_map을 사용하자 선형 탐색보다 2배 빠른 성능 향상을 보였습니다.
  • Rust의 기본 HashMap은 이번 사용 사례에서 C++의 unordered_map만큼 최적화되어 있지 않았습니다.

• 성능 팁 1: 일단 시도해보기(Try it)

  • 머릿속에 떠오르는 첫 번째 방법(선형 탐색)부터 시도하고, 만족스러울 때까지 다른 방법들을 계속 테스트하며 성능 사고방식을 유지해야 합니다.

• 범용 해시 함수의 한계와 최적화 전략

  • 범용 해시 함수는 데이터의 특성을 모르기 때문에 모든 문자를 확인해야 하며, CPU가 선호하지 않는 가변 길이 데이터를 처리해야 합니다.
  • 문자열 길이(Length)를 해시로 쓰는 것이 가장 빠르지만, 길이가 같은 키워드가 많아 충돌이 빈번합니다.
  • 첫 글자와 마지막 글자의 조합 등을 시도한 끝에, '처음 2바이트'와 '마지막 2바이트'를 추출하여 조합하는 방식이 충돌을 피하는 효율적인 방법임을 발견했습니다.
  • 16비트 로드(Load) 두 번, 시프트(Shift), 비트 OR 연산을 통해 루프 없이 4개의 어셈블리 명령어로 해시 값을 생성할 수 있습니다.

• 성능 팁 2: 데이터에 대한 가정을 세우기(Make assumptions about your data)

  • 데이터는 결코 무작위가 아니며 패턴이 존재합니다. 이번 사례에서는 '모든 키워드는 최소 2글자 이상'이며 '특정 위치의 문자 조합이 고유하다'는 가정을 활용했습니다.

• 기존의 완벽한 해시 생성 도구 분석

  • Rust의 rustphf: 내부 헬퍼 테이블을 사용하여 충돌을 방지하지만, 커스텀 해시 함수를 쓴 C++보다 느렸습니다.
  • C++의 Frozen: rustphf보다 2배 빠르며, 커스텀 해시 함수를 적용했을 때 성능이 다시 2배 향상되었습니다.
  • Gperf: 많은 컴파일러에서 사용하는 도구로, 문자를 숫자로 변환해 합산하는 방식을 사용하며 성능이 매우 뛰어납니다.

• 저자의 새로운 해시 테이블 구현 방식

  • 해시 값을 생성한 뒤 테이블에 직접 접근하는 단순한 구조를 채택했습니다.
  • 충돌이 발생하면 해시 함수의 '시드(Seed)' 값을 바꿔가며 충돌이 없을 때까지 반복 생성합니다. (시드 1, 2, 3... 순차 시도)
  • 50,000번 시도 후에도 실패하면 테이블 크기를 키워 다시 시도합니다.

• 성능 팁 3: 타인의 방식을 참고하기(See how other people did it)

  • Gperf가 왜 빠른지 분석한 결과, 문자열 전체 비교(memcmp) 전에 '첫 번째 문자'만 먼저 비교하는 트릭을 발견했습니다.
  • 이 작은 조건문 하나를 추가하는 것만으로 50%의 성능 향상을 얻어 Gperf를 추월했습니다.

• 성능 팁 4: 데이터를 개선하기(Improve your data)

  • 문자열 비교 시 경계 검사(Bound check)를 없애기 위해, 입력 데이터 뒤에 널 바이트(Null bytes)를 충분히 추가하여 메모리 초과 접근 시에도 크래시가 나지 않도록 조정했습니다.

• 성능 팁 5: 계속해서 질문 던지기(Keep asking questions)

  • '11바이트를 비교하는 가장 빠른 방법' 등을 검색하며 SIMD(SSE, AVX) 같은 하드웨어 가속 기능을 탐구해야 합니다.

• 성능 팁 6: 작다고 항상 좋은 것은 아님(Smaller isn't always better)

  • 31개의 명령어로 구성된 가장 짧은 코드가 더 많은 명령어를 가진 다른 구현보다 느린 경우가 발생했습니다. 명령어 수보다 CPU의 실행 효율이 중요합니다.

• 프로파일링 도구의 활용과 브랜치 예측

  • Intel VTune으로 분석했을 때 문자열 비교(memcmp)가 CPU의 60%를 점유하고 있음을 확인했습니다.
  • perf stat을 통해 브랜치 미스(Branch miss)가 성능 저하의 원인임을 발견했습니다.
  • CPU는 조건문의 결과를 예측하는데, 실패할 경우 성능 비용이 큽니다.
  • Cmove 명령어를 사용하거나 수학적 트릭을 써서 조건문(Branch) 자체를 없애는 'Branchless' 코드를 작성하여 성능을 극대화했습니다.

• 성능 팁 7: 여러 프로파일링 도구 사용(Use multiple profiling tools)

  • VTune, perf record, perf stat 등 서로 다른 도구는 각기 다른 관점의 병목 현상을 보여줍니다.

• 성능 팁 8: 실제 데이터로 벤치마크하기(Benchmark on real data)

  • 가짜 데이터는 CPU가 예측하기 너무 쉬워 브랜치 미스 문제를 발견하지 못할 수 있습니다. jQuery 같은 실제 코드베이스의 데이터를 사용해야 실질적인 최적화가 가능합니다.

• 테이블 인덱스 계산 최적화

  • 나머지 연산(Modulo) 대신 테이블 크기를 2의 거듭제곱으로 설정하고 비트 AND 연산을 사용합니다.
  • 엔트리 크기도 2의 거듭제곱(16바이트 등)으로 맞추어 곱셈 대신 비트 시프트를 활용하거나, 더 나아가 시프트 없이 AND 연산만으로 주소를 계산하는 기법을 적용했습니다.

• 성능 팁 9: 새로운 아이디어를 계속 시도하기(Keep trying new ideas)

  • 2주 동안 수많은 막다른 길을 만났지만, 포기하지 않고 실험하는 과정에서 PTEST 명령어 활용법 등을 익히게 되었습니다.

• 성능 팁 10: 최적화에 대해 이야기하기(Talk about your optimizations)

  • 영상을 제작하며 생각하는 과정에서 '경계 검사를 완전히 삭제'할 수 있다는 아이디어를 얻었습니다. 고무 오리 디버깅처럼 남에게 설명하는 과정이 새로운 통찰을 줍니다.

• 최종 결과

  • C++ 표준 해시 테이블보다 10배 빠른 성능을 달성했습니다.
  • 키워드 감지는 컴파일러 전체에서 작은 부분이지만, 이 최적화를 통해 전체 컴파일 속도가 약 5% 향상되었습니다.