Why collected languages don't need a free operation 
Author Message
 Why collected languages don't need a free operation

It has been suggested that garbage collected languages
would benefit in efficiency from the addition of a
'free' construct. I distribute a conservative collector
for C & C++ in a variety of environments and do not
think this is the case.

Usually adding our collector is either efficiency neutral,
changing efficiency by too small an amount to matter or
it provides an efficiency improvement often a radical one.
On occasions we have a radical efficiency loss but when
this happens I find we can tune the application to where
the addition of the collector is either efficiency neutral
or an improvement.

The key understanding is that paging is more expensive
than logic and you can use a lot of logic to prevent a
paging operation and come out far ahead. A collector
improves efficiency by striking amounts when it kills
storage leaks and reduces paging.

Where the collector is expensive we fix things by three
tactics. In order of importance.

1. Identify leaf objects for the collector. A leaf object
is an object which cannot contain pointers. These take zero
time to scan. Often large applications which take lots of
time to collect are 99% leaf objects such as bit maps or
arrays of double precision numbers. Identifying these is
simple and speeds collection by 100 to 1. In languages with
garbage collection this is done naturally.

2. Trade space for speed. If the collector starts off with
1 Meg, fills it collects down to 1/4 Meg when it runs out
of that Meg it will collect again. This may result in an
unreasonable number of collection cycles. Starting with
10 Meg will divide that by 10.

3. Replace free(p) with p = 0; where appropriate. Here is
why this works. To improve efficiency you want to reduce
paging at the expense of logic. If any object is likely
to be paged out it is one the user thinks [S]he can free.
But freeing that object touches it and may produce a page
or a ripple of them. In killing frees we often simplify
the application by removing the code that supported them.

If a collected language has a free construct is will
encourage code like
  if (x->expireDate < today)
     free (x);
Even if free is a nop, x->expireDate touches *x. In
performance terms this is a guaranteed mistake. Let dead
objects rot, don't page them in. The collector is carefully
organized so that free bits etc are kept on separate pages
so the free(x) is likely to be harmless though silly. The
code to support it is not.

If the language has finalizers there must be syntax to
execute them directly and there must be a simantec
definition for post finalized objects. I think the C++
zeroing the vtable entry is very wrong. I propose treating
finalizers as no different from other functions.

After the collection cycle the collector should do a
topological sort of finalizer objects, cycles should
be ignored or warnings printed as a debug option. Users
can reconcile these states themselves by setting flags
in finalizers.

                        -  
Charles Fiterman                Geodesic Systems
414 North Orleans Suite 410     Phone 312 832 1221 x223
Chicago IL 60610-4418           FAX   312 832 1230
                                http://www.*-*-*.com/

A young man saw a product advertised in a magazine that said
"Guaranteed 100% effective against bugs when properly used."
He sent away and got two blocks of wood with the instructions
"Place bug on block A, strike sharply with block B." De{*filter*}s
are like that, and you can get stung while using them. Great
Circle tries to be something better than that.



Mon, 20 Dec 1999 03:00:00 GMT  
 Why collected languages don't need a free operation



Quote:
>3. Replace free(p) with p = 0; where appropriate. Here is
>why this works. To improve efficiency you want to reduce
>paging at the expense of logic. If any object is likely
>to be paged out it is one the user thinks [S]he can free.
>But freeing that object touches it and may produce a page
>or a ripple of them.

Why does free(p) need to touch *p?  It should just update the heap memory
management information that refers to p.  Of course, if your heap is
designed such that the allocation size of *p is stored in the word before p
then you're right, but if you're designing a system to reduce paging you
wouldn't do that.  And if *p has destructors you'll need to run them
eventually.

And if the system has a good GC, free(p) could just be a no-op.

--

BBN Corporation, Cambridge, MA
Support the anti-spam movement; see <http://www.cauce.org/>



Tue, 21 Dec 1999 03:00:00 GMT  
 Why collected languages don't need a free operation


  [snip]
  >
  >And if the system has a good GC, free(p) could just be a no-op.

I don't know if you'd consider DEC SRC's Modula-3's GC a "good" one,
but the language does provide for "DISPOSE" for untraced references.
Thus, you can mostly write in gc'd environments but for realtime and
other tight situations, you can explicitly control memory management.
Doing so requires you to explicitly declare the module "UNSAFE",
of course.
--
---------------------------------------------------------
Disclaimer:  IMPORT StandardDisclaimer;
Contact:     Harry George    M-S: 6-6M31
Organization:6-6M31, BCAG Knowledge Based Engineering  
Phone:       (206) 237-6915



Fri, 24 Dec 1999 03:00:00 GMT  
 
 [ 3 post ] 

 Relevant Pages 

1. Why patterns don't suck

2. why awk don't display the results?

3. Why I don't Like HTML Help...

4. Animated Gifs Some work some don't why

5. Why don't Memo Entry Fields wrap?????

6. I don't understand why my haskell program works

7. Why I don't use Dylan

8. Why don't large companies use Ada?

9. Why don't my textures map correctly?

10. Why don't Paragraph reply?

11. why don't crash?

 

 
Powered by phpBB® Forum Software