Optimizing the Ion compiler back end

Moral of the story:

First, use an array. If an array doesn't work, try something else.

It's definitely the case that in many scenarios, the right data structure is an array, since you'll have work dominated by gets and sets.

However, the OP has one scenario where the opposite was true - they were using a dense bitset that needed to be obscenely huge because of degenerate code in the wasm module, so swapping to a sparse container was a win.

In the end you just have to profile and understand your data.

To your point, profile your data as you would your code.

A sorted array of bit locations would represent a sparse bit set well enough to start, with O(N) storage and O(log N) access. Once the sets became large and/or dense, another data structure could be considered.