Re: Addressing fragmentation

On Tue, 1 Feb 2005 10:26:10 +1100, Mark Wayland <Mwayland <at> torus.com.au> wrote:
> (1) Pools of fixed sized items; simple, exceedingly fast and only 4
> bytes overhead for the entire pool, not on each item.
>    (2 lines of code for an allocate, 2 lines for free, memory required =
> 4 + (pool item count * pool item size))

This brings up something I've wondered about recently. I require that
users of the pool system track allocation sizes themselves, and pass
it to (our version of) free(); with so many ways of allocating memory,
it's hard to tell just from a bare pointer (or even a pointer and a
library id) where the pointer came from. I especially don't want to go
through all our various pools asking them "did this pointer come from
you?"

An additional C++ annoyance is that there doesn't seem to be a way to
pass arguments to the delete operator and have them passed onto
operator delete. So while it's easy to do something like

char* pFoo = new(arena) char[n];

you can't follow it up with

delete(arena)[] pFoo;

So instead we either macro in operators new/delete into the class
declaration, or use a more verbose API.

Any clever tricks here?

p

RE: Addressing fragmentation

 > This brings up something I've wondered about recently. I 
> require that users of the pool system track allocation sizes 
> themselves, and pass it to (our version of) free(); with so 
> many ways of allocating memory, it's hard to tell just from a 
> bare pointer (or even a pointer and a library id) where the 
> pointer came from.

I'm not sure I understand what you mean, surely when deallocating the
pointer goes back to the pool it comes from?
Something like so..

// create a 256 pool of somethings
cPool<Something> newPool(256);

Something* someThing = newPool.Allocate();
newPool.Free(someThing );

For type-variable pools we do something similar with byte, but use placement
new when needed.

A.

> -----Original Message-----
> From: 
> sweng-gamedev-midnightryder.com-admin <at> lists.midnightryder.com 
> [mailto:sweng-gamedev-midnightryder.com-admin <at> lists.midnightry
> der.com] On Behalf Of Paul Du Bois
> Sent: Monday, January 31, 2005 4:36 PM
> To: sweng-gamedev <at> midnightryder.com
> Subject: Re: [Sweng-gamedev] Addressing fragmentation

RE: Addressing fragmentation

> char* pFoo = new(arena) char[n];

> you can't follow it up with

> delete(arena)[] pFoo;

But you can put the pointer to the arena before the block 
returned into pFoo. That, of course, costs you 4 bytes per 
allocation, so it's not entirely free, but a reasonable 
trade-off for a general-purpose allocator system.

However, 99% of the time, whomever allocated an object 
also frees it, so it's easy to match up the deletion with 
the allocation. And allocation/deletion out of pools 
typically looks something like:

  PoolAllocator< MyThing, 100 > pool_;

  MyThing * thing = pool_.makeOne();
  thing->initialize( args );

  pool_.reclaim( thing );

Cheers,

			/ h+

_______________________________________________
Sweng-gamedev mailing list

Re: Addressing fragmentation

On Tue, 1 Feb 2005 00:53:34 -0000, Andrew Grant <agrant <at> climaxgroup.com> wrote:
> I'm not sure I understand what you mean, surely when deallocating the
> pointer goes back to the pool it comes from?

The difference is that all our memory alloc/dealloc gets funneled
through a single set of routines, which choose a particular
implementation or arena. There are pool-like structures lying around
at the user level, but there is also a full slate of pools buried
under our allocator interface. A simple example:

// using custom operator new/delete
Trigger* pTrigger = new Trigger(...);
// becomes PsychonautsAlloc(size=sizeof(Trigger),
type=MEMTYPE_Trigger, bWantsPool=true)
delete pTrigger;
// becomes PsychonautsFree(ptr, size=sizeof(Trigger),
type=MEMTYPE_Trigger, bWantsPool=true)

And a tricker one -- in Lua, all memory allocation eventually goes to
a routine with the prototype

    void* luaM_realloc(void* oldptr, size_t newsize);

Since Lua tends to allocate a ton of very tiny blocks, it's definitely
worthwhile to pool its allocs. So we went through the lua library
figuring out the sizes of objects (where possible) and passing the
size to luaM_realloc, which propagates the info to our own alloc/free.
Where we can't figure out the size (or can't be bothered with figuring
it out) we just pass -1 and force a linear search to see if it came
from a pool: annoying, but the fallback isn't used often.

Re: Addressing fragmentation

Paul Du Bois wrote:

> Actually, I realize that we have just one freelist which threads through all
> of the blocks; that can't be good.  It seems clearly superior for each block
> to have its own freelist.  Currently, our allocations spread out over time,
> tending to prevent any blocks from being reclaimed:
> 
> Pool 48: 82 blocks, 2639 free chunks
>     0:   27/ 128 chunks free (0x0155e2f0 + 6160)
>     1:   13/ 128 chunks free (0x01acd730 + 6160)
>     ...
>    80:    0/ 128 chunks free (0x00bfcae0 + 6160)
>    81:    0/ 256 chunks free (0x00be9e60 + 12304)
> 
> Thanks all for the suggestions so far. I'll be sure to take a good
> look at that paper.

Here's a revere of nostalgia for (uh) the middle 1980s...

The Amiga had a nifty editor called UEdit, which used a page block
algorithm that totally shredded, in only 7 megahertz. When you type it
would split the current block, so the next characters have all the
remaining block available for themselves. No more splits. Then when
the editor idled, it would start an interruptible heap compaction.

