One-bit counts between unique and sticky

ABSTRACT

Stoye's one-bit reference tagging scheme can be extended to local counts of two or more via two strategies. The first, suited to pure register transactions, is a cache of referents to two shared references. The analog of Deutsch's and Bobrow's multiple-reference table, this cache is sufficient to manage small counts across successive assignment statements. Thus, accurate reference counts above one can be tracked for short intervals, like those bridging one function's environment to its successor's.The second, motivated by runtime stacks that duplicate references, avoids counting any references from the stack. It requires a local pointer-inversion protocol in the mutator, but one still local to the referent and the stack frame. Thus, an accurate reference count of one can be maintained regardless of references from the recursion stack.

REFERENCES

• 1: Henry G. Baker, Lively linear Lisp: “look ma, no garbage!”, ACM SIGPLAN Notices, v.27 n.8, p.89-98, Aug. 1992 [doi>10.1145/142137.142162]
• 2: Jeffrey M. Barth, Shifting garbage collection overhead to compile time, Communications of the ACM, v.20 n.7, p.513-518, July 1977 [doi>10.1145/359636.359713]
• 3: Adrienne Bloss , Paul Hudak, Variations on strictness analysis, Proceedings of the 1986 ACM conference on LISP and functional programming, p.132-142, August 1986, Cambridge, Massachusetts, United States [doi>10.1145/319838.319857]
• 4: T. Chikayama & Y. Kimura. Multiple reference management in flat GHC. In J.-L. Lassez (ed.), Logic Programming, Proc. 4th Intl. Conf. 1. Cambridge, MA: M.I.T. Press (1987), 276-293.
• 5: D. W. Clark & C. C. Green. A note on shared list structure in LISp. Inf Process. Lett. 7, 6 (October 1978), 312-315.
• 6: Jacques Cohen, Garbage Collection of Linked Data Structures, ACM Computing Surveys (CSUR), v.13 n.3, p.341-367, Sept. 1981 [doi>10.1145/356850.356854]
• 7: George E. Collins, A method for overlapping and erasure of lists, Communications of the ACM, v.3 n.12, p.655-657, Dec. 1960 [doi>10.1145/367487.367501]
• 8: David E. Culler , Richard M. Karp , David Patterson , Abhijit Sahay , Eunice E. Santos , Klaus Erik Schauser , Ramesh Subramonian , Thorsten von Eicken, LogP: a practical model of parallel computation, Communications of the ACM, v.39 n.11, p.78-85, Nov. 1996 [doi>10.1145/240455.240477]
• 9: L. Peter Deutsch , Daniel G. Bobrow, An efficient, incremental, automatic garbage collector, Communications of the ACM, v.19 n.9, p.522-526, Sept. 1976 [doi>10.1145/360336.360345]
• 10: R. Gillam. The anatomy of the assignment operator. C++ Report 9, I0 (November-December 1997), 15-23.
• 11: Jean-Yves Girard, Linear logic, Theoretical Computer Science, v.50 n.1, p.1-102, Jan. 30, 1987 [doi>10.1016/0304-3975(87)90045-4]
• 12: David Gries, An exercise in proving parallel programs correct, Communications of the ACM, v.20 n.12, p.921-930, Dec. 1977 [doi>10.1145/359897.359903]
• 13: Y. Inamura, N. Ichiyoshi, K. Rokusawa, & K. Nakajima. Optimization techniques using the MRB and their evaluation on the Multi-PSI/V2. In E. L. Lusk & R. A. Overbeek, Logic Programming, Proc. of North American Conf. 1989 2, Cambridge, MA: M.I.T. Press (1989), 907-921.
• 14: R. Jones & R. Lins. Garbage Collection. Chichester: Wiley (1996).
• 15: Simon B. Jones , Daniel Le Métayer, Compile-time garbage collection by sharing analysis, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.54-74, September 11-13, 1989, Imperial College, London, United Kingdom [doi>10.1145/99370.99375]
• 16: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 17: Harry R. Lewis , Larry Denenberg, Data Structures and Their Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 18: Rinus Plasmeijer , Marko Van Eekelen, Functional Programming and Parallel Graph Rewriting, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1993
• 19: M. G. Sobe|. A Practical Guide to the UNIX System (3rd ed.) Redwood City, CA: Benjamin/Cummings (1995), 609-611.
• 20: W. R. Stoye , T. J. W. Clarke , A. C. Norman, Some practical methods for rapid combinator reduction, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.159-166, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802032]
• 21: Norihisa Suzuki, Analysis of pointer “rotation”, Communications of the ACM, v.25 n.5, p.330-335, May 1982 [doi>10.1145/358506.358513]
• 22: A. J. Perlis , Charles Thornton, Symbol manipulation by threaded lists, Communications of the ACM, v.3 n.4, p.195-204, April 1960 [doi>10.1145/367177.367202]
• 23: David N. Turner , Philip Wadler , Christian Mossin, Once upon a type, Proceedings of the seventh international conference on Functional programming languages and computer architecture, p.1-11, June 26-28, 1995, La Jolla, California, United States [doi>10.1145/224164.224168]
• 24: J. Weizenbaum, Symmetric list processor, Communications of the ACM, v.6 n.9, p.524-536, Sept. 1963 [doi>10.1145/367593.367617]
• 25: Paul R. Wilson, Uniprocessor Garbage Collection Techniques, Proceedings of the International Workshop on Memory Management, p.1-42, September 17-19, 1992
• 26: David S. Wise, Stop-and-copy and one-bit reference counting, Information Processing Letters, v.46 n.5, p.243-249, July 9, 1993 [doi>10.1016/0020-0190(93)90103-G]
• 27: D. S. Wise & D. P. Friedman. The one-bit reference count. BIT 17, 3 (September 1977), 351-359.
• 28: David S. Wise , Brian Heck , Caleb Hess , Willie Hunt , Eric Ost, Research Demonstration of a Hardware Reference-Counting Heap, Lisp and Symbolic Computation, v.10 n.2, p.159-181, July 1997 [doi>10.1023/A:1007715101339]
• 29: David S. Wise , Joshua Walgenbach, Static and dynamic partitioning of pointers as links and threads, ACM SIGPLAN Notices, v.31 n.6, p.42-49, June 15, 1996

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Allocation/deallocation strategies

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Garbage collection

  E. Data
  E.2 DATA STORAGE REPRESENTATIONS
      Subjects: Linked representations

  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

General Terms:
Algorithms, Design, Languages, Measurement, Theory

Keywords:
MRB, garbage collection, multiple reference bit, storage management