Skip to content

Commit 66c2d6d

Browse files
pilaodapilaoda
committed
fix(lualib): rewrite Map/Set with flat array storage for safe iteration during deletion
Replace linked list (nextKey/previousKey) with flat arrays + V8-style version chain compaction. Deleted entries become tombstones (nil slots); iterators skip them via idx++. Compaction creates new arrays and links old → new; iterators transition lazily by adjusting their index. Changes: - Map/Set use keyIndex (hash), orderedKeys/orderedValues (arrays) - delete() marks tombstone, triggers compact when deletedCount > size - compact() records hole positions, links old arrays to new via index 0 - Iterator transitions through version chain (V8 Transition algorithm) - has() uses keyIndex (works correctly with null/undefined values) Based on V8's OrderedHashTable: https://chromium.googlesource.com/v8/v8/+/main/src/objects/ordered-hash-table.cc Tests: 166 Map/Set tests including V8 stress tests, memory leak tests, delete-during-iteration, re-add, and consecutive delete scenarios. Adapted from V8's collection-iterator.js: https://chromium.googlesource.com/v8/v8/+/main/test/mjsunit/es6/collection-iterator.js
1 parent 60cb2e1 commit 66c2d6d

4 files changed

Lines changed: 746 additions & 155 deletions

File tree

‎src/lualib/Map.ts‎

