[dart2wasm] Avoid repeatedly allocating strings for the same json object keys
Most jsons have ascii strings as keys in json objects and very often
those keys are highly repetitive.
In previous CLs we started to compute the hash of the json object keys
eagerly, even before allocating the string.
We can take advantage of this now by using consulting a fixed-size
interning cache. The cost of this cache is
* Memory: It has max 512 entries and only contains one byte strings used
as keys in json (keys are usually very small).
* Lookup: Bitmask and lookup in array, length comparison (fails often if
keys are not the same), plus byte comparison (may often suceeed)
* Insert: Simply store into an array.
The benefit is that we are very likely to allocate a lot less string
objects for the keys. This will make data fit better in caches, will
make string equality checks (in map lookups) more often hit the
fast case (pointer equality) and reduce GC pressure.
Change-Id: Id8ed3a972a267dd0201383f8f51ed82758bc0e63
Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/409680
Reviewed-by: Ömer Ağacan <omersa@google.com>
Commit-Queue: Martin Kustermann <kustermann@google.com>
diff --git a/sdk/lib/_internal/wasm/lib/convert_patch.dart b/sdk/lib/_internal/wasm/lib/convert_patch.dart
index 9121387..a5b5e4f 100644
--- a/sdk/lib/_internal/wasm/lib/convert_patch.dart
+++ b/sdk/lib/_internal/wasm/lib/convert_patch.dart
@@ -27,6 +27,7 @@
String source,
Object? Function(Object? key, Object? value)? reviver,
) {
+ _oneByteStringInternCache.fill(0, null, _oneByteStringInternCacheSize);
final listener = _JsonListener(reviver);
if (source is OneByteString) {
final parser = _JsonOneByteStringParser(listener);
@@ -1644,13 +1645,7 @@
String getStringWithHash(int start, int end, int bits, int stringHash) {
final sourceArray = chunk.array;
final length = end - start;
- final result = OneByteString.withLength(length);
- for (int i = 0; i < length; ++i) {
- result.array.write(i, sourceArray.readUnsigned(start++));
- }
- assert(result.hashCode.toWasmI32() == stringHash.toWasmI32());
- setIdentityHashField(result, stringHash);
- return result;
+ return _internOneByteStringFromI8(sourceArray, stringHash, start, length);
}
void beginString() {
@@ -1732,12 +1727,12 @@
const asciiBits = 0x7f;
if (bits <= asciiBits) {
- final result = OneByteString.withLength(length);
- for (int i = 0; i < length; ++i) {
- result.array.write(i, sourceArray.readUnsigned(start++));
- }
- setIdentityHashField(result, stringHash);
- return result;
+ return _internOneByteStringFromI16(
+ sourceArray,
+ stringHash,
+ start,
+ length,
+ );
}
final result = TwoByteString.withLength(length);
@@ -1787,6 +1782,73 @@
}
}
+const int _oneByteStringInternCacheSize = 512;
+final WasmArray<OneByteString?> _oneByteStringInternCache =
+ WasmArray<OneByteString?>(_oneByteStringInternCacheSize);
+OneByteString _internOneByteStringFromI8(
+ WasmArray<WasmI8> array,
+ int stringHash,
+ int offset,
+ int length,
+) {
+ final int index = stringHash & (_oneByteStringInternCacheSize - 1);
+ final existing = _oneByteStringInternCache[index];
+
+ insert:
+ {
+ if (existing != null) {
+ if (existing.length == length) {
+ final existingArray = existing.array;
+ for (int start = offset, i = 0; i < length; ++i, start++) {
+ if (existingArray.readUnsigned(i) != array.readUnsigned(start)) {
+ break insert;
+ }
+ }
+ return existing;
+ }
+ }
+ }
+
+ final result = OneByteString.withLength(length);
+ result.array.copy(0, array, offset, length);
+ setIdentityHashField(result, stringHash);
+ _oneByteStringInternCache[index] = result;
+ return result;
+}
+
+OneByteString _internOneByteStringFromI16(
+ WasmArray<WasmI16> array,
+ int stringHash,
+ int offset,
+ int length,
+) {
+ final int index = stringHash & (_oneByteStringInternCacheSize - 1);
+ final existing = _oneByteStringInternCache[index];
+
+ insert:
+ {
+ if (existing != null) {
+ if (existing.length == length) {
+ final existingArray = existing.array;
+ for (int start = offset, i = 0; i < length; ++i, start++) {
+ if (existingArray.readUnsigned(i) != array.readUnsigned(start)) {
+ break insert;
+ }
+ }
+ return existing;
+ }
+ }
+ }
+
+ final result = OneByteString.withLength(length);
+ for (int start = offset, i = 0; i < length; ++i, start++) {
+ result.array.write(i, array.readUnsigned(start));
+ }
+ setIdentityHashField(result, stringHash);
+ _oneByteStringInternCache[index] = result;
+ return result;
+}
+
@patch
class JsonDecoder {
@patch
