!standard  A.18.32(0)                                  18-03-28    AC95-00306/00
!class Amendment 18-03-28
!status received no action 18-03-28
!status received 18-03-09
!subject Defining when default initialization happens in a container
!summary

!appendix

From: Tucker Taft
Sent: Friday, March  9, 2018  8:16 AM

Here is a comment from Martin Dowie, the customer who was complaining about
"unnecessary initialization" of containers:

> Spotted the AI (http://www.ada-auth.org/cgi-bin/cvsweb.cgi/ai12s/ai12-0258-1.txt?rev=1.1) ...hope the example replacement implementation I sent made it more obvious that it wasn't the Controlled nature of the vector element per se that I had concerns about (although I think they have the potential to make things worse...I could always grab a scarce system resource via the Controlled type's Initialize subprogram)...it was the initialisation of objects that logically don’t exist yet *at all*...even simple records with an Integer value with default initial value. See example with very large array of default initialized elements.

His point is that if you have a large bounded vector, there might be a large
start-up cost to initialize the entire vector's space for no good reason, if
ultimately only a small portion of the vector is used.  He seems less concerned
about controlling when finalization happens, as many real-time embedded systems
are never expected to terminate (or at least not gracefully ;-).

***************************************************************

From: Randy Brukardt
Sent: Friday, March  9, 2018  3:34 PM

Sure, but this is a problem for arrays in general (it has little to do with the
containers). I'd run into this occassionally in my programs, the only sane thing
to do is to remove the initialization for the component type so that readers and
the compiler both know that it isn't initialized.

You could suppress the initialization by using Import, but that essentially is
just lying about the initialization of the array. And if anyone uses the
uninitialized junk, your program is erroneous (because Import means that you
expect the foreign code to do the needed initialization, if it doesn't do that -
in this case because there is no foreign code - then the code is erroneous by
the blanket rule in Annex B).

If we want the containers to be implementable in Ada, then a bounded container
(which is built out of an array) is of course going to suffer from the same
problem -- and need the same solution (don't do that if it hurts).

What he really wants is a bounded indefinite container. (Note that the
Bounded_Indefinite_Holders by themselves don't help for this, because they'll
have internal initialization, causing the problem all over again. You need a
real Bounded_Indefinite_Hashed_Map or the like).

***************************************************************

From: Tucker Taft
Sent: Friday, March  9, 2018  3:58 PM

I already gave him that advice, but agreed to pass along his concern.  He claims
that the C++ bounded vectors don't have this problem, and so are many times
faster.  Sigh...

And yes, I think we should probably offer Bounded_Indefinite_Vectors, at least.

***************************************************************

From: Randy Brukardt
Sent: Friday, March  9, 2018  11:42 PM

I can write an AI to that effect (including the wording needed), but don't want
to bother if there is a lot of opposition.

As I previously noted, because of Janus/Ada code shared generics, a
Bounded_Indefinite_Vectors would probably be a lot more efficient than the other
forms (assuming that all of the forms are written in Ada).

***************************************************************

From: Tucker Taft
Sent: Saturday, March 10, 2018  9:02 AM

> I can write an AI to that effect (including the wording needed), but
> don't want to bother if there is a lot of opposition.

No opposition on my end, of course.

***************************************************************

From: Bob Duff
Sent: Saturday, March 10, 2018  9:41 AM

I would rather either do nothing, or fix the problem properly (as C++ does,
using "placement new"). And I don't have the energy to determine whether the
"proper" solution is feasible, so I reluctantly advocate doing nothing.  We have
more important things to do.

***************************************************************

From: Tucker Taft
Sent: Saturday, March 10, 2018  9:56 AM

I believe our customer implemented a version that does the "right" thing for
bounded containers, at least in his view.   I presume he used tricks with byte
arrays and address clauses and/or perhaps the storage-subpool feature. He
doesn't seem to object to the current implementation of unbounded containers, as
these generally start small and grow incrementally, so there is no massive
one-time default initialization expense.

I think bounded indefinite containers make perfect sense for other reasons, and
would be a welcome addition to the language without much expense from a
specification or implementation point of view, and as a side-effect they would
provide "precise" initialization/finalization semantics.

***************************************************************

From: Randy Brukardt
Sent: Saturday, March 10, 2018  7:52 PM

> I would rather either do nothing, or fix the problem properly (as C++
> does, using "placement new").
> And I don't have the energy to determine whether the "proper"
> solution is feasible, so I reluctantly advocate doing nothing.  We
> have more important things to do.

"Placement New" itself is no real problem -- the Janus/Ada implementation uses
something like it to initialize all objects. For record types, this is
materialized into a procedure "thunk" which takes the address of the memory to
initialize. (Allocation is done separately, since it might come from the heap, a
user-defined storage pool, or the stack.)

The real problem with it from an Ada perspective is "what happens to whatever
was there previously?". If we were to somehow declare that the memory is truly
uninitialized, then you have a new way to introduce erroneousness (I surely hope
that a discontiguous object whose other parts are missing is erroneous!!). And
you've abandoned the guarantee that every object of an initialized type is
initialized. That seems to be the wrong direction to move for a language
primarily intended for safety-critical work.

If the previous contents are initialized, then (A) we have to figure out what to
do with those contents (especially in cases like controlled and protected
objects), and (B) we haven't really fixed anything.

So the 30 second think on the topic suggests that "placement new" is the wrong
thing for Ada. (I suppose one could come to a different conclusion if one spent
more time thinking about the topic -- but, like Bob, I don't have the energy --
or budget -- for that.)

***************************************************************

From: Tucker Taft
Sent: Sunday, March 11, 2018  10:43 AM

My sense is that the storage subpool stuff (13.11.{4,5,6}) would be almost
exactly what you want for bounded indefinite containers.  You create a subpool
to represent the bounded container, and then use an allocator identifying that
subpool each time a new element is created in the container, and you do an
unchecked deallocation each time you delete an element, and you reclaim the
whole subpool when the container goes away.  Presuming this approach is viable,
this makes bounded indefinite containers pretty easy for an (Ada 2012)
implementation to support.

***************************************************************

From: Randy Brukardt
Sent: Monday, March 12, 2018  8:11 PM

Subpools might lead to fragmentation, since the Inserts for various containers
of the type could be interleaved.

I had an even easier idea, although it turns out to have a problem.
Essentially, each container includes a pool object (with trivial initialization
and finalization so it doesn't act controlled). That object is declared
something like (the types aren't right and none of the checking code - for size,
alignment, and deallocation - is shown):

   type Bounded_Pool (Size, Capacity : Natural) is record
      Data : Storage_Elements (0 .. Size);
      Is_Allocated : Bool_Array (1 .. Capacity) := (others => False);
   end record;

   procedure Allocate(
      Pool : in out Bounded_Pool;
      Storage_Address : out Address;
      Size_In_Storage_Elements : in Storage_Elements.Storage_Count;
      Alignment : in Storage_Elements.Storage_Count) is
      Slot : Natural := 0;
   begin
      -- Find an unallocated slot:
      for I in Is_Allocated'Range loop
         if not Is_Allocated(I) then
	      Slot := I;
            exit;
         end if;
      end loop;
      -- Aside: Tucker can probably turn the above into a reduction
	-- expression, even though it has nothing to do with reduction per-se. :-)
      if Slot = 0 then
         raise Storage_Error; -- Full.
      end if;
      Pool.Is_Allocated(Slot) := True;
      Storage_Address := Pool.Data((Slot-1) * Size)'Address;
   end Allocate;

   procedure Deallocate(
      Pool : in out Root_Storage_Pool;
      Storage_Address : in Address;
      Size_In_Storage_Elements : in Storage_Elements.Storage_Count;
      Alignment : in Storage_Elements.Storage_Count) is
      Offset : Address;
   begin
      Offset := Storage_Address - Pool.Data(0)'Address;
      Pool.Is_Allocated ((Offset / Size)+1) := False;
   end Deallocate;

The implementation for Janus/Ada or any implementation with discontiguous
objects would be more complicated, but the idea remains the same. (Since the use
of this pool is in lock-step with it's definition, one can use some extra
operations to delineate the boundaries of each object, in which case one just
needs a high-water mark in the current slot for allocation.)

The problem with this is that the Size discriminant is clearly a function of the
Capacity discriminant (probably actually a function in order to do rounding up
for alignment), and that is illegal by 3.8(12).

That is, the component needs to be something like:
     type Bounded_List (Capacity : Natural) is record
         My_Pool : Bounded_Pool (Capacity*Element_Size, Capacity);

which is not allowed by Ada. The only way that I know to get around that is
allocate this from some global storage pool, which is not a problem for
Janus/Ada (since everything pretty much uses the heap anyway, worrying about one
more use is silly) -- but it defeats the purpose in safety-critical systems that
don't allow using the heap.

I recall that Steve had some of his usual unlikely examples to demonstrate why
lifting 3.8(12) wasn't a good idea, even though this particular case wouldn't be
a problem. I think.

It seems nasty that the idea of Bounded_Indefinite containers would fall apart on such a minor implementation issue.

***************************************************************

From: Tucker Taft
Sent: Monday, March 12, 2018  8:42 PM

> Subpools might lead to fragmentation, since the Inserts for various
> containers of the type could be interleaved.

I don't follow.  I am presuming each bounded container object would get its own subpool.

...
>      -- Aside: Tucker can probably turn the above into a reduction
> 	-- expression, even though it has nothing to do with reduction per-se. :-)

I suppose the following would work (but be delightfully inefficient):

   (for I in reverse Is_Allocated'Range => (if not Is_Allocated(I) then I else <0>))

***************************************************************

From: Randy Brukardt
Sent: Monday, March 12, 2018  9:12 PM

> > Subpools might lead to fragmentation, since the Inserts for various
> > containers of the type could be interleaved.
>
> I don't follow.  I am presuming each bounded container object would
> get its own subpool.

Generally, subpools allocate out of a shared memory space. If, on the other
hand, each subpool has it's own memory space that's part of the container, then
that's not an issue. But then it seems that there isn't any use to the shared
pool object. And it seems that you'd have the same problem declaring the
subpool's data area (can't use a formula of a discriminant in a type
declaration) as I had with a separate pool in each container.

...

> >      -- Aside: Tucker can probably turn the above into a reduction
> > 	-- expression, even though it has nothing to do with reduction
> > per-se. :-)
>
> I suppose the following would work (but be delightfully inefficient):
>
>    (for I in reverse Is_Allocated'Range => (if not
> Is_Allocated(I) then I else <0>))

This is missing the selection part.

I was thinking something like:

    (for I in Pool.Is_Allocated'Range when Pool.Is_Allocated(I) => I)'Reduce(Natural'Min, Natural'Last);

Assuming you get 100% of your wants in this area. It would be inefficient if the
compiler didn't recognize this case and stop the iteration early. (Since I is
steadily increasing, and 'Min is just looking for the smallest value, once it
"hits" there's no use in continuing.) And, for me at least, it is rather tricky.

If you wanted to get trickier still and care even less about efficiency, you
could use an array aggregate:

    (declare
        Find_Slot : Natural_Array := (for I in Pool.Is_Allocated'Range when Pool.Is_Allocated(I) => I);
     begin
        (if Find_Slot'Length = 0 then raise Storage_Error else Find_Slot(Find_Slot'First)))

Here, the compiler would know the lifetime of Find_Slot is really short and
could try to optimize some or all of it away (only the first component is ever
referenced, after all). Probably would need a pretty fancy compiler, though.

Functional programming is way cool, huh??? :-)

Aside: I didn't think these aggregate iterators included "reverse" since the
order of evaluation is unspecified??

***************************************************************

From: Tucker Taft
Sent: Monday, March 12, 2018  9:27 PM

>>> Subpools might lead to fragmentation, since the Inserts for various
>>> containers of the type could be interleaved.
>>
>> I don't follow.  I am presuming each bounded container object would
>> get its own subpool.
>
> Generally, subpools allocate out of a shared memory space.

Not in my world!  The whole point of subpools in my world view is to support
rapid deallocation, meaning they aren't interspersed in some shared memory
space.

> If, on the other
> hand, each subpool has it's own memory space that's part of the
> container, then that's not an issue.

Yes, that was always my model of subpools.

> But then it seems that there isn't any use to the shared pool object.

It keeps track of which is the default subpool.  It could also keep track of
empty blocks that are released when a subpool is released, rather than returning
them back to the O/S.

> And it seems that you'd have the same problem declaring the subpool's
> data area (can't use a formula of a discriminant in a type
> declaration) as I had with a separate pool in each container.

I didn't understand the problem you were trying to solve.  I presumed the user
would specify the size of the bounded indefinite container in storage units, not
in number of elements, since the size of the elements would typically vary, and
what they care about is bounding the total space occupied by the container.
E.g.:

  type Vector (Space : Storage_Count) is tagged private;

> ...
>>>     -- Find an unallocated slot:
>>>     for I in Is_Allocated'Range loop
>>>        if not Is_Allocated(I) then
>>> 	      Slot := I;
>>>           exit;
>>>        end if;
>>>     end loop;
>>>     -- Aside: Tucker can probably turn the above into a reduction
>>> 	-- expression, even though it has nothing to do with reduction per-se. :-)
>>
>> I suppose the following would work (but be delightfully inefficient):
>>
>>   (for I in reverse Is_Allocated'Range => (if not
>> Is_Allocated(I) then I else <0>))
>
> This is missing the selection part.

I did it in reverse so the first element would be last ;-)  That is why I said
it was delightfully inefficient.  But you are right, a filter would make more
sense...
...

***************************************************************

From: Randy Brukardt
Sent: Tuesday, March 13, 2018  12:01 AM