Lines changed: 167 additions & 81 deletions
Original file line numberDiff line numberDiff line change
@@ -1,15 +1,28 @@
1+
// Insertion-ordered Map using flat arrays with tombstone deletion and
2+
// V8-style version chain compaction. Deleted entries become nil (tombstones);
3+
// iterators skip them via idx++. Compaction creates new arrays and links
4+
// old → new at index 0; iterators transition lazily by adjusting their
5+
// index (subtracting holes before current position).
6+
//
7+
// Using integer-indexed arrays (orderedKeys/orderedValues) for the insertion
8+
// order leverages Lua's array part: sequential integer keys are stored in
9+
// contiguous memory, making iteration a simple pointer offset (~2-3 cycles)
10+
// rather than a hash table lookup (~15-50 cycles per step).
11+
//
12+
// Based on V8's OrderedHashTable (ordered-hash-table.cc: Rehash, Transition):
13+
// https://chromium.googlesource.com/v8/v8/+/main/src/objects/ordered-hash-table.cc
114
export class Map<K extends AnyNotNil, V> {
215
public static [Symbol.species] = Map;
316
public [Symbol.toStringTag] = "Map";
417

5-
private items = new LuaTable<K, V>();
618
public size = 0;
719

8-
// Key-order variables
9-
private firstKey: K | undefined;
10-
private lastKey: K | undefined;
11-
private nextKey = new LuaTable<K, K>();
12-
private previousKey = new LuaTable<K, K>();
20+
// Flat array storage (1-based indices for Lua)
21+
private keyIndex = new LuaTable<K, number>();
22+
private orderedKeys = new LuaTable<number, K>();
23+
private orderedValues = new LuaTable<number, V>();
24+
private nextSlot = 1;
25+
private deletedCount = 0;
1326

1427
constructor(entries?: Iterable<readonly [K, V]> | Array<readonly [K, V]>) {
1528
if (entries === undefined) return;
@@ -36,141 +49,214 @@ export class Map<K extends AnyNotNil, V> {
3649
}
3750

3851
public clear(): void {
39-
this.items = new LuaTable();
40-
this.nextKey = new LuaTable();
41-
this.previousKey = new LuaTable();
42-
this.firstKey = undefined;
43-
this.lastKey = undefined;
52+
this.keyIndex = new LuaTable();
53+
this.orderedKeys = new LuaTable();
54+
this.orderedValues = new LuaTable();
55+
this.nextSlot = 1;
4456
this.size = 0;
57+
this.deletedCount = 0;
4558
}
4659

4760
public delete(key: K): boolean {
48-
const contains = this.has(key);
49-
if (contains) {
50-
this.size--;
51-
52-
// Do order bookkeeping
53-
const next = this.nextKey.get(key);
54-
const previous = this.previousKey.get(key);
55-
if (next !== undefined && previous !== undefined) {
56-
this.nextKey.set(previous, next);
57-
this.previousKey.set(next, previous);
58-
} else if (next !== undefined) {
59-
this.firstKey = next;
60-
this.previousKey.set(next, undefined!);
61-
} else if (previous !== undefined) {
62-
this.lastKey = previous;
63-
this.nextKey.set(previous, undefined!);
61+
const idx = this.keyIndex.get(key);
62+
if (idx === undefined) return false;
63+
this.size--;
64+
this.deletedCount++;
65+
this.keyIndex.delete(key);
66+
this.orderedKeys.delete(idx);
67+
this.orderedValues.delete(idx);
68+
69+
if (this.deletedCount > this.size) {
70+
this.compact();
71+
}
72+
return true;
73+
}
74+
75+
// Compaction is needed because nextSlot grows monotonically — deleted
76+
// entries leave nil tombstones but Lua tables don't shrink on nil
77+
// assignment. Lua only resizes a table during rehash, and rehash only
78+
// triggers when a hash-part insert exhausts free nodes (ltable.c:
79+
// luaH_newkey → getfreepos → rehash). Since orderedKeys uses sequential
80+
// integer indices (array part), normal inserts rarely touch the hash
81+
// part, so rehash won't trigger naturally to reclaim the space.
82+
//
83+
// V8-style: copy live entries to new arrays, record hole positions in
84+
// the old array at negative indices, link old[0] → new. Active iterators
85+
// hold old arrays and transition lazily on next() by adjusting their
86+
// index (subtracting holes before current position).
87+
//
88+
// Index 0 and negative indices go to Lua's hash part (not array part),
89+
// so they don't conflict with the 1-based data entries.
90+
private compact(): void {
91+
const oldKeys = this.orderedKeys;
92+
const oldValues = this.orderedValues;
93+
const oldNextSlot = this.nextSlot;
94+
const newKeys = new LuaTable<number, K>();
95+
const newValues = new LuaTable<number, V>();
96+
let newSlot = 1;
97+
let holeCount = 0;
98+
99+
for (let i = 1; i < oldNextSlot; i++) {
100+
const k = oldKeys.get(i);
101+
if (k !== undefined) {
102+
newKeys.set(newSlot, k);
103+
newValues.set(newSlot, oldValues.get(i));
104+
this.keyIndex.set(k, newSlot);
105+
newSlot++;
64106
} else {
65-
this.firstKey = undefined;
66-
this.lastKey = undefined;
107+
holeCount++;
108+
oldKeys.set(-holeCount, i as any);
67109
}
68-
69-
this.nextKey.set(key, undefined!);
70-
this.previousKey.set(key, undefined!);
71110
}
72-
this.items.set(key, undefined!);
73111

74-
return contains;
112+
oldKeys.set(0, newKeys as any);
113+
oldValues.set(0, newValues as any);
114+
115+
this.orderedKeys = newKeys;
116+
this.orderedValues = newValues;
117+
this.nextSlot = newSlot;
118+
this.deletedCount = 0;
75119
}
76120

77121
public forEach(callback: (value: V, key: K, map: Map<K, V>) => any): void {
78122
for (const key of this.keys()) {
79-
callback(this.items.get(key), key, this);
123+
callback(this.orderedValues.get(this.keyIndex.get(key)), key, this);
80124
}
81125
}
82126

83127
public get(key: K): V | undefined {
84-
return this.items.get(key);
128+
const idx = this.keyIndex.get(key);
129+
if (idx === undefined) return undefined;
130+
return this.orderedValues.get(idx);
85131
}
86132

87133
public has(key: K): boolean {
88-
return this.nextKey.get(key) !== undefined || this.lastKey === key;
134+
return this.keyIndex.get(key) !== undefined;
89135
}
90136

91137
public set(key: K, value: V): this {
92-
const isNewValue = !this.has(key);
93-
if (isNewValue) {
138+
const existingIdx = this.keyIndex.get(key);
139+
if (existingIdx !== undefined) {
140+
this.orderedValues.set(existingIdx, value);
141+
} else {
94142
this.size++;
143+
const idx = this.nextSlot;
144+
this.nextSlot = idx + 1;
145+
this.keyIndex.set(key, idx);
146+
this.orderedKeys.set(idx, key);
147+
this.orderedValues.set(idx, value);
95148
}
96-
this.items.set(key, value);
97-
98-
// Do order bookkeeping
99-
if (this.firstKey === undefined) {
100-
this.firstKey = key;
101-
this.lastKey = key;
102-
} else if (isNewValue) {
103-
this.nextKey.set(this.lastKey!, key);
104-
this.previousKey.set(key, this.lastKey!);
105-
this.lastKey = key;
106-
}
107-
108149
return this;
109150
}
110151

111152
public [Symbol.iterator](): IterableIterator<[K, V]> {
112153
return this.entries();
113154
}
114155

156+
// entries/keys/values are intentionally kept inline (not refactored into
157+
// a shared helper) to avoid per-step function call overhead on this hot path.
115158
public entries(): IterableIterator<[K, V]> {
116-
const getFirstKey = () => this.firstKey;
117-
const { items, nextKey } = this;
118-
let key: K | undefined;
119-
let started = false;
159+
let keys = this.orderedKeys;
160+
let vals = this.orderedValues;
161+
const map = this; // eslint-disable-line @typescript-eslint/no-this-alias
162+
let idx = 1;
120163
return {
121164
[Symbol.iterator](): IterableIterator<[K, V]> {
122165
return this;
123166
},
124167
next(): IteratorResult<[K, V]> {
125-
if (!started) {
126-
started = true;
127-
key = getFirstKey();
128-
} else {
129-
key = nextKey.get(key!);
168+
while (keys.get(0) !== undefined) {
169+
let adj = 0;
170+
let h = 1;
171+
while (true) {
172+
const holePos = keys.get(-h) as any as number | undefined;
173+
if (holePos === undefined || holePos >= idx) break;
174+
adj++;
175+
h++;
176+
}
177+
idx -= adj;
178+
vals = vals.get(0) as any;
179+
keys = keys.get(0) as any;
180+
}
181+
while (idx < map.nextSlot && keys.get(idx) === undefined) {
182+
idx++;
183+
}
184+
if (idx >= map.nextSlot) {
185+
return { done: true, value: undefined! };
130186
}
131-
return { done: !key, value: [key!, items.get(key!)] as [K, V] };
187+
const i = idx;
188+
idx++;
189+
return { done: false, value: [keys.get(i), vals.get(i)] as [K, V] };
132190
},
133191
};
134192
}
135193

136194
public keys(): IterableIterator<K> {
137-
const getFirstKey = () => this.firstKey;
138-
const nextKey = this.nextKey;
139-
let key: K | undefined;
140-
let started = false;
195+
let keys = this.orderedKeys;
196+
const map = this; // eslint-disable-line @typescript-eslint/no-this-alias
197+
let idx = 1;
141198
return {
142199
[Symbol.iterator](): IterableIterator<K> {
143200
return this;
144201
},
145202
next(): IteratorResult<K> {
146-
if (!started) {
147-
started = true;
148-
key = getFirstKey();
149-
} else {
150-
key = nextKey.get(key!);
203+
while (keys.get(0) !== undefined) {
204+
let adj = 0;
205+
let h = 1;
206+
while (true) {
207+
const holePos = keys.get(-h) as any as number | undefined;
208+
if (holePos === undefined || holePos >= idx) break;
209+
adj++;
210+
h++;
211+
}
212+
idx -= adj;
213+
keys = keys.get(0) as any;
151214
}
152-
return { done: !key, value: key! };
215+
while (idx < map.nextSlot && keys.get(idx) === undefined) {
216+
idx++;
217+
}
218+
if (idx >= map.nextSlot) {
219+
return { done: true, value: undefined! };
220+
}
221+
const i = idx;
222+
idx++;
223+
return { done: false, value: keys.get(i) };
153224
},
154225
};
155226
}
156227

157228
public values(): IterableIterator<V> {
158-
const getFirstKey = () => this.firstKey;
159-
const { items, nextKey } = this;
160-
let key: K | undefined;
161-
let started = false;
229+
let keys = this.orderedKeys;
230+
let vals = this.orderedValues;
231+
const map = this; // eslint-disable-line @typescript-eslint/no-this-alias
232+
let idx = 1;
162233
return {
163234
[Symbol.iterator](): IterableIterator<V> {
164235
return this;
165236
},
166237
next(): IteratorResult<V> {
167-
if (!started) {
168-
started = true;
169-
key = getFirstKey();
170-
} else {
171-
key = nextKey.get(key!);
238+
while (keys.get(0) !== undefined) {
239+
let adj = 0;
240+
let h = 1;
241+
while (true) {
242+
const holePos = keys.get(-h) as any as number | undefined;
243+
if (holePos === undefined || holePos >= idx) break;
244+
adj++;
245+
h++;
246+
}
247+
idx -= adj;
248+
vals = vals.get(0) as any;
249+
keys = keys.get(0) as any;
250+
}
251+
while (idx < map.nextSlot && keys.get(idx) === undefined) {
252+
idx++;
253+
}
254+
if (idx >= map.nextSlot) {
255+
return { done: true, value: undefined! };
172256
}
173-
return { done: !key, value: items.get(key!) };
257+
const i = idx;
258+
idx++;
259+
return { done: false, value: vals.get(i) };
174260
},
175261
};
176262
}

0 commit comments

Comments
 (0)