>>>>> "clgonsal" == Carl Laurence Gonsalves <········@undergrad.math.uwaterloo.ca> writes:
In article <··········@undergrad.math.uwaterloo.ca> ········@undergrad.math.uwaterloo.ca (Carl Laurence Gonsalves) writes:
clgonsal> The incredible slowness of Java is only evidence of the inefficiency of
clgonsal> garbage collection. I've programmed in a few languages that have garbage
clgonsal> collection (among them are Scheme, Modula-3, and now Java), and all have
clgonsal> been *much* slower than C or C++. I'm not saying Java is bad. ...
You must be joking. Aside from higher programming cost (for worrying
about memory leak and dangling pointers), malloc/free (or new/delete)
is generally slower than cons/gc because cost of free is proportional
to the amount of objects died during computation while gc cost isn't.
Besides, many implementations of languages that have garbage
collection has cons-aware compilers which opencode data-allocating
operations.
See e.g. the following article and also article in Lisp Pointers
Vol.8, No.1.
In short, if you allocate the same amount of data then memory
management cost should be lower in Lisp than in C. So having garbage
collection can never be a cause of inefficiency of a language.
(Poorly implemented garbage collector can slows down *an
implementation*, of course.)
In article <·····················@lager.bbn.com> ········@lager.bbn.com (Ken Anderson) writes:
kanderso> MALLOC/CONS 5.8 4.0
kanderso> FREE/GC 25.4 9.7
kanderso> ---------------------
kanderso> TOTAL 31.2 14.7
kanderso> So, CONS/GC is about twice as faster as MALLOC/FREE here. Object lifetimes
kanderso> match the assumptions of ephemeral GC quite well here (exponential
kanderso> lifetimes which are otherwise unpredicatable). You milage may vary.
If your Lisp program really runs slower than C counterpart, then they
may not be truly `equivalent'. I often see programmers tend to use
inefficient algorithms in Lisp which they don't use in C; they
generate unnecessary garbages, or they use linear search where it
isn't appropriate. They stick to APPEND, MEMBER, UNION etc. which
they learned from introductory textbooks.
--mad
;;; Keio University
;;; Faculty of Science and Technology
;;; Department of Math
;;; MAEDA Atusi (In Japan we write our family names first.)
;;; ···@math.keio.ac.jp
From: Paul Wilson
Subject: Re: Garbage collection cost (was Re: Parenthesized syntax challenge)
Date:
Message-ID: <45ksdk$7gr@jive.cs.utexas.edu>
In article <·················@tanzanite.math.keio.ac.jp>,
MAEDA Atusi <···@math.keio.ac.jp> wrote:
>>>>>> "clgonsal" == Carl Laurence Gonsalves <········@undergrad.math.uwaterloo.ca> writes:
>In article <··········@undergrad.math.uwaterloo.ca> ········@undergrad.math.uwaterloo.ca (Carl Laurence Gonsalves) writes:
>> The incredible slowness of Java is only evidence of the inefficiency of
>> garbage collection. I've programmed in a few languages that have garbage
>> collection (among them are Scheme, Modula-3, and now Java), and all have
>> been *much* slower than C or C++. I'm not saying Java is bad. ...
>
>You must be joking. Aside from higher programming cost (for worrying
>about memory leak and dangling pointers), malloc/free (or new/delete)
>is generally slower than cons/gc because cost of free is proportional
>to the amount of objects died during computation while gc cost isn't.
While the original poster was both wrong and goofy, this counterargument
isn't really right. The asymptotic complexity of GC is pretty much
irrelevant---what matters is the actual constant factors (ratio of
allocated data to live data, etc.). In practice, GC tends to cost a
little, but you generally get it back in reduced bookkeeping and
hassles in your application code.
It's a myth that GC is expensive, but it's also a myth that it's cheaper
than malloc/free for any very simple reason. A well-implemented malloc
and free should be very fast, and the real costs are in the contortions
you get in your applications.
For more info, you might see followups that made it to some of the three
newsgroups the original post went to (but not all), and a recent thread
in comp.lang.scheme. Hans Boehm has clearly argued (again) that the
asymptotic arguments about GC cost (and about relative costs of copying
vs. non-copying GC) just don't wash. He (and I) have repeatedly tried
to kill all of these myths, but they're very hardy memes. There are
some similar misunderstandings of generational GC issues.
For detailed discussions of these issues, check out my long survey on
garbage collection (in revision for Computing Surveys) and my new survey
on memory allocators. Both are available via my web page (click on
the "OOPS Research Group" button) or via ftp. See my .sig, below, for
pointers. (The OOPS web page also has pointers to Henry Baker's
web page, and Hans Boehm's ftp site. The thread in comp.lang.scheme
contains a pointer to a particular page on Hans' site that discusses
asymptotic complexity vs. constant factors.)
--
| Paul R. Wilson, Comp. Sci. Dept., U of Texas @ Austin (······@cs.utexas.edu)
| Papers on memory allocators, garbage collection, memory hierarchies,
| persistence and Scheme interpreters and compilers available via ftp from
| ftp.cs.utexas.edu, in pub/garbage (or http://www.cs.utexas.edu/users/wilson/)
On 13 Oct 1995 00:11:16 -0500, ······@cs.utexas.edu (Paul Wilson)
wrote:
>It's a myth that GC is expensive, but it's also a myth that it's cheaper
>than malloc/free for any very simple reason. A well-implemented malloc
>and free should be very fast, and the real costs are in the contortions
>you get in your applications.
>
Not forgetting some more myths, namely that doing your own memory
management ends all software quality as we know it. This axiom is
firmly stated in all GC backgrounding.
One aspect of the GC applications I have missed is that you invoke an
object OK, but you also have to say that you are disinterested in it
(which involves a pointer nullification showhow), but you don't dare
delete it, because you cannot ensure the structure of your programs...
hmm ... who ever heard of properly ordered/boundaried/containerised
OO design!
···@math.keio.ac.jp (MAEDA Atusi) wrote:
>You must be joking. Aside from higher programming cost (for worrying
>about memory leak and dangling pointers), malloc/free (or new/delete)
>is generally slower than cons/gc because cost of free is proportional
>to the amount of objects died during computation while gc cost isn't.
just a sec. Are you saying that the number of free call necessary in a GC
system is different than the number of free calls in a malloc/free program
which allocates the same number of objects ? If yes, I'd like to see a
reference or discussion on this.
If you are not saying that (which I don't think you can), than a "perfectly
implemented" malloc/free program has a lower bound in terms of memory
management cost because the "programmer" (remember that person who wrote the
perfect program ?) knows exactly when the memory is not needed anymore and
doesn't incur any costs for finding out which objects are to be collected. IOW,
a GC program's memory management cost will be always higher than that of a
malloc/free program. BUT whether the cost difference justifies the added
enormous cost of developing an asymptotically perfect malloc/free program is a
completely different question.
I can believe that GC systems can be as fast as malloc/free systems but if
malloc/free systems are implemented correctly and as efficiently as possible,
there is no way a GC system can be faster than them.
muzo
standard disclaimer
In article <··········@voyager.internex.net> ·····@msn.com writes:
>···@math.keio.ac.jp (MAEDA Atusi) wrote:
>>You must be joking. Aside from higher programming cost (for worrying
>>about memory leak and dangling pointers), malloc/free (or new/delete)
>>is generally slower than cons/gc because cost of free is proportional
>>to the amount of objects died during computation while gc cost isn't.
>
>just a sec. Are you saying that the number of free call necessary in a GC
>system is different than the number of free calls in a malloc/free program
>which allocates the same number of objects ? If yes, I'd like to see a
>reference or discussion on this.
>
>If you are not saying that (which I don't think you can), than a "perfectly
>implemented" malloc/free program has a lower bound in terms of memory
>management cost because the "programmer" (remember that person who wrote the
>perfect program ?) knows exactly when the memory is not needed anymore and
>doesn't incur any costs for finding out which
>objects are to be collected. IOW,
>a GC program's memory management cost will be always higher than that of a
>malloc/free program. BUT whether the cost difference justifies the added
>enormous cost of developing an asymptotically perfect malloc/free program is a
>completely different question.
>
>I can believe that GC systems can be as fast as malloc/free systems but if
>malloc/free systems are implemented correctly and as efficiently as possible,
>there is no way a GC system can be faster than them.
You are ignoring the space and time requirements of whatever machinery
the malloc/free programmer must put in place to keep track of all space
allocated and to do the appropriate check on the books to decide
when to free storage. Keeping track of allocated storage by yourself
not only requires programming (and maintenance) effort, but run-time
costs when it's doing its "perfect" job.
If a programmer had to do this task herself, over and over for every
program written, she might decide to build some more systematic tools
to handle it. Such tools, when refined and elaborated, could well
be a garbage collector. In fact, a great deal of attention can be, and
has been, paid to the theory and implementation of GC systems. Their
abilities often exceed a home-grown malloc/free facility put into place
quickly to get a job done for a specific program.
Finally, and I can never emphasize this too much, it is possible to
write code that generates lots of garbage and slows things down, but
the same operations could be accomplished by code that generates
little or no garbage. It is important to learn how to write such
space-conserving code.
>muzo
Bob Futrelle
--
Prof. Robert P. Futrelle | Biological Knowledge Lab, College of CS
Office: (617)-373-2076 | Northeastern University, 161CN
Fax: (617)-373-5121 | 360 Huntington Ave.
········@ccs.neu.edu | Boston, MA 02115
From: Paul Wilson
Subject: Re: Garbage collection cost (was Re: Parenthesized syntax challenge)
Date:
Message-ID: <462uqo$nfn@jive.cs.utexas.edu>
In article <··········@camelot.ccs.neu.edu>,
Robert Futrelle <········@ccs.neu.edu> wrote:
>
>If a programmer had to do this task herself, over and over for every
>program written, she might decide to build some more systematic tools
>to handle it. Such tools, when refined and elaborated, could well
>be a garbage collector.
This is in fact exactly what happens in practice. Many large programs
end up containing some form of garbage collection---often using
reference counting---to make it easier to modify and maintain
the program.
Unfortunately, these hand-hacked GC's are often poorly implemented,
costing more than a GC built into a language by an expert. They
are also often limited (e.g., reference counting can't reclaim cycles,
so you may get unexpected leaks) and/or buggy and/or hard to maintain.
>In fact, a great deal of attention can be, and
>has been, paid to the theory and implementation of GC systems. Their
>abilities often exceed a home-grown malloc/free facility put into place
>quickly to get a job done for a specific program.
Yes. It's very common in languages like C++ for people to write their
own special purpose allocators. (In C++ this is often done with
weird constructors and operator overloading.) This is often done to
get around bad implementations of malloc, and the resulting kludges
are often less efficient than a good malloc or a good GC. Bleah.
>Finally, and I can never emphasize this too much, it is possible to
>write code that generates lots of garbage and slows things down, but
>the same operations could be accomplished by code that generates
>little or no garbage. It is important to learn how to write such
>space-conserving code.
Actually, you can emphasize this too much. With a good generational
GC, allocation is usually pretty cheap, and the hacks necessary to
avoid allocation may actually be slower than the cleaner code that
uses allocation a lot. Allocating short-lived data usually
doesn't cost much, and you're better off writing your code cleanly
and maintainably rather than bumming a few allocations here and there.
(A generational GC shifts the usual costs of operations, making allocation
cheaper and side-effects to old data more expensive.)
--
| Paul R. Wilson, Comp. Sci. Dept., U of Texas @ Austin (······@cs.utexas.edu)
| Papers on memory allocators, garbage collection, memory hierarchies,
| persistence and Scheme interpreters and compilers available via ftp from
| ftp.cs.utexas.edu, in pub/garbage (or http://www.cs.utexas.edu/users/wilson/)
······@sphinx.biosci.wayne.edu (Kenneth R. Knight) writes:
>Let me suggest another possible example of a real-world system that uses
>GC at its core: Newtons.
Don't forget the level 2 PostScript interpreter in your printer ...
Hans-J. Boehm
(·····@parc.xerox.com)
Standard disclaimer ...
In article <·········@news.parc.xerox.com>, ·····@parc.xerox.com (Hans
Boehm) wrote:
] ······@sphinx.biosci.wayne.edu (Kenneth R. Knight) writes:
]
] >Let me suggest another possible example of a real-world system that uses
] >GC at its core: Newtons.
]
] Don't forget the level 2 PostScript interpreter in your printer ...
no wonder my NeXT machine swaps so much :-)
s.
·····@msn.com (muzo) writes:
>···@math.keio.ac.jp (MAEDA Atusi) wrote:
>>You must be joking. Aside from higher programming cost (for worrying
>>about memory leak and dangling pointers), malloc/free (or new/delete)
>>is generally slower than cons/gc because cost of free is proportional
>>to the amount of objects died during computation while gc cost isn't.
>just a sec. Are you saying that the number of free call necessary in a GC
>system is different than the number of free calls in a malloc/free program
>which allocates the same number of objects ? If yes, I'd like to see a
>reference or discussion on this.
Come on, there might be *no* calls to "free" when a GC is used.
(I say "might" because you might have both GC and some explicit
deallocation.)
>If you are not saying that (which I don't think you can), than a "perfectly
>implemented" malloc/free program has a lower bound in terms of memory
>management cost because the "programmer" (remember that person who wrote the
>perfect program ?) knows exactly when the memory is not needed anymore and
>doesn't incur any costs for finding out which objects are to be collected.
So long as Paul Wilson (and Hans Boehm) are in the business of
trying to kill myths, could they please so something about _this_
one? The idea that malloc/free must be better because the
programmer knows exactly ... is, these days, one of the chief
weapons used against GC and indeed against entire families of
programming languages.
>I can believe that GC systems can be as fast as malloc/free systems but if
>malloc/free systems are implemented correctly and as efficiently as possible,
>there is no way a GC system can be faster than them.
You may be right, but why, exactly? And will it be so for all
programs?
-- jd
From: Paul Wilson
Subject: Re: Garbage collection cost (was Re: Parenthesized syntax challenge)
Date:
Message-ID: <4614sm$704@estoril.cs.utexas.edu>
In article <··········@Cadence.COM>, Simon Kinahan <simonk> wrote:
>
>Thats the point. The copying algorithm (to my knowledge this doesn't apply to
>any other form og GC) never needs to find out which objects are allocated or
>not. It just blindly copoies.
Actually, a couple of people have shown how to make a non-copying collector
that is isomorphic to a copying collector and shares its basic ability
to reclaim an arbitrary amount of free memory in constant time (once the
live data have been traversed and distinguished).
The basic idea is that you don't really need to move things from one
area of memory to another, and reclaim the old area. You just have to
move things from one *set* to another, and whatever remains in the old
set after the live things are removed must be free.
All you need is an efficient implementation of sets, e.g. doubly-linked
lists. You keep hidden data structures, and move things from one data
structure to another as they're traversed by the GC. (When the GC's
tracing traversal reaches a live object, it unlinks the corresponding
block of memory from the old subject-to-gc list, and links it into another,
the known-live-at-this-gc list.)
At the end of the tracing phase, whatever's left in the original list is
known to be garbage, and that list can just be appended to a free list
and used for subsequent allocation.
Thomas Wang used this idea in what he called a "fake copying" collector,
and Baker used it in his "treadmill" design.
We use it in our real-time GC, where it's handy to be able to reclaim
the free memory very quickly rather than sweeping through memory.
(Sweep costs can be low, and pipelined with other GC phases to avoid
losing real-time---as in Quiennec's mark-during-sweep collector---but
being able to reclaim memory immediately in constant time is even
nicer.)
This stuff is described in the my GC survey, which contains pointers to
other peoples' papers. Citations are in my heaps.bib file, also available
on our ftp site.
--
| Paul R. Wilson, Comp. Sci. Dept., U of Texas @ Austin (······@cs.utexas.edu)
| Papers on memory allocators, garbage collection, memory hierarchies,
| persistence and Scheme interpreters and compilers available via ftp from
| ftp.cs.utexas.edu, in pub/garbage (or http://www.cs.utexas.edu/users/wilson/)
From: Paul Wilson
Subject: Re: Garbage collection cost (was Re: Parenthesized syntax challenge)
Date:
Message-ID: <4615eo$717@estoril.cs.utexas.edu>
In article <··········@estoril.cs.utexas.edu>,
Paul Wilson <······@cs.utexas.edu> wrote:
>In article <··········@Cadence.COM>, Simon Kinahan <simonk> wrote:
>>
>>Thats the point. The copying algorithm (to my knowledge this doesn't apply to
>>any other form og GC) never needs to find out which objects are allocated or
>>not. It just blindly copoies.
>
>Actually, a couple of people have shown how to make a non-copying collector
>that is isomorphic to a copying collector and shares its basic ability
>to reclaim an arbitrary amount of free memory in constant time (once the
>live data have been traversed and distinguished).
>
I should also have mentioned that these fake-copying collectors also
can support very fast allocation. You can maintain an array of lists of
different-sized blocks, and index into the list very quickly to find
the appropriate list, based on the requested size. For languages like
Lisp, where the desired size is usually known statically
(e.g., in CONS)---and often in most strongly typed languages---the index
can be computed at compile time
All that's necessary at run time (in the usual case) is
1. a load to get the free list pointer,
2. a check to see if it's null,
3. a pointer dereference to get the "next" pointer of the first
block in the list (i.e., the pointer to the rest of the
list, and
4. an assignment to update the free list (i.e., skip past the allocated
block), and
So we're talking about a small handful of instructions here---allocating
from free lists is not much slower than allocating from contiguous memory,
if you do it right.
Actually, under some circumstances, you can even make it marginally faster.
to "remove" something from a list, you can just bump a pointer that
separates the "allocated" part of the list from the "free" part. This
is isomorphic to the usual copying collector technique of using an
allocation pointer to separate the allocated part of memory from the
free part, and just bumping the pointer to do the allocation.
These things are described in more detail in my GC survey and our allocator
survey.
--
| Paul R. Wilson, Comp. Sci. Dept., U of Texas @ Austin (······@cs.utexas.edu)
| Papers on memory allocators, garbage collection, memory hierarchies,
| persistence and Scheme interpreters and compilers available via ftp from
| ftp.cs.utexas.edu, in pub/garbage (or http://www.cs.utexas.edu/users/wilson/)
·····@msn.com (muzo) writes:
>I can believe that GC systems can be as fast as malloc/free systems but if
>malloc/free systems are implemented correctly and as efficiently as possible,
>there is no way a GC system can be faster than them.
There are cases in which a tracing collector can be much faster than anything
else I can think of. See ftp://parcftp.xerox.com/pub/gc/example.html for an
example.
In general, garbage collectors seem to perform relatively better in a
multithreaded environment. Acquiring a lock for every free call is expensive.
Even in a single-threaded environment, free has to read some amount of
data structure information for every call. A garbage collector (especially
a copying one) frees more than one element at a time.
(The cited example actually relies on a completely different observation.)
Hans-J. Boehm
(·····@parc.xerox.com)
Standard disclaimer ...
On 15 Oct 1995 15:11:49 -0800, ···@best.com () wrote:
>| I can believe that GC systems can be as fast as malloc/free systems but if
>| malloc/free systems are implemented correctly and as efficiently as possible,
>| there is no way a GC system can be faster than them.
>
>That belief is common but false. You can make specially constructed
>test cases using GC nearly arbitrarily faster than anything equivalent
>that could be called a "malloc/free system". In practice, the
>differences are usually not that dramatic.
Wait a minute doing your own memory management is zero cost.
The tranversal phase of GC is the cost.
Of course when you are creating and deleting heaps you
have the immediate deletion tasks (I have a permutation class
that does copy constuctors of bags of pointers per
permutation list entry (and their deletion) as the permutation phases
build up .... YEAPPS! But this is an unusual case.
In <··········@st-james.comp.vuw.ac.nz>, ········@branz.org.nz (Christopher Price) writes:
>Wait a minute doing your own memory management is zero cost.
>The tranversal phase of GC is the cost.
Sorry, I think I've lost you here.
Have you ever profiled a program that uses malloc/free? I think you
will find that there is some cost involved. In the kind of programs I
work with have intermediate computation stages that generate a lot of
temporary data (a ration of about 40 to 1, temporary to live, in a
smallish test case for something I am working on now). Typically in a
C/C++ environment I get 30-35% of execution time spent in my rather
specialised malloc/free routines. I've seen 98% using standard malloc
and free.
I believe that you may also find that there is a measurable proportion
of live data that is there solely to keep track of the live data.
I've seen this in the 20-25% range, though I do not think this is
typical (I am not talking about the overhead of malloc and free). Of
course, if you have these structures to keep track of live data, then
you have to maintain them at runtime, and this, of course, consumes
additional execution time. That execution time cannot necessarily be
isolated from the actual execution time of the application, and in
fact, is not included in the 30-35% of execution time I mentioned
above).
Then, on top of all that, there is at least some cost to the design of
your software that results from explicit memory management. If
nothing else, you have to consider it at design time, and this takes
time, and so has a cost. The big gain here with GC is that the global
issue of memory management is transformed into localised management of
live data. I believe you expressed some concern in a separate post
about having to zero out pointers in GC. This is not difficult thing
to do -- when some object no longer requires a reference to an object
you simply remove the reference (the only difference between this and
setting a pointer to 0 in C++ is that you never have to concern
yourself with the possibility that this may or may not be the last
reference to that object).
As a (dramatic) concrete example I can describe briefly something I
did a few years ago. I implemented a manufacturing scheduling
algorithm in C++. I could not get the malloc/free overhead below 58%
despite using every trick known by me or anyone else at the company.
Worse was the cost of adding any functionality to the thing, it took
days for a feature of moderate complexity. Since this was supposed to
be an investigation into an algorithm (i.e. an algorithmic
improvement) the addition of features was of greatest interest to us.
As a result we re-wrote it in smalltalk. As expected the features
became much easier to add. But, quite unexpected by me at least, the
execution time of the smalltalk implementation was statistically
indistinguishable from the C++ implementation, despite the fact that
smalltalk simply could not execute the algorithm as quickly as C++.
An investigation into this resulted in confirmation that the GC
overhead was much less in smalltalk than the explicit stuff in C++
especially when considering the time that must have been lost
maintaining the live data in C++ that we could not distinguish from
the time spent in the algorithm. The cost? Eight months working with
the C++ implementation.
Cheers,
Bob
Paul Wilson notes [amongst other good points]:
It's not really clear what NOT having a GC costs in practice, and it's
very difficult to get reliable data on the subject. The few comparisions
of GC'd and non-GC'd code that are available generally fail to control
the many variables involved. Many simply retrofit a program developed
without a GC with a GC, and compare the costs of the non-GC'd version
with the same code running with a GC instead of explicit freeing. This
is quite unfair to GC's, one of whose major benefits is allowing you
to code your application more elegantly in the first place---the
experiments are rigged against GC's, because the cruft in the application
is still there; the indirect costs of extra copying and poor modularity
are still there, so the GC'd version pays twice.
this claim looks fine in theory, but in practice, GC-able C code (for
example) looks as contorted as any one can come up with using malloc/free.
new cruft in the form of stacks of root pointers, object registration
calls are added. sometimes additional indirection (eg handles) are used.
the result is just as hard to maintain as any, especially if you forget
to protect something you should have. i understand the point you are
trying to make, but it is now as simple as you make it sound.
cheers... oz