Problems with dynamic allocation in tasks

Problems with dynamic allocation in tasks

[ldb]

I have a piece of code that runs great under linux using GNAT and
terrible under Windows also using GNAT. The code makes ample use of
dynamic allocation and threads.

I've tracked the problem down to simple memory allocation. Under
windows, it appears to me that the 'new' operator and the unchecked-
decallocate operations are using a task lock that is totally jamming
the system. A single threaded version of the windows code runs faster
than the dual-threaded version (on linux, I get a speed-up of a factor
close to 2). The sad fact is 99+% of the these allocations are local
and do not need to be shared across tasks. Ideally, i'd be able to
create a task-local memory pool that doesn't require a mutex for these
allocations.. not sure how feasible this is in Ada, though.

The obvious solution is to remove or minimize dynamic allocations but
I fear this isn't really practical. If it comes to this, so be it, but
I'd rather exhaust the other options first.

The other option is to replace the allocator with one of my own (or
someone elses), which brings me to my question: how! What I'd really
like to do is make a library that lets me replace the global allocator
a la libgmem. I struggled through the source code and makefiles of
GNAT and failed miserably in replicated it's function.

In a nut shell, what I want to be able to do is take System.Memory,
copy it, change a line of code (Put_Line("hello world")), and then be
able to replace the global allocator with this one. I was able to get
a replacement body for System.Memory to build with the gnatg flag, and
was able to get an o file, but whenever i make a simple test program
it automatically wants to put the original System.Memory in and I get
duplicate units if I try to bind them.

If anyone knows a more elegant solution to the actual problem, or has
any other advice, I'd love to hear it.

Re: Problems with dynamic allocation in tasks

[Robert A Duff]

ldb <ldb_nospam@hotmail.com> writes:

>...Ideally, i'd be able to
> create a task-local memory pool that doesn't require a mutex for these
> allocations.. not sure how feasible this is in Ada, though.

It's quite feasible.  Look up storage pools (section 13.11 in the RM).

- Bob

Re: Problems with dynamic allocation in tasks

[ldb]

On Jul 25, 12:45 pm, Robert A Duff <bobd...@shell01.TheWorld.com>
wrote:
> ldb <ldb_nos...@hotmail.com> writes:
> >...Ideally, i'd be able to
> > create a task-local memory pool that doesn't require a mutex for these
> > allocations.. not sure how feasible this is in Ada, though.
>
> It's quite feasible.  Look up storage pools (section 13.11 in the RM).
>
> - Bob

I'm at a loss for how this possible using storage pools.

I've worked a good deal with storage pools but perhaps my vision of
their functionality is too narrow. It was my belief that a storage
pool can only be used globally for a particular type. These dynamic
allocations are done with global types, ie, Access_Vector. Certainly a
storage pool can be attached to Access_Vector and intercept, figure
out which thread its in.. but then what? In a "simple" implementation,
I'm still depending on System.Memory (which is malloc()) and it's
still gonna hit these mutexes.

I -could- make the storage-pool implement a full allocator so it's not
dependant on malloc() for each allocation. This is alot of work and
there are alot of types. If I go this route, I'd prefer to do a global
replace (which goes back to my original question of how to do it like
gmem does it).

Re: Problems with dynamic allocation in tasks

[Robert A Duff]

ldb <ldb_nospam@hotmail.com> writes:

> I'm at a loss for how this possible using storage pools.

You're right -- it's not as simple as I implied.

> I've worked a good deal with storage pools but perhaps my vision of
> their functionality is too narrow. It was my belief that a storage
> pool can only be used globally for a particular type.

Correct.

The Allocate routine for your pool would have to grab a pointer to the
"real" pool out of thread-local storage, and allocate memory from that.
Whether thread-local storage is efficient enough depends on the
system.

I don't think there's any portable and efficient way to use thread-local
storage -- you'd have to program that.  Task_Attributes doesn't count --
it does locking, which is what you're trying to avoid.

