Help needed - Upper Bound of an array - Question.

Help needed - Upper Bound of an array - Question.

[adacrypt]

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.

- adacrypt

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

[Yannick Duchêne (Hibou57)]

Le Tue, 07 Feb 2012 15:41:38 +0100, adacrypt <austin.obyrne@hotmail.com> a  
écrit:
> 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?
No. Limits are implementation defined.

> I need to know this before resorting to a 64-bit computer which might
> not solve the problem and be an expensive mistake.
Did you look at Ada containers?
http://www.adaic.org/resources/add_content/standards/05rm/html/RM-A-18.html
Available since Ada 2005.

-- 
“Syntactic sugar causes cancer of the semi-colons.” [1]
“Structured Programming supports the law of the excluded muddle.” [1]
[1]: Epigrams on Programming — Alan J. — P. Yale University

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

[Mark Lorenzen]

On 7 Feb., 15:41, adacrypt <austin.oby...@hotmail.com> wrote:
> 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 take it that the size of the array then will be up to 10,000,000
times 8 octets = approx 80 Mb. Is that true?

> I have already found out that I cannot go more than 500,000 elements
> in the array size.  My computer has 32-bit architecture.

Probably true.

> 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?

It is not a restriction imposed on you by the Ada language, but the
environment under which your program is runnning. By environment I
mean the operating system.

How is memory for the array allocated? If it is allocated on the
stack, then you could easily hit the maximum stack size allowed by
your environment.

> I need to know this before resorting to a 64-bit computer which might
> not solve the problem and be an expensive mistake.

A 32-bit environment can easily address 80 Mb of data.

Regards,

Mark L

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

[Ludovic Brenta]

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.

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

[Yannick Duchêne (Hibou57)]

