Re: Variable-block memory managers bad in realtime

[gwinn@res.ray.com (Joe Gwinn)]

This is a re-posting.  Robert Dewar reports that although he got the email
of the original posting, he never saw it on the newsgroup.  I can see it,
but who knows what happened and who got it?  So, it's safest to repost.  I
have added some clarifying text from the side discussion between Robert
and myself.

Date: Fri, 19 Dec 1997 14:30:51 -0500
From: gwinn@ED.RAY.COM (Joe Gwinn)
To: dewar@merv.cs.nyu.edu (Robert Dewar)
Subject: Re: Variable-block memory managers bad in realtime
Newsgroups: comp.lang.ada

(A copy of this message has also been posted to the following newsgroups:
comp.lang.ada)

> From: dewar@merv.cs.nyu.edu (Robert Dewar)
> Newsgroups: comp.lang.ada
> Date: 14 Dec 1997 09:08:07 -0500
> 
> <<The historical problem with such algorithms, many of which are quite good,
> is that they aren't *perfect*, and there is always a spectrum of
> allocations and deallocations that will cause failure, because their
> design depends on statistical regularities of one kind or another.
> 
> Another reason we have always avoided such algorithms is that they were
> too complex for us to prove that they would *never* jam, even after months
> of continuous heavy field use without a system reset.  Even the slightest
> memory leakage or fragmentation will accumulate and become a problem under
> such a scenario.>> -- from Joe Gwinn
> 
> 
> This is plain false. There are well known algorithms that work just fine,
> and do not depend on statistical regularity. Basically the tradeoff is
> that if you want guaranteed constant time allocation, you have to be willing
> to waste some fixed proportion of memory in the worst case.

Waste lots of memory, actually.  Sometimes we don't have the memory to
waste, or we would rather waste it on something else.  I don't know that
these algorithms have guaranteed absolute upper bounds on response time,
and absolute protection against fragmentation, together with the requisite
efficiency.  

Fixed-block allocators waste no space, and have absolutely constant
service time.

 
> As or proving such algorithms correct, again you need to go to the literature.

Strikeout!  The literature on memory management algorithms is huge.  I've
yet to see a fully suitable variable-block algorithm.  It appears that you
have dug much deeper into the literature than I have.  Perhaps you can
point me to a suitable article or two?  

 
> This is precisely the kind of area where you don't need "domain experts".
> You need people who are aware of the standard work in analysis of algorithms,
> for which there is a large established literature. 

See above.  The vast bulk of that large established literature solves
problems we don't have in realtime, at the expense of problems we do
have.  Perhaps you have been so fortunate as to find one of the few truly
relevant articles.  I haven't.  If so, a pointer or two would be greatly
appreciated.  I doubt that I will ever have the time to read a significant
fraction of that literature.


> No doubt you will complain that you don't want or need "experts in memory
> allocation", but as your note makes clear you certainly COULD benefit from
> having people in your project who know this kind of material. Once again,
> this is not the sort of thing you can pick up from newsgroup FAQ's. The
> literature on memory allocation is comprehensive, and accessible to someone
> with basic knowledge of the area, but it is not so accessible if you don't
> have the general background. 

There are plenty of people here who can read the literature.  The question
is time and interest and reason, especially if they have an adequate,
proven solution in hand.  It's rare to risk a new and untried algorithm in
something so fundamental, unless the current algorithms are clearly
inadequate.  

We are a development lab, not a research university.  The objectives and
tradeoffs are quite different.  There is no endowed chair in anything so
specific as memory allocation; we are all of necessity generalists.  We
draw on the university experts if we can, but are not ourselves
university-level experts in such things, and never will be.

Actually, newsgroups and FAQs are a rich source of specific pointers.  The
more people combing the literature, the higher the chance someone
somewhere will strike paydirt.  Also, the more practical information there
is on what part of the theory really works in industrial applications, or
why this or that theory fails in practice, the better.

 
> If I gave my graduate students in CS the task of looking up a memory
> allocation algorithm that had "perfect" characterstics as far as constant
> time (i.e. O(1)) allocation, I would expect them to be able to track it
> down. On the other hand, if I asked them to track down papers in high
> energy physics or quantum chemistry, I would not expect them to have the
> background.

We are not students, we are practitioners, and have limited time and
interest in research, and even less interest in reinventing the wheel.

