[m-rev.] for post-commit review: announce fatter_sparse_bitset.m

[Zoltan Somogyi]

2023-02-03 20:59 GMT+11:00 "Peter Wang" <novalazy at gmail.com>:
> Do you know of any code that uses fat_sparse_bitset? I couldn't find
> any.

sparse_bitset, tree_bitset, fat_sparse_bitset  are all variations of each other.
Each has its relative strengths and weaknesses. None are universally better
than any one other. For example, we got a significant speedup on the compiler
when we switched from using sparse_bitset to tree_bitset to represent
sets of variables in compiler passes such as quantification, and then,
a fair while later, we got another significant speedup when we switched
from tree_bitsets back to sparse_bitsets. The first speedup happened
because tree_bitset was designed to improve worst-case behavior
in the union operation that the compiler encountered frequently at that time,
and that improvement was more important than tree_bitset's higher
constant factors. We switched back to using sparse_bitset after
changes in the rest of the compiler drastically reduced the frequency
with which the worst case of the union operation was encountered,
which made the constant factors more important.

The implementation of set_of_var can use only one of these three
(now four) modules at a time, but different choices may be better
at different times (i.e. with different algorithms in the rest of the
compiler). That is why it is set up to make such changes trivial.
So the fact that fat_sparse_bitset is now unused does not matter;
it *could* be used easily.

fat_sparse_bitset.m is probably the one we can do without, because
it is roughly halfway between sparse_bitset and fatter_sparse_bitset
in terms of tradeoffs, in the sense that the advantages that it has
over sparse_bitset (such as fewer pointers needing to be followed
to traverse a set) are things in which fatter_sparse_bitset is even better,
and vice versa. However, that is only my intuition; we shouldn't
delete any of these modules without considerably more hard data.

Zoltan.