Finding out minimal allocation unit

Finding out minimal allocation unit

[Stefan Bellon]

Hi,

In a few places we are using long lists of items. Those items mostly
consist of just a pointer or a record of two pointers. We need cheap
insertions and deletions of elements in those lists, therefore we
indeed used linked lists and no array solution.

However we found out that the minimum allocation unit for a record of 8
bytes is much more (around 32 bytes?), so each list cell loses lots of
memory. Therefore we created some kind of "B-list" where each cell
contains more than one item in an array in order to make best use of
the space that is allocated anyway.

However tests have shown that 32 bytes does not seem to be the mimimum
allocation unit. If this was the case, then our solution should in no
case be worse than a simple linked list, but there are cases where it
is, indicating that 32 bytes is not the minimal allocation unit.

Is there a reliable way of finding out the smallest allocation unit?

Greetings,
Stefan

-- 
Stefan Bellon

Re: Finding out minimal allocation unit

[Georg Bauhaus]

On Tue, 2007-04-03 at 14:43 +0200, Stefan Bellon wrote:

> Is there a reliable way of finding out the smallest allocation unit?

FWIW,

 type LP is -- new ... with
            record
                forward: access LP;
                backward: access LP;
            end record;
        for LP'Size use 63;

should make the compiler complain when 63 bits aren't enough.

Re: Finding out minimal allocation unit

[Stefan Bellon]

Georg Bauhaus wrote:

> On Tue, 2007-04-03 at 14:43 +0200, Stefan Bellon wrote:
> 
> > Is there a reliable way of finding out the smallest allocation unit?
> 
>  type LP is -- new ... with
>             record
>                 forward: access LP;
>                 backward: access LP;
>             end record;
>         for LP'Size use 63;
> 
> should make the compiler complain when 63 bits aren't enough.

Ok, but when wanting to calculate it in a generic, it gets lots harder.
At present we are using something like this:

generic

   type Item_Type is private;

   with function Equal
     (X, Y : in Item_Type)
     return Boolean
     is "=";

   Min_Elements_In_Cell : in Positive := 1;
   --  The minimum amount of Item_Type elements that should be in
   --  one array cell of the B-List.

   Min_Allocation_Size  : in Positive := 32 * 8;  --  32 Bytes
   --  Minimum size of a list cell.  List cells are allocated in powers of
   --  two and so that at least Min_Elements_In_Cell of type Item_Type
   --  fit into one cell.

package BLists is

   -- ...

private

   type Cell;

   type List is access Cell;

   function Power2_Ceiling
     (N : in Natural)
     return Natural;
   --  Calculates the next larger power-of-two with regard to N.

   Misc_Data_In_Bits : constant Natural := Natural'Size + List'Size;
   --  Size of Item_Type-independent data in the cell record.

   type Dummy_Array is array (Natural range 1 .. 1) of Item_Type;
   Item_Size : constant Natural := Dummy_Array'Component_Size;
   --  Use the dummy array in order to find out the size the Item_Type
   --  takes in an array in order to calculate the correct size below.

   Cell_Size_In_Bits : constant Natural := Natural'Max
     (Min_Allocation_Size,
      Power2_Ceiling
        (Misc_Data_In_Bits + Min_Elements_In_Cell * Item_Size));
   --  Calculated cell size to best fit an allocation unit.

   Array_Size : constant Natural
     := (Cell_Size_In_Bits - Misc_Data_In_Bits) / Item_Size;
   --  Amount of Item_Types fitting into one cell.

   type Item_Array is array (Natural range 1 .. Array_Size)
     of Item_Type;

   type Cell is record
      First_Used : Natural;
      Next       : List;
      Elements   : Item_Array;
   end record;
   --  Fill the array from 'Last down to 'First and First_Used denotes
   --  the first used entry, this results in faster prepending.

end BLists;

But this way your suggestion does not work anymore as the 'Size
attribute must be static.

-- 
Stefan Bellon

Re: Finding out minimal allocation unit

[Martin Krischik]

Georg Bauhaus schrieb:
> On Tue, 2007-04-03 at 14:43 +0200, Stefan Bellon wrote:
> 
>> Is there a reliable way of finding out the smallest allocation unit?
> 
> FWIW,
> 
>  type LP is -- new ... with
>             record
>                 forward: access LP;
>                 backward: access LP;
>             end record;
>         for LP'Size use 63;
> 
> should make the compiler complain when 63 bits aren't enough.
> 

I think you misunderstood the OP: if you use new to create an object 
inside an storage pool then additional housekeeping informations are 
added to object.

Also if the storage pool uses C malloc (as GNAT does) then the object 
need to universally aligned. C - unlike Ada - demands that the pointer 
returned need to suitable for all kind of data.

So I believe the OP wanted to know how to find out how much memory for 
"new"ed object is allocated in total in order to know if extra 
optimisation is needed.

Martin

Re: Finding out minimal allocation unit

[Stefan Bellon]

Martin Krischik wrote:

> So I believe the OP wanted to know how to find out how much memory
> for "new"ed object is allocated in total in order to know if extra 
> optimisation is needed.

Exactly. :-)

-- 
Stefan Bellon

Re: Finding out minimal allocation unit

[Robert A Duff]

Stefan Bellon <sbellon@sbellon.de> writes:

> Is there a reliable way of finding out the smallest allocation unit?

You could print out the addresses of allocated objects,
and guess what's going on.  If you have access to the source,
you could read it.

If the underlying allocator is malloc(), there will typically be a
couple of words or so of extra space wasted per object, primarily due
to design flaws in the C language.  If you don't like that, then you can
write your own allocator -- look up "storage pools".

- Bob

Re: Finding out minimal allocation unit

[Larry Kilgallen]

