Skip to content

Commit cb1c48b

Browse files
hyjorc1hyjorc1
committed
[JSC] Extend Array.from()'s Set fast path to cover set.keys()/.values()
https://bugs.webkit.org/show_bug.cgi?id=320575 rdar://183552376 Reviewed by Yusuke Suzuki. Array.from() already bypasses the generic iterator protocol for plain Array.from(set) and Array.from(map.keys()/.values()), reading internal hash-table storage directly. arrayConstructorPrivateFromFastWithoutMapFn had a JSMapIteratorType case but no JSSetIteratorType case, so Array.from(set.keys()) and Array.from(set.values()) never got the fast path Map already had. Add tryCreateArrayFromSetIterator(), a mirror of the existing tryCreateArrayFromMapIterator(). ToT Patched array-from-set-iterator 6.3581+-0.4507 ^ 2.9109+-0.1796 ^ definitely 2.1842x faster Tests: JSTests/microbenchmarks/array-from-set-iterator.js JSTests/stress/array-from-set-iterator-fast-path.js Canonical link: https://commits.webkit.org/318251@main
1 parent c45604e commit cb1c48b

3 files changed

Lines changed: 244 additions & 0 deletions

File tree

‎JSTests/microbenchmarks/array-from-set-iterator.js‎

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
class ObservableSet {
2+
constructor(values) {
3+
this._set = new Set(values);
4+
}
5+
keys() {
6+
return this._set.keys();
7+
}
8+
}
9+
10+
const set = new ObservableSet();
11+
for (let i = 0; i < 64; ++i)
12+
set._set.add(i);
13+
14+
let total = 0;
15+
for (let i = 0; i < 1e4; ++i)
16+
total += Array.from(set.keys()).length;

‎JSTests/stress/array-from-set-iterator-fast-path.js‎

Lines changed: 110 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,110 @@
1+
function shouldBe(actual, expected) {
2+
if (actual !== expected)
3+
throw new Error(`Expected ${expected} but got ${actual}`);
4+
}
5+
6+
function shouldBeArray(actual, expected) {
7+
shouldBe(actual.length, expected.length);
8+
for (let i = 0; i < expected.length; ++i)
9+
shouldBe(actual[i], expected[i]);
10+
}
11+
12+
// Basic correctness: keys() and values() are the exact same function (aliased in the spec),
13+
// both produce a JSSetIterator with IterationKind::Values.
14+
{
15+
let s = new Set([1, 2, 3]);
16+
shouldBeArray(Array.from(s.values()), [1, 2, 3]);
17+
shouldBeArray(Array.from(s.keys()), [1, 2, 3]);
18+
shouldBeArray(Array.from(s[Symbol.iterator]()), [1, 2, 3]);
19+
}
20+
21+
// entries() must not take this fast path -- it still yields [v, v] pairs correctly.
22+
{
23+
let s = new Set(['a', 'b']);
24+
let entries = Array.from(s.entries());
25+
shouldBe(entries.length, 2);
26+
shouldBeArray(entries[0], ['a', 'a']);
27+
shouldBeArray(entries[1], ['b', 'b']);
28+
}
29+
30+
// Partially-consumed iterator must resume from its real cursor, not restart from the beginning.
31+
{
32+
let s = new Set([10, 20, 30, 40]);
33+
let it = s.values();
34+
it.next();
35+
it.next();
36+
shouldBeArray(Array.from(it), [30, 40]);
37+
}
38+
39+
// Empty set iterator.
40+
{
41+
let s = new Set();
42+
shouldBeArray(Array.from(s.values()), []);
43+
}
44+
45+
// Already-exhausted iterator should yield an empty array, not throw.
46+
{
47+
let s = new Set([1]);
48+
let it = s.values();
49+
it.next();
50+
it.next();
51+
shouldBeArray(Array.from(it), []);
52+
}
53+
54+
// Own "return" property on the iterator instance forces the slow path
55+
// (per getDirectOffset(returnKeyword) inside setIteratorProtocolIsFastAndNonObservable).
56+
{
57+
let s = new Set([1, 2, 3]);
58+
let it = s.values();
59+
let called = false;
60+
it.return = function () { called = true; return { done: true, value: undefined }; };
61+
shouldBeArray(Array.from(it), [1, 2, 3]);
62+
shouldBe(called, false);
63+
}
64+
65+
// Overriding SetIteratorPrototype.next must be observed, i.e. the fast path must disengage.
66+
{
67+
let s = new Set([1, 2, 3]);
68+
let proto = Object.getPrototypeOf(s.values());
69+
let calls = 0;
70+
let origNext = proto.next;
71+
proto.next = function () { calls++; return origNext.call(this); };
72+
try {
73+
shouldBeArray(Array.from(s.values()), [1, 2, 3]);
74+
if (calls === 0)
75+
throw new Error('overridden next() was never called -- fast path incorrectly bypassed observable override');
76+
} finally {
77+
proto.next = origNext;
78+
}
79+
}
80+
81+
// A Set subclass's own .values()/.keys() iterator still fast-paths correctly: the guard checks
82+
// the iterator's own prototype, not the underlying Set's prototype chain.
83+
{
84+
class MySet extends Set { }
85+
let s = new MySet([5, 6, 7]);
86+
shouldBeArray(Array.from(s.values()), [5, 6, 7]);
87+
}
88+
89+
// Mutating the underlying set between manual next() calls and Array.from of the remaining
90+
// iterator must not crash and must reflect the live storage.
91+
{
92+
let s = new Set([1, 2]);
93+
let it = s.values();
94+
it.next();
95+
s.add(3);
96+
s.add(4);
97+
shouldBeArray(Array.from(it), [2, 3, 4]);
98+
}
99+
100+
// Mixed types exercise the contiguous (non-int32/non-double) storage path.
101+
{
102+
let s = new Set(['x', { a: 1 }, [1, 2], null, undefined]);
103+
shouldBe(Array.from(s.values()).length, 5);
104+
}
105+
106+
// All-double-representable values exercise the hasDouble() storage path.
107+
{
108+
let s = new Set([1.5, 2.5, 3.5]);
109+
shouldBeArray(Array.from(s.values()), [1.5, 2.5, 3.5]);
110+
}

