* Re: Efficient Matrix? [not found] <3e0b2a66_4@news.bluewin.ch> @ 2002-12-26 22:09 ` Adrian Knoth 2002-12-27 0:23 ` Alvery Grazebrook 2002-12-27 12:25 ` Gautier 1 sibling, 1 reply; 20+ messages in thread From: Adrian Knoth @ 2002-12-26 22:09 UTC (permalink / raw) 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!" ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: Efficient Matrix? 2002-12-26 22:09 ` Efficient Matrix? Adrian Knoth @ 2002-12-27 0:23 ` Alvery Grazebrook 2002-12-27 9:53 ` Adrian Knoth 0 siblings, 1 reply; 20+ messages in thread From: Alvery Grazebrook @ 2002-12-27 0:23 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: Efficient Matrix? 2002-12-27 0:23 ` Alvery Grazebrook @ 2002-12-27 9:53 ` Adrian Knoth 2002-12-27 16:58 ` Robert A Duff 0 siblings, 1 reply; 20+ messages in thread From: Adrian Knoth @ 2002-12-27 9:53 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: Efficient Matrix? 2002-12-27 9:53 ` Adrian Knoth @ 2002-12-27 16:58 ` Robert A Duff 2002-12-28 1:44 ` Nick Roberts 2002-12-28 13:00 ` Adrian Knoth 0 siblings, 2 replies; 20+ messages in thread From: Robert A Duff @ 2002-12-27 16:58 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: Efficient Matrix? 2002-12-27 16:58 ` Robert A Duff @ 2002-12-28 1:44 ` Nick Roberts 2002-12-28 13:00 ` Adrian Knoth 1 sibling, 0 replies; 20+ messages in thread From: Nick Roberts @ 2002-12-28 1:44 UTC (permalink / raw) [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 ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: Efficient Matrix? 2002-12-27 16:58 ` Robert A Duff 2002-12-28 1:44 ` Nick Roberts @ 2002-12-28 13:00 ` Adrian Knoth 2002-12-28 15:21 ` Bill Findlay 2002-12-28 15:58 ` Robert A Duff 1 sibling, 2 replies; 20+ messages in thread From: Adrian Knoth @ 2002-12-28 13:00 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: Efficient Matrix? 2002-12-28 13:00 ` Adrian Knoth @ 2002-12-28 15:21 ` Bill Findlay 2002-12-28 15:48 ` Adrian Knoth 2002-12-28 16:07 ` Robert A Duff 2002-12-28 15:58 ` Robert A Duff 1 sibling, 2 replies; 20+ messages in thread From: Bill Findlay @ 2002-12-28 15:21 UTC (permalink / raw) 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 ("-" => "") ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: Efficient Matrix? 2002-12-28 15:21 ` Bill Findlay @ 2002-12-28 15:48 ` Adrian Knoth 2002-12-28 23:26 ` Adrian Knoth 2002-12-28 16:07 ` Robert A Duff 1 sibling, 1 reply; 20+ messages in thread From: Adrian Knoth @ 2002-12-28 15:48 UTC (permalink / raw) 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) ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: Efficient Matrix? 2002-12-28 15:48 ` Adrian Knoth @ 2002-12-28 23:26 ` Adrian Knoth 0 siblings, 0 replies; 20+ messages in thread From: Adrian Knoth @ 2002-12-28 23:26 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: Efficient Matrix? 2002-12-28 15:21 ` Bill Findlay 2002-12-28 15:48 ` Adrian Knoth @ 2002-12-28 16:07 ` Robert A Duff 2002-12-28 17:25 ` Bill Findlay 1 sibling, 1 reply; 20+ messages in thread From: Robert A Duff @ 2002-12-28 16:07 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: Efficient Matrix? 2002-12-28 16:07 ` Robert A Duff @ 2002-12-28 17:25 ` Bill Findlay 2002-12-28 17:35 ` Bill Findlay 2002-12-28 20:51 ` Robert A Duff 0 siblings, 2 replies; 20+ messages in thread From: Bill Findlay @ 2002-12-28 17:25 UTC (permalink / raw) 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 ("-" => "") ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: Efficient Matrix? 2002-12-28 17:25 ` Bill Findlay @ 2002-12-28 17:35 ` Bill Findlay 2002-12-28 20:51 ` Robert A Duff 1 sibling, 0 replies; 20+ messages in thread From: Bill Findlay @ 2002-12-28 17:35 UTC (permalink / raw) 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 ("-" => "") ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: Efficient Matrix? 2002-12-28 17:25 ` Bill Findlay 2002-12-28 17:35 ` Bill Findlay @ 2002-12-28 20:51 ` Robert A Duff 1 sibling, 0 replies; 20+ messages in thread From: Robert A Duff @ 2002-12-28 20:51 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: Efficient Matrix? 2002-12-28 13:00 ` Adrian Knoth 2002-12-28 15:21 ` Bill Findlay @ 2002-12-28 15:58 ` Robert A Duff 2002-12-28 17:19 ` Adrian Knoth 1 sibling, 1 reply; 20+ messages in thread From: Robert A Duff @ 2002-12-28 15:58 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: Efficient Matrix? 2002-12-28 15:58 ` Robert A Duff @ 2002-12-28 17:19 ` Adrian Knoth 2002-12-28 19:16 ` James S. Rogers 2002-12-28 20:45 ` Robert A Duff 0 siblings, 2 replies; 20+ messages in thread From: Adrian Knoth @ 2002-12-28 17:19 UTC (permalink / raw) 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. ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: Efficient Matrix? 2002-12-28 17:19 ` Adrian Knoth @ 2002-12-28 19:16 ` James S. Rogers 2002-12-28 20:45 ` Robert A Duff 1 sibling, 0 replies; 20+ messages in thread From: James S. Rogers @ 2002-12-28 19:16 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: Efficient Matrix? 2002-12-28 17:19 ` Adrian Knoth 2002-12-28 19:16 ` James S. Rogers @ 2002-12-28 20:45 ` Robert A Duff 2002-12-28 22:07 ` Adrian Knoth 1 sibling, 1 reply; 20+ messages in thread From: Robert A Duff @ 2002-12-28 20:45 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: Efficient Matrix? 2002-12-28 20:45 ` Robert A Duff @ 2002-12-28 22:07 ` Adrian Knoth 2002-12-28 23:42 ` Robert A Duff 0 siblings, 1 reply; 20+ messages in thread From: Adrian Knoth @ 2002-12-28 22:07 UTC (permalink / raw) 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. ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: Efficient Matrix? 2002-12-28 22:07 ` Adrian Knoth @ 2002-12-28 23:42 ` Robert A Duff 0 siblings, 0 replies; 20+ messages in thread From: Robert A Duff @ 2002-12-28 23:42 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: Efficient Matrix? [not found] <3e0b2a66_4@news.bluewin.ch> 2002-12-26 22:09 ` Efficient Matrix? Adrian Knoth @ 2002-12-27 12:25 ` Gautier 1 sibling, 0 replies; 20+ messages in thread From: Gautier @ 2002-12-27 12:25 UTC (permalink / raw) 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! ^ permalink raw reply [flat|nested] 20+ messages in thread
end of thread, other threads:[~2002-12-28 23:42 UTC | newest] Thread overview: 20+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- [not found] <3e0b2a66_4@news.bluewin.ch> 2002-12-26 22:09 ` Efficient Matrix? Adrian Knoth 2002-12-27 0:23 ` Alvery Grazebrook 2002-12-27 9:53 ` Adrian Knoth 2002-12-27 16:58 ` Robert A Duff 2002-12-28 1:44 ` Nick Roberts 2002-12-28 13:00 ` Adrian Knoth 2002-12-28 15:21 ` Bill Findlay 2002-12-28 15:48 ` Adrian Knoth 2002-12-28 23:26 ` Adrian Knoth 2002-12-28 16:07 ` Robert A Duff 2002-12-28 17:25 ` Bill Findlay 2002-12-28 17:35 ` Bill Findlay 2002-12-28 20:51 ` Robert A Duff 2002-12-28 15:58 ` Robert A Duff 2002-12-28 17:19 ` Adrian Knoth 2002-12-28 19:16 ` James S. Rogers 2002-12-28 20:45 ` Robert A Duff 2002-12-28 22:07 ` Adrian Knoth 2002-12-28 23:42 ` Robert A Duff 2002-12-27 12:25 ` Gautier
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox