Ada containers and custom allocators

Ada containers and custom allocators

[Maciej Sobczak]

Hi,

Is it possible to set up a custom allocator for use with any given Ada
container?

--
Maciej Sobczak * www.msobczak.com * www.inspirel.com

Re: Ada containers and custom allocators

[Dmitry A. Kazakov]

On Mon, 7 Jan 2008 07:48:58 -0800 (PST), Maciej Sobczak wrote:

> Is it possible to set up a custom allocator for use with any given Ada
> container?

Formally yes, the container type is just a type and you can declare a
pool-specific access type for it.

Though, if the container implementation allocates some things privately,
then you have no influence on how it does that, unless this allocation is
exposed in container's interface.

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

Re: Ada containers and custom allocators

[Randy Brukardt]

"Maciej Sobczak" <see.my.homepage@gmail.com> wrote in message
news:472f2c87-1238-42a5-8b94-92e9b70981da@f47g2000hsd.googlegroups.com...
> Hi,
>
> Is it possible to set up a custom allocator for use with any given Ada
> container?

If you mean an allocator for the private data of the container (which
includes all of the elements and is the bulk of the container), the answer
is no. The standard Ada containers do not provide any mechanism to control
how/were the container allocates memory.

We've discussed whether it would be possible to change that (perhaps by
including a Storage_Pool parameter to the instantiation), but that would be
(a) rather inconvenient, as there is no name for the standard storage pool,
and there was substantial opposition to defining one; (b) very constraining
on implementations, as the allocation behavior of the container would have
to be fairly strongly defined in order for this to be useful (or, the
storage pool passed would have to be completely general, allowing any size
allocation, which would eliminate the vast majority of interesting things
that you can do with storage pools).

Thus, it seems more valuable to have bounded forms for which all of the
allocation can be part of the container object, in which case a regular
access type and allocator would do the trick. There is a project to define
those in the works, but it hasn't been making a lot of progress.

                     Randy.

Re: Ada containers and custom allocators

[Maciej Sobczak]

On 8 Sty, 02:54, "Randy Brukardt" <ra...@rrsoftware.com> wrote:

> > Is it possible to set up a custom allocator for use with any given Ada
> > container?
>
> If you mean an allocator for the private data of the container (which
> includes all of the elements and is the bulk of the container), the answer
> is no.

This is exactly what I mean. It is not uncommon for a program to have
a majority of its dynamic memory managed by containers.

> The standard Ada containers do not provide any mechanism to control
> how/were the container allocates memory.

This limitation prevents programmers from doing many interesting
optimizations. Even if we put performance issues aside, I might want
to control the memory allocation for reliability.

[...]
> (or, the
> storage pool passed would have to be completely general, allowing any size
> allocation, which would eliminate the vast majority of interesting things
> that you can do with storage pools).

There are ways to overcome this problem, at least for some container
types. Node-based containers could use fixed-size allocators, but of
course it is the container which would then instantiate the allocator
with the proper node size. It was possible in C++.

--
Maciej Sobczak * www.msobczak.com * www.inspirel.com

Re: Ada containers and custom allocators

[Randy Brukardt]

"Maciej Sobczak" <see.my.homepage@gmail.com> wrote in message
news:fb7764c5-31f9-488d-a0e6-53ffd6c96182@k39g2000hsf.googlegroups.com...
> On 8 Sty, 02:54, "Randy Brukardt" <ra...@rrsoftware.com> wrote:
...
> > The standard Ada containers do not provide any mechanism to control
> > how/were the container allocates memory.
>
> This limitation prevents programmers from doing many interesting
> optimizations. Even if we put performance issues aside, I might want
> to control the memory allocation for reliability.

Yes, of course. It could be used for performance monitoring as well. But I
wouldn't characterize it as "many" interesting optimizations, it's more like
a few interesting things. But it isn't valuable enough to force every user
of a container to define a storage pool (since there is no name for a
standard storage pool). And we needed to keep the number of standard
containers manageable.

> [...]
> > (or, the
> > storage pool passed would have to be completely general, allowing any
size
> > allocation, which would eliminate the vast majority of interesting
things
> > that you can do with storage pools).
>
> There are ways to overcome this problem, at least for some container
> types. Node-based containers could use fixed-size allocators, but of
> course it is the container which would then instantiate the allocator
> with the proper node size. It was possible in C++.