> > But then it seems that there isn't any use to the shared pool object.
>
> It keeps track of which is the default subpool.  It could also keep
> track of empty blocks that are released when a subpool is released,
> rather than returning them back to the O/S.

I don't think you would want to allocate anything from a default subpool.
Remember one of the purposes of these guys is to be used in environments where
dynamic allocation isn't allowed. Ideally, these allocators would map directly
into an array of bytes.

> > And it seems that you'd have the same problem declaring the
> > subpool's data area (can't use a formula of a discriminant in a type
> > declaration) as I had with a separate pool in each container.
>
> I didn't understand the problem you were trying to solve.  I presumed
> the user would specify the size of the bounded indefinite container in
> storage units, not in number of elements, since the size of the
> elements would typically vary, and what they care about is bounding
> the total space occupied by the container.  E.g.:
>
>   type Vector (Space : Storage_Count) is tagged private;

I was following the model of the Bounded_Indefinite_Holder: there is a generic
parameter which specifies the maximum number of storage units for each element.
And to minimize the differences with the regular bounded containers, a Capacity
discriminant. The above would seem to maximize the differences without any added
benefit.

For each container, the model was that the underlying data was an array of fixed
size buckets, each the size specified by the generic parameter. This model
eliminates any possibility of fragmentation; the reason for using a pool at all
is to get the effect of placement new. Thus, the pool is just divvying up a
array. If you used "normal" allocation, then you have all of the possibilities
for fragmentation that scares these safety-critical folks.

So the allocation size is the max size of one element times the capacity
(adjusted as needed for alignment).

Just letting the user set the size this way doesn't fix anything, since one then
would have to calculate the capacity. (One needs a sane bound on the number of
elements in the pool.) And that requires an expression (again, taking into
account the alignment of the element type). Again, you could do that with a heap
allocation, but again, the safety critical people would not be happy.

***************************************************************

From: Tucker Taft
Sent: Tuesday, March 13, 2018  7:44 AM

> I don't think you would want to allocate anything from a default subpool.

In this case, I agree.  I was taking about my more general model of subpools,
where the pool object could be used to keep track of large blocks from which
subpool blocks are allocated, as well as a pointer to the current default
subpool.  In this case of bounded indefinite containers, I am not sure the
shared pool object would be used for much, but that seems fine.

> Remember one of the purposes of these guys is to be used in environments
> where dynamic allocation isn't allowed. Ideally, these allocators would map
> directly into an array of bytes.

In many of these environments, they allow dynamic allocation within an overall
bounded pool during library unit elaboration, and then things are locked down.
Or they allow allocation within a bounded pool, but no deallocation.

...
>>I didn't understand the problem you were trying to solve.  I
>>presumed the user would specify the size of the bounded
>>indefinite container in storage units, not in number of
>>elements, since the size of the elements would typically
>>vary, and what they care about is bounding the total space
>>occupied by the container.  E.g.:
>>
>>  type Vector (Space : Storage_Count) is tagged private;
>
>I was following the model of the Bounded_Indefinite_Holder: there is a
>generic parameter which specifies the maximum number of storage units for
>each element.

We had different ideas of how to generalize Bounded_Indefinite_Holder.  I saw
the original limit as a maximum for the holder as a whole, which had a single
element.  The generalization to multiple elements I imagined was to specify a
maximum for the container as a whole, which now might have a variable number of
elements of differing sizes.  That is, I was bounding the total, not the
individual elements.   If the user wanted to bound the individual elements, they
could use the existing bounded (definite) containers, and use  a variant record
with defaults, or wrap each element in a holder.

>And to minimize the differences with the regular bounded
>containers, a Capacity discriminant. The above would seem to maximize the
>differences without any added benefit.