‎Source/JavaScriptCore/runtime/ArrayConstructor.cpp‎

Lines changed: 118 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -33,8 +33,10 @@
3333
#include "JSMapIterator.h"
3434
#include "JSSet.h"
3535
#include "JSSetInlines.h"
36+
#include "JSSetIterator.h"
3637
#include "MapIteratorPrototypeInlines.h"
3738
#include "ProxyObject.h"
39+
#include "SetIteratorPrototypeInlines.h"
3840
#include <wtf/text/MakeString.h>
3941

4042
#include "VMInlines.h"
@@ -578,6 +580,115 @@ static JSArray* tryCreateArrayFromMapIterator(JSGlobalObject* globalObject, JSMa
578580
return JSArray::createWithButterfly(vm, nullptr, resultStructure, resultButterfly);
579581
}
580582

583+
static JSArray* tryCreateArrayFromSetIterator(JSGlobalObject* globalObject, JSSetIterator* setIterator)
584+
{
585+
VM& vm = globalObject->vm();
586+
auto scope = DECLARE_THROW_SCOPE(vm);
587+
588+
JSSet* set = setIterator->iteratedObject();
589+
if (!set) [[unlikely]]
590+
return nullptr;
591+
592+
ASSERT(setIterator->kind() == IterationKind::Keys || setIterator->kind() == IterationKind::Values);
593+
594+
JSCell* storageCell = setIterator->tryGetStorage();
595+
if (storageCell == vm.orderedHashTableSentinel())
596+
RELEASE_AND_RETURN(scope, constructEmptyArray(globalObject, nullptr));
597+
if (!storageCell) {
598+
storageCell = set->storageOrSentinel(vm);
599+
if (storageCell == vm.orderedHashTableSentinel())
600+
RELEASE_AND_RETURN(scope, constructEmptyArray(globalObject, nullptr));
601+
}
602+
603+
JSSet::Helper::Entry startEntry = setIterator->entry();
604+
auto* storage = uncheckedDowncast<JSSet::Storage>(storageCell);
605+
606+
IndexingType indexingType = IsArray;
607+
JSSet::Helper::Entry entry = startEntry;
608+
unsigned length = 0;
609+
610+
while (true) {
611+
JSCell* nextCell = JSSet::Helper::nextAndUpdateIterationEntry(vm, *storage, entry);
612+
if (nextCell == vm.orderedHashTableSentinel())
613+
break;
614+
615+
auto* currentStorage = uncheckedDowncast<JSSet::Storage>(nextCell);
616+
entry = JSSet::Helper::iterationEntry(*currentStorage) + 1;
617+
JSValue entryValue = JSSet::Helper::getIterationEntryKey(*currentStorage);
618+
619+
indexingType = leastUpperBoundOfIndexingTypeAndValue(indexingType, entryValue);
620+
++length;
621+
storage = currentStorage;
622+
}
623+
624+
if (!length)
625+
RELEASE_AND_RETURN(scope, constructEmptyArray(globalObject, nullptr));
626+
627+
Structure* resultStructure = globalObject->arrayStructureForIndexingTypeDuringAllocation(indexingType);
628+
IndexingType resultIndexingType = resultStructure->indexingType();
629+
630+
if (hasAnyArrayStorage(resultIndexingType)) [[unlikely]]
631+
return nullptr;
632+
633+
ASSERT(!globalObject->isHavingABadTime());
634+
635+
auto vectorLength = Butterfly::optimalContiguousVectorLength(resultStructure, length);
636+
void* memory = vm.auxiliarySpace().allocate(
637+
vm,
638+
Butterfly::totalSize(0, 0, true, vectorLength * sizeof(EncodedJSValue)),
639+
nullptr, AllocationFailureMode::ReturnNull);
640+
if (!memory) [[unlikely]]
641+
return nullptr;
642+
auto* resultButterfly = Butterfly::fromBase(memory, 0, 0);
643+
resultButterfly->setVectorLength(vectorLength);
644+
resultButterfly->setPublicLength(length);
645+
646+
storageCell = setIterator->tryGetStorage();
647+
if (!storageCell)
648+
storageCell = set->storageOrSentinel(vm);
649+
storage = uncheckedDowncast<JSSet::Storage>(storageCell);
650+
entry = startEntry;
651+
size_t i = 0;
652+
653+
if (hasDouble(resultIndexingType)) {
654+
while (true) {
655+
JSCell* nextCell = JSSet::Helper::nextAndUpdateIterationEntry(vm, *storage, entry);
656+
if (nextCell == vm.orderedHashTableSentinel())
657+
break;
658+
659+
auto* currentStorage = uncheckedDowncast<JSSet::Storage>(nextCell);
660+
entry = JSSet::Helper::iterationEntry(*currentStorage) + 1;
661+
JSValue value = JSSet::Helper::getIterationEntryKey(*currentStorage);
662+
663+
ASSERT(value.isNumber());
664+
resultButterfly->contiguousDouble().atUnsafe(i) = value.asNumber();
665+
++i;
666+
storage = currentStorage;
667+
}
668+
} else if (hasInt32(resultIndexingType) || hasContiguous(resultIndexingType)) {
669+
while (true) {
670+
JSCell* nextCell = JSSet::Helper::nextAndUpdateIterationEntry(vm, *storage, entry);
671+
if (nextCell == vm.orderedHashTableSentinel())
672+
break;
673+
674+
auto* currentStorage = uncheckedDowncast<JSSet::Storage>(nextCell);
675+
entry = JSSet::Helper::iterationEntry(*currentStorage) + 1;
676+
JSValue value = JSSet::Helper::getIterationEntryKey(*currentStorage);
677+
678+
resultButterfly->contiguous().atUnsafe(i).setWithoutWriteBarrier(value);
679+
++i;
680+
storage = currentStorage;
681+
}
682+
} else
683+
RELEASE_ASSERT_NOT_REACHED();
684+
685+
Butterfly::clearRange(resultIndexingType, resultButterfly, length, vectorLength);
686+
687+
setIterator->close(vm);
688+
689+
return JSArray::createWithButterfly(vm, nullptr, resultStructure, resultButterfly);
690+
}
691+
581692
JSC_DEFINE_HOST_FUNCTION(arrayConstructorPrivateFromFastWithoutMapFn, (JSGlobalObject* globalObject, CallFrame* callFrame))
582693
{
583694
VM& vm = globalObject->vm();
@@ -640,6 +751,13 @@ JSC_DEFINE_HOST_FUNCTION(arrayConstructorPrivateFromFastWithoutMapFn, (JSGlobalO
640751
result = tryCreateArrayFromMapIterator(globalObject, mapIterator);
641752
RETURN_IF_EXCEPTION(scope, { });
642753
}
754+
} else if (items && items.isCell() && items.asCell()->type() == JSSetIteratorType) {
755+
// For `Array.from(set.keys())`, `Array.from(set.values())`
756+
auto* setIterator = uncheckedDowncast<JSSetIterator>(items.asCell());
757+
if (setIterator->kind() != IterationKind::Entries && setIteratorProtocolIsFastAndNonObservable(vm, setIterator)) [[likely]] {
758+
result = tryCreateArrayFromSetIterator(globalObject, setIterator);
759+
RETURN_IF_EXCEPTION(scope, { });
760+
}
643761
}
644762
if (result)
645763
return JSValue::encode(result);

0 commit comments

Comments
 (0)