NetNews Usenet Archive 1992 #31/NN_1992_31.iso/spool/comp/lang/cplus/18570

Text File | 1992-12-30 | 2.5 KB | 51 lines

Newsgroups: comp.lang.c++
Path: sparky!uunet!microsoft!hexnut!jimad
From: [e-mail] (Jim Adcock)
Subject: Re: Special-purpose-heap-managers - references, FTP?
Message-ID: <[e-mail]>
Date: 30 Dec 92 21:25:05 GMT
Organization: Microsoft Corporation
References: <[e-mail]>
Lines: 40

In article <[e-mail]> [e-mail] (Dave Detlefs) writes:
|I regard the proposition that special-purpose heap managers are "much
|faster" than *all* general purpose ones as quite unproven.

The counter-proposition also remains "unproven."

| It is
|certainly true that there exist bad general purpose allocators, and
|that special purpose allocators are much faster than these.  But this
|does not imply that there can't be a really good general-purpose
|allocator whose performance approaches the performance of writing a
|special-purpose allocator for each class in your program.  In fact, I
|believe that some variation on the Quickfit algorithm [1] fits the
|bill.  If you want to look at some very interesting empirical studies
|of allocator performance, I strongly recommend some papers by Ben Zorn
|and Dirk Grunwald at the University of Colorado [2], [3].

I agree that Quickfit is a good algorithm that people should seriously
examine for their object allocation needs if they haven't already done so.
Mallocs are typically designed to handle larger-sized allocations than
single-object, so mallocs are typically pretty poor choices for such needs.
Converesly Quickfit doesn't help with large allocations.  Looking at
the inline code the authors generate for quickfit allocations makes
it clear that fix-sized class-based allocations should be possible
about twice as fast with about half as much generated code, so class-
based allocators will remain popular for people trying to get very
fast allocations.  Also, quickfit works pretty well for objects
when temporal locality remains fixed [ie objects that are allocated
together continue to be used together, and objects that weren't allocated
together continue not to be used together].  Works terrible in situations
where this is not true.  For example, in OODBMSs queries pull
together objects into new working sets.  Objects needed together in this
query may never had a relationship to each other in the past.  Quickfit
does poorly in such a system since its assumptions that temporal locality
~= spatial locality are violated.  Such systems need moveable objects
and allocation systems supporting moveable objects instead.