In article <1175606570.4684.11.camel@localhost>, Georg Bauhaus <bauhaus@futureapps.de> writes:
> On Tue, 2007-04-03 at 14:43 +0200, Stefan Bellon wrote:
> 
>> Is there a reliable way of finding out the smallest allocation unit?
> 
> FWIW,
> 
>  type LP is -- new ... with
>             record
>                 forward: access LP;
>                 backward: access LP;
>             end record;
>         for LP'Size use 63;
> 
> should make the compiler complain when 63 bits aren't enough.

Doesn't that deal with the size of an access variable, rather than
the smallest allocation unit ?

Re: Finding out minimal allocation unit

[Markus E Leypold]

Stefan Bellon <sbellon@sbellon.de> writes:

> Martin Krischik wrote:
>
>> So I believe the OP wanted to know how to find out how much memory
>> for "new"ed object is allocated in total in order to know if extra 
>> optimisation is needed.
>
> Exactly. :-)


I'm only guessing, but here is my approach for GNAT: GNAT is AFAIK
linked against libc (at least on Unix). On linux that is glibc, which
provides methods to catch/trace malloc() requests. My suggestion is
that you do that and look which sizes are actually requested from
malloc(). 

Another option: Allocate objects in a loop and observe when sbrk()
occurs.

Regards -- Markus

Re: Finding out minimal allocation unit

[Dmitry A. Kazakov]

On Tue, 3 Apr 2007 14:43:50 +0200, Stefan Bellon wrote:

> In a few places we are using long lists of items. Those items mostly
> consist of just a pointer or a record of two pointers. We need cheap
> insertions and deletions of elements in those lists, therefore we
> indeed used linked lists and no array solution.

If size is an issue, you can also use indices instead of access types.
Provided that all items have same size. Then you split your list of records
into lists of fields.

type Index is mod ...;

type Item_List is array (Index) of Item;
pragma Pack (Item_List);

type Previous is array (Index) of Index; 
pragma Pack (Previous);

type Next is array (Index) of Index; 
pragma Pack (Next);

First_Free  : Index := ...;
   -- The list of free items (empty)
First_In : Index := ...;
   -- The list (empty)
Non_Yet_Visited : Index := ...;
   -- To avoid initialization of the list of free items

You can avoid memory allocation in advance if you segment the arrays above
and split Index into (Segment_No, In_Segment) pair.

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

Re: Finding out minimal allocation unit

[Randy Brukardt]

"Martin Krischik" <krischik@users.sourceforge.net> wrote in message
news:461257ea$1@news.post.ch...
...
> So I believe the OP wanted to know how to find out how much memory for
> "new"ed object is allocated in total in order to know if extra
> optimisation is needed.

But that isn't really a meaningful question. It clearly depends on the
storage pool, and if the storage pool comes from somewhere else, it may even
depend on the OS version you are running. For instance, the standard storage
pool in Janus/Ada uses a standard Windows heap. Those exhibit vastly
different behavior on Windows 95 than Windows 2000, and somewhat different
on almost every version of Windows.

Rule of thumb: if the behavior of the standard storage pool actually makes a
difference in your application, then don't use it! Write your own storage
pool that has the behavior you need. It's relatively easy to do, especially
if you have fixed size elements. And then you can effectively use an array
to allocate elements and still have cheap insertion and deletion and
reordering.

                              Randy.

Re: Finding out minimal allocation unit

[Robert A Duff]

Markus E Leypold
<development-2006-8ecbb5cc8aREMOVETHIS@ANDTHATm-e-leypold.de> writes:

> Stefan Bellon <sbellon@sbellon.de> writes:
>
>> Martin Krischik wrote:
>>
>>> So I believe the OP wanted to know how to find out how much memory
>>> for "new"ed object is allocated in total in order to know if extra 
>>> optimisation is needed.
>>
>> Exactly. :-)
>
>
> I'm only guessing, but here is my approach for GNAT: GNAT is AFAIK
> linked against libc (at least on Unix). On linux that is glibc, which
> provides methods to catch/trace malloc() requests. My suggestion is
> that you do that and look which sizes are actually requested from
> malloc(). 

That won't quite give the right answer, because malloc() adds a couple
of words or so to what was requested.

- Bob

Re: Finding out minimal allocation unit

[Stefan Bellon]

Randy Brukardt wrote:

> But that isn't really a meaningful question. It clearly depends on
> the storage pool, and if the storage pool comes from somewhere else,
> it may even depend on the OS version you are running. For instance,
> the standard storage pool in Janus/Ada uses a standard Windows heap.
> Those exhibit vastly different behavior on Windows 95 than Windows
> 2000, and somewhat different on almost every version of Windows.

I don't agree that it isn't a meaningful question because of that.
Quite the contrary. _Because_ we realize that there are differences,
we'd like to find out the allocation strategy in order to optimize for
that.

> Rule of thumb: if the behavior of the standard storage pool actually
> makes a difference in your application, then don't use it!

Ok, this is an alternative to think about.

> Write your own storage pool that has the behavior you need. It's
> relatively easy to do, especially if you have fixed size elements.
> And then you can effectively use an array to allocate elements and
> still have cheap insertion and deletion and reordering.

I'm a bit unclear about how to do it. Do I implement the Allocate using
the standard storage pool (i.e. using 'new') or do I interface it
directly to the underlying C library (i.e. using 'malloc')? In both
cases I still have the same problem as above.

Are there examples of such a storage pool implementation around?

-- 
Stefan Bellon

Re: Finding out minimal allocation unit

[Martin Krischik]

Stefan Bellon wrote:

>> Write your own storage pool that has the behavior you need. It's
>> relatively easy to do, especially if you have fixed size elements.
>> And then you can effectively use an array to allocate elements and
>> still have cheap insertion and deletion and reordering.
> 
> I'm a bit unclear about how to do it. Do I implement the Allocate using
> the standard storage pool (i.e. using 'new') or do I interface it
> directly to the underlying C library (i.e. using 'malloc')? In both
> cases I still have the same problem as above.

