Preston Briggs
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.
- AHO, A. V., HOPCROFT, J. E., AND ULLMAN, J.D. 1974. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, Mass. Google Scholar
- BENTLEY, J. 1986. Programming Pearls. Addison-Wesley, Reading, Mass. Google Scholar
- BOEHM, H.-J., AND WEISER, M. 1988. Garbage collection in an uncooperative environment. Softw. Prac. Exp. 18, 9 (Sept.), 807-820. Google Scholar
- BRIGGS, P. 1992. Register allocation via graph coloring. Ph.D. thesis, Rice Univ., Houston, Tex. Google Scholar
- BRIGGS, P., COOPER, K. D., AND TORCZON, L. 1992. Rematerialization. SIGPLAN Not. 27, 7 (July), 311-321. Proceedings of the ACM SIGPLAN '92 Conference on Programming Language Design and Implementation. Google Scholar
- CHAITIN, G.J. 1982. Register allocation and spilling via graph coloring. SIGPLAN Not. 17, 6 (June), 98-105. Proceedings of the ACM SIGPLAN '82 Symposium on Compiler Construction. Google Scholar
- 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.Google Scholar
- CYTRON, R., FERRANTE, J., ROSEN, B. K., WEGMAN, M. N., AND ZADECK, F.K. 1991. Efficiently computing static single assignment form and the control dependence graph. ACM Trans. Program. Lang. Syst. 13, 4 (Oct.), 451-490. Google Scholar
- CYTRON, R., FERRANTE, J., ROSEN, B. K., WEGMAN, M. N., AND ZADECK, F.K. 1989. An efficient method of computing static single assignment form. In Conference Record of the 16th Annual ACM Symposium on the Principles of Programming Languages. ACM, New York, 25-35. Google Scholar
- DEWAR, R. B. K., GRAND, A., LIU, S.-C., SCHWARTZ, J. T., AND SCHONBERG, E. 1979. Programming by refinement, as exemplified by the SETL representation sublanguage. ACM Trans. Program. Lang. Syst. 1, 1 (July), 27-49. Google Scholar
- STANDARDS PERFORMANCE EVALUATION CORP. 1990. SPEC Release 1.2. SPEC Corp., Freemont, Calif.Google Scholar
- WESTBROOK, J. AND TARJAN, R.E. 1989. Amortized analysis of algorithms for set union with backtracking. SIAM J. Comput. 18, 1 (Feb.), 1-11. Google Scholar
- YELLIN, D.M. 1989. Representing sets with constant time equality testing. Tech. Rep. RC 14539, IBM, Yorktown Heights, N.Y.Google Scholar
Index Terms
- An efficient representation for sparse sets
Recommendations
Efficient Set Operations over k2-Trees
DCC '15: Proceedings of the 2015 Data Compression Conferencek2-trees have been proved successful to represent in avery compact way different kinds of binary relations, such as web graphs, RDFs or raster data. In order to be a fully functional succinct representation for these domains, the k2-tree must support ...
Differential register allocation
PLDI '05: Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementationMicro-architecture designers are very cautious about expanding the number of architected registers (also the register field), because increasing the register field adds to the code size, raises I-cache and memory pressure, complicates processor ...
Integrated instruction selection and register allocation for compact code generation exploiting freeform mixing of 16- and 32-bit instructions
CGO '10: Proceedings of the 8th annual IEEE/ACM international symposium on Code generation and optimizationFor memory constrained embedded systems code size is at least as important as performance. One way of increasing code density is to exploit compact instruction formats, e.g. ARM Thumb, where the processor either operates in standard or compact ...
Reviews
Aaron M. Tenenbaum
A time-efficient mechanism for representing sparse sets on a predetermined universe is presented. If the universe contains u elements, and the elements are represented by the integers from 0 to u-1 , the set is represented by two integer arrays and an integer. A dense array contains all the elements in the set in the first n positions. A sparse array contains, in position k if k is an element of the set, the position of k in the dense array. The integer is n , the number of elements in the set. Addition of a new element and deletion of an element are constant-time operations. Iteration over all elements of the set takes time proportional to the number of elements in the set, not to the size of the universe (as is true of bit-vector implementations) . The paper provides algorithms, efficiency analyses, and cost comparisons with bit vectors. It also lists a number of applications where the representation has been used successfully.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments