Skip to content

Consider using fixed-size bitsets for terminal sets #1

@osa1

Description

@osa1

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.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions