Re: Question about Lua 5.1.3 and realloc() on life.lua

[Mike Pall <mikelu-0805@...>]

Ralph Hempel wrote:
> I've written a stripped down best-fit malloc [...]

Bogdan Marinescu wrote:
> My allocator does best fit too [...]

Umm, reinventing the wheel? And why do so without studying the
literature? There's plenty out there and it will tell you that
best-fit is rarely a good choice. While it has the least amount of
internal fragmentation it causes the highest amount of external
fragmentation and has unacceptable worst-case behaviour.

I realize the complexity of a mature general-purpose allocator can
be daunting. But a good deal of it is due to multi-threading
issues and handling the various ways to get memory blocks from the
OS. And since the allocator must be general-purpose it needs a lot
of code to avoid some pathological cases. You won't need most of
this for Lua.

I think the easiest way is to start with something like dlmalloc
and strip it down. Try to throw out only the things you obviously
don't need (e.g. per-thread allocation), but don't strip more
stuff unless it still doesn't meet your code-size goal.

But if you really, really want to write your own allocator for
Lua, here are my suggestions: use quick-fit with a relatively
coarse quantization (*) and tune the fixed bin sizes to the
observed allocations. Use lazy coalescing for the fixed bin sizes
and immediate coalescing for the medium sizes. Round up large
sizes to pages and let the OS manage them. Block splitting should
look for size 2n+k at least.

When you're finished, be sure to compare the size of your code to
a stripped down dlmalloc. ;-)

(*) Make bins a multiple of 16, 32 or even 64 bytes. The higher
internal fragmentation helps to reduce external fragmentation.
You'll need to search for the quantization that leads to a global
optimum. This is likely to be higher for Lua than what you'd
choose for a general-purpose allocator (because Lua has immutable
strings).

--Mike