Only if you put severe limits on the implementations. For one thing, you
would need to know the fixed node size in the storage pool in order to take
any realistic advantage of it, but you couldn't ask the container's
implementation for that size since you'd have to pass the storage pool to
the instance. The only practical way to do that is to *require* a particular
node layout. We might as well just standardize the source code of the
container body in that case.

Moreover, there is no requirement in Ada that objects be laid out
continuously. Janus/Ada will often make several allocator calls when
allocating parts of an object, and those calls will all be different sizes.
That's especially true inside of a generic body, where essentially
everything that depends on a formal type is of an unknown size and thus has
to be allocated separately. Even if you had the source code of the body, it
probably would make different calls to Storage_Pool.Allocate on Janus/Ada
and on GNAT.

We'd also have to define what operations can calls the allocators.
Currently, there are no such restrictions on the containers implementation.

Also, of course, it would only work for a couple of the containers. All of
the hashed forms also are going to allocate the hash table, so there are
going to be odd-size allocations (more than just nodes). And the vectors are
likely to allocate chunks of various sizes.

The net effect is that this is not possible to define (or use) in any
useful, portable way. (If you're willing to stick to a single vendor, then
it is more possible, but that of course has nothing to do with the
standard.) Combined with the inability to name the standard storage pool,
there isn't much point in doing this for the primary containers.

The basic idea of the containers was to define a specification, and allow
implementers to innovate on the implementations. (They don't even have to be
in Ada.) The extra specification required to allow passing in a storage pool
would seriously reduce these possibilities.