I don't agree.  By bounding each individual element, you are introducing an
enormous potential for "internal" fragmentation, just to avoid external
fragmentation (where "internal" fragmentation means waste due to rounding-up the
size of individual elements, while external fragmentation means waste due to
deallocations that leave holes that can't be re-used -- see
https://en.wikipedia.org/wiki/Fragmentation_(computing)).

For example, if I created a "string pool" which stored strings in a
bounded-indefinite-vector pool, and then used the indices into the vector as a
short index for each string, I certainly wouldn't want to bound each individual
string.

>For each container, the model was that the underlying data was an array of
>fixed size buckets, each the size specified by the generic parameter. This
>model eliminates any possibility of fragmentation

(eliminates *external* fragmentation in favor of potentially huge *internal*
fragmentation -- see ref above);

>; the reason for using a
>pool at all is to get the effect of placement new. Thus, the pool is just
>divvying up a array. If you used "normal" allocation, then you have all of
>the possibilities for fragmentation that scares these safety-critical folks.

Fragmentation is never pleasant, but it is not clear that huge internal
fragmentation is better than a potential for external fragmentation, especially
in cases where deallocation is relatively rare compared to allocation.
Certainly the most important thing is to have an upper bound on the total space
devoted to a given data structure.  Given the ability to create a "definite"
type either by using defaults for the discriminants or wrapping each element in
a holder, I don't see the need to force internal fragmentation on the user of
bounded *indefinite* containers.

What I see the user wants is the equivalent of a storage-sized access
collection, but where you can have a separate "collection" for each container
object.  Ada's access-type model requires a separate access *type* for each such
collection, but with containers, you want a separate "collection" for each
container *object*.  And this is where subpools help, but not if you force the
individual elements to each occupy the same amount of space.

>So the allocation size is the max size of one element times the capacity
>(adjusted as needed for alignment).

As indicated above, we were working from different assumptions.  I suggest there
is no point in proceeding further until we agree on the fundamental model --  a
single bound for the total size vs. two bounds, one for the total size and one
for each element.  To me, *indefinite* containers implies that individual
elements will occupy different amounts of space.  The only "bound" for such a
container refers to the total amount of space the container occupies.

***************************************************************

From: Randy Brukardt
Sent: Tuesday, March 13, 2018  4:29 PM

...
>>Remember one of the purposes of these guys is to be used in
>>environments where dynamic allocation isn't allowed. Ideally, these
>>allocators would map
>>directly into an array of bytes.

>In many of these environments, they allow dynamic allocation within an overall
>bounded pool during library unit elaboration, and then things are locked down.
>Or they allow allocation within a bounded pool, but no deallocation.

Sure, but then one doesn't need a special container. If you have a way to verify
that no deletes are being used, any container will work for that. Even better
would be a container kind that takes a storage pool (then that storage pool just
doesn't implement any deallocation).

>> I was following the model of the Bounded_Indefinite_Holder: there is
>> a generic parameter which specifies the maximum number of storage
>> units for each element.

>We had different ideas of how to generalize Bounded_Indefinite_Holder.
>I saw the original limit as a maximum for the holder as a whole, which
>had a single element.  The generalization to multiple elements I
>imagined was to specify a maximum for the container as a whole, which
>now might have a variable number of elements of differing sizes.  That
>is, I was bounding the total, not the individual elements.

That requires a totally general storage pool (supporting arbitrary allocates and
deletes in any order). And then there is literally nothing bounded about the
container other than the use of this pool -- all of the nodes and other internal
data structures also have to be allocated from this object.

For users like the original proposer, all of this complication and uncertainty
would be unacceptable. They could simplify their applications by avoiding
deletes and replaces (but the original proposer wanted to specifically do such
things), or more likely they'd just ban the use of these containers.

>If the user wanted to bound the individual elements, they could use the
>existing bounded (definite) containers, and use  a variant record with
>defaults, or wrap each element in a holder.

All of those would force initialization of all of the elements when they are
created (since a holder object requires at a mimimum nulling its internal
pointer). Leaving the secondary problem unsolved.

>>And to minimize the differences with the regular bounded containers, a
>>Capacity discriminant. The above would seem to maximize the
>>differences without any added benefit.

>I don't agree.  By bounding each individual element, you are
>introducing an enormous potential for "internal" fragmentation, just to
>avoid external fragmentation (where "internal" fragmentation means
>waste due to rounding-up
>the size of individual elements, while external fragmentation means
>waste due to deallocations that leave holes that can't be re-used --
>see https://en.wikipedia.org/wiki/Fragmentation_(computing)).

That's a massive abuse of the term "fragmentation". Fragmentation ("external" in
this article "with multiple issues") is bad because it is unpredictable. Waste
is bad its own way, but one thing it is not is unpredictable. The only way to
get rid of fragmentation is to increase waste, so it is a trade-off. If one uses
the term fragmentation for both things, then it is impossible to get rid of
fragmentation. Obviously, who ever came up with this terminology never dealt
with safety-critical systems and their programmers!

Note that the references in this article are "the PC guide" and some Symantec
document -- those are hardly reliable references to a CS term -- I believe it
more if it was "Knuth" or some Stanford documents. I suspect hardly anyone has
heard of "internal fragmentation" unless they've read this article.

>For example, if I created a "string pool" which stored strings in a
>bounded-indefinite-vector pool, and then used the indices into the
>vector as a short index for each string, I certainly wouldn't want to
>bound each individual string.

You also wouldn't want to use this sort of container, because you'd end up
wasting substantial space storing bounds that are trivial to reconstruct. You
might remember that Matt had proposed special string-keyed maps for this very
reason, but those got dumped early on. (The only "container" that I use
regularly is a string-to-index map - there is no counterpart in Ada.Containers.)

>>For each container, the model was that the underlying data was an
>>array of fixed size buckets, each the size specified by the generic
>>parameter. This model eliminates any possibility of fragmentation

>(eliminates *external* fragmentation in favor of potentially huge *internal*
>fragmentation -- see ref above);

Eliminates the unpredictability of fragmentation by the predictability of memory
usage! Waste is the only way to do that.

>>; the reason for using a
>>pool at all is to get the effect of placement new. Thus, the pool is
>>just divvying up a array. If you used "normal" allocation, then you
>>have all of the possibilities for fragmentation that scares these
>>safety-critical folks.

>Fragmentation is never pleasant, but it is not clear that huge internal
>fragmentation

...please call this "waste". It has none of the characteristics of
fragmentation!

>...is better than a potential for external fragmentation, especially in cases
>where deallocation is relatively rare compared to allocation. Certainly the
>most important thing is to have an upper bound on the total space devoted to a
>given data structure.  Given the ability to create a "definite" type either by
>using defaults for the discriminants or wrapping each element in a holder, I
>don't see the need to force internal fragmentation on the user of bounded
>*indefinite* containers.
>
>What I see the user wants is the equivalent of a storage-sized access
>collection, but where you can have a separate "collection" for each container
> object.

That's definitely not what the original proposer was looking for; recall that he
wanted "bounded" class-wide components. Those necessarily have some waste
per-element.

>Ada's access-type model requires a separate access *type* for each such
>collection, but with containers, you want a separate "collection" for
>each container *object*.  And this is where subpools help, but not if
>you force the individual elements to each occupy the same amount of space.

Don't see the "but" here; the same is true regardless of what type of pool one
uses. (Wanting separate "collections" seems orthogonal to how allocations are
done in each collection.)

>>So the allocation size is the max size of one element times the
>>capacity (adjusted as needed for alignment).

>As indicated above, we were working from different assumptions.  I
>suggest there is no point in proceeding further until we agree on the
>fundamental model --  a single bound for the total size vs. two bounds,
>one for the total size and one for each element.  To me, *indefinite*
>containers implies that individual elements will occupy different amounts of
>space. >The only "bound" for such a container refers to the total amount of
>space the container occupies.

I was going to suggest that we instead focus on a bounded container (bounded in
number of elements) that passes in a storage pool for allocating to indefinite
components. Then the user can do whatever they like in that pool.

But that doesn't completely work, because the pool needs to be able to find out
the capacity of the actual container object. Probably would have to pass in the
pool *type*, as a type derived from some special abstract pool with appropriate
discriminants.

I can propose something on this line tomorrow if you want to see it fleshed out
a bit more. Otherwise, I think we have to drop this idea (I don't think we could
- or necessarily should try to - agree on how memory should be allocated).

And there is a much bigger problem. You finally got through my fat head of why
you have to use subpools here - the issue that you can only have one pool per
access type. For some reason, I was thinking of a pool object per container and
thus essentially a access type per container. But that doesn't seem to be a
possibility in Ada (or is there, see below).

But the use of subpools is problematical, as it prevents the
Bounded_Indefinite_xxx containers from being Pure. There has to be a global pool
object for the (global) access type to use, one that manages the subpools. That
violates the Pure restrictions. Worse, I don't see any way to implement that
object for an unbounded number of holders (or any other container) without
either using non-trivial finalization or dynamic allocation. Which both are
out-of-bounds for such containers.

So I don't think a subpool implementation would fly. It has to be one pool
object per container, no strings attached. That would require a headstanding
implementation using local access types (declared in Insert and Delete),
'Unchecked_Access (to strip the accessibility info), and type conversions to the
more global type. Yuck (but less yucky than a subpool implementation that
violates the basic requirements).

***************************************************************

From: Tucker Taft
Sent: Tuesday, March 13, 2018  5:02 PM

Not sure this discussion makes sense since we have different models in mind, but
I'll try to clarify my views one last time...

>> We had different ideas of how to generalize Bounded_Indefinite_Holder.  I
>> saw the original limit as a maximum for the holder as a whole, which had a
>> single element.  The generalization to multiple elements I imagined was to
>> specify a maximum for the container as a whole, which now might have a
>> variable number of elements of differing sizes.  That is, I was bounding
>> the total, not the individual elements.
>
> That requires a totally general storage pool (supporting arbitrary allocates
> and deletes in any order). And then there is literally nothing bounded about
> the container other than the use of this pool -- all of the nodes and other
> internal data structures also have to be allocated from this object.

I was always presuming the key thing to bound was the total amount of storage
used, and the implementation *I* envisaged for a storage subpool encapsulated
all of the storage needed to maintain free lists, etc.  If your storage subpool
doesn't work that way, then it wouldn't be the right thing to use for
implementing the bounded indefinite containers.  We don't need to argue about
how to implement storage subpools.  I was simply indicating that *if* you
implemented storage subpools the way *I* imagined, then bounded indefinite
containers could piggy back on that implementation.  If you implement them some
different way, then you can't.

>For users like the original proposer, all of this complication and
>uncertainty would be unacceptable. They could simplify their applications by
>>avoiding deletes and replaces (but the original proposer wanted to
>specifically do such things), or more likely they'd just ban the use of
>these containers.

We certainly don't need to agree whether storage subpools are relevant here.  We
do need to agree on what exactly do bounded indefinite containers bound.  My
proposal is that they bound the total amount of storage used, but don't force
each element to use the same amount of space.  Let's try to get some consensus
on that issue first, if we can.  If we can't, then I don't see any point in
further discussion.

>>If the user wanted to bound the individual elements, they could use the
>>existing bounded (definite) containers, and use  a variant record with
>>defaults, or wrap each element in a holder.
>
>All of those would force initialization of all of the elements when they are
>created (since a holder object requires at a mimimum nulling its internal
>pointer). Leaving the secondary problem unsolved.

The model I had in mind is still not clear, I guess.  I was presuming that you
just have "raw" space until an element is added to the container.  When you add
the element, you do the equivalent of a "new," and if you were to use my
envisaged model of storage subpools, then you could actually use the Ada 2012
subpool allocator.  If not, then you will need some other magic, which might
still be based on the subpool allocator feature (to get the finalization scope
right), but might be a very special implementation of subpools not useful for
anything else.  In any case, the key point is that you are converting "raw"
space into an object, and at that point the initialization would take place.
Similarly, when you remove an element from the container, you would use
something very close to Unchecked_Deallocation, to do the finalization.  And
when the container as a whole went away, you would do something analogous to
finalizing the whole storage subpool, which would finalize the eleme s that
still exist in the container.  Alternatively, you could iterate through the
container and individually finalize the remaining elements.


>>By bounding each individual element, you are introducing
>>an enormous potential for "internal" fragmentation, just to avoid external
>>fragmentation (where "internal" fragmentation means waste due to rounding-up
>>the size of individual elements, while external fragmentation means waste
>>due to deallocations that leave holes that can't be re-used -- see
>>https://en.wikipedia.org/wiki/Fragmentation_(computing)).
>
>That's a massive abuse of the term "fragmentation". ...

Well that matches the definition of fragmentation that at least I am familiar
with, and appears in many books and various online courses.  So I would suggest
you use the term "external fragmentation" if that is the only kind of
fragmentation you are interested in.

...
>Note that the references in this article are "the PC guide" and some
>Symantec document -- those are hardly reliable references to a CS term -- I
>believe it more if it was "Knuth" or some Stanford documents. I suspect
>hardly anyone has heard of "internal fragmentation" unless they've read this
>article.

For what it is worth, see also:

  http://www.cis.upenn.edu/~lee/03cse380/exam3-v8.pdf  (first question in the exam ;-)

  https://courses.cs.washington.edu/courses/cse451/00sp/misc/quiz2sol.txt (also first exam question)

  https://www.quora.com/What-are-the-differences-between-internal-fragmentation-and-external-fragmentation

  https://techdifferences.com/difference-between-internal-and-external-fragmentation.html

etc, etc.

A google search for "internal fragmentation vs. external fragmentation" will
provide you with approximately 131,000 results... ;-)

***************************************************************

From: Randy Brukardt
Sent: Tuesday, March 13, 2018  5:44 PM

>Not sure this discussion makes sense since we have different models in
>mind, but I'll try to clarify my views one last time...

I don't think it really matters. If we need to support your view and my view
(and I can see arguments for that), then we have to allow passing in a storage
pool so the user can deal with it. Otherwise, there is no point in continuing,
because what you are proposing wouldn't be useable by the "original proposer",
which makes the utility dubious to me. They are looking for absolute
predictability, and definitely don't want to give up Replace and Delete
operations to get it (reading between the lines).

>>>We had different ideas of how to generalize
>>>Bounded_Indefinite_Holder.  I saw the original limit as a maximum for
>>>the holder as a whole, which had a
>>>single element.  The generalization to multiple elements I imagined was to
>>>specify a maximum for the container as a whole, which now might have
>>>a variable number of elements of differing sizes.  That is, I was
>>>bounding the total, not the individual elements.

>>That requires a totally general storage pool (supporting arbitrary allocates
>>and deletes in any order). And then there is literally nothing bounded about
>>the container other than the use of this pool -- all of the nodes and other
>>internal data structures also have to be allocated from this object.

>I was always presuming the key thing to bound was the total amount of
storage used, ...

Not for the "original proposer". In his environment, he was using machine-code
level verification, so the complexity of the implementation also comes into
play. He was looking for arbitrary operations on class-wide types, thus the
holder definition that we came up with.

The regular bounded pools are designed to meet similar requirements (bounded
pools by their definition waste vast amounts of memory; you use them because you
value predictability). I've been assuming that those requirements carry over to
any other "bounded" form pools.

>and the implementation *I* envisaged for a storage subpool encapsulated
>all of the storage needed to maintain free lists, etc.  If your storage
>subpool doesn't work that way, then it wouldn't be the right thing to
>use for implementing the bounded indefinite containers.  We don't need
>to argue about
>how to implement storage subpools.  I was simply indicating that *if*
>you implemented storage subpools the way *I* imagined, then bounded
>indefinite containers could piggy back on that implementation.  If you
>implement them some different way, then you can't.

Umm, there is no standard definition of a subpool; the language doesn't define
one. *I* personally don't have any such implementations as I've never had a good
use for them. In any case, any subpool implementation used here requires a
global pool object -- which is incompatible with a Pure package. Ergo, you can't
use a subpool to implement these containers, even if is seems reasonable to do
so.

Anyway, this implementation would not meet any of the requirements of the other
kinds of "bounded" containers: it couldn't be Pure; it would need either
finalization or heap allocation to track the existing subpools; and it wouldn't
eliminate "external" fragmentation if Replace/Delete is used. Sounds like it
wouldn't meet the usual safety-critical requirements, and it would barely differ
from the usual unbounded containers.

>We certainly don't need to agree whether storage subpools are relevant here.
>We do need to agree on what exactly do bounded indefinite containers bound.
>My proposal is that they bound the total amount of storage used, but
>don't force each element to use the same amount of space.  Let's try to
>get some consensus on that issue first, if we can.  If we can't, then I
>don't see any point in further discussion.

I think that is quite the wrong question at this point. We should leave that
question up to the user, because I can see at least two use-cases that still
meeting the safety-critical restrictions:
  (1) An allocate-only pool used with container objects that doesn't
      Replace/Delete elements -- bounding just the memory is fine.
  (2) A "blocked" pool that supports full functionality -- again, no
      non-determinism so we're fine. -- One has to bound two of the total
      memory, the container capacity, and the maximum element size.
There's a third use case for the rest of us:
  (3) A full pool implementation, we just want deterministic memory usage and
     deterministic (and lazy) initialization.

That's three separate storage pool implementations, and it's pretty clear to me
that one size does not fit all here. We're not going to have three kinds of
containers in the Standard, so the only question is whether we can design one
that actually allows all three use cases by letting the user choose their
storage pool.

If not, we should drop the subject. Do you want me to try, or forget it??

>>>If the user wanted to bound the individual elements, they could use
>>>the existing bounded (definite) containers, and use  a variant record
>>>with defaults, or wrap each element in a holder.

>>All of those would force initialization of all of the elements when they are
>>created (since a holder object requires at a minimum nulling its
>>internal pointer). Leaving the secondary problem unsolved.

>The model I had in mind is still not clear, I guess.  I was presuming
>that you just have "raw" space until an element is added to the container. ...

Huh? You said: "the user would use the existing bounded (definite)
containers..." which have the initialization behavior I cited. I was responding
specifically to the suggestion that a user that wanted to bound individual
elements should just use holders or variants in an existing definite container.

That, after all, is indeed the current state of the Standard, and we would have
never started this discussion if that was an adequate solution! You essentially
are saying that you can have one of memory certainty or sane initialization, but
not both. Sounds weird to me.

>>That's a massive abuse of the term "fragmentation". ...

>Well that matches the definition of fragmentation that at least I am
>familiar with, and appears in many books and various online courses.
>So I would suggest you use the term "external fragmentation" if that is
>the only kind of fragmentation you are interested in.

The reason I hate this is that it implies that fragmentation is a problem that
cannot be solved -- since the only way to get rid of "external fragmentation" is
to increase waste (padding bits, fixed size allocates, etc.). But the issue of
concern is predictability, and these supposedly similar views have very
different characteristics for that issue.

In any case, you felt it necessary to explain "internal fragmentation" in your
original post, so you must not have intuitively thought that the term was very
obvious. QED. :-)

'nuff on that.

***************************************************************