Le Tue, 07 Feb 2012 16:08:11 +0100, Ludovic Brenta  
<ludovic@ludovic-brenta.org> a écrit:
> Alternatively, you should consider replacing the array
> with a rope (see  
> http://en.wikipedia.org/wiki/Rope_%28computer_science%29).
Or alternatively again, and as we can suppose there will be no insertion  
or removal (so much inefficient with an array, he would not have choose an  
array), a balanced binary tree, which is very fast and easy when created  
for a given fixed size. I did it some years ago, on a machine with heap  
fragmentation and no virtual memory. Above all, appending is still fast  
and simple, if ever the size has to be increased.

-- 
“Syntactic sugar causes cancer of the semi-colons.” [1]
“Structured Programming supports the law of the excluded muddle.” [1]
[1]: Epigrams on Programming — Alan J. — P. Yale University

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

[adacrypt]

On Feb 7, 3:08 pm, Ludovic Brenta <ludo...@ludovic-brenta.org> wrote:
> 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 (seehttp://en.wikipedia.org/wiki/Rope_%28computer_science%29).
>
> HTH
>
> --
> Ludovic Brenta.- Hide quoted text -
>
> - Show quoted text -

Many thanks to everyone - your'e a bit over my head technically but I
get the gist of it from each one of you.

This is my declaration.

 SUBTYPE Index_30 IS Integer RANGE -500000 .. 500000;
  TYPE I_CoefficientsNumArray IS ARRAY(Index_30) OF Integer;
  I_Num : I_CoefficientsNumArray;
  -- counts the occurences of the j coefficients of the ciphertext.

Question : can I use your 'big array' declaration procedure in Ada-95
just as you have typed here ? that would be great - will it work just
by replacing the present declaration with this? do I type in as a
straight crib just like that, regards - adacrypt

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

[Gautier write-only]

On 7 fév, 16:59, adacrypt <austin.oby...@hotmail.com> wrote:

> Question : can I use your 'big array' declaration procedure in Ada-95
> just as you have typed here ? that would be great - will it work just
> by replacing the present declaration with this? do I type in as a
> straight crib just like that, regards - adacrypt

The only difference is that the array itself is My_Array.all; My_Array
is its access.
But since My_Array.all(i) can also be written shorter as My_Array(i),
the changes to you program will be minimal.
And yes, you can use it in Ada 95 and above, and even in Ada 83 (with
a small difference: no "Ada." before Unchecked_Deallocation).
_________________________
Gautier's Ada programming
http://gautiersblog.blogspot.com/search/label/Ada
NB: follow the above link for a valid e-mail address

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

[Jeffrey Carter]

On 02/07/2012 08:59 AM, adacrypt wrote:
>
> This is my declaration.
>
>   SUBTYPE Index_30 IS Integer RANGE -500000 .. 500000;
>    TYPE I_CoefficientsNumArray IS ARRAY(Index_30) OF Integer;
>    I_Num : I_CoefficientsNumArray;
>    -- counts the occurences of the j coefficients of the ciphertext.

Here is a 3rd source of limits on the size of the array: the index subtype of 
the array, in this case Index_30. Index_30 has 1_000_001 values, so I_Num has 
1_000_001 components.

-- 
Jeff Carter
"Why, the Mayflower was full of Fireflies, and a few
horseflies, too. The Fireflies were on the upper deck,
and the horseflies were on the Fireflies."
Duck Soup
95

--- Posted via news://freenews.netfront.net/ - Complaints to news@netfront.net ---

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

[tmoran]

> >   SUBTYPE Index_30 IS Integer RANGE -500000 .. 500000;
> >    TYPE I_CoefficientsNumArray IS ARRAY(Index_30) OF Integer;
> >    I_Num : I_CoefficientsNumArray;
>
> Here is a 3rd source of limits on the size of the array: the index subtype of
> the array, in this case Index_30. Index_30 has 1_000_001 values, so I_Num has
> 1_000_001 components.

The OP is probably using Gnat, with its very limited stack size.  Other
Ada compilers are not so limited.  Janus, for instance, compiles, and
runs on an old 3GB 32 bit Windows XP machine:

  type Index_30 is range -100_000_000 .. 100_000_000;
  type Coefficient_Type is new Interfaces.Unsigned_32;
  TYPE I_CoefficientsNumArray IS ARRAY(Index_30) OF Coefficient_Type;
  I_Num : I_CoefficientsNumArray;

which allocates 800,000,004 bytes.

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

[Randy Brukardt]

To correct Tom slightly, this will work when allocated in a package, but 
probably not when allocated in a procedure (like the main subprogram).

For the OP's declaration, allocation on the heap shouldn't be necessary, but 
library-level allocation is a must. (But I have never tried to allocate 
really big objects in GNAT.)

                                   Randy.

<tmoran@acm.org> wrote in message news:jgrvc5$243$1@speranza.aioe.org...
>> >   SUBTYPE Index_30 IS Integer RANGE -500000 .. 500000;
>> >    TYPE I_CoefficientsNumArray IS ARRAY(Index_30) OF Integer;
>> >    I_Num : I_CoefficientsNumArray;
>>
>> Here is a 3rd source of limits on the size of the array: the index 
>> subtype of
>> the array, in this case Index_30. Index_30 has 1_000_001 values, so I_Num 
>> has
>> 1_000_001 components.
>
> The OP is probably using Gnat, with its very limited stack size.  Other
> Ada compilers are not so limited.  Janus, for instance, compiles, and
> runs on an old 3GB 32 bit Windows XP machine:
>
>  type Index_30 is range -100_000_000 .. 100_000_000;
>  type Coefficient_Type is new Interfaces.Unsigned_32;
>  TYPE I_CoefficientsNumArray IS ARRAY(Index_30) OF Coefficient_Type;
>  I_Num : I_CoefficientsNumArray;
>
> which allocates 800,000,004 bytes. 

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

[Ludovic Brenta]

adacrypt writes on comp.lang.ada:
> Many thanks to everyone - your'e a bit over my head technically but I
> get the gist of it from each one of you.
>
> This is my declaration.
>
>  SUBTYPE Index_30 IS Integer RANGE -500000 .. 500000;
>   TYPE I_CoefficientsNumArray IS ARRAY(Index_30) OF Integer;
>   I_Num : I_CoefficientsNumArray;
>   -- counts the occurences of the j coefficients of the ciphertext.
>
> Question : can I use your 'big array' declaration procedure in Ada-95
> just as you have typed here ? that would be great - will it work just
> by replacing the present declaration with this? do I type in as a
> straight crib just like that, regards - adacrypt

Yes, you would simply augment your program with an access type
declaration like so:

SUBTYPE Index_30 IS Integer RANGE -500000 .. 500000;
TYPE I_CoefficientsNumArray IS ARRAY(Index_30) OF Integer;

type Array_Access is access I_CoefficientsNumArray; -- new type

I_Num : Array_Access := new I_CoefficientsNumArray; -- allocate on the heap
-- counts the occurences of the j coefficients of the ciphertext.

For more details on dynamic memory allocation and deallocation and
access types, read this:

http://www.it.bton.ac.uk/staff/je/adacraft/ch11.htm

which is the book I recommend for novice programmers.  In fact, even I
enjoyed this book thoroughly when I learned Ada as my 12th (or so)
programming language :)

-- 
Ludovic Brenta.

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

[adacrypt]

On Feb 7, 6:22 pm, Ludovic Brenta <ludo...@ludovic-brenta.org> wrote:
> adacrypt writes on comp.lang.ada:
>
> > Many thanks to everyone - your'e a bit over my head technically but I
> > get the gist of it from each one of you.
>
> > This is my declaration.
>
> >  SUBTYPE Index_30 IS Integer RANGE -500000 .. 500000;
> >   TYPE I_CoefficientsNumArray IS ARRAY(Index_30) OF Integer;
> >   I_Num : I_CoefficientsNumArray;
> >   -- counts the occurences of the j coefficients of the ciphertext.
>
> > Question : can I use your 'big array' declaration procedure in Ada-95
> > just as you have typed here ? that would be great - will it work just
> > by replacing the present declaration with this? do I type in as a
> > straight crib just like that, regards - adacrypt
>
> Yes, you would simply augment your program with an access type
> declaration like so:
>
> SUBTYPE Index_30 IS Integer RANGE -500000 .. 500000;
> TYPE I_CoefficientsNumArray IS ARRAY(Index_30) OF Integer;
>
> type Array_Access is access I_CoefficientsNumArray; -- new type
>
> I_Num : Array_Access := new I_CoefficientsNumArray; -- allocate on the heap
> -- counts the occurences of the j coefficients of the ciphertext.
>
> For more details on dynamic memory allocation and deallocation and
> access types, read this:
>
> http://www.it.bton.ac.uk/staff/je/adacraft/ch11.htm
>
> which is the book I recommend for novice programmers.  In fact, even I
> enjoyed this book thoroughly when I learned Ada as my 12th (or so)
> programming language :)
>
> --
> Ludovic Brenta.