First we need to know which platform you are using (compiler/OS).

Then: how a storrage pool get's it memory is up to the pool designer.

In your case you could allocate a large chuck of memory strait from the OS
and then sub-allocate it using an algorithm optimised for your needs.

You spoke of storing data inside an array - which suggest all elements have
the same size. Then you optimised storrage pool won't need keep track of
the allocation size - something a universal pool needs to do.

Martin
-- 
mailto://krischik@users.sourceforge.net
Ada programming at: http://ada.krischik.com

Re: Finding out minimal allocation unit

[Markus E Leypold]

Robert A Duff <bobduff@shell01.TheWorld.com> writes:

> Markus E Leypold
> <development-2006-8ecbb5cc8aREMOVETHIS@ANDTHATm-e-leypold.de> writes:
>
>> Stefan Bellon <sbellon@sbellon.de> writes:
>>
>>> Martin Krischik wrote:
>>>
>>>> So I believe the OP wanted to know how to find out how much memory
>>>> for "new"ed object is allocated in total in order to know if extra 
>>>> optimisation is needed.
>>>
>>> Exactly. :-)
>>
>>
>> I'm only guessing, but here is my approach for GNAT: GNAT is AFAIK
>> linked against libc (at least on Unix). On linux that is glibc, which
>> provides methods to catch/trace malloc() requests. My suggestion is
>> that you do that and look which sizes are actually requested from
>> malloc(). 
>
> That won't quite give the right answer, because malloc() adds a couple
> of words or so to what was requested.

And I thought it would exactly be the extra padding the OP was
interested in?

Regards -- Markus

Re: Finding out minimal allocation unit

[Robert A Duff]

Stefan Bellon <sbellon@sbellon.de> writes:

> Randy Brukardt wrote:
>> Write your own storage pool that has the behavior you need. It's
>> relatively easy to do, especially if you have fixed size elements.
>> And then you can effectively use an array to allocate elements and
>> still have cheap insertion and deletion and reordering.
>
> I'm a bit unclear about how to do it. Do I implement the Allocate using
> the standard storage pool (i.e. using 'new') or do I interface it
> directly to the underlying C library (i.e. using 'malloc')? In both
> cases I still have the same problem as above.

There are many ways to do it.  In your case, you have a large number of
small objects.  In that case, it would make sense to allocate large
chunks of memory (possibly using "new"), and then have Allocate chop
them up into small pieces on request.  If all objects are the same size,
then Deallocate can put things on a single free list.  If you have a
small number of different small sizes, you can have one free list per
size.

The chunks might be of type Storage_Array, or might be an
array-of-<your-type>, depending on what's convenient.

This is low level programming.  If you mess up, you will have nasty bugs.

> Are there examples of such a storage pool implementation around?

I don't know.  There should be.  If I ever get enough spare time,
I might create a library of useful pools, if such a thing doesn't
already exist.

- Bob

Re: Finding out minimal allocation unit

[Stefan Bellon]

Markus E Leypold wrote:

> And I thought it would exactly be the extra padding the OP was
> interested in?

Yes, basically I'm interested in the padding which is inserted and
wasted and which could be used without resulting in a larger allocated
memory chunk.

So, instead of doing:

   type Cell1;

   type List is access all Cell1;

   type Cell1 is record
      Next : List;
      Item : Item_Type;
   end record;

We would like to do:

   type Cell2 is record
      Next  : List;
      Used  : Natural;
      Items : array (1 .. N) of Item_Type;
   end record;

Where N is chosen in a way that N is maximized without resulting in the
whole Cell to require the next larger allocation size.

Of course, there is a problem when Cell1'Size (or Cell1'Object_Size?)
is _exactly_ an allocation size as the Cell2 has the necessary Used
element which takes space and thus forces the next larger allocation
unit. But then, N is at least 2 which makes the whole list not worse
than a list of Cell1.

The whole List/Cell stuff is inside a generic and Item_Type is the type
the generic is instantiated with.

So, the question is, how to accurately find out the allocation size for
Cell1 and Cell2 respectively in order to calculate the best N.

In theory it should be possible to create a list of Cell2 which is no
worse in memory consumption than a list of Cell1, but at present we see
quite some memory penalty and figured out that this is because GNAT
(the compiler we use) allocates larger memory chunks than we calculated
using the provided attributes ('Size, 'Object_Size, 'Component'Size,
...).

The main two problems seem to be that we a) don't know the memory
allocation strategy and b) that GNAT's record/array layout seems to be
different than we assume.

Let's look at some data which is puzzling us:

   type Cell is record
      Item : Ada.Strings.Unbounded.Unbounded_String;
   end record;

   type Items is array (1 .. 1)
     of Ada.Strings.Unbounded.Unbounded_String;

Then, the following is the result of querying the mentioned attributes:

Cell'Size: 352
Cell'Object_Size: 352
Items'Component_Size: 192

So, when used in an array, an unbounded string only needs 24 bytes, and
when used in an record, it needs 44 bytes. Now, when adding another
unbounded string to a record and then building an array of that:

   type CellX is record
      Item1, Item2 : Ada.Strings.Unbounded.Unbounded_String;
   end record;

   type ItemsX is array (1 .. 1) of CellX;

Then the following is the result:

CellX'Size: 544
CellX'Object_Size: 544
ItemsX'Component_Size: 544

Where 544 are 68 bytes = 24 bytes + 44 bytes.

I am really not sure how to explain this ... any help is very welcome!

-- 
Stefan Bellon

Re: Finding out minimal allocation unit

[Stefan Bellon]

Martin Krischik wrote:

> First we need to know which platform you are using (compiler/OS).

GNAT on GNU/Linux, Windows and Solaris, where the memory allocation
should work well on all three of them (but using separates or package
Naming in a project file to supply different algorithms for the
allocation strategy is no problem).

> Then: how a storrage pool get's it memory is up to the pool designer.

> In your case you could allocate a large chuck of memory strait from
> the OS and then sub-allocate it using an algorithm optimised for your
> needs.

When using storage pools, can the storage pools be dynamically resized,
or is a storage pool, once created, fixed in its size? The latter would
rule out using storage pools since we do not know in advance how many
data we need to store, just the "Item_Type" is known when instantiating
the data structure, so it's size is known (provided we can trust the
'Size, 'Object_Size, and 'Component_Size attributes).

-- 
Stefan Bellon

Re: Finding out minimal allocation unit

[Stefan Bellon]

Robert A Duff wrote:

> There are many ways to do it.  In your case, you have a large number
> of small objects.  In that case, it would make sense to allocate
> large chunks of memory (possibly using "new"), and then have Allocate
> chop them up into small pieces on request.

This sounds good, provided that

a) we can resize an already existing storage pool to increase the
memory inside it, and

b) we can really get at the size GNAT uses for each of the items (see
my other posting with the unbounded string example).

-- 
Stefan Bellon

Re: Finding out minimal allocation unit

[Randy Brukardt]

"Stefan Bellon" <sbellon@sbellon.de> wrote in message
news:4ecee3fe5esbellon@sbellon.de...
> Robert A Duff wrote:
>
> > There are many ways to do it.  In your case, you have a large number
> > of small objects.  In that case, it would make sense to allocate
> > large chunks of memory (possibly using "new"), and then have Allocate
> > chop them up into small pieces on request.
>
> This sounds good, provided that
>
> a) we can resize an already existing storage pool to increase the
> memory inside it, and

It's whatever you want it to be! A storage pool is just a container that is
automatically called when you allocate or deallocate memory. There of course
are the predefined ones, but you can provide your own about which you define
*all* of the details.

In your case, I'd probably implement the pool as a linked list of arrays
that hold enough elements for some large size (at least 4K for Windows,
can't say for Linux). And then I'd manage them with a free chain and a pass
through for unusual sizes (see below). You could even set the item size as a
discriminant of the pool type, possibly using the attribute designed for
this purpose ('Max_Size_in_Storage_Elements).

> b) we can really get at the size GNAT uses for each of the items (see
> my other posting with the unbounded string example).

I don't know about that for certain (I don't use GNAT that much), but I'd be
fairly surprised if it wasn't. To some extent it is irrelevant, since the
size to allocate is passed into Allocate, and it is easy enough to have
unanticipated sizes just allocate from the regular pool (i.e. use New).
Indeed, I have a pool whose job was to find the source of dangling pointers,
and all it did was save the pointers and clobber memory on deallocation; the
actual allocation was a pure pass-through to the standard pool (using New
and Unchecked_Deallocation).

I suggest reading up on storage pools in whatever you can find. As Bob said,
this is low-level programming; Ada won't be much help if you screw up -- if
you give non-existent memory to Ada, she will screw up just like those other
language some of us love to hate. It's likely that most of the pools that
have been written are specific to some OS or compiler, which may explain why
there aren't many out there. (Mine are all specific to Janus/Ada; not much
use to you.) But they can be fairly generic (allocating large chunks from
the regular heap), and reasonably well-checked: you don't have to write them
solely with pointer arithmetic.

                             Randy.

Re: Finding out minimal allocation unit

[Randy Brukardt]

"Stefan Bellon" <sbellon@sbellon.de> wrote in message
news:4ecee347d7sbellon@sbellon.de...
> Markus E Leypold wrote:
>
> > And I thought it would exactly be the extra padding the OP was
> > interested in?
>
> Yes, basically I'm interested in the padding which is inserted and
> wasted and which could be used without resulting in a larger allocated
> memory chunk.
>
> So, instead of doing:
>
>    type Cell1;
>
>    type List is access all Cell1;
>
>    type Cell1 is record
>       Next : List;
>       Item : Item_Type;
>    end record;
>
> We would like to do:
>
>    type Cell2 is record
>       Next  : List;
>       Used  : Natural;
>       Items : array (1 .. N) of Item_Type;
>    end record;
>
> Where N is chosen in a way that N is maximized without resulting in the
> whole Cell to require the next larger allocation size.

Right, but that obscures your algorithm and makes it harder to maintain.
It's better to write a storage pool that does the blocking, and does it
behind the scenes. (Of course, if the overhead of "Next" is contributing to
the problem, you might not have any choice.)

But, honestly, I don't see why you're so concerned about getting the
blocking factor exactly right. Just make it big enough so you're always
allocating at least 256 bytes at a time, and relax. Unless you have a huge
number of these structures, the possible waste of a couple hundred bytes per
list item isn't going to make much difference. And if they're expandable
anyway, you're probably going to be filling them up. Remember, the actual OS
memory allocator on Windows allocates in 64K chunks -- I doubt you want to
use *that* size for blocking!

So, in summary, if the insertion/deletion issues are really significant,
then use a custom storage pool, and don't mess with the top-level algorithm.
And if they're not, just allocate decent sized blocks and don't worry too
much about the waste - it's inevitable unless you write your own storage
pool (tuning as you are trying to do will only work on a single compiler
version/target operating system version; any change to either is likely to
change something - everyone is forever fiddling with their heap
implementations to improve something or other).

                                  Randy.

Re: Finding out minimal allocation unit

[Stefan Bellon]

Randy Brukardt wrote:

