🚀 go-pugleaf

enseeg14@grenet.fr wrote:
|> (I primarily posted this to comp.lang.c++, but the conclusion of it
|>  make it fit to this ng -- unless I'm too ignorant about compiler
|>  optimization....)

|> A question arose during a flamewar on comp.lang.fortran, about compiler
|> optimization.

|> C has always been the language where _THE PROGRAMMER_ could make his
|> own optimization, but this style of programming is getting deprecated
|> according to most C++ who basically say "rely on the compiler, optimize
|> only as a last minute operation". But here I have an example of what
|> would be very unefficient in C/C++ compared to F90:

|> > for (i = 0 ; i < n ; i++) {
|> >    for (j = 0 ; j < n ; j++) {
|> >       a[i][j] = b[i][j] * c[i] ;
|> >    }
|> > }

|> > do j = 1,m
|> >   do i = 1, n
|> >     a (i,j) = b(i,j) * c(i)
|> >   enddo
|> > enddo 

|> The Fortran compiler can easy unroll the loop and take advantage of scalar
|> caches, and easily use vectorial registers, whereas the C compiler
|> can't even move the evaluation of c[i] out of the inner loop because
|> &c[i] could be == to &a[x][y] ............ That's the problem with
|> weak typin... I'm wondering if any of the "const" tweak would change
|> anything...

Const won't help, and the problem isn't typing, but potential aliasing.
Fortran basically says that the results are undefined if aliasing is
present, C/C++ doesn't.  (In this regard, one could very easily argue
that C/C++ is safer.  In fact *in* *this* *regard*, I think it is, in
that you get defined results even if the arrays overlap.)

If the compiler can determine that no aliasing is present, they can
optimize.  Typically, this would require intermodule flow analysis,
something that is not frequently done in either C/C++ or Fortran
(although I've heard rumors of a C++ compiler which does it).

|> Despite I'm really disgusted by Fortran, I must concede this and
|> since only few compilers do really perform all the optimizations you
|> see in the books, I don't know they could get sthng good out of this...

|> So, if we're obliged to barf (see note) in this case, could there be any kin
d
|> of C++ extension -- another one! -- to imporve this? 

There is a proposed extention to C which would do it, a sort of son of
noalias.  I don't know any of the details, but I'm sure that a question
in comp.std.c would reach people who did, or who could point you in the
right direction.

I don't know what the current stand is with regards to the proposed C
extensions, and their incorporation into C++.  The C standard is part of
C++ `by reference', but in fact, I think that this is only where there
is an explicit reference (e.g.: some of the libraries).  In addition, I
think that the version of the C standard included by reference is part
of the standard.
-- 
James Kanze           (+33) 88 14 49 00          email: kanze@gabi-soft.fr
GABI Software, Sarl., 8 rue des Francs Bourgeois, 67000 Strasbourg, France
Conseils en informatique industrielle--
                             --Beratung in industrieller Datenverarbeitung
---
[ comp.std.c++ is moderated.  Submission address: std-c++@ncar.ucar.edu.
  Contact address: std-c++-request@ncar.ucar.edu.  The moderation policy
  is summarized in http://dogbert.lbl.gov/~matt/std-c++/policy.html. ]

kanze@gabi-soft.fr (J. Kanze) writes:
	...
>Fortran basically says that the results are undefined if aliasing is
>present, C/C++ doesn't.  (In this regard, one could very easily argue
>that C/C++ is safer.  In fact *in* *this* *regard*, I think it is, in
>that you get defined results even if the arrays overlap.)

Agreed, from practical experience; this _was_ an occasional cause of
very obscure bugs when we used to code in Fortran, as even very
experienced Fortran practitioners were all but clear on the no-alias
rule of that language... I remember people used to disable optimization
(thus often hiding the alias-related bug) and thought they had just hit
"one more optimizer bug"!-).


>I don't know what the current stand is with regards to the proposed C
>extensions, and their incorporation into C++.  The C standard is part of
>C++ `by reference', but in fact, I think that this is only where there

By _const_ reference, surely?-)


Alex
--
DISCLAIMER: these are TOTALLY personal opinions and viewpoints, NOT connected
in any way with my employer, nor any other organization or individual!
Email: martelli@cadlab.it                            Phone: +39 (51) 597313
CAD.LAB s.p.a., v. Ronzani 7/29, Casalecchio, Italia   Fax: +39 (51) 597120

[ comp.std.c++ is moderated.  Submission address: std-c++@ncar.ucar.edu.
  Contact address: std-c++-request@ncar.ucar.edu.  The moderation policy
  is summarized in http://dogbert.lbl.gov/~matt/std-c++/policy.html. ]

In article <45o2n2$o48@gabi.gabi-soft.fr>, kanze@gabi-soft.fr (J. Kanze) writes:
> enseeg14@grenet.fr wrote:
> 
> |> > for (i = 0 ; i < n ; i++) {
> |> >    for (j = 0 ; j < n ; j++) {
> |> >       a[i][j] = b[i][j] * c[i] ;
> |> >    }
> |> > }
> 
> |> > do j = 1,m
> |> >   do i = 1, n
> |> >     a (i,j) = b(i,j) * c(i)
> |> >   enddo
> |> > enddo 
> 
> Const won't help, and the problem isn't typing, but potential aliasing.
> Fortran basically says that the results are undefined if aliasing is
> present, C/C++ doesn't.

A minor point: Fortran doesn't say the results are *always* undefined if
aliasing is present.  The only thing that Fortran says that C/C++ do not is
that, if a, b, and c are all arguments to the function or subroutine, the
results are undefined if they refer to the same object.

You could easily write a Fortran program containing the above code fragment
wherein the compiler would not be allowed to vectorize the loop because of
aliasing.  That's one reason why vectorizing Fortran compilers are not
cheap. :-)

I'll also note that, despite the fact that the Fortran standard says the
results are undefined if two arguments overlap, there is a ton of extant
code that breaks that rule.  For that reason, some commercial Fortran
compilers have some way of telling the compiler to avoid any optimization
based on that rule.

