* Finding out minimal allocation unit @ 2007-04-03 12:43 Stefan Bellon 2007-04-03 13:22 ` Georg Bauhaus ` (2 more replies) 0 siblings, 3 replies; 27+ messages in thread From: Stefan Bellon @ 2007-04-03 12:43 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Finding out minimal allocation unit 2007-04-03 12:43 Finding out minimal allocation unit Stefan Bellon @ 2007-04-03 13:22 ` Georg Bauhaus 2007-04-03 13:28 ` Stefan Bellon ` (2 more replies) 2007-04-03 13:48 ` Robert A Duff 2007-04-03 16:45 ` Dmitry A. Kazakov 2 siblings, 3 replies; 27+ messages in thread From: Georg Bauhaus @ 2007-04-03 13:22 UTC (permalink / raw) 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. ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Finding out minimal allocation unit 2007-04-03 13:22 ` Georg Bauhaus @ 2007-04-03 13:28 ` Stefan Bellon 2007-04-03 13:34 ` Martin Krischik 2007-04-03 14:12 ` Larry Kilgallen 2 siblings, 0 replies; 27+ messages in thread From: Stefan Bellon @ 2007-04-03 13:28 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Finding out minimal allocation unit 2007-04-03 13:22 ` Georg Bauhaus 2007-04-03 13:28 ` Stefan Bellon @ 2007-04-03 13:34 ` Martin Krischik 2007-04-03 13:37 ` Stefan Bellon 2007-04-03 23:53 ` Randy Brukardt 2007-04-03 14:12 ` Larry Kilgallen 2 siblings, 2 replies; 27+ messages in thread From: Martin Krischik @ 2007-04-03 13:34 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Finding out minimal allocation unit 2007-04-03 13:34 ` Martin Krischik @ 2007-04-03 13:37 ` Stefan Bellon 2007-04-03 15:17 ` Markus E Leypold 2007-04-03 23:53 ` Randy Brukardt 1 sibling, 1 reply; 27+ messages in thread From: Stefan Bellon @ 2007-04-03 13:37 UTC (permalink / raw) To: Martin Krischik 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 ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Finding out minimal allocation unit 2007-04-03 13:37 ` Stefan Bellon @ 2007-04-03 15:17 ` Markus E Leypold 2007-04-04 17:16 ` Robert A Duff 0 siblings, 1 reply; 27+ messages in thread From: Markus E Leypold @ 2007-04-03 15:17 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Finding out minimal allocation unit 2007-04-03 15:17 ` Markus E Leypold @ 2007-04-04 17:16 ` Robert A Duff 2007-04-05 8:55 ` Markus E Leypold 0 siblings, 1 reply; 27+ messages in thread From: Robert A Duff @ 2007-04-04 17:16 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Finding out minimal allocation unit 2007-04-04 17:16 ` Robert A Duff @ 2007-04-05 8:55 ` Markus E Leypold 2007-04-05 17:55 ` Stefan Bellon 0 siblings, 1 reply; 27+ messages in thread From: Markus E Leypold @ 2007-04-05 8:55 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Finding out minimal allocation unit 2007-04-05 8:55 ` Markus E Leypold @ 2007-04-05 17:55 ` Stefan Bellon 2007-04-06 1:40 ` Randy Brukardt 0 siblings, 1 reply; 27+ messages in thread From: Stefan Bellon @ 2007-04-05 17:55 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Finding out minimal allocation unit 2007-04-05 17:55 ` Stefan Bellon @ 2007-04-06 1:40 ` Randy Brukardt 2007-04-06 8:06 ` Stefan Bellon 0 siblings, 1 reply; 27+ messages in thread From: Randy Brukardt @ 2007-04-06 1:40 UTC (permalink / raw) "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. ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Finding out minimal allocation unit 2007-04-06 1:40 ` Randy Brukardt @ 2007-04-06 8:06 ` Stefan Bellon 2007-04-06 11:06 ` Markus E Leypold 0 siblings, 1 reply; 27+ messages in thread From: Stefan Bellon @ 2007-04-06 8:06 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Finding out minimal allocation unit 2007-04-06 8:06 ` Stefan Bellon @ 2007-04-06 11:06 ` Markus E Leypold 0 siblings, 0 replies; 27+ messages in thread From: Markus E Leypold @ 2007-04-06 11:06 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Finding out minimal allocation unit 2007-04-03 13:34 ` Martin Krischik 2007-04-03 13:37 ` Stefan Bellon @ 2007-04-03 23:53 ` Randy Brukardt 2007-04-05 6:12 ` Stefan Bellon 1 sibling, 1 reply; 27+ messages in thread From: Randy Brukardt @ 2007-04-03 23:53 UTC (permalink / raw) "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. ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Finding out minimal allocation unit 2007-04-03 23:53 ` Randy Brukardt @ 2007-04-05 6:12 ` Stefan Bellon 2007-04-05 7:35 ` Martin Krischik ` (2 more replies) 0 siblings, 3 replies; 27+ messages in thread From: Stefan Bellon @ 2007-04-05 6:12 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Finding out minimal allocation unit 2007-04-05 6:12 ` Stefan Bellon @ 2007-04-05 7:35 ` Martin Krischik 2007-04-05 17:58 ` Stefan Bellon 2007-04-05 13:07 ` Robert A Duff 2007-04-06 12:38 ` Stephen Leake 2 siblings, 1 reply; 27+ messages in thread From: Martin Krischik @ 2007-04-05 7:35 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Finding out minimal allocation unit 2007-04-05 7:35 ` Martin Krischik @ 2007-04-05 17:58 ` Stefan Bellon 2007-04-07 9:27 ` Martin Krischik 2007-04-10 21:42 ` Robert A Duff 0 siblings, 2 replies; 27+ messages in thread From: Stefan Bellon @ 2007-04-05 17:58 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Finding out minimal allocation unit 2007-04-05 17:58 ` Stefan Bellon @ 2007-04-07 9:27 ` Martin Krischik 2007-04-10 21:42 ` Robert A Duff 1 sibling, 0 replies; 27+ messages in thread From: Martin Krischik @ 2007-04-07 9:27 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Finding out minimal allocation unit 2007-04-05 17:58 ` Stefan Bellon 2007-04-07 9:27 ` Martin Krischik @ 2007-04-10 21:42 ` Robert A Duff 1 sibling, 0 replies; 27+ messages in thread From: Robert A Duff @ 2007-04-10 21:42 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Finding out minimal allocation unit 2007-04-05 6:12 ` Stefan Bellon 2007-04-05 7:35 ` Martin Krischik @ 2007-04-05 13:07 ` Robert A Duff 2007-04-05 18:02 ` Stefan Bellon 2007-04-06 12:38 ` Stephen Leake 2 siblings, 1 reply; 27+ messages in thread From: Robert A Duff @ 2007-04-05 13:07 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Finding out minimal allocation unit 2007-04-05 13:07 ` Robert A Duff @ 2007-04-05 18:02 ` Stefan Bellon 2007-04-06 1:31 ` Randy Brukardt 0 siblings, 1 reply; 27+ messages in thread From: Stefan Bellon @ 2007-04-05 18:02 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Finding out minimal allocation unit 2007-04-05 18:02 ` Stefan Bellon @ 2007-04-06 1:31 ` Randy Brukardt 2007-04-06 8:10 ` Stefan Bellon 0 siblings, 1 reply; 27+ messages in thread From: Randy Brukardt @ 2007-04-06 1:31 UTC (permalink / raw) "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. ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Finding out minimal allocation unit 2007-04-06 1:31 ` Randy Brukardt @ 2007-04-06 8:10 ` Stefan Bellon 2007-04-06 17:17 ` Simon Wright 0 siblings, 1 reply; 27+ messages in thread From: Stefan Bellon @ 2007-04-06 8:10 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Finding out minimal allocation unit 2007-04-06 8:10 ` Stefan Bellon @ 2007-04-06 17:17 ` Simon Wright 0 siblings, 0 replies; 27+ messages in thread From: Simon Wright @ 2007-04-06 17:17 UTC (permalink / raw) 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 ...) ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Finding out minimal allocation unit 2007-04-05 6:12 ` Stefan Bellon 2007-04-05 7:35 ` Martin Krischik 2007-04-05 13:07 ` Robert A Duff @ 2007-04-06 12:38 ` Stephen Leake 2 siblings, 0 replies; 27+ messages in thread From: Stephen Leake @ 2007-04-06 12:38 UTC (permalink / raw) 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; ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Finding out minimal allocation unit 2007-04-03 13:22 ` Georg Bauhaus 2007-04-03 13:28 ` Stefan Bellon 2007-04-03 13:34 ` Martin Krischik @ 2007-04-03 14:12 ` Larry Kilgallen 2 siblings, 0 replies; 27+ messages in thread From: Larry Kilgallen @ 2007-04-03 14:12 UTC (permalink / raw) 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 ? ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Finding out minimal allocation unit 2007-04-03 12:43 Finding out minimal allocation unit Stefan Bellon 2007-04-03 13:22 ` Georg Bauhaus @ 2007-04-03 13:48 ` Robert A Duff 2007-04-03 16:45 ` Dmitry A. Kazakov 2 siblings, 0 replies; 27+ messages in thread From: Robert A Duff @ 2007-04-03 13:48 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Finding out minimal allocation unit 2007-04-03 12:43 Finding out minimal allocation unit Stefan Bellon 2007-04-03 13:22 ` Georg Bauhaus 2007-04-03 13:48 ` Robert A Duff @ 2007-04-03 16:45 ` Dmitry A. Kazakov 2 siblings, 0 replies; 27+ messages in thread From: Dmitry A. Kazakov @ 2007-04-03 16:45 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 27+ messages in thread
end of thread, other threads:[~2007-04-10 21:42 UTC | newest] Thread overview: 27+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2007-04-03 12:43 Finding out minimal allocation unit Stefan Bellon 2007-04-03 13:22 ` Georg Bauhaus 2007-04-03 13:28 ` Stefan Bellon 2007-04-03 13:34 ` Martin Krischik 2007-04-03 13:37 ` Stefan Bellon 2007-04-03 15:17 ` Markus E Leypold 2007-04-04 17:16 ` Robert A Duff 2007-04-05 8:55 ` Markus E Leypold 2007-04-05 17:55 ` Stefan Bellon 2007-04-06 1:40 ` Randy Brukardt 2007-04-06 8:06 ` Stefan Bellon 2007-04-06 11:06 ` Markus E Leypold 2007-04-03 23:53 ` Randy Brukardt 2007-04-05 6:12 ` Stefan Bellon 2007-04-05 7:35 ` Martin Krischik 2007-04-05 17:58 ` Stefan Bellon 2007-04-07 9:27 ` Martin Krischik 2007-04-10 21:42 ` Robert A Duff 2007-04-05 13:07 ` Robert A Duff 2007-04-05 18:02 ` Stefan Bellon 2007-04-06 1:31 ` Randy Brukardt 2007-04-06 8:10 ` Stefan Bellon 2007-04-06 17:17 ` Simon Wright 2007-04-06 12:38 ` Stephen Leake 2007-04-03 14:12 ` Larry Kilgallen 2007-04-03 13:48 ` Robert A Duff 2007-04-03 16:45 ` Dmitry A. Kazakov
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox