home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / lang / cplus / 12637 < prev    next >
Encoding:
Text File  |  1992-08-20  |  5.6 KB  |  231 lines
  1. Path: sparky!uunet!snorkelwacker.mit.edu!ai-lab!life.ai.mit.edu!tmb
  2. From: tmb@arolla.idiap.ch (Thomas M. Breuel)
  3. Newsgroups: comp.lang.c++
  4. Subject: garbage collection (some actual DATA)...
  5. Message-ID: <TMB.92Aug20145357@arolla.idiap.ch>
  6. Date: 20 Aug 92 18:53:57 GMT
  7. Sender: news@ai.mit.edu
  8. Reply-To: tmb@idiap.ch
  9. Distribution: comp
  10. Organization: IDIAP (Institut Dalle Molle d'Intelligence Artificielle
  11.     Perceptive)
  12. Lines: 217
  13.  
  14. OK, lots of people have been claiming that GC is "obviously" a drag
  15. and "obviously" costs you an arm and a leg. Well, here are some simple
  16. benchmarks that suggest that this isn't so obvious.
  17.  
  18. The main point is that there is no significant difference between
  19. running the same code with or without GC if you explicitly free the
  20. storage that you have allocated (the small difference that there is is
  21. probably due to the fact that the storage returned by gc_malloc is
  22. already initialized; this is not strictly speaking necessary).
  23.  
  24. In this particular case, it turns out that letting the garbage
  25. collector do the freeing is actually _faster_ than manual freeing of
  26. memory. I don't want to claim that this is generally true, but it
  27. shows that even conservative collectors _can_ do better than manual
  28. storage management.
  29.  
  30. Reference counting in C++ is, not surprisingly, the slowest method of
  31. memory management. You can reduce the cost significantly by putting
  32. the reference count into the data itself, but it then gets much
  33. messier if you try to "package up" memory management into a template
  34. class.
  35.  
  36. For comparison, I have also included a "real" system with GC, namely
  37. NJ/SML. In fact, compared to all the C/C++ programs, it seems to have
  38. the lowest overhead for memory management. The reason why it isn't
  39. much faster than the C version is probably that the compiler is still
  40. under development (some inefficient calling sequences, failure to
  41. inline), and that there are a lot of (useful!) runtime checks for
  42. arithmetic overflow, out-of-bounds indexes, etc. built in.
  43. Incidentally, the NJ/SML collector managed to clean up this large
  44. volume of garbage (about 48M) without a single major collection,
  45. meaning, that in an interactive system there would have been no
  46. noticeable delay.
  47.  
  48.                     Thomas.
  49.  
  50. ================================================================
  51.  
  52. int *a[10];
  53.  
  54. main() {
  55.     int i;
  56.     for(i=0;i<1000000;i++) {
  57.         int j = i%10;
  58.         int k,*p;
  59.         if(a[j]) free(a[j]);
  60.         p=(int*)malloc(10*sizeof (int));
  61.         a[j]=p;
  62.         for(k=0;k<10;k++) *p++ = 0;
  63.     }
  64. }
  65.  
  66. compiled with gcc-2.2 -g -O4
  67.  
  68. arolla$ time a.out
  69.        15.7 real        15.6 user         0.0 sys  
  70. arolla$ int *a[10];
  71.  
  72. Here is a profile for the same program compiled with "-p":
  73.  
  74.  %time  cumsecs  #call  ms/call  name
  75.   40.4    10.69      1 10690.00  _main
  76.   18.1    15.48                  mcount
  77.   10.5    18.271000000     0.00  .rem
  78.   10.5    21.05                  _strcpy
  79.    9.5    23.571000001     0.00  _malloc
  80.    6.3    25.25 999991     0.00  _free
  81.    4.6    26.46                  _realloc
  82.    0.0    26.46      1     0.00  .udiv
  83.    ...
  84.  
  85. Now, the time spent in _malloc, _free, and (presumably) _strcpy is
  86. storage allocation related. This is a total of 8.2 seconds, or 50% of
  87. the running time of the program.
  88.  
  89. ================================================================
  90.  
  91. int *a[10];
  92.  
  93. void *gc_malloc();
  94.  
  95. main() {
  96.     int i;
  97.     gc_init();
  98.     for(i=0;i<1000000;i++) {
  99.         int j = i%10;
  100.         int k,*p;
  101.         if(a[j]) gc_free(a[j]);
  102.         p=(int*)gc_malloc(10*sizeof (int));
  103.         a[j]=p;
  104.         for(k=0;k<10;k++) *p++ = 0;
  105.     }
  106. }
  107.  
  108. compiled with gcc-2.2 -g -O4 memory-gc-auto.c ~/mit/src/lib/cgc/gc.a
  109. (Boehm-Dehmers collector version 1.6)
  110.  
  111. arolla$ time a.out
  112.        16.8 real        16.6 user         0.0 sys  
  113. arolla$
  114.  
  115. ================================================================
  116.  
  117. int *a[10];
  118.  
  119. void *gc_malloc();
  120.  
  121. main() {
  122.     int i;
  123.     gc_init();
  124.     for(i=0;i<1000000;i++) {
  125.         int j = i%10;
  126.         int k,*p;
  127.         p=(int*)gc_malloc(10*sizeof (int));
  128.         a[j]=p;
  129.         for(k=0;k<10;k++) *p++ = 0;
  130.     }
  131.     gcollect();
  132. }
  133.  
  134. compiled with gcc-2.2 -g -O4 memory-gc-auto.c ~/mit/src/lib/cgc/gc.a
  135. (Boehm-Dehmers collector version 1.6)
  136.  
  137. arolla$ time a.out
  138.        12.3 real        12.1 user         0.2 sys  
  139. arolla$
  140.  
  141. Note that this is _faster_ than the version that calls gc_free
  142. explicitly. (Of course, GC has an unusually low overhead in this case,
  143. since there are very few roots.)
  144.  
  145. ================================================================
  146.  
  147. template <class T>
  148. struct Counted {
  149.  private:
  150.     int *count;
  151.     T *object;
  152.     void drop() {
  153.         if(!count) return;
  154.         (*count)--;
  155.         if(*count<=0) {
  156.             delete count;
  157.             delete object;
  158.             count=0;
  159.             object=0;
  160.         }
  161.     }
  162.     void acquire() {
  163.         (*count)++;
  164.     }
  165.  public:
  166.     Counted() {
  167.         count=0;
  168.         object=0;
  169.     }
  170.     Counted(T *object):object(object) {
  171.         count = new int(1);
  172.     }
  173.     ~Counted() {
  174.         drop();
  175.     }
  176.     Counted(Counted &other) {
  177.         count=other.count;
  178.         object=other.object;
  179.         acquire();
  180.     }
  181.     Counted &operator=(Counted &other) {
  182.         drop();
  183.         count=other.count;
  184.         object=other.object;
  185.         acquire();
  186.         return *this;
  187.     }
  188.  
  189.     T &operator*() {return *object;}
  190.     T *operator->() {return object;}
  191.     operator T() {return *object;}
  192. };
  193.  
  194. struct IArt {
  195.     int a[10];
  196. };
  197.  
  198. typedef Counted<IArt> CIArt;
  199.  
  200. CIArt a[10];
  201.  
  202. main() {
  203.     for(int i=0;i<1000000;i++) {
  204.         a[i%10] = CIArt(new IArt);
  205.     }
  206. }
  207.  
  208. compiled with gcc-2.2 -g -O4:
  209.  
  210. arolla$ time a.out
  211.        33.0 real        32.8 user         0.0 sys  
  212. arolla$
  213.  
  214. ================================================================
  215.  
  216. val a = Array.array(10,Array.array(10,0));
  217.  
  218. fun doit(0) = ()
  219.   | doit(i) =
  220.     (Array.update(a,i mod Array.length(a),Array.array(10,0));
  221.      doit(i-1))
  222.  
  223. compiled with nj-sml-0.85
  224.     
  225. - timeit(fn () => doit(1000000));
  226. user: 16.130000  gc: 1.720000  system: 0.030000  real: 17.902393
  227. val it = () : unit
  228. - 
  229.  
  230. ================================================================
  231.