What made this great was a little memory viewer on the side. You could
type, and watch the blocks split up. Then you could idle, and watch
the blocks sort themselves out and compact. (Amigas ran with
super-primitive memory, so applications could frag each other's arenas
freely. UEdit played by the rules, and left the maximum contiguous

RE: Addressing fragmentation

Ahh I see, your pools are based on the size of what you're trying to alloc
and then the allocator figures out whether to return memory from a pool or
the main heap?

It seems a little convoluted, but I guess that makes things easier for
client code in so far as it doesn't need to worry about using pools - but
then for things which need to be pooled then then client code should really
be aware of this fact in most cases and dumbing things down isn't always a
good idea. What happens if a pool is full? I'm guessing the allocator
doesn't throw an exception since it's console based.

I would agree that LUA (or most scripting languages!) are good candidates
for using their own pool due to their memory allocation whims, but surely in
this case it's better to make LUA always do all it's allocations from a
separate memory pool or heap?

Andrew

> -----Original Message-----
> From: 
> sweng-gamedev-midnightryder.com-admin <at> lists.midnightryder.com 
> [mailto:sweng-gamedev-midnightryder.com-admin <at> lists.midnightry
> der.com] On Behalf Of Paul Du Bois
> Sent: Monday, January 31, 2005 5:18 PM
> To: sweng-gamedev <at> midnightryder.com
> Subject: Re: [Sweng-gamedev] Addressing fragmentation
> 
> On Tue, 1 Feb 2005 00:53:34 -0000, Andrew Grant 
> <agrant <at> climaxgroup.com> wrote:

Re: Addressing fragmentation

On Tue, 1 Feb 2005 01:58:33 -0000, Andrew Grant <agrant <at> climaxgroup.com> wrote:
> Ahh I see, your pools are based on the size of what you're trying to alloc
> and then the allocator figures out whether to return memory from a pool or
> the main heap?

Pretty much. The user still must request pooling explicitly; but the
intent was to share the pools as much as possible.

I see a couple different use-cases for pools:

- You know you're never going to need more than N widgets, so you set
aside the space up-front
- (for whatever reason) you have a lot of small allocations, and you
want to reduce your allocator overhead.

For the former use case, we use user-space collection classes which
don't happen to be called pools (but that's pretty much what they
are).

> It seems a little convoluted, but I guess that makes things easier for
> client code in so far as it doesn't need to worry about using pools - but

Well, the client code still does need to follow a particular protocol:
it must ask for a pooled alloc; if it does, it must ask for a pooled
free; it should pass a size to free(). The intent isn't to make a
dumbed-down API (although there's nothing wrong with a _simple_ api)
but to encourage sharing of the system.

> then for things which need to be pooled then then client code should really
> be aware of this fact in most cases and dumbing things down isn't always a

RE: Addressing fragmentation

To fix your linear search I'd recommend a pooling system which does
three things:

1.  Allocates base sets of blocks in individual virtual page
allocations.  Then if you run a garbage collect you can hand entire
pages back to the global memory space for re-purposing.  And you can do
#2.
2.  Tracks a bit for each possible virtual page indicating whether it
was allocated by the pooling system.  On a certain system I work on this
ends up being 4KB worth of bits so a single page is dedicated to this
tracking for the entire pooling system (not one per pool).
3.  Stores a per page header at a standard place in the page (like the
end to avoid alignment problems with your individual blocks).  In the
header you keep your link to the next page of blocks and a size value.
Or a pointer to the pool which owns the page.

Then you're able to a) determine in constant time whether a pointer came
from your pooling system (look up the bit for the page the pointer is
on) and b) identify which individual pool to free the pointer from
(based on the size or owner pointer in the header).

Plus you didn't have to hand around the size parameter to all of your
destructors so you can override every allocation you can find regardless
of function signature.

I'm having good success with a small block allocator designed around
these criteria.

chris

Re: Addressing fragmentation

> 1.  Allocates base sets of blocks in individual virtual page allocations.

That's a nice solution. I like page table tricks; I use them with our
stack-like allocator. It's too bad they don't work with another
certain system 

p
_______________________________________________
Sweng-gamedev mailing list
Sweng-gamedev <at> lists.midnightryder.com
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com

Re: Addressing fragmentation

   I love page table tricks (I just wish I could tell you _exactly_ how much .

   The only improvement I have over this type of allocator is (ab)using virtual memory space to eliminate the overhead of the headers.

   The trick is to reserve a large amount of virtual address space (I used 512 MB), and split it into pools of blocks of various sizes. This way, you can determine the size of a block just by examining the pointer. This way, all the memory is either free or allocated, so no overhead, only fragmentation if any. You'd then allocate and free pages explicitly within each pool as appropriate. Group blocks into pages (also of constant size, and with a little header each - can't get around that), and use the space of free blocks to keep a singly-linked list of free blocks. So, all operations stay constant-time, including reclaiming unused memory. Not even a map of bits is needed. Maps of bits are great for debugging, though: they allow you to determine whether blocks are really allocated or not.

   Implementation of this is particular to each platform. I can confirm that this works fine on Xbox (the Win32 VirtualAlloc API works great for this). On Windows it'd be very similar, but you'd need a good fallback mechanism, because the virtual space might already be too fragmented (due to DLL placement) to allocate a single large range of addresses. I've seen programs fail to allocate 512 MB due to this, although that was back on Windows 98. Other platforms... it should be doable as long as they support virtual address remapping.

JCAB

Paul Du Bois wrote:

1. Allocates base sets of blocks in individual virtual page allocations.

That's a nice solution. I like page table tricks; I use them with our stack-like allocator. It's too bad they don't work with another certain system p _______________________________________________ Sweng-gamedev mailing list Sweng-gamedev <at> lists.midnightryder.com http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com