(The article by muzok hasn't reached to our site yet.)
In article <··········@Cadence.COM> Simon Kinahan <simonk> writes:
simonk> ·····@msn.com (muzo) wrote:
>> 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.
simonk> I can't give you a reference, but I promise you it is true. Firstly you need
simonk> to understand that in a garbage collected langauge you do not normally
simonk> make free calls.
[omitted by mad]
simonk> As I understand it the proof that GC is less expensive than malloc/free
simonk> is based on the copying style of garbage collector, used in may
simonk> newer compilers. The simplest form of copying GC keeps two blocks
simonk> of memory, both large enough to hold all active objects, and simply
simonk> copies all active objects from their current locatrions to locations in the
simonk> other block every so oftwen, marking the old block as free. This both
simonk> compacts the memory abnd 'implicitly' collects the garbage.
Yes, my statement about gc cost was written copying GC in mind. As
Simon Kinahan explained, such a collector doesn't really "collect" or
free garbages explicitly. But "proof" is too strong a word. I doubt
such a formal proof exists. Most gc papers I read just evaluated
algorithms with a few small benchmarks. Some did mathematical
analysis (e.g. Hickey and Cohen) but based on very simplified
assumption (constant number of live objects, constant pace of cell
creation/consumption etc.). They are valuable but can't be claimed as
"proof".
When I wrote my previous article, I also believed the two major
benefits (compaction and asymptotic complexity) of copying collector.
But see Boehm's web page (ftp://parcftp.xerox.com/pub/gc/complexity.html).
>> 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.
Now it turned out that we were both wrong w.r.t. relationship between
number of calls to free() and total memory management cost. So I
don't argue along this line anymore.
But just one comment; even perfect programmer must sometimes do gc
(or something similar). When handling graph structured data you can't
free object so easily. If you have an experience with GUI libraries
such as InterViews, then you can see what I mean. You need something
like garbage collection. For example, InterViews used reference
counting scheme on top of C++ builtin new/delete.
;;; Keio University
;;; Faculty of Science and Technology
;;; Department of Math
;;; MAEDA Atusi (In Japan we write our family names first.)
;;; ···@math.keio.ac.jp