allocation of an array

allocation of an array

[Davide]

Hello experts,

I'm an Ada beginner.
My question is about the allocation of an array into memory.
In particular: can I be sure (from the standard) of the fact that the
elements (unsigned int, 16 bit) of an array (really big) are allocated
contiguously into memory?
Is (and how) this dependent on implementation/platform (0.S, processor,
etc.)?

Thanks in advance.

Dave

Re: allocation of an array

[Robert I. Eachus]

Davide wrote:
> Hello experts,
> 
> I'm an Ada beginner.
> My question is about the allocation of an array into memory.
> In particular: can I be sure (from the standard) of the fact that the
> elements (unsigned int, 16 bit) of an array (really big) are allocated
> contiguously into memory?

For an Ada beginner, you ask pretty subtle questions!  There are three 
answers to your question.  The first is that yes, you can always count 
on an Ada array being an array, where the data elements are evenly 
spaced.  Beyond that it gets tricky.

Compilers normally try to allocate arrays so that their elements fall on 
natural boundaries for the element's TYPE.  For example, if, in the 
implementation you are using Integer is a 32-bit type, then:

subtype Small_Int is Integer range -128..127;
type Small_Int_Array is array(Integer range <>) of Small_Int;
My_Small_Int_Array: Small_Int_Array(1..10);

...will probably result in the allocation of 320 bits or more for 
My_Small_Int_Array.

If you say pragma Pack(Small_Int_Array); the elements should be stored 
in one byte each, saving 240 bits of storage.  Can you go further? Sure. 
  If you say:

   for My_Small_Int_Array'Size use 80;

...you are specifying that the compiler must use only 80 bits to store 
My_Small_Int_Array--or refuse at compile time and reject the compilation 
unit.  You can be less aggressive and say:

   for Small_Int_Array'Component_Size use 8;

This allows the compiler to use additional space to store the bounds 
information for the object, but requires that the elements be stored in 
eight bits each.  Note that I changed from applying the attribute clause 
to the object, to specifying it for all objects of the composite (array) 
type.  You can do either, but it is usual to use the 'Component_Size 
representation clause on unconstrained (sub)types, and the 'Size clause 
on statically constrained objects or subtypes.

Incidentally, if you had declared:

   subtype Small_Int is Integer range 0..127;

Then you could say,

   for Small_Int_Array'Component_Size use 7;

or even:

   subtype Small_Int is Integer range 120..127;
   ...
   for Small_Int_Array'Component_Size use 3;
or
   for My_Small_Int_Array'Size use 32;
   -- allowing for an integral byte size