Many Many thanks to every one - adacrypt

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

[Georg Bauhaus]

On 07.02.12 16:59, adacrypt wrote:
> On Feb 7, 3:08 pm, Ludovic Brenta <ludo...@ludovic-brenta.org> wrote:

>> 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;

> 
> Many thanks to everyone - your'e a bit over my head technically but I
> get the gist of it from each one of you.
> 
> This is my declaration.
> 
>  SUBTYPE Index_30 IS Integer RANGE -500000 .. 500000;
>   TYPE I_CoefficientsNumArray IS ARRAY(Index_30) OF Integer;
>   I_Num : I_CoefficientsNumArray;
>   -- counts the occurences of the j coefficients of the ciphertext.
> 
> Question : can I use your 'big array' declaration procedure in Ada-95
> just as you have typed here ? that would be great - will it work just
> by replacing the present declaration with this? do I type in as a
> straight crib just like that, regards - adacrypt


Yes, also in Ada 83. I'd also follow Gaultier's suggestions.
(Note that resorting to pointers is necessary only if you use
a compiler + OS that cannot handle somewhat larger array sizes
in the environment task ("main program"), even when they are
just fine in tasks' storage).


Another boon to your program might be in Ada's fundamental
types: you can express your knowledge about the integers
("7 or 8 digits in magnitude") as a type, something like

  type Ints_in_the_Set is range 0 .. 87_456_321;

replacing the limits with whatever you think they should be,
of course, and choosing a suitable name.  This has several effects:

- the program no longer depends on implementation defined
  type Integer

- you, your readers, and the compiler will know what values to
  expect in all objects of type Ints_in_the_Set; this is not
  the case with Integer

- you can even adjust the type's size (in bits) as you see
  fit; when your program is compiled on a 64bit platform
  you might still specify a 'Size of 32 bits, which could
  save some cache memory

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

[Robert A Duff]

adacrypt <austin.obyrne@hotmail.com> writes:

> This is my declaration.
>
>  SUBTYPE Index_30 IS Integer RANGE -500000 .. 500000;

Why 30?  Why not a new type?

>   TYPE I_CoefficientsNumArray IS ARRAY(Index_30) OF Integer;
>   I_Num : I_CoefficientsNumArray;
>   -- counts the occurences of the j coefficients of the ciphertext.
>
> Question : can I use your 'big array' declaration procedure in Ada-95
> just as you have typed here ? that would be great - will it work just
> by replacing the present declaration with this? do I type in as a
> straight crib just like that, regards - adacrypt

I suggest you figure out how to increase the stack size,
so you don't have to use pointers.  It's in the GNAT
documentation.

If that's impossible, and you want to use pointers, you
can avoid the issue of adding ".all" all over the place:

    I_Num_Pointer : I_CoefficientsNumArray_Pointer := new ...;
    I_Num : I_CoefficientsNumArray renames I_Num_Pointer.all;

- Bob

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

[Álex R. Mosteo]

adacrypt wrote:

> 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?

Without looking at what the ARM has to say, my first impression is that this 
is a problem with stack size limits. I would expect otherwise your arrays to 
be potentially as large as ~2^31 elements.

You could try to raise the stack size (in a task, with pragma Stack_Size, 
and *additionally* in your linker/OS, with whatever means it provides).

Or, perhaps simpler, you could allocate the array in the heap with "new". 
You could further and optionally create a [limited] private type that 
exposed the array via an access, and that took care of memory management.

Or you could try to move to Ada 2005 and use vectors from the standard 
library, although this most likely will have an impact on speed.

> I need to know this before resorting to a 64-bit computer which might
> not solve the problem and be an expensive mistake.

As last resort, I'd try to cook some ADT before investing serious money ;-)

> Your help would be greatly appreciated.

Hope this helps, I'm sure you'll get answers from the experts soon.

> - adacrypt

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

[Jerry]

On Feb 7, 7:41 am, adacrypt <austin.oby...@hotmail.com> wrote:
> 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.
>
> - adacrypt

This question arises from time to time; see these two previous
threads:

http://groups.google.com/group/comp.lang.ada/browse_thread/thread/ae395e5c11de7bc9/bda8d61bd3a66ee9?hl=en&q=Jerry+stack&lnk=nl&

http://groups.google.com/group/comp.lang.ada/browse_thread/thread/419864ed91cc937d?hl=en#

(Sorry if I'm repeating anything earlier in this thread.)

Your best option is to use dynamic allocation which uses the heap,
then use "rename" to simplify your code.

Some (lesser) problems can be solved by increasing the stack size. I
don't know if this is possible from within the Ada code using pragmas,
but you can do it from the shell (before running your program) using
ulimit, or from within the Ada code by importing the C functions
setrlimit and getrlimit.

Jerry