`hashCode` cache

[modulovalue]

Hello @isoos!

(I hope you don't mind all the issues. Having an efficient bitset in Dart has been on my TODO list for a looong time :), and your work is the best starting point that I've been able to find so far.)

One of my BitArray-related bottlenecks appears to be related to hashCode calculations:

What do you think about having a hashCode cache on BitArray? That is, on each mutation to the underlying BitArray buffer we'd invalidate the current hashCode (i.e., _hashCodeCache = null) and on each invocation of hashCode we'd set it to the current hashCode if it is not present (i.e., _hashCodeCache ??= currentHashCode).

What do you think?

[isoos]

I'm curious: why do you need the hashCode to be called? I think I've added it for completeness, but didn't plan on using it, so far...

A cache could be good, but we could also have unmodifiable version of the BitArray that calculates it via late final hashCode = - mostly depending on the use case we want to solve.

[modulovalue]

I'm curious: why do you need the hashCode to be called? I think I've added it for completeness, but didn't plan on using it, so far...

I need to store sets of powersets. I.e., imagine you have a bunch of states Q. If each Q has been assigned a unique integer between 0 and |Q| - 1, a single powerset of Q can then be represented as a BitArray.

Now, if we need to keep track of sets of powersets, we might use Set<BitArray>, which is where my fast hashCode requirement comes from.

A cache could be good, but we could also have unmodifiable version of the BitArray that calculates it via late final hashCode = - mostly depending on the use case we want to solve.

I agree. I'm not entirely sure whether I can use an unmodifiable BitArray for my use case, but, in any case, I would love to see a way to construct immutable BitArrays.

[modulovalue]

Here are some results:

I'm using the following wrapper for the Uint32List buffer to have better control over mutating operations:

class _HashCodeCachedUint32List {
  Uint32List _buffer;
  int? _cachedHashCode;

  int get cachedHashCode {
    final _currentCachedHashCode = _cachedHashCode;
    if (_currentCachedHashCode == null) {
      // Cache miss. We recalculate the hashCode and store it for future use.
      int total = 0;
      for (int i = 0; i < _buffer.length; i++) {
        total ^= _buffer[i].hashCode;
      }
      return _cachedHashCode = total;
    } else {
      // Cache hit. We reuse the precalculated hashCode.
      return _currentCachedHashCode;
    }
  }

  _HashCodeCachedUint32List(int size) : _buffer = Uint32List(size);

  _HashCodeCachedUint32List.raw(this._buffer);

  /// Immutable operation, the hashCode does not change.
  int get length => _buffer.length;

  /// Immutable operation, the hashCode does not change.
  int operator[](int i) => _buffer[i];

  /// Mutable operation, the hashCode does change.
  void operator[]=(int i, int v) {
    _buffer[i] = v;
    _cachedHashCode = null;
  }

  /// Be careful not to mutate this or the hashCode will become invalid.
  Uint32List get unsafe => _buffer;
}

With the following hashCode:

  // BitArray
  // ...
  _HashCodeCachedUint32List _data;
  // ...
  @override
  int get hashCode {
    return _data.cachedHashCode ^ length.hashCode;
  }

JIT • cached hashCode
Measure: run: took: 5124.08500 ms
Measure: run: took: 5115.86900 ms
Measure: run: took: 5140.93300 ms
Measure: run: took: 5159.43600 ms
Measure: run: took: 5158.00300 ms
Measure: run: took: 5148.05600 ms
Measure: run: took: 5121.50000 ms
Measure: run: took: 5156.80300 ms
Measure: run: took: 5185.92400 ms
Measure: run: took: 5143.36700 ms

JIT • uncached hashCode
Measure: run: took: 6049.48500 ms
Measure: run: took: 6008.08100 ms
Measure: run: took: 6028.06100 ms
Measure: run: took: 5983.81700 ms
Measure: run: took: 6073.51400 ms
Measure: run: took: 6040.68400 ms
Measure: run: took: 6018.03600 ms
Measure: run: took: 6067.68200 ms
Measure: run: took: 6056.42900 ms
Measure: run: took: 6018.30000 ms

AOT • cached hashCode
Measure: run: took: 8351.44300 ms
Measure: run: took: 8373.44700 ms
Measure: run: took: 8399.11700 ms
Measure: run: took: 8391.79800 ms
Measure: run: took: 8410.36200 ms
Measure: run: took: 8405.59500 ms
Measure: run: took: 8407.25100 ms
Measure: run: took: 8414.22500 ms
Measure: run: took: 8533.98000 ms
Measure: run: took: 8467.47600 ms

AOT • uncached hashCode
Measure: run: took: 9268.60400 ms
Measure: run: took: 9306.74800 ms
Measure: run: took: 9333.03100 ms
Measure: run: took: 9468.62700 ms
Measure: run: took: 9343.36200 ms
Measure: run: took: 9355.83900 ms
Measure: run: took: 9354.98400 ms
Measure: run: took: 9347.98200 ms
Measure: run: took: 9362.56500 ms
Measure: run: took: 9356.97800 ms

Definitely an improvement!

---

Note that BitArray exposes the underlying buffer via byteBuffer. I'm not sure what your use case for it is, or whether it's really necessay, but I think it would be good to remove it or else the hashCode might become invalid as we can't control what people do with the buffer.

[isoos]

Note that BitArray exposes the underlying buffer via byteBuffer.

The goal of that is to store the bytes efficiently without re-iterating them. I don't mind a breaking change there, e.g. it can be wrapped in UnmodifiableByteBufferView and a different asByteBuffer() method or we can find another way to expose it.

[modulovalue]

e.g. it can be wrapped in UnmodifiableByteBufferView

I didn't know UnmodifiableByteBufferView was a thing. I agree with that change.

  /// The backing, mutable byte buffer of the [BitArray].
  /// Use with caution.
  ByteBuffer get byteBuffer => UnmodifiableByteBufferView(_data.unsafe.buffer);

[modulovalue]

HUGE gains can in performance be achieved by marking the ops in the hashcode wrapped Uint32List with an inline pragma:

  /// Immutable operation, the hashCode does not change.
  @pragma("vm:prefer-inline")
  int get length => _buffer.length;

  /// Immutable operation, the hashCode does not change.
  @pragma("vm:prefer-inline")
  int operator[](int i) => _buffer[i];

  /// Mutable operation, the hashCode does change.
  @pragma("vm:prefer-inline")
  void operator[]=(int i, int v) {
    _buffer[i] = v;
    _cachedHashCode = null;
  }

  /// Be careful not to mutate this or the hashCode will become invalid.
  @pragma("vm:prefer-inline")
  Uint32List get unsafe => _buffer;

AOT • without inline pragma
Measure: run: took: 7802.59000 ms
Measure: run: took: 7819.36900 ms
Measure: run: took: 7842.12500 ms
AOT • with inline pragma
Measure: run: took: 6376.85400 ms
Measure: run: took: 6365.38700 ms
Measure: run: took: 6366.64500 ms
JIT • without inline pragma
Measure: run: took: 5928.06900 ms
Measure: run: took: 5847.31000 ms
Measure: run: took: 5834.46000 ms
Measure: run: took: 5834.15000 ms
JIT • with inline pragma
Measure: run: took: 4502.31100 ms
Measure: run: took: 4465.45400 ms
Measure: run: took: 4470.10700 ms
Measure: run: took: 4493.93200 ms