We currently use FxHashSet for terminal sets in first and follow sets, but we could use fixed-size bitsets instead. I have an implementation in refactor_terminal_sets but it doesn't make much difference: a benchmark runs in 4.9s instead of 5.0s. I think part of the reason is because these sets are usually tiny, perhaps with 3-4 elements at most, so it doesn't matter what we use.
I also have a bitset implementation in smol_bitset repo. It uses a single word for bitsets smaller than 63 elements. For larger, it falls back to heap allocated word array. However, when I replace the bitset in refactor_terminal_sets branch with smol_bitset it literally made no difference in the benchmark.
We currently use
FxHashSetfor terminal sets in first and follow sets, but we could use fixed-size bitsets instead. I have an implementation inrefactor_terminal_setsbut it doesn't make much difference: a benchmark runs in 4.9s instead of 5.0s. I think part of the reason is because these sets are usually tiny, perhaps with 3-4 elements at most, so it doesn't matter what we use.I also have a bitset implementation in
smol_bitsetrepo. It uses a single word for bitsets smaller than 63 elements. For larger, it falls back to heap allocated word array. However, when I replace the bitset inrefactor_terminal_setsbranch withsmol_bitsetit literally made no difference in the benchmark.