Re: Efficient Matrix?

Re: Efficient Matrix?

[Adrian Knoth]

Jonas Gasser <jonas.gasser@dataflow.ch> wrote:

> type MATRIX is array (POSITIVE range <>, POSITIVE range <>) of BOOLEAN;
> type POINTER_MATRIX is access all MATRIX;
> A : POINTER_MATRIX := new MATRIX(1..10000,1..5000);
 
> ideas to optimize this.

You might want to pack it. And you might even want to think about
your style. Here is an example:

procedure bla is

   type MATRIX is array (Positive range <>, Positive range <>) of Boolean;
   type POINTER_MATRIX is access all MATRIX;

   pragma Pack (MATRIX);

   A : POINTER_MATRIX := new MATRIX (1 .. 10000, 1 .. 5000);

begin
   null;
end bla;

I would also write the identifiers in lower-/mixedcase, now it awfully
looks like MODULA.

-- 
mail: adi@thur.de  	http://adi.thur.de	PGP: v2-key via keyserver

Werbung f�r einen Sch�tzenverein:
"Lernen Sie bei uns schie�en und treffen Sie gute Freunde!"

Re: Efficient Matrix?

[Alvery Grazebrook]

In message <slrnb0mvgq.j0i.adi@drcomp.erfurt.thur.de>, Adrian Knoth
<adi@drcomp.erfurt.thur.de> writes
>Jonas Gasser <jonas.gasser@dataflow.ch> wrote:
>
>> type MATRIX is array (POSITIVE range <>, POSITIVE range <>) of BOOLEAN;
>> type POINTER_MATRIX is access all MATRIX;
>> A : POINTER_MATRIX := new MATRIX(1..10000,1..5000);
>
>> ideas to optimize this.
>
>   pragma Pack (MATRIX);
>

There is another issue / option for efficiency - nothing particular to
Ada, just an alternative way to do a Matrix. This option works if you
have a very large array, and the array only has a fairly small number of
significant values in it. I would be guessing, and it depends on the
application, but if your array of booleans has most values False, and
only a few hundred or thousand True, then it would be more space
efficient to store a list of the elements which are actually set to
true.

As you are probably aware, your matrix will take up 5e7 bits, or just
under 10 Mbytes of storage, assuming the compiler is efficient in the
way it packs the data. This may not matter much if you are writing for a
workstation environment, but probably will matter for some types of
system.

To present this, you would probably want a structure something like
this:

generic
   First_Size, Second_Size : Positive;
package Sparse_Boolean_Array is

subtype First_Range is Positive range 1..First_Size;
subtype Second_Range is Positive range 1..Second_Size;

type List_Entry is
   record
      first : First_Range;
      second : Second_Range;
   end record;

-- you need to insert some structure to hold List_Entries in a
searchable
-- form in here. Perhaps a binary tree or hash-table.
-- The subprograms Value and Set will access the structure to handle
-- the data structure you choose.

function Value
      (pFirst : First_Range;
       pSecond : Second_Range)
return Boolean;

procedure Set
      (pFirst : First_Range;
       pSecond : Second_Range;
       pValue : Boolean);

end Sparse_Boolean_Array ;

-- 
Alvery Grazebrook

Re: Efficient Matrix?

[Adrian Knoth]

Alvery Grazebrook <nospam@grazebrook.demon.co.uk> wrote:

>>> type MATRIX is array (POSITIVE range <>, POSITIVE range <>) of BOOLEAN;
>>> type POINTER_MATRIX is access all MATRIX;
>>> A : POINTER_MATRIX := new MATRIX(1..10000,1..5000);
>>
>>> ideas to optimize this.
>>   pragma Pack (MATRIX);

> As you are probably aware, your matrix will take up 5e7 bits, or just
> under 10 Mbytes of storage, assuming the compiler is efficient in the
> way it packs the data. 

I'm not sure whether the compiler packs it at all. It is heap-allocated
memory (not stack) and it is not a bounded array (the type MATRIX).

That is why I cancelled my posting you're referring to.


-- 
mail: adi@thur.de  	http://adi.thur.de	PGP: v2-key via keyserver

Esistsehrschwierigindiesensiebzigzeichenhierkreativzuseinoderetwanicht

Re: Efficient Matrix?

[Robert A Duff]

Adrian Knoth <adi@drcomp.erfurt.thur.de> writes:

