Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Help needed - Upper Bound of an array - Question.
30 views
Skip to first unread message
adacrypt
Feb 7, 2012, 9:41:38 AM2/7/12
to
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
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
Yannick Duchêne (Hibou57)
Feb 7, 2012, 10:00:59 AM2/7/12
to
Le Tue, 07 Feb 2012 15:41:38 +0100, adacrypt <austin...@hotmail.com> a
écrit:
> 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
é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.
> 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.
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
Mark Lorenzen
Feb 7, 2012, 10:04:33 AM2/7/12
to
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
> 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.
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.
> 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?
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.
Regards,
Mark L
Ludovic Brenta
Feb 7, 2012, 10:08:11 AM2/7/12
to
adacrypt wrote on comp.lang.ada:
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.
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.
Yannick Duchêne (Hibou57)
Feb 7, 2012, 10:27:01 AM2/7/12
to
Le Tue, 07 Feb 2012 16:08:11 +0100, Ludovic Brenta
<lud...@ludovic-brenta.org> a écrit:
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.
<lud...@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
> with a rope (see
> http://en.wikipedia.org/wiki/Rope_%28computer_science%29).
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.
Álex R.
Feb 7, 2012, 10:33:13 AM2/7/12
to
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
> 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?
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.
> Your help would be greatly appreciated.
> - adacrypt
adacrypt
Feb 7, 2012, 10:59:15 AM2/7/12
to
>
> - 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
Gautier write-only
Feb 7, 2012, 11:13:11 AM2/7/12
to
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
> 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
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
Jeffrey Carter
Feb 7, 2012, 12:30:10 PM2/7/12
to
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
>
> 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.
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 ne...@netfront.net ---
Ludovic Brenta
Feb 7, 2012, 1:22:52 PM2/7/12
to
adacrypt writes on comp.lang.ada:
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
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 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
> 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
declaration like so:
SUBTYPE Index_30 IS Integer RANGE -500000 .. 500000;
TYPE I_CoefficientsNumArray IS ARRAY(Index_30) OF Integer;
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.
Georg Bauhaus
Feb 7, 2012, 1:56:38 PM2/7/12
to
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;
>
> 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.
> 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
(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
tmo...@acm.org
Feb 7, 2012, 2:51:33 PM2/7/12
to
> > SUBTYPE Index_30 IS Integer RANGE -500000 .. 500000;
> > TYPE I_CoefficientsNumArray IS ARRAY(Index_30) OF Integer;
> > I_Num : I_CoefficientsNumArray;
>
> > 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
> the array, in this case Index_30. Index_30 has 1_000_001 values, so I_Num has
> 1_000_001 components.
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.
adacrypt
Feb 7, 2012, 3:42:35 PM2/7/12
to
Robert A Duff
Feb 7, 2012, 4:22:15 PM2/7/12
to
adacrypt <austin...@hotmail.com> writes:
> This is my declaration.
>
> SUBTYPE Index_30 IS Integer RANGE -500000 .. 500000;
Why 30? Why not a new type?
> 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
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
Jerry
Feb 7, 2012, 5:08:08 PM2/7/12
to
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
Randy Brukardt
Feb 8, 2012, 10:31:45 PM2/8/12
to
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.
<tmo...@acm.org> wrote in message news:jgrvc5$243$1...@speranza.aioe.org...
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.
<tmo...@acm.org> wrote in message news:jgrvc5$243$1...@speranza.aioe.org...
0 new messages