home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / lang / cplus / 12549 < prev    next >
Encoding:
Internet Message Format  |  1992-08-19  |  3.2 KB
  1. Path: sparky!uunet!zephyr.ens.tek.com!uw-beaver!cornell!batcomputer!caen!sdd.hp.com!elroy.jpl.nasa.gov!decwrl!deccrl!bloom-beacon!eru.mt.luth.se!lunic!sunic!seunet!appli!niklas
  2. From: niklas@appli.se (Niklas Hallqvist)
  3. Newsgroups: comp.lang.c++
  4. Subject: Re: Garbage Collection for C++
  5. Message-ID: <2135@appli.se>
  6. Date: 19 Aug 92 08:54:52 GMT
  7. References: <1992Aug6.014619.2111@ucc.su.OZ.AU>     <DAVEG.92Aug13025629@synaptx.synaptics.com>     <1992Aug14.021547.15215@news.mentorg.com>     <DAVEG.92Aug14194411@synaptx.synaptics.com> <2009@appli.se> <TMB.92Aug17204854@arolla.idiap.ch>
  8. Organization: Applitron Datasystem AB, GOTHENBURG, SWEDEN
  9. Lines: 53
  10.  
  11. tmb@arolla.idiap.ch (Thomas M. Breuel) writes:
  12.  
  13. >niklas@appli.se (Niklas Hallqvist) writes:
  14.  
  15. >   I just wanted to say that conservative GC won't really help in all
  16. >   situations.  Jonathan Shapiro taught me this useful trick once.
  17. >   When you want to do a doubly linked list to the cost of a singly
  18. >   linked one (i.e. in mem. space).  Instead of having two pointers
  19. >   for the link in each node, take the "previous" and "next" pointers
  20. >   and XOR them, and store the result!
  21.  
  22. >   Now you just need to store two entry consecutive points into the
  23. >   list, and make an iterator intelligent enough to work things out.
  24. >   This is of course a very special trick, but it IS useful, and it
  25. >   shows NO GC strategy always wins unless the programmer explicitly
  26. >   can tell what objects are live/dead, but then again, we're back to
  27. >   explicit memory management.
  28.  
  29. >You didn't take that seriously, did you? In any case, it's an old hat
  30. >and it's unportable (*).
  31.  
  32. Well, I did mean it seriously, in order to show C++ rules need to be changed
  33. to allow even conservative GC.  It's only unportable between environments
  34. which don't have sufficiently sized integers to store pointers in.  If you
  35. restrict your program to only work on more "normal" architectures it IS
  36. defined.  Read ARM 5.4!  Of course, this means conservative GC is
  37. implementable on architectures where no integer type can hold a void pointer,
  38. but otherwise it is NOT.  Do I miss anything in my thinking?
  39.  
  40. >Incidentally, there is a widely used, simple, efficient, more general,
  41. >and completely portable technique for getting the same kinds of
  42. >storage savings as with the XOR trick.
  43.  
  44. Oh?  I can't think of any completely portable transformation of two pointers
  45. into a single field where you can get one of the pointers back if you know
  46. the other.  Subtraction, for example, is only defined if the pointers are
  47. pointing into the same array (ARM 5.7).  Maybe I'm on a soapbox when I
  48. assume a doubly linked listnode must be able to encode TWO pointers.
  49. And "widely used"?  I have read lots and lots of source for over ten years
  50. and I have obviously missed it.  Please show us this trick!
  51.  
  52. >(*) In C++, there is no guarantee that there exists an integral type
  53. >large enough to hold a pointer; ARM p.67-68.
  54.  
  55. So you had read this section, and still think GC can be done, if the text isn't
  56. changed to something like:
  57.  
  58. "All pointer to integer conversions and back are implementation defined."
  59. -- 
  60. Niklas Hallqvist    Phone: +46-(0)31-40 75 00
  61. Applitron Datasystem    Fax:   +46-(0)31-83 39 50
  62. Molndalsvagen 95    Email: niklas@appli.se
  63. S-412 63  GOTEBORG, Sweden     mcsun!seunet!appli!niklas
  64.