An efficient representation for sparse sets
Authors:
Open Access
- 1 March 1993
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Letters on Programming Languages and Systems
- Vol. 2 (1-4) , 59-69
Abstract
Sets are a fundamental abstraction widely used in programming. Many representations are possible, each offering different advantages. We describe a representation that supports constant-time implementations of clear-set, add-member, and delete-member . Additionally, it supports an efficient forall iterator, allowing enumeration of all the members of a set in time proportional to the cardinality of the set. We present detailed comparisons of the costs of operations on our representation and on a bit vector representation. Additionally, we give experimental results showing the effectiveness of our representation in a practical application: construction of an interference graph for use during graph-coloring register allocation. While this representation was developed to solve a specific problem arising in register allocation, we have found it useful throughout our work, especially when implementing efficient analysis techniques for large programs. However, the new representation is not a panacea. The operations required for a particular set should be carefully considered before this representation, or any other representation, is chosen.Keywords
This publication has 8 references indexed in Scilit:
- RematerializationACM SIGPLAN Notices, 1992
- Efficiently computing static single assignment form and the control dependence graphACM Transactions on Programming Languages and Systems, 1991
- Amortized Analysis of Algorithms for Set Union with BacktrackingSIAM Journal on Computing, 1989
- An efficient method of computing static single assignment form1989
- Garbage collection in an uncooperative environmentSoftware: Practice and Experience, 1988
- Register allocation & spilling via graph coloring1982
- Register allocation via coloringComputer Languages, 1981
- Programming by Refinement, as Exemplified by the SETL Representation SublanguageACM Transactions on Programming Languages and Systems, 1979