Large arrays (again), problem case for GNAT

Large arrays (again), problem case for GNAT

[Dr. Adrian Wrigley]

Hi guys!

A month or two back I hinted that I had been having problems
the GNAT code accessing large data structures.  It seemed that
incorrect code was silently being generated.  Since I didn't
have a test case available, no progress could be made.

I have encountered the problem again, and produced a test case.

In summary:

Certain uses of arrays over about 800MB cause code to fail.
In particular, 'Address is sometimes incorrect
Accessing high elements is incorrect, depending on exact code to
  generate the index.

The problems only seem to occur if the upper bound of the array
is compile-time constant.

Can someone test this on later versions of GNAT please?
-- 
Adrian Wrigley, Cambridge, UK


with Text_IO;
with System.Address_Image;

procedure TestBug is

-- Test devised by Adrian Wrigley, amtw@linuxchip.demon.co.uk.uk.uk (one uk is enough)
-- I disclaim all rights to this code.  Do what you wish with it!

-- This test case illustrates a problem with code
-- compiled on GNAT 3.15p for x86 under Linux

-- It shows that the 'Address of elements of large
-- arrays can be silently incorrect

-- Notes:
--
-- This test works if the word "constant" is removed
--
-- The test also works if the value is less than 200_000_000
-- Indexing element also works with computed index
   Size : constant Integer := 210_000_000;

   type Big_T is array (1 .. Size) of aliased Float;

   type Big_A is access Big_T;

   Big : Big_A;

   function GetSomeMemory (X : Integer) return Big_A;
   pragma Import (C, GetSomeMemory, "malloc");

