Branch: refs/heads/main
Home: https://github.com/WebKit/WebKit
Commit: 8e2d66bfd161086e6431803f0b02aca31c87d622
https://github.com/WebKit/WebKit/commit/8e2d66bfd161086e6431803f0b02aca31c87d622
Author: Yusuke Suzuki <[email protected]>
Date: 2026-10-01 (Thu, 01 Oct 2026)
Changed paths:
M Source/WTF/wtf/LayeredHashMap.h
M Tools/TestWebKitAPI/Tests/WTF/LayeredHashMap.cpp
Log Message:
-----------
[JSC] Enhance LayeredHashMap
https://bugs.webkit.org/show_bug.cgi?id=325885
rdar://188868868
Reviewed by Keith Miller.
This changes internal implementation of LayeredHashMap to improve
performance & cache locality and add further features.
1. Instead of recording linked list of entries in the same layer, we
start having ordered-hash-map like mechanism. So hash-table just
records the index in Entry buffer. This is beneficial since we can
just record the size of this buffer when layer starts, then the
entries after this index *is* the inserted values.
2. (1)'s architecture offers a feature, "defining overlay entry in this
layer". Previously we cannot define a entry which has the same key
and already existing in the upper layer. But now, each layer can have
the same key entry, and this is overlayed. We keep the old Entry in
the buffer, and this buffer effectively works as an undo log. When
dropping the layer, we roll back the table's index to the older one,
which is recorded in the Entry.
3. Since table size becomes significantly smaller, we changed the load
factor to 50%, as our main client, ValueNumbering's map, super
heavily hit the miss case, and it turned out that this 50% is
critical.
This is improving B3 compile time because of much tighter cache locality
(table tends to be sparse because it is hash-table, but now it is just
uint32_t index table. Entries are in the tight buffer. Dropping layer
becomes iterating the Vector).
Test: Tools/TestWebKitAPI/Tests/WTF/LayeredHashMap.cpp
* Source/WTF/wtf/LayeredHashMap.h:
(WTF::LayeredHashMap::LayeredHashMap):
(WTF::LayeredHashMap::startLayer):
(WTF::LayeredHashMap::dropLastLayer):
(WTF::LayeredHashMap::layerCount const):
(WTF::LayeredHashMap::clearEntries):
(WTF::LayeredHashMap::clear):
(WTF::LayeredHashMap::find):
(WTF::LayeredHashMap::findOrAdd):
(WTF::LayeredHashMap::overlay):
(WTF::LayeredHashMap::Entry::isLayerMarker const):
(WTF::LayeredHashMap::appendLayerMarker):
(WTF::LayeredHashMap::findSlot):
(WTF::LayeredHashMap::slotHolding):
(WTF::LayeredHashMap::rehashIfNeeded):
(WTF::LayeredHashMap::Entry::isEmpty const): Deleted.
(WTF::LayeredHashMap::allocateTable): Deleted.
* Tools/TestWebKitAPI/Tests/WTF/LayeredHashMap.cpp:
(TestWebKitAPI::TEST(WTF_LayeredHashMap, AddDoesNotUpdate)):
(TestWebKitAPI::TEST(WTF_LayeredHashMap, RandomizedAgainstModel)):
(TestWebKitAPI::TEST(WTF_LayeredHashMap, OverlayShadowsEnclosingLayer)):
(TestWebKitAPI::TEST(WTF_LayeredHashMap, OverlayWithinOneLayer)):
(TestWebKitAPI::TEST(WTF_LayeredHashMap, OverlayInLayerThatAddedKey)):
(TestWebKitAPI::TEST(WTF_LayeredHashMap, OverlayAcrossRehash)):
(TestWebKitAPI::TEST(WTF_LayeredHashMap, OverlayOfNewKeyRehashes)):
(TestWebKitAPI::TEST(WTF_LayeredHashMap, ClearEntriesDropsOverlays)):
Canonical link: https://commits.webkit.org/322459@main
To unsubscribe from these emails, change your notification settings at
https://github.com/WebKit/WebKit/settings/notifications
