[dart2wasm] Better handling of list/map/set literals
If the literals are
* empty: call function with zero arguments
* non-empty: call function taking `WasmArray<Object?>`
=> This avoids making a call for each element we add.
Reorganize the map/set mixins:
* pull out the `createIndex` into it's own mixin
* make mutable set/map implementations use that mixin
* remove compiler-knowledge about how to create hash mask
(instead set the hashmask field in `_createIndex()`)
=> Function creating map/set from `WasmArray<Object?>` can create index
=> Allows the above
Outline functions (for now only for list/map/set literal creation
functions):
* Often many call sites use literals with instantiated types
* Make outlined functions that will populate those instantiated types
and forward the arguments
This turns e.g. `<A, B>{}` (if `A`/`B` are instantiated, e.g. `int`)
global.get A
global.get B
call _WasmDefaultMap._default
into
call createEmpty<A, B>
createEmpty<A, B>:
global.get A
global.get B
call _WasmDefaultMap._default
All together this
* reduces flute size by a bit more than 0.5%
* makes some benchmarks faster
Change-Id: I13c7e6060470d74769a3d49816671aceb2cd3aab
Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/356500
Reviewed-by: Ömer Ağacan <omersa@google.com>
Commit-Queue: Martin Kustermann <kustermann@google.com>
diff --git a/pkg/dart2wasm/lib/code_generator.dart b/pkg/dart2wasm/lib/code_generator.dart
index 306fd4b..224258e 100644
--- a/pkg/dart2wasm/lib/code_generator.dart
+++ b/pkg/dart2wasm/lib/code_generator.dart
@@ -2921,31 +2921,33 @@
@override
w.ValueType visitListLiteral(ListLiteral node, w.ValueType expectedType) {
- return makeListFromExpressions(node.expressions, node.typeArgument,
- isGrowable: true);
- }
+ final useSharedCreator = types.isTypeConstant(node.typeArgument);
- /// Allocate a Dart `List` with element type [typeArg], length [length] and
- /// push the list to the stack.
- ///
- /// [generateItem] will be called [length] times to initialize list elements.
- ///
- /// Concrete type of the list will be `_GrowableList` if [isGrowable] is
- /// true, `_List` otherwise.
- w.ValueType makeList(DartType typeArg, int length,
- void Function(w.ValueType, int) generateItem,
- {bool isGrowable = false}) {
- return translator.makeList(
- function, (b) => types.makeType(this, typeArg), length, generateItem,
- isGrowable: isGrowable);
- }
+ final passType = !useSharedCreator;
+ final passArray = node.expressions.isNotEmpty;
- w.ValueType makeListFromExpressions(
- List<Expression> expressions, DartType typeArg,
- {bool isGrowable = false}) =>
- makeList(typeArg, expressions.length,
- (w.ValueType elementType, int i) => wrap(expressions[i], elementType),
- isGrowable: isGrowable);
+ final targetReference = passArray
+ ? translator.growableListFromWasmArray.reference
+ : translator.growableListEmpty.reference;
+
+ final w.BaseFunction target = useSharedCreator
+ ? translator.partialInstantiator.getOneTypeArgumentForwarder(
+ targetReference,
+ node.typeArgument,
+ 'create${passArray ? '' : 'Empty'}List<${node.typeArgument}>')
+ : translator.functions.getFunction(targetReference);
+
+ if (passType) {
+ types.makeType(this, node.typeArgument);
+ }
+ if (passArray) {
+ makeArrayFromExpressions(node.expressions,
+ translator.coreTypes.objectRawType(Nullability.nullable));
+ }
+
+ b.call(target);
+ return target.type.outputs.single;
+ }
w.ValueType makeArrayFromExpressions(
List<Expression> expressions, InterfaceType elementType) {
@@ -2963,55 +2965,71 @@
@override
w.ValueType visitMapLiteral(MapLiteral node, w.ValueType expectedType) {
- types.makeType(this, node.keyType);
- types.makeType(this, node.valueType);
- w.ValueType factoryReturnType =
- call(translator.mapFactory.reference).single;
- if (node.entries.isEmpty) {
- return factoryReturnType;
+ final useSharedCreator = types.isTypeConstant(node.keyType) &&
+ types.isTypeConstant(node.valueType);
+
+ final passTypes = !useSharedCreator;
+ final passArray = node.entries.isNotEmpty;
+
+ final targetReference = passArray
+ ? translator.mapFromWasmArray.reference
+ : translator.mapFactory.reference;
+
+ final w.BaseFunction target = useSharedCreator
+ ? translator.partialInstantiator.getTwoTypeArgumentForwarder(
+ targetReference,
+ node.keyType,
+ node.valueType,
+ 'create${passArray ? '' : 'Empty'}Map<${node.keyType}, ${node.valueType}>')
+ : translator.functions.getFunction(targetReference);
+
+ if (passTypes) {
+ types.makeType(this, node.keyType);
+ types.makeType(this, node.valueType);
}
- w.FunctionType mapPutType =
- translator.functions.getFunctionType(translator.mapPut.reference);
- w.ValueType putReceiverType = mapPutType.inputs[0];
- w.ValueType putKeyType = mapPutType.inputs[1];
- w.ValueType putValueType = mapPutType.inputs[2];
- w.Local mapLocal = addLocal(putReceiverType);
- translator.convertType(function, factoryReturnType, mapLocal.type);
- b.local_set(mapLocal);
- for (MapLiteralEntry entry in node.entries) {
- b.local_get(mapLocal);
- wrap(entry.key, putKeyType);
- wrap(entry.value, putValueType);
- call(translator.mapPut.reference);
- b.drop();
+ if (passArray) {
+ makeArray(translator.nullableObjectArrayType, 2 * node.entries.length,
+ (elementType, elementIndex) {
+ final index = elementIndex ~/ 2;
+ final entry = node.entries[index];
+ if (elementIndex % 2 == 0) {
+ wrap(entry.key, elementType);
+ } else {
+ wrap(entry.value, elementType);
+ }
+ });
}
- b.local_get(mapLocal);
- return mapLocal.type;
+ b.call(target);
+ return target.type.outputs.single;
}
@override
w.ValueType visitSetLiteral(SetLiteral node, w.ValueType expectedType) {
- types.makeType(this, node.typeArgument);
- w.ValueType factoryReturnType =
- call(translator.setFactory.reference).single;
- if (node.expressions.isEmpty) {
- return factoryReturnType;
+ final useSharedCreator = types.isTypeConstant(node.typeArgument);
+
+ final passType = !useSharedCreator;
+ final passArray = node.expressions.isNotEmpty;
+
+ final targetReference = passArray
+ ? translator.setFromWasmArray.reference
+ : translator.setFactory.reference;
+
+ final w.BaseFunction target = useSharedCreator
+ ? translator.partialInstantiator.getOneTypeArgumentForwarder(
+ targetReference,
+ node.typeArgument,
+ 'create${passArray ? '' : 'Empty'}Set<${node.typeArgument}>')
+ : translator.functions.getFunction(targetReference);
+
+ if (passType) {
+ types.makeType(this, node.typeArgument);
}
- w.FunctionType setAddType =
- translator.functions.getFunctionType(translator.setAdd.reference);
- w.ValueType addReceiverType = setAddType.inputs[0];
- w.ValueType addKeyType = setAddType.inputs[1];
- w.Local setLocal = addLocal(addReceiverType);
- translator.convertType(function, factoryReturnType, setLocal.type);
- b.local_set(setLocal);
- for (Expression element in node.expressions) {
- b.local_get(setLocal);
- wrap(element, addKeyType);
- call(translator.setAdd.reference);
- b.drop();
+ if (passArray) {
+ makeArrayFromExpressions(node.expressions,
+ translator.coreTypes.objectRawType(Nullability.nullable));
}
- b.local_get(setLocal);
- return setLocal.type;
+ b.call(target);
+ return target.type.outputs.single;
}
@override
diff --git a/pkg/dart2wasm/lib/constants.dart b/pkg/dart2wasm/lib/constants.dart
index da3b84a..e9061c7262 100644
--- a/pkg/dart2wasm/lib/constants.dart
+++ b/pkg/dart2wasm/lib/constants.dart
@@ -2,7 +2,6 @@
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.
-import 'dart:math';
import 'dart:typed_data';
import 'package:kernel/ast.dart';
@@ -519,8 +518,7 @@
_uninitializedHashBaseIndexConstant,
// _hashMask
- translator.hashFieldBaseHashMaskField.fieldReference:
- IntConstant(_computeHashMask(constant.entries.length)),
+ translator.hashFieldBaseHashMaskField.fieldReference: IntConstant(0),
// _data
translator.hashFieldBaseDataField.fieldReference:
@@ -553,8 +551,7 @@
_uninitializedHashBaseIndexConstant,
// _hashMask
- translator.hashFieldBaseHashMaskField.fieldReference:
- IntConstant(_computeHashMask(constant.entries.length)),
+ translator.hashFieldBaseHashMaskField.fieldReference: IntConstant(0),
// _data
translator.hashFieldBaseDataField.fieldReference:
@@ -576,17 +573,6 @@
return ensureConstant(instanceConstant);
}
- int _computeHashMask(int entries) {
- // This computation of the hash mask follows the computations in
- // [_ImmutableLinkedHashMapMixin._createIndex],
- // [_ImmutableLinkedHashSetMixin._createIndex] and
- // [_HashBase._indexSizeToHashMask].
- const int initialIndexSize = 8;
- final int indexSize = max(entries * 2, initialIndexSize);
- final int hashMask = (1 << (31 - (indexSize - 1).bitLength)) - 1;
- return hashMask;
- }
-
@override
ConstantInfo? visitStaticTearOffConstant(StaticTearOffConstant constant) {
Procedure member = constant.targetReference.asProcedure;
diff --git a/pkg/dart2wasm/lib/kernel_nodes.dart b/pkg/dart2wasm/lib/kernel_nodes.dart
index d9ac961..9f7ac52 100644
--- a/pkg/dart2wasm/lib/kernel_nodes.dart
+++ b/pkg/dart2wasm/lib/kernel_nodes.dart
@@ -174,20 +174,16 @@
// dart:collection procedures and fields
late final Procedure mapFactory =
index.getProcedure("dart:collection", "LinkedHashMap", "_default");
- late final Procedure mapPut = index
- .getClass("dart:collection", "_WasmDefaultMap")
- .superclass! // _LinkedHashMapMixin<K, V>
- .procedures
- .firstWhere((p) => p.name.text == "[]=");
+ late final Procedure mapFromWasmArray =
+ index.getProcedure("dart:collection", "_WasmDefaultMap", "fromWasmArray");
late final Procedure setFactory =
index.getProcedure("dart:collection", "LinkedHashSet", "_default");
- late final Procedure setAdd = index
- .getClass("dart:collection", "_WasmDefaultSet")
- .superclass! // _LinkedHashSetMixin<K, V>
- .procedures
- .firstWhere((p) => p.name.text == "add");
- late final Procedure growableListAdd =
- index.getProcedure("dart:core", "_GrowableList", "add");
+ late final Procedure setFromWasmArray =
+ index.getProcedure("dart:collection", "_WasmDefaultSet", "fromWasmArray");
+ late final Procedure growableListEmpty =
+ index.getProcedure("dart:core", "_GrowableList", "empty");
+ late final Constructor growableListFromWasmArray =
+ index.getConstructor("dart:core", "_GrowableList", "_withData");
late final Procedure hashImmutableIndexNullable = index.getProcedure(
"dart:collection", "_HashAbstractImmutableBase", "get:_indexNullable");
late final Field hashFieldBaseIndexField =
diff --git a/pkg/dart2wasm/lib/translator.dart b/pkg/dart2wasm/lib/translator.dart
index 07378aa..d3a89ae 100644
--- a/pkg/dart2wasm/lib/translator.dart
+++ b/pkg/dart2wasm/lib/translator.dart
@@ -147,6 +147,9 @@
late final w.RefType nullableObjectArrayTypeRef =
w.RefType.def(nullableObjectArrayType, nullable: false);
+ late final PartialInstantiator partialInstantiator =
+ PartialInstantiator(this);
+
/// Dart types that have specialized Wasm representations.
late final Map<Class, w.StorageType> builtinTypes = {
coreTypes.boolClass: w.NumType.i32,
@@ -994,29 +997,6 @@
return null;
}
- w.ValueType makeList(
- w.FunctionBuilder function,
- void Function(w.InstructionsBuilder b) generateType,
- int length,
- void Function(w.ValueType, int) generateItem,
- {bool isGrowable = false}) {
- final b = function.body;
-
- final Class cls = isGrowable ? growableListClass : fixedLengthListClass;
- final ClassInfo info = classInfo[cls]!;
- functions.recordClassAllocation(info.classId);
- final w.ArrayType arrayType = listArrayType;
-
- b.i32_const(info.classId);
- b.i32_const(initialIdentityHash);
- generateType(b);
- b.i64_const(length);
- makeArray(function, arrayType, length, generateItem);
- b.struct_new(info.struct);
-
- return info.nonNullableType;
- }
-
w.ValueType makeArray(w.FunctionBuilder function, w.ArrayType arrayType,
int length, void Function(w.ValueType, int) generateItem) {
final b = function.body;
@@ -1356,3 +1336,93 @@
node.visitChildren(this);
}
}
+
+/// Creates forwarders for generic functions where the caller passes a constant
+/// type argument.
+///
+/// Let's say we have
+///
+/// foo<T>(args) => ...;
+///
+/// and 3 call sites
+///
+/// foo<int>(args)
+/// foo<int>(args)
+/// foo<double>(args)
+///
+/// the callsites can instead call a forwarder
+///
+/// fooInt(args)
+/// fooInt(args)
+/// fooDouble(args)
+///
+/// fooInt(args) => foo<int>(args)
+/// fooDouble(args) => foo<double>(args)
+///
+/// This saves code size on the call site.
+class PartialInstantiator {
+ final Translator translator;
+
+ final Map<(Reference, DartType), w.BaseFunction> _oneTypeArgument = {};
+ final Map<(Reference, DartType, DartType), w.BaseFunction> _twoTypeArguments =
+ {};
+
+ PartialInstantiator(this.translator);
+
+ w.BaseFunction getOneTypeArgumentForwarder(
+ Reference target, DartType type, String name) {
+ assert(translator.types.isTypeConstant(type));
+
+ return _oneTypeArgument.putIfAbsent((target, type), () {
+ final wasmTarget = translator.functions.getFunction(target);
+
+ final function = translator.m.functions.define(
+ translator.m.types.defineFunction(
+ [...wasmTarget.type.inputs.skip(1)],
+ wasmTarget.type.outputs,
+ ),
+ name);
+ final b = function.body;
+ translator.constants.instantiateConstant(function, b,
+ TypeLiteralConstant(type), translator.types.nonNullableTypeType);
+ for (int i = 1; i < wasmTarget.type.inputs.length; ++i) {
+ b.local_get(b.locals[i - 1]);
+ }
+ b.call(wasmTarget);
+ b.return_();
+ b.end();
+
+ return function;
+ });
+ }
+
+ w.BaseFunction getTwoTypeArgumentForwarder(
+ Reference target, DartType type1, DartType type2, String name) {
+ assert(translator.types.isTypeConstant(type1));
+ assert(translator.types.isTypeConstant(type2));
+
+ return _twoTypeArguments.putIfAbsent((target, type1, type2), () {
+ final wasmTarget = translator.functions.getFunction(target);
+
+ final function = translator.m.functions.define(
+ translator.m.types.defineFunction(
+ [...wasmTarget.type.inputs.skip(2)],
+ wasmTarget.type.outputs,
+ ),
+ name);
+ final b = function.body;
+ translator.constants.instantiateConstant(function, b,
+ TypeLiteralConstant(type1), translator.types.nonNullableTypeType);
+ translator.constants.instantiateConstant(function, b,
+ TypeLiteralConstant(type2), translator.types.nonNullableTypeType);
+ for (int i = 2; i < wasmTarget.type.inputs.length; ++i) {
+ b.local_get(b.locals[i - 2]);
+ }
+ b.call(wasmTarget);
+ b.return_();
+ b.end();
+
+ return function;
+ });
+ }
+}
diff --git a/pkg/dart2wasm/lib/types.dart b/pkg/dart2wasm/lib/types.dart
index 15aa86e..ba40432 100644
--- a/pkg/dart2wasm/lib/types.dart
+++ b/pkg/dart2wasm/lib/types.dart
@@ -287,23 +287,23 @@
return typeNamesType;
}
- bool _isTypeConstant(DartType type) {
+ bool isTypeConstant(DartType type) {
return type is DynamicType ||
type is VoidType ||
type is NeverType ||
type is NullType ||
- type is FutureOrType && _isTypeConstant(type.typeArgument) ||
+ type is FutureOrType && isTypeConstant(type.typeArgument) ||
(type is FunctionType &&
- type.typeParameters.every((p) => _isTypeConstant(p.bound)) &&
- _isTypeConstant(type.returnType) &&
- type.positionalParameters.every(_isTypeConstant) &&
- type.namedParameters.every((n) => _isTypeConstant(n.type))) ||
- type is InterfaceType && type.typeArguments.every(_isTypeConstant) ||
+ type.typeParameters.every((p) => isTypeConstant(p.bound)) &&
+ isTypeConstant(type.returnType) &&
+ type.positionalParameters.every(isTypeConstant) &&
+ type.namedParameters.every((n) => isTypeConstant(n.type))) ||
+ type is InterfaceType && type.typeArguments.every(isTypeConstant) ||
(type is RecordType &&
- type.positional.every(_isTypeConstant) &&
- type.named.every((n) => _isTypeConstant(n.type))) ||
+ type.positional.every(isTypeConstant) &&
+ type.named.every((n) => isTypeConstant(n.type))) ||
type is StructuralParameterType ||
- type is ExtensionType && _isTypeConstant(type.extensionTypeErasure);
+ type is ExtensionType && isTypeConstant(type.extensionTypeErasure);
}
Class classForType(DartType type) {
@@ -359,7 +359,7 @@
/// Allocates a `WasmArray<_Type>` from [types] and pushes it to the
/// stack.
void _makeTypeArray(CodeGenerator codeGen, Iterable<DartType> types) {
- if (types.every(_isTypeConstant)) {
+ if (types.every(isTypeConstant)) {
translator.constants.instantiateConstant(codeGen.function, codeGen.b,
translator.constants.makeTypeArray(types), typeArrayExpectedType);
} else {
@@ -457,7 +457,7 @@
b.i64_const(type.requiredParameterCount);
// WasmArray<_NamedParameter> namedParameters
- if (type.namedParameters.every((n) => _isTypeConstant(n.type))) {
+ if (type.namedParameters.every((n) => isTypeConstant(n.type))) {
translator.constants.instantiateConstant(
codeGen.function,
b,
@@ -469,7 +469,7 @@
namedParameterClass.constructors.single;
List<Expression> expressions = [];
for (NamedType n in type.namedParameters) {
- expressions.add(_isTypeConstant(n.type)
+ expressions.add(isTypeConstant(n.type)
? ConstantExpression(
translator.constants.makeNamedParameterConstant(n),
namedParameterType)
@@ -495,7 +495,7 @@
// Always ensure type is normalized before making a type.
type = normalize(type);
final b = codeGen.b;
- if (_isTypeConstant(type)) {
+ if (isTypeConstant(type)) {
translator.constants.instantiateConstant(
codeGen.function, b, TypeLiteralConstant(type), nonNullableTypeType);
return nonNullableTypeType;
diff --git a/sdk/lib/_internal/wasm/lib/compact_hash.dart b/sdk/lib/_internal/wasm/lib/compact_hash.dart
index e89480b..768ed52 100644
--- a/sdk/lib/_internal/wasm/lib/compact_hash.dart
+++ b/sdk/lib/_internal/wasm/lib/compact_hash.dart
@@ -211,6 +211,7 @@
_OperatorEqualsAndCanonicalHashCode,
_LinkedHashMapMixin<K, V>,
_UnmodifiableMapMixin<K, V>,
+ _MapCreateIndexMixin<K, V>,
_ImmutableLinkedHashMapMixin<K, V>
implements LinkedHashMap<K, V> {
factory _ConstMap._uninstantiable() {
@@ -219,28 +220,16 @@
}
}
-mixin _ImmutableLinkedHashMapMixin<K, V>
- on _LinkedHashMapMixin<K, V>, _HashFieldBase {
- bool containsKey(Object? key) {
- if (identical(_index, _uninitializedHashBaseIndex)) {
- _createIndex();
- }
- return super.containsKey(key);
- }
+mixin _MapCreateIndexMixin<K, V> on _LinkedHashMapMixin<K, V>, _HashFieldBase {
+ void _createIndex(bool canContainDuplicates) {
+ assert(_index == _uninitializedHashBaseIndex);
+ assert(_hashMask == _HashBase._UNINITIALIZED_HASH_MASK);
+ assert(_deletedKeys == 0);
- V? operator [](Object? key) {
- if (identical(_index, _uninitializedHashBaseIndex)) {
- _createIndex();
- }
- return super[key];
- }
-
- void _createIndex() {
final size =
_roundUpToPowerOfTwo(max(_data.length, _HashBase._INITIAL_INDEX_SIZE));
final newIndex = WasmArray<WasmI32>.filled(size, const WasmI32(0));
- final hashMask = _HashBase._indexSizeToHashMask(size);
- assert(_hashMask == hashMask);
+ final hashMask = _hashMask = _HashBase._indexSizeToHashMask(size);
for (int j = 0; j < _usedData; j += 2) {
final key = _data[j] as K;
@@ -249,6 +238,18 @@
final hashPattern = _HashBase._hashPattern(fullHash, hashMask, size);
final d =
_findValueOrInsertPoint(key, fullHash, hashPattern, size, newIndex);
+
+ if (d > 0 && canContainDuplicates) {
+ // Replace the existing entry.
+ _data[d] = _data[j + 1];
+
+ // Mark this as a free slot.
+ _HashBase._setDeletedAt(_data, j);
+ _HashBase._setDeletedAt(_data, j + 1);
+ _deletedKeys++;
+ continue;
+ }
+
// We just allocated the index, so we should not find this key in it yet.
assert(d <= 0);
@@ -263,6 +264,22 @@
// Publish new index, uses store release semantics.
_index = newIndex;
}
+}
+
+mixin _ImmutableLinkedHashMapMixin<K, V> on _MapCreateIndexMixin<K, V> {
+ bool containsKey(Object? key) {
+ if (identical(_index, _uninitializedHashBaseIndex)) {
+ _createIndex(false);
+ }
+ return super.containsKey(key);
+ }
+
+ V? operator [](Object? key) {
+ if (identical(_index, _uninitializedHashBaseIndex)) {
+ _createIndex(false);
+ }
+ return super[key];
+ }
Iterable<K> get keys =>
_CompactIterableImmutable<K>(this, _data, _usedData, -2, 2);
@@ -842,6 +859,7 @@
_OperatorEqualsAndCanonicalHashCode,
_LinkedHashSetMixin<E>,
_UnmodifiableSetMixin<E>,
+ _SetCreateIndexMixin<E>,
_ImmutableLinkedHashSetMixin<E>
implements LinkedHashSet<E> {
factory _ConstSet._uninstantiable() {
@@ -857,63 +875,78 @@
Set<E> toSet() => _Set<E>()..addAll(this);
}
-mixin _ImmutableLinkedHashSetMixin<E>
+mixin _SetCreateIndexMixin<E>
on Set<E>, _LinkedHashSetMixin<E>, _HashFieldBase {
+ void _createIndex(bool canContainDuplicates) {
+ assert(_index == _uninitializedHashBaseIndex);
+ assert(_hashMask == _HashBase._UNINITIALIZED_HASH_MASK);
+ assert(_deletedKeys == 0);
+
+ final size = _roundUpToPowerOfTwo(
+ max(_data.length * 2, _HashBase._INITIAL_INDEX_SIZE));
+ final index = WasmArray<WasmI32>.filled(size, const WasmI32(0));
+ final hashMask = _hashMask = _HashBase._indexSizeToHashMask(size);
+
+ final sizeMask = size - 1;
+ final maxEntries = size >> 1;
+
+ for (int j = 0; j < _usedData; j++) {
+ next:
+ {
+ final key = _data[j];
+
+ final fullHash = _hashCode(key);
+ final hashPattern = _HashBase._hashPattern(fullHash, hashMask, size);
+
+ int i = _HashBase._firstProbe(fullHash, sizeMask);
+ int pair = index.readUnsigned(i);
+ while (pair != _HashBase._UNUSED_PAIR) {
+ assert(pair != _HashBase._DELETED_PAIR);
+
+ final int d = hashPattern ^ pair;
+ if (d < maxEntries) {
+ // We should not already find an entry in the index.
+ if (canContainDuplicates && _equals(key, _data[d])) {
+ // Exists already, skip this entry.
+ _HashBase._setDeletedAt(_data, j);
+ _deletedKeys++;
+ break next;
+ } else {
+ assert(!_equals(key, _data[d]));
+ }
+ }
+
+ i = _HashBase._nextProbe(i, sizeMask);
+ pair = index.readUnsigned(i);
+ }
+
+ final int insertionPoint = i;
+ assert(1 <= hashPattern && hashPattern < (1 << 32));
+ assert((hashPattern & j) == 0);
+ index[insertionPoint] = WasmI32.fromInt(hashPattern | j);
+ }
+ }
+
+ // Publish new index, uses store release semantics.
+ _index = index;
+ }
+}
+
+mixin _ImmutableLinkedHashSetMixin<E> on _SetCreateIndexMixin<E> {
E? lookup(Object? key) {
if (identical(_index, _uninitializedHashBaseIndex)) {
- _createIndex();
+ _createIndex(false);
}
return super.lookup(key);
}
bool contains(Object? key) {
if (identical(_index, _uninitializedHashBaseIndex)) {
- _createIndex();
+ _createIndex(false);
}
return super.contains(key);
}
- void _createIndex() {
- final size = _roundUpToPowerOfTwo(
- max(_data.length * 2, _HashBase._INITIAL_INDEX_SIZE));
- final index = WasmArray<WasmI32>.filled(size, const WasmI32(0));
- final hashMask = _HashBase._indexSizeToHashMask(size);
- assert(_hashMask == hashMask);
-
- final sizeMask = size - 1;
- final maxEntries = size >> 1;
-
- for (int j = 0; j < _usedData; j++) {
- final key = _data[j];
-
- final fullHash = _hashCode(key);
- final hashPattern = _HashBase._hashPattern(fullHash, hashMask, size);
-
- int i = _HashBase._firstProbe(fullHash, sizeMask);
- int pair = index.readUnsigned(i);
- while (pair != _HashBase._UNUSED_PAIR) {
- assert(pair != _HashBase._DELETED_PAIR);
-
- final int d = hashPattern ^ pair;
- if (d < maxEntries) {
- // We should not already find an entry in the index.
- assert(!_equals(key, _data[d]));
- }
-
- i = _HashBase._nextProbe(i, sizeMask);
- pair = index.readUnsigned(i);
- }
-
- final int insertionPoint = i;
- assert(1 <= hashPattern && hashPattern < (1 << 32));
- assert((hashPattern & j) == 0);
- index[insertionPoint] = WasmI32.fromInt(hashPattern | j);
- }
-
- // Publish new index, uses store release semantics.
- _index = index;
- }
-
Iterator<E> get iterator =>
_CompactIteratorImmutable<E>(this, _data, _usedData, -1, 1);
}
diff --git a/sdk/lib/_internal/wasm/lib/growable_list.dart b/sdk/lib/_internal/wasm/lib/growable_list.dart
index f824469..321f264 100644
--- a/sdk/lib/_internal/wasm/lib/growable_list.dart
+++ b/sdk/lib/_internal/wasm/lib/growable_list.dart
@@ -8,6 +8,7 @@
class _GrowableList<E> extends _ModifiableList<E> {
_GrowableList._(int length, int capacity) : super(length, capacity);
+ @pragma("wasm:entry-point")
_GrowableList._withData(WasmArray<Object?> data)
: super._withData(data.length, data);
@@ -21,6 +22,7 @@
// Specialization of List.empty constructor for growable == true.
// Used by pkg/dart2wasm/lib/list_factory_specializer.dart.
+ @pragma("wasm:entry-point")
factory _GrowableList.empty() => _GrowableList(0);
// Specialization of List.filled constructor for growable == true.
diff --git a/sdk/lib/_internal/wasm/lib/hash_factories.dart b/sdk/lib/_internal/wasm/lib/hash_factories.dart
index 0828ab4..a1c8b5a 100644
--- a/sdk/lib/_internal/wasm/lib/hash_factories.dart
+++ b/sdk/lib/_internal/wasm/lib/hash_factories.dart
@@ -3,6 +3,7 @@
// BSD-style license that can be found in the LICENSE file.
import "dart:_internal" show patch;
+import "dart:_wasm";
import "dart:typed_data" show Uint32List;
@@ -28,7 +29,7 @@
}
@pragma("wasm:entry-point")
- factory LinkedHashMap._default() => _WasmDefaultMap<K, V>();
+ static _WasmDefaultMap<K, V> _default<K, V>() => _WasmDefaultMap<K, V>();
@patch
factory LinkedHashMap.identity() => _CompactLinkedIdentityHashMap<K, V>();
@@ -56,7 +57,7 @@
}
@pragma("wasm:entry-point")
- factory LinkedHashSet._default() => _WasmDefaultSet<E>();
+ static _WasmDefaultSet<E> _default<E>() => _WasmDefaultSet<E>();
@patch
factory LinkedHashSet.identity() => _CompactLinkedIdentityHashSet<E>();
@@ -68,9 +69,25 @@
MapMixin<K, V>,
_HashBase,
_OperatorEqualsAndHashCode,
- _LinkedHashMapMixin<K, V>
+ _LinkedHashMapMixin<K, V>,
+ _MapCreateIndexMixin<K, V>
implements LinkedHashMap<K, V> {
@pragma("wasm:entry-point")
+ static _WasmDefaultMap<K, V> fromWasmArray<K, V>(WasmArray<Object?> data) {
+ final map = _WasmDefaultMap<K, V>();
+ assert(map._index == _uninitializedHashBaseIndex);
+ assert(map._hashMask == _HashBase._UNINITIALIZED_HASH_MASK);
+ assert(map._data == _uninitializedHashBaseData);
+ assert(map._usedData == 0);
+ assert(map._deletedKeys == 0);
+
+ map._data = data;
+ map._usedData = data.length;
+ map._createIndex(true);
+
+ return map;
+ }
+
void operator []=(K key, V value);
}
@@ -80,9 +97,25 @@
SetMixin<E>,
_HashBase,
_OperatorEqualsAndHashCode,
- _LinkedHashSetMixin<E>
+ _LinkedHashSetMixin<E>,
+ _SetCreateIndexMixin<E>
implements LinkedHashSet<E> {
@pragma("wasm:entry-point")
+ static _WasmDefaultSet<E> fromWasmArray<E>(WasmArray<Object?> data) {
+ final map = _WasmDefaultSet<E>();
+ assert(map._index == _uninitializedHashBaseIndex);
+ assert(map._hashMask == _HashBase._UNINITIALIZED_HASH_MASK);
+ assert(map._data == _uninitializedHashBaseData);
+ assert(map._usedData == 0);
+ assert(map._deletedKeys == 0);
+
+ map._data = data;
+ map._usedData = data.length;
+ map._createIndex(true);
+
+ return map;
+ }
+
bool add(E key);
Set<R> cast<R>() => Set.castFrom<E, R>(this, newSet: _newEmpty);
@@ -99,6 +132,7 @@
_HashBase,
_OperatorEqualsAndHashCode,
_LinkedHashMapMixin<K, V>,
+ _MapCreateIndexMixin<K, V>,
_UnmodifiableMapMixin<K, V>,
_ImmutableLinkedHashMapMixin<K, V>
implements LinkedHashMap<K, V> {}
@@ -110,13 +144,14 @@
_HashBase,
_OperatorEqualsAndHashCode,
_LinkedHashSetMixin<E>,
+ _SetCreateIndexMixin<E>,
_UnmodifiableSetMixin<E>,
_ImmutableLinkedHashSetMixin<E>
implements LinkedHashSet<E> {
Set<R> cast<R>() => Set.castFrom<E, R>(this, newSet: _newEmpty);
- static Set<R> _newEmpty<R>() => LinkedHashSet<R>._default();
+ static Set<R> _newEmpty<R>() => LinkedHashSet._default<R>();
// Returns a mutable set.
- Set<E> toSet() => LinkedHashSet<E>._default()..addAll(this);
+ Set<E> toSet() => LinkedHashSet._default<E>()..addAll(this);
}
