← 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 is the open-addressing table behind HashMap, HashSet and many internal caches (atom strings, DFG CSE, JIT thunks, DOM caches). Each key type used to reserve two sentinel values, empty and deleted, that stored keys could never equal, and the table recorded bucket state by writing those values into buckets. A translator lets callers look up and insert with a different type than the stored key, and its translate() fills in the new bucket; since the bucket held a valid sentinel, translators could simply assign into it.

The table now keeps a separate status byte per bucket (empty, deleted, or seven bits of the key's hash), and lookups scan that byte array before touching bucket storage. Per-type sentinels are no longer needed, so a fresh bucket's memory can be truly uninitialized, and translators across JSC, WTF and WebCore now take a T* to raw storage and construct in place.

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)

Speedometer 3 improves by about 1%, MotionMark by 0.5% and JetStream 3 by up to 0.8%, because misses and collisions resolve within one cache line. It also removes the long-standing class of bugs around reserved sentinel key values. The flip side, per the commit message, is that assigning into a fresh bucket is now much more likely to hit real garbage bits.