begin

   Big := GetSomeMemory (Size*4 + 16); -- This seems to work OK for now

   Text_IO.Put_Line ("First element attribute " & Integer'Image (Big_T'First));
   Text_IO.Put_Line ("Last element attribute  " & Integer'Image (Big_T'Last));

   Text_IO.Put_Line ("Address of first element is " & System.Address_Image (Big (Big_T'First)'Address));
   Text_IO.Put_Line ("Address of last element is  " & System.Address_Image (Big (Big_T'Last)'Address)); -- Fails!!!!!
   Text_IO.Put_Line ("(Last element should be at higher address than first)");


   declare
      J : Integer := Size;
   begin
      Text_IO.Put_Line ("Address of last element is " & System.Address_Image (Big (J)'Address));
   end;

   Text_IO.Put_Line ("Writing to all elements in loop");
   for I in Big_T'Range loop
      Big (I) := 0.0;
   end loop;

   Text_IO.Put_Line ("Writing to 'Last element");

--raised STORAGE_ERROR : stack overflow (or erroneous memory access):
   Big (Big_T'Last) := 0.0; -- Fails!!!!!

end TestBug;

I get
$ gnatmake -O3  testbug
$ ./testbug

First element attribute  1
Last element attribute   210000000
Address of first element is 4212F008
Address of last element is  34245204
Last element should be at higher address than first
Address of last element is 74245204
Writing to all elements in loop
Writing to 'Last element

raised STORAGE_ERROR : stack overflow (or erroneous memory access)

Re: Large arrays (again), problem case for GNAT

[Larry Kilgallen]

In article <pan.2005.04.13.12.46.52.518681@linuxchip.demon.co.uk.uk.uk>, "Dr. Adrian Wrigley" <amtw@linuxchip.demon.co.uk.uk.uk> writes:
> Hi guys!
> 
> A month or two back I hinted that I had been having problems
> the GNAT code accessing large data structures.  It seemed that
> incorrect code was silently being generated.  Since I didn't
> have a test case available, no progress could be made.
> 
> I have encountered the problem again, and produced a test case.
> 
> In summary:
> 
> Certain uses of arrays over about 800MB cause code to fail.
> In particular, 'Address is sometimes incorrect
> Accessing high elements is incorrect, depending on exact code to
>   generate the index.
> 
> The problems only seem to occur if the upper bound of the array
> is compile-time constant.
> 
> Can someone test this on later versions of GNAT please?

Later than what ?

Re: Large arrays (again), problem case for GNAT

[Alex R. Mosteo]

Larry Kilgallen wrote:
> In article <pan.2005.04.13.12.46.52.518681@linuxchip.demon.co.uk.uk.uk>, "Dr. Adrian Wrigley" <amtw@linuxchip.demon.co.uk.uk.uk> writes:
> 
>>Hi guys!
>>
>>A month or two back I hinted that I had been having problems
>>the GNAT code accessing large data structures.  It seemed that
>>incorrect code was silently being generated.  Since I didn't
>>have a test case available, no progress could be made.
>>
>>I have encountered the problem again, and produced a test case.
>>
>>In summary:
>>
>>Certain uses of arrays over about 800MB cause code to fail.
>>In particular, 'Address is sometimes incorrect
>>Accessing high elements is incorrect, depending on exact code to
>>  generate the index.
>>
>>The problems only seem to occur if the upper bound of the array
>>is compile-time constant.
>>
>>Can someone test this on later versions of GNAT please?
> 
> 
> Later than what ?

Somewhere 3.15p is mentioned.

Re: Large arrays (again), problem case for GNAT

[Marc A. Criley]

Larry Kilgallen wrote:
> In article <pan.2005.04.13.12.46.52.518681@linuxchip.demon.co.uk.uk.uk>, "Dr. Adrian Wrigley" <amtw@linuxchip.demon.co.uk.uk.uk> writes:
> 
>>
>>Can someone test this on later versions of GNAT please?
> 
> 
> Later than what ?

Probably this:

 >> -- This test case illustrates a problem with code
 >> -- compiled on GNAT 3.15p for x86 under Linux

Re: Large arrays (again), problem case for GNAT

[Jeffrey Carter]

Dr. Adrian Wrigley wrote:

>    function GetSomeMemory (X : Integer) return Big_A;
>    pragma Import (C, GetSomeMemory, "malloc");

This isn't Ada, and how well this works is going to depend on the 
compiler and on the implementation of malloc used. Some compilers do not 
represent access values in the same way as C pointers (unless Convention 
C is specified), so this would fail miserably on them.

With GNAT and gcc, obviously, you get something semi-useful; the fact 
that it fails sometimes indicates that perhaps you shouldn't be doing 
this. Maybe you should use a Convention-C array and use C functions to 
access the elements.

-- 
Jeff Carter
"Apart from the sanitation, the medicine, education, wine,
public order, irrigation, roads, the fresh water system,
and public health, what have the Romans ever done for us?"
Monty Python's Life of Brian
80

Re: Large arrays (again), problem case for GNAT

[Randy Brukardt]

"Dr. Adrian Wrigley" <amtw@linuxchip.demon.co.uk.uk.uk> wrote in message
news:pan.2005.04.13.12.46.52.518681@linuxchip.demon.co.uk.uk.uk...
> Hi guys!
>
> A month or two back I hinted that I had been having problems
> the GNAT code accessing large data structures.  It seemed that
> incorrect code was silently being generated.  Since I didn't
> have a test case available, no progress could be made.

I tried to make an all-Ada version to test on Janus/Ada. But there is not
enough memory on my machine to run it (at least, I think that's why I'm
getting Storage_Error; the Janus/Ada runtime bypasses the system heap and
goes directly to the Windows virtual memory manager for large blocks of
memory, so the failure should indicate that Windows couldn't allocate it.)

I made three changes to the program:
    Added a type Big_Int to replace Integer (better portability, especially
for a compiler
       with Integer'Size = 16);
    Replaced the GNAT-specific "Address_Image" with
      System.Storage_Elements.Integer_Address (clunky, but pure Ada);
    Replaced the call to Malloc with New.

The latter was done simply because end-running the compiler's memory
management is likely to cause bugs. And ours, at least, is designed to work
with any reasonable-sized chunk of memory. Finally, if I hadn't changed
that, it would not have worked, as Janus/Ada does not allow random memory to
be used with a pool-specific type. (Really, the access type should be a
general access type if you are going to end-run Ada's heap management.)

The test works with small enough numbers to run on my machine with 384Meg of
RAM (the top value being about 130_000_000). If you were our customer, I'd
try to figure out why the Storage_Error is being raised. Probably the answer
really is to use a supported compiler; you do really get what you pay for.

                       Randy.


 with Text_IO;
with System.Storage_Elements; -- Added, RLB.

procedure TestBig2 is

-- Test devised by Adrian Wrigley, amtw@linuxchip.demon.co.uk.uk.uk (one uk
is e
-- I disclaim all rights to this code.  Do what you wish with it!

-- This test case illustrates a problem with code
-- compiled on GNAT 3.15p for x86 under Linux

-- It shows that the 'Address of elements of large
-- arrays can be silently incorrect

-- Redid by Randy Brukardt to work with Janus/Ada; added an appropriate
Integer
-- type, use New to allocate, and removed GNAT specific stuff.

-- Notes:
--
-- This test works if the word "constant" is removed
--
-- The test also works if the value is less than 200_000_000
-- Indexing element also works with computed index
   Size : constant := 210_000_000;
   type Big_Int is range 0 .. Size;

   type Big_T is array (Big_Int range 1 .. Size) of aliased Float;

   type Big_A is access Big_T;

   Big : Big_A;

--   function GetSomeMemory (X : Integer) return Big_A;
--   pragma Import (C, GetSomeMemory, "malloc");

begin

--   Big := GetSomeMemory (Size*4 + 16); -- This seems to work OK for now
   Big := new Big_T;

   Text_IO.Put_Line ("First element attribute " & Big_Int'Image
(Big_T'First));
   Text_IO.Put_Line ("Last element attribute  " & Big_Int'Image
(Big_T'Last));

   Text_IO.Put_Line ("Address of first element is " &
        System.Storage_Elements.Integer_Address'Image(
           System.Storage_Elements.To_Integer(Big (Big_T'First)'Address)));
   Text_IO.Put_Line ("Address of last element is  " &
        System.Storage_Elements.Integer_Address'Image(
           System.Storage_Elements.To_Integer(Big (Big_T'Last)'Address)));
   Text_IO.Put_Line ("(Last element should be at higher address than
first)");


   declare
      J : Big_Int := Size;
   begin
      Text_IO.Put_Line ("Address of last element is " &
        System.Storage_Elements.Integer_Address'Image(
           System.Storage_Elements.To_Integer(Big (J)'Address)));
   end;

   Text_IO.Put_Line ("Writing to all elements in loop");
   for I in Big_T'Range loop
      Big (I) := 0.0;
   end loop;

   Text_IO.Put_Line ("Writing to 'Last element");
--raised STORAGE_ERROR : stack overflow (or erroneous memory access):
   Big (Big_T'Last) := 0.0; -- Fails!!!!!

end TestBig2;

Re: Large arrays (again), problem case for GNAT

[(see below)]

On 13/4/05 8:54 pm, in article ltGdnU4oIZ3j5cDfRVn-qw@megapath.net,
"Randy Brukardt" <randy@rrsoftware.com> wrote:

>  Text_IO.Put_Line ("Writing to all elements in loop");
>  for I in Big_T'Range loop
>     Big (I) := 0.0;
>  end loop;
> 
>  Text_IO.Put_Line ("Writing to 'Last element");
>  Big (Big_T'Last) := 0.0; -- Fails!!!!!

For better confirmation of success I changed this to:

>  Text_IO.Put_Line ("Writing to all elements in loop");
>  for I in Big_T'Range loop
>     Big (I) := Float(i);
>  end loop;
> 
>  Text_IO.Put_Line ("Reading 'Last element");
>  if Big (Big_T'Last) /= Float(Big_T'Last) then
>     Text_IO.Put_Line ("...FAILED");
>  else
>     Text_IO.Put_Line ("...OK");
>  end if;

It compiled and ran perfectly on my 640Mb Macintosh iBook,
GNAT 3.3 20040913 (GNAT for Mac OS X build 1650):

> First element attribute  1
> Last element attribute   210000000
> Address of first element is  33587200
> Address of last element is   873587196
> (Last element should be at higher address than first)
> Address of last element is  873587196
> Writing to all elements in loop
> Reading 'Last element
> ...OK

I see that Adrian is using Linux.
Is Linux not notorious for problems of this kind?

I seem to remember that it has some kind of optimistic allocator
that can grant a memory allocation request, only for it to fail
when you try to use the memory you appear to have been granted.

-- 
Bill Findlay
<surname><forename> chez blueyonder.co.uk

Re: Large arrays (again), problem case for GNAT

[Robert A Duff]

"(see below)" <yaldnif.b@blueyonder.co.uk> writes:

> I see that Adrian is using Linux.
> Is Linux not notorious for problems of this kind?
> 
> I seem to remember that it has some kind of optimistic allocator
> that can grant a memory allocation request, only for it to fail
> when you try to use the memory you appear to have been granted.

Hmm.  If the OS allocates virtual address space for that giant array,
but doesn't allocate physical memory, or backing store, for it, then an
access to that array could allocate memory, thus causing Storage_Error.
That would be legitimate behavior on the part of the Ada compiler.
Maybe Adrian should try increasing the size of the paging file?

But there's a loop writing 0.0 over the whole thing, so I would guess
*that* would actually allocate the memory.  Also, the above doesn't
explain why the 'Address attribute returns strange results.

I'm not sure why you say "notorious".  It seems to me that
allocate-on-write is desirable.

- Bob

Re: Large arrays (again), problem case for GNAT

[Alexander E. Kopilovich]

Robert A Duff wrote;

> "(see below)" <yaldnif.b@blueyonder.co.uk> writes:
>
> > I see that Adrian is using Linux.
> > Is Linux not notorious for problems of this kind?
> > 
> > I seem to remember that it has some kind of optimistic allocator
> that can grant a memory allocation request, only for it to fail
> when you try to use the memory you appear to have been granted.
>
>...
>
> I'm not sure why you say "notorious".  It seems to me that
> allocate-on-write is desirable.

So, what is the meaning of malloc call with this approach? In which court
(somewhere in Linux or outside) I should defend my right to use the memory,
which I legally requested by malloc, was granted, and then deprived of it?

Re: Large arrays (again), problem case for GNAT

[Dmitry A. Kazakov]

On Thu, 14 Apr 2005 05:11:56 +0400 (MSD), Alexander E. Kopilovich wrote:

> Robert A Duff wrote;
> 
>> "(see below)" <yaldnif.b@blueyonder.co.uk> writes:
>>
>>> I see that Adrian is using Linux.
>>> Is Linux not notorious for problems of this kind?
>>> 
>>> I seem to remember that it has some kind of optimistic allocator
>> that can grant a memory allocation request, only for it to fail
>> when you try to use the memory you appear to have been granted.
>>
>>...
>>
>> I'm not sure why you say "notorious".  It seems to me that
>> allocate-on-write is desirable.
> 
> So, what is the meaning of malloc call with this approach? In which court
> (somewhere in Linux or outside) I should defend my right to use the memory,
> which I legally requested by malloc, was granted, and then deprived of it?

It is a well known and very old design flaw of many OSes including Linux,
that successful allocation does not give you any amount of virtual memory
until you commit the pages. It is not memory you are granted, it is even
not virtual memory, it is address space which is worth of nothing. This
controversy is as old as in-out parameters of Ada functions...

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Large arrays (again), problem case for GNAT

[Duncan Sands]

> It is a well known and very old design flaw of many OSes including Linux,
> that successful allocation does not give you any amount of virtual memory
> until you commit the pages. It is not memory you are granted, it is even
> not virtual memory, it is address space which is worth of nothing. This
> controversy is as old as in-out parameters of Ada functions...

The reason for doing it is pragmatic: many programs allocate memory that
they never use.  By not actually giving them memory until they really use
it, there's more memory for other programs.  This makes writing programs
that fail gracefully in out-of-memory situations even harder than usual.
With Linux, you can choose the memory allocation policy on a system wide
basis, as I mentioned in another email.

Ciao,

D.

Re: Large arrays (again), problem case for GNAT

[Marius Amado Alves]

On 14 Apr 2005, at 08:45, Duncan Sands wrote:

> The reason for doing it is pragmatic: many programs allocate memory 
> that
> they never use....

This problem seems easy to solve then. Just allocate and immediately 
write some stuff to the start and end of the block.

Re: Large arrays (again), problem case for GNAT

[Dr. Adrian Wrigley]

On Thu, 14 Apr 2005 14:59:01 +0100, Marius Amado Alves wrote:

> 
> On 14 Apr 2005, at 08:45, Duncan Sands wrote:
> 
>> The reason for doing it is pragmatic: many programs allocate memory 
>> that
>> they never use....
> 
> This problem seems easy to solve then. Just allocate and immediately 
> write some stuff to the start and end of the block.

You need to write something to *every* machine page to make sure
real memory is allocated.  If there isn't enough memory, you
probably can't do anything about it (can you trap this at all?).
But at least it fails early, rather than at a random point much later.
-- 
Adrian

Re: Large arrays (again), problem case for GNAT

[(see below)]

On 14/4/05 3:09 pm, in article
pan.2005.04.14.14.09.18.977493@linuxchip.demon.co.uk.uk.uk,
"Dr. Adrian Wrigley" <amtw@linuxchip.demon.co.uk.uk.uk> wrote:

> 
> You need to write something to *every* machine page to make sure
> real memory is allocated.  If there isn't enough memory, you
> probably can't do anything about it (can you trap this at all?).
> But at least it fails early, rather than at a random point much later.

Indeed, and after the program had undertaken costly operations that
might be even more costly to revert, if that were even possible.

-- 
Bill Findlay
<surname><forename> chez blueyonder.co.uk

Re: Large arrays (again), problem case for GNAT

[Duncan Sands]

On Thu, 2005-04-14 at 14:59 +0100, Marius Amado Alves wrote:
> On 14 Apr 2005, at 08:45, Duncan Sands wrote:
> 
> > The reason for doing it is pragmatic: many programs allocate memory 
> > that
> > they never use....
> 
> This problem seems easy to solve then. Just allocate and immediately 
> write some stuff to the start and end of the block.

No, you have to write to every page (usually 4k in size).

Ciao,

D.

Re: Large arrays (again), problem case for GNAT

[Robert A Duff]

"Alexander E. Kopilovich" <aek@VB1162.spb.edu> writes:

> Robert A Duff wrote;
> 
> > "(see below)" <yaldnif.b@blueyonder.co.uk> writes:
> >
> > > I see that Adrian is using Linux.
> > > Is Linux not notorious for problems of this kind?
> > > 
> > > I seem to remember that it has some kind of optimistic allocator
> > that can grant a memory allocation request, only for it to fail
> > when you try to use the memory you appear to have been granted.
> >
> >...
> >
> > I'm not sure why you say "notorious".  It seems to me that
> > allocate-on-write is desirable.
> 
> So, what is the meaning of malloc call with this approach? In which court
> (somewhere in Linux or outside) I should defend my right to use the memory,
> which I legally requested by malloc, was granted, and then deprived of it?

You have no such right!  ;-)

You've allocated address space, and it's perfectly legitimate (according
to the Ada RM, and according to Linux docs) for the system to run out of
memory when you touch it.  I admit that it would be easier to program if
you could isolate the Storage_Error to the allocation point, presuming
you want to handle Storage_Error and recover somehow.

But Storage_Error is pretty broken in Ada anyway.  It's practically
impossible to write a formally correct handler for this exception.

AARM-11.1 says:

6     The execution of any
construct raises Storage_Error if there is insufficient storage for that
execution.  The amount of storage needed for the
execution of constructs is unspecified.

    6.a   Ramification: Note that any execution whatsoever can raise
          Storage_Error. This allows much implementation freedom in
          storage management.

The reason I like allocate-on-write is that it is very useful to
allocate a huge array, and then only use some part of it.  That way, the
program can deal with enormous input data, without paying the cost when
the input data is small.  Physical memory is 1000 times more expensive
than address space.

Does anybody here know how to get allocate-on-write under MS Windows?

But I admit it would be useful to be able to turn off allocate-on-write
for particular objects.  Somebody posted a note telling how to do that
on Linux, but unfortunately it's apparently global to the whole system,
which just isn't good enough, in my opinion.

You could achieve that by touching every page, but it's not portable:
the Ada manual doesn't guarantee anything about that, and you have to
know the page size and understand the underlying OS behavior.
I can imagine a system where touching every page does not necessarily
allocate physical memory.

The original example that started this thread *did* touch every page;
it's a mystery to me why this didn't work.

- Bob

Re: Large arrays (again), problem case for GNAT

[Robert A Duff]

Robert A Duff <bobduff@shell01.TheWorld.com> writes:

> Does anybody here know how to get allocate-on-write under MS Windows?

Just to be clear: Windows does not allocate physical memory on
allocation, but it does allocate backing store in the page file.
And the page file is limited to 4GB, which isn't all that big
these days.  Does anybody know how to tell Windows not to
allocate backing store?

I want to write a Storage_Pool, which allocates an array of (say)
hundreds of megabytes, and allocate little pieces out of that giant
array.  I want to be *able* to use all those hundreds of megabytes, but
I don't want to allocate space in the paging file unless they're
needed.  This works by default on most Unices, but not on Windows.

- Bob

Re: Large arrays (again), problem case for GNAT

[Randy Brukardt]

"Robert A Duff" <bobduff@shell01.TheWorld.com> wrote in message
news:wccbr8h4c0f.fsf@shell01.TheWorld.com...
> Robert A Duff <bobduff@shell01.TheWorld.com> writes:
>
> > Does anybody here know how to get allocate-on-write under MS Windows?
>
> Just to be clear: Windows does not allocate physical memory on
> allocation, but it does allocate backing store in the page file.
> And the page file is limited to 4GB, which isn't all that big
> these days.  Does anybody know how to tell Windows not to
> allocate backing store?
>
> I want to write a Storage_Pool, which allocates an array of (say)
> hundreds of megabytes, and allocate little pieces out of that giant
> array.  I want to be *able* to use all those hundreds of megabytes, but
> I don't want to allocate space in the paging file unless they're
> needed.  This works by default on most Unices, but not on Windows.

You can do something like that with the actual memory management functions
of Windows, which separately allocate and commit pages. (Commit uses the
backing store.) But you get a trap if the pages aren't commited and are
touched.

I have a storage pool that sort of works this way. It was intended to allow
allocating virtual space for large arrays, and then expand them as needed
with committed memory. Warning: although Windows uses 4K pages, address
space management allocation is done in 64K chunks. Ask for 1 byte, and you
get one byte, and the other 63.9K is lost to all other use. My pool expands
the arrays by rewriting the dope of the arrays passed into the functions -
something that no one should ever do unless they're the author of the
compiler. And probably not even then.

I'll e-mail to it you.

                     Randy.

Re: Large arrays (again), problem case for GNAT

[Dr. Adrian Wrigley]

On Fri, 15 Apr 2005 00:21:50 -0500, Randy Brukardt wrote:

> My pool expands
> the arrays by rewriting the dope of the arrays passed into the functions -
> something that no one should ever do unless they're the author of the
> compiler. And probably not even then.

I did this a lot a few years ago with GNAT.  It worked extremely well.
(no I'm not the author of the compiler!)

I couldn't understand why there was no decent mechanism for changing
the size of an array.  The resulting code was much cleaner, faster
and more memory efficient than using fancy data structures/container
libraries.

Why did the language not provide an equivalent of 'realloc' for
arrays?  What is the best work-around?  Are we supposed to allocate
a completely new array and copy everything over, and deallocate the old?
Does Ada 2005 really help give efficient resizable arrays at all?

Thanks for views!
-- 
Adrian Wrigley, Cambridge, uk.
(one uk in email address!)

Re: Large arrays (again), problem case for GNAT

[Dmitry A. Kazakov]

On Fri, 15 Apr 2005 11:49:23 GMT, Dr. Adrian Wrigley wrote:

> On Fri, 15 Apr 2005 00:21:50 -0500, Randy Brukardt wrote:
> 
>> My pool expands
>> the arrays by rewriting the dope of the arrays passed into the functions -
>> something that no one should ever do unless they're the author of the
>> compiler. And probably not even then.
> 
> I did this a lot a few years ago with GNAT.  It worked extremely well.
> (no I'm not the author of the compiler!)
> 
> I couldn't understand why there was no decent mechanism for changing
> the size of an array.  The resulting code was much cleaner, faster
> and more memory efficient than using fancy data structures/container
> libraries.
> 
> Why did the language not provide an equivalent of 'realloc' for
> arrays?

I would propose:

generic
   type Element_Type is limited private;
   type Index_Type is (<>);
   type Array_Type is array (Index_Type) of Element_Type;
   type Access_Type is access Array_Type;
procedure Ada.Array_Resize (X : in out Access_Type; Elements : Integer);

and 

generic
   type Element_Type is private;
   type Index_Type is (<>);
   type Array_Type is array (Index_Type) of Element_Type;
   type Access_Type is access Array_Type;
procedure Ada.Array_Expand
   (  X : in out Access_Type;
      Elements : Natural;
      Initial : Element_Type
   );

- Element_Type is limited in the variant with 2 arguments and for an actual
array of limited elements the implementation ensures that the result will
not be moved in the address space. Otherwise Storage_Error is propagated.

- For arrays of non-limited components the implementation is free to copy,
adjust, finalize elements.

- When Elements is negative the removed elements are properly finalized.

- Storage_Error is propagated when the array wasn't re-sized as required,
but X.all is valid.

- Program_Error is propagated when X.all becomes invalid, for example after
element's initialization/finalization exceptions.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Large arrays (again), problem case for GNAT

[Dr. Adrian Wrigley]

On Fri, 15 Apr 2005 15:21:32 +0200, Dmitry A. Kazakov wrote:

> On Fri, 15 Apr 2005 11:49:23 GMT, Dr. Adrian Wrigley wrote:
> 
...
>> I couldn't understand why there was no decent mechanism for changing
>> the size of an array.  The resulting code was much cleaner, faster
>> and more memory efficient than using fancy data structures/container
>> libraries.
>> 
>> Why did the language not provide an equivalent of 'realloc' for
>> arrays?
> 
> I would propose:
> 
> generic
>    type Element_Type is limited private;
>    type Index_Type is (<>);
>    type Array_Type is array (Index_Type) of Element_Type;
>    type Access_Type is access Array_Type;
> procedure Ada.Array_Resize (X : in out Access_Type; Elements : Integer);
> 
> and 
> 
> generic
>    type Element_Type is private;
>    type Index_Type is (<>);
>    type Array_Type is array (Index_Type) of Element_Type;
>    type Access_Type is access Array_Type;
> procedure Ada.Array_Expand
>    (  X : in out Access_Type;
>       Elements : Natural;
>       Initial : Element_Type
>    );

This looks plausible.  Could we specify the new 'Last index instead of
the Elements parameter? (what about a new 'First index?) Maybe you'd
have difficulty creating a zero element array though.

It'd be nice if it was less verbose too. 'new' seems so simple
to use - something equally simple would be nice for resizing.
Maybe an extra parameter for new or something(?)
-- 
Adrian

Re: Large arrays (again), problem case for GNAT

[Dmitry A. Kazakov]

On Fri, 15 Apr 2005 14:31:30 GMT, Dr. Adrian Wrigley wrote:

> On Fri, 15 Apr 2005 15:21:32 +0200, Dmitry A. Kazakov wrote:
> 
>> On Fri, 15 Apr 2005 11:49:23 GMT, Dr. Adrian Wrigley wrote:
>> 
> ...
>>> I couldn't understand why there was no decent mechanism for changing
>>> the size of an array.  The resulting code was much cleaner, faster
>>> and more memory efficient than using fancy data structures/container
>>> libraries.
>>> 
>>> Why did the language not provide an equivalent of 'realloc' for
>>> arrays?
>> 
>> I would propose:
>> 
>> generic
>>    type Element_Type is limited private;
>>    type Index_Type is (<>);
>>    type Array_Type is array (Index_Type) of Element_Type;
>>    type Access_Type is access Array_Type;
>> procedure Ada.Array_Resize (X : in out Access_Type; Elements : Integer);
>> 
>> and 
>> 
>> generic
>>    type Element_Type is private;
>>    type Index_Type is (<>);
>>    type Array_Type is array (Index_Type) of Element_Type;
>>    type Access_Type is access Array_Type;
>> procedure Ada.Array_Expand
>>    (  X : in out Access_Type;
>>       Elements : Natural;
>>       Initial : Element_Type
>>    );
> 
> This looks plausible.  Could we specify the new 'Last index instead of
> the Elements parameter? (what about a new 'First index?)

Sounds interesting especially because "renames" handles it wrong. It might
be very useful not to expand but just to adjust array view by moving 'First
and 'Last. Typical case is:

procedure Copy (X : in out My_Array; Y : in My_Array) is
begin
   if X'Length /= Y'Length then raise ...;

Now I know that I can copy Y to X, but I cannot synchronize their views to
avoid range checks, clumsy I - X'First + Y'First and headache about
possible overflows in the index expressions.

> Maybe you'd
> have difficulty creating a zero element array though.
> 
> It'd be nice if it was less verbose too. 'new' seems so simple
> to use - something equally simple would be nice for resizing.
> Maybe an extra parameter for new or something(?)

It isn't "new" it is a mixture of "renames", "new" and
Unchecked_Deallocation. We could speculate about sugar like "with new" but
what should be the right side:

declare
   X : My_Array_Ptr := new My_Array (1..100_000);
begin
   ...
   X := X with new (1..100_000 => 0.0); -- This is seems OK

but what to do with arrays of limited elements?

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Large arrays (again), problem case for GNAT

[Dr. Adrian Wrigley]

On Thu, 14 Apr 2005 11:18:22 -0400, Robert A Duff wrote:

> The original example that started this thread *did* touch every page;
> it's a mystery to me why this didn't work.

It *did* work. And it wrote the correct values to the correct addresses
(I checked this).

This failure at the end was writing into the last element using:
Big (Big_T'Last) := 0.0;

The reason this fails is that the offset into 'Big' is
(incorrectly) calculated at compile time (since Big_T'Last
is constant). The calculation is faulty, apparently based
on bits offset in a 32-bit signed quantity.  This exceeds
2Gbit (silently), and generates code to access 'Big' with
a negative offset - which touches unallocated addresses.
This analysis is supported by the incorrect calculation
of the address of the last value, output a few lines earlier.

The work-around for my code at present is to take out the
word 'constant' in the declaration of 'Size'.  Now works nicely!
-- 
Adrian

Re: Large arrays (again), problem case for GNAT

[Dmitry A. Kazakov]

On 14 Apr 2005 11:18:22 -0400, Robert A Duff wrote:

> The reason I like allocate-on-write is that it is very useful to
> allocate a huge array, and then only use some part of it.  That way, the
> program can deal with enormous input data, without paying the cost when
> the input data is small.  Physical memory is 1000 times more expensive
> than address space.

I think this approach is flawed. The contract of malloc is to return memory
not the address space. That must be just another system call.

Consider an application that needs contiguous address space. User storage
pool is an excellent example. The application must request the space from
OS telling something like: "reserve me 100GB and allocate n bytes starting
from the first address." After that it could allocate memory *within* that
space by pieces as needed. For this it would simply use realloc instead of
malloc. No need to break contracts.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Large arrays (again), problem case for GNAT

[Robert A Duff]

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:

> On 14 Apr 2005 11:18:22 -0400, Robert A Duff wrote:
> 
> > The reason I like allocate-on-write is that it is very useful to
> > allocate a huge array, and then only use some part of it.  That way, the
> > program can deal with enormous input data, without paying the cost when
> > the input data is small.  Physical memory is 1000 times more expensive
> > than address space.
> 
> I think this approach is flawed. The contract of malloc is to return memory
> not the address space. 

Well, I'm not an expert on malloc.  Where is it documented that this is
the contract?  Apparently the Linux folks don't think that's the
contract.

I *am* an expert on Ada, and I know that "new" does not necessarily
reserve real memory -- it might just reserve address space.

>...That must be just another system call.

I agree that there *should* be two separate calls: one reserves address
space, and the other reserves real memory.  Or one call with a Boolean
parameter.

> Consider an application that needs contiguous address space. User storage
> pool is an excellent example. The application must request the space from
> OS telling something like: "reserve me 100GB and allocate n bytes starting
> from the first address." After that it could allocate memory *within* that
> space by pieces as needed. For this it would simply use realloc instead of
> malloc.

No, I don't want to do realloc or anything like that.  I just want it to
allocate physical memory (and backing store) when I write upon that
memory.  Apparently, malloc on Linux is exactly the "reserve me 100GB
and allocate n bytes starting from the first address" primitive, except
there's no need for the "allocate n bytes starting from the first
address" part.  And it does exactly what I want in the storage-pool
example.

I understand that other examples would prefer to prevent Storage_Error
happening willy-nilly all over the place.  Ada does not provide that
semantics, and apparently Linux does not either, unless you set some
global flag.

>... No need to break contracts.

I don't think Linux (or GNAT upon Linux) is breaking any contract.
You just don't like what the contract defines!  Fair enough.

- Bob

P.S. Nobody has challenged my remark that Storage_Error handlers are
impossible.  ;-)

Re: Large arrays (again), problem case for GNAT

[Dmitry A. Kazakov]

On 14 Apr 2005 17:19:31 -0400, Robert A Duff wrote:

> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
> 
>> On 14 Apr 2005 11:18:22 -0400, Robert A Duff wrote:
>> 
>>> The reason I like allocate-on-write is that it is very useful to
>>> allocate a huge array, and then only use some part of it.  That way, the
>>> program can deal with enormous input data, without paying the cost when
>>> the input data is small.  Physical memory is 1000 times more expensive
>>> than address space.
>> 
>> I think this approach is flawed. The contract of malloc is to return memory
>> not the address space. 
> 
> Well, I'm not an expert on malloc.  Where is it documented that this is
> the contract?

OK, let's call it an implied contract. The result of malloc is either 0 or
a valid pointer as long as C does not distinguish pointers and addresses.

> Apparently the Linux folks don't think that's the contract.

Yes I know. I participated in discussions on this issue 10+ years ago in
Linux groups. Nothing has changed since then. It is still badly wrong.

> I *am* an expert on Ada, and I know that "new" does not necessarily
> reserve real memory -- it might just reserve address space.

I think that this should be changed. Consider a tagged object.
Storage_Error could be raised in Initialize! Even worse, if the constructor
does not touch all bits, then you might get a properly constructed object
which is potentially unusable. It is a disaster. This is what people have
with that large arrays.

[ BTW, as a palliative, what about the attribute X'Valid, where X is a
pointer. X'Valid should be false in all cases when X.all is not properly
allocated (may result in Storage_Error.) ]

>>...That must be just another system call.
> 
> I agree that there *should* be two separate calls: one reserves address
> space, and the other reserves real memory.  Or one call with a Boolean
> parameter.
> 
>> Consider an application that needs contiguous address space. User storage
>> pool is an excellent example. The application must request the space from
>> OS telling something like: "reserve me 100GB and allocate n bytes starting
>> from the first address." After that it could allocate memory *within* that
>> space by pieces as needed. For this it would simply use realloc instead of
>> malloc.
> 
> No, I don't want to do realloc or anything like that.  I just want it to
> allocate physical memory (and backing store) when I write upon that
> memory.

You cannot write into memory you don't have. Moreover, either in Ada or in
any other higher level language one simply cannot define the term "memory
write" in a way which would allow any reasonable handling of "write
errors". But in the case of the storage pool your program *knows* that it
does not have this memory. So it can allocate it using realloc without any
assumptions about OS behavior which might appear wrong.

[ Here I mean imaginary malloc and realloc and not Linux ones. The contract
or realloc should be that if I call it on a pointer which memory block is
followed by free address space, then the result will be the same pointer if
the additional memory is allocated and fits into the space ]

> Apparently, malloc on Linux is exactly the "reserve me 100GB
> and allocate n bytes starting from the first address" primitive, except
> there's no need for the "allocate n bytes starting from the first
> address" part.  And it does exactly what I want in the storage-pool
> example.

But your storage pool will be simply unusable for many applications. And
that is independent on the fact that Storage_Error cannot be handled.
Consider an application that allocates something in your pool and then
starts series of transactions with a data base. In the middle of this
business it will crash leaving data in some unpredictable state! I wouldn't
equalize this scenario to memory check-sum error etc.

> I understand that other examples would prefer to prevent Storage_Error
> happening willy-nilly all over the place.  Ada does not provide that
> semantics, and apparently Linux does not either, unless you set some
> global flag.

I think that Ada should differentiate Storage_[Access]_Error and
Storage_[Allocation]_Error.

>>... No need to break contracts.
> 
> I don't think Linux (or GNAT upon Linux) is breaking any contract.
> You just don't like what the contract defines! Fair enough.
>
> - Bob
> 
> P.S. Nobody has challenged my remark that Storage_Error handlers are
> impossible.  ;-)

Maybe because you are right! (:-))

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Large arrays (again), problem case for GNAT

[Duncan Sands]

You know, this is just like overbooking on airplanes.  You don't notice
when you benefit from it (you get to buy a ticket and fly even though
the plane was sold out), but for sure you notice when it goes against
you (you aren't allowed on the plane because everyone else turned up
too).

With a computer you also have backing store (swap), which means that
when the plane starts getting full, sleeping passengers are quietly
shifted to a donkey cart :)

Ciao,

Duncan.

Re: Large arrays (again), problem case for GNAT

[Dmitry A. Kazakov]

On Fri, 15 Apr 2005 10:38:14 +0200, Duncan Sands wrote:

> You know, this is just like overbooking on airplanes.  You don't notice
> when you benefit from it (you get to buy a ticket and fly even though
> the plane was sold out), but for sure you notice when it goes against
> you (you aren't allowed on the plane because everyone else turned up
> too).

I heard that EU has ordered a compensation to be paid...

> With a computer you also have backing store (swap), which means that
> when the plane starts getting full, sleeping passengers are quietly
> shifted to a donkey cart :)

It is rather like all aircrafts doing emergency landing and everybody
proceeds afoot. (:-))

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Large arrays (again), problem case for GNAT

[Mark Lorenzen]

Robert A Duff <bobduff@shell01.TheWorld.com> writes:

> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
> 
> > On 14 Apr 2005 11:18:22 -0400, Robert A Duff wrote:
> > 
> > > The reason I like allocate-on-write is that it is very useful to
> > > allocate a huge array, and then only use some part of it.  That way, the
> > > program can deal with enormous input data, without paying the cost when
> > > the input data is small.  Physical memory is 1000 times more expensive
> > > than address space.
> > 
> > I think this approach is flawed. The contract of malloc is to return memory
> > not the address space. 
> 
> Well, I'm not an expert on malloc.  Where is it documented that this is
> the contract?  Apparently the Linux folks don't think that's the
> contract.

Exactly. As mentioned in another post, it is a popular implementation
strategy to only allocate memory on write in order to save the system
from memory exhaustion.

> 
> I *am* an expert on Ada, and I know that "new" does not necessarily
> reserve real memory -- it might just reserve address space.
> 
> >...That must be just another system call.
> 
> I agree that there *should* be two separate calls: one reserves address
> space, and the other reserves real memory.  Or one call with a Boolean
> parameter.

A simple "man malloc" specifies that the default overcommitting
behaviour can be turned of by writing the letter "2" to the file
/proc/sys/vm/overcommit_memory . F.x.:

echo 2 > /proc/sys/vm/overcommit_memory

- Mark Lorenzen

<snip>

Re: Large arrays (again), problem case for GNAT

[Robert A Duff]

Mark Lorenzen <mark.lorenzen@surfpost.dk> writes:

> A simple "man malloc" specifies that the default overcommitting
> behaviour can be turned of by writing the letter "2" to the file
> /proc/sys/vm/overcommit_memory . F.x.:
> 
> echo 2 > /proc/sys/vm/overcommit_memory

Well, that's not much use.  Whether you want to overcommit depends on
the situation.  Some programs are written with overcommit in mind,
so you can't just globally turn it off.  Ideally, it would be
controllable on a per-object basis.  It should be controlled by
the programmer, not by the user/system-administrator.

Not just heap objects, either.  I'd like to have overcommit for
statically allocated (library level) variables, so I'd want to
be able to turn that off or on.

- Bob

Re: Large arrays (again), problem case for GNAT

[Duncan Sands]

> So, what is the meaning of malloc call with this approach? In which court
> (somewhere in Linux or outside) I should defend my right to use the memory,
> which I legally requested by malloc, was granted, and then deprived of it?

Hi Alexander, I'd be interested to see the standard that stipulates that
the default linux behavior is illegal.  Anyway, you can choose the
strategy by writing to /proc/sys/vm/overcommit_memory.  Here is what the
documentation for 2.6 kernels says:

> overcommit_memory:
> 
> This value contains a flag that enables memory overcommitment.
> 
> When this flag is 0, the kernel attempts to estimate the amount
> of free memory left when userspace requests more memory.
> 
> When this flag is 1, the kernel pretends there is always enough
> memory until it actually runs out.
> 
> When this flag is 2, the kernel uses a "never overcommit"
> policy that attempts to prevent any overcommit of memory.
> 
> This feature can be very useful because there are a lot of
> programs that malloc() huge amounts of memory "just-in-case"
> and don't use much of it.
> 
> The default value is 0.
> 
> See Documentation/vm/overcommit-accounting and
> security/commoncap.c::cap_vm_enough_memory() for more information.

Re: Large arrays (again), problem case for GNAT

[Robert A Duff]

"Dr. Adrian Wrigley" <amtw@linuxchip.demon.co.uk.uk.uk> writes:

> Hi guys!
> 
> A month or two back I hinted that I had been having problems
> the GNAT code accessing large data structures.  It seemed that
> incorrect code was silently being generated.  Since I didn't
> have a test case available, no progress could be made.
> 
> I have encountered the problem again, and produced a test case.

Interesting.

I ran your program on windows XP professional, using GNAT version 5.03a,
which is a supported version.  It ran fine, and produced this output:

First element attribute  1
Last element attribute   210000000
Address of first element is 02570020
Address of last element is  3468621C
(Last element should be at higher address than first)
Address of last element is 3468621C
Writing to all elements in loop
Writing to 'Last element

It ran in a few seconds.  I changed Size to 410_000_000, and it still
worked fine (but took longer).  At 510_000_000 the malloc failed.

Why do you use malloc?  Why didn't you write:

    Big := new Big_T;

?  I'm not sure it makes any difference in this case,
but in general, if you're going to play games with memory
allocation, you should use storage pools, rather than relying
on the hope that malloc returns something that the Ada compiler
likes.  If you had an access to unconstrained array, the malloc
method would almost certainly fail, unless you wrap it in the proper
storage pool thing.

Also, I would think "access" should be "access all" if you're playing
those games.

I suspect your problem is an OS problem, and not a GNAT problem.

- Bob

Re: Large arrays (again), problem case for GNAT

[Dr. Adrian Wrigley]

On Wed, 13 Apr 2005 18:35:42 -0400, Robert A Duff wrote:

> Why do you use malloc?  Why didn't you write:
> 
>     Big := new Big_T;

(I explain this in another post.  There seems to be a bug
in 'new's size calculation, causing it to fail)

> ?  I'm not sure it makes any difference in this case,
> but in general, if you're going to play games with memory
> allocation, you should use storage pools, rather than relying
> on the hope that malloc returns something that the Ada compiler
> likes.  If you had an access to unconstrained array, the malloc
> method would almost certainly fail, unless you wrap it in the proper
> storage pool thing.

I thought I read somewhere that 'import/export' of C pointer values into
simple access values (without constraints/variants) is designed
to work in the obvious way.  If the access value is incompatible
with a 'C' pointer, the compiler (GNAT) generates a warning.
But it is obviously an area of potential hazard, relying on
a compiler warning if code becomes broken.

...
> I suspect your problem is an OS problem, and not a GNAT problem.

Curiously, removing the word "constant" on the Size value allows
the program to run fine!

I think the crux of the problem is illustrated by the erroneous
'Address values.  This problem occurs without needing valid
memory allocated, and minises the risk of OS issues interfering.
(failure of 'new' is a bit of a give-away too!)

In doing these tests (triggered by a failure on a real application),
I have characterised the problem, and now understand how to work
around these 3.15p/x86 issues. I'm told that 3.14p and 3.15p have
the problem, and 3.4, 5.01, and 4.0 prerelease work fine. (thanks Dan!)

Thanks!
-- 
Adrian

Re: Large arrays (again), problem case for GNAT

[Dr. Adrian Wrigley]

Hi!

Thank you very much for the feedback on this, particularly
those reporting success on particular configurations.

I should also comment:

I used 'malloc' rather then 'new' for two reasons:

1) Using 'new' fails, giving "raised STORAGE_ERROR : object too large"
   (in spite of having enough store to malloc and use)

2) My original program used 'mmap', but this is much more verbose
   to set up.  On Linux, large 'malloc' uses mmap anyway.

I calculate the size to allocate manually because attempting
to use the 'Size attribute fails (even when converted to a
suitably large type).

In fact the 'Size attribute fails on objects over 2147483647 bits :(
Sometimes this failure is silent (not trapped even with -gnato),
sometimes it gets a constaint error at compile time.

(The test supplied also fails with Size set to 67_108_865, which
is the smallest failing case.  This just exceeds the 2Gbit size limit.
In the 4-6Gbit region, the access to the 'last element is to the
wrong address, silently.  This is potentially serious!)

I have just tried the same code on GNAT/gcc 3.4.2 (Fedora Core 3, x86).
Everything works correctly, as far as I can tell!

My conclusions:

1) Update compilers more often!
   Don't expect (32-bit) 3.15p to work properly on large data

2) Convert 'size to a large type (eg 64-bit) before
   calculating bytes etc.

(and upgrade to x86-64 and 64-bit GNAT as soon as practicable)
(and pay for support if this kind of thing matters!)
-- 
Adrian Wrigley, Cambridge, UK.

Re: Large arrays (again), problem case for GNAT

[Robert A Duff]

"Dr. Adrian Wrigley" <amtw@linuxchip.demon.co.uk.uk.uk> writes:

> Hi!
> 
> Thank you very much for the feedback on this, particularly
> those reporting success on particular configurations.
> 
> I should also comment:
> 
> I used 'malloc' rather then 'new' for two reasons:
> 
> 1) Using 'new' fails, giving "raised STORAGE_ERROR : object too large"
>    (in spite of having enough store to malloc and use)

'malloc' should work for the case you showed, where the array is
constrained, and there are no default initializations, etc.
In more complicated cases, you would need to hide 'malloc' behind
a storage pool in order to make things work properly.

> 2) My original program used 'mmap', but this is much more verbose
>    to set up.  On Linux, large 'malloc' uses mmap anyway.
> 
> I calculate the size to allocate manually because attempting
> to use the 'Size attribute fails (even when converted to a
> suitably large type).
> 
> In fact the 'Size attribute fails on objects over 2147483647 bits :(
> Sometimes this failure is silent (not trapped even with -gnato),
> sometimes it gets a constaint error at compile time.

Yeah, it was a language design mistake to measure everything in bits.
In 1983, it might have been unthinkable that a single object would be as
big as 1/8 the address space on a 32-bit machine.  But 16-bit machines
with 16 bits worth of real memory were common in those days, and the
same issue arises there.

But surely silent overflow is a compiler bug!

Actually, now that I think about it, it seems like non-silent overflow
is a compiler bug too.  The value of 'Size is universal_integer.  And
there's a rule somewhere (which I'm too lazy to look up) that says
non-static values of type universal_integer must be calculated using
the largest integer type allowed.  Since GNAT supports 64-bit integers,
it ought to be using that for 'Size when necessary.  Of course, this is
not portable, since compiles are not required to support 64-bit
integers.

- Bob

Re: Large arrays (again), problem case for GNAT

[Dmitry A. Kazakov]

On 14 Apr 2005 11:03:17 -0400, Robert A Duff wrote:

>> In fact the 'Size attribute fails on objects over 2147483647 bits :(
>> Sometimes this failure is silent (not trapped even with -gnato),
>> sometimes it gets a constaint error at compile time.
> 
> Yeah, it was a language design mistake to measure everything in bits.

Is there anything smaller than one bit? (:-))

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Large arrays (again), problem case for GNAT

[Pascal Obry]

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:

> Is there anything smaller than one bit? (:-))

Yes a weak-bit :) Do you remember the time of floppy disk. A specific copy
protection was to read/write many time at the same address a 0 and a 1. After
some time when reading at this specific location you got either a 0 or a 1.
This was use as a copy-protection by some softwares. Amazinlgy Copywrite (a
nice copy tool at this time) was able to reproduce a weak-bit.

So somehow yes a weak-bit was smaller than a plain-bit :)

Should I add that this is plain OT !

Pascal.

-- 

--|------------------------------------------------------
--| Pascal Obry                           Team-Ada Member
--| 45, rue Gabriel Peri - 78114 Magny Les Hameaux FRANCE
--|------------------------------------------------------
--|              http://www.obry.net
--| "The best way to travel is by means of imagination"
--|
--| gpg --keyserver wwwkeys.pgp.net --recv-key C1082595

Re: Large arrays (again), problem case for GNAT

[Dmitry A. Kazakov]

On 14 Apr 2005 20:30:49 +0200, Pascal Obry wrote:

> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
> 
>> Is there anything smaller than one bit? (:-))
> 
> Yes a weak-bit :) Do you remember the time of floppy disk. A specific copy
> protection was to read/write many time at the same address a 0 and a 1. After
> some time when reading at this specific location you got either a 0 or a 1.
> This was use as a copy-protection by some softwares. Amazinlgy Copywrite (a
> nice copy tool at this time) was able to reproduce a weak-bit.
> 
> So somehow yes a weak-bit was smaller than a plain-bit :)

