Skip to content

Commit f72ea56

Browse files
committed
[JSC] JSOrderedHashTable is overly allocating DataTable
https://bugs.webkit.org/show_bug.cgi?id=315829 rdar://178227340 Reviewed by Yijia Huang. CloseTable (JSOrderedHashTable) has HashTable and DataTable. HashTable manages indice, and DataTable is a vector of actual key-values so that we can maintain insertion order in that vector side. This means that DataTable size does not need to be the same to HashTable: load-factor is typically 50% or 75%. So actually held key-values are only up to 75% of size of HashTable. This patch computes this and reduces the allocation of DataTable. But we add one slot IterationSentinel at the end and keeping it empty. So iterator can stop by detecting empty value. Previously overly allocated DataTable was guaranteeing this empty sentinel. But now we may use full of DataTable vector, thus we need this sentinel explicitly. Also, we found several issues. 1. forEachInIteratorProtocol is introduced in 299358@main. While we are getting entry index from MapIterator / SetIterator, we are obtaining storage from iterated Map / Set, not MapIterator / SetIterator's current cursor. 2. forEachInIteratorProtocol is not draining an iterator, which is incorrect as for-of should drain it. 3. (1) and (2) exist in tryCreateArrayFromMapIterator as well. Test: JSTests/stress/map-iterator-fully-packed-table.js * JSTests/stress/iterator-helpers-fast-path-drain-and-reentrancy.js: Added. (shouldEq): (throw.new.Error): (i.shouldEq.it.next): * JSTests/stress/map-iterator-fully-packed-table.js: Added. (assert): (buildMap): (buildSet): (drainMap): (drainSet): * Source/JavaScriptCore/runtime/ArrayConstructor.cpp: (JSC::tryCreateArrayFromMapIterator): * Source/JavaScriptCore/runtime/IteratorOperations.h: (JSC::forEachInIteratorProtocol): * Source/JavaScriptCore/runtime/JSMapIterator.h: * Source/JavaScriptCore/runtime/JSOrderedHashTableHelper.h: (JSC::JSOrderedHashTableHelper::dataCapacity): (JSC::JSOrderedHashTableHelper::dataTableSize): (JSC::JSOrderedHashTableHelper::tableSize): (JSC::JSOrderedHashTableHelper::tableSizeSlow): (JSC::JSOrderedHashTableHelper::expandIfNeeded): (JSC::JSOrderedHashTableHelper::transitAndNext): * Source/JavaScriptCore/runtime/JSSetIterator.h: Canonical link: https://commits.webkit.org/314169@main
1 parent ebc771f commit f72ea56

7 files changed

Lines changed: 374 additions & 56 deletions

File tree

Lines changed: 183 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,183 @@
1+
// Regression tests for the Iterator.prototype.toArray / forEach / etc. fast path
2+
// in forEachInIteratorProtocol, and Array.from(map.keys() / .values()) fast path
3+
// in tryCreateArrayFromMapIterator. Requirements:
4+
// 1. Seed iteration from the iterator's stored storage (not the map's current),
5+
// so transit() can shift entry indices across rehashes/clears.
6+
// 2. Leave the iterator drained when iteration completes.
7+
// 3. The fast path and the user-visible callback share the iterator's cursor:
8+
// a reentrant iter.next() inside the callback must advance the iterator,
9+
// consuming the next element so the helper does not see it again.
10+
// Closing the iterator inside the callback (iter.return-equivalent) must
11+
// stop the helper.
12+
13+
function shouldEq(actual, expected, msg) {
14+
const a = JSON.stringify(actual);
15+
const e = JSON.stringify(expected);
16+
if (a !== e)
17+
throw new Error("FAIL " + msg + ": got " + a + ", expected " + e);
18+
}
19+
20+
// --- Iterator.prototype.toArray on Map/Set iterators ---
21+
22+
// Partial-consume returns the remaining elements.
23+
{
24+
const s = new Set([1, 2, 3]);
25+
const it = s.values();
26+
it.next();
27+
shouldEq(it.toArray(), [2, 3], "set toArray after partial consume");
28+
}
29+
30+
// Iterator must be drained after toArray.
31+
{
32+
const s = new Set([1, 2, 3]);
33+
const it = s.values();
34+
it.toArray();
35+
shouldEq(it.next(), { value: undefined, done: true }, "set: next() after toArray must be done");
36+
}
37+
{
38+
const s = new Set([1, 2, 3]);
39+
const it = s.values();
40+
it.next();
41+
it.toArray();
42+
shouldEq(it.next(), { value: undefined, done: true }, "set: next() after partial+toArray must be done");
43+
}
44+
{
45+
const m = new Map([[1, "a"], [2, "b"], [3, "c"]]);
46+
const it = m.entries();
47+
it.toArray();
48+
shouldEq(it.next(), { value: undefined, done: true }, "map: next() after toArray must be done");
49+
}
50+
51+
// Rehash with deletions during partial consume.
52+
{
53+
const s = new Set();
54+
s.add("a"); s.add("b"); s.add("c"); s.add("d");
55+
const it = s.values();
56+
it.next(); it.next();
57+
s.delete("a"); s.delete("b");
58+
s.add("e");
59+
shouldEq(it.toArray(), ["c", "d", "e"], "set toArray after rehash with deletions");
60+
}
61+
62+
// Drained iterator across clear().
63+
{
64+
const s = new Set();
65+
for (let i = 0; i < 1000; i++) s.add(i);
66+
const it = s.values();
67+
while (!it.next().done) {}
68+
s.clear();
69+
shouldEq(it.toArray(), [], "set toArray after drain+clear");
70+
}
71+
72+
// --- Reentrancy: callback advances the iterator, helper picks up after it ---
73+
74+
// Set: callback calls iter.next() once per element, "stealing" alternate entries.
75+
// Helper should see the rest. Total elements distributed between helper & callback
76+
// must equal the iterator contents in spec order.
77+
{
78+
const s = new Set([10, 20, 30, 40, 50]);
79+
const it = s.values();
80+
const helperSaw = [];
81+
const userTook = [];
82+
it.forEach(v => {
83+
helperSaw.push(v);
84+
const n = it.next();
85+
if (!n.done)
86+
userTook.push(n.value);
87+
});
88+
shouldEq(helperSaw, [10, 30, 50], "set forEach: helper sees alternate elements when callback steals one each step");
89+
shouldEq(userTook, [20, 40], "set forEach: callback's iter.next() takes interleaved elements");
90+
shouldEq(it.next(), { value: undefined, done: true }, "set: drained after forEach");
91+
}
92+
93+
// Map: same shape.
94+
{
95+
const m = new Map([[1, "a"], [2, "b"], [3, "c"], [4, "d"], [5, "e"]]);
96+
const it = m.values();
97+
const helperSaw = [];
98+
const userTook = [];
99+
it.forEach(v => {
100+
helperSaw.push(v);
101+
const n = it.next();
102+
if (!n.done)
103+
userTook.push(n.value);
104+
});
105+
shouldEq(helperSaw, ["a", "c", "e"], "map forEach: helper sees alternate elements");
106+
shouldEq(userTook, ["b", "d"], "map forEach: callback gets the rest");
107+
shouldEq(it.next(), { value: undefined, done: true }, "map: drained after forEach");
108+
}
109+
110+
// Callback drains the iterator entirely via repeated iter.next() — helper must
111+
// then see no more elements.
112+
{
113+
const s = new Set([1, 2, 3, 4, 5]);
114+
const it = s.values();
115+
const helperSaw = [];
116+
const userTook = [];
117+
it.forEach(v => {
118+
helperSaw.push(v);
119+
if (v === 1) {
120+
while (true) {
121+
const n = it.next();
122+
if (n.done) break;
123+
userTook.push(n.value);
124+
}
125+
}
126+
});
127+
shouldEq(helperSaw, [1], "set forEach: helper stops after callback drains rest");
128+
shouldEq(userTook, [2, 3, 4, 5], "set forEach: callback drained the rest");
129+
shouldEq(it.next(), { value: undefined, done: true }, "set: drained");
130+
}
131+
132+
// --- Array.from(map.keys()) / Array.from(map.values()) ---
133+
134+
// Partial-consume returns remaining elements.
135+
{
136+
const m = new Map([[1, "a"], [2, "b"], [3, "c"]]);
137+
const it = m.keys();
138+
it.next();
139+
shouldEq(Array.from(it), [2, 3], "Array.from(map.keys()) after partial consume");
140+
}
141+
142+
// Iterator drained after Array.from.
143+
{
144+
const m = new Map([[1, "a"], [2, "b"], [3, "c"]]);
145+
const it = m.keys();
146+
Array.from(it);
147+
shouldEq(it.next(), { value: undefined, done: true }, "map: next() after Array.from must be done");
148+
}
149+
{
150+
const m = new Map([[1, "a"], [2, "b"], [3, "c"]]);
151+
const it = m.values();
152+
it.next();
153+
Array.from(it);
154+
shouldEq(it.next(), { value: undefined, done: true }, "map: next() after partial+Array.from must be done");
155+
}
156+
157+
// Fresh iterator on a map with deletions — fast path skips empties.
158+
{
159+
const m = new Map([[1, "a"], [2, "b"], [3, "c"], [4, "d"]]);
160+
m.delete(2);
161+
m.delete(3);
162+
shouldEq(Array.from(m.keys()), [1, 4], "Array.from(map.keys()) fresh, with deletions");
163+
}
164+
165+
// Partial consume across a rehash with deletions.
166+
{
167+
const m = new Map();
168+
m.set("a", 1); m.set("b", 2); m.set("c", 3); m.set("d", 4);
169+
const it = m.keys();
170+
it.next(); it.next();
171+
m.delete("a"); m.delete("b");
172+
m.set("e", 5);
173+
shouldEq(Array.from(it), ["c", "d", "e"], "Array.from(map.keys()) after rehash with deletions");
174+
}
175+
176+
// Repeat under JIT tiers.
177+
for (let i = 0; i < 1000; i++) {
178+
const m = new Map([[1, "a"], [2, "b"], [3, "c"]]);
179+
const it = m.keys();
180+
it.next();
181+
shouldEq(Array.from(it), [2, 3], "Array.from(map.keys()) loop");
182+
shouldEq(it.next(), { value: undefined, done: true }, "iterator drained loop");
183+
}
Lines changed: 104 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,104 @@
1+
// Regression test for the JIT-inlined MapIteratorNext / SetIteratorNext path
2+
// and the C++ helper transitAndNext.
3+
//
4+
// JSOrderedHashTable's DataTable is sized to its load-factor cap (DataCapacity)
5+
// rather than the bucket count, so a Map/Set populated to exactly DataCapacity
6+
// has no spare zero-initialized slot inside the DataTable past the last entry.
7+
// The iterator (both the JIT-inlined fast path and the C++ helper) terminates
8+
// when it loads an empty JSValue from the slot one past the last alive entry;
9+
// without a trailing IterationSentinel slot, that load would run off the end
10+
// of the storage and read whatever happens to be in adjacent memory, which can
11+
// either yield bogus extra entries, loop forever on a stray deleted-marker, or
12+
// crash. ASan reliably catches the OOB read; in normal release builds the bug
13+
// surfaces only when adjacent memory happens to hold a non-zero value, so this
14+
// test exercises the path but is not a deterministic detector on its own.
15+
//
16+
// The sizes packed below are exactly DataCapacity at the small-capacity
17+
// regime, where DataCapacity = capacity / 2. If the dataCapacity formula in
18+
// JSOrderedHashTableHelper ever changes, regenerate these values.
19+
// capacity 8 -> DataCapacity 4
20+
// capacity 32 -> DataCapacity 16
21+
// capacity 128 -> DataCapacity 64
22+
23+
function assert(b, msg) {
24+
if (!b)
25+
throw new Error("FAIL: " + msg);
26+
}
27+
noInline(assert);
28+
29+
const fullSizes = [4, 16, 64];
30+
31+
function buildMap(n) {
32+
const m = new Map();
33+
for (let i = 0; i < n; ++i)
34+
m.set(i, i * 2);
35+
return m;
36+
}
37+
38+
function buildSet(n) {
39+
const s = new Set();
40+
for (let i = 0; i < n; ++i)
41+
s.add(i);
42+
return s;
43+
}
44+
45+
function drainMap(m) {
46+
const it = m[Symbol.iterator]();
47+
let count = 0;
48+
let sumK = 0;
49+
let sumV = 0;
50+
while (true) {
51+
const { value, done } = it.next();
52+
if (done) {
53+
assert(value === undefined, "done iterator value");
54+
break;
55+
}
56+
sumK += value[0];
57+
sumV += value[1];
58+
++count;
59+
}
60+
// One additional next() after done must keep returning done with no error.
61+
const after = it.next();
62+
assert(after.done === true, "post-done iterator");
63+
return [count, sumK, sumV];
64+
}
65+
noInline(drainMap);
66+
67+
function drainSet(s) {
68+
const it = s[Symbol.iterator]();
69+
let count = 0;
70+
let sum = 0;
71+
while (true) {
72+
const { value, done } = it.next();
73+
if (done) {
74+
assert(value === undefined, "done iterator value");
75+
break;
76+
}
77+
sum += value;
78+
++count;
79+
}
80+
const after = it.next();
81+
assert(after.done === true, "post-done iterator");
82+
return [count, sum];
83+
}
84+
noInline(drainSet);
85+
86+
for (const n of fullSizes) {
87+
const map = buildMap(n);
88+
const set = buildSet(n);
89+
90+
const expectedSumK = (n * (n - 1)) / 2;
91+
const expectedSumV = expectedSumK * 2;
92+
const expectedSetSum = expectedSumK;
93+
94+
for (let i = 0; i < testLoopCount; ++i) {
95+
const [c, sk, sv] = drainMap(map);
96+
assert(c === n, "map count " + n);
97+
assert(sk === expectedSumK, "map sumK " + n);
98+
assert(sv === expectedSumV, "map sumV " + n);
99+
100+
const [sc, ss] = drainSet(set);
101+
assert(sc === n, "set count " + n);
102+
assert(ss === expectedSetSum, "set sum " + n);
103+
}
104+
}

0 commit comments

Comments
 (0)