this is known as "fierce packing."  You can ask for it, and some 
compilers support it.  How fierce depends on the compiler of course, and 
in any case you can expect access to components of fiercely packed 
objects to take longer.  (Whether the caching effects result in your 
program's overall behavior improving is up to you to determine.)

> Is (and how) this dependent on implementation/platform (0.S, processor,
> etc.)?

See above.  Most compilers will support natural packing for the 
hardware, storing objects on byte or word bounds.  Of course, I can't 
say much more about it than the reference manual makes it 
"Implementation Advice" because the natural packing will depend on the 
hardware.

Also note that in the discussion above I mostly avoided mentioning array 
descriptors.  In most cases, arrays that are not statically bounded will 
need to store descriptor information.  The format of this information, 
and where it is stored relative to the rest of the array is of course, 
implementation defined.  The reference manual recommends that the 
address of an array be the same as the address of the first element.  So 
many implementations store the descriptors at negative offsets from the 
array elements.  Other implementations may store the descriptors 
separately, resulting in a two part object.  There are also 
implementations which will use offset pointers for the data so that, for 
example, a String declared as:

Foo: String(80..85) := "offset";

Might use a descriptor that contains the address of byte 1 of a 
hypothetical String where the bytes 80..85 have the value above.  But 
normally even on implementations that do this for efficiency, 
Foo'Address will equal Foo(80)'Address.

> Thanks in advance.

I hope this answer is not overwhelming.  In practice you can ignore all 
of it unless you have to interface with hardware, or with code in some 
other language.

-- 
                                           Robert I. Eachus

"The only thing necessary for the triumph of evil is for good men to do 
nothing." --Edmund Burke

Re: allocation of an array

[Davide]

Robert I. Eachus wrote:

> For an Ada beginner, you ask pretty subtle questions!  There are three
> answers to your question.  The first is that yes, you can always count
> on an Ada array being an array, where the data elements are evenly
> spaced.  Beyond that it gets tricky.

[CUT]

> I hope this answer is not overwhelming.  In practice you can ignore all
> of it unless you have to interface with hardware, or with code in some
> other language.

Thank you very much for your exhaustive response, Robert.

I hope not to bother you if I try to explain a little bit better why my
question arose.

First of all I must use the SPARK Ada subset (so no access types, no
unconstrained arrays,...quite nothing...).
My machine is a Power-PC with 32-bit alignment. My compiler is AdaMulti.
I must download long messages composed of 16-bit integers items from a FIFO
memory device.
In my implementation I store them into arrays of 16 bit-integers.
Then I have to filter those buffered messages, extracting a subset of items.
I chosen to use a constant array of offsets for each message (an offset
index for each item to extract).
Then I go through the array extracting items at the specified indexes.
This is my solution, but now I'm wondering if I could have done better if I
had "mapped" a record
to each of those arrays, with 16-bit fields corresponding to the message
items and copying the relevant items to "filtered" records.
That's why I was asking about the array allocation, that is therefore
essential to this solution.

I still hope that the first solution could be preferable...since I have done
a lot of code...  :-) ...what do you think, also in terms of portability and
reusability (i.e independence from platform and compiler, which I like to
take into account)?

Sorry for my bad english,
and thank you for your patience,

Dave

Re: allocation of an array

[Robert I. Eachus]

Davide wrote:

> My machine is a Power-PC with 32-bit alignment. My compiler is AdaMulti.
> I must download long messages composed of 16-bit integers items from a FIFO
> memory device.
> In my implementation I store them into arrays of 16 bit-integers.
> Then I have to filter those buffered messages, extracting a subset of items.
> I chosen to use a constant array of offsets for each message (an offset
> index for each item to extract).
> Then I go through the array extracting items at the specified indexes.
> This is my solution, but now I'm wondering if I could have done better if I
> had "mapped" a record
> to each of those arrays, with 16-bit fields corresponding to the message
> items and copying the relevant items to "filtered" records.
> That's why I was asking about the array allocation, that is therefore
> essential to this solution.

If I understand what you are saying.  You have messages which consist of 
some number of 16-bit chunks.  You need to map some? templates on to the 
received messages and extract data from some of those fields.

I think I will answer by pointing you to the Ada.Streams package.  If 
you can use it for the streams you are dealing with it will make things 
much easier.  The real magic occurs with 'Read and 'Write in the next 
section. (And if you have multiple message formats that depend on 
information in one or more header words, S'Output and S'Input.)

With luck you should be able to declare your messages as a single 
variant record type, and use 'Input to read those messages.

> I still hope that the first solution could be preferable...since I have done
> a lot of code...  :-) ...what do you think, also in terms of portability and
> reusability (i.e independence from platform and compiler, which I like to
> take into account)?

-- 
                                           Robert I. Eachus

"The only thing necessary for the triumph of evil is for good men to do 
nothing." --Edmund Burke

Re: allocation of an array

[Rod Chapman]

"Davide" <ppp@ppp.it> wrote in message news:<c1vt3t$np4$1@e3k.asi.ansaldo.it>...
> First of all I must use the SPARK Ada subset (so no access types, no
> unconstrained arrays,...quite nothing...).

SPARK support queries should be addressed to sparkinfo@praxis-cs.co.uk -
you are more likely to get a sensible answer from my team, not all
of whom read c.l.a.
 - Rod Chapman, SPARK Team, Praxis Critical Systems Limited