The bounded forms seem to allow even better control over dynamic allocation
(by not having any in the common case, although that surely wouldn't be true
for Janus/Ada), are much easier to use (don't have to write a storage pool),
and would work for the high-intergrity types that cannot allow an allocator
near their program. Thus, they're the first focus of work. There are a lot
of other ideas, but I can't say what if anything will come of them.

                                                     Randy.

Re: Ada containers and custom allocators

[Dmitry A. Kazakov]

On Tue, 8 Jan 2008 17:54:44 -0600, Randy Brukardt wrote:

> But it isn't valuable enough to force every user
> of a container to define a storage pool (since there is no name for a
> standard storage pool).

That always wondered me, why there is no name for. Especially because the
default storage pool can be obtained anyway:

type Some_Ptr is access Integer; -- Goes to the default storage pool
package Foo is new Boo (Some_Ptr'Storage_Pool);

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

Re: Ada containers and custom allocators

[Robert A Duff]

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:

> On Tue, 8 Jan 2008 17:54:44 -0600, Randy Brukardt wrote:
>
>> But it isn't valuable enough to force every user
>> of a container to define a storage pool (since there is no name for a
>> standard storage pool).
>
> That always wondered me, why there is no name for. Especially because the
> default storage pool can be obtained anyway:
>
> type Some_Ptr is access Integer; -- Goes to the default storage pool
> package Foo is new Boo (Some_Ptr'Storage_Pool);

The compiler is not required to use the same storage pool for all
types.  Therefore, the concept "THE default pool" does not exist.

Some_Ptr'Storage_Pool might be a special pool tuned for the fact that
Size_In_Storage_Elements = 4 and Alignment = 4.  Allocate could
add 4 to a known-aligned pointer, and ignore the
Size_In_Storage_Elements and Alignment parameters.

If Boo uses this pool for something other than Integer,
it might not work.

However, I see nothing wrong with having a predefined operation that
returns a suitable pool.

- Bob

Re: Ada containers and custom allocators

[Dmitry A. Kazakov]

On Wed, 09 Jan 2008 10:29:46 -0500, Robert A Duff wrote:

> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
> 
>> On Tue, 8 Jan 2008 17:54:44 -0600, Randy Brukardt wrote:
>>
>>> But it isn't valuable enough to force every user
>>> of a container to define a storage pool (since there is no name for a
>>> standard storage pool).
>>
>> That always wondered me, why there is no name for. Especially because the
>> default storage pool can be obtained anyway:
>>
>> type Some_Ptr is access Integer; -- Goes to the default storage pool
>> package Foo is new Boo (Some_Ptr'Storage_Pool);
> 
> The compiler is not required to use the same storage pool for all
> types.  Therefore, the concept "THE default pool" does not exist.
> 
> Some_Ptr'Storage_Pool might be a special pool tuned for the fact that
> Size_In_Storage_Elements = 4 and Alignment = 4.  Allocate could
> add 4 to a known-aligned pointer, and ignore the
> Size_In_Storage_Elements and Alignment parameters.
> 
> If Boo uses this pool for something other than Integer,
> it might not work.

Which is broken then. Because it does not fulfill the contract of
Storage_Pool'Class. I guess that Allocate is allowed to raise
Storage_Error, but not to ignore parameters.

If the implementation handles a family of pools one per object's size power
of two or like that, then it should return the family root rather than the
size-specific pool. Otherwise, the following will work either:

type Integer_Ptr is access Integer;
type Character_Ptr is access Character;
for Character_Ptr'Storage_Pool use Integer_Ptr'Storage_Pool;

I think ARM should clarify the issue of how pools could be constrained
while allowing a safe use.

> However, I see nothing wrong with having a predefined operation that
> returns a suitable pool.

Yes. 

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

Re: Ada containers and custom allocators

[Robert A Duff]

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:

> On Wed, 09 Jan 2008 10:29:46 -0500, Robert A Duff wrote:
>> Some_Ptr'Storage_Pool might be a special pool tuned for the fact that
>> Size_In_Storage_Elements = 4 and Alignment = 4.  Allocate could
>> add 4 to a known-aligned pointer, and ignore the
>> Size_In_Storage_Elements and Alignment parameters.
>> 
>> If Boo uses this pool for something other than Integer,
>> it might not work.
>
> Which is broken then. Because it does not fulfill the contract of
> Storage_Pool'Class.

What's the contract of Storage_Pool'Class?  It is certainly not intended
that all pools must support all sizes and alignments -- that would
defeat the optimization purpose of pools.

>...I guess that Allocate is allowed to raise
> Storage_Error, but not to ignore parameters.

Well, if it ignores the size, or raises an exception when the size is
not 4, either way, it won't work when the size is not 4.  But I agree
that an exception is better.  I'd like to suppress that check, though,
if it's too slow.

> If the implementation handles a family of pools one per object's size power
> of two or like that, then it should return the family root rather than the
> size-specific pool.

What if there is no such root?  How about an implementation that creates
one pool for each static size that is used in the program, up to 100
bytes.  Any access type whose designated type's size is nonstatic,
or > 100, uses a separate pool that can handle any size, and does
not call those static-size pools.  Each static-size pool has the
size built in to its code.

Sounds like an efficient implementation.  When you say "new Integer",
there's no need to check the size at run time, because the compiler
knows it's 4.  Do you think this implementation is wrong?

>...Otherwise, the following will work either:
>
> type Integer_Ptr is access Integer;
> type Character_Ptr is access Character;
> for Character_Ptr'Storage_Pool use Integer_Ptr'Storage_Pool;

I don't think the RM requires the above to work properly.

> I think ARM should clarify the issue of how pools could be constrained
> while allowing a safe use.

Perhaps.

>> However, I see nothing wrong with having a predefined operation that
>> returns a suitable pool.
>
> Yes. 

- Bob

Re: Ada containers and custom allocators

[Dmitry A. Kazakov]

On Wed, 09 Jan 2008 16:58:22 -0500, in comp.lang.ada you wrote:

> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
> 
>> On Wed, 09 Jan 2008 10:29:46 -0500, Robert A Duff wrote:
>>> Some_Ptr'Storage_Pool might be a special pool tuned for the fact that
>>> Size_In_Storage_Elements = 4 and Alignment = 4.  Allocate could
>>> add 4 to a known-aligned pointer, and ignore the
>>> Size_In_Storage_Elements and Alignment parameters.
>>> 
>>> If Boo uses this pool for something other than Integer,
>>> it might not work.
>>
>> Which is broken then. Because it does not fulfill the contract of
>> Storage_Pool'Class.
> 
> What's the contract of Storage_Pool'Class?  It is certainly not intended
> that all pools must support all sizes and alignments -- that would
> defeat the optimization purpose of pools.

But a loose contract would make storage pools unusable. Actually it depends
on the semantics of the attribute P'Storage_Pool. When the result is a
constrained (optimized) pool then indeed there will be no way to fix it.

>>...I guess that Allocate is allowed to raise
>> Storage_Error, but not to ignore parameters.
> 
> Well, if it ignores the size, or raises an exception when the size is
> not 4, either way, it won't work when the size is not 4.  But I agree
> that an exception is better.  I'd like to suppress that check, though,
> if it's too slow.

Either way is bad. Storage_Error should indicate a run-time problem, while
using an inappropriate pool is just a bug, basically a type error. And it
should be Constraint_Error then.

>> If the implementation handles a family of pools one per object's size power
>> of two or like that, then it should return the family root rather than the
>> size-specific pool.
> 
> What if there is no such root?  How about an implementation that creates
> one pool for each static size that is used in the program, up to 100
> bytes.  Any access type whose designated type's size is nonstatic,
> or > 100, uses a separate pool that can handle any size, and does
> not call those static-size pools.  Each static-size pool has the
> size built in to its code.
> 
> Sounds like an efficient implementation.  When you say "new Integer",
> there's no need to check the size at run time, because the compiler
> knows it's 4.  Do you think this implementation is wrong?

It is not wrong. Wrong is when P'Storage_Pool returns a specific pool from
the family. It should return a possibly less efficient family root pool,
which has to be present (when used). If an access type is created with this
root pool, the implementation is free to choose a more specific pool
instead. If for example the object size is known to be static. But that is
an implementation detail which may not leak outside (through
P'Storage_Pool, for instance). I think it should be no problem to remove
the root pool altogether upon linking when it is never used, i.e. there
should be no any overhead.

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

Re: Ada containers and custom allocators

[Randy Brukardt]

"Robert A Duff" <bobduff@shell01.TheWorld.com> wrote in message
news:wcchchnc905.fsf@shell01.TheWorld.com...
> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
...
> > That always wondered me, why there is no name for. Especially because
the
> > default storage pool can be obtained anyway:
> >
> > type Some_Ptr is access Integer; -- Goes to the default storage pool
> > package Foo is new Boo (Some_Ptr'Storage_Pool);
>
> The compiler is not required to use the same storage pool for all
> types.  Therefore, the concept "THE default pool" does not exist.
>
> Some_Ptr'Storage_Pool might be a special pool tuned for the fact that
> Size_In_Storage_Elements = 4 and Alignment = 4.  Allocate could
> add 4 to a known-aligned pointer, and ignore the
> Size_In_Storage_Elements and Alignment parameters.
>
> If Boo uses this pool for something other than Integer,
> it might not work.

Right. And it turns out that some commonly used compilers actually do use
different pools in different circumstances. (I think the mechanism had to do
with the nesting level of the access type declaration; I recall that we
discussed it in detail.)

The net effect is that in some existing implementations, there is no general
pool. It didn't make much sense to force them to change to a more general
model that could introduce storage leaks in existing programs, and thus
there is (still) no name for the standard pool.

                          Randy.


> However, I see nothing wrong with having a predefined operation that
> returns a suitable pool.
>
> - Bob

Re: Ada containers and custom allocators

[Robert A Duff]

"Randy Brukardt" <randy@rrsoftware.com> writes:

> Yes, of course. It could be used for performance monitoring as well. But I
> wouldn't characterize it as "many" interesting optimizations, it's more like
> a few interesting things. But it isn't valuable enough to force every user
> of a container to define a storage pool (since there is no name for a
> standard storage pool).

That seems easy enough to fix.  Simply have a predefined function:

    type Storage_Pool_Pointer is access all Root_Storage_Pool'Class;
    function Default_Storage_Pool return Storage_Pool_Pointer;

and use that for the default in the generic.

Default_Storage_Pool must be general enough to support any size.
There's no requirement that this be the same pool used by
default for misc access types.


>... And we needed to keep the number of standard
> containers manageable.

I suppose, but we weren't shy about writing macros in English -- see for
example package Float_Text_IO.  It would take one paragraph in the RM
to double the number of container packages by having versions with
a Pool parameter.  Pretty ugly, but there's precedent.

>> [...]
>> > (or, the
>> > storage pool passed would have to be completely general, allowing any
> size
>> > allocation, which would eliminate the vast majority of interesting
> things
>> > that you can do with storage pools).
>>
>> There are ways to overcome this problem, at least for some container
>> types. Node-based containers could use fixed-size allocators, but of
>> course it is the container which would then instantiate the allocator
>> with the proper node size. It was possible in C++.
>
> Only if you put severe limits on the implementations. For one thing, you
> would need to know the fixed node size in the storage pool in order to take
> any realistic advantage of it, but you couldn't ask the container's
> implementation for that size since you'd have to pass the storage pool to
> the instance. The only practical way to do that is to *require* a particular
> node layout. We might as well just standardize the source code of the
> container body in that case.
>
> Moreover, there is no requirement in Ada that objects be laid out
> continuously.

Perhaps there should be!

But anyway, given this fact, user-defined storage pools need to be fully
general (accept any size), or else depend on details of the Ada
implementation.  This is not specific to containers.

>...Janus/Ada will often make several allocator calls when
> allocating parts of an object, and those calls will all be different sizes.
> That's especially true inside of a generic body, where essentially
> everything that depends on a formal type is of an unknown size and thus has
> to be allocated separately. Even if you had the source code of the body, it
> probably would make different calls to Storage_Pool.Allocate on Janus/Ada
> and on GNAT.
>
> We'd also have to define what operations can calls the allocators.

I don't see why.

> Currently, there are no such restrictions on the containers implementation.
>
> Also, of course, it would only work for a couple of the containers. All of
> the hashed forms also are going to allocate the hash table, so there are
> going to be odd-size allocations (more than just nodes). And the vectors are
> likely to allocate chunks of various sizes.

It can work -- you just can't take advantage of (say) fixed sized
chunks.  I guess what you're saying is that that defeats the main
purpose!

> The net effect is that this is not possible to define (or use) in any
> useful, portable way. (If you're willing to stick to a single vendor, then
> it is more possible, but that of course has nothing to do with the
> standard.) Combined with the inability to name the standard storage pool,
> there isn't much point in doing this for the primary containers.
>
> The basic idea of the containers was to define a specification, and allow
> implementers to innovate on the implementations. (They don't even have to be
> in Ada.) The extra specification required to allow passing in a storage pool
> would seriously reduce these possibilities.
>
> The bounded forms seem to allow even better control over dynamic allocation
> (by not having any in the common case, although that surely wouldn't be true
> for Janus/Ada), are much easier to use (don't have to write a storage pool),
> and would work for the high-intergrity types that cannot allow an allocator
> near their program. Thus, they're the first focus of work. There are a lot
> of other ideas, but I can't say what if anything will come of them.

- Bob

Re: Ada containers and custom allocators

[Randy Brukardt]

"Robert A Duff" <bobduff@shell01.TheWorld.com> wrote in message
news:wcclk6zc91o.fsf@shell01.TheWorld.com...
> "Randy Brukardt" <randy@rrsoftware.com> writes:
>
> > Yes, of course. It could be used for performance monitoring as well. But
I
> > wouldn't characterize it as "many" interesting optimizations, it's more
like
> > a few interesting things. But it isn't valuable enough to force every
user
> > of a container to define a storage pool (since there is no name for a
> > standard storage pool).
>
> That seems easy enough to fix.  Simply have a predefined function:
>
>     type Storage_Pool_Pointer is access all Root_Storage_Pool'Class;
>     function Default_Storage_Pool return Storage_Pool_Pointer;
>
> and use that for the default in the generic.
>
> Default_Storage_Pool must be general enough to support any size.
> There's no requirement that this be the same pool used by
> default for misc access types.

Maybe, but that could be a substantially worse pool on some implementations
than used for normal access types. So I'm unsure if that is a good idea.

> >... And we needed to keep the number of standard
> > containers manageable.
>
> I suppose, but we weren't shy about writing macros in English -- see for
> example package Float_Text_IO.  It would take one paragraph in the RM
> to double the number of container packages by having versions with
> a Pool parameter.  Pretty ugly, but there's precedent.

OK, but only if you are willing to leave absolutely everything about how the
pool is used implementation-defined. At which point, I have to wonder what
the point is: you couldn't do anything at all portably.

Otherwise, you're going to have to have wording about where user-defined
pool operations can be called, what happens to the exceptions that they
propagate, and possibly other issues that I haven't thought about yet. This
isn't going to be a single sentence change -- maybe more like the magnitude
of "Wide String Handling" (A.4.7).

...
> > Moreover, there is no requirement in Ada that objects be laid out
> > continuously.
>
> Perhaps there should be!

Over my dead body. A serious attempt to propose that would get very, very
nasty.

> But anyway, given this fact, user-defined storage pools need to be fully
> general (accept any size), or else depend on details of the Ada
> implementation.  This is not specific to containers.

Correct. But it means that little useful can be done with custom pools on
the predefined containers libraries. The needed generality prevents using
any optimizations in the pool, so it pretty much limits you to tracking the
allocations and deallocations.

...
> > We'd also have to define what operations can calls the allocators.
>
> I don't see why.

The current containers library spends quite a bit of effort defining the
places where objects can be destroyed (that is, where Finalize can be
called). Admittedly, a lot of that effort is to say that it isn't defined
closely. But one thing we don't do is allow random calls to reading
operations to call Finalize. Similarly, we always have wording to define
what and where exceptions are propagated.

If we allow user storage pools, we'd need the definitions of where those
operations can be called (hopefully not in operations that merely read and
return something!) and wording to say that the exceptions are propagated.
And probably other things as well.

> > Currently, there are no such restrictions on the containers
implementation.
> >
> > Also, of course, it would only work for a couple of the containers. All
of
> > the hashed forms also are going to allocate the hash table, so there are
> > going to be odd-size allocations (more than just nodes). And the vectors
are
> > likely to allocate chunks of various sizes.
>
> It can work -- you just can't take advantage of (say) fixed sized
> chunks.  I guess what you're saying is that that defeats the main
> purpose!

The OP claimed that fixed-size allocators could be used, and my lengthy
reply was intended to rebut that. Surely, they can't be used portably or
generally. It is true that you probably could do it on a specific
implementation for a specific element type (it would even work on Janus/Ada
that way). But as soon as you move to a different compiler (or even
potentially an update for the same compiler with an "improved" containers
library), it will no longer work. That might make sense to do for debugging,
but it can't be used for anything long term.

All of which begs the question of whether it is worth the work to
accomplish.

                                  Randy.



Of

Re: Ada containers and custom allocators

[Maciej Sobczak]

On 11 Sty, 06:00, "Randy Brukardt" <ra...@rrsoftware.com> wrote:

> > It can work -- you just can't take advantage of (say) fixed sized
> > chunks.  I guess what you're saying is that that defeats the main
> > purpose!
>
> The OP claimed that fixed-size allocators could be used, and my lengthy
> reply was intended to rebut that. Surely, they can't be used portably or
> generally.

In Ada, you mean?

In C++ this works by passing the allocator parameter to the template
container class, which in turn can re-bind the allocator to use
whatever size is used internally. This means that the fixed-size
allocator cannot be prepared for only a given allocation size, but
that does not seem to be a problem in practice. The whole point of
using a fixed-size allocator is to enable some specialized allocation
scheme (like bitmap-based management of free blocks) and this is
independent of any given size. In other words, the allocator should be
ready to work with any size, but this is fixed once by the container
itself.
You might say that there is a limitation in that container will have
to use nodes of fixed size, but this, again does not seem to be a
problem - I have never seen a list (for example) that internally uses
nodes of varying sizes.

This works in C++ and gives spectacular performance improvements. It's
a pity Ada does not provide anything in this area.

--
Maciej Sobczak * www.msobczak.com * www.inspirel.com

Re: Ada containers and custom allocators

[Robert A Duff]

Maciej Sobczak <see.my.homepage@gmail.com> writes:

> This works in C++ and gives spectacular performance improvements. It's
> a pity Ada does not provide anything in this area.

Why does it give spectacular performance improvements?
Doesn't this indicate that the default storage management
is needlessly inefficient?

- Bob

Re: Ada containers and custom allocators

[Maciej Sobczak]

On 11 Sty, 23:41, Robert A Duff <bobd...@shell01.TheWorld.com> wrote:

> Why does it give spectacular performance improvements?
> Doesn't this indicate that the default storage management
> is needlessly inefficient?

Default storage management is always needlessly inefficient, because
it is general and cannot benefit from any additional knowledge about
what will be allocated. Every single bit of additional knowledge is an
improvement opportunity in some area. Fixed-size allocators can use
faster algorithms than general allocators.

Another axis of improvement with custom allocators is thread-safety.
The global allocator cannot assume anything about threading and has to
be defensive in relation to threads, which means that it has to
proactively synchronize everything, always - just in case. Now imagine
you have a container and you know by the design of your system that
this given container will be always used in the context of a single
thread. Why not give it a separate allocator that benefits from this
knowledge (ie. operates on a separate, non-synchronized pool)? On
multicore or multiprocessor systems unnecessary synchronization
(memory barriers and such) is *VERY* expensive and can kill
performance. Why not make things easier for the hardware by reducing
the number of unnecessary membars?
Here, again - every single bit of additional knowledge is an
improvement opportunity.

Related note: it was repeated many times on this groups that Ada is
particularly appropriate for the coming multicore era. I'm not so sure
about this and the above issue is one of the question marks. Forget
about performance if you cannot partition allocation schemes for
containers by threads. This will get only worse as the number of cores
in CPUs increases.

--
Maciej Sobczak * www.msobczak.com * www.inspirel.com

Re: Ada containers and custom allocators

[Robert A Duff]

Maciej Sobczak <see.my.homepage@gmail.com> writes:

> On 11 Sty, 23:41, Robert A Duff <bobd...@shell01.TheWorld.com> wrote:
>
>> Why does it give spectacular performance improvements?
>> Doesn't this indicate that the default storage management
>> is needlessly inefficient?
>
> Default storage management is always needlessly inefficient, because
> it is general and cannot benefit from any additional knowledge about
> what will be allocated. Every single bit of additional knowledge is an
> improvement opportunity in some area. Fixed-size allocators can use
> faster algorithms than general allocators.

True, but the container implementation knows whether it is allocating
fixed-size objects.

> Another axis of improvement with custom allocators is thread-safety.

Good point.  I'd like to have a language where the compiler can tell
which objects are shared by more than one thread.  But that's not Ada
(nor is it C++).

> The global allocator cannot assume anything about threading and has to
> be defensive in relation to threads, which means that it has to
> proactively synchronize everything, always - just in case.

You don't necessarily have to lock every allocation and deallocation.
There are more efficient schemes, but you're right -- there is a
cost.

- Bob

Re: Ada containers and custom allocators

[Jeffrey R. Carter]

Maciej Sobczak wrote:
> On 8 Sty, 02:54, "Randy Brukardt" <ra...@rrsoftware.com> wrote:
> 
>>> Is it possible to set up a custom allocator for use with any given Ada
>>> container?
>> If you mean an allocator for the private data of the container (which
>> includes all of the elements and is the bulk of the container), the answer
>> is no.
> 
> This is exactly what I mean. It is not uncommon for a program to have
> a majority of its dynamic memory managed by containers.

Actually, Brukardt's reply is technically incorrect. The containers are tagged; 
you can derive from them and override the appropriate operations to obtain the 
behavior you require. Of course, this means you either have to know the 
internals of the container in question, or you have to override all the 
operations, effectively writing your own container.

Which brings us to

>> The standard Ada containers do not provide any mechanism to control
>> how/were the container allocates memory.
> 
> This limitation prevents programmers from doing many interesting
> optimizations. Even if we put performance issues aside, I might want
> to control the memory allocation for reliability.

The standard library is necessarily intended for general use, not optimized for 
any specific requirements. If it doesn't meet your specific requirements, then 
you should consider custom components that do.

-- 
Jeff Carter
"Gentlemen, you can't fight in here. This is the War Room!"
Dr. Strangelove
30