[gclist] Allocator algorithms.

[Nick Barnes]

> > 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.

What I was meaning was a tool which deliberately created holes smaller
than its future allocations, forcing fragmentation. To do this you
have to be able to examine addresses (to know which objects to free),
which is where the non-conformancy comes in. The neat thing about it
is that it automatically adapts to the memory manager's algorithm.

> 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.

There's a product called something like SmartHeap, which sells on the
basis of avoiding this behaviour. Apparently the default memory
manager for some version of some PC C compiler had really lousy VM
behaviour.

Nick Barnes