Name
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. |
Year | DOI | Venue |
|---|---|---|
1993 | 10.1145/176454.176484 | LOPLAS |
Keywords | Field | DocType |
bit vector representation,efficient forall iterator,detailed comparison,efficient analysis technique,graph-coloring register allocation,compiler implementation,constant-time implementation,register allocation,sparse set,set representations,particular set,set operations,new representation,efficient representation,graph coloring | Register allocation,Computer science,Set operations,Enumeration,Cardinality,Implementation,Theoretical computer science,Bit array,Function representation,Iterator | Journal |
Volume | Issue | Citations |
2 | 1-4 | 43 |
PageRank | References | Authors |
2.79 | 8 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Preston Briggs | 1 | 379 | 32.43 |
| Linda Torczon | 2 | 1096 | 146.31 |