memory allocation

[Richard Harter]

In article <784 at proxftl.UUCP> bill at proxftl.UUCP (T. William Wells) writes:

	re space for allocator programs

]Well, mine did have that kind of code; it also had grunge for
]handling buffer pools and a few hacks to make it fit with the
]rest of the kernel.  Anyway, 200 lines of C code, translated into
]assembler, would have been a lot of code compared to any of the
]other parts of the kernel.

	Good point.  My concern has been with allocators for large
systems rather than for kernels.  I don't begrudge the time or code
spent on making an allocator hot; in many applications allocators get
a heavy workout and the payback for improving them is large.  A slow
allocator can make you look very bad.


]There are also a few minor points favoring the buddy system; one
]is that it can do a much better job of reducing fragmentation
](though you milage almost certainly will vary :-) Another is
]that, if you know that you have a buddy system allocator, you can
]sometimes choose which structures things go in so that the
]structure sizes are the appropriate ones for your allocator.

	Actually it buries the fragmentation in the oversize
allocation.  If block sizes are random the buddy system has a 67%
storage usage efficiency.  Exact fit allocators can get upwards of
90% if request sizes are not too small (and small request size are
best handled separately.)  Efficiencies depend on the ratio of mean
requested size to maximum space available, the request size distribution,
and the request/free pattern characteristics.

	I can't say I'm much enthused about the notion of bending the
code structure to fit the allocator characteristics.

]Another point, which I haven't given much though to, but I though
]I'd toss out to see what people think, is that a buddy system
]allocator can go very well with a paged memory system; wasted
]space at the end of small blocks is irrelevant and wasted space
]at the end of large blocks wastes address space but does not
]waste much working set memory.

	Now this is a very interesting point, and one which I hadn't
thought about.  There is a clear profit to be gained in taking page
sizes into account -- page faults are a lovely way to take a performance
hit.  In a best fit (or EF+WF) allocator one should have criteria for
not straddling page boundaries.  I'm going to have think about that one.

]: One point which I feel strongly about is that most allocators use the
]: blocks (free and allocated) to hold control information.  I think that
]: this is a mistake.  I put all control information in structures in a
]: separate node space.  This adds overhead, but it makes life a lot safer.
]: Array indexing errors do not damage the allocator.  Free's can be checked
]: for validity.

]Depends on what you want.  If you want a bulletproof system, then
]you should definitely segregate the control information.  If you
]want a high-performance system, then you have to put the control
]information in an unsafe place.  That's life.

But note that the performance hit is on storage use and not on time.
Moreover the hit is not all that great unless there are a lot of short
requests.  I am a fan of bulletproof code.  However different situations
make for different requirements.


-- 

In the fields of Hell where the grass grows high
Are the graves of dreams allowed to die.
	Richard Harter, SMDS  Inc.