Finding out minimal allocation unit
in [ADA]
|
From: Stefan Bellon on 3 Apr 2007 08:43 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
From: Georg Bauhaus on 3 Apr 2007 09:22 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.
From: Stefan Bellon on 3 Apr 2007 09:28 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
From: Martin Krischik on 3 Apr 2007 09:34 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
From: Stefan Bellon on 3 Apr 2007 09:37
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 |