Re: allocation of an array

["Robert I. Eachus" <rieachus@comcast.net>]

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