> Right, but that obscures your algorithm and makes it harder to
> maintain. It's better to write a storage pool that does the blocking,
> and does it behind the scenes. (Of course, if the overhead of "Next"
> is contributing to the problem, you might not have any choice.)

Ok, will have a close look at storage pools.

> But, honestly, I don't see why you're so concerned about getting the
> blocking factor exactly right. Just make it big enough so you're
> always allocating at least 256 bytes at a time, and relax. Unless you
> have a huge number of these structures, the possible waste of a
> couple hundred bytes per list item isn't going to make much
> difference.

Just an example, in one case of our tools, I replaced the simple linked
list with the above mentioned "b-list" and memory usage went down from
2500 MB zu 1900 MB. That's a saving of 600 MB. So, yes, we are
concerned about efficiency in memory storage as we come close to the 3
GB limit of addressable user space on 32-bit machines.

> So, in summary, if the insertion/deletion issues are really
> significant, then use a custom storage pool, and don't mess with the
> top-level algorithm.

Will do. Thanks for all the help and ideas!

-- 
Stefan Bellon

Re: Finding out minimal allocation unit

[Stefan Bellon]

Randy Brukardt wrote:
> "Stefan Bellon" <sbellon@sbellon.de> wrote in message

> > a) we can resize an already existing storage pool to increase the
> > memory inside it, and

> It's whatever you want it to be! A storage pool is just a container
> that is automatically called when you allocate or deallocate memory.
> There of course are the predefined ones, but you can provide your own
> about which you define *all* of the details.

Ok, that sounds gook.

