home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / compiler / 1426 < prev    next >
Encoding:
Internet Message Format  |  1992-08-20  |  6.5 KB
  1. Xref: sparky comp.compilers:1426 comp.lang.c++:12690
  2. Path: sparky!uunet!dtix!darwin.sura.net!jvnc.net!yale.edu!qt.cs.utexas.edu!cs.utexas.edu!rutgers!faatcrl!iecc!compilers-sender
  3. From: kelvin@kickapoo.cs.iastate.edu (Kelvin Don Nilsen)
  4. Newsgroups: comp.compilers,comp.lang.c++
  5. Subject: Our experiences with garbage collection of C++
  6. Keywords: C++, GC
  7. Message-ID: <92-08-126@comp.compilers>
  8. Date: 20 Aug 92 20:43:24 GMT
  9. Sender: compilers-sender@iecc.cambridge.ma.us
  10. Reply-To: kelvin@kickapoo.cs.iastate.edu (Kelvin Don Nilsen)
  11. Organization: Iowa State University, Ames IA
  12. Lines: 112
  13. Approved: compilers@iecc.cambridge.ma.us
  14. Return-Path: <news@news.iastate.edu>
  15.  
  16. Ph.D. candidate William Schmidt and I are winding down some recent
  17. research on hardware-assisted real-time garbage collection.  Together, we
  18. would like to contribute the following additional observations to the
  19. discussions regarding garbage collection for C++.
  20.  
  21. Background:
  22.  
  23. We have designed a new memory architecture that mimics traditional memory
  24. while performing garbage collection as a background activity.  We use a
  25. variant of Baker's real-time copying garbage collection algorithm.
  26. Numerous studies have demonstrated that this algorithm, implemented in
  27. software, severely degrades overall system throughput.  The goals of our
  28. hardware design were to provide guaranteed real-time response to all
  29. memory operations with minimal negative impact on system performance.
  30. Additionally, it was our hope that the hardware costs could be kept to a
  31. minimum.  
  32.  
  33. To evaluate the utility of our proposed architecture, we have constructed
  34. a RISC-based hardware simulator and retargeted a version of the g++
  35. compiler to this architecture.  Since we use a copying garbage collection
  36. algorithm, it is necessary for the compiler to assist us in locating all
  37. pointers in the system.  In our environment, we tag each word at the time
  38. of its allocation.  These tags are transparent to the C++ application;
  39. each 32-bit word of garbage-collected memory is accompanied by an extra
  40. one-bit pointer tag.
  41.  
  42. With help from our g++ compiler, we have ported several applications to
  43. the experimental architecture.  These applications include a fast-fourier
  44. transform program, the groff typesetting software, a simple line editor,
  45. and a lisp interpreter written by Tim Budd.  Empirical investigation of
  46. these applications revealed shortcomings and bottlenecks in the original
  47. designs of the architecture and code generator.  In response to these
  48. findings, we have made several refinements to the original design.
  49. Unfortunately, due to limited time and resources, we have not yet been
  50. able to run all of the sample applications through the most recent
  51. incarnation of the system.  Some of the performance figures reported below
  52. represent careful extrapolations of measured results.
  53.  
  54.  
  55. Results:
  56.  
  57.  We feel that we have satisfied our major goals.
  58.  
  59.     Guaranteed Real-Time Response:
  60.        The worst-case time required to fetch a word of garbage-collected
  61.        memory is six traditional memory cycles.  The worst-case time
  62.        required to write a word of garbage-collected memory is three
  63.        traditional memory cycles.  In practice, over 99% of fetches and
  64.        stores are completed in only one memory cycle.  The worst-case time
  65.        required to initiate a flip is two traditional memory cycles times
  66.        the number of pointers in the application's root set.
  67.  
  68.     High System Throughput:
  69.        Garbage-collected memory can be cached, and our simulations reveal
  70.        that data cache hit rates for garbage collected memory are usually
  71.        within a fraction of a percent of the hit rates for traditional
  72.        implementations of otherwise identical applications.  The average
  73.        cost of servicing a cache miss is generally within 50% of the
  74.        cost of servicing cache misses from traditional memory.  Garbage
  75.        collection consistently executes in approximately a tenth of the
  76.        time required by traditional C++ implementations to execute malloc
  77.        and free.  However, the performance of our garbage collected C++
  78.        system is limited by the overhead of "tagging" pointers within 
  79.        function activation frames.  In sum, we have found that
  80.        garbage-collected C++ programs generally run within plus or minus
  81.        25% of the time required to run traditional implementations of
  82.        the same programs  (That's right.  Some programs run 25% slower.
  83.        Some run 25% faster!)  These measurements are based on real
  84.        applications originally written for traditional architectures,
  85.        which have been tuned (to varying degrees) to those environments.
  86.  
  87.     Is the hardware practical?
  88.        Remember, we are talking about real-time garbage collection.  Thus,
  89.        we assume that the entire application fits within real memory.
  90.        Further, the amount of memory available to represent live objects
  91.        is only a fraction (typically, 35-45%) of the total amount of memory
  92.        dedicated to the garbage-collected memory module.  We estimate the
  93.        costs of the additional hardware required to support this
  94.        architecture as 15-50% of the cost of the memory controlled by the
  95.        module.  The bottom line:
  96.  
  97.          Are you willing to spend 3-5 times the cost of traditional
  98.       memory to get "high-performance" real-time garbage
  99.           collection?
  100.  
  101.        By the way, the special hardware required to support garbage
  102.        collection is located entirely within the expansion memory
  103.        module.  No special hardware is required in the CPU.  We 
  104.        originally set out to design hardware that is completely
  105.        portable between CPU and bus-based system architectures.
  106.        Our garbage-collected memory module will work in any bus-based
  107.        architecture that provides support for some form of multi-processor
  108.        cache coherency.  Alternative configurations are available for
  109.        cached and uncached single-processor environments.
  110.      
  111.    
  112. If you are interested in more complete descriptions of our system design
  113. and/or experimental methods, please don't hesitate to contact either of
  114. us:
  115.  
  116.   Kelvin Nilsen            William Schmidt
  117.   Assistant Professor        Ph.D. candidate
  118.   Computer Science Dept.    Computer Science Dept.
  119.   Iowa State University        Iowa State University
  120.   kelvin@cs.iastate.edu        schmidt@cs.iastate.edu
  121. --
  122.  
  123. Kelvin Nilsen/Dept. of Computer Science/Iowa State University/Ames, IA  50011 
  124.  (515) 294-2259   kelvin@cs.iastate.edu  uunet!kelvin@cs.iastate.edu
  125. -- 
  126. Send compilers articles to compilers@iecc.cambridge.ma.us or
  127. {ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
  128.