Re: Help needed - Upper Bound of an array - Question.

[Ludovic Brenta <ludovic@ludovic-brenta.org>]

adacrypt wrote on comp.lang.ada:
> I am not an expert programmer in Ada but I have taught myself enough
> Ada-95 to be able to write some difficult cryptography programs that I
> post in another group.
>
> My problem is this.  I need to test the frequency of the ciphertext
> which is sometimes a long string of large positive integers of 7 or 8
> digits in magnitude and to do that I need an array that will
> accommodate up to 10,000,000 elements ideally.
>
> I have already found out that I cannot go more than 500,000 elements
> in the array size.  My computer has 32-bit architecture.
>
> What I need to know from some kind person is this - Is the array size
> a property of the Ada-95 language or the computer?
>
> I need to know this before resorting to a 64-bit computer which might
> not solve the problem and be an expensive mistake.
>
> Your help would be greatly appreciated.

Both.

The computer (and its operating system) limit the size of a single
object in memory and also the maximum combined sizes of all objects
you allocate.  On modern 32-bit operating systems, this limit is
usually 2, 3 or 4 gibibytes (1 gibibyte = 2**30 bytes) per process.

However there is also a limit imposed by the compiler and linker: the
stack size. The compiler and linker emit code that will allocate a
stack for each thread. This stack will have a limited size, typically
2 mebibytes (2 * 2**20 bytes) per thread.  If you declare Ada tasks,
you can tell the compiler how large the stack must be for each but you
must use linker options to control the size of the stack for the
environment task (the task where your main program executes).

Your observation that 500_000 elements (presumably 32-bit integers) is
the maximum you can achieve suggests that you are allocating your
array on the stack of the environment task (500_000 * 32bits = 2
million bytes, i.e. almost 2 mebibytes).  If you would allocate your
array from the heap, you would be able to use all your physical and
virtual memory.

Stack allocation looks like:

declare
   My_Array : array (1 .. 500_000) of Integer; -- 2_000_000 bytes on
the stack
begin
   ...
end;

Heap allocation looks like:

declare
   type Big_Array is array (Positive range <>) of Integer;
   type Big_Array_Access is access Big_Array;
   procedure Free is
     new Ada.Uncheched_Deallocation (Big_Array, Big_Array_Access);
   My_Array : Big_Array_Access is new Big_Array (1 .. 10_000_000);
   -- 40_000_000 bytes on the heap
begin
   ...
   Free (My_Array); -- optional, if your program just exits at this
point, the operating system will reclaim memory
end;

Note that allocating such a large array from the heap presumes a
large, *contiguous* range of free addresses in your virtual address
space.  Such a range normally exists when your program starts but will
probably be fragmented into insufficiently large free ranges if you
allocate and deallocate lots of smaller objects.  So, you should
allocate your large array as early as possible in the execution of
your program.  Alternatively, you should consider replacing the array
with a rope (see http://en.wikipedia.org/wiki/Rope_%28computer_science%29).

HTH

--
Ludovic Brenta.