> Alvery Grazebrook <nospam@grazebrook.demon.co.uk> wrote:
> 
> >>> type MATRIX is array (POSITIVE range <>, POSITIVE range <>) of BOOLEAN;
> >>> type POINTER_MATRIX is access all MATRIX;
> >>> A : POINTER_MATRIX := new MATRIX(1..10000,1..5000);
> >>
> >>> ideas to optimize this.
> >>   pragma Pack (MATRIX);
> 
> > As you are probably aware, your matrix will take up 5e7 bits, or just
> > under 10 Mbytes of storage, assuming the compiler is efficient in the
> > way it packs the data. 
> 
> I'm not sure whether the compiler packs it at all. It is heap-allocated
> memory (not stack) and it is not a bounded array (the type MATRIX).
> 
> That is why I cancelled my posting you're referring to.

Compilers are required to pack tightly in this case (one bit per Boolean
component).  I.e., Matrix'Component_Size will be 1 if there's a pragma
Pack.  See RM-13.2(9).

It's got nothing to do with the fact that the thing is heap allocated,
nor the fact that the bounds are not known at compile time.
(If the compiler used a different representation for a heap allocated
array than for a stack allocated array, it would have to be continually
translating back and forth.  So compilers don't do that.)

- Bob

Re: Efficient Matrix?

[Nick Roberts]

[Jonas Gasser asked about how to efficiently model a large boolean matrix in
Ada.]

It may be worth pointing out that on a computer with typical virtual memory
management, if patterns of actual access to your large boolean array will
tend to be 'sparse' (i.e. your program will tend to concentrate on one or a
few small parts of the matrix at a time during computation), only a small
part of the matrix will be part of the 'working set' (the set of memory
pages which are actually being used at a certain 'moment', e.g. each second,
during the program's execution). In this case, the fact that the matrix
takes up many megabytes (or even gigabytes) of memory may recede in
importance compared to the fact that only a small part (perhaps a few 100
kilobytes) needs to be in RAM at any one time during most of the program's
execution.

Or to put it more simply, if you are running your program on a virtual
memory machine, try the big array declaration and see if it works!  If it
seems intolerably slow, try another more sophisticated strategy, such as a
hash table, and see if this increases speed (it may decrease speed, so be
wary).

One technique that may be worth investigating (again, on a virtual memory
machine) is that of using a small hash table which simply uses the full
array to resolve collisions.


type Matrix is array (Positive range <>, Positive range <>) of Boolean;

type Hash_Index is range 0..999; -- whatever range is appropriate
function Hash (i, j: Positive) return Hash_Index;

type Hashtable_Entry is
   record
      Value: Boolean := False; -- or True if most values will be true
      Collision: Boolean := False;
   end record;

type Matrix_by_Hash (Hash_Index) of Hashtable_Entry;

M1: Matrix(1..10000,1..5000) := (others => (others => False));
-- M1 may need to be dynamically allocated.
-- The initialisation may need to be different or omitted.

H1: Matrix_by_Hash;

function Get_M1 (i, j: in Positive) return Boolean is
   h: constant Hash_Index := Hash(i,j);
   E: constant Hashtable_Entry := H1(h);
begin
   if E.Collision then return M1(i,j); else return E.Value; end if;
end;

procedure Set_M1 (i, j: in Positive; b: in Boolean) is
   h: constant Hash_Index := Hash(i,j);
begin
   M1(i,j) := b;
   if H1(h).Value /= b then H1(h).Collision := True; end if;
end;


It is one of the basic premises of the hashing technique that the data
written into the full matrix will tend, in practice, to be sparse (i.e. that
it will contain mainly falses (or maybe that it will have mainly trues)).
The computation of the hashing index (the Hash function) always needs to be
fast, but particularly so in this kind of situation, I think. I'll leave the
actual choice of the Hash function and Hash_Index range to you.

Also, for the above specific technique, since Set_M1 always accesses the big
M1 array, it is supposed that the number of reads will greatly outnumber the
number of writes. You may well wish to apply pragma Inline to Hash, Get_M1
and Set_M1. You will almost certainly wish to apply pragma Pack to M1 (or
the (sub)type Matrix), and possibly also to H1 (or Matrix_by_Hash) and
Hashtable_Entry.

If this technique works, you ought to 'pot' the matrix types and functions
in a package; possibly a generic one which takes the full matrix array type,
the hash index type, and the hashing function as generic parameters.

Hope this is of some help (or interest).  Good luck!

--
Nick Roberts

Re: Efficient Matrix?

[Adrian Knoth]

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

> Compilers are required to pack tightly in this case (one bit per Boolean
> component).  I.e., Matrix'Component_Size will be 1 if there's a pragma
> Pack.  See RM-13.2(9).

Hmm?

with Ada.Text_IO; use Ada.Text_IO;

procedure bla is

   type MATRIX is array (Positive range <>, Positive range <>) of Boolean;
   type POINTER_MATRIX is access all MATRIX;

   pragma Pack (MATRIX);

   type my_matrix is array (Positive range <>, Positive range <>) of Boolean;

   A : POINTER_MATRIX := new MATRIX (1 .. 10000, 1 .. 5000);

begin
   Put_Line (Integer'Image (MATRIX'Component_Size));
   Put_Line (Integer'Image (my_matrix'Component_Size));
