[idea] Add memory pool to Lua?

classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

[idea] Add memory pool to Lua?

Xavier Wang
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.

Reply | Threaded
Open this post in threaded view
|

Re: [idea] Add memory pool to Lua?

Daurnimator
On 4 June 2016 at 18:56, Xavier Wang <[hidden email]> 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.

Reply | Threaded
Open this post in threaded view
|

Re: [idea] Add memory pool to Lua?

Xavier Wang


2016-06-04 17:42 GMT+08:00 Daurnimator <[hidden email]>:
> 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.
>

Good point! thanks for remind me.

So, I could first make a special allocate function for Lua, export as lua_Alloc to see whether it's different. But I can't get correct object size outside Lua, so if it does make different, to merge code into Lua is necessary.

system's malloc/free is good at general memory maintain, but if most memory are same size (not Lua itself, Lua use many variable size objects. But my library nui's object mostly have same size), *maybe* use pool may fast, with pool, only one pointer calculate is need when allocate, and two need when free in most scene, can system's malloc fast than that?

--
regards,
Xavier Wang.
Reply | Threaded
Open this post in threaded view
|

Re: [idea] Add memory pool to Lua?

Christian Thaeter
In reply to this post by Daurnimator
On 2016-06-04 19:42, Daurnimator wrote:

> On 4 June 2016 at 18:56, Xavier Wang <[hidden email]> 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


Reply | Threaded
Open this post in threaded view
|

Re: [idea] Add memory pool to Lua?

Sean Conner
In reply to this post by Daurnimator
It was thus said that the Great Daurnimator once stated:

> On 4 June 2016 at 18:56, Xavier Wang <[hidden email]> wrote:
> > 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.
>
> 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.

  You might also want to record the memory allocations that Lua does to see
if there is any benefit to your idea.  I installed a custom allocator that
just logged memory allocations/frees done by Lua [1] and ran it over one
relatively simple Lua application I have.  The output looked like:

        + 348 0
        + 192 0
        + 540 0
        + 32 0
        - 0 0
        + 56 0

... and so on.  Lines leading with a '-' are frees, and lines with a '+'
are allocations or reallocations; second column is new size, last column is
old size.  Using simple Unix commands, a list of the most common operations
[2]:

   2268 - 0 0
   1027 - 0 32
   1027 + 32 0
    826 - 0 112
    826 + 112 0
    464 - 0 24
    404 - 0 20
    386 + 24 0
    361 + 20 0
    354 - 0 26
    354 + 26 0
    299 + 16 0
    279 - 0 36
    260 + 36 0
    241 - 0 28
    235 + 28 0
    233 - 0 56
    227 + 56 0
        ...

And another look [3], this time with just resizing memory blocks:

    199 + 32 16
    135 + 64 32
    100 + 128 64
     92 + 96 48
     66 + 256 128
     52 + 24 12
     49 + 24 48
     49 + 192 96
     46 + 4 16
     43 + 20 32
     41 + 8 16
     37 + 48 24
     29 + 12 48
        ...

  A different application will have different allocations, so this is
something you'll need to measure for your particular usage.

  -spc (don't forget---those numbers above are for one aplication---I
        measured another Lua program and the top to allocations were 32
        bytes and 108 bytes ... )

[1] The code.  Feel free to use it.

#include <stdlib.h>
#include <stdio.h>
#include <lua.h>
#include <lualib.h>
#include <lauxlib.h>

/*********************************************************************/

static void *my_alloc(
        void   *ud,
        void   *ptr,
        size_t  osize,
        size_t  nsize
)
{
  FILE *out = ud;
 
  if (nsize == 0) /* free() */
  {
    fprintf(out,"- %zu %zu\n",nsize,osize);
    free(ptr);
    return NULL;
  }
  else
  {
    fprintf(out,"+ %zu %zu\n",nsize,osize);
    return realloc(ptr,nsize);
  }
}

/*********************************************************************/

int main(int argc,char *argv[])
{
  lua_State  *L;
  FILE       *out;
  int         rc;
  int         i;
 
  if (argc == 1)
  {
    fprintf(stderr,"usage: %s script\n",argv[0]);
    return EXIT_FAILURE;
  }
 
  out = fopen("/tmp/memusage.txt","w");
  L = lua_newstate(my_alloc,out);
 
  if (L == NULL)
  {
    fprintf(stderr,"lua_newstate() failed\n");
    exit(EXIT_FAILURE);
  }
 
  lua_gc(L,LUA_GCSTOP,0);
  luaL_openlibs(L);
  lua_gc(L,LUA_GCRESTART,0);
 
  lua_createtable(L,0,0);
  for (i = 0 ; i < argc ; i++)
  {
    lua_pushinteger(L,i-1);
    lua_pushstring(L,argv[i]);
    lua_settable(L,-3);
  }
  lua_setglobal(L,"arg");
 
  rc = luaL_loadfile(L,argv[1]);
  if (rc == 0)
    rc = lua_pcall(L,0,LUA_MULTRET,0);
   
  if (rc != 0)
    fprintf(stderr,"%s: %s\n",argv[1],lua_tostring(L,-1));
 
  lua_close(L);
  fclose(out);
  return rc;
}

/*********************************************************************/

[2] sort memusage.txt | uniq -c | sort -rn | more

[3] grep '+' memusage.txt | grep -v ' 0$' | sort | uniq -c | sort -rn | more

Reply | Threaded
Open this post in threaded view
|

Re: [idea] Add memory pool to Lua?

Long Cheng
In reply to this post by Xavier Wang
 From my experience google perftools tcmalloc is good enough, you really
dont have to reinvent the wheel, and chances are you can't make one beat
google tcmalloc's performance.

https://github.com/gperftools/gperftools


在 2016/6/4 16:56, Xavier Wang 写道:

> 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
>