* Ada containers and custom allocators @ 2008-01-07 15:48 Maciej Sobczak 2008-01-07 16:29 ` Dmitry A. Kazakov 2008-01-08 1:54 ` Randy Brukardt 0 siblings, 2 replies; 18+ messages in thread From: Maciej Sobczak @ 2008-01-07 15:48 UTC (permalink / raw) Hi, Is it possible to set up a custom allocator for use with any given Ada container? -- Maciej Sobczak * www.msobczak.com * www.inspirel.com ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: Ada containers and custom allocators 2008-01-07 15:48 Ada containers and custom allocators Maciej Sobczak @ 2008-01-07 16:29 ` Dmitry A. Kazakov 2008-01-08 1:54 ` Randy Brukardt 1 sibling, 0 replies; 18+ messages in thread From: Dmitry A. Kazakov @ 2008-01-07 16:29 UTC (permalink / raw) On Mon, 7 Jan 2008 07:48:58 -0800 (PST), Maciej Sobczak wrote: > Is it possible to set up a custom allocator for use with any given Ada > container? Formally yes, the container type is just a type and you can declare a pool-specific access type for it. Though, if the container implementation allocates some things privately, then you have no influence on how it does that, unless this allocation is exposed in container's interface. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: Ada containers and custom allocators 2008-01-07 15:48 Ada containers and custom allocators Maciej Sobczak 2008-01-07 16:29 ` Dmitry A. Kazakov @ 2008-01-08 1:54 ` Randy Brukardt 2008-01-08 7:59 ` Maciej Sobczak 1 sibling, 1 reply; 18+ messages in thread From: Randy Brukardt @ 2008-01-08 1:54 UTC (permalink / raw) "Maciej Sobczak" <see.my.homepage@gmail.com> wrote in message news:472f2c87-1238-42a5-8b94-92e9b70981da@f47g2000hsd.googlegroups.com... > Hi, > > Is it possible to set up a custom allocator for use with any given Ada > container? If you mean an allocator for the private data of the container (which includes all of the elements and is the bulk of the container), the answer is no. The standard Ada containers do not provide any mechanism to control how/were the container allocates memory. We've discussed whether it would be possible to change that (perhaps by including a Storage_Pool parameter to the instantiation), but that would be (a) rather inconvenient, as there is no name for the standard storage pool, and there was substantial opposition to defining one; (b) very constraining on implementations, as the allocation behavior of the container would have to be fairly strongly defined in order for this to be useful (or, the storage pool passed would have to be completely general, allowing any size allocation, which would eliminate the vast majority of interesting things that you can do with storage pools). Thus, it seems more valuable to have bounded forms for which all of the allocation can be part of the container object, in which case a regular access type and allocator would do the trick. There is a project to define those in the works, but it hasn't been making a lot of progress. Randy. ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: Ada containers and custom allocators 2008-01-08 1:54 ` Randy Brukardt @ 2008-01-08 7:59 ` Maciej Sobczak 2008-01-08 23:54 ` Randy Brukardt 2008-01-09 1:17 ` Jeffrey R. Carter 0 siblings, 2 replies; 18+ messages in thread From: Maciej Sobczak @ 2008-01-08 7:59 UTC (permalink / raw) On 8 Sty, 02:54, "Randy Brukardt" <ra...@rrsoftware.com> wrote: > > Is it possible to set up a custom allocator for use with any given Ada > > container? > > If you mean an allocator for the private data of the container (which > includes all of the elements and is the bulk of the container), the answer > is no. This is exactly what I mean. It is not uncommon for a program to have a majority of its dynamic memory managed by containers. > The standard Ada containers do not provide any mechanism to control > how/were the container allocates memory. This limitation prevents programmers from doing many interesting optimizations. Even if we put performance issues aside, I might want to control the memory allocation for reliability. [...] > (or, the > storage pool passed would have to be completely general, allowing any size > allocation, which would eliminate the vast majority of interesting things > that you can do with storage pools). There are ways to overcome this problem, at least for some container types. Node-based containers could use fixed-size allocators, but of course it is the container which would then instantiate the allocator with the proper node size. It was possible in C++. -- Maciej Sobczak * www.msobczak.com * www.inspirel.com ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: Ada containers and custom allocators 2008-01-08 7:59 ` Maciej Sobczak @ 2008-01-08 23:54 ` Randy Brukardt 2008-01-09 8:56 ` Dmitry A. Kazakov 2008-01-09 15:28 ` Robert A Duff 2008-01-09 1:17 ` Jeffrey R. Carter 1 sibling, 2 replies; 18+ messages in thread From: Randy Brukardt @ 2008-01-08 23:54 UTC (permalink / raw) "Maciej Sobczak" <see.my.homepage@gmail.com> wrote in message news:fb7764c5-31f9-488d-a0e6-53ffd6c96182@k39g2000hsf.googlegroups.com... > On 8 Sty, 02:54, "Randy Brukardt" <ra...@rrsoftware.com> wrote: ... > > The standard Ada containers do not provide any mechanism to control > > how/were the container allocates memory. > > This limitation prevents programmers from doing many interesting > optimizations. Even if we put performance issues aside, I might want > to control the memory allocation for reliability. Yes, of course. It could be used for performance monitoring as well. But I wouldn't characterize it as "many" interesting optimizations, it's more like a few interesting things. But it isn't valuable enough to force every user of a container to define a storage pool (since there is no name for a standard storage pool). And we needed to keep the number of standard containers manageable. > [...] > > (or, the > > storage pool passed would have to be completely general, allowing any size > > allocation, which would eliminate the vast majority of interesting things > > that you can do with storage pools). > > There are ways to overcome this problem, at least for some container > types. Node-based containers could use fixed-size allocators, but of > course it is the container which would then instantiate the allocator > with the proper node size. It was possible in C++. Only if you put severe limits on the implementations. For one thing, you would need to know the fixed node size in the storage pool in order to take any realistic advantage of it, but you couldn't ask the container's implementation for that size since you'd have to pass the storage pool to the instance. The only practical way to do that is to *require* a particular node layout. We might as well just standardize the source code of the container body in that case. Moreover, there is no requirement in Ada that objects be laid out continuously. Janus/Ada will often make several allocator calls when allocating parts of an object, and those calls will all be different sizes. That's especially true inside of a generic body, where essentially everything that depends on a formal type is of an unknown size and thus has to be allocated separately. Even if you had the source code of the body, it probably would make different calls to Storage_Pool.Allocate on Janus/Ada and on GNAT. We'd also have to define what operations can calls the allocators. Currently, there are no such restrictions on the containers implementation. Also, of course, it would only work for a couple of the containers. All of the hashed forms also are going to allocate the hash table, so there are going to be odd-size allocations (more than just nodes). And the vectors are likely to allocate chunks of various sizes. The net effect is that this is not possible to define (or use) in any useful, portable way. (If you're willing to stick to a single vendor, then it is more possible, but that of course has nothing to do with the standard.) Combined with the inability to name the standard storage pool, there isn't much point in doing this for the primary containers. The basic idea of the containers was to define a specification, and allow implementers to innovate on the implementations. (They don't even have to be in Ada.) The extra specification required to allow passing in a storage pool would seriously reduce these possibilities. The bounded forms seem to allow even better control over dynamic allocation (by not having any in the common case, although that surely wouldn't be true for Janus/Ada), are much easier to use (don't have to write a storage pool), and would work for the high-intergrity types that cannot allow an allocator near their program. Thus, they're the first focus of work. There are a lot of other ideas, but I can't say what if anything will come of them. Randy. ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: Ada containers and custom allocators 2008-01-08 23:54 ` Randy Brukardt @ 2008-01-09 8:56 ` Dmitry A. Kazakov 2008-01-09 15:29 ` Robert A Duff 2008-01-09 15:28 ` Robert A Duff 1 sibling, 1 reply; 18+ messages in thread From: Dmitry A. Kazakov @ 2008-01-09 8:56 UTC (permalink / raw) On Tue, 8 Jan 2008 17:54:44 -0600, Randy Brukardt wrote: > But it isn't valuable enough to force every user > of a container to define a storage pool (since there is no name for a > standard storage pool). That always wondered me, why there is no name for. Especially because the default storage pool can be obtained anyway: type Some_Ptr is access Integer; -- Goes to the default storage pool package Foo is new Boo (Some_Ptr'Storage_Pool); -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: Ada containers and custom allocators 2008-01-09 8:56 ` Dmitry A. Kazakov @ 2008-01-09 15:29 ` Robert A Duff 2008-01-09 17:09 ` Dmitry A. Kazakov 2008-01-11 5:00 ` Randy Brukardt 0 siblings, 2 replies; 18+ messages in thread From: Robert A Duff @ 2008-01-09 15:29 UTC (permalink / raw) "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes: > On Tue, 8 Jan 2008 17:54:44 -0600, Randy Brukardt wrote: > >> But it isn't valuable enough to force every user >> of a container to define a storage pool (since there is no name for a >> standard storage pool). > > That always wondered me, why there is no name for. Especially because the > default storage pool can be obtained anyway: > > type Some_Ptr is access Integer; -- Goes to the default storage pool > package Foo is new Boo (Some_Ptr'Storage_Pool); The compiler is not required to use the same storage pool for all types. Therefore, the concept "THE default pool" does not exist. Some_Ptr'Storage_Pool might be a special pool tuned for the fact that Size_In_Storage_Elements = 4 and Alignment = 4. Allocate could add 4 to a known-aligned pointer, and ignore the Size_In_Storage_Elements and Alignment parameters. If Boo uses this pool for something other than Integer, it might not work. However, I see nothing wrong with having a predefined operation that returns a suitable pool. - Bob ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: Ada containers and custom allocators 2008-01-09 15:29 ` Robert A Duff @ 2008-01-09 17:09 ` Dmitry A. Kazakov 2008-01-09 21:58 ` Robert A Duff 2008-01-11 5:00 ` Randy Brukardt 1 sibling, 1 reply; 18+ messages in thread From: Dmitry A. Kazakov @ 2008-01-09 17:09 UTC (permalink / raw) On Wed, 09 Jan 2008 10:29:46 -0500, Robert A Duff wrote: > "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes: > >> On Tue, 8 Jan 2008 17:54:44 -0600, Randy Brukardt wrote: >> >>> But it isn't valuable enough to force every user >>> of a container to define a storage pool (since there is no name for a >>> standard storage pool). >> >> That always wondered me, why there is no name for. Especially because the >> default storage pool can be obtained anyway: >> >> type Some_Ptr is access Integer; -- Goes to the default storage pool >> package Foo is new Boo (Some_Ptr'Storage_Pool); > > The compiler is not required to use the same storage pool for all > types. Therefore, the concept "THE default pool" does not exist. > > Some_Ptr'Storage_Pool might be a special pool tuned for the fact that > Size_In_Storage_Elements = 4 and Alignment = 4. Allocate could > add 4 to a known-aligned pointer, and ignore the > Size_In_Storage_Elements and Alignment parameters. > > If Boo uses this pool for something other than Integer, > it might not work. Which is broken then. Because it does not fulfill the contract of Storage_Pool'Class. I guess that Allocate is allowed to raise Storage_Error, but not to ignore parameters. If the implementation handles a family of pools one per object's size power of two or like that, then it should return the family root rather than the size-specific pool. Otherwise, the following will work either: type Integer_Ptr is access Integer; type Character_Ptr is access Character; for Character_Ptr'Storage_Pool use Integer_Ptr'Storage_Pool; I think ARM should clarify the issue of how pools could be constrained while allowing a safe use. > However, I see nothing wrong with having a predefined operation that > returns a suitable pool. Yes. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: Ada containers and custom allocators 2008-01-09 17:09 ` Dmitry A. Kazakov @ 2008-01-09 21:58 ` Robert A Duff 2008-01-10 10:12 ` Dmitry A. Kazakov 0 siblings, 1 reply; 18+ messages in thread From: Robert A Duff @ 2008-01-09 21:58 UTC (permalink / raw) "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes: > On Wed, 09 Jan 2008 10:29:46 -0500, Robert A Duff wrote: >> Some_Ptr'Storage_Pool might be a special pool tuned for the fact that >> Size_In_Storage_Elements = 4 and Alignment = 4. Allocate could >> add 4 to a known-aligned pointer, and ignore the >> Size_In_Storage_Elements and Alignment parameters. >> >> If Boo uses this pool for something other than Integer, >> it might not work. > > Which is broken then. Because it does not fulfill the contract of > Storage_Pool'Class. What's the contract of Storage_Pool'Class? It is certainly not intended that all pools must support all sizes and alignments -- that would defeat the optimization purpose of pools. >...I guess that Allocate is allowed to raise > Storage_Error, but not to ignore parameters. Well, if it ignores the size, or raises an exception when the size is not 4, either way, it won't work when the size is not 4. But I agree that an exception is better. I'd like to suppress that check, though, if it's too slow. > If the implementation handles a family of pools one per object's size power > of two or like that, then it should return the family root rather than the > size-specific pool. What if there is no such root? How about an implementation that creates one pool for each static size that is used in the program, up to 100 bytes. Any access type whose designated type's size is nonstatic, or > 100, uses a separate pool that can handle any size, and does not call those static-size pools. Each static-size pool has the size built in to its code. Sounds like an efficient implementation. When you say "new Integer", there's no need to check the size at run time, because the compiler knows it's 4. Do you think this implementation is wrong? >...Otherwise, the following will work either: > > type Integer_Ptr is access Integer; > type Character_Ptr is access Character; > for Character_Ptr'Storage_Pool use Integer_Ptr'Storage_Pool; I don't think the RM requires the above to work properly. > I think ARM should clarify the issue of how pools could be constrained > while allowing a safe use. Perhaps. >> However, I see nothing wrong with having a predefined operation that >> returns a suitable pool. > > Yes. - Bob ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: Ada containers and custom allocators 2008-01-09 21:58 ` Robert A Duff @ 2008-01-10 10:12 ` Dmitry A. Kazakov 0 siblings, 0 replies; 18+ messages in thread From: Dmitry A. Kazakov @ 2008-01-10 10:12 UTC (permalink / raw) On Wed, 09 Jan 2008 16:58:22 -0500, in comp.lang.ada you wrote: > "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes: > >> On Wed, 09 Jan 2008 10:29:46 -0500, Robert A Duff wrote: >>> Some_Ptr'Storage_Pool might be a special pool tuned for the fact that >>> Size_In_Storage_Elements = 4 and Alignment = 4. Allocate could >>> add 4 to a known-aligned pointer, and ignore the >>> Size_In_Storage_Elements and Alignment parameters. >>> >>> If Boo uses this pool for something other than Integer, >>> it might not work. >> >> Which is broken then. Because it does not fulfill the contract of >> Storage_Pool'Class. > > What's the contract of Storage_Pool'Class? It is certainly not intended > that all pools must support all sizes and alignments -- that would > defeat the optimization purpose of pools. But a loose contract would make storage pools unusable. Actually it depends on the semantics of the attribute P'Storage_Pool. When the result is a constrained (optimized) pool then indeed there will be no way to fix it. >>...I guess that Allocate is allowed to raise >> Storage_Error, but not to ignore parameters. > > Well, if it ignores the size, or raises an exception when the size is > not 4, either way, it won't work when the size is not 4. But I agree > that an exception is better. I'd like to suppress that check, though, > if it's too slow. Either way is bad. Storage_Error should indicate a run-time problem, while using an inappropriate pool is just a bug, basically a type error. And it should be Constraint_Error then. >> If the implementation handles a family of pools one per object's size power >> of two or like that, then it should return the family root rather than the >> size-specific pool. > > What if there is no such root? How about an implementation that creates > one pool for each static size that is used in the program, up to 100 > bytes. Any access type whose designated type's size is nonstatic, > or > 100, uses a separate pool that can handle any size, and does > not call those static-size pools. Each static-size pool has the > size built in to its code. > > Sounds like an efficient implementation. When you say "new Integer", > there's no need to check the size at run time, because the compiler > knows it's 4. Do you think this implementation is wrong? It is not wrong. Wrong is when P'Storage_Pool returns a specific pool from the family. It should return a possibly less efficient family root pool, which has to be present (when used). If an access type is created with this root pool, the implementation is free to choose a more specific pool instead. If for example the object size is known to be static. But that is an implementation detail which may not leak outside (through P'Storage_Pool, for instance). I think it should be no problem to remove the root pool altogether upon linking when it is never used, i.e. there should be no any overhead. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: Ada containers and custom allocators 2008-01-09 15:29 ` Robert A Duff 2008-01-09 17:09 ` Dmitry A. Kazakov @ 2008-01-11 5:00 ` Randy Brukardt 1 sibling, 0 replies; 18+ messages in thread From: Randy Brukardt @ 2008-01-11 5:00 UTC (permalink / raw) "Robert A Duff" <bobduff@shell01.TheWorld.com> wrote in message news:wcchchnc905.fsf@shell01.TheWorld.com... > "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes: ... > > That always wondered me, why there is no name for. Especially because the > > default storage pool can be obtained anyway: > > > > type Some_Ptr is access Integer; -- Goes to the default storage pool > > package Foo is new Boo (Some_Ptr'Storage_Pool); > > The compiler is not required to use the same storage pool for all > types. Therefore, the concept "THE default pool" does not exist. > > Some_Ptr'Storage_Pool might be a special pool tuned for the fact that > Size_In_Storage_Elements = 4 and Alignment = 4. Allocate could > add 4 to a known-aligned pointer, and ignore the > Size_In_Storage_Elements and Alignment parameters. > > If Boo uses this pool for something other than Integer, > it might not work. Right. And it turns out that some commonly used compilers actually do use different pools in different circumstances. (I think the mechanism had to do with the nesting level of the access type declaration; I recall that we discussed it in detail.) The net effect is that in some existing implementations, there is no general pool. It didn't make much sense to force them to change to a more general model that could introduce storage leaks in existing programs, and thus there is (still) no name for the standard pool. Randy. > However, I see nothing wrong with having a predefined operation that > returns a suitable pool. > > - Bob ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: Ada containers and custom allocators 2008-01-08 23:54 ` Randy Brukardt 2008-01-09 8:56 ` Dmitry A. Kazakov @ 2008-01-09 15:28 ` Robert A Duff 2008-01-11 5:00 ` Randy Brukardt 1 sibling, 1 reply; 18+ messages in thread From: Robert A Duff @ 2008-01-09 15:28 UTC (permalink / raw) "Randy Brukardt" <randy@rrsoftware.com> writes: > Yes, of course. It could be used for performance monitoring as well. But I > wouldn't characterize it as "many" interesting optimizations, it's more like > a few interesting things. But it isn't valuable enough to force every user > of a container to define a storage pool (since there is no name for a > standard storage pool). That seems easy enough to fix. Simply have a predefined function: type Storage_Pool_Pointer is access all Root_Storage_Pool'Class; function Default_Storage_Pool return Storage_Pool_Pointer; and use that for the default in the generic. Default_Storage_Pool must be general enough to support any size. There's no requirement that this be the same pool used by default for misc access types. >... And we needed to keep the number of standard > containers manageable. I suppose, but we weren't shy about writing macros in English -- see for example package Float_Text_IO. It would take one paragraph in the RM to double the number of container packages by having versions with a Pool parameter. Pretty ugly, but there's precedent. >> [...] >> > (or, the >> > storage pool passed would have to be completely general, allowing any > size >> > allocation, which would eliminate the vast majority of interesting > things >> > that you can do with storage pools). >> >> There are ways to overcome this problem, at least for some container >> types. Node-based containers could use fixed-size allocators, but of >> course it is the container which would then instantiate the allocator >> with the proper node size. It was possible in C++. > > Only if you put severe limits on the implementations. For one thing, you > would need to know the fixed node size in the storage pool in order to take > any realistic advantage of it, but you couldn't ask the container's > implementation for that size since you'd have to pass the storage pool to > the instance. The only practical way to do that is to *require* a particular > node layout. We might as well just standardize the source code of the > container body in that case. > > Moreover, there is no requirement in Ada that objects be laid out > continuously. Perhaps there should be! But anyway, given this fact, user-defined storage pools need to be fully general (accept any size), or else depend on details of the Ada implementation. This is not specific to containers. >...Janus/Ada will often make several allocator calls when > allocating parts of an object, and those calls will all be different sizes. > That's especially true inside of a generic body, where essentially > everything that depends on a formal type is of an unknown size and thus has > to be allocated separately. Even if you had the source code of the body, it > probably would make different calls to Storage_Pool.Allocate on Janus/Ada > and on GNAT. > > We'd also have to define what operations can calls the allocators. I don't see why. > Currently, there are no such restrictions on the containers implementation. > > Also, of course, it would only work for a couple of the containers. All of > the hashed forms also are going to allocate the hash table, so there are > going to be odd-size allocations (more than just nodes). And the vectors are > likely to allocate chunks of various sizes. It can work -- you just can't take advantage of (say) fixed sized chunks. I guess what you're saying is that that defeats the main purpose! > The net effect is that this is not possible to define (or use) in any > useful, portable way. (If you're willing to stick to a single vendor, then > it is more possible, but that of course has nothing to do with the > standard.) Combined with the inability to name the standard storage pool, > there isn't much point in doing this for the primary containers. > > The basic idea of the containers was to define a specification, and allow > implementers to innovate on the implementations. (They don't even have to be > in Ada.) The extra specification required to allow passing in a storage pool > would seriously reduce these possibilities. > > The bounded forms seem to allow even better control over dynamic allocation > (by not having any in the common case, although that surely wouldn't be true > for Janus/Ada), are much easier to use (don't have to write a storage pool), > and would work for the high-intergrity types that cannot allow an allocator > near their program. Thus, they're the first focus of work. There are a lot > of other ideas, but I can't say what if anything will come of them. - Bob ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: Ada containers and custom allocators 2008-01-09 15:28 ` Robert A Duff @ 2008-01-11 5:00 ` Randy Brukardt 2008-01-11 21:02 ` Maciej Sobczak 0 siblings, 1 reply; 18+ messages in thread From: Randy Brukardt @ 2008-01-11 5:00 UTC (permalink / raw) "Robert A Duff" <bobduff@shell01.TheWorld.com> wrote in message news:wcclk6zc91o.fsf@shell01.TheWorld.com... > "Randy Brukardt" <randy@rrsoftware.com> writes: > > > Yes, of course. It could be used for performance monitoring as well. But I > > wouldn't characterize it as "many" interesting optimizations, it's more like > > a few interesting things. But it isn't valuable enough to force every user > > of a container to define a storage pool (since there is no name for a > > standard storage pool). > > That seems easy enough to fix. Simply have a predefined function: > > type Storage_Pool_Pointer is access all Root_Storage_Pool'Class; > function Default_Storage_Pool return Storage_Pool_Pointer; > > and use that for the default in the generic. > > Default_Storage_Pool must be general enough to support any size. > There's no requirement that this be the same pool used by > default for misc access types. Maybe, but that could be a substantially worse pool on some implementations than used for normal access types. So I'm unsure if that is a good idea. > >... And we needed to keep the number of standard > > containers manageable. > > I suppose, but we weren't shy about writing macros in English -- see for > example package Float_Text_IO. It would take one paragraph in the RM > to double the number of container packages by having versions with > a Pool parameter. Pretty ugly, but there's precedent. OK, but only if you are willing to leave absolutely everything about how the pool is used implementation-defined. At which point, I have to wonder what the point is: you couldn't do anything at all portably. Otherwise, you're going to have to have wording about where user-defined pool operations can be called, what happens to the exceptions that they propagate, and possibly other issues that I haven't thought about yet. This isn't going to be a single sentence change -- maybe more like the magnitude of "Wide String Handling" (A.4.7). ... > > Moreover, there is no requirement in Ada that objects be laid out > > continuously. > > Perhaps there should be! Over my dead body. A serious attempt to propose that would get very, very nasty. > But anyway, given this fact, user-defined storage pools need to be fully > general (accept any size), or else depend on details of the Ada > implementation. This is not specific to containers. Correct. But it means that little useful can be done with custom pools on the predefined containers libraries. The needed generality prevents using any optimizations in the pool, so it pretty much limits you to tracking the allocations and deallocations. ... > > We'd also have to define what operations can calls the allocators. > > I don't see why. The current containers library spends quite a bit of effort defining the places where objects can be destroyed (that is, where Finalize can be called). Admittedly, a lot of that effort is to say that it isn't defined closely. But one thing we don't do is allow random calls to reading operations to call Finalize. Similarly, we always have wording to define what and where exceptions are propagated. If we allow user storage pools, we'd need the definitions of where those operations can be called (hopefully not in operations that merely read and return something!) and wording to say that the exceptions are propagated. And probably other things as well. > > Currently, there are no such restrictions on the containers implementation. > > > > Also, of course, it would only work for a couple of the containers. All of > > the hashed forms also are going to allocate the hash table, so there are > > going to be odd-size allocations (more than just nodes). And the vectors are > > likely to allocate chunks of various sizes. > > It can work -- you just can't take advantage of (say) fixed sized > chunks. I guess what you're saying is that that defeats the main > purpose! The OP claimed that fixed-size allocators could be used, and my lengthy reply was intended to rebut that. Surely, they can't be used portably or generally. It is true that you probably could do it on a specific implementation for a specific element type (it would even work on Janus/Ada that way). But as soon as you move to a different compiler (or even potentially an update for the same compiler with an "improved" containers library), it will no longer work. That might make sense to do for debugging, but it can't be used for anything long term. All of which begs the question of whether it is worth the work to accomplish. Randy. Of ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: Ada containers and custom allocators 2008-01-11 5:00 ` Randy Brukardt @ 2008-01-11 21:02 ` Maciej Sobczak 2008-01-11 22:41 ` Robert A Duff 0 siblings, 1 reply; 18+ messages in thread From: Maciej Sobczak @ 2008-01-11 21:02 UTC (permalink / raw) On 11 Sty, 06:00, "Randy Brukardt" <ra...@rrsoftware.com> wrote: > > It can work -- you just can't take advantage of (say) fixed sized > > chunks. I guess what you're saying is that that defeats the main > > purpose! > > The OP claimed that fixed-size allocators could be used, and my lengthy > reply was intended to rebut that. Surely, they can't be used portably or > generally. In Ada, you mean? In C++ this works by passing the allocator parameter to the template container class, which in turn can re-bind the allocator to use whatever size is used internally. This means that the fixed-size allocator cannot be prepared for only a given allocation size, but that does not seem to be a problem in practice. The whole point of using a fixed-size allocator is to enable some specialized allocation scheme (like bitmap-based management of free blocks) and this is independent of any given size. In other words, the allocator should be ready to work with any size, but this is fixed once by the container itself. You might say that there is a limitation in that container will have to use nodes of fixed size, but this, again does not seem to be a problem - I have never seen a list (for example) that internally uses nodes of varying sizes. This works in C++ and gives spectacular performance improvements. It's a pity Ada does not provide anything in this area. -- Maciej Sobczak * www.msobczak.com * www.inspirel.com ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: Ada containers and custom allocators 2008-01-11 21:02 ` Maciej Sobczak @ 2008-01-11 22:41 ` Robert A Duff 2008-01-12 13:40 ` Maciej Sobczak 0 siblings, 1 reply; 18+ messages in thread From: Robert A Duff @ 2008-01-11 22:41 UTC (permalink / raw) Maciej Sobczak <see.my.homepage@gmail.com> writes: > This works in C++ and gives spectacular performance improvements. It's > a pity Ada does not provide anything in this area. Why does it give spectacular performance improvements? Doesn't this indicate that the default storage management is needlessly inefficient? - Bob ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: Ada containers and custom allocators 2008-01-11 22:41 ` Robert A Duff @ 2008-01-12 13:40 ` Maciej Sobczak 2008-01-12 15:59 ` Robert A Duff 0 siblings, 1 reply; 18+ messages in thread From: Maciej Sobczak @ 2008-01-12 13:40 UTC (permalink / raw) On 11 Sty, 23:41, Robert A Duff <bobd...@shell01.TheWorld.com> wrote: > Why does it give spectacular performance improvements? > Doesn't this indicate that the default storage management > is needlessly inefficient? Default storage management is always needlessly inefficient, because it is general and cannot benefit from any additional knowledge about what will be allocated. Every single bit of additional knowledge is an improvement opportunity in some area. Fixed-size allocators can use faster algorithms than general allocators. Another axis of improvement with custom allocators is thread-safety. The global allocator cannot assume anything about threading and has to be defensive in relation to threads, which means that it has to proactively synchronize everything, always - just in case. Now imagine you have a container and you know by the design of your system that this given container will be always used in the context of a single thread. Why not give it a separate allocator that benefits from this knowledge (ie. operates on a separate, non-synchronized pool)? On multicore or multiprocessor systems unnecessary synchronization (memory barriers and such) is *VERY* expensive and can kill performance. Why not make things easier for the hardware by reducing the number of unnecessary membars? Here, again - every single bit of additional knowledge is an improvement opportunity. Related note: it was repeated many times on this groups that Ada is particularly appropriate for the coming multicore era. I'm not so sure about this and the above issue is one of the question marks. Forget about performance if you cannot partition allocation schemes for containers by threads. This will get only worse as the number of cores in CPUs increases. -- Maciej Sobczak * www.msobczak.com * www.inspirel.com ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: Ada containers and custom allocators 2008-01-12 13:40 ` Maciej Sobczak @ 2008-01-12 15:59 ` Robert A Duff 0 siblings, 0 replies; 18+ messages in thread From: Robert A Duff @ 2008-01-12 15:59 UTC (permalink / raw) Maciej Sobczak <see.my.homepage@gmail.com> writes: > On 11 Sty, 23:41, Robert A Duff <bobd...@shell01.TheWorld.com> wrote: > >> Why does it give spectacular performance improvements? >> Doesn't this indicate that the default storage management >> is needlessly inefficient? > > Default storage management is always needlessly inefficient, because > it is general and cannot benefit from any additional knowledge about > what will be allocated. Every single bit of additional knowledge is an > improvement opportunity in some area. Fixed-size allocators can use > faster algorithms than general allocators. True, but the container implementation knows whether it is allocating fixed-size objects. > Another axis of improvement with custom allocators is thread-safety. Good point. I'd like to have a language where the compiler can tell which objects are shared by more than one thread. But that's not Ada (nor is it C++). > The global allocator cannot assume anything about threading and has to > be defensive in relation to threads, which means that it has to > proactively synchronize everything, always - just in case. You don't necessarily have to lock every allocation and deallocation. There are more efficient schemes, but you're right -- there is a cost. - Bob ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: Ada containers and custom allocators 2008-01-08 7:59 ` Maciej Sobczak 2008-01-08 23:54 ` Randy Brukardt @ 2008-01-09 1:17 ` Jeffrey R. Carter 1 sibling, 0 replies; 18+ messages in thread From: Jeffrey R. Carter @ 2008-01-09 1:17 UTC (permalink / raw) Maciej Sobczak wrote: > On 8 Sty, 02:54, "Randy Brukardt" <ra...@rrsoftware.com> wrote: > >>> Is it possible to set up a custom allocator for use with any given Ada >>> container? >> If you mean an allocator for the private data of the container (which >> includes all of the elements and is the bulk of the container), the answer >> is no. > > This is exactly what I mean. It is not uncommon for a program to have > a majority of its dynamic memory managed by containers. Actually, Brukardt's reply is technically incorrect. The containers are tagged; you can derive from them and override the appropriate operations to obtain the behavior you require. Of course, this means you either have to know the internals of the container in question, or you have to override all the operations, effectively writing your own container. Which brings us to >> The standard Ada containers do not provide any mechanism to control >> how/were the container allocates memory. > > This limitation prevents programmers from doing many interesting > optimizations. Even if we put performance issues aside, I might want > to control the memory allocation for reliability. The standard library is necessarily intended for general use, not optimized for any specific requirements. If it doesn't meet your specific requirements, then you should consider custom components that do. -- Jeff Carter "Gentlemen, you can't fight in here. This is the War Room!" Dr. Strangelove 30 ^ permalink raw reply [flat|nested] 18+ messages in thread
end of thread, other threads:[~2008-01-12 15:59 UTC | newest] Thread overview: 18+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2008-01-07 15:48 Ada containers and custom allocators Maciej Sobczak 2008-01-07 16:29 ` Dmitry A. Kazakov 2008-01-08 1:54 ` Randy Brukardt 2008-01-08 7:59 ` Maciej Sobczak 2008-01-08 23:54 ` Randy Brukardt 2008-01-09 8:56 ` Dmitry A. Kazakov 2008-01-09 15:29 ` Robert A Duff 2008-01-09 17:09 ` Dmitry A. Kazakov 2008-01-09 21:58 ` Robert A Duff 2008-01-10 10:12 ` Dmitry A. Kazakov 2008-01-11 5:00 ` Randy Brukardt 2008-01-09 15:28 ` Robert A Duff 2008-01-11 5:00 ` Randy Brukardt 2008-01-11 21:02 ` Maciej Sobczak 2008-01-11 22:41 ` Robert A Duff 2008-01-12 13:40 ` Maciej Sobczak 2008-01-12 15:59 ` Robert A Duff 2008-01-09 1:17 ` Jeffrey R. Carter
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox