Common allocation sizes for Lua

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

Common allocation sizes for Lua

Thomas Harning Jr.
Just wondering... are there any common allocation sizes for Lua that could perhaps take advantage of a memory pool (like boost's.. only coded in C instead)?

Boost's memory pool template class has the interesting property that it stores the free list interleaved in the data such that you end up w/ structures like this.
NEXTFREE -> A
A FREE->B
B FREE->D
C DATA
D FREE->NULL (requires another memory block)
E DATA
F DATA

Allocating requires simple ptr arithmetic that can be carried over such that multiple items can be allocated to handle arrays of data that are larger than a unit size.

Example Malloc:

ret = *nextfree; // ret = A
nextfree = *ret; // nextfree = B
return ret

Example free (non-ordered... ordered would be used if you want to do arrays of data w/ O(N) rather than O(N^2) or high fail-rate
//freed = A
*freed = *nextfree; // A => B
nextfree = freed;   // nextfree = A


Has anybody seen any library like this already for C? I've generally only seen linked-list style implementations that require separate storage.

Also... has anybody seen a way to calculate the LCM at compile-time for C? This is the way that the boost pool gets its allocation unit- size to get a safe alignment... At compile-time, i suppose a union w/ { void*, DATATYPE, size_t } /* size_t for the end of the structure to handle linking to the next major block */ would get me proper alignment right... run-time would require runtime LCM anyways.....

To see what I'm looking at as theory/impl reference:
http://www.boost.org/doc/libs/1_36_0/libs/pool/doc/concepts.html
http://www.boost.org/doc/libs/1_36_0/libs/pool/doc/implementation/alignment.html

Reply | Threaded
Open this post in threaded view
|

Re: Common allocation sizes for Lua

Alex Davies
You could create a sub-allocator for 32 bytes (x86), for allocating/freeing tables. I don't know how much the savings would be though - the node / array parts are what are expensive to create and resize. Other then that, not much could be gained from fixed size allocations (strings include a header + the string in the single allocation, as do userdata, so neither of these could be improved which leaves only coroutines and tables from runtime-allocated structures).

- Alex
Reply | Threaded
Open this post in threaded view
|

Re: Common allocation sizes for Lua

David Jones-2
In reply to this post by Thomas Harning Jr.

On 11 Sep 2008, at 06:19, Thomas Harning wrote:

Just wondering... are there any common allocation sizes for Lua that could perhaps take advantage of a memory pool (like boost's.. only coded in C instead)?

If you're suffering performance problems that you believe are due to memory allocation then plug in another memory allocator. Such as dlmalloc. Do NOT write your own.

If you're still suffering performance problems and you are absolutely sure that it is the memory allocator, then better start reading some papers. Start here: http://www.memorymanagement.org/bib/ and here: http://www.cs.kent.ac.uk/people/staff/rej/gc.html .

If your summary of Boosts' memory pool template class is correct, then they had better start reading some papers too.

drj


Reply | Threaded
Open this post in threaded view
|

Re: Common allocation sizes for Lua

Enrico Colombini
David Jones wrote:
If you're suffering performance problems that you believe are due to memory allocation then plug in another memory allocator. Such as dlmalloc. Do NOT write your own.

Or tlsf for embedded systems (bounded alloc/dealloc time).

  Enrico

Reply | Threaded
Open this post in threaded view
|

Re: Common allocation sizes for Lua

Thomas Harning Jr.
In reply to this post by David Jones-2

On Sep 11, 2008, at 4:26 AM, David Jones wrote:

If you're suffering performance problems that you believe are due to memory allocation then plug in another memory allocator. Such as dlmalloc. Do NOT write your own.

If you're still suffering performance problems and you are absolutely sure that it is the memory allocator, then better start reading some papers. Start here: http://www.memorymanagement.org/ bib/ and here: http://www.cs.kent.ac.uk/people/staff/rej/gc.html .

If your summary of Boosts' memory pool template class is correct, then they had better start reading some papers too.
No performance problems at all. Just looking to see if there's another use for what I plan on putting together.

Thinking over what I summarized as what happened, it turns out I got it mostly wrong... In trying to digest what needed to be done, I only thought out the case of data-size < ptr. A union will certainly not work here... now I see why they did LCM.... and why the ugly case looks like it does.

Target usage-- Note: Pools allocated for single data-types
Certain data items are expected to either be allocated/deallocated frequently (esp if no arrays of objects needed) or would like fast deterministic time OR it's highly beneficial that their memory can be dumped (optionally [if 1 element only] destructed w/ a function)

You can also get some other bonuses for normal use, such as locality/ etc.

Basic assumptions made:
* Arrays may not have padding... otherwise most assumptions will not work (sizeof array / sizeof element != num elements) * Block memory allocator will allocate blocks properly aligned such that the returned ptr will be aligned for (at least) a single element of any data-type <= the size requested.. ex: alloc(128) good enough for double, float, etc since they're all < 128... not necessarily good enough for a 200-byte object.

Ascii-drawing of an ugly case
	sizeof(T)         == 5
	sizeof(void*)     == 3
	sizeof(size_type) == 1

LCM(3,1)   == 3
LCM(5,3,1) == 15

Individual unit-chunk....
size  void* T
-----------+--------
1     3    |5
1     (12) | -- (10) left over
1          |
-----------|
1     3    |
1          |
1          |
-----------|
1     3    |
1          |
1          |
-----------|--------

In the normal case... such as a struct { void* ptr, int x, char z }
The compiler will pad it out such that in an array of them, the accesses are aligned...
Ex: AMD64
	sizeof(that T) == 16
	sizeof(void*)  == 8
	sizeof(size_t) == 8
LCM = 16 -- perfect!

Reply | Threaded
Open this post in threaded view
|

Re: Common allocation sizes for Lua

Taj Khattra
In reply to this post by David Jones-2
On Thu, Sep 11, 2008 at 1:26 AM, David Jones <[hidden email]> wrote:
> If you're suffering performance problems that you believe are due to memory
> allocation then plug in another memory allocator.  Such as dlmalloc.  Do NOT
> write your own.

... or try to tune your existing allocator:

    http://www.usenix.org/publications/library/proceedings/als01/ezolt.html