> In your case, I'd probably implement the pool as a linked list of
> arrays that hold enough elements for some large size (at least 4K for
> Windows, can't say for Linux). And then I'd manage them with a free
> chain and a pass through for unusual sizes (see below). You could
> even set the item size as a discriminant of the pool type, possibly
> using the attribute designed for this purpose
> ('Max_Size_in_Storage_Elements).

Well, our idea was to build a generic storage pool which can handle
only memory chunks of one size. And the generic storage pool is
instantiated with that size as generic parameter. So that each data
structure instance (be it a list, a tree, hash table, ...) has its own
storage pool with the exact Item_Type'Size instantiated.

> Indeed, I have a pool whose job was to find the source of dangling
> pointers, and all it did was save the pointers and clobber memory on
> deallocation; the actual allocation was a pure pass-through to the
> standard pool (using New and Unchecked_Deallocation).

Cool idea!

> I suggest reading up on storage pools in whatever you can find.

Ok, thanks for all the help and ideas so far!

-- 
Stefan Bellon

Re: Finding out minimal allocation unit

[Markus E Leypold]

Stefan Bellon <sbellon@sbellon.de> writes:

> Randy Brukardt wrote:
>
>> Right, but that obscures your algorithm and makes it harder to
>> maintain. It's better to write a storage pool that does the blocking,
>> and does it behind the scenes. (Of course, if the overhead of "Next"
>> is contributing to the problem, you might not have any choice.)
>
> Ok, will have a close look at storage pools.
>
>> But, honestly, I don't see why you're so concerned about getting the
>> blocking factor exactly right. Just make it big enough so you're
>> always allocating at least 256 bytes at a time, and relax. Unless you
>> have a huge number of these structures, the possible waste of a
>> couple hundred bytes per list item isn't going to make much
>> difference.
>
> Just an example, in one case of our tools, I replaced the simple linked
> list with the above mentioned "b-list" and memory usage went down from
> 2500 MB zu 1900 MB. That's a saving of 600 MB. So, yes, we are
> concerned about efficiency in memory storage as we come close to the 3
> GB limit of addressable user space on 32-bit machines.

Since memory allocation patterns are usually not completely
predictable, won't that mean, that (if don't allocated everything from
custom storage pools) the maximum allocation will have a certain
amount of statistical "jitter", i.e. will sometimes exceed the 3 GB
limit and your application will fail now and then --
that is, the application will be anreliable?

You would have to prove that 3GB is the absolute upper limit needed,
something really difficult to do when you don't controll ALL
allocation (as opposed to only this special list type).

Regards -- Markus

Re: Finding out minimal allocation unit

[Stephen Leake]

Stefan Bellon <sbellon@sbellon.de> writes:

> Are there examples of such a storage pool implementation around?

Here's the debug storage pool from SAL
(http://stephe-leake.org/ada/sal.html)

I wrote it to check for memory leaks in the SAL containers. It doesn't
resize the pool when it gets full, but you can add that using other
SAL containers :).

-- 
-- Stephe

--  Abstract:
--
--  A storage pool that keeps track of allocation and deallocation,
--  and allows queries. Used to verify storage management in container
--  tests. NOT task safe!
--
--  Copyright (C) 1997 - 1999, 2002 Stephen Leake.  All Rights Reserved.
--
--  This program is free software; you can redistribute it and/or
--  modify it under terms of the GNU General Public License as
--  published by the Free Software Foundation; either version 2, or
--  (at your option) any later version. This program is distributed in
--  the hope that it will be useful, but WITHOUT ANY WARRANTY; without
--  even the implied warranty of MERCHANTABILITY or FITNESS FOR A
--  PARTICULAR PURPOSE. See the GNU General Public License for more
--  details. You should have received a copy of the GNU General Public
--  License distributed with this program; see file COPYING. If not,
--  write to the Free Software Foundation, 59 Temple Place - Suite
--  330, Boston, MA 02111-1307, USA.

with System.Storage_Pools;
with System.Storage_Elements;
package Test_Storage_Pools is
   pragma Elaborate_Body; -- body depends on Ada.Text_IO;

   type String_Access_Constant_Type is access constant String;

   type Storage_Pool_Type
      (Pool_Size : System.Storage_Elements.Storage_Count;
       Name      : String_Access_Constant_Type) -- for debug messages
   is new System.Storage_Pools.Root_Storage_Pool with private;

   -----------
   --  Override Root_Storage_Pool operations

   procedure Allocate
      (Pool                     : in out Storage_Pool_Type;
       Storage_Address          :    out System.Address;
       Size_In_Storage_Elements : in     System.Storage_Elements.Storage_Count;
       Alignment                : in     System.Storage_Elements.Storage_Count);

   procedure Deallocate
      (Pool                     : in out Storage_Pool_Type;
       Storage_Address          : in     System.Address;
       Size_In_Storage_Elements : in     System.Storage_Elements.Storage_Count;
       Alignment                : in     System.Storage_Elements.Storage_Count);

   function Storage_Size (Pool : in Storage_Pool_Type) return System.Storage_Elements.Storage_Count;

   -----------
   --  New operations (alphabetical)

   function Allocate_Count (Pool : in Storage_Pool_Type) return Natural;
   --  Number of times Allocate has been called successfully.

   function Allocated_Elements (Pool : in Storage_Pool_Type) return Natural;
   --  Net allocated storage.

   procedure Check_Deallocated (Pool : in Storage_Pool_Type);
   --  If Allocated_Elements is not zero, print an error message and
   --  call Show_Storage.

   function Deallocate_Count (Pool : in Storage_Pool_Type) return Natural;
   --  Number of times Deallocate has been called.

   function Max_Allocated_Elements (Pool : in Storage_Pool_Type) return Natural;
   --  Max allocated storage, over lifetime of Pool.

   procedure Reset_Counts (Pool : in out Storage_Pool_Type);
   --  Reset Allocated and Deallocated counts to zero.

   procedure Set_Debug (Pool : in out Storage_Pool_Type; Debug : in Boolean);
   --  If Debug is True, Allocate, Deallocate, and Show_Storage print
   --  helpful messages to Standard_Output.

   procedure Show_Storage (Pool : in Storage_Pool_Type; Force_Debug : in Boolean := False);
   --  Print storage stats to Ada.Text_IO.Standard_Output, if
   --  Pool.Debug or Force_Debug is True.

private

   procedure Initialize (Pool : in out Storage_Pool_Type);

   type Block_Header_Type;
   type Block_Access_Type is access all Block_Header_Type;
   type Block_Header_Type is record
      Size : System.Storage_Elements.Storage_Count;
      Next : Block_Access_Type;
   end record;

   type Storage_Pool_Type
      (Pool_Size : System.Storage_Elements.Storage_Count;
       Name      : String_Access_Constant_Type)
   is new System.Storage_Pools.Root_Storage_Pool with
   record
      Debug                  : Boolean;
      Allocate_Count         : Natural;
      Deallocate_Count       : Natural;
      Allocated_Elements     : Natural;
      Max_Allocated_Elements : Natural;
      First_Free             : Block_Access_Type;
      Storage                : System.Storage_Elements.Storage_Array (1 .. Pool_Size);
      --  The first few elements of each free block contain the block
      --  header. Small requested blocks are padded up to at least the
      --  block header size. All blocks have alignment 8, to keep
      --  things simple.
   end record;

end Test_Storage_Pools;
--  Abstract:
--
--  see spec
--
--  Copyright (C) 1997 - 1999, 2002, 2003 Stephen Leake.  All Rights Reserved.
--
--  This program is free software; you can redistribute it and/or
--  modify it under terms of the GNU General Public License as
--  published by the Free Software Foundation; either version 2, or (at
--  your option) any later version. This program is distributed in the
--  hope that it will be useful, but WITHOUT ANY WARRANTY; without even
--  the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
--  PURPOSE. See the GNU General Public License for more details. You
--  should have received a copy of the GNU General Public License
--  distributed with this program; see file COPYING. If not, write to
--  the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
--  MA 02111-1307, USA.

pragma License (GPL);

with Ada.Text_IO;
with System.Address_To_Access_Conversions;
with Ada.Exceptions;
package body Test_Storage_Pools is

   Block_Header_Size : constant System.Storage_Elements.Storage_Count :=
      System.Storage_Elements.Storage_Count (Block_Header_Type'Size /
                                             System.Storage_Elements.Storage_Element'Size);

   --  This would be cleaner if Address_To_Access_Conversions took the
   --  pointer type as parameter, instead of declaring it!
   package Address_To_Block_Access is new System.Address_To_Access_Conversions (Block_Header_Type);

   function To_Block_Access
      (Pool    : in Storage_Pool_Type;
       Address : in System.Address)
       return Block_Access_Type
   is
      use type System.Address;
   begin
      if Address < Pool.Storage (1)'Address or
         Address > Pool.Storage (Pool.Pool_Size)'Address
      then
         raise Storage_Error;
      end if;
      return Block_Access_Type (Address_To_Block_Access.To_Pointer (Address));
   end To_Block_Access;

   function To_Address (Value : in Block_Access_Type) return System.Address
   is begin
      return Address_To_Block_Access.To_Address (Address_To_Block_Access.Object_Pointer (Value));
   end To_Address;

   function Aligned_Address
      (Address     : in System.Storage_Elements.Integer_Address;
       Alignment   : in System.Storage_Elements.Storage_Count)
      return System.Storage_Elements.Integer_Address
      --  Adjust Address upwards to next Alignment.
   is
      use System.Storage_Elements;
      Aligned : constant Integer_Address := Address + Address rem Integer_Address (Alignment);
   begin
      return Aligned;
   end Aligned_Address;

   -----------
   --  Override Root_Storage_Pool operations

   procedure Allocate
      (Pool                     : in out Storage_Pool_Type;
       Storage_Address          :    out System.Address;
       Size_In_Storage_Elements : in     System.Storage_Elements.Storage_Count;
       Alignment                : in     System.Storage_Elements.Storage_Count)
   is
      pragma Unreferenced (Alignment);

      use System.Storage_Elements;
      use Ada.Exceptions;
      Block                : Block_Access_Type := Pool.First_Free;
      Block_Start          : Integer_Address;
      Remaining_Block      : Block_Access_Type;
      Aligned              : Integer_Address;
      Prev                 : Block_Access_Type := null;

      --  We store a block header in free'd blocks, to maintain the
      --  free block list. So each allocated block has to be at least
      --  that big.
      Padded_Size    : constant Storage_Count := Storage_Count'Max (Size_In_Storage_Elements, Block_Header_Size);
      Allocated_Size : Storage_Count;
   begin
      if Pool.Debug then
         Ada.Text_IO.Put_Line ("allocating " &
                               Storage_Count'Image (Size_In_Storage_Elements) &
                               " from " &
                               Pool.Name.all);
      end if;

      Find_Free_Fit :
      loop
         if Block = null then
            Raise_Exception (Storage_Error'Identity, "Allocate: pool full (or fragmented)");
         end if;
         exit Find_Free_Fit when Block.Size >= Padded_Size;
         Prev := Block;
         Block := Block.Next;
      end loop Find_Free_Fit;

      --  Aligned points past the end of the just-allocated block; it
      --  is the base of the block of remaining space.
      Block_Start := To_Integer (To_Address (Block));
      Aligned     := Aligned_Address
          (Address   => Block_Start + Integer_Address (Padded_Size),
           Alignment => 8);

      Allocated_Size  := Storage_Count (Aligned - Block_Start);

      --  Allocated_Size might be > Block.Size because of alignment.
      --  In that case, their is no remaining space, so it can't be a
      --  block.
      if Block.Size > Allocated_Size and then Block.Size - Allocated_Size >= Block_Header_Size then
         --  Ok, remaining space can be a real block. But check to see
         --  if it is outside the pool!
         begin
            Remaining_Block := To_Block_Access (Pool, To_Address (Aligned));
         exception
         when Storage_Error =>
            Raise_Exception (Storage_Error'Identity, "Allocate: pool full (or fragmented)");
         end;

         if Prev = null then
            --  Allocated from first free block.
            Pool.First_Free := Remaining_Block;
         else
            Prev.Next := Remaining_Block;
         end if;

         Remaining_Block.all :=
            (Size => Block.Size - Allocated_Size,
             Next => Block.Next);
      else
         --  Remaining space too small for a block. Just link to next
         --  free block.
         if Prev = null then
            --  Allocated from first free block.
            Pool.First_Free := Pool.First_Free.Next;
         else
            Prev.Next := Block.Next;
         end if;

      end if;

      Pool.Allocate_Count         := Pool.Allocate_Count + 1;
      --  Only track actual request in Allocated_Elements, since
      --  that's what will be deallocated.
      Pool.Allocated_Elements     := Pool.Allocated_Elements + Natural (Size_In_Storage_Elements);
      Pool.Max_Allocated_Elements := Natural'Max (Pool.Allocated_Elements, Pool.Max_Allocated_Elements);
      Storage_Address             := To_Address (Block);
   end Allocate;

   procedure Deallocate
      (Pool                     : in out Storage_Pool_Type;
       Storage_Address          : in     System.Address;
       Size_In_Storage_Elements : in     System.Storage_Elements.Storage_Count;
       Alignment                : in     System.Storage_Elements.Storage_Count)
   is
      pragma Unreferenced (Alignment);

      use System.Storage_Elements;
      Block : Block_Access_Type;
   begin
      if Pool.Debug then
         Ada.Text_IO.Put_Line ("deallocating " &
                               Storage_Count'Image (Size_In_Storage_Elements) &
                               " from " &
                               Pool.Name.all);
      end if;

      --  Store a free-list block header in the free'd block, add
      --  block to head of free list.

      Block := To_Block_Access (Pool, Storage_Address);

      Block.all :=
         (Size => Size_In_Storage_Elements,
          Next => Pool.First_Free);

      Pool.First_Free := Block;

      Pool.Deallocate_Count := Pool.Deallocate_Count + 1;
      Pool.Allocated_Elements := Pool.Allocated_Elements - Natural (Size_In_Storage_Elements);
   exception
   when Storage_Error =>
      Ada.Exceptions.Raise_Exception
         (Program_Error'Identity,
          "Address not from storage pool " & Pool.Name.all);
   end Deallocate;

   function Storage_Size (Pool : Storage_Pool_Type) return System.Storage_Elements.Storage_Count
   is begin
      return Pool.Pool_Size;
   end Storage_Size;

   -----------
   --  New operations

   function Allocate_Count (Pool : Storage_Pool_Type) return Natural
   is begin
      return Pool.Allocate_Count;
   end Allocate_Count;

   function Allocated_Elements (Pool : Storage_Pool_Type) return Natural
   is begin
      return Pool.Allocated_Elements;
   end Allocated_Elements;

   procedure Check_Deallocated (Pool : in Storage_Pool_Type)
   is begin
      if Pool.Allocated_Elements /= 0 then
         Ada.Text_IO.Put_Line ("Error : " & Pool.Name.all & " not deallocated");
         Show_Storage (Pool, Force_Debug => True);
      end if;
   end Check_Deallocated;

   function Deallocate_Count (Pool : Storage_Pool_Type) return Natural
   is begin
      return Pool.Deallocate_Count;
   end Deallocate_Count;

   function Max_Allocated_Elements (Pool : Storage_Pool_Type) return Natural
   is begin
      return Pool.Max_Allocated_Elements;
   end Max_Allocated_Elements;

   procedure Reset_Counts (Pool : in out Storage_Pool_Type)
   is begin
      Pool.Deallocate_Count := 0;
      Pool.Allocate_Count := 0;
      Pool.Max_Allocated_Elements := Pool.Allocated_Elements;
   end Reset_Counts;

   procedure Set_Debug (Pool : in out Storage_Pool_Type; Debug : in Boolean)
   is begin
      Pool.Debug := Debug;
   end Set_Debug;

   procedure Show_Storage (Pool : in Storage_Pool_Type; Force_Debug : in Boolean := False)
   is
      use Ada.Text_IO;
   begin
      if Pool.Debug or Force_Debug then
         Put_Line (Pool.Name.all & " : ");
         Put_Line ("Allocate_Count         => " & Natural'Image (Pool.Allocate_Count));
         Put_Line ("Deallocate_Count       => " & Natural'Image (Pool.Deallocate_Count));
         Put_Line ("Allocated_Elements     => " & Natural'Image (Pool.Allocated_Elements));
         Put_Line ("Max_Allocated_Elements => " & Natural'Image (Pool.Max_Allocated_Elements));
      end if;
   end Show_Storage;

   -----------
   --  Private operations

   procedure Initialize (Pool : in out Storage_Pool_Type)
   is
      use System.Storage_Elements;
      use Ada.Exceptions;
   begin
      if Pool.Pool_Size < Block_Header_Size then
         Raise_Exception (Storage_Error'Identity, "Initialize: pool_size < header_size");
      end if;

      Pool.Debug                  := False;
      Pool.Allocate_Count         := 0;
      Pool.Deallocate_Count       := 0;
      Pool.Allocated_Elements     := 0;
      Pool.Max_Allocated_Elements := 0;
      Pool.First_Free             := To_Block_Access
         (Pool,
          To_Address
            (Aligned_Address
               (Address   => To_Integer (Pool.Storage'Address),
                Alignment => 8)));
      Pool.First_Free.all         := (Pool.Pool_Size, null);
   end Initialize;

end Test_Storage_Pools;

Re: Finding out minimal allocation unit

[Simon Wright]

Stefan Bellon <sbellon@sbellon.de> writes:

> Well, our idea was to build a generic storage pool which can handle
> only memory chunks of one size. And the generic storage pool is
> instantiated with that size as generic parameter. So that each data
> structure instance (be it a list, a tree, hash table, ...) has its
> own storage pool with the exact Item_Type'Size instantiated.

I have a feeling that generics were problematic when I tried something
like this -- but you can always use a constraint:

   with System.Storage_Pools;
   with System.Storage_Elements;

   package BC.Support.Managed_Storage is

      pragma Elaborate_Body;

      package SSE renames System.Storage_Elements;
      package SSP renames System.Storage_Pools;

      type Pool (Chunk_Size : SSE.Storage_Count) is
        new SSP.Root_Storage_Pool with private;

from the Booch Components (this particular pool has a bug filed
against it at the moment, caused by a perceived need to allocate
variously-sized items from within large chunks and the resulting need
to chain the free list through chunks ...)

Re: Finding out minimal allocation unit

[Martin Krischik]

Stefan Bellon wrote:

> Martin Krischik wrote:
> 
>> First we need to know which platform you are using (compiler/OS).
> 
> GNAT on GNU/Linux, Windows and Solaris, where the memory allocation
> should work well on all three of them (but using separates or package
> Naming in a project file to supply different algorithms for the
> allocation strategy is no problem).

The GNAT default storrage pool just calls malloc and free from the C
libraries - which explains the overhead.

>> Then: how a storrage pool get's it memory is up to the pool designer.
> 
>> In your case you could allocate a large chuck of memory strait from
>> the OS and then sub-allocate it using an algorithm optimised for your
>> needs.
> 
> When using storage pools, can the storage pools be dynamically resized,
> or is a storage pool, once created, fixed in its size? The latter would
> rule out using storage pools since we do not know in advance how many
> data we need to store, just the "Item_Type" is known when instantiating
> the data structure, so it's size is known (provided we can trust the
> 'Size, 'Object_Size, and 'Component_Size attributes).

Whatever you implement. Other posters allready suggested a linked list of
arrays which seems the best approach for a variable amount of fixed sized
elements.

Martin
-- 
mailto://krischik@users.sourceforge.net
Ada programming at: http://ada.krischik.com

Re: Finding out minimal allocation unit

[Robert A Duff]

Stefan Bellon <sbellon@sbellon.de> writes:

> Martin Krischik wrote:
>
>> First we need to know which platform you are using (compiler/OS).
>
> GNAT on GNU/Linux, Windows and Solaris, where the memory allocation
> should work well on all three of them (but using separates or package
> Naming in a project file to supply different algorithms for the
> allocation strategy is no problem).

You can probably use storage pool code that is entirely portable to
these three systems.  If you need to use OS-specific things like mmap
and VirtualAlloc, you can isolate those parts, but in your case, it's
probably not necessary.

>> Then: how a storrage pool get's it memory is up to the pool designer.
>
>> In your case you could allocate a large chuck of memory strait from
>> the OS and then sub-allocate it using an algorithm optimised for your
>> needs.
>
> When using storage pools, can the storage pools be dynamically resized,
> or is a storage pool, once created, fixed in its size?

User-defined storage pools are entirely programmable.  You write the
code.  You make it do whatever you like.  If you want
dynamically-resizable pools, then write the Allocate procedure
to dynamically resize when needed.

>... The latter would
> rule out using storage pools since we do not know in advance how many
> data we need to store, just the "Item_Type" is known when instantiating
> the data structure, so it's size is known (provided we can trust the
> 'Size, 'Object_Size, and 'Component_Size attributes).

You need to look up the 'Max_Size_In_Storage_Elements attribute,
which is more relevant to storage pools.  If your types are not
unconstrained arrays or discriminated records, then the "Max_" size
is probably the only size.

- Bob