Dynamic Storage Allocator Pros and Cons

[Richard Harter]

In article <1990Nov25.162505.3445 at diku.dk>, njk at diku.dk (Niels J|rgen Kruse) writes:
njk rh at smds.UUCP (Richard Harter) writes:

njk rh >(A)    All invalid size requests (zero, negative, too large) are trapped.
njk njk>--------------------------------------------------^^^^^^^^^
njk njk> Try ``getsp (2147483646,0)''.   ;-)
njk rh >       ??? What machine is this on?  It worked fine on the
njk rh >       a couple of tests.

njk Sorry, i should have given more details.  It was a Vax-11/785
njk running MORE/Bsd 4.3, compiling with cc -g.  You must have used
njk a machine that zero-fill on signed right shift...

	Detailed debug printout deleted.  The essence of the
	matter is that the request size is 2**31-2.  The code
	checks for <=0 first, then adds 4, and then shifts 
	right 3.  With the requested size there is overflow.
	With 1-fill the size remains negative.  Nailed me to
	the wall, he did.

njk Authors of dynamic storage allocators almost never check for
njk overflow, when rounding up requests.  This is the first thing i
njk look for, when i come across a new one.

I can't imagine why. :-)  Given that the allocator argument is integer
the best fix is probably to check size for negative a second time
after the round up.  [There are sundry theological reasons why I
think that the argument should be signed which we needn't go into.]

njk rh >       Both advantages are much less when the request sizes
njk rh >       are "large". [re lifo vs best-fit]

njk This depends very much on the shape of the request size
njk distribution.  Consider what happens when you have request
njk sizes, that are very large and very rare.  With LIFO, the
njk largest free blocks tend to get nibbled at by smaller
njk requests, so when the very large request finally comes
njk along, no block is large enough and you have to grow the
njk heap.  Best Fit on the other hand, tend to preserve the
njk largest free blocks.

Can't argue with you there.  This was an engineering trade-off
decision on my part.  It didn't seem worth it to me at the time
I wrote the package to strive for that last bit of space efficiency.
For that matter I wan't overwhelmingly concerned with space
efficiency per se -- witness the decision to go with separate
nodes.  I wanted time efficiency (I tend to make heavy use of
allocation) with good error checking.

I tend to be of the school that believes that fixed table sizes
are a sin against nature and an abomination unto the Lord.  I am
offended when I get messages like "arg list too long".  Call me
a crufty bigoted old curmudgeon, if you like, but that's my view.

But if you do take that view you end doing a lot of allocation
and deallocation which, unfortunately, is a veritable hotbed
of mystery bugs.  Whence my predilection for error checking.
What I need is an OS with the commands

	fix$typos
	fix$syntax
	fix$logic

Ah well, they tell me that VMS is the OS for people who are
doing real production software.  Maybe I can find them there. :-)
-- 
Richard Harter, Software Maintenance and Development Systems, Inc.
Net address: jjmhome!smds!rh Phone: 508-369-7398 
US Mail: SMDS Inc., PO Box 555, Concord MA 01742
This sentence no verb.  This sentence short.  This signature done.