> Lua also allocates memory at runtime, for growing the Lua stack and otherIt's those internal structures that concern me. My goal is to try to minimize the use of the heap because no dynamic memory allocator is perfect.
> internal structures, and also when creating strings (notably implicitly
> when converting things to strings for output).
No, but some of them go pretty close. On a system without a MMU, dlmalloc seems to perform very well. TLSF might be another good choice, although its own memory requirements are larger than dlmalloc's. Overall, based on some of my experiments, I recommend a form of segregated allocator, they seem to handle fragmentation quite well.
I'm thinking about using Lua to write programs for microcontrollers. My concern is with determining the upper bound runtime of chunks of Lua code. For example, I like to know my interrupt service routine won't miss an interrupt.
> Perhaps it will help if you could tell us what kind of Lua programs you
> intend to run.
This doesn't depend on the allocator that much, most of the execution time will still most likely be in the Lua interpreter main loop, and this isn't really something you can avoid. If you want to have realtime response to your interrupts directly from Lua, I don't think this is possible. Of course, this largely depends on your realtime requirements and when the hardware capabilities of the platform you're using, but for microcontrollers experience suggests that this is true. The approach we're taking to provide this in eLua is two level: servce all the critical interrupts in hardware when needed, and queue all the others. Then the Lua code will be able to serve the interrupts in the queue later. Obviously not realtime, but at least you're not keeping your interrupt controller blocked while waiting for the interrupt to be acknowledged in Lua.
Other more radical possibilities include modifying eLua itself :) It's what our LTR patch does. All things considered though, Lua will always need a memory allocator, so it's up to you to provide a good one for your system.