Hmm, that looks rather like a random bit, which number of states (assuming
the theory of hidden parameter) could be from two to any possible cardinal
and even larger. That can't be smaller than 1! (:-))

But what could indeed be, is a read-only content. It has only one state, so
if you choose an appropriate encoding that codes YOUR program as 0 and
anything else as 1xxxxx..., then YOUR very special program can be put into
0 bit memory! (:-))

> Should I add that this is plain OT !

Yep, a shameless one! (:-))

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Large arrays (again), problem case for GNAT

[Duncan Sands]

> Can someone test this on later versions of GNAT please?

gcc version 3.4.4 20050328 (prerelease) for GNAT Pro 5.04w (20050326)

$ ./testbug
First element attribute  1
Last element attribute   210000000

raised CONSTRAINT_ERROR : testbug.adb:39 access check failed

Ciao,

Duncan.

PS: I couldn't reply directly to Adrian:

RCPT TO <amtw@linuxchip.demon.co.uk.uk.uk> failed: Requested action not
taken: mailbox unavailable.

Re: Large arrays (again), problem case for GNAT

[Dr. Adrian Wrigley]

On Wed, 13 Apr 2005 15:52:57 +0200, Duncan Sands wrote:

>> Can someone test this on later versions of GNAT please?
> 
> gcc version 3.4.4 20050328 (prerelease) for GNAT Pro 5.04w (20050326)
> 
> $ ./testbug
> First element attribute  1
> Last element attribute   210000000
> 
> raised CONSTRAINT_ERROR : testbug.adb:39 access check failed

Sorry guys, forgot a couple of things:

Didn't put in a check for malloc failing... doesn't everyone have 6GB
  of RAM+SWAP nowadays? (Presumably malloc returned NULL)

Didn't highlight the mutilated email address (one uk is enough!)
-- 
Adrian