end bla;


adi@drcomp:/tmp$ ./bla
 8
 8
adi@drcomp:/tmp$
 
> It's got nothing to do with the fact that the thing is heap allocated,
> nor the fact that the bounds are not known at compile time.

For the variable A it is even known, but I was not able to determine
a valuable difference in memory-comsumption.


-- 
mail: adi@thur.de  	http://adi.thur.de	PGP: v2-key via keyserver

Praktisch denken, S�rge schenken

Re: Efficient Matrix?

[Bill Findlay]

On 28/12/02 13:00, in article slrnb0r842.2n7.adi@drcomp.erfurt.thur.de,
"Adrian Knoth" <adi@drcomp.erfurt.thur.de> wrote:

> Robert A Duff <bobduff@shell01.TheWorld.com> wrote:
> 
>> Compilers are required to pack tightly in this case (one bit per Boolean
>> component).  I.e., Matrix'Component_Size will be 1 if there's a pragma
>> Pack.  See RM-13.2(9).
> 
[snip]
> 
>> It's got nothing to do with the fact that the thing is heap allocated,
>> nor the fact that the bounds are not known at compile time.
> 
> For the variable A it is even known, but I was not able to determine
> a valuable difference in memory-comsumption.
> 

I get good results as follows, with GNAT 5.00w for MacOS X.
-----------------------------------------------------------
with Ada.Text_IO; use Ada.Text_IO;

procedure bla is

   type unconstrained_type is
        array (Positive range <>, Positive range <>) of Boolean;
   for unconstrained_type'Component_Size use 1;
   pragma Pack (unconstrained_type);

   subtype constrained_type is unconstrained_type (1 .. 10000, 1 .. 5000);
   type constrained_type_ptr is access constrained_type;

   A : constrained_type_ptr := new constrained_type;

begin
   Put_Line (Integer'Image (constrained_type'Component_Size));
   Put_Line (Integer'Image (unconstrained_type'Component_Size));
   Put_Line (Integer'Image (constrained_type'Size));
   Put_Line (Integer'Image (A.all'Size));
end bla;
----------------------------------------------------------------
% ./bla
 1
 8
 50000000
 50000000
----------------------------------------------------------------
-- 
Bill-Findlay chez blue-yonder.co.uk ("-" => "")

Re: Efficient Matrix?

[Adrian Knoth]

Bill Findlay <yaldnifw@blueyonder.co.uk> wrote:

>>> It's got nothing to do with the fact that the thing is heap allocated,
>>> nor the fact that the bounds are not known at compile time.
>> For the variable A it is even known, but I was not able to determine
>> a valuable difference in memory-comsumption.
> I get good results as follows, with GNAT 5.00w for MacOS X.

What you get is exactly what I meant:

The compiler optimizes if it is a constrained type and does nothing if
it is unconstrained as the original poster wanted it.

For sure it would be better to use a constrained subtype. Here your
program modified to the asked context:

with Ada.Text_IO; use Ada.Text_IO;

procedure bla is

   type unconstrained_type is
        array (Positive range <>, Positive range <>) of Boolean;
   for unconstrained_type'Component_Size use 1;
   pragma Pack (unconstrained_type);

   type unconstrained_type_ptr is access unconstrained_type;

   A : unconstrained_type_ptr := new unconstrained_type
                                      (1 .. 10000, 1 .. 5000);

