Performance of HashMap.update is slow

[gaaclarke]

This tracker is for issues related to:

• Dart core libraries ("dart:async", "dart:io", etc.)

Map.update is implemented as:

  V update(K key, V update(V value), {V Function()? ifAbsent}) {
    if (this.containsKey(key)) {
      return this[key] = update(this[key] as V);
    }
    if (ifAbsent != null) {
      return this[key] = ifAbsent();
    }
    throw ArgumentError.value(key, "key", "Key not in map.");
  }

This performs 3 lookups into the map. The map implementations should override their update implementations to be faster:

class HashMap<K, V> {
  @override
  V update(K key, V update(V value), {V Function()? ifAbsent}) {
    final hashCode = key.hashCode;
    final buckets = _buckets;
    final length = buckets.length;
    final index = hashCode & (length - 1);
    var entry = buckets[index];
    while (entry != null) {
      if (hashCode == entry.hashCode && entry.key == key) {
        entry.value = update(value);
        return;
      }
      entry = entry.next;
    }
    if (ifAbsent != null) {
      _addEntry(buckets, index, length, key, ifAbsent(), hashCode);
    }
    throw ArgumentError.value(key, "key", "Key not in map.");
  }
}

In local benchmarks the current HashMap.update implementation is ~2x slower than just using x[y] = x[y] + 1. In SplayTreeMap it's ~40% faster to use update because it does update in one pass.

[gaaclarke]

CL at https://dart-review.googlesource.com/c/sdk/+/242120