From: dewar@merv.cs.nyu.edu (Robert Dewar)
Subject: Re: Garbage Collection in Ada
Date: 1996/10/17
Date: 1996-10-17T00:00:00+00:00 [thread overview]
Message-ID: <dewar.845607377@merv> (raw)
In-Reply-To: 3266C15E.2781@mti.sgi.com
"I believe the version with full coalescing has worst-case allocation
time log N, where N is the heap size. Consider a heap with only one
large empty block and repeated requests to alternately allocate and
deallocate a 1 byte block. (I'm referring to the algorithm in Knuth,
vol. 1, 2nd edition, starting at page 442. Knuth credits it to
Markowitz and Knowlton.)"
Yes, sure, if the largest block size is the size of the heap, but this is
not the normal scenario for the binary storage allocator. But yes, you are
quite right about the fragmentation, I was thinking of something else when
I answered, and yes, indeed the fragmentation can be much worse than a
factor of 2. Indeed the only way to avoid fragmentation that is pretty
much arbitrarily bad is to implement a proper compacting garbage collector.
My feeling is that if you are going to go beyond the simple conservative
allocators, you really want to go all the way to a fully compacting
collector. This is more practical with Ada than with C++.
next prev parent reply other threads:[~1996-10-17 0:00 UTC|newest]
Thread overview: 126+ messages / expand[flat|nested] mbox.gz Atom feed top
1996-10-13 0:00 Garbage Collection in Ada Jonas Nygren
1996-10-13 0:00 ` Robert Dewar
1996-10-13 0:00 ` Lars Farm
1996-10-13 0:00 ` Larry Kilgallen
1996-10-13 0:00 ` Robert Dewar
[not found] ` <19961014115513529729@dialup105-2-16.swipnet.se>
1996-10-16 0:00 ` Robert Dewar
1996-10-16 0:00 ` Lars Farm
1996-10-16 0:00 ` Robert Dewar
1996-10-16 0:00 ` Hans-Juergen Boehm
1996-10-17 0:00 ` Robert A Duff
1996-10-17 0:00 ` Hans-Juergen Boehm
1996-10-17 0:00 ` Larry Kilgallen
1996-10-17 0:00 ` Robert Dewar
1996-10-17 0:00 ` Hans-Juergen Boehm
1996-10-17 0:00 ` Lars Farm
1996-10-23 0:00 ` Robert Dewar
1996-10-16 0:00 ` Hans-Juergen Boehm
1996-10-16 0:00 ` Robert Dewar
1996-10-16 0:00 ` Hans-Juergen Boehm
1996-10-17 0:00 ` Robert Dewar
1996-10-17 0:00 ` Hans-Juergen Boehm
1996-10-17 0:00 ` Robert Dewar [this message]
1996-10-14 0:00 ` Robert A Duff
1996-10-14 0:00 ` Lars Farm
1996-10-15 0:00 ` Robert A Duff
1996-10-16 0:00 ` Lars Farm
1996-10-16 0:00 ` Robert Dewar
1996-10-17 0:00 ` Robert A Duff
1996-10-19 0:00 ` Robert Dewar
1996-10-19 0:00 ` Lars Farm
1996-10-20 0:00 ` Robert Dewar
1996-10-20 0:00 ` Robert A Duff
1996-10-20 0:00 ` Robert Dewar
1996-10-21 0:00 ` Geert Bosch
1996-10-21 0:00 ` Hans-Juergen Boehm
1996-10-21 0:00 ` Lars Farm
1996-10-21 0:00 ` Robert Dewar
1996-10-21 0:00 ` Lars Farm
1996-10-23 0:00 ` Fergus Henderson
1996-10-24 0:00 ` Richard A. O'Keefe
1996-10-20 0:00 ` Robert A Duff
1996-10-20 0:00 ` Robert Dewar
1996-10-21 0:00 ` Hans-Juergen Boehm
1996-10-21 0:00 ` Robert Dewar
1996-10-19 0:00 ` Richard Kenner
1996-10-15 0:00 ` Hans-Juergen Boehm
1996-10-14 0:00 ` John Howard
1996-10-15 0:00 ` Lars Farm
1996-10-15 0:00 ` Robert A Duff
1996-10-15 0:00 ` Robert Dewar
1996-10-15 0:00 ` Hans-Juergen Boehm
1996-10-15 0:00 ` Lars Farm
1996-10-17 0:00 ` Thomas Kendelbacher
1996-10-17 0:00 ` Robert Dewar
1996-10-23 0:00 ` Richard A. O'Keefe
1996-10-23 0:00 ` Larry Kilgallen
1996-10-15 0:00 ` Keith Thompson
1996-10-14 0:00 ` Jon S Anthony
1996-10-15 0:00 ` Robert Dewar
1996-10-15 0:00 ` Robert I. Eachus
1996-10-15 0:00 ` Robert Dewar
1996-10-16 0:00 ` whiting_ms@corning.com (Matt Whiting)
1996-10-16 0:00 ` Robert Dewar
1996-10-17 0:00 ` John Howard
1996-10-17 0:00 ` Robert Dewar
1996-10-18 0:00 ` Lars Farm
1996-10-19 0:00 ` Robert Dewar
1996-10-20 0:00 ` Lars Farm
1996-10-21 0:00 ` Robert Dewar
1996-10-22 0:00 ` Lars Farm
1996-10-21 0:00 ` Nicolay Belofastow
1996-10-21 0:00 ` Robert Dewar
1996-10-20 0:00 ` Robert A Duff
1996-10-20 0:00 ` Robert Dewar
1996-10-22 0:00 ` Mitch Gart
1996-10-23 0:00 ` Hans-Juergen Boehm
1996-10-27 0:00 ` Richard Riehle
1996-10-23 0:00 ` Fergus Henderson
1996-10-29 0:00 ` Jon S Anthony
1996-10-30 0:00 ` James Rogers
1996-10-30 0:00 ` Jon S Anthony
1996-10-30 0:00 ` Brian Rogoff
1996-10-30 0:00 ` Jonas Nygren
1996-10-18 0:00 ` Lars Farm
1996-10-20 0:00 ` Robert A Duff
1996-10-18 0:00 ` Hans-Juergen Boehm
1996-10-15 0:00 ` Hannes Haug
1996-10-16 0:00 ` Jon S Anthony
1996-10-17 0:00 ` Robert Dewar
1996-10-16 0:00 ` Jon S Anthony
1996-10-16 0:00 ` Ole-Hjalmar Kristensen FOU.TD/DELAB
1996-10-16 0:00 ` Robert Dewar
1996-10-16 0:00 ` Jon S Anthony
1996-10-16 0:00 ` Jon S Anthony
1996-10-17 0:00 ` Robert I. Eachus
1996-10-17 0:00 ` Robert Dewar
1996-10-17 0:00 ` Richard Kenner
1996-10-17 0:00 ` Hans-Juergen Boehm
1996-10-17 0:00 ` Rick Hudson
1996-10-18 0:00 ` Rick Hudson
1996-10-18 0:00 ` Jon S Anthony
1996-10-18 0:00 ` Robert Dewar
1996-10-18 0:00 ` Jon S Anthony
1996-10-23 0:00 ` Robert Dewar
1996-10-21 0:00 ` Laurent Pautet
1996-10-21 0:00 ` Jon S Anthony
1996-10-22 0:00 ` Jon S Anthony
1996-10-22 0:00 ` Tapani Rundgren
1996-10-23 0:00 ` Jon S Anthony
1996-10-24 0:00 ` Mitch Gart
1996-10-24 0:00 ` Hans-Juergen Boehm
1996-10-24 0:00 ` Robert I. Eachus
1996-10-25 0:00 ` Jon S Anthony
1996-10-28 0:00 ` Robert I. Eachus
1996-10-29 0:00 ` Hans-Juergen Boehm
[not found] <01bbc6a3$4cf03480$829d6482@joy.ericsson.se>
1996-10-31 0:00 ` Mitch Gart
1996-10-31 0:00 ` Jonas Nygren
1996-11-03 0:00 ` Matthew Heaney
1996-11-06 0:00 ` Robert A Duff
1996-11-06 0:00 ` Norman H. Cohen
1996-11-01 0:00 ` Jon S Anthony
1996-11-06 0:00 ` Brian Rogoff
1996-11-07 0:00 ` Tucker Taft
-- strict thread matches above, loose matches on Subject: below --
1996-11-02 0:00 Jon S Anthony
1996-10-22 0:00 Brian Rogoff
1996-10-11 0:00 C++ Standardization (was: Once again, Ada absent from DoD SBIR solicitation) Dave Wood
1996-10-17 0:00 ` Garbage Collection in Ada Thomas Kendelbacher
replies disabled
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox