Re: [idea] Add memory pool to Lua?

[Christian Thaeter <ct@...>]

On 2016-06-04 19:42, Daurnimator wrote:

> On 4 June 2016 at 18:56, Xavier Wang <weasley.wx@gmail.com> wrote:
> > Hi list :)
> >
> > I have made a small library before[1], and I found a memory pool can
> > keep memory footprint small, and reduce allocate count much,
> > especially for object have same size.
> >
> > The implement is here[2], only less than 50loc, and it allocates a
> > page (4K) per time, and use it as a array to avoid alignment issues.
> > it use the last sizeof(void*) to make a linked list. When each page
> > allocated, the objects in it will use the first sizeof(void*) bytes
> > to make a free object linked list. if free objects exists, it just
> > do a pointer calculates to get a new object, and if no free object
> > exists, it allocate new pages. implements are quite small and clear.
> >
> > So, I plan to add this idea to Lua codebase, in two favours: first,
> > I will make a small memory pool, say 64bit per object, if Lua tries
> > alloc a memory less than 64bit, the memory will allocate from pool,
> > it save memory pieces created by small Lua closures, small strings,
> > etc. then, I will find objects that have same small size to make
> > they own pool for them. I think UpVal, Table are fits.
> >
> > I share this idea to list, so may somebody could interest it and
> > give some help, about:
> >   - Any advice or review are welcome, Thanks everybody that points
> > my fault :)
> >   - I'm not sure it can improve performance, it could make less
> > memory allocate count, but waste a little memory, So any test case
> > are welcome.
> >
> >
> > I will reply this mail after I make patch and have any result about
> > this.
> >
> > Thanks for watching :)
> >
> >
> > [1]: https://github.com/starwing/nui
> > [2]: https://github.com/starwing/nui/blob/new/nui.h#L441
> >
> > --
> > regards,
> > Xavier Wang.
> >
> 
> The main benefit of multiple memory pools is that cleanup is easy: you
> free/unmap the whole pool at once, instead of freeing each and every
> allocation. This saves you a substantial amount of bookkeeping.
> 
> What you're suggesting is just an optimised malloc/realloc for common
> lua object sizes.
> Lua *does* have a facility for this: you can pass a lua_Alloc to
> lua_newstate. However, it will be hard to beat your system's malloc;
> lots of research and benchmarking has (should have) gone into it.

Not necessary. I once made an static size-object allocator in a simple
unoptimized way (arrays of objects and a bitmap for free objects).
Then instead having a 'dumb' malloc() it has a malloc_near() interface.
One can pass another address and the allocator takes this as hint to
place things closely together to improve cache locality. For some
access patterns and datastructures the benefits are close to awesome.
Even in the unoptimized version where malloc/free is slower than then C
lib malloc, overall performance/throughput of the whole program
can be up to 60% higher. Operations like list/tree walking etc. benefit
extremely from cache locality on modern computers.

By default there is a malloc() interface in my code which takes the most
recent allocation as 'near' hint. But things really shine when the
calling program can provide proper hints. If it is possible to modify
the Lua-VM in this way, I expect there could be a huge benefit.

Code for reference is at:
 http://git.lumiera.org/gitweb/?p=LUMIERA;a=blob;f=src/lib/mpool.h
 http://git.lumiera.org/gitweb/?p=LUMIERA;a=blob;f=src/lib/mpool.c

I don't want to compete with your proposal, if you like some of my
stuff, feel free to use/copy things and put it under the MIT-License.

	Cheers
		Christian