> If the compiler can determine that no aliasing is present, they can
> optimize.  Typically, this would require intermodule flow analysis,
> something that is not frequently done in either C/C++ or Fortran
> (although I've heard rumors of a C++ compiler which does it).

Well, if a, b, and c were all local arrays, a C/C++ compiler could easily
determine that no aliasing is present.  However, typically they are
arguments to a function/subroutine.

|> The Fortran compiler can easy unroll the loop and take advantage of scalar
|> caches, and easily use vectorial registers, whereas the C compiler
|> can't even move the evaluation of c[i] out of the inner loop because
|> &c[i] could be == to &a[x][y] ............ That's the problem with
|> weak typin... I'm wondering if any of the "const" tweak would change
|> anything...

A C/C++ compiler could still unroll the loop, which would at least reduce
the loop overhead.  However, reordering operations would be verboten unless
the compiler could prove no aliasing.

> There is a proposed extention to C which would do it, a sort of son of
> noalias.  I don't know any of the details, but I'm sure that a question
> in comp.std.c would reach people who did, or who could point you in the
> right direction.

I continue to think such extensions are a bad idea.  They basically force
the compiler to trust the programmer, and historically that is not a
reliable thing to do.  The original programmer may have been careful to
avoid aliasing, but what about the 50 other programmers who came later and
made modifications to the program?  Worse still, you may have a bug lurking
there for decades until you happen to compile with a compiler that takes
advantage of the noalias declaration *and* does it in such a way that the
illegal aliasing changes the behavior of the program.  Such bugs are
extremely difficult to track down.

For example, suppose that in the above matrix multiplication, a[i][j] is
the same as b[i][j+2].  This violates the programmer's assertion that a and
b are not aliased, but you won't be able to tell it unless the compiler
generates code that fetches two elements of b ahead of an assignment to an
element of a.  One fetch ahead would be okay.

IMHO, the best answer is improved interprocedural analysis by compilers,
because that is the safest and also the most optimal -- it detects aliasing
when it is present, and detects lack of aliasing when it is absent (even if
the programmer didn't know whether aliasing was present or not).

-- 
Bill Leonard
Harris Computer Systems Corporation
2101 W. Cypress Creek Road
Fort Lauderdale, FL  33309
Bill.Leonard@mail.hcsc.com

These opinions and statements are my own and do not necessarily reflect the
opinions or positions of Harris Computer Systems Corporation.

------------------------------------------------------------------------------
I feel like I've been sent for and couldn't go, and weren't needed after I
got there.
------------------------------------------------------------------------------

[ comp.std.c++ is moderated.  Submission address: std-c++@ncar.ucar.edu.
  Contact address: std-c++-request@ncar.ucar.edu.  The moderation policy
  is summarized in http://dogbert.lbl.gov/~matt/std-c++/policy.html. ]

>>>>> "BL" == Bill Leonard <bill@amber.ssd.hcsc.com> writes:
[...]
James Kanze:
>> There is a proposed extention to C which would do it, a sort of son of
>> noalias.  I don't know any of the details, but I'm sure that a question
>> in comp.std.c would reach people who did, or who could point you in the
>> right direction.

BL> I continue to think such extensions are a bad idea.  They basically force
BL> the compiler to trust the programmer, and historically that is not a
BL> reliable thing to do.
[...]

Note that James was not talking about `noalias', but about `restrict'.
I don't doubt restricted pointers can be misused or abused and hence
lead to trouble; so can many features of C and C++. I'm not sure I
totally with your view of history though: trusting the programmer is
often pragmatically essential.

Scientific computing in C++ could sure use the extra cycles...

	Daveed
---
[ comp.std.c++ is moderated.  Submission address: std-c++@ncar.ucar.edu.
  Contact address: std-c++-request@ncar.ucar.edu.  The moderation policy
  is summarized in http://dogbert.lbl.gov/~matt/std-c++/policy.html. ]

[Moderator's note: I deleted about 50 lines of quoted material
from this article. -fjh.]

bill@amber.ssd.hcsc.com (Bill Leonard) writes:
[...]
> IMHO, the best answer is improved interprocedural analysis by compilers,
> because that is the safest and also the most optimal -- it detects aliasing
> when it is present, and detects lack of aliasing when it is absent (even if
> the programmer didn't know whether aliasing was present or not).

This is all true, BUT there are and will ever be situations where it is
impossible for a machine to figure out if there is aliasing or not.
I remember a case where I had to tell the CRAY FORTRAN compiler (via
a special comment) to vectorize a loop. It took me and a collegue of
mine nearly an hour to prove that there is no aliasing. But on the other
hand it was crucial to get full speed in that loop.

If it is impossible or hard to get good performance with C++ it will
die out in the scientific computing world, just because there are very
few things missing.  If you are afraid, you can let the compiler print
tons of warnings whenever such a construct is used. But there is need
for a PORTABLE construct and not just a vendor specific #pragma.

Helmut Jarausch
Institute of Technology
RWTH Aachen
Germany
---
[ comp.std.c++ is moderated.  Submission address: std-c++@ncar.ucar.edu.
  Contact address: std-c++-request@ncar.ucar.edu.  The moderation policy
  is summarized in http://dogbert.lbl.gov/~matt/std-c++/policy.html. ]

Bill Leonard (bill@amber.ssd.hcsc.com) wrote:
|> kanze@gabi-soft.fr (J. Kanze) writes:
|> > enseeg14@grenet.fr wrote:
|> > 
|> > |> > for (i = 0 ; i < n ; i++) {
|> > |> >    for (j = 0 ; j < n ; j++) {
|> > |> >       a[i][j] = b[i][j] * c[i] ;
|> > |> >    }
|> > |> > }
|> > 
|> > |> > do j = 1,m
|> > |> >   do i = 1, n
|> > |> >     a (i,j) = b(i,j) * c(i)
|> > |> >   enddo
|> > |> > enddo 
|> > 
|> > Const won't help, and the problem isn't typing, but potential aliasing.
|> > Fortran basically says that the results are undefined if aliasing is
|> > present, C/C++ doesn't.

    [...]

|> > There is a proposed extention to C which would do it, a sort of son of
|> > noalias.  I don't know any of the details, but I'm sure that a question
|> > in comp.std.c would reach people who did, or who could point you in the
|> > right direction.

|> I continue to think such extensions are a bad idea.  They basically force
|> the compiler to trust the programmer, and historically that is not a
|> reliable thing to do.  The original programmer may have been careful to
|> avoid aliasing, but what about the 50 other programmers who came later and
|> made modifications to the program?  Worse still, you may have a bug lurking
|> there for decades until you happen to compile with a compiler that takes
|> advantage of the noalias declaration *and* does it in such a way that the
|> illegal aliasing changes the behavior of the program.  Such bugs are
|> extremely difficult to track down.

I agree (although I'm not too familiar with the proposal, except for
knowing that it exists).  The real problem is that the declaration
affects the code generation in the function, but requires discipline on
the part of the callers.
-- 
James Kanze           (+33) 88 14 49 00          email: kanze@gabi-soft.fr
GABI Software, Sarl., 8 rue des Francs Bourgeois, 67000 Strasbourg, France
Conseils en informatique industrielle--
                             --Beratung in industrieller Datenverarbeitung
---
[ comp.std.c++ is moderated.  Submission address: std-c++@ncar.ucar.edu.
  Contact address: std-c++-request@ncar.ucar.edu.  The moderation policy
  is summarized in http://dogbert.lbl.gov/~matt/std-c++/policy.html. ]

In article <45ld1i$m7i@cicg-communication.grenet.fr>, enseeg14@grenet.fr () writes:
[..]
> C has always been the language where _THE PROGRAMMER_ could make his
> own optimization, but this style of programming is getting deprecated
> according to most C++ who basically say "rely on the compiler, optimize
> only as a last minute operation". But here I have an example of what
> would be very unefficient in C/C++ compared to F90:
> 
> > for (i = 0 ; i < n ; i++) {
> >    for (j = 0 ; j < n ; j++) {
> >       a[i][j] = b[i][j] * c[i] ;
> >    }
> > }
> 
> > do j = 1,m
> >   do i = 1, n
> >     a (i,j) = b(i,j) * c(i)
> >   enddo
> > enddo 
> 
[...]

As a physicist programming in C++ I have to compare the performance of my
programs to those written in FORTRAN.
C++ routines written in a FORTRAN _style_ are often slower than the routines
written in FORTRAN.
Nevertheless my programs are faster since I try to avoid loops
as the one mentioned above, hiding the actual calculation in linear
algebra classes in which I call BLAS routines.
And why not using a FORTRAN subroutine in special cases ?

What's really needed, in my opinion, is not a change in the language which enables
the compiler to perform better optimization, but powerful libraries & classes,
e.g. a BLAS class or sophisticated matrix classes (like LAPACK++ (LAPACK+=2 ?) ).

Regards Peter

------------------------------------------------------------

Peter Schmitteckert   ---  Lehrstuhl fuer Theoret. Physik 2
Institut f\"ur Physik ---  D 86135 Uni Augsburg 
e-mail: Peter.Schmitteckert@Physik.Uni-Augsburg.de
URL:    http://www.physik.uni-augsburg.de/theo2/Group/Schmitteckert.html
Phone:  +49-821-5977-246  Fax:  +49-821-5977-262

[Moderator's note: this discusson seems to be drifting away from the
C++ standard, so I've inserted a Followup-to line to redirect
followups to comp.lang.c++.  You should edit the Newsgroups line if
your reply is relevant to the standard and if you want it to appear in
comp.std.c++.  mha]

---
[ comp.std.c++ is moderated.  Submission address: std-c++@ncar.ucar.edu.
  Contact address: std-c++-request@ncar.ucar.edu.  The moderation policy
  is summarized in http://dogbert.lbl.gov/~matt/std-c++/policy.html. ]