Add BitSet (bit vector) to Dart library

[DartBot]

This issue was originally filed by @ahmetaa

---

Although it is not as commonly used as other collection types, an efficient bit vector (BitSet) implementation would be nice to have.

[dgrove]

Removed Type-Defect label. Added Type-Enhancement, Area-Library, Triaged labels.

[DartBot]

This comment was originally written by sk...@gmail.com

---

I had a need for an efficient bitset and ended up implementing it myself (it was also an exercise in learing Dart, so I welcome comments on implementation): https://pub.dartlang.org/packages/bit_set

[DartBot]

This comment was originally written by @arhad

---

I would say that border must be implemented as List<bool> template specialisation, like in C++.

[lrhn]

Not currently planned for the platform libraries. We may want to add it to a package like package:collection.

[modulovalue]

I think it would be great to have a stable and reliable Bitset implementation in [the] Dart [ecosystem].

If one considers Lists to be efficient Maps where the domain of the keys are integers, then Bitsets are efficient sets where the domain of the values are integers, but unfortunately, Dart doesn't come with a Bitset, and HashSets are absurdly suboptimal for Sets over some integral domains.

---

One usecase for Bitsets comes up when trying to optimize algorithms over finite domains, where the obvious improvements are:

• normalize the domain to integers
• use Lists instead of Maps
• use Bitsets instead of Sets.

Sadly, the last step can't be done yet without reimplementing bitsets or relying on a third party (literally, only one third party).

---

It should be noted that Bitsets, in general, do not support efficient enumeration of set bits the way that HashSets do. I think that this is a useful operation and it could be surprising to some that Bitsets can't do that. I know two ways to deal with that:

• use popcount/SIMD to skip/extract unset/set bits more efficiently. ~It appears that there are highly efficient popcount instructions (that don't pollute the cache with lookup tables), which Dart doesn't support.~ (I have filed: https://github.com/dart-lang/sdk/issues/52673) SIMD support is weak and integer SIMD support will hopefully receive some more love one day.

• use an alternative Bitset design like this FASTSET (which seems to also be known as a sparse set, but I'm not entirely sure). It supports all important operations efficiently (not just some), but it is significantly less efficient memory-wise than a standard Bitset because it represents all integers explicitly twice, and not just one bit per integer, but it is still more efficient than a HashSet.

---

I believe Roaring bitmaps are considered to be the state of the art (when it comes to bitsets) and appear to be used by practically everybody. I was hoping to get roaring bitmaps to work in Dart (in a portable way across all platforms) via WASM, but the current experiment for running WASM inside of Dart is being discontinued :(.

[modulovalue]

Note: there is a BoolList in package:collection. It doesn't have efficient bitset operations, but it appears to support the use-case of a memory efficient collection of bits.