Is that "O(1)" the average behaviour, or the upper bound?   We need an
algorithm that is mathematically proven to be fixed-time, regardless of
just about everything, and the proof has to be simple enough that we (and
our customers) can understand it without having to take an added graduate
degree, which would take longer than it takes us to build the typical
system.

 
> So this is another opportunity to emphasize that these days, we recognize
> that programming is a complex task, but that there are many tools available
> to help, some of them quite complex, and requiring a significant level of
> training and understanding. The best programming efforts are where domain
> experts work with experts in the technology in a cooperative manner to
> make sure that the best technology is used to incorporate the most accurate
> model of the domain, reaching for the best knowledge available in both areas.

It would be nice, yes...  Sounds like the Courant Institute.  I don't
think they build embedded realtime systems under contract, though.

 
> If you look at what is happening in scientific programming these days, you
> see an interesting trend. The typical quantum chemistry or crystallography
> programs of the 60's (my thesis is in the xtalography area), did not require
> complex algorithms from a CS point of view, and the work was done by chemists
> who had picked up some general Fortran programming knowledge.
> 
> But even back then, the result was very effective programming of silly
> algorithms in some cases. I improved one data gathering program by replacing
> a bubble sort with treesort3 (people know it as heapsort today), and then
> further improved it by devising a modification of treesort3 that halved the
> number of compares from 2logN to logN [already I was becoming more of a
> computer scientist than a chemist (*)]

I have like war stories.  My favorite, from fortran on Univac 1108s in the
1970s, involved a young radio propagation engineer who recomputed
everything at every turn, because he didn't know what a disk was.  The CPU
and elapsed time went from days to minutes after he discovered disks.  

These stories prove that not all programmers (engineers, cobblers,
tailors, ...) are equally adept, and that domain experts may not be
computer experts, and vice versa.  But, we knew that.

 
> These days, scientific programs tend to use highly complex algorithms, and
> numerical computing is an avid consumer of some of the most advanced work
> in algorithmic design and analysis. At the Courant Institute, computer
> scientist, numerical analysis, and other scientific experts work together
> to solve problems in such areas as secondary oil recovery, design of
airframes,
> and design of fusion reactors.

Well, we are trying to solve much different problems.  We are trying to do
by comparison simple things, but do them at 64 Hz, controlling hardware
and *never* overrunning.  I doubt that those scientific programmers would
learn much useful from our projects, and vice versa.


> (*) This optimziation has never been properly published, although full details
> are in my thesis. The idea appeared as an excercise in Volume III of Knuth,
> though Knuth's answer was in fact wrong in an important detail (one of the
> several nice Wells Fargo checks for $1 that I got from this volume was for
> finding this bug :-)

Congratulations.  It isn't just a dollar -- it comes complete with
bragging rights.  

So, it's Knuth with bugfix?  I assume that the second edition has the
problem fixed.  Which problem was it?

 
> If you are interested in learning more about that optimization, or using
> it, you have easy access to the necessary information. Just look at the
> extensively commented body of GNAT.Heap_Sort_A or GNAT.Heap_Sort_G in
> files g-hesora.adb and g-hesorg.adb. In general spend some time wandering
> through the GNAT.xxx hierarchy of useful stuff if you are a GNAT user, you
> will find it worth while :-)

Actually, it sounds like I should instead read the relevant parts of your
thesis.  This way I get peer-reviewed rationale, not just the code.  What
are the title, date and school?  I'm pretty sure the crystallography won't
do permanent damage.  <Got the ref; thanks.>


One thing that occurred to me after the original posting was that in one
sense we had drifted off the original point, which was the use of malloc
in Ada RTEs.  Note that some Ada RTEs are using malloc to acquire memory
for such things as saving exception contexts, so the user has no control
over this.  Even if your algorithm is perfect in every way, it isn't what
people are using (like it or not), and I liked your suggestion to Tucker
Taft that there should be hooks allowing one to substitute one's own
memory manager for malloc or whatever the Ada RTE is using.  This solves
in a stroke the problem of finding the perfect memory manager by allowing
use of domain expertise to choose.


>Note that an allocator that allocates only fixed length blocks may be
>*VERY* wasteful if your application really requires variable length
>blocks.  <From a side discussion>

True, but our applications are happy with from three to six different
block sizes; the specific spectrum of sizes varies with the specific
application.  Remember, I don't have to solve as general a problem as does
a compiler or runtime writer, and I am more interested in predictability
and behaviour under overload and near overload than memory efficiency per
se.  Nor do I agree that there is one "best" algorithm, for all
applications.



Joe Gwinn