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

["Bogdan Marinescu" <bogdan.marinescu@...>]

Hi all,

I'm trying to understand what would be the best memory allocator to use in order to run Lua (5.1.3) in an embedded system. As part of this task, I wrote a simple memory statistics module that replaces Lua's default allocator and logs  malloc, realloc and free calls and their arguments, and a Python script (I'm still a beginner at Lua :) ) to interpret the results. I ran 'life.lua', and the results surprised me. Specifically, I can see lots and lots of realloc calls with a one byte difference between the old block size and the new block size, in both directions (+1 or -1 difference). There are about 818000 of them. These are the complete statistics, for whoever is curious about them: 

One byte reallocs: 818003
MALLOCS: 1642338
FREES: 1642338
RELLOCS: 833088
Min block size: 12
Max block size: 4096

INTERVAL                MALLOCS         FREES           REALLOCS                
=======================================================================
12 - 216                394650          394602          985             
216 - 420               408021          408026          30055           
420 - 624               408020          408022          408006          
624 - 828               408000          408041          394040          
828 - 1032              20007           20007           2               
1032 - 1236             0               0               0               
1236 - 1440             0               0               0               
1440 - 1644             0               0               0               
1644 - 1848             1               1               0               
1848 - 2052             1820            1820            0               
2052 - 2256             0               0               0               
2256 - 2460             0               0               0               
2460 - 2664             0               0               0               
2664 - 2868             0               0               0               
2868 - 3072             0               0               0               
3072 - 3276             0               0               0               
3276 - 3480             0               0               0               
3480 - 3684             0               0               0               
3684 - 3888             0               0               0               
3888 - 4092             0               0               0               
4092 - 4096             1819            1819            0   

Again, I'm a beginner at Lua, so I apologise in advance if this is a stupid question, but is this amount of very small delta (1 byte in this case) reallocs normal? I suspect this has quite a large impact on performance and memory fragmentation (again, I'm trying to run this on an embedded system that has no MMU and a limited amount of RAM, so memory allocation is an important issue). As part of the tests, I implemented a very simple allocator (DOS-like, with variable sized blocks chained to each other) on a desktop machine and tried to run 'life.lua' with it. After giving it 512M of RAM to use, it was still not able to run 'life.lua' (it runs fine with other tests). I know this doesn't really prove anything, as a chained allocator like this is anything but smart or optimal from a fragmentation perspective, but it does give an idea about the effects of fragmentation.
I ran other tests too ('factorial.lua' and 'bisect.lua', for example), but the reallocs there looked much more 'natural' to me. 'life.lua' is the only example that exhibits this behaviour. Any thoughts on this?

Thanks,
Bogdan