Automatic Garbage Collection Taken Too Far!
Tom Emerson
Mike> [Much deleted]
Mike> Precisely, memory management shouldn't be a concern to the programmer.
Mike> Modern programming languages such as Chez Scheme or SML implement
Mike> garbage collection algorithms which surpass C++ memory management in
Mike> terms of speed and ease. Traditionally old Lisps and stuff are way to
Mike> slow to be effective, but things have changed. No wonder most new
Mike> programming languages implement garbage collection, its faster than
Mike> reclaiming your own storage, especially in systems with virtual memory
Mike> management.
Then people shouldn't use C for their programming. If they want this kind of
functionality, then use ML or Lisp or whatever. If you need fast code and if
you want complete control, use C or other systems level language. It is,
IMHO, and issue of chosing the right tool for the job.
Mike> -Mike
Tom
--
\ Systems Programmer --- EMBA Computer Facilty
Thomas Emerson \ University of Vermont, Burlington VT 05405 USA
tr...@uvm.edu /\ "Magic is real, unless declared integer"
/ \ (in-package "std-disclaimer")
Phil Howard KA9WGN / I am the NRA
> Ah! You have brought up another interesting point that has been
> ignored (by me as well) with respect to the absolute need for
> GC in languages that exclusively use objects (or actors as they
> are often called). Since objects in these languages (like Smalltalk
> Eiffel and Actor) constantly get created and then are no longer
> needed, the so-called "perfect C programmer" model of requiring
> the programmer to always deallocate explicitly that which s/he
> allocates not only is imperfect, it may actually be less efficient.
> Constant deallocation of space takes significant resources, which
> in a real-time program might interfere with the performance of
> the actual main-line code. Better to let a GC routine work its
> magic in the spare cycles of the system.
>
> As it turns out, Smalltalk had problems with this very issue
> early on when dealing with relatively small space objects like
> integers and ended up adding special processes for dealing with
> allocating, deallocating and reusing space for these types of
> objects.
I've run into the allocate/free cycle resource hog a lot in assembler
language. GC was still not practical, but work arounds did include
things like "caching" the memory resources in simple DLLQ's that could
be worked in O(1) (as long as something was there to be grabbed).
--
/***********************************************************************\
| Phil Howard --- KA9WGN --- p...@netcom.com | "The problem with |
| depending on government is that you cannot depend on it" - Tony Brown |
\***********************************************************************/
Phil Howard KA9WGN / I am the NRA
> QUESTION! How does one get the nitty gritty and the friendly in the
>same language.
>
> ANSWER! (one possible one anyhow) Add a "allocGC" method to the
>Object Class, which will self terminate the object when its reference is
>lost. And the programmer would have to follow the rule "don't do any
>funky stuff with referencing the object, 'cause once the original
>reference is gone, the object is free to die."
The nitty-gritty and the higher levels do need to be separated, in spirit,
but not necessarily to prevent their concurrent use. It's probably wise
to encapsulate the nitty gritty into the objects themselves, though, as
you might figure out. I do like the idea of the "allocGC", and if there
is any "garbage collector" as such, it should operate only if "allocGC"
is used (and not if not).
Phil Howard KA9WGN / I am the NRA
>Sure, but what is the point of getting into the nitty-gritty when you can at
>the accomplish the same thing, faster and "cleaner" in a language that takes
>care of that, and only has you worrying about abstraction and the algorithms
>necessary to accomplish what you want?
Depends.
If your argument were universal, there would no longer be any nitty-gritty
programming. But we know there still is. Of course maybe the argument is
valid but ignored.
However I still find many problems solved much easier and more quickly by
just getting down to the nitty-gritty and making it do exactly what I want
it to do, instead of trying to find workarounds to implementations that
do the nitty-gritty for you ..... the wrong way.
"If you want it done right....."
>Precisely, memory management shouldn't be a concern to the programmer. Modern
>programming languages such as Chez Scheme or SML implement garbage collection
>algorithms which surpass C++ memory management in terms of speed and ease.
>Traditionally old Lisps and stuff are way to slow to be effective, but things
>have changed. No wonder most new programming languages implement garbage
>collection, its faster than reclaiming your own storage, especially in systems
>with virtual memory management.
The problem I have see with garbage collection is not the CPU time it takes
up, but rather that it defers the use of that CPU time until later and does
all the garbage collection IN BULK, blocking execution of the program.
Depending on what the program is, delays for GC of more than 50 or 100
milliseconds can be detected, and over 250 can begin to be annoying.
Interactive games are one such example. So if current GC technology
allows things to keep on running, even for very large virtual address
spaces, then maybe it is time for me to re-examine. Tell me more.
Mike Percy
>Adam Christopher Swift <as...@andrew.cmu.edu> writes:
>> QUESTION! How does one get the nitty gritty and the friendly in the
>>same language.
>>
>> ANSWER! (one possible one anyhow) Add a "allocGC" method to the
>>Object Class, which will self terminate the object when its reference is
>>lost. And the programmer would have to follow the rule "don't do any
>>funky stuff with referencing the object, 'cause once the original
>>reference is gone, the object is free to die."
>The nitty-gritty and the higher levels do need to be separated, in spirit,
>but not necessarily to prevent their concurrent use. It's probably wise
>to encapsulate the nitty gritty into the objects themselves, though, as
>you might figure out. I do like the idea of the "allocGC", and if there
>is any "garbage collector" as such, it should operate only if "allocGC"
>is used (and not if not).
Interesting. In the course of my thesis work (on the Actor
computational model, building a viable VM for same), I needed some form
of GC, since actors come and go with such rapidity. SInce this was for
a distributed/parallel system, GC becomes a bit tricky (to say the
least). Rather than try to solve problems others are working on
(distributed GC), I have the actors trash themselves -- many actor codes
cuase actors to come onto existance for a very short period of time,
compute something, and then ... they hang around waiting for the next
message. When no one knows their address, they can be GCed. These
short-lived actors can (under the programmers control) compute their
thing, send the result off somewhere, and assume that their creator is
not going to send them anything else, and hasn't sent a copy of their
address anywhere. They kill themselves off with a become(garbage)
command.
So far, this has worked out well. The programmer (me) knows which
behaviors should end with a become(garbage) and writes them that way.
The other behaviors are almost always very long term objects which would
not be GCed anyway.
Interestingly enough, I use a modified distributed GC mechaism for
termination detection.
Mike Percy | gri...@hubcap.clemson.edu | I don't know about
Sr. Systems Analyst | msp...@clemson.clemson.edu | your brain, but mine
Info. Sys. Development | msp...@clemson.BITNET | is really...bossy.
Clemson University | (803) 656-3780 | (Laurie Anderson)
Scott Draves
Phil> So if current GC technology allows things to keep on running,
Phil> even for very large virtual address spaces, then maybe it is
Phil> time for me to re-examine. Tell me more.
there are two ways to do this: 1) use a seperate thread for the GC
process (can be hard to write), or 2) interleave GC with allocation
(can be expensive). i don't know of any major language
implementations that do either of these, however. the reason, as far
as i know, is simply lack of demand.
--
original
scott draves cheddar
sp...@cs.cmu.edu ranch
Globulator
> Ah! You have brought up another interesting point that has been
> ignored (by me as well) with respect to the absolute need for
> GC in languages that exclusively use objects (or actors as they
> are often called). Since objects in these languages (like Smalltalk
> Eiffel and Actor) constantly get created and then are no longer
> needed, the so-called "perfect C programmer" model of requiring
> the programmer to always deallocate explicitly that which s/he
> allocates not only is imperfect, it may actually be less efficient.
> Constant deallocation of space takes significant resources, which
> in a real-time program might interfere with the performance of
> the actual main-line code. Better to let a GC routine work its
> magic in the spare cycles of the system.
> As it turns out, Smalltalk had problems with this very issue
> early on when dealing with relatively small space objects like
> integers and ended up adding special processes for dealing with
> allocating, deallocating and reusing space for these types of
> objects.
Yes! We are in the midst of a project now in which one of the members
has created many small 'proxy' or 'smart pointer' classes. Since these
things generally live on the stack, they get allocated constantly and copied
almost every time a new method is called. The inefficiency really isn't
terribly important, 'cause we're event driven, and I don't care much about
the speed, but it takes a very LOOOOONNNNNGGGG time to step through even
a short series of method calls with the debugger. I'm constantly hopping
into constructors and destructors. Of course, it's somewhat of a circular
argument, because if we had some form of GC, much of the impetus for
developing 'smart pointers' in the first place is gone (although he plans
to do other things with them as well).
--
Tim McClarren (ti...@ncsa.uiuc.edu)|"I'm countin' down to the day deservin'
Mac Programmer (217)244-0015 | Fittin' for a king I'm waitin' for the
NCSA/STG@University of Illinois | time when I can Get to Arizona" PE Apoc 91
Jon Rosen
>
>Interesting. In the course of my thesis work (on the Actor
>computational model, building a viable VM for same), I needed some form
>of GC, since actors come and go with such rapidity. SInce this was for
>a distributed/parallel system, GC becomes a bit tricky (to say the
>least). Rather than try to solve problems others are working on
>(distributed GC), I have the actors trash themselves -- many actor codes
>cuase actors to come onto existance for a very short period of time,
>compute something, and then ... they hang around waiting for the next
>message. When no one knows their address, they can be GCed. These
>short-lived actors can (under the programmers control) compute their
>thing, send the result off somewhere, and assume that their creator is
>not going to send them anything else, and hasn't sent a copy of their
>address anywhere. They kill themselves off with a become(garbage)
>command.
ignored (by me as well) with respect to the absolute need for
GC in languages that exclusively use objects (or actors as they
are often called). Since objects in these languages (like Smalltalk
Eiffel and Actor) constantly get created and then are no longer
needed, the so-called "perfect C programmer" model of requiring
the programmer to always deallocate explicitly that which s/he
allocates not only is imperfect, it may actually be less efficient.
Constant deallocation of space takes significant resources, which
in a real-time program might interfere with the performance of
the actual main-line code. Better to let a GC routine work its
magic in the spare cycles of the system.
As it turns out, Smalltalk had problems with this very issue
early on when dealing with relatively small space objects like
integers and ended up adding special processes for dealing with
allocating, deallocating and reusing space for these types of
objects.
Jon Rosen
Mike Henry
> A GC is a really nice feature WHEN YOU WANT IT.
I agree, but when AGC makes your program faster why wouldn't you want it?
> Obj-C gives you the same ability, which is "really cool".
Sure, but what is the point of getting into the nitty-gritty when you can at
the accomplish the same thing, faster and "cleaner" in a language that takes
care of that, and only has you worrying about abstraction and the algorithms
necessary to accomplish what you want?
> It would be really nice to extend Obj-C in such a way that one could
>program in the style of the theoretical programmer (i.e. lamda calculus)
>where your attention is not at all devoted to memory considerations,
>bit/byte alignment orders, CPU, or any facet of your hardware
>architecture.
Precisely, memory management shouldn't be a concern to the programmer. Modern
programming languages such as Chez Scheme or SML implement garbage collection
algorithms which surpass C++ memory management in terms of speed and ease.
Traditionally old Lisps and stuff are way to slow to be effective, but things
have changed. No wonder most new programming languages implement garbage
collection, its faster than reclaiming your own storage, especially in systems
with virtual memory management.
>- adam
-Mike
--
Mike Henry INET : mi...@cs.uoregon.edu ///
441 E 13th St. #2 mi...@ida.liu.se ///
Eugene, OR. 97401 \\\///
USA TEL : +1 (503) 344-5122 \XX/
Tom Emerson
Adam> This is out of control.
Perhaps.
[Several good points deleted . . .]
Adam> C is portable assembly (please don't carry on some snot-infested
Adam> semantic argument about that statement), and should be that way. It's
Adam> the nitty gritty I wanny play with the guts of my machine language of
Adam> choice!
Here here, I was waiting for someone to mention this little fact. I can't say
I would express it the same way, but the fact of the matter is that C gives
the programmer this low level functionality. That is the purpose of the
language. To me an OO C is rather silly - one is putting I high level of
abstraction on top of relatively low-level language (ok, so it's a
``mid-level'' language, so sue me).
An OO Pascal or similar bondage-and-discipline language makes sense. OO
functional or semi-functional languages make even more sense. OO C doesn't,
IMHO.
Adam> It would be really nice to extend Obj-C in such a way that one could
Adam> program in the style of the theoretical programmer (i.e. lamda calculus)
Adam> where your attention is not at all devoted to memory considerations,
Adam> bit/byte alignment orders, CPU, or any facet of your hardware
Adam> architecture.
If you want to do this, use Lisp, not C. Trying to raise C up to this level
is like nailing jelly to a tree. Why bother? There are already perfectly good
languages that give you this.
[...]
Adam> QUESTION! How does one get the nitty gritty and the friendly in the
Adam> same language.
Adam> ANSWER! (one possible one anyhow) Add a "allocGC" method to the
Adam> Object Class, which will self terminate the object when its reference is
Adam> lost. And the programmer would have to follow the rule "don't do any
Adam> funky stuff with referencing the object, 'cause once the original
Adam> reference is gone, the object is free to die."
That is placing untold restrictions on the programmer. While the idea is a
good one, I don't know if it makes a whole lot of sense. You would have to
link your GC into your application, you would have to handle reference
counts... a royal pain.
Just my $0.02 worth.
Tree
Graham Matthews
> Ah! You have brought up another interesting point that has been
> ignored (by me as well) with respect to the absolute need for
> GC in languages that exclusively use objects (or actors as they
> are often called).
Just a minor nitpick, Jon, but actors and objects are not the same
thing. The difference lies in that fact that OO languages have a
single thread of control, whereas actor languages do not. Subtle
difference I know, but maybe you wanted to know :-)
Cheers
graham
--
Graham Matthews And it's true we are immune
Pure Math, Uni.Sydney, Oz When fact is fiction and T.V. is reality
gra...@maths.su.oz.au
Phil Howard KA9WGN / I am the NRA
>Here here, I was waiting for someone to mention this little fact. I can't say
>I would express it the same way, but the fact of the matter is that C gives
>the programmer this low level functionality. That is the purpose of the
>language. To me an OO C is rather silly - one is putting I high level of
>abstraction on top of relatively low-level language (ok, so it's a
>``mid-level'' language, so sue me).
One could conside the approach that an OO C allows you to isolate the
nitty gritty stuff which you can DO in C to let you write a program that
makes USE of the nitty gritty at a higher level.
>An OO Pascal or similar bondage-and-discipline language makes sense. OO
>functional or semi-functional languages make even more sense. OO C doesn't,
>IMHO.
How about a language that is higher level and has the look and feel (oops,
might get sued) of C (especially the syntax), and you can implement the
object methods using real C (including all the nitty gritty). Then just
call that higher level language "OO C". It isn't exactly C, but close
enough for C programmers to readily adapt. But the nitty gritty is still
available directly in the real C used to implement object methods and in
the OOC but using objects that have the nitty gritty hidden away in them.
>If you want to do this, use Lisp, not C. Trying to raise C up to this level
>is like nailing jelly to a tree. Why bother? There are already perfectly good
>languages that give you this.
A higher level language that has the look and feel of C would be better
(at least for the C programmers). Having it does not rule out using the
"real C".
Dave Schaumann
>tr...@newton.uvm.edu (Tom Emerson) writes:
>
>>Here here, I was waiting for someone to mention this little fact. I can't say
>>I would express it the same way, but the fact of the matter is that C gives
>>the programmer this low level functionality. That is the purpose of the
>>language. To me an OO C is rather silly - one is putting I high level of
>>abstraction on top of relatively low-level language (ok, so it's a
>>``mid-level'' language, so sue me).
>
>One could conside the approach that an OO C allows you to isolate the
>nitty gritty stuff which you can DO in C to let you write a program that
>makes USE of the nitty gritty at a higher level.
Of course, any problem you can solve with one turing-complete language
you can also solve with another. The *important* differences between
languages are really in the following areas:
1. expressability -- how easy is it to code the solution?
object-orientedness (and garbage collection) (and the concept of
high-level-languages, for that matter) all make solutions easier to
code.
2. efficiency -- how fast/small is the code that is generated?
Note that this is a complex function of compiler and hardware
technology, as much as it is a function of language design.
3. saftey -- how hard is it to shoot yourself in the foot?
Pascal has "high saftey". C has "low safety"
Now, it is true that C is very much a mid-level language. (I would reserve
"low level" for assembler languages). But that is not necessarily so. The
*spirit* of C is that it provide a reasonably machine-independant way to
specify algorithms that can be compiled into efficient executables. If
you can add features like object-orientedness without sacrificing the
efficiency aspect, I'd say the spirit of C has not been violated. (I also
think that C++ has mostly managed to do this).
>>An OO Pascal or similar bondage-and-discipline language makes sense. OO
>>functional or semi-functional languages make even more sense. OO C doesn't,
>>IMHO.
Obviously, I disagree. If you stick to your definition of C as "portable
assembly language", you're right. Personally, I think that's missing the
point, and selling C *way* short.
>How about a language that is higher level and has the look and feel C
>(especially the syntax), and you can implement the object methods using
>real C
This is exactly what C++ is. The original C++ "compiler" was merely a
C++ to C translator, which piped its output to a regular C compiler.
>It isn't exactly C, but close enough for C programmers to readily adapt.
No, it's not exactly C. I think it most ways it's far superior.
>>If you want to do this, use Lisp, not C. Trying to raise C up to this level
>>is like nailing jelly to a tree. Why bother? There are already perfectly good
>>languages that give you this.
>
>A higher level language that has the look and feel of C would be better
>(at least for the C programmers). Having it does not rule out using the
>"real C".
This gets back to my "important differences" between languages. In specifying
a language, you have to pick some balance between expressability, efficiency,
and safety. For instance, if you add the safety of Pascal's range checking,
you loose the efficiency avalable without it. If you add the expressability
of C's & (address-of) operator, you definitely loose safety. Lisp has high
expressability, reasonable safety, and not too much concern for efficiency.
But suppose you want an OO language that strikes a similar balance to C?
I guess the root of our disagreement is your assertion that C is fundamentally
and irrevokably a mid-level language with no room for higher level concepts.
Hopefully, I've made the case that this isn't so.
--
You're traveling through another dimension -- a dimension not only of sight and
sound but of mind. A journey into a wonderous land whose boundaries are that of
imagination. That's a signpost up ahead: your next stop -- the Twilight Zone
Ralf Brown
}Now, it is true that C is very much a mid-level language. (I would reserve
}"low level" for assembler languages). But that is not necessarily so. The
I wonder where Turbo Assembler 3.0 fits into the scheme of things....
OO Assembler, anyone? (TA3.0 provides objects, methods, virtual methods,
VMTs, inheritance, etc.)
--
{backbone}!cs.cmu.edu!ralf ARPA: RA...@CS.CMU.EDU FIDO: Ralf Brown 1:129/26.1
BITnet: RALF%CS.CMU.EDU@CARNEGIE AT&Tnet: (412)268-3053 (school) FAX: ask
DISCLAIMER? Did | Hansen's Library Axiom: The closest library doesn't
I claim something? | have the material you need.
Brandon S. Allbery KF8NH
+---------------
| Adam Christopher Swift <as...@andrew.cmu.edu> writes:
| Adam> C is portable assembly (please don't carry on some snot-infested
| Adam> semantic argument about that statement), and should be that way. It's
| Adam> the nitty gritty I wanny play with the guts of my machine language of
| Adam> choice!
|
| Here here, I was waiting for someone to mention this little fact. I can't say
| I would express it the same way, but the fact of the matter is that C gives
| the programmer this low level functionality. That is the purpose of the
| language. To me an OO C is rather silly - one is putting I high level of
| abstraction on top of relatively low-level language (ok, so it's a
| ``mid-level'' language, so sue me).
|
| An OO Pascal or similar bondage-and-discipline language makes sense. OO
| functional or semi-functional languages make even more sense. OO C doesn't,
| IMHO.
I disagree. Assuming the OO C is upwards compatible with vanilla C, it has
one advantage: you can do both the low level and the OO code in the same
language, for all intents and purposes. Better than writing the OO in
Modula-3 and the low-level code in C, then having to maintain code in two
completely different languages at the same time.
The same argument, of course, applies to a (hypothetical) low-level variant of
a language like Modula-3. Programs written in a single language are more
maintainable than programs in multiple languages. (Having written and
attempted to maintain a "bastard hybrid" of a system with parts in C,
Accell/SQL (commercial 4GL), Perl, and SB-Prolog (!), I speak from experience.
I eventually chopped out both the Prolog and the Perl by rewriting both parts
in C.)
++Brandon
--
Brandon S. Allbery, KF8NH [44.70.4.88] all...@NCoast.ORG
Senior Programmer, Telotech, Inc. (if I may call myself that...)
Lance Norskog
A note on the power of C: C doesn't have "code as data" the
way LISP does, but you can write a C interpreter, tack
it in as a library, run yourself under ptrace() and add
breakpoints that jump into the interpreter. This ability
to reify itself via the library interface is very cute,
and demonstrates that the library/pointer stuff is a "closed
set of operators", i.e. you can do anything.
The UPS debugger from U of Kent in the UK has an Ansi C
interpreter built in and lets you tack new C anywhere in
a binary program; it also has a very nice all-X interface.
Very spiffy, but it only runs on SUNs. That's where I got the idea.
Lance Norskog
Phil Howard KA9WGN / I am the NRA
>Of course, any problem you can solve with one turing-complete language
>you can also solve with another. The *important* differences between
>languages are really in the following areas:
>
> 1. expressability -- how easy is it to code the solution?
> object-orientedness (and garbage collection) (and the concept of
> high-level-languages, for that matter) all make solutions easier to
> code.
>
> 2. efficiency -- how fast/small is the code that is generated?
> Note that this is a complex function of compiler and hardware
> technology, as much as it is a function of language design.
>
> 3. saftey -- how hard is it to shoot yourself in the foot?
> Pascal has "high saftey". C has "low safety"
4. compilation efficiency
>This gets back to my "important differences" between languages. In specifying
>a language, you have to pick some balance between expressability, efficiency,
>and safety. For instance, if you add the safety of Pascal's range checking,
>you loose the efficiency avalable without it. If you add the expressability
>of C's & (address-of) operator, you definitely loose safety. Lisp has high
>expressability, reasonable safety, and not too much concern for efficiency.
>But suppose you want an OO language that strikes a similar balance to C?
You could increase safety without the loss of #2 by making the compiler do
a **LOT** more analysis of the source code. Of course this can have a
tremendous cost in #4. I'm sure you are NOT interested in development
cycles like:
do
analyze
write or change code
start compilation
go home
come back next work day
get compiler results
until project done
>I guess the root of our disagreement is your assertion that C is fundamentally
>and irrevokably a mid-level language with no room for higher level concepts.
>Hopefully, I've made the case that this isn't so.
Most certainly so. But my original references you were discounting were
allowing for non-C languages (that might look like C) as higher level
languages building upon things/modules implemented in real C.
To someone that does not (yet) know C++, C++ != C, because such a person
cannot develop an object method in C++.
But you don't HAVE to use an OOL to OOP, it's just more convenient.
Michael D Mellinger
Then people shouldn't use C for their programming. If they want
this kind of functionality, then use ML or Lisp or whatever. If you
need fast code and if you want complete control, use C or other
systems level language. It is, IMHO, and issue of chosing the
right tool for the job.
I haven't read any articles to the effect, but I'm heard from a few
people that having GC is faster than calling malloc and free all of
the time. Does anyone know of any articles that back up this claim?
Does compile-time GC exist in Smalltalk or Self?
-Mike
Scott Draves
Tom> If you need fast code and if you want complete control, use C or
Tom> other systems level language. It is, IMHO, and issue of chosing
Tom> the right tool for the job.
exactly. and C is the wrong tool for building powerful user
interfaces. Obj-C is better, but still a lose compared to, eg, LISP.
Nick Haines
Anything by Andrew Appel on the subject would assert this (see
`Compiling with Continuations' as a book reference (CUP, 1992)). I
don't agree in the instance of Appel's (New Jersey) ML compiler,
because there is a _really_ big locality lose (especially if you use
continuations, which Appel's compiler does all the time), so the cache
performance is abysmal. I think it will be true for a suitable
compiler/GC combination, though. The reason is the copying GC has cost
proportional to the _live_ data, in a generational GC there is very
little repeated copying of live data, and allocation in a good system
is linear and almost free (<=2 instructions for each object you wish
to allocate, which is a _lot_ cheaper than malloc). So if you have
equal cache performance, then you get much cheaper allocation, and no
cost for `free' at all for most objects (most [90%+] objects don't
live long enough to survive the first GC). Can't name a system that
does it really well, though (except the Harlequin ML compiler, due out
this year, plug, plug).
Nick Haines ni...@cs.cmu.edu
Nick Haines
on this group could be construed as flaming the New Jersey ML
compiler. This was not my intention. The NJ/ML compiler is an
excellent system, especially considering that it is free. It raises
all sorts of new ideas (using pure CPS with stackless programming, a
simple GC which is readily extensible, as well as various issues more
directly connected with ML). And it _is_ an example of a system in
which GC is cheaper than malloc/free, and the main proponent of this
view (with which I most whole-heartedly agree) in recent years has
been Andrew Appel.
However, I stand by my assertion that it has bad cache performance,
which I think is brought on by doing _too_much_ heap allocation. I
feel that if it used stacks instead of continuations, and reduced
consing in some simple situations, it would improve locality to the
point where the win of using GC was more obvious.
Nick Haines ni...@cs.cmu.edu
Hans Boehm
Aside from Appel's work based on copying collection, this can be true
even for mark/sweep collection. The PCR collector/allocator is similar
in performance to Sun's malloc/free. It's a faster on a few simple
examples that I've tried, but may be a little slower on others. As usual,
there are good and bad reasons for this:
Bad:
There may be better implementations of malloc/free than Sun's. I haven't
tried to find the best one.
Good:
1. Sweeping an entire page looking for free objects is often cheaper than
calling free on one at a time. Efficient allocators often use a page
for only one size object, with things like size information stored
per page. The collector may only have to look it up once. But
every free call has to look it up.
2. Garbage collectors probably have an easier time discovering that a
whole page full of small objects is empty, and can be recycled for
objects of a different size. There is no convenient time to do
this inside free. And there is evidence that not doing it leads to
fragmentation problems.
3. In a multi-threaded environment, locking can be a major factor in the
cost of allocation. malloc/free has to acquire and release a lock twice,
where malloc/drop acquires it only once.
Of course, a collector has to spend time marking, which free doesn't
have to do.
Here are two other points relevant to this discussion:
1. There are garbage collectors that typically have garbage collection time
under 250 milliseconds. Recent versions of the PCR (Xerox Portable Common
Runtime) collector achieves this with order of 20 MB live data on a
SPARCstation 2. (The 15 MB live data isn't really relevant. Collection
times really depend on something like the number of pages written in the
last 200 msecs. See "Mostly Parallel Garbage Collection" by Boehm, Demers,
and Shenker, in the 1991 SIGPLAN PLDI Proceedings.) An earlier
paper by Appel, Ellis, and Li also reports similar behavior for
a copying collector, using a different scheme. Such collectors are
typically not tremendously portable, because operating systems tend to
not give us the right primitives in a standardized way. With exactly
the right primitives, we could probably get appreciably shorter
collection pauses, still.
2. One reason for supporting garbage collection in C is that ML or
Lisp programs often need to call C code, and vice-versa. This gets
a bit messy if you can't collect C code. Another is that many
implementations of higher-level (than C) languages use C as target
code. I would argue that this is increasingly the right thing to
do, as code generators become more sophisticated, and
depend on more and more timing information
known to the hardware manufacturer and the C compiler writer,
but not necessarily known to the Scheme (or whatever) compiler writer.
Based on the amount of C code that imposes arbitrary static limits
on its input in order to avoid memory management issues, I'm not sure
this is the most convincing reason, but ...
Hans
(bo...@parc.xerox.com)
Tom Emerson
Hans> [Much deleted.]
Hans> 2. One reason for supporting garbage collection in C is that ML or Lisp
Hans> programs often need to call C code, and vice-versa. This gets a bit
Hans> messy if you can't collect C code. Another is that many implementations
Hans> of higher-level (than C) languages use C as target code. I would argue
Hans> that this is increasingly the right thing to do, as code generators
Hans> become more sophisticated, and depend on more and more timing
Hans> information known to the hardware manufacturer and the C compiler
Hans> writer, but not necessarily known to the Scheme (or whatever) compiler
Hans> writer. Based on the amount of C code that imposes arbitrary static
Hans> limits on its input in order to avoid memory management issues, I'm not
Hans> sure this is the most convincing reason, but ...
I have written a fair amount of C code that is used with a large Common LISP
system at our site. If you create and use CL objects in your C routine (AKCL
uses C as its intermediate code, btw) they are liable for GC unless you
declare them on the LISP value stack (which is not gc'd). In this case the GC
is under control of the CL runtime environment, not the C compiler.
My point is this: While GC would be quite useful, I don't know if it should be
"part of the language", rather it is something that should be added if the
programmer wants it, and only if. Would a generic GC work well enough for all
situations (where its use would be appropriate)? Then the question arises
(which I believe has been addressed, I don't remember): how does one determine
when a block is no longer in use and available to be collected? Is there a
deterministic way to do this in C without imposing undue constraints on the
programmer?
mkro...@amherst.edu
Or could someone explain how this thread is so closely related
to programming NeXT's. There is a comp.lang.objective-c group.
(What is really annoying is this system refuses to kill this thread.)
-mike
m...@cs.amherst.edu
Hans Boehm
>My point is this: While GC would be quite useful, I don't know if it should be
>"part of the language", rather it is something that should be added if the
>programmer wants it, and only if.
I agree entirely. If your program needs guaranteed 1 msec response, and is
just barely fast enough on your processor, you don't want a garbage
collector. (In this case, you probably don't want malloc/free either,
but there's certainly room in the middle where malloc/free would have
sufficiently low latency, but collection wouldn't.) Languages like
Modula-3 provide garbage collection, but are also careful to allow
you to write code that doesn't invoke the collector. In such languages,
the distinction is very explicit, in that explicit deallocation (i.e. free)
violates pointer safety. It allows an object to trash data belonging
to a completely unrelated object. This is prevented by the safe
subset of the language, which excludes the equivalent of "free".
C makes no such claims to start with. (I believe Turing uses a technique
that nearly guarantees safety in the presence of "free". But it costs
you something in performance.)
>Would a generic GC work well enough for all
>situations (where its use would be appropriate)? Then the question arises
>(which I believe has been addressed, I don't remember): how does one determine
>when a block is no longer in use and available to be collected? Is there a
>deterministic way to do this in C without imposing undue constraints on the
>programmer?
Conservative collectors simply treat any bit pattern that looks like a
pointer as a pointer. This works well under most conditions. See
"Garbage Collection in an Uncooperative Environment", Boehm & Weiser,
Software Practice & Experience, September 1988. It does impose some
constraints on the programmer. In our experience, these constraints
are satisfied by the average 10,000+ line C program written without
knowledge of the constraints. I believe the constraints could be
reasonably checked by a compiler, but there is currently no compiler
that does so. It also requires that C compilers be "garbage collector
safe". All UNIX workstation C compilers that I know of are safe without -O.
Indeed, they essentially have to be. Almost none are safe with -O, but
I'm not aware of any noncontrived code that exhibits this problem. We
are working on building GC-safe C compilers. Other C-compiler
authors are more than encouraged to join in.
I'm not sure what you mean by "deterministic". No garbage collector
that I know of makes any useful absolute guarantees about space consumption.
Neither does malloc/free. Space consumption will be the same for
identical runs of your program if the environment doesn't introduce
any random values, (e.g. by sending signals to your thread scheduler
at different times, or by not clearing registers on a return from a system
call.)
Hans-J. Boehm
(bo...@parc.xerox.com)
Thomas M. Breuel
> My point is this: While GC would be quite useful, I don't know if it should be
> "part of the language", rather it is something that should be added if the
> programmer wants it, and only if.
If you want a "safe" language with both assignment and dynamic storage
allocation, GC must be part of the language.
Since there are situations (involving real-time programs or
multiprocessing) in which you positively don't want a GC to happen,
what the language should guarantee is that if you only use static and
automatic allocation of objects (no malloc) in some section of code,
no garbage collection will occur in that section of code. That's no
big restriction, since malloc, like GC, makes no guarantees about
real-time performance or locking, and, thus, if you cannot use
anything that might cause a GC to happen, you cannot use malloc
either.
Thomas.
Michael D Mellinger
(Thomas M. Breuel) writes:
If you want a "safe" language with both assignment and dynamic storage
allocation, GC must be part of the language.
Since there are situations (involving real-time programs or
multiprocessing) in which you positively don't want a GC to happen,
what the language should guarantee is that if you only use static and
automatic allocation of objects (no malloc) in some section of code,
no garbage collection will occur in that section of code. That's no
big restriction, since malloc, like GC, makes no guarantees about
real-time performance or locking, and, thus, if you cannot use
anything that might cause a GC to happen, you cannot use malloc
either.
"There are situations..." Who cares. That simply means that 99.9% of
the time it doesn't matter. To the damn "we want a fast language"
freaks: if we assume for the sake of argument that GC is slow, then
for 5% of those applications where [insert fast language] is better
then that doesn't justify not having GC 95% of the time where it would
be beneficial. Having GC improves programmer productivity and helps
ensure correctness, therefore it is good. The NeXT is great because
it makes programming easier, but it isn't the end all be all of
programming. We still have a ways to go, so let's not let the NeXT
stagnate out of ignorance.
Followups to comp.programming.
-Mike
Urs Hoelzle
>Does compile-time GC exist in Smalltalk or Self?
In Self it does exist, but only for blocks (closures). Often the
compiler can delay allocation of a block until it is really needed
(and many blocks such as error blocks are very rarely actually used).
Even better, if all uses of a block are known to the compiler, it can
eliminate it entirely (i.e. no allocation at all).
These optimizations significantly reduce the amount of garbage
produced because blocks are used to implement control structures like
if-the-else and loops. I believe they could be extended profitably to
normal objects, but nobody has actually implemented it and so the jury
is still out on exactly how much this would reduce GC overhead. I am
pretty sure, however, that "garbage prevention" has a higher potential
for savings than trying to improve today's GC algorithms.
-Urs
----------------------------------------------------------------------------
Urs Hoelzle u...@cs.stanford.EDU
Computer Systems Laboratory, CIS 57, Stanford University, Stanford, CA 94305
Triangle man
>Aside from Appel's work based on copying collection, this can be true
>even for mark/sweep collection. The PCR collector/allocator is similar
>in performance to Sun's malloc/free. It's a faster on a few simple
>examples that I've tried, but may be a little slower on others.
Every time I hear anyone complain that "garbage collection is slow",
they're considering only the extra time needed to do the collection.
They don't consider the savings in program complexity that a garbage
collector can give you.
At work, I had the job of rewriting part of a large project to take
advantage of existing object-oriented models. (We use Think C 5.0
on the Macintosh. It's better than nothing.) In the course of doing
my project, I decided I wanted to GC my code, and so I wrote a garbage
collector. It was a simple mark-and-sweep, called by my code whenever
it thought it'd be fortuitous to collect.
"Conventional wisdom" (i.e. the more-senior engineers) freaked,
thinking that my code was wasteful and would be too slow. The original
version was written very low-level, with all memory management being
done explicitly, with no object-oriented dispatch (all messages are in
O(nm), with n being the number of methods per class and m being the
depth of the class hierarchy from where you start) or other "slowdowns".
My code turned out to be *faster* than the original, low-level
implementation, and that was after I added a ton of new features
to it!
This of course went against all that they knew about programming,
and they're still at a loss to explain how that could be.
I know it's because my simplified memory management allowed me to
do things that would take a lot more programming under malloc/free,
and the speed gained from this simplicity far outweighed the time
it takes to GC (averaging 1/30 to 1/20 of a second per GC).
So when you're deciding on a memory management model, consider this
added benefit of GCing, in addition to shortened programming time,
better extendibility, and the lack of memory leaks/dangling pointers.
Has anyone else had similar experience with their code?
--
Steve Boswell
wha...@ucsd.edu
Stephen P Spackman
techniques in a hard-real-time environment anyway. You do your
processor allocation on a compound-deadline basis (i.e., you present a
structured processor schedule at thread creation), and you make this
preallocation cover space bounds as well as time. Then your scheduler
just needs to work backwards from upcoming deadlines to figure out
when a garbage collection needs to be put into unscheduled time in
order to guarantee meeting all future deadlines.
Well, it's worth thinking about.
----------------------------------------------------------------------
stephen p spackman Center for Information and Language Studies
ste...@estragon.uchicago.edu University of Chicago
----------------------------------------------------------------------