begin
   Put_Line (Integer'Image (unconstrained_type'Component_Size));
   Put_Line (Integer'Image (A.all'Size));
end bla;

------
adi@drcomp:/tmp$ ./bla
 8
 400000000

(last value is 50000000*8)

-- 
mail: adi@thur.de  	http://adi.thur.de	PGP: v2-key via keyserver

Der merkt halt, dass das seine muttermilch ist, die gerade �bertragen wird.
(user w�hrend des dd's der root-partition auf den fileserver)

Re: Efficient Matrix?

[Adrian Knoth]

Adrian Knoth <adi@drcomp.erfurt.thur.de> wrote:

Hi!

>    for unconstrained_type'Component_Size use 1;

>    Put_Line (Integer'Image (unconstrained_type'Component_Size));

Well, the error is not the representation-clause, but the output
of the read-access to Component_Size.

This behaviour is filed as PR9087.

-- 
mail: adi@thur.de  	http://adi.thur.de	PGP: v2-key via keyserver

Der Tod der nimmt dich schneller mit, rauchst du manches Mal auch Shit

Re: Efficient Matrix?

[Robert A Duff]

Bill Findlay <yaldnifw@blueyonder.co.uk> writes:

> I get good results as follows, with GNAT 5.00w for MacOS X.
        ^^^^
You misspelled "bad".  ;-)

> -----------------------------------------------------------
> with Ada.Text_IO; use Ada.Text_IO;
> 
> procedure bla is
> 
>    type unconstrained_type is
>         array (Positive range <>, Positive range <>) of Boolean;
>    for unconstrained_type'Component_Size use 1;
>    pragma Pack (unconstrained_type);
> 
>    subtype constrained_type is unconstrained_type (1 .. 10000, 1 .. 5000);
>    type constrained_type_ptr is access constrained_type;
> 
>    A : constrained_type_ptr := new constrained_type;
> 
> begin
>    Put_Line (Integer'Image (constrained_type'Component_Size));
>    Put_Line (Integer'Image (unconstrained_type'Component_Size));
>    Put_Line (Integer'Image (constrained_type'Size));
>    Put_Line (Integer'Image (A.all'Size));
> end bla;
> ----------------------------------------------------------------
> % ./bla
>  1
>  8
>  50000000
>  50000000

That makes no sense.  How can the 'Component_Size differ between
subtypes of the same type?  And how can the compiler accept the "for
unconstrained_type'Component_Size use 1;", and then return
unconstrained_type'Component_Size use = 8?
I suspect that if you add:

    type Unconstrained_Type_Ptr is access Unconstrained_Type;
    B: Unconstrained_Type_Ptr := new Unconstrained_Type(1..10_000, 1..5000);

then B.all'Size will be 50_000_000, implying that
Unconstrained_Type'Component_Size really is 1, but the attribute is
returning the wrong answer.  If that's not true, then I'm very confused
about what this compiler is up to.

Note that the above is equivalent to:

    B: Unconstrained_Type_Ptr := new Constrained_Type;

- Bob

Re: Efficient Matrix?

[Bill Findlay]

On 28/12/02 16:07, in article wccisxeqg8m.fsf@shell01.TheWorld.com, "Robert
A Duff" <bobduff@shell01.TheWorld.com> wrote:

> Bill Findlay <yaldnifw@blueyonder.co.uk> writes:
> 
>> I get good results as follows, with GNAT 5.00w for MacOS X.
>       ^^^^
> You misspelled "bad".  ;-)
> 

I meant it was good that the OP could get the array well packed.
It is bad in every other sense. 8-)

But I read 13.2 as normative, not binding: 13.2(6) says "should try" and
13.2(7) says "recommended". 13.3 is similarly worded w.r.t. Component_Size.

> 
> That makes no sense.  How can the 'Component_Size differ between
> subtypes of the same type?  And how can the compiler accept the "for
> unconstrained_type'Component_Size use 1;", and then return
> unconstrained_type'Component_Size use = 8?

I agree that this has to be a bug.

> I suspect that if you add:
> 
>   type Unconstrained_Type_Ptr is access Unconstrained_Type;
>   B: Unconstrained_Type_Ptr := new Unconstrained_Type(1..10_000, 1..5000);
> 
> then B.all'Size will be 50_000_000, implying that

Alas not (I reduced the array bounds by a factor of 10 to get a reasonable
execution time):
----------------------------------------------------------------
procedure bla is

   type unconstrained_type is
        array (Positive range <>, Positive range <>) of Boolean;
   for unconstrained_type'Component_Size use 1;
   pragma Pack (unconstrained_type);
   type unconstrained_type_ptr is access unconstrained_type;

   subtype constrained_type is unconstrained_type (1 .. 1000, 1 .. 500);
   type constrained_type_ptr is access constrained_type;

   C : constrained_type_ptr   := new constrained_type;
   U : unconstrained_type_ptr := new unconstrained_type
                                     (1 .. 1000, 1 .. 500);

begin
   Put_Line (Integer'Image (constrained_type'Component_Size));
   Put_Line (Integer'Image (unconstrained_type'Component_Size));
   Put_Line (Integer'Image (constrained_type'Size));
   Put_Line 
("Cannot evaluate unconstrained_type'Size - would raise Constraint_Error");
   Put_Line (Integer'Image (C.all'Size));
   Put_Line (Integer'Image (U.all'Size));
   for i in C'range(1) loop
       for j in C'range(2) loop
            C(i,j) := true;
            U(i,j) := false;
        end loop;
    end loop;
   U(500, 250) := true;
   C.all := U.all;
   Put_Line("C(500, 250..251) = " &
       Boolean'image(C(500, 250)) &","& Boolean'image(C(500, 251)));
end bla;

----------------------------------------------------------------
%  ./bla
 1
 8
 500000
Cannot evaluate unconstrained_type'Size - would raise Constraint_Error
 500000
 4000000
C(500, 250..251) = TRUE,FALSE
----------------------------------------------------------------

Definitely something fishy here.
If the components of C and U had different sizes then a lot of run-time
packing would be needed to implement

   C.all := U.all;

(and indeed the object code is enormous, but I don't know enough to say if
that's what it's doing - it certainly shouldn't be).

How can we tell whether the size attributes are lying?

-- 
Bill-Findlay chez blue-yonder.co.uk ("-" => "")

Re: Efficient Matrix?

[Bill Findlay]

On 28/12/02 17:25, in article BA338F12.1700%yaldnifw@blueyonder.co.uk, "Bill
Findlay" <yaldnifw@blueyonder.co.uk> wrote:

> procedure bla is
> 
>  type unconstrained_type is
>       array (Positive range <>, Positive range <>) of Boolean;
>  for unconstrained_type'Component_Size use 1;
>  pragma Pack (unconstrained_type);
>  type unconstrained_type_ptr is access unconstrained_type;
> 
>  subtype constrained_type is unconstrained_type (1 .. 1000, 1 .. 500);
>  type constrained_type_ptr is access constrained_type;
> 
>  C : constrained_type_ptr   := new constrained_type;
>  U : unconstrained_type_ptr := new unconstrained_type
>                                    (1 .. 1000, 1 .. 500);
> 
...

Well I had a closer look and found this:
        li r6,0
        ori r3,r6,62500
                  ^^^^^ = 1000*500 / 8
        bl L___gnat_malloc$stub
        stw r3,1556(r1)

        li r7,0
        ori r3,r7,62516
                  ^^^^^ = 1000*500 / 8 + 16 (for dope vector?)
        bl L___gnat_malloc$stub
...
So it looks as though the component size and packing are honoured, but the
attributes are lying about it

-- 
Bill-Findlay chez blue-yonder.co.uk ("-" => "")

Re: Efficient Matrix?

[Robert A Duff]

Bill Findlay <yaldnifw@blueyonder.co.uk> writes:

> I meant it was good that the OP could get the array well packed.
> It is bad in every other sense. 8-)

;-)

> But I read 13.2 as normative, not binding: 13.2(6) says "should try" and
                     ^^^^^^^^^
> 13.2(7) says "recommended". 13.3 is similarly worded w.r.t. Component_Size.

I think you mean "nonnormative".  Normative means binding.  Probably a
typo.

Anyway, as I said in another post, 13.2(7) *is* binding if the compiler
claims to support the SP annex.

13.2(6) is Implementation Advice, and therefore nonbinding.

