Investigate loop unrolling.

[modulovalue]

Consider this bitset implementation by lemire is JS https://github.com/lemire/FastBitSet.js:

It appears to manually unroll some loops which might also give us a boost in performance, too, e.g.:

https://github.com/lemire/FastBitSet.js/blob/d673f8ed91b4eb4e0104881aa1ff0402c3203648/FastBitSet.js#L285-L299

The or operation is currently on my hot path and I'm curious whether manually unrolling some loops could help.

[modulovalue]

Good news!

Without unrolling:

JIT
Measure: run: took: 6318.75100 ms
Measure: run: took: 6315.31500 ms
Measure: run: took: 6307.61400 ms
Measure: run: took: 6319.54600 ms

  static void inplaceOr(BitArray a, BitArray b) {
    final answer = a._data;
    final other = b._data;
    final count = math.min(answer.length, other.length);
    for (int i = 0; i < count; i++) {
      answer[i] |= other[i];
    }
  }

With unrolling:

JIT
Measure: run: took: 6106.47600 ms
Measure: run: took: 6087.64900 ms
Measure: run: took: 6070.16600 ms
Measure: run: took: 6068.03400 ms

  static void inplaceOr(BitArray a, BitArray b) {
    final answer = a._data;
    final other = b._data;
    final count = math.min(answer.length, other.length);
    int k = 0;
    for (; k + 7 < count; k += 8) {
      answer[k] |= other[k];
      answer[k + 1] |= other[k + 1];
      answer[k + 2] |= other[k + 2];
      answer[k + 3] |= other[k + 3];
      answer[k + 4] |= other[k + 4];
      answer[k + 5] |= other[k + 5];
      answer[k + 6] |= other[k + 6];
      answer[k + 7] |= other[k + 7];
    }
    for (; k < count; ++k) {
      answer[k] |= other[k];
    }
  }

Assuming that unrolling always improves performance, I think we should unroll all BitArray specialized implementations for the set ops, specialized equality, and the BitArray hashCode calculation.

[modulovalue]

Unrolling 16x times as opposed to 8x appears to only result in an improvement AOT and not JIT.

Unrolling the forEach in #19 (comment) results in an improvement AOT but not JIT.

The heuristic that I'm deriving from that experiment is to prefer unrolling small loops 8 times, and not to unroll big loops at all.

[modulovalue]

This blogpost shows how SIMD can significantly improve the performance of unrolled loops like the ones that bit_array would have once this issue is resolved.

Since Dart hart some support for SIMD, it might be worthwhile to investigate whether it is good enough for doing what that blogpost proposes.