3 ms·
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
by barrkel 17y ago
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.
- rsc 17y agoYou 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.