An efficient representation for sparse sets

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.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: Jon Bentley, Programming pearls, ACM Press, New York, NY, 1986
• 3: Hans-Juergen Boehm , Mark Weiser, Garbage collection in an uncooperative environment, Software—Practice & Experience, v.18 n.9, p.807-820, September 1988 [doi>10.1002/spe.4380180902]
• 4: Preston Briggs, Register allocation via graph coloring, Rice University, Houston, TX, 1992
• 5: Preston Briggs , Keith D. Cooper , Linda Torczon, Rematerialization, ACM SIGPLAN Notices, v.27 n.7, p.311-321, July 1992
• 6: G. J. Chaitin, Register allocation & spilling via graph coloring, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.98-105, June 23-25, 1982, Boston, Massachusetts, United States
• 7: CHAITIN, G. J., AUSLANDER, M. A., CHANDRA, A. K., COCKE, J., HOPKINS, M. E., AND MARKSTEIN, P.W. 1981. Register allocation via coloring. Comput. Lang. 6, 1 (Jan.), 47-57.
• 8: Ron Cytron , Jeanne Ferrante , Barry K. Rosen , Mark N. Wegman , F. Kenneth Zadeck, Efficiently computing static single assignment form and the control dependence graph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.451-490, Oct. 1991 [doi>10.1145/115372.115320]
• 9: R. Cytron , J. Ferrante , B. K. Rosen , M. N. Wegman , F. K. Zadeck, An efficient method of computing static single assignment form, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.25-35, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75280]
• 10: Robert K. Dewar , Arthur and Ssu-Cheng Liu and Jacob T. Schwartz and Edmond Schonberg, Programming by Refinement, as Exemplified by the SETL Representation Sublanguage, ACM Transactions on Programming Languages and Systems (TOPLAS), v.1 n.1, p.27-49, July 1979 [doi>10.1145/357062.357064]
• 11: STANDARDS PERFORMANCE EVALUATION CORP. 1990. SPEC Release 1.2. SPEC Corp., Freemont, Calif.
• 12: J. Westbrook , R. E. Tarjan, Amortized analysis of algorithms for set union with backtracking, SIAM Journal on Computing, v.18 n.1, p.1-11, Feb. 1989 [doi>10.1137/0218001]
• 13: YELLIN, D.M. 1989. Representing sets with constant time equality testing. Tech. Rep. RC 14539, IBM, Yorktown Heights, N.Y.

INDEX TERMS

Primary Classification:
  E. Data

Additional Classification:
  E. Data

General Terms:
Algorithms, Experimentation, Measurement

Keywords:
compiler implementation, register allocation, set operations, set representations