>...These dynamic
> allocations are done with global types, ie, Access_Vector. Certainly a
> storage pool can be attached to Access_Vector and intercept, figure
> out which thread its in.. but then what? In a "simple" implementation,
> I'm still depending on System.Memory (which is malloc()) and it's
> still gonna hit these mutexes.
>
> I -could- make the storage-pool implement a full allocator so it's not
> dependant on malloc() for each allocation.

Well, yeah, if you implement your own storage pool, you have to
implement it.  ;-)

>...This is alot of work and
> there are alot of types.

Yes, it's a lot of work.  Not sure what you mean by "a lot of types".
Many types can share the same pool, if you program the pool to work
for multiple sizes and alignments.  You have to write
"for T'Storage_Pool use ..." on each type, though.

>...If I go this route, I'd prefer to do a global
> replace (which goes back to my original question of how to do it like
> gmem does it).

- Bob

Re: Problems with dynamic allocation in tasks

[Dmitry A. Kazakov]

On Wed, 25 Jul 2007 10:04:48 -0700, ldb wrote:

> On Jul 25, 12:45 pm, Robert A Duff <bobd...@shell01.TheWorld.com>
> wrote:
>> ldb <ldb_nos...@hotmail.com> writes:

>>>...Ideally, i'd be able to
>>> create a task-local memory pool that doesn't require a mutex for these
>>> allocations.. not sure how feasible this is in Ada, though.
>>
>> It's quite feasible.  Look up storage pools (section 13.11 in the RM).
> 
> I'm at a loss for how this possible using storage pools.
> 
> I've worked a good deal with storage pools but perhaps my vision of
> their functionality is too narrow. It was my belief that a storage
> pool can only be used globally for a particular type.

In which sense? If you are going to make your pools task-local, then you
should know in advance which objects are local to the task. Types of the
objects are irrelevant, only access types count. So you just have to use
task-local access types. This will warranty that nothing would leak out:

task body Foo is
   Local_Pool : My_Own_Pool; -- The pool of the task

   type Thing_Ptr is access Thing; -- The access type of
   for Thing_Ptr'Storage_Pool use Local_Pool;

begin
   ...
   -- Now each new targeting a Thing_Ptr will go to My_Own_Pool

> I -could- make the storage-pool implement a full allocator so it's not
> dependant on malloc() for each allocation. This is alot of work and
> there are alot of types.

You have to implement only Allocate and Deallocate. Choose any of numerous
algorithms existing around. You should certainly know about the behavior of
your program. For example if you don't need to free objects, then you have
an "area", etc.

> If I go this route, I'd prefer to do a global
> replace (which goes back to my original question of how to do it like
> gmem does it).

That would be a bad idea, because in that case if you occasionally mixed
allocators / deallocators from different tasks, you'd mess up the pool
state beyond repair. It would be damn difficult to catch such bugs. With
task-local access types you are safe. Note that pool is an object, so you
can reuse your pool type implementation across many tasks just creating an
instance of for each.

P.S. If your objects aren't task-local, you could still avoid mutexes on a
single-CPU machine by implementing your pool owned by a protected object
with priority ceiling locking (ARM D.3)

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Problems with dynamic allocation in tasks

[Simon Wright]

ldb <ldb_nospam@hotmail.com> writes:

> In a nut shell, what I want to be able to do is take System.Memory,
> copy it, change a line of code (Put_Line("hello world")), and then
> be able to replace the global allocator with this one. I was able to
> get a replacement body for System.Memory to build with the gnatg
> flag, and was able to get an o file, but whenever i make a simple
> test program it automatically wants to put the original
> System.Memory in and I get duplicate units if I try to bind them.

I'm pretty sure that gnatmake -a recompiles all library units affected
by a change. So if you put your replacement library source in the
normal source path (eg in the current directory) gnatmake -a will
recompile all the library files that use it, automatically applying
the right flags (-gnatpg etc).