[gclist] Allocator algorithms.

[David Chase]

> Has anyone out there ever got around to writing a pessimal allocator?
> That is, a program which hits the worst case of whichever memory
> manager it's plugged into. It would seem to be a fairly
> straightforward programming exercise, in non-conforming C. Maybe some
> academic on the list could get a student to do one....

I'm not certain what it is you're asking for here.  Couldn't you 
get decently far with conforming C?  It would be an entertaining
exercise to merely write a suite of programs, rather than a single
one that was bad for all allocators.

More entertaining yet would be a program that "learned" bad behavior. 
Give it the task of allocating a megabyte of memory, any way it wants 
to, and report its score back to it when it is done, and let it use 
the results from previous runs to pessimize its future behavior.  

It also makes sense to consider VM behavior in this exercise -- the 
worst allocator I've ever seen, was terrible because of its VM behavior.
Every allocation (or maybe every Nth allocation, for small N) walked
over the entire address space.  It was appalling.  It was vastly 
slower than any garbage collector I've ever used or heard of.

David Chase