> Definitely something fishy here.
> If the components of C and U had different sizes then a lot of run-time
> packing would be needed to implement
> 
>    C.all := U.all;
> 
> (and indeed the object code is enormous, but I don't know enough to say if
> that's what it's doing - it certainly shouldn't be).

Indeed.  In other words, the compiler writer would have to go to more
trouble to fail to pack the unconstrained one, than to do it right
(given that the constrained one is clearly packed correctly).

> How can we tell whether the size attributes are lying?

Look at the machine code.

Or, maybe print out the value of U.all(1,1)'Address and
U.all(100,100)'Address, or something like that.

- Bob

Re: Efficient Matrix?

[Robert A Duff]

Adrian Knoth <adi@drcomp.erfurt.thur.de> writes:

> Robert A Duff <bobduff@shell01.TheWorld.com> wrote:
> 
> > Compilers are required to pack tightly in this case (one bit per Boolean
> > component).  I.e., Matrix'Component_Size will be 1 if there's a pragma
> > Pack.  See RM-13.2(9).
> 
> Hmm?

Looks like a compiler bug to me.  It seems to me that RM-13.2(9) implies
packed arrays of Boolean have 'Component_Size = 1.  Don't you think so?

> with Ada.Text_IO; use Ada.Text_IO;
> 
> procedure bla is
> 
>    type MATRIX is array (Positive range <>, Positive range <>) of Boolean;
>    type POINTER_MATRIX is access all MATRIX;
> 
>    pragma Pack (MATRIX);
> 
>    type my_matrix is array (Positive range <>, Positive range <>) of Boolean;
> 
>    A : POINTER_MATRIX := new MATRIX (1 .. 10000, 1 .. 5000);
> 
> begin
>    Put_Line (Integer'Image (MATRIX'Component_Size));
>    Put_Line (Integer'Image (my_matrix'Component_Size));
> end bla;
> 
> 
> adi@drcomp:/tmp$ ./bla
>  8
>  8
> adi@drcomp:/tmp$
>  
> > It's got nothing to do with the fact that the thing is heap allocated,
> > nor the fact that the bounds are not known at compile time.
> 
> For the variable A it is even known, but I was not able to determine
> a valuable difference in memory-comsumption.

So what size is A.all?

- Bob

Re: Efficient Matrix?

[Adrian Knoth]

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

>> > Compilers are required to pack tightly in this case (one bit per Boolean
>> > component).  I.e., Matrix'Component_Size will be 1 if there's a pragma
>> > Pack.  See RM-13.2(9).
>> Hmm?
> Looks like a compiler bug to me.  

Not really.

    9  For a packed array type, if the component subtype's Size is less
       than or equal to the word size, and Component_Size is not
       specified for the type, Component_Size should be less than or
       equal to the Size of the component subtype, rounded up to the
       nearest factor of the word size.

"should be less than or equal", so gnat is RM-conformable here, but
the important question is why the representation-clause is not
respected. I guess, the answer is in RM-13.1(21):

   22  An implementation need not support representation items
       containing nonstatic expressions, except that an implementation
       should support a representation item for a given entity if each
       nonstatic expression in the representation item is a name that
       statically denotes a constant declared before the entity.

   23  An implementation need not support a specification for the Size
       for a given composite subtype, nor the size or storage place for
       an object (including a component) of a given composite subtype,
       unless the constraints on the subtype and its composite
       subcomponents (if any) are all static constraints.

And it looks like that "Positive range <>" is not static. In fact,
it is unconstrained.

> It seems to me that RM-13.2(9) implies packed arrays of Boolean have 
> 'Component_Size = 1.  Don't you think so?

No. For static arrays this would be right because 1 bit f�r Boolean is
smallest packing. This will happen if you say something like

  type static_array is (1 .. 64) of Boolean;
  pragma Pack (static_array);

which should return static_array'Size=64, implying Component_Size=1.

But the other paragraphs in Section 13 permit the compiler to neglect
all nonstatic expressions.

>> adi@drcomp:/tmp$ ./bla
>>  8
>>  8
>> adi@drcomp:/tmp$
> So what size is A.all?

10000*5000*8 bits.


-- 
mail: adi@thur.de  	http://adi.thur.de	PGP: v2-key via keyserver

Ausgerottet ist die Pest, das macht doch nichts, es gibt doch West.

Re: Efficient Matrix?

[James S. Rogers]

Testing the following program on the free Aonix Object Ada (7.2.2)
I get the expected results:

with Ada.Text_Io;
use Ada.Text_Io;

procedure Bla is

   type Unconstrained_Type is array (Positive range <>, Positive range <>)
