Nothing Special   »   [go: up one dir, main page]

skip to main content
10.1145/286860.286866acmconferencesArticle/Chapter ViewAbstractPublication PagesismmConference Proceedingsconference-collections
Article
Free access

One-bit counts between unique and sticky

Published: 01 October 1998 Publication History

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]
H.G. Baker. Lively linear lispm'Look Ma, no garbage!' SIG- PLAN Not. 27, 8 (August 1992), 89-98.
[2]
J. Barth. Shifting garbage collection overhead to compile time. Commun. ACM 20, 7 (July 1977), 513-518.
[3]
A. Bloss & P. Hudak. Variations on strictness analysis. Conf Rec. 1986 A CM Symp. on Lisp and Functional Programming, 132-142.
[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]
J. Cohen. Garbage collection of linked data structures. ACM Comput Surv. 13, 3 (September 1981 ), 341-367.
[7]
G. E. Collins. A method for overlapping and erasure of lists. Commun. ACM 3, 12 (December 1960), 655-657.
[8]
D. Culler, R. Karp, D. Patterson, A. Sahay, K. E. Schauser, E. Santos, R. Subramonian, & T. von Eicken. LogP: a practical model of parallel computation. Commun. ACM 39, 11 (November 1996), 78-85.
[9]
L. E Deutsch & D. G. Bobrow. An efficient, incremental, automatic garbage collector. Commun. ACM 19, 9 (September 1976), 522-526.
[10]
R. Gillam. The anatomy of the assignment operator. C++ Report 9, I0 (November-December 1997), 15-23.
[11]
J.-Y. Girard. Linear logic. Theor. Comput. Sci. 50 (1987), 1- 102.
[12]
D. Gries. An exercise in proving programs correct. Commun. ACM 20, 12 (December 1977), 921-930.
[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]
S. B. Jones & D. Le M6tayer. Compile-time garbage colleclion by sharing analysis. Functional Programming and Computer Architecture, New York: ACM (I989) 54-74.
[16]
D. E. Knuth The Art of Computer Programming I, Fundamental Algorithms (3rd ed.), Reading MA: Addison-Wesley (1997).
[17]
H. R. Lewis & L. Dennenberg. Data Structures & Their Algorithms. New York: HarperCollins (1991).
[18]
R. Plasmiejer & M. van Eekelen. Functional Programming and Parallel Graph Rewriting, Workingham, UK: Addison- Wesley (1993), ~8.5.
[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. Conf. Rec. 1984 ACM Symp. on Lisp and Functional Programming, 159-166.
[21]
N. Suzuki. Analysis of pointer 'rotation.' Commun. ACM 25, 5 (May 1982), 330-335.
[22]
A. J. Perlis & C. Thornton. Symbol manipulation by threaded lists. Commun. ACM 3, 4 (April 1960), 195-204.
[23]
D. N. Turner & E Wadler. Once upon a type. Conf Rec. of FPCA '95: Functional Programming Languages and Computer Architecture, New York: ACM Press (1995), l-11.
[24]
J. Weizenbaum. Symmetric list processor. Commun. ACM 6, 9 (September 1963), 524-554.
[25]
E R. Wilson. Uniprocessor garbage collection techniques. In Y. Bekkers & J. Cohen (eds.) Memory Management, LNCS 637, Berlin: Springer (1992), 1-42.
[26]
D. S. Wise. Stop-and-copy and one-bit reference counting. lnf Process. Lett. 46, 5 (July 1993), 243-249. Also ftp://ftp.cs.indiana.edu/pub/techreports/TR360.ps.Z
[27]
D. S. Wise & D. P. Friedman. The one-bit reference count. BIT 17, 3 (September 1977), 351-359.
[28]
D. S. Wise, C. Hess, W. Hunt, & E. Ost. Research demonstration of a hardware reference-counting heap. Lisp Symb. Comp. 10, 2 (July 1997), 159-181.
[29]
D. S. Wise & J. Walgenbach. Static and dynamic partitioning of pointers as links and threads. Proc. 1996 ACM SIGPLAN Intl. Conf. on Functional Programming, SIGPLAN Not. 31, 6 (June 1996), 42--49.

Cited By

View all
  • (2006)Clustering the heap in multi-threaded applications for improved garbage collectionProceedings of the 8th annual conference on Genetic and evolutionary computation10.1145/1143997.1144314(1901-1908)Online publication date: 8-Jul-2006
  • (2005)An energy efficient garbage collector for java embedded devicesACM SIGPLAN Notices10.1145/1070891.106594340:7(230-238)Online publication date: 15-Jun-2005
  • (2005)On designing a low-power garbage collector for java embedded devicesProceedings of the 2005 ACM symposium on Applied computing10.1145/1066677.1066875(868-873)Online publication date: 13-Mar-2005
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
ISMM '98: Proceedings of the 1st international symposium on Memory management
October 1998
200 pages
ISBN:1581131143
DOI:10.1145/286860
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 1998

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. MRB
  2. garbage collection
  3. multiple reference bit
  4. storage management

Qualifiers

  • Article

Conference

ISMM98
Sponsor:
ISMM98: International Symposium on Memory Management 1998
October 17 - 19, 1998
British Columbia, Vancouver, Canada

Acceptance Rates

Overall Acceptance Rate 72 of 156 submissions, 46%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)109
  • Downloads (Last 6 weeks)17
Reflects downloads up to 20 Nov 2024

Other Metrics

Citations

Cited By

View all
  • (2006)Clustering the heap in multi-threaded applications for improved garbage collectionProceedings of the 8th annual conference on Genetic and evolutionary computation10.1145/1143997.1144314(1901-1908)Online publication date: 8-Jul-2006
  • (2005)An energy efficient garbage collector for java embedded devicesACM SIGPLAN Notices10.1145/1070891.106594340:7(230-238)Online publication date: 15-Jun-2005
  • (2005)On designing a low-power garbage collector for java embedded devicesProceedings of the 2005 ACM symposium on Applied computing10.1145/1066677.1066875(868-873)Online publication date: 13-Mar-2005
  • (2005)An energy efficient garbage collector for java embedded devicesProceedings of the 2005 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems10.1145/1065910.1065943(230-238)Online publication date: 15-Jun-2005
  • (2005)Derivation and evaluation of concurrent collectorsProceedings of the 19th European conference on Object-Oriented Programming10.1007/11531142_25(577-601)Online publication date: 25-Jul-2005
  • (2004)The space cost of lazy reference countingACM SIGPLAN Notices10.1145/982962.96401939:1(210-219)Online publication date: 1-Jan-2004
  • (2004)The space cost of lazy reference countingProceedings of the 31st ACM SIGPLAN-SIGACT symposium on Principles of programming languages10.1145/964001.964019(210-219)Online publication date: 14-Jan-2004
  • (2004)BarriersProceedings of the 4th international symposium on Memory management10.1145/1029873.1029891(143-151)Online publication date: 24-Oct-2004
  • (2001)An on-the-fly reference counting garbage collector for JavaACM SIGPLAN Notices10.1145/504311.50430936:11(367-380)Online publication date: 1-Oct-2001
  • (2001)An on-the-fly reference counting garbage collector for JavaProceedings of the 16th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications10.1145/504282.504309(367-380)Online publication date: 1-Oct-2001
  • Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media