Liveness analysis - the motivating example - is typically in the form of a set with one element per local variable. Most practical routines will have less than 32 or 64 variables, however, so even in practice a 32-bit or 64-bit word will be better. Also, you often have to compute other set operations, such as union, intersection and difference, rather than just membership and iteration.
You still have to do something for the functions with many local variables. In those cases you have little choice but to allow all N variables into the set, even if comparatively few are in any particular set at one time.
Sparse sets are also a great way to implement NFA state sets, where again you have a large number of possible set members but most sets are small, and you don't want to pay the O(all possible states) cost over and over.
Comments
Liveness analysis - the motivating example - is typically in the form of a set with one element per local variable. Most practical routines will have less than 32 or 64 variables, however, so even in practice a 32-bit or 64-bit word will be better. Also, you often have to compute other set operations, such as union, intersection and difference, rather than just membership and iteration.
You still have to do something for the functions with many local variables. In those cases you have little choice but to allow all N variables into the set, even if comparatively few are in any particular set at one time.
Sparse sets are also a great way to implement NFA state sets, where again you have a large number of possible set members but most sets are small, and you don't want to pay the O(all possible states) cost over and over.