Unconstrained Arrays

[belteshazzar]

I have a program that uses a lot of different sized arrays and passed
into math functions. So I'm using an unconstrained array type. The
problem that I have is that I'm not allowed to use "new" this means
that I have to use pools (which I can't because to intantiate a pool I
have to constrain the array type) or allocated the arrays on the
stack. Allocating the arrays on the stack is fine, BUT it means that i
have to use array initializers so that they remain unconstrained
rather than becoming an anonomous contrained type that can no longer
be passed to my math functions.

We have now noticed that because of the size of our arrays that the
array intialisation is causing significant performance issues. Thus,
we need a new way of handling our arrays.

The best option seems to be to turn the functions that take arrays
into generic functions and instantiate them on the fly according to
the required size. Does anyone know if there are performance issues
with dynamically creating instantiations of generic functions all over
teh place?

Also, and the main point of my post, I've found that I can place the
unconstrained array inside a record with a distriminant and this seems
to solve all our problems. We don't have to use array initialisers and
we can get pointers to aliased objects that can be easily passed to
the math functions.

Has anyone come across these sorts of issues? I'm curious as to the
solution that others have found, and why Ada seems to handle
unconstrained arrays differently to unconstrained arrays inside a
record.

[Jeffrey R. Carter]

belteshazzar wrote:
> I have a program that uses a lot of different sized arrays and passed
> into math functions. So I'm using an unconstrained array type. The
> problem that I have is that I'm not allowed to use "new" this means
> that I have to use pools (which I can't because to intantiate a pool I
> have to constrain the array type) or allocated the arrays on the
> stack. Allocating the arrays on the stack is fine, BUT it means that i
> have to use array initializers so that they remain unconstrained
> rather than becoming an anonomous contrained type that can no longer
> be passed to my math functions.

I'm not clear what you're talking about. You can pass a constrained subtype to a
subprogram that takes a parameter of an unconstrained array type.

For example, String is an unconstrained array type. If we have

function F (S : in String) return Natural;

V : String (1 .. 10);
C : Natural;

then it's perfectly legal to call F with V as its actual parameter:

C := F (S);

> Also, and the main point of my post, I've found that I can place the
> unconstrained array inside a record with a distriminant and this seems
> to solve all our problems. We don't have to use array initialisers and
> we can get pointers to aliased objects that can be easily passed to
> the math functions.

Here is your problem. There should be no reason to pass explicit pointers to
these functions. Your best solution is to rewrite or change your library.

--
Jeff Carter
"Drown in a vat of whiskey. Death, where is thy sting?"
Never Give a Sucker an Even Break
106

[belteshazzar]

On Mar 17, 11:49 am, "Jeffrey R. Carter"

As we have very large array's we're using something like:

type Unconstrained_Array is array ( Integer range <> ) of Integer;
type Unconstrained_Array_Pointer is access all Unconstrained_Array;

procedure F (S : in Unconstrained_Array_Pointer);

V : Unconstrained_Array := (1 .. 10_000 => 0);
V_Ptr : Unconstrained_Array_Ptr :=
Unconstrained_Array'unchecked_Access

F (V_Ptr);

Note the use of the array intialiaser, if this isn't used then the
pointer is no longer compatible.

[Jeffrey Creem]

I think the problem here is you are assuming you need to pass a pointer
to the function in order to avoid a copy. This is an incorrect assumption.
Just make the function take in the unconstrained array. No large copy
will be made.

[Jeffrey R. Carter]

belteshazzar wrote:
>
> type Unconstrained_Array is array ( Integer range <> ) of Integer;
> type Unconstrained_Array_Pointer is access all Unconstrained_Array;
>
> procedure F (S : in Unconstrained_Array_Pointer);
>
> V : Unconstrained_Array := (1 .. 10_000 => 0);
> V_Ptr : Unconstrained_Array_Ptr :=
> Unconstrained_Array'unchecked_Access
>
> F (V_Ptr);

If you do

procedure F (S : in Unconstrained_Array);

V : Unconstrained_Array (-10_000 .. -1);
-- You must do things like this, since your index subtype is Integer.
-- If you intended only positive indices, surely you would use Positive.

F (S => V);

I know of no compiler that will not use pass by reference.

[Adam Beneschan]

As Jeffrey C. and Jeffrey C. have pointed out, you shouldn't use
pointers in your library routines. Declare your library routines to
have parameters of type Unconstrained_Array and don't worry about
access types at all. Ada makes things real simple if you let it.

If for some reason you really need to use a pointer (like maybe your
library is frozen and you can't change it without trying to sneak a
library change requisition form past a vicious CM man-wolf), I think
that in Ada 2005 you can improve performance with something like this:

V : aliased Unconstrained_Array := (1 .. 10_000 => <>);
V_Ptr : Unconstrained_Array_Ptr := V'Unchecked_Access;

This uses the "default" initializer for the element type. Since the
default initializer for Integer is to leave it as undefined garbage,
the compiler shouldn't generate any code to set up the array. No
guarantees, though; your compiler may do something anyway.

Also, if you were able to use 'Unchecked_Access without making V
aliased, your compiler is broken.

-- Adam

[Jeffrey R. Carter]

Jeffrey R. Carter wrote:
>
> I know of no compiler that will not use pass by reference.

Rereading, I realize this may be difficult to understand, especially for those
who are not native English speakers. So I'll rephrase:

Every compiler that I'm familiar with will use pass by reference.

--
Jeff Carter
"My dear Mrs. Hemoglobin, when I first saw you, I
was so enamored with your beauty I ran to the basket,
jumped in, went down to the city, and bought myself a
wedding outfit."

Never Give a Sucker an Even Break

111

[anon]

Most people just use pointer to a string. Then they must write a set of
routines to handle the pointers

But Ada 95 and Ada 2005 contains package called
"Ada.Strings.Unbounded"
which was designed to handle this problem.

Instead of using type "String" you will use "Unbounded_String".

-- For a simplier design:
--
-- From "Ada Problem Solving and Program Design", 1992
--
-- Program 10.9 : Specification Page 504
-- Program 10.10: Gives the Body on Page 508 (not posted)
--
-- Modified for Ada 95. Some comments have been removed
-- easy to adapt for generic package.
--
with Ada.Text_IO ;
package VString is

-- Specification for ADT to handle string variable 1-80 characyer

MaxLength : constant Integer := 80 ;
subtype Index is Integer range 0..MaxLength ;

type VString is Private ;

-- exceptions

StringOverflow : exception ;
EmptyString : exception ;
InvalidArgument : exception ;

-- operators

function MakeVString (S : String) return VString ;
function MakeVString (C : Character) return VString ;
function EmptyVString return VString ;

-- selectors

function Length (S : VString) return Index ;
function Value (S : VString) return String ;
function Head (S : VString) return Character ;

-- inquiry

function IsEmpty (S : VString) return Boolean ;

-- concattenation

function "&" (S1, S2 : VString) return VString ;
function "&" (S1 : VString; C : Character) return VString ;
function "&" (C : Character; S1 : VString) return VString ;
function "&" (S1 : VString; S : String) return VString ;
function "&" (S : String; S1 : VString) return VString ;

-- lexical compariason

function "<" (S1, S2 : VString) return Boolean ;
function "<=" (S1, S2 : VString) return Boolean ;
function ">" (S1, S2 : VString) return Boolean ;
function ">=" (S1, S2 : VString) return Boolean ;

-- search

function locate (Sub : VString; within : VString) return Index ;
function locate (Sub : String; within : VString) return Index ;
function locate (C : Character; within : VString) return Index ;

function Tail (S : String) return VString ;

function substring (S : VString; start, size : Index) return VString ;

-- I/O

procedure Get_Line ( Item : out VString ) ;
procedure Put ( Item : VString ) ;

procedure Get_Line ( File : Ada.Text_IO.File_Type;
Item : out VString ) ;
procedure Put ( File : Ada.Text_IO.File_Type;
Item : VString ) ;

private

type VString is record
CurrentLength : Index := 0 ;
StringPart : String ( 1 .. MaxLength ) :=
( others => Ascii.Nul ) ;
end record ;
end VString ;

[belteshazzar]

>                                 -- Adam- Hide quoted text -
>
> - Show quoted text -

Unfortuantely this is a 2005 feature and we're using 95 ... but thanks
for the tip.

[belteshazzar]

On Mar 18, 3:56 am, "Jeffrey R. Carter"

Unfortuantely this is an optimisation and actually doesn't occur with
optimisation off. (I just ran a test program). I'm told that due to
the significant performance hit of the array initialisers when
optimisation is turned off we can't use that.

[Jeffrey R. Carter]

belteshazzar wrote:
>
> Unfortuantely this is an optimisation and actually doesn't occur with
> optimisation off. (I just ran a test program). I'm told that due to
> the significant performance hit of the array initialisers when
> optimisation is turned off we can't use that.

If your compiler passes a 10,000-component array by copy at any optimization
level, then you have a very poor compiler. If your vendor won't fix this, I'd
recommend using another compiler.

And I'm sure everyone here would appreciate knowing what compiler this is, so we
can avoid it.

--
Jeff Carter
"Mr. President, we must not allow a mine-shaft gap!"
Dr. Strangelove
33

[Peter C. Chapin]

belteshazzar <gbelte...@gmail.com> wrote in
news:386b0e00-a1c6-4c5f...@c11g2000yqj.googlegroups.com:

> Unfortuantely this is an optimisation and actually doesn't occur with
> optimisation off. (I just ran a test program). I'm told that due to
> the significant performance hit of the array initialisers when
> optimisation is turned off we can't use that.

Are those initializers actually necessary?

type Unconstrained_Array is array(Integer range <>) of Integer;

My_Array : Unconstrained_Array(-10_000 .. 10_000);

In the above the array is uninitialized. Yes, you have to provide
constraints, but you don't have to initialize the array here (obviously
you'll need to do so eventually... perhaps as part of your algorithm). The
code you showed use an array aggregate to initialize the array... the
constraints where taken from the initializer. However, there are other ways
to specify the constraints.

Or am I totally confused?

Peter

[sjw]

On Mar 20, 1:53 am, "Peter C. Chapin" <pcc482...@gmail.com> wrote:

There is a deep language-lawyerly reason (which I don't understand)
why an array like your My_Array can't be aliased (at any rate in
Ada95); you have to use the initialize-with-aggregate approach.
Perhaps that's what leads to the initialize-with-aggregate style.

[Jacob Sparre Andersen]

sjw <simon.j...@mac.com> writes:

> There is a deep language-lawyerly reason (which I don't understand)
> why an array like your My_Array can't be aliased (at any rate in
> Ada95); you have to use the initialize-with-aggregate approach.
> Perhaps that's what leads to the initialize-with-aggregate style.

Why doesn't my compiler complain about it then?

And can you please quote the explanation, so the rest of us can
attempt to understand it.

Greetings,

Jacob
--
»When Roman engineers built a bridge, they had to stand under it while
the first legion marched across. If programmers today worked under
similar ground rules, they might well find themselves getting much more
interested in Ada!« -- Robert Dewar

[Jean-Pierre Rosen]

sjw a écrit :

> There is a deep language-lawyerly reason (which I don't understand)
> why an array like your My_Array can't be aliased (at any rate in
> Ada95); you have to use the initialize-with-aggregate approach.
> Perhaps that's what leads to the initialize-with-aggregate style.

Here is an example:

procedure essai is
type Acc is access all String;
V : Acc;
S1 : aliased String := "abcd";
S2 : aliased String (1..4);
begin
V := S1'Access;
V := S2'Access;
end;

And this is what GNAT says:

essai.adb:5:04: warning: aliased object has explicit bounds
essai.adb:5:04: warning: declare without bounds (and with explicit
initialization)
essai.adb:5:04: warning: for use with unconstrained access
essai.adb:8:09: object subtype must statically match designated subtype

The message is pretty explicit. The underlying reason has to do with
dope vectors (i.e. how the bounds of an array are attached to the
array). It might be different, depending on whether the array is
/declared/ constrained or not (S1 is declared unconstrained, although
constrained by initialization).

For example, in the constrained case, the array might include a pointer
to a structure that describes the subtype, while in the unconstrained
case, the array might keep the bounds with the data. Therefore, a
pointer to a constrained array is incompatible with a pointer to an
unconstrained array.
--
---------------------------------------------------------
J-P. Rosen (ro...@adalog.fr)
Visit Adalog's web site at http://www.adalog.fr

[christo...@eurocopter.com]

type Unconstrained_Array is array ( Integer range <> ) of Integer;

type Unconstrained_Array_Pointer is access all Unconstrained_Array;

procedure F (S : in Unconstrained_Array_Pointer);

With the above declarations, the following is illegal:

V : aliased Unconstrained_Array (1 .. 10_000);
V_Ptr: Unconstrained_Array_Ptr := V'[Unchecked_]Access

because V is nominally constrained and the pointer is to nominally
unconstrained objects only.
Thus you have to use

V : aliased Unconstrained_Array := (1 .. 10_000 => 0);
V_Ptr: Unconstrained_Array_Ptr := V'[Unchecked_]Access

Now V is nominally unconstrained, its subtype however is constrained.
The corresponding paragraphs in the RM are admittedly a bit
complicated. See

http://www.christ-usch-grein.homepage.t-online.de/AdaMagica/ThickThin.html

But as was explained to you, you do not need pointers to have call by
reference. The Ada RM specifies exactly for which kind of types you
can rely on call be copy vs call be reference and for which types it
remains unspecified.

For array as yours, it's unspecified - this is because the compile can
then choose the best method. E.g. for a packed boolean array that fits
into a register, call by copy will normally be used for all modes, for
all longer array call be reference for all modes will be used.

There is the famous Robert Dewar rule that no decent compiler does
silly things - and doing a copy of a 10_000 element array surely is
complete nonsense!

Thus use the following and all will be well if you have a decent
compiler. If not, dump it into the bin and complain at the
manufacturer!

procedure F (S: in Unconstrained_Array);

V: Unconstrained_Array (-10_000 .. -1);

F (V); -- call by reference with any decent compiler

[Adam Beneschan]

On Mar 19, 11:45 pm, sjw <simon.j.wri...@mac.com> wrote:

> There is a deep language-lawyerly reason (which I don't understand)
> why an array like your My_Array can't be aliased (at any rate in
> Ada95); you have to use the initialize-with-aggregate approach.
> Perhaps that's what leads to the initialize-with-aggregate style.

I don't remember what exact rules make this illegal (I could look them
up, but I don't feel like it right now; it has to do with nominal
subtypes). But here's the issue:

Say you declare an array

type Unconstrained_Array is array (Natural range <>) of Integer;
type Unconstrained_Array_P is access Unconstrained_Array;
Arr : aliased Unconstrained_Array (1..100);

When you have an object of type Unconstrained_Array_P, it points to a
specific object with specific bounds, and the code has to have a way
to get the bounds from the pointer. In some Ada implementations, the
way this works is that the bounds of the array are stored in memory
followed by the array data. This worked fine in Ada 83, where the
only way you could get an Unconstrained_Array_P was with an
allocator. In Ada 95, we have 'Access and "aliased", so we have to
consider the possibility that someone would want to use the 'Access of
Arr as an Unconstrained_Array_P. In those Ada implementations, this
would mean that the compiler would have to store the bounds of every
aliased array in front of the array data, including those that are
record components, just in case some other part of the code somewhere
else in the program decided to use the 'Access of it as an
Unconstrained_Array_P. This was deemed to be too much overhead, so as
a compromise the language rules were engineered so that in this case,

Arr : aliased Unconstrained_Array (1..100);

'Access could not be used as an Unconstrained_Array_P, while in this
case:

Arr : aliased Unconstrained_Array := <initial expression>

it could (and the bounds would have to be stored in memory). So that
way, the programmer has a choice.

I'm sure that things were done in this way to avoid adding too much
extra language syntax. If I had been responsible for designing the
Ada syntax, the language would have already died a horrible death and
we wouldn't even be having this discussion; nevertheless, I might have
suggested something like

Arr : aliased {unconstrained_access_ok} Unconstrained_Array
(1..100);

with attribute names (that aren't added to the list of reserved words)
in braces to tell the compiler things whether it's legal to convert
the 'Access to an unconstrained array pointer.

Hope this helps explain things. In any case, I strongly agree with
everyone else that using pointers in the OP's particular situation is
the wrong approach, and there shouldn't be any reason for it except
perhaps to work around a poor compiler implementation.

-- Adam

[belteshazzar]

I have to say that in my opinion this is a crappy language feature,
unconstrained and constrained arrays of the same type should be
interchangeable when declared on the stack. I realise that Ada05
allows the <> initialiser but i see that as a pretty poor solution.

we've converted our system to not use handles and it is so much
cleaner. the only problem is that for no-optimisation compilation
(used for debugging) it seems that the compiler is copying the large
arrays around. personally i don't see that as a problem.

thanks for everyone's help.

[sjw]

That makes so much sense! I think my brain freezes when I see the
compiler quoting rules about statically matching, so I just remember
the first 2 lines of the message (as you say, pretty explicit) and
pass over the reason why in the last 2 lines. After all, GNAT is much
more likely to be right than I am.

[sjw]

Thanks for the explanation.

My current problem is with this ..

type Stream_Type
(Buffer : access Ada.Streams.Stream_Element_Array)
is new Ada.Streams.Root_Stream_Type with private;
-- Provides an in-memory Stream over the elements of Buffer.
--
-- When one of these Stream_Types is created, it is notionally
-- empty. If Buffer is not in fact empty (perhaps it has been read
-- from a datagram socket), use Set_Last to indicate the index of
-- the last valid element.

where having to initialize a buffer of size 2048 (say) with useless
data and then overwrite it by reading from a socket goes against the
grain. Perhaps I'll be able to find the Ada way of doing it and it
will be suitably elegant.

[Adam Beneschan]

Well, you can initialize it with garbage data instead of useless data:

Buffer : aliased Ada.Streams.Stream_Element_Array := (1 .. 2048 =>
<>);

A minor improvement, maybe. I do think this is clunky, though, but I
don't know what the answer is. A worse problem is that there are
contexts where this workaround is disallowed.

-- Adam

[Robert A Duff]

sjw <simon.j...@mac.com> writes:

> That makes so much sense! I think my brain freezes when I see the
> compiler quoting rules about statically matching, so I just remember
> the first 2 lines of the message (as you say, pretty explicit) and
> pass over the reason why in the last 2 lines. After all, GNAT is much
> more likely to be right than I am.

Well, GNAT is right in the sense that it obeys the Ada RM on this point.
But some people (including some of the folks who wrote GNAT) think the
language designers were wrong on this point. It's an efficiency issue.
You can certainly come up with cases that make a big difference:

subtype S is String (1..4);
type A is array (Positive range <>) of aliased S;
X : A (1..1_000_000);

type S_Ref is access all S;

An object of subtype S is likely 4 bytes without dope, 12 bytes with
dope. Removing this restriction from the language would triple
the size of X from 4 million bytes to 12 million. If you only
wanted to point at components of X from objects of type S_Ref,
(as opposed to some "access all String" type) then that would be
annoying (why store 1 million copies of the compile-time-known
values 1 and 4?).

Memory is not cheap -- using more memory tends to cause cache misses.

On the other hand, the restriction is confusing, and not strictly
necessary.

- Bob

[Randy Brukardt]

"Robert A Duff" <bob...@shell01.TheWorld.com> wrote in message
news:wccy6ut...@shell01.TheWorld.com...
> sjw <simon.j...@mac.com> writes:
...

> Well, GNAT is right in the sense that it obeys the Ada RM on this point.
> But some people (including some of the folks who wrote GNAT) think the
> language designers were wrong on this point. It's an efficiency issue.
> You can certainly come up with cases that make a big difference:
>
> subtype S is String (1..4);
> type A is array (Positive range <>) of aliased S;
> X : A (1..1_000_000);
>
> type S_Ref is access all S;
>
> An object of subtype S is likely 4 bytes without dope, 12 bytes with
> dope. Removing this restriction from the language would triple
> the size of X from 4 million bytes to 12 million. If you only
> wanted to point at components of X from objects of type S_Ref,
> (as opposed to some "access all String" type) then that would be
> annoying (why store 1 million copies of the compile-time-known
> values 1 and 4?).

There is another option if you use non-contiguous dope (as Janus/Ada does):
create the dope on the fly when the 'Access is encountered. That's what we
did in our Ada 9x prototype compiler (before the "static matching" rule was
added to Ada 9x). The problem is that recovering the dope's memory is hard
in that case (you can't do it until either the object or the access type go
out of scope), and we didn't have a way to do it then (we hadn't implemented
finalization at that time).

As I recall, when I complained about the problem and asked for advice, you
guys added the "static matching" rule. Which eliminated this problem but
also made many safe and easy cases illegal. (OT3H, some of those "safe"
cases have other problems - see my response to Adam on Ada-Comment.) It is
interesting, though, that virtually every complaint I've seen on this has
always been asking about the case which is prohibitively expensive to
implement (either in complexity or in space used) -- no one seems concerned
about the "easy" cases that are illegal.

Randy.

[Jeffrey R. Carter]

Randy Brukardt wrote:
>
> also made many safe and easy cases illegal. (OT3H, some of those "safe"

That should be "on the gripping hand" ...

--
Jeff Carter
"Sir Lancelot saves Sir Gallahad from almost certain temptation."
Monty Python & the Holy Grail
69

[Robert A Duff]

"Jeffrey R. Carter" <spam.jrc...@nospam.acm.org> writes:

> That should be "on the gripping hand" ...

;-)

- Bob

[tmo...@acm.org]

>Well, you can initialize it with garbage data instead of useless data:
>
> Buffer : aliased Ada.Streams.Stream_Element_Array := (1 .. 2048 => <>);

Life is so much simpler if you drop the pointers and "aliased".

[Jean-Pierre Rosen]

sjw a écrit :

>
> My current problem is with this ..
>
> type Stream_Type
> (Buffer : access Ada.Streams.Stream_Element_Array)
> is new Ada.Streams.Root_Stream_Type with private;
> -- Provides an in-memory Stream over the elements of Buffer.
> --

But why do you need to pass a Stream_Element_Array? Why not pass the
size as a discriminant, and have the buffer internal to Stream_Type.

If you really need to access the buffer from the outside, you could have
a Get_Buffer function on Stream_Type that returns (your choice) the
buffer content, or a pointer to the internal buffer.

[Gautier]

sjw:

> My current problem is with this ..
>
> type Stream_Type
> (Buffer : access Ada.Streams.Stream_Element_Array)
> is new Ada.Streams.Root_Stream_Type with private;

Don't know if it helps, but here is an in-memory stream
(Unbounded_Stream) with random access:

http://unzip-ada.sourceforge.net/za_html/zip_streams__ads.htm
_________________________________________________________
Gautier's Ada programming -- http://sf.net/users/gdemont/
NB: For a direct answer, e-mail address on the Web site!

[sjw]

On Mar 27, 8:39 am, Jean-Pierre Rosen <ro...@adalog.fr> wrote:
> sjw a écrit :
>
> > My current problem is with this ..
>
> >    type Stream_Type
> >      (Buffer : access Ada.Streams.Stream_Element_Array)
> >    is new Ada.Streams.Root_Stream_Type with private;
> >    --  Provides an in-memory Stream over the elements of Buffer.
> >    --
>
> But why do you need to pass a Stream_Element_Array? Why not pass the
> size as a discriminant, and have the buffer internal to Stream_Type.
>
> If you really need to access the buffer from the outside, you could have
> a Get_Buffer function on Stream_Type that returns (your choice) the
> buffer content, or a pointer to the internal buffer.

I'm going to be using this with GNAT.Sockets, so I need (certainly for
reading from the network) access to the actual buffer content as a
Stream_Element_Array. So I could use an "access all
Stream_Element_Array".

Of course, if I made it specific to GNAT.Sockets it might be easier ..

[sjw]

On Mar 27, 9:39 am, Jean-Pierre Rosen <ro...@adalog.fr> wrote:
> sjw a écrit :
>
> > My current problem is with this ..
>
> >    type Stream_Type
> >      (Buffer : access Ada.Streams.Stream_Element_Array)
> >    is new Ada.Streams.Root_Stream_Type with private;
> >    --  Provides an in-memory Stream over the elements of Buffer.
> >    --
>
> But why do you need to pass a Stream_Element_Array? Why not pass the
> size as a discriminant, and have the buffer internal to Stream_Type.
>
> If you really need to access the buffer from the outside, you could have
> a Get_Buffer function on Stream_Type that returns (your choice) the
> buffer content, or a pointer to the internal buffer.

To be useful, the pointer to the internal buffer would have to be an
'access Ada.Streams.Stream_Element_Array'. How could I create one of
these from a constrained object?

I think this idea of mine is a non-starter; I'll stick with the
current BC.Support.Memory_Streams. No point providing a library
component that no one can actually use!