From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.3 required=5.0 tests=BAYES_00,INVALID_MSGID autolearn=no autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,3498dd887729ed19 X-Google-Attributes: gid103376,public From: dewar@merv.cs.nyu.edu (Robert Dewar) Subject: Re: Garbage Collection in Ada Date: 1996/10/17 Message-ID: #1/1 X-Deja-AN: 190114165 references: <01bbb910$f1e73f60$829d6482@joy.ericsson.se> <199610132138291604607@dialup101-6-14.swipnet.se> <19961014115513529729@dialup105-2-16.swipnet.se> <32652A7C.41C6@mti.sgi.com> <3265C383.167E@mti.sgi.com> organization: New York University newsgroups: comp.lang.ada Date: 1996-10-17T00:00:00+00:00 List-Id: HJB says "N log K, where N is the size of live data and K is the size ratio between largest and smallest bound is the best worst-case bound acheivable by a general purpose nonmoving allocator. This is an old result due to Robson, cited in Knuth (I don't have the reference handy). This means a binary buddy system without coalescing is asymptotically optimal for the worst case. It does poorly if your program allocates 1MB of 5 byte objects, deallocates them, then allocates 1MB of 9 byte objects, deallocates them, allocates 17 byte objects, etc. (It's also less space efficient in the typical case tah other algorithms with worse worst-case behavior.)" When I say binary storage allocator, I am referring to the Knowlton paper (note that Knuth did not invent the algorith, just the term buddy system, and Knuth is concerned to give the right credit as always!) The essence of the binary storage allocator is that it DOES coalesce on return, and that for a given maximum block size, the time to coalesce is bounded by a constant, as is the time to allocate. And in such a system it is obvious that you cannot be worse than a factor of 2 inefficient in use of storage (the worst case occcurs if all your allocations are for one size of block, that is a power of 2 plus one in size).