Re: Promptness of collection

In a similar vein, my student Matthew Hertz and I performed an
extensive experimental evaluation of the relative costs of garbage
collection and explicit memory allocation (in the context of Java, via
simulator magic and the Merlin algorithm).

Among other things, we measured the effect of reclaiming memory as
soon as possible (immediately after its last use - liveness-based),
versus reclaiming it as late as possible (just before the last
reference goes away - reachability-based). The former resulted in
substantial memory savings but not that substantial of a difference in
execution time (for example, see tables 4 and 5).

http://dl.acm.org/citation.cfm?doid=1094811.1094836

@inproceedings{DBLP:conf/oopsla/HertzB05,
  author    = {Matthew Hertz and
               Emery D. Berger},
  title     = {Quantifying the performance of garbage collection vs. explicit
               memory management},
  booktitle = {OOPSLA},
  year      = {2005},
  pages     = {313-326},
  ee        = {http://doi.acm.org/10.1145/1094811.1094836},
  crossref  = {DBLP:conf/oopsla/2005},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract:

Garbage collection yields numerous software engineering benefits, but
its quantitative impact on performance remains elusive. One can
compare the cost of conservative garbage collection to explicit memory
management in C/C++ programs by linking in an appropriate collector.
This kind of direct comparison is not possible for languages designed
for garbage collection (e.g., Java), because programs in these
languages naturally do not contain calls to free. Thus, the actual gap
between the time and space performance of explicit memory management
and precise, copying garbage collection remains unknown.

We introduce a novel experimental methodology that lets us quantify
the performance of precise garbage collection versus explicit memory
management. Our system allows us to treat unaltered Java programs as
if they used explicit memory management by relying on oracles to
insert calls to free. These oracles are generated from profile
information gathered in earlier application runs. By executing inside
an architecturally-detailed simulator, this "oracular" memory manager
eliminates the effects of consulting an oracle while measuring the
costs of calling malloc and free. We evaluate two different oracles: a
liveness-based oracle that aggressively frees objects immediately
after their last use, and a reachability-based oracle that
conservatively frees objects just after they are last reachable. These
oracles span the range of possible placement of explicit deallocation
calls.

We compare explicit memory management to both copying and non-copying
garbage collectors across a range of benchmarks using the oracular
memory manager, and present real (non-simulated) runs that lend
further validity to our results. These results quantify the time-space
tradeoff of garbage collection: with five times as much memory, an
Appel-style generational collector with a non-copying mature space
matches the performance of reachability-based explicit memory
management. With only three times as much memory, the collector runs
on average 17% slower than explicit memory management. However, with
only twice as much memory, garbage collection degrades performance by
nearly 70%. When physical memory is scarce, paging causes garbage
collection to run an order of magnitude slower than explicit memory
management.

--
Professor Emery Berger
School of Computer Science
University of Massachusetts, Amherst
www.cs.umass.edu/~emery


On Wed, Mar 13, 2013 at 8:31 AM, Eliot Moss <[email protected]> wrote:
> Some time ago Ole Agesen, David Detlefs, and I studied what
> would happen if we added a liveness analysis to Java and
> cleared pointers when they became dead. Normally they would
> still contain an old value until the end of their scope
> (which might or might not be the end of the method call).
>
> Here's the citation and a link:
>
> Ole Agesen, David Detlefs, and J. Eliot B. Moss, ``Garbage Collection and
> Local
> Variable Type-Precision and Liveness in Java Virtual Machines,'' 1998 ACM
> SIGPLAN Conference on Programming Language Design and Implementation (PLDI
> 1998), June
> 1998, Montreal, Quebec, Canada, pp.~269-279.
>
> http://www.cs.umass.edu/~moss/papers/pldi-1998-liveness.pdf
>
> We found there were cases where it made some difference. Also,
> there are subtleties of the language (the JVM spec really) that
> make it hard to achieve the best. Specifically, if the last use
> of a pointer within a given method is to pass it as an argument
> to another method, then we can't clear it out until the method
> returns, which extends the reachability of the referent if it dies
> during the method call.
>
> Regards -- Eliot