← All reports

Store one status byte per bucket in WTF::HashTable

Component: WTF HashTable | 53bedf6

Source/WTF/wtf/HashMap.h

- template<typename U> static void translate(auto& location, U&& key, NOESCAPE const Invocable<typename ValueTraits::ValueTraits::TraitType()> auto& functor)
+ template<typename U> static void translate(typename ValueTraits::TraitType* location, U&& key, NOESCAPE const Invocable<typename ValueTraits::ValueTraits::TraitType()> auto& functor)
{
- ValueTraits::KeyTraits::assignToEmpty(location.key, std::forward<U>(key));
- ValueTraits::ValueTraits::assignToEmpty(location.value, functor());
+ std::construct_at(std::addressof(location->key), std::forward<U>(key));
+ std::construct_at(std::addressof(location->value), functor());
}

Source/JavaScriptCore/dfg/DFGLazyJSValue.cpp

- static void translate(String& location, const StringImpl* impl, unsigned)
+ static void translate(String* location, const StringImpl* impl, unsigned)
{
- location = impl->isolatedCopy();
+ new (NotNull, location) String(impl->isolatedCopy());
}

WTF::HashTable은 open addressing 방식의 hash table입니다. HashMap과 HashSet은 물론, atom string, DFG CSE, JIT thunk, DOM cache 같은 내부 cache 상당수가 이 구현 위에서 동작합니다.

기존에는 key 타입마다 sentinel 값 두 개를 예약해 두었습니다. 하나는 empty, 다른 하나는 deleted를 뜻하며, 실제로 저장되는 key는 이 값과 같아질 수 없었습니다. 그리고 table은 bucket에 이 sentinel 값을 직접 기록하는 방식으로 bucket 상태를 관리했습니다.

한편 translator는 저장된 key와 다른 타입으로 조회와 삽입을 수행할 수 있게 해 주는 장치입니다. 새 bucket을 채우는 일은 translator의 translate()가 담당합니다. 이때 bucket에는 이미 유효한 sentinel 객체가 들어 있었으므로, translator는 그 위에 단순히 대입만 해도 문제가 없었습니다.

이번 commit에서는 bucket마다 별도의 status byte를 두도록 변경되었습니다. 이 byte는 empty, deleted, 또는 key hash의 7 bit 중 하나를 나타냅니다. 조회 시에는 bucket storage에 접근하기 전에 이 byte 배열을 먼저 탐색합니다.

결과적으로 타입별 sentinel이 더 이상 필요하지 않게 되었습니다. 새로 확보한 bucket의 메모리도 실제로 초기화되지 않은 상태로 둘 수 있습니다. 그래서 JSC, WTF, WebCore 전반의 translator가 raw storage를 가리키는 T*를 받아 그 자리에서 객체를 생성하도록 수정되었습니다.

Before:                              After:
buckets[]: key/value pairs           status[]: 1 byte per bucket
  empty   = sentinel key               0x00 = empty
  deleted = sentinel key               0x01 = deleted
  lookup loads full bucket/probe       0x80|h7 = full, 7 hash bits
translate(T& slot, ...)              translate(T* raw, ...)
  slot = value (assign over            new (NotNull, raw) T(value)
  sentinel)

miss와 collision이 cache line 하나 안에서 처리되면서, Speedometer 3는 약 1%, MotionMark는 0.5%, JetStream 3는 최대 0.8% 개선되었습니다. 예약된 sentinel key 값을 둘러싸고 오랫동안 이어져 온 버그 유형도 함께 사라집니다. 다만 commit message에 따르면 반대 측면도 있습니다. 새 bucket에 대입하는 코드가 실제 garbage bit를 건드릴 가능성이 이전보다 훨씬 높아졌습니다.