[250415]Ideal Hash Tree(HAMT) - 01 - Array Mapped Tries(AMT)

AMT의 각 노드는 두 개의 32비트 워드로 구성되며, 이는 비트맵과 포인터 배열로 나뉜다.

• 비트맵
  • 32비트 정수로, 최대 32개의 아크를 나타냄.
  • 각 비트는 아크의 존재 여부를 나타냄
  • 예: 비트맵 00000000000000000000000000000000은 모든 아크가 비어있음을 나타냄. 예: 비트맵 00000000000000000000000000000101라면 0, 2가 유효한 아크.
• 포인터 배열(Table)
  • 비트맵에서 1로 표시된 아크에 대응하는 하위노드(또는 데이터)
  • 포인터는 비트맵의 1 비트 순서대로 정렬되어 있어, 빈 아크는 저장되지 않음.
  • 예: 비트맵 00000000000000000000000000000101에 대한 포인터 배열은 0, 2번 인덱스에 대한 포인터를 저장.
• 노드 크기
  • 비트맵(4바이트) + 포인터 배열(최대 32개 포인터, 각 4바이트)로 구성.
  • 그러나 실제 포인터 배열의 크기는 유효한 아크 수에 따라 동적으로 결정되므로, 빈 아크로 인한 메모리 낭비가 적음.
• 메모리 효율성:
  • 빈 아크는 비트맵에서 단 1비트로 표현되므로, 전통적인 트라이처럼 빈 포인터를 저장하는 방식보다 훨씬 적은 메모리를 사용.

AMT는 키를 탐색하거나 삽입할 때, 비트맵과 CTPOP(Count Population) 연산을 활용해 동작한다.

탐색 :

1. 입력: 탐색하려는 키의 일부(예: 5비트 조각, 0~31 범위의 값).
2. 비트맵 확인:
   • 키에 해당하는 비트(예: 키 값이 3이면 비트 3)를 확인.
   • 비트가 1이면 유효한 아크로 진행.
   • 비트가 0이면 데이터가 없음. 탐색실패
3. 포인터 배열 인덱스 계산:
   • 비트맵에서 해당 비트 아래의 1 비트 수를 CTPOP으로 계산.
   • 이 값은 포인터 배열에서 해당 아크의 위치(인덱스)를 나타냄.
   • 포인터 배열은 비트가 1인 데이터만 갖고 있다.
4. 다음단계:
   • 포인터를 따라 하위 노드(또다른 비트맵)로 이동하거나, 단말 노드(최종 목적지)라면 키 비교를 수행.
   • 필요하면 다음 5비트 조각을 사용해 탐색을 반복.

4.1 하위노드에 대한 탐색

처음엔 어떻게 하위노드로 검색을 할 것이 있나? 싶었다. 하지만 AMT 의 특성은 키를 한번에 비교하는 것이 아니다. 키의 앞부분을 잘라서 그것만으로 비교가 완료되면 그 뒤에 있는 키는 비교하지 않는다.

• 키: 00101 00100 (10비트, 첫 5비트는 00101=5, 다음 5비트는 00100=4)
• 루트 노드: 첫 5비트 5를 사용해 P3 선택.
• P3가 하위 노드라면: 다음 5비트 4를 사용해 하위 노드의 비트맵을 확인하고, 동일한 탐색 과정을 반복.
• 단말 노드에 도달하면: 전체 키 00101 00100를 비교.

삽입 (Insert)

• 탐색과 유사한 과정을 따르며, 키가 없는 경우 새 아크를 추가.
• 비트맵에 새 1 비트를 설정하고, 포인터 배열을 확장해 새 하위 노드(또는 데이터)를 추가.
• 충돌 시, 기존 노드를 하위 트리로 변환해 키를 분리.

삭제 (Delete)

• 키를 찾아 해당 아크를 제거.
• 비트맵에서 1을 0으로 변경하고, 포인터 배열에서 해당 항목을 삭제.
• 필요 시 상위 노드를 정리해 메모리를 최적화.

CTPOP(Count Population)은 비트맵에서 특정 비트 아래의 1 비트 수를 세는 연산으로, AMT의 핵심적인 성능 요소. (AMT에서 포인터 배열 인덱스를 계산할 때 필수적이며, 성능에 큰 영향을 미친다)

역할:

• 비트맵에서 유효한 아크의 인덱스를 계산.
• 예: 비트맵이 10110이고 키가 3(비트 3)이라면, 비트 3 아래의 1 비트 수(즉, 1011의 1 개수)를 계산해 포인터 배열의 인덱스를 결정.
• 즉, 비트맵에서 키 4의 값을 찾고 싶다고하면, 비트 4에 일단 1이 있는지 확인하고, 포인터 배열에서 몇번쨰 인덱스에 있는지 확인해야 한다. 하지만 포인터 인덱스는 비트맵이 1인 데이터만 동적으로 배열로 가진다. 즉, 어느 인덱스에 있는지 알 수가 없다. 키가 4라고 4에 있는게 아니다. 그래서 비트 4 이하의 비트맵에 1의 개수가 몇개인지 세서 포인터 배열의 인덱스를 결정한다. 만약 비트 4 이하 키가 하나도 없다면 내가 찾는 키의 인덱스 배열의 인덱스는 0이다. 예) 포인터배열 [P1, P2, P3] 에서 P1이 값이 있는 곳이다.

하드웨어 지원:

• 현대 CPU(예: Intel Itanium, ARM, PowerPC 등)에서 CTPOP은 단일 명령어로 실행되며 매우 빠름.
• popcnt(population count)라는 단일 명령어로 실행. 예: popcnt(10110) → 3 (10진수).
• 지원되지 않는 경우, 논문은 소프트웨어 에뮬레이션 코드를 제공

const unsigned int 5%5=0x55555555, 3%3=0x33333333;
const unsigned int 5%F0=0xF0F0F0F, 3KFF=0xFF00FF;
int CTPop(int Map)
{
    Map = ((Map >> 1) & 3);
    Map = (Map & 3) + ((Map >> 2) & 3);
    Map = (Map & 3) + ((Map >> 4) & 3);
    Map += Map >> 8;
    return (Map + (Map >> 16)) & 3;
}

• 이 코드는 비트맵(Map)의 1 비트를 효율적으로 세기 위해 비트 연산을 사용.
• 비트를 2개, 4개, 8개, 16개 단위로 묶어 합산하며, 최종적으로 1의 개수를 반환.
• 예: Map = 10110 (10진수 22)일 때, CTPop(10110)은 3을 반환.
• 문제점: 하드웨어 CTPOP보다 훨씬 느림. 특히 Java처럼 최적화가 부족한 환경에서는 성능 저하가 두드러짐(페이지 5).

예시로 자세히 알아보기

상황:

• 비트맵: 0000010110 (비트 1, 2, 4가 1).
• 키 값: 4 (비트 4를 확인).

CTPOP 동작:

• 비트 4 이하(비트 0~4) 확인: 10110.
• CTPOP(10110) → 3 (1 비트 3개).
• 포인터 배열에서 인덱스 2(3-1, 0-based)를 선택.

clojure의 PersistentHashMap 은 AMT 를 사용한다.

;; Clojure의 PersistentHashMap은 AMT 기반
(def my-map (hash-map :a 1 :b 2))
;; 삽입/검색은 O(1)에 가까움
(get my-map :a) ;; => 1

PersistentHashMap 은 HAMT 에서 자세히 알아보자.