of Boolean;
   pragma Pack (Unconstrained_Type);

   subtype Constrained_Type is Unconstrained_Type (1 .. 10000, 1 .. 5000);
   type Constrained_Type_Ptr is access Constrained_Type;
   function Component_Bits (Item : constrained_Type) return Integer is
   begin
      return Item'Component_Size;
   end Component_Bits;


   A : Constrained_Type_Ptr := new Constrained_Type;

begin
   Put_Line (Integer'Image (Constrained_Type'Component_Size));
   Put_Line (Integer'Image (Unconstrained_Type'Component_Size));
   Put_Line(Integer'Image(A(1,1)'Size));
   Put_Line(Integer'Image(Component_Bits(A.all)));
   Put_Line (Integer'Image (Constrained_Type'Size));
   Put_Line (Integer'Image (A.All'Size));
end Bla;

Results:

1
1
1
1
50000
50000

Jim Rogers

Re: Efficient Matrix?

[Robert A Duff]

Adrian Knoth <adi@drcomp.erfurt.thur.de> writes:

> Robert A Duff <bobduff@shell01.TheWorld.com> wrote:
> 
> >> > Compilers are required to pack tightly in this case (one bit per Boolean
> >> > component).  I.e., Matrix'Component_Size will be 1 if there's a pragma
> >> > Pack.  See RM-13.2(9).
> >> Hmm?
> > Looks like a compiler bug to me.  
> 
> Not really.
> 
>     9  For a packed array type, if the component subtype's Size is less
>        than or equal to the word size, and Component_Size is not
>        specified for the type, Component_Size should be less than or
>        equal to the Size of the component subtype, rounded up to the
>        nearest factor of the word size.
> 
> "should be less than or equal", so gnat is RM-conformable here, ...

It is true that 13.2(9) is "Implementation Advice", and therefore need
not be obeyed.  However, the Systems Programming Annex, in C.2,
turns it into a binding requirement.  13.1(20) also mentions this.

So a standards conforming compiler can get away without supporting any
representation items at all.  But a compiler that claims to support the
SP annex must obey 13.2(9).  I believe all compilers claim to support
the SP annex.  GNAT certainly does -- Robert Dewar has been heard around
here bragging that GNAT is the only compiler that supports *all* of the
optional annexes.  ;-)

So, I claim that a packed array of Boolean *must* have 'Component_Size
= 1, presuming SP support.

>.... but
> the important question is why the representation-clause is not
> respected. I guess, the answer is in RM-13.1(21):
> 
>    22  An implementation need not support representation items
>        containing nonstatic expressions, except that an implementation
>        should support a representation item for a given entity if each
>        nonstatic expression in the representation item is a name that
>        statically denotes a constant declared before the entity.

The above does not apply to pragma Pack, because the Pack contains no
expressions (certainly no non-static ones).  Similarly, it does not
apply to "for T'Component_Size use 1;", since the expression "1" is
static.

>    23  An implementation need not support a specification for the Size
>        for a given composite subtype, nor the size or storage place for
>        an object (including a component) of a given composite subtype,
>        unless the constraints on the subtype and its composite
>        subcomponents (if any) are all static constraints.

For Pack, again this doesn't apply: Pack does not "specify Size...",
even though it does have an affect on the size. ;-)

As for 'Component_Size, the subtype in question is Boolean, which is
neither composite nor unconstrained.  Again, not applicable.

What it's saying is that the compiler need not support specifying 'Size
on the whole array.

> And it looks like that "Positive range <>" is not static. In fact,
> it is unconstrained.
> 
> > It seems to me that RM-13.2(9) implies packed arrays of Boolean have 
> > 'Component_Size = 1.  Don't you think so?

How about now?  ;-)

> No. For static arrays this would be right because 1 bit f�r Boolean is
> smallest packing. This will happen if you say something like
> 
>   type static_array is (1 .. 64) of Boolean;
>   pragma Pack (static_array);
> 
> which should return static_array'Size=64, implying Component_Size=1.
> 
> But the other paragraphs in Section 13 permit the compiler to neglect
> all nonstatic expressions.

No, I don't think it says exactly that.  Nor should it -- specifying the
Component_Size should reasonably require that the size of the component
subtype be static, but it's got nothing to do with the size of the
array, nor whether it's constrained; there's no implementation burden in
that case.

- Bob

Re: Efficient Matrix?

[Adrian Knoth]

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

> turns it into a binding requirement.  13.1(20) also mentions this.

ACK.
 
> So a standards conforming compiler can get away without supporting any
> representation items at all.  But a compiler that claims to support the
> SP annex must obey 13.2(9).  

    9  For a packed array type, if the component subtype's Size is less
       than or equal to the word size, and Component_Size is not
       specified for the type, Component_Size should be less than or
       equal to the Size of the component subtype, rounded up to the
       nearest factor of the word size.

How does this _forces_ a compiler to set a packed boolean array's
Component_Size to 1? As I understand the paragraph it determines
the compiler's behaviour if the Component_Size of a packed array is
_not_ defined by the user.

> I believe all compilers claim to support the SP annex. GNAT certainly does

Sure.

> So, I claim that a packed array of Boolean *must* have 'Component_Size
>= 1, presuming SP support.

I've not resurveyed all aspects of the RM, especially the dependencies,
but I would, for now, acknowledge.
 
> How about now?  ;-)

I guess I'll send a bug-report. Unfortunately the gcc-bug-database is
write-only at the moment, so to say, there seems to be nobody carrying
much about ProblemReports. 


-- 
mail: adi@thur.de  	http://adi.thur.de	PGP: v2-key via keyserver

Ein Mann ein Wort, eine Frau ein W�rterbuch.

Re: Efficient Matrix?

[Robert A Duff]

Adrian Knoth <adi@drcomp.erfurt.thur.de> writes:

> Robert A Duff <bobduff@shell01.TheWorld.com> wrote:
> 
> > turns it into a binding requirement.  13.1(20) also mentions this.
> 
> ACK.
>
> > So a standards conforming compiler can get away without supporting any
> > representation items at all.  But a compiler that claims to support the
> > SP annex must obey 13.2(9).  
> 
>     9  For a packed array type, if the component subtype's Size is less
>        than or equal to the word size, and Component_Size is not
>        specified for the type, Component_Size should be less than or
>        equal to the Size of the component subtype, rounded up to the
>        nearest factor of the word size.
> 
> How does this _forces_ a compiler to set a packed boolean array's
> Component_Size to 1? As I understand the paragraph it determines
> the compiler's behaviour if the Component_Size of a packed array is
> _not_ defined by the user.

I guess I was talking about that case.  E.g:

    type T is array (Positive range <>) of Boolean;
    pragma Pack(T);

The component subtype is Boolean.

Boolean'Size = 1, by 13.3(49).  Also 13.3(55), combined with the SP
annex thing.

This size (1 bit) is <= word size on every machine.  And it's a factor
of the word size on every machine.  So the compiler must choose
T'Component_Size <= 1.  And it can't very well choose < 1, so it must
choose = 1.

If you specify T'Component_Size, then the above paragraph is saying that
overrides the pragma.  So if you say:

    type T is array (Positive range <>) of Boolean;
    pragma Pack(T);
    for T'Component_Size use 2;

then T'Component_Size = 2.  This is required to be supported by
13.3(73), combined with the SP annex thing, assuming the word size
is an even number of bits (which is quite common ;-)).

> I guess I'll send a bug-report. Unfortunately the gcc-bug-database is
> write-only at the moment, so to say, there seems to be nobody carrying
> much about ProblemReports. 

Unless you're a paying customer, they have no obligation to fix things
soon.  But they do seem to fix things "eventually".

- Bob

Re: Efficient Matrix?

[Gautier]

Jonas Gasser:

> A : POINTER_MATRIX := new MATRIX(1..10000,1..5000);
> 
> I initialize a variable A from the type POINTER_MATRIX.
> Now I 'm interested to know if this is a common way of creating matrixes and
> if there is a faster and efficient way to handle this or if you have some
> ideas to optimize this.

Briefly, there is not _one_ answer to this (read also the other replies...),
but depending on your data density, computer RAM and CPU cache, the "best"
can be
- your MATRIX
- your MATRIX with pragma pack (smaller but machine code access to data
  possibly more complicated)
- a band matrix
- a sparse matrix
- ... ?

Code for both are in mathpaqs.zip below - just change
the Digits <> into Boolean.
________________________________________________________
Gautier  --  http://www.mysunrise.ch/users/gdm/gsoft.htm

NB: For a direct answer, e-mail address on the Web site!