Pointers and Optimization
Daniel Carrera
It is my understanding that one advantage of Fortran pointers compared
to C/C++ pointers is that Fortran pointers don't harm optimization as
much. Can someone show me a simple example that illustrates this?
The only thing I've come up with is the following operations:
a = b + c
d = e + f
These operations are dominated by memory access. A compiler might want
to reorder these operations to access memory sequentially. But if any of
these are pointers, you cannot do that.
I was planning to say that the Fortran compiler always knows if there
are pointers involved. But come to think of it, the C/C++ compiler
should know that too, right? If these operations had pointers you would
see something like:
(*a) = b + c
d = (*e) + f
So it looks like my example is wrong.
Can anyone suggest a correct example that shows how pointers can hurt
optimization and how Fortran avoids it?
Daniel.
Arjen Markus
For one thing, a pointer in C/C++ can point to anything, whereas in
Fortran
a pointer (or better: reference variable) can only point to:
- allocated memory
- variables that have the target attribute or the pointer (which
implies target)
Therefore the Fortran compiler can assume a great number of things
about
variables that do not have either attribute.
A second thing: you can get rid of the pointer attribute by passing
the
array to a routine whose corresponding dummy argument is an ordinary
variable without the target or pointer attribute. That way all the
optimisations get possible again.
I have tried to measure the impact of pointer and allocatable
attributes
in the past, but I have never seen a consistent difference in
performance.
(Which is probably due to me not trying hard enough :))
Regards,
Arjen
Daniel Carrera
> For one thing, a pointer in C/C++ can point to anything, whereas in
> Fortran a pointer (or better: reference variable) can only point to:
> - allocated memory
> - variables that have the target attribute or the pointer (which
> implies target)
>
> Therefore the Fortran compiler can assume a great number of things
> about variables that do not have either attribute.
Can you give me an example of some optimization the Fortran compiler can
do and a C/C++ compiler cannot? I'd like to show it in class.
Daniel.
Tobias Burnus
> It is my understanding that one advantage of Fortran pointers compared
> to C/C++ pointers is that Fortran pointers don't harm optimization as
> much. Can someone show me a simple example that illustrates this?
To my knowledge, Fortran and C have the same issue with regards to
pointers: The pointer address can escape and thus compiler has to assume
that two pointer can point to the same object.
Example for the issue:
subroutine foo(a,b)
real, POINTER :: a(:), b(:)
b = a * 5
In this example, one even needs a temporary array as the A and B might
point to the same array in a nontrivial way. (Based on a real-world
example. One solution would be to mark the arguments as ALLOCATABLE -
then no temporary array is needed.)
The huge advantage in Fortran is that many objects are not pointers,
where C uses pointers: Arrays (except of pointer arrays) and strings,
and any dummy argument which can be modified ("pass by reference").
In Fortran, variables can only alias if they are a pointer or explicitly
marked as TARGET.
Since the 99 standard of C (C99) one can use the "restrict" attribute
for pointers, thus, the same optimizations are also possible with C. The
advantage of Fortran is that by default all variables are not aliasing
while with C one has to make sure that one always uses "restrict", if
possible.
(There are also some differences in standard where the semantics of
Fortran and C is slightly different, which also could help with the
optimization, but I do not know whether this plays a role in practise.)
Thus, Fortran's advantage is that one does not need to use pointers as
often as with C - and that the default attribute favours better
optimization, while for C one needs to take care oneself. (Additionally,
C99 is not yet used everywhere.)
Side note: In many cases, one can replace POINTER by ALLOCATABLE which
gives many advantages: It not only helps to avoid the alias issue, but
allocatables are also always in a well-defined state (allocated or not;
pointers can be associated, not associated or undefined), allocatables
can never leak memory, and convenient things like (re)allocate on
assignment also work:
character(len=:), allocatable :: str
real, allocatable :: x(:)
str = "World"
str = "Hello "//str
x = [ real :: 1, 2, 3, 4, 5 ]
end ! variables automatically freed
which syntactically very much resembles scripting languages. Actually,
arrays is an area where Fortran excels: One can set the bounds as one
wants, multiple ranks are nicely integrate, whole-array operations and
strides are possible. And also bounds checking is possible, which
tremendously helps to find bugs.
Tobias
Tobias Burnus
> Can you give me an example of some optimization the Fortran compiler can
> do and a C/C++ compiler cannot? I'd like to show it in class.
Example for aliasing:
#include <stdlib.h>
void bar(int *);
void foo(void);
void foobar (void)
{
int i;
bar (&i);
i = 5;
foo ();
if (i != 5) { /* .... */ exit(1); }
}
As the pointer address escapes for the "bar" call, the address of "i"
might be known to "foo" and thus the "if" cannot be optimized away.
Using GCC 4.7 with -O2 -fdump-tree-optimized one finds in the dump
(internal representation shown using a C-like syntax; note not all
internal attributes are shown):
int i;
int i.0;
<bb 2>:
bar (&i);
i = 5;
foo ();
i.0_1 = i;
if (i.0_1 != 5)
goto <bb 3>;
(I tried to play around with "restrict", but it didn't make any
difference. Either a "restrict" is not sufficient for GCC's C compiler
or I cannot properly write C99 programs.)
By contrast for the Fortran example:
subroutine foobar()
implicit none
interface
subroutine bar(i)
integer :: i
end subroutine bar
subroutine foo()
end subroutine foo
end interface
integer :: i
call bar(i)
i = 5
call foo()
if (i /= 5) call abort()
end subroutine foobar
Here, the -O2 -fdump-tree-optimized of gfortran 4.7 has:
integer(kind=4) i;
<bb 2>:
bar (&i);
i = 5;
foo (); [tail call]
return;
I am not claiming that that's unfixable in C, but Fortran makes it
easier to write code where the compiler knows that it does not alias.
Note: In case of Fortran, using a module is a better way to get an
explicit interface. If both procedures are in the same file, the
compiler (C and Fortran) have a better chance to do optimizations as it
can analyse (and inline) the procedures.
Note 2: In case of gfortran, the "if" is currently only optimized away
if the explicit interface of "bar" is known. (In future gfortran
versions, the optimization will presumably also applied to calls to
procedures with implicit interfaces.)
Tobias
Daniel Carrera
> The huge advantage in Fortran is that many objects are not pointers,
> where C uses pointers: Arrays (except of pointer arrays) and strings,
> and any dummy argument which can be modified ("pass by reference").
Suppose that "a", "b" and "c" are arrays. Consider array addition:
In Fortran:
a = b + c
In C/C++:
for (i=0, i<10, i++)
{
a[i] = b[i] + c[i]
}
Would it be fair to say that the C/C++ version cannot be optimized to
the same extent as the Fortran version? If so, can you help me
understand how? The picture in my mind is that the C/C++ version
requires pointers while the Fortran version does not, but I'm not really
clear what the Fortran compiler can do to speed up the computation.
> In Fortran, variables can only alias if they are a pointer or explicitly
> marked as TARGET.
I mention this in my talk, and it obviously helps avoid bugs. But can
this feature also improve performance?
Btw, is it correct to say that Fortran pointers are safe from buffer
overruns? Intuitively, it seems like it, because you never do pointer
arithmetic... but I'm not sure.
> Since the 99 standard of C (C99) one can use the "restrict" attribute
> for pointers, thus, the same optimizations are also possible with C.
Thanks for the tip. I looked up "restrict" on Google and found the
following example:
*a += *c;
*b += *c;
If there is a chance that a,b,c point to the same memory location, the
compiler will generate the less optimal code:
load R1 <- *c
load R2 <- *a
add R2 += R1
set R2 -> *a
load R1 <- *c
load R2 <- *b
add R2 += R1
set R2 -> *b
Notice that *c is loaded twice. With the "restrict" keyword, you only
load it once.
But somehow this example is not very satisfying. It looks like a very
small optimization.
Daniel.
Tobias Burnus
> Suppose that "a", "b" and "c" are arrays. Consider array addition:
>
> In Fortran:
> a = b + c
>
> In C/C++:
> for (i=0, i<10, i++)
> {
> a[i] = b[i] + c[i]
> }
>
> Would it be fair to say that the C/C++ version cannot be optimized to
> the same extent as the Fortran version?
Well, it really depends on the declaration - and sometimes on things
which come in between (like in my other example, where "bar(&i)" caused
a variable to escape).
If your C example had:
func(float *a, float b, float *c)
while Fortran had
subroutine func(a, b, c)
real :: a(10), b(10), c(10)
then I'd agree that the C/C++ version cannot be optimized as well as the
Fortran version. However, if (a, b, c) were restricted pointers in C or
simply
float a[10], b[10], c[10]
there would be no difference.
The compiler will generate a similar loop out of the whole-array
assignment as your C loop. And the loop itself can then be optimized by
techniques such as vectorization, loop unrolling etc.
* * *
Side note: I uses "a(10)" in the example above as for "a(:)" strides
would be possible; then the Fortran loop would be equivalent to:
do i = 1, N, stride
a(i) = b(i) + c(i)
end do
where the "stride" hampers optimizations. Use Fortran 2008's CONTIGUOUS
or an explicit-shape dummy argument (or "allocatable :: a" as
allocatables are by construction contiguous).
>> In Fortran, variables can only alias if they are a pointer or explicitly
>> marked as TARGET.
>
> I mention this in my talk, and it obviously helps avoid bugs. But can
> this feature also improve performance?
Hmm, I actually saw it primarily as performance feature. As written,
many optimizations are only possible if the compiler knows that two
variables do not (partially) overlap or that a call to a procedure,
which does not take a variable as argument, cannot have access to the
address of that variable through the back door.
> Btw, is it correct to say that Fortran pointers are safe from buffer
> overruns? Intuitively, it seems like it, because you never do pointer
> arithmetic... but I'm not sure.
Well, you can easily have buffer issues in Fortran. Contrary to C, you
do not get certain types of buffer issues - or at least not as easily,
and some issues are much easier to diagnose, but there are issues. The
most common are out-of-bounds accesses for arrays:
real :: array(10)
array(11) = 7
array(-10) = 8
Those can often be diagnosed at run time (the ones above even at compile
time), but bounds checking reduces the performance.
Another type of pointer issues is:
pointer :: a, b
allocate(a)
b => a
deallocate(b)
a = 7
Here, the last line is wrong as "a" is no longer associated.
And a third issue is if one passes the wrong argument to a procedure
(e.g. a real number to a complex dummy). That's more an issue for
Fortran 77 as with Fortran 90+ modules are more widely used (-> explicit
interfaces). Also Fortran 77 often has assumed-size arrays ("real
array(*)"), which makes bound checking very hard. Nevertheless, it is
still in principle an issue.
But I agree as one does not really do pointer arithmetic and as one
often has objects with well-defined bounds - which includes strings, or
allocatables (rather than pointers), buffer overflows are a bit less of
an issue and easier to diagnose with run-time checking. (Especially the
NAG compiler offers impressive run-time checking support.)
[restrict]
> But somehow this example is not very satisfying. It looks like a very
> small optimization.
Well, the real advantage is the case when the compiler can reorganize
code or even optimize away large chunks of code - but this only works if
it knows that the data is not needed elsewhere. Besides, even small
differences become important if they occur in a hot loop.
Tobias
glen herrmannsfeldt
> On 03/31/2011 10:53 AM, Tobias Burnus wrote:
>> The huge advantage in Fortran is that many objects are not pointers,
>> where C uses pointers: Arrays (except of pointer arrays) and strings,
>> and any dummy argument which can be modified ("pass by reference").
> Suppose that "a", "b" and "c" are arrays. Consider array addition:
> In Fortran:
> a = b + c
> In C/C++:
> for (i=0, i<10, i++)
> {
> a[i] = b[i] + c[i]
> }
> Would it be fair to say that the C/C++ version cannot be optimized to
> the same extent as the Fortran version?
As someone else noted, if the Fortran example can't exclude aliasing,
then a temporary array is needed. The C form never requires a
temporary array.
In contrast to Fortran requiring a temporary array for such
array assignment, PL/I array expressions require changes to
visible. That is, element by element assignment is required.
A processor with vector registers (like the Cray-1) could speed
up the Fortran array assignment, but, in the case of C aliasing,
not the C version. (Consider the case where b=a+1.)
> If so, can you help me
> understand how? The picture in my mind is that the C/C++ version
> requires pointers while the Fortran version does not, but I'm not really
> clear what the Fortran compiler can do to speed up the computation.
It gets more interesting with common subexpression elimination,
which traditionally Fortran compilers did pretty well. Aliasing
does make that harder.
(snip)
> Btw, is it correct to say that Fortran pointers are safe from buffer
> overruns? Intuitively, it seems like it, because you never do pointer
> arithmetic... but I'm not sure.
There are many problems that occur due to the C use of null-terminated
strings, and relying on things being the right length. With C
character operations almost always involving pointers and Fortran
rarely, it isn't as likely, but it isn't that hard to do (if you
have bounds checking (if any) disabled.) Consider:
real a(10), b(20), c(20)
...
a=b+c
(and that is without pointers)
The Fortran compiler can use the dimension of a, b, or c, to
determine the end of the array assignment. Unless bounds checking
is on, it can easily be wrong.
(snip)
It does seem slightly harder to do some optimizations in C, but
they way people usually write C is different enough that it
isn't easy to generalize. As noted recently, there are a few
optmizations that gcc makes that gfortran doesn't. Specifically,
loop unrolling of recursive routines and tail call elimination.
There are likely others, for both languages.
-- glen
Daniel Carrera
> It does seem slightly harder to do some optimizations in C, but
> they way people usually write C is different enough that it
> isn't easy to generalize. As noted recently, there are a few
> optmizations that gcc makes that gfortran doesn't. Specifically,
> loop unrolling of recursive routines and tail call elimination.
>
> There are likely others, for both languages.
Over-all, would you say that Fortran gives you the same speed as C
without having to think as much about low-level optimization?
Daniel.
m_b_metcalf
> >> In Fortran, variables can only alias if they are a pointer or explicitly
> >> marked as TARGET.
>
> > I mention this in my talk, and it obviously helps avoid bugs. But can
> > this feature also improve performance?
>
> Hmm, I actually saw it primarily as performance feature.
The target attribute was added to Fortran solely as an aid to
optimization (its absence was pointed out (no pun intended) by a
Pascal expert.
Regards,
Mike Metcalf
Daniel Carrera
> The target attribute was added to Fortran solely as an aid to
> optimization (its absence was pointed out (no pun intended) by a
> Pascal expert.
I'm dumb today. Could you help me understand how it helps optimization?
I think that would be a nice thing to explain on a slide in my talk.
Daniel.
m_b_metcalf
Simply to indicate what is a target. Everything else is not and (if
not a pointer) can participate in standard optimizations.
Regards,
Mike Metcalf
Daniel Carrera
> Simply to indicate what is a target. Everything else is not and (if
> not a pointer) can participate in standard optimizations.
Not trying to be difficult, but what I meant was, can you show me a
"standard optimization" that cannot be done with a target? This is
basically what I have been trying to figure out since I started this
thread. It appears that my first example was wrong. Tobias showed a
different example:
int i;
bar (&i);
i = 5;
foo ();
if (i != 5) { /* .... */ exit(1); }
Is this the main scenario you have in mind? So, if Fortran terms, if "i"
is not set to "target", it is safe to optimize away the conditional. Is
this what you are thinking of mainly?
Daniel.
m_b_metcalf
Yes. It is very helpful to a compiler to know that a variable that is
not a pointer or a taget may not be accessed by a pointer target.
Regards,
Mike Metcalf
Arjen Markus
One example:
subroutine doit( a, b )
real, target :: a
real :: b
real :: d
real, pointer :: c
c => a
d = a + 1
call subc( c )
b = 2 * a
...
end subroutine
If a does not have the target attribute, the two assignments trivially
use the
same value of a and that value can be left in a register, possibly
moving the
second assignment to before the call.
Now that a does have that and there is even a pointer pointing to it,
the intervening
call might just change the value of a, so that a has to be reloaded
from memory
into the registers. Code motion is prevented too.
A bit artificial perhaps, but code motion and register allocation are
of very
great concern to a compiler.
Regards,
Arjen
Gordon Sande
One of the standard optimizations is recognition of common subexpressions.
When there is aliasing, due to pointers or the side effects of argument
association, a potential common subexpression may no longer be possible.
Common subexpressions turn into compiler generated (i.e unkown to the user)
tempoaries with aliasing limiting the scope for forming them.
Fortran is strongly biased towards there being no aliasing while my
understanding is that C has added keywords to indicated that there
is no aliasing, (sort of (only) like TARGET in Fortran).
Daniel Carrera
> One example:
>
> subroutine doit( a, b )
> real, target :: a
> real :: b
>
> real :: d
> real, pointer :: c
>
> c => a
>
> d = a + 1
> call subc( c )
> b = 2 * a
>
> ...
> end subroutine
>
> If a does not have the target attribute, the two assignments trivially
> use the same value of a and that value can be left in a register, possibly
> moving the second assignment to before the call.
Thank you. Am I right to think that if "c => a" had not been there, the
compiler would optimize?
I have been trying to turn your example into something where C/C++
cannot optimize but Fortran can. My first thoght was this:
real :: a, b, d
real, pointer :: ptr
d = a + 1
call foo( a, ptr )
b = 2 * a
And C/C++:
float a, b, d;
float *ptr;
d = a + 1
foo( &a, ptr )
b = 2 * a
But then I realized that Fortran would not be able to optimize this
either because "foo()" could change "a" directly. So my next thought was:
real :: a, b, d
real, pointer :: ptr
d = a + 1
call foo( ptr )
b = 2 * a
And C/C++:
float a, b, d;
float *ptr;
d = a + 1
foo( ptr )
b = 2 * a
But now they can *both* optimize because ptr is not pointing to "a".
So I haven't been able to show what the "target" attribute buys you. I
need to think some more...
Cheers,
Daniel.
Arjen Markus
>
> - Tekst uit oorspronkelijk bericht weergeven -
If, in my example, you leave out the target attribute to a, c can not
point
to it and therefore any optimisation wrt a is okay.
(A clever compiler might be able to see this when c is not pointing to
a,
but I doubt it will be able to in more realistic cases with a lot
more
code)
Regards,
Arjen
Daniel Carrera
> If, in my example, you leave out the target attribute to a, c can not
> point to it and therefore any optimisation wrt a is okay.
>
> (A clever compiler might be able to see this when c is not pointing to
> a, but I doubt it will be able to in more realistic cases with a lot
> more code)
Are you saying that in a non-trivial case, a Fortran compiler would be
able to optimize this:
real :: a, b, d
real, pointer :: ptr
d = a + 1
... lots of code ...
call foo( ptr )
b = 2 * a
While in C/C++ it would not, because basically everything is "target"?
Daniel.
Arjen Markus
For sufficiently small amounts of "lots of code" (and the added
constraint
that a can not be changed by that code), yes, as far as I understand
it.
But I am not a compiler expert - I may be wrong here. But by all the
stuff
that I have read, that is what can happen.
Regards,
Arjen
Daniel Carrera
>> Are you saying that in a non-trivial case, a Fortran compiler would be
>> able to optimize this:
>>
>> real :: a, b, d
>> real, pointer :: ptr
>>
>> d = a + 1
>> ... lots of code ...
>> call foo( ptr )
>> b = 2 * a
>>
>> While in C/C++ it would not, because basically everything is "target"?
>
> that a can not be changed by that code), yes, as far as I understand it.
> But I am not a compiler expert - I may be wrong here. But by all the
> stuff that I have read, that is what can happen.
Sufficiently small? When "lots of code" == "nothing" (i.e. your example)
Fortran and C/C++ seem to do exactly the same optimization.
I just found an example where the compiler does *not* optimize even
though I think it should:
function foo(a,b,c,ptr)
real :: a, b, c, foo
real, pointer :: ptr
a = 1 ! Can delete
b = ptr + 2
a = 3
foo = a + b
end function
The "a = 1" line doesn't do anything, but gfortran doesn't remove it.
Compiling with -O2 -fdump-tree-optimized I get the following tree:
<bb 2>:
*a_1(D) = 1.0e+0;
D.1498_3 = *ptr_2(D);
D.1499_4 = *D.1498_3;
D.1500_5 = D.1499_4 + 2.0e+0;
*b_6(D) = D.1500_5;
*a_1(D) = 3.0e+0;
__result_foo.1_9 = D.1500_5 + 3.0e+0;
return __result_foo.1_9;
Daniel Carrera
artificial and less obvious.
Here is the C/C++ version:
#include <stdlib.h>
void bar(int *);
void foo(void);
int foobar (void)
{
int a, b, c;
int *ptr;
ptr = &c;
bar (ptr);
c = 3;
a = 1 + c;
foo();
b = c*2;
if (a > b)
return 4;
else
return 5;
}
You can see that, as long as foo() doesn't change "c", you can do
massive optimization. Here is the Fortran:
module test
interface
subroutine bar(i)
integer :: i
end subroutine bar
subroutine foo()
end subroutine foo
end interface
contains
function foobar()
integer :: a, b
integer :: foobar
integer, pointer :: ptr
integer, target :: c
ptr => c
call bar(ptr)
c = 3
a = 1 + c
call foo()
b = c*2
if (a > b) then
foobar = 4
else
foobar = 5
end if
end function
end module
Because bar() receives "ptr" and not "c", we can be confident that foo()
cannot modify "c", and thus we can optimize. Using gcc -O2, the
optimized tree for the C/C++ version is:
foobar ()
{
int c;
int b;
int D.2614;
int c.0;
<bb 2>:
bar (&c);
c = 3;
foo ();
c.0_5 = c;
b_6 = c.0_5 * 2;
if (b_6 <= 3)
goto <bb 3>;
else
goto <bb 4>;
<bb 3>:
<bb 4>:
# D.2614_1 = PHI <4(3), 5(2)>
return D.2614_1;
}
While the tree for the Fortran version is:
foobar ()
{
integer(kind=4) c;
<bb 2>:
bar (&c);
foo ();
return 5;
}
Cheers,
Daniel.
glen herrmannsfeldt
> On 03/31/2011 01:55 PM, m_b_metcalf wrote:
>> Simply to indicate what is a target. Everything else is not and (if
>> not a pointer) can participate in standard optimizations.
> Not trying to be difficult, but what I meant was, can you show me a
> "standard optimization" that cannot be done with a target?
One of the favorite Fortran optimization historically has been
common subexpression elimination. Now, many use temporary variables
to avoid writing the same thing twice, but many compilers will
find them. If the compiler can't be sure that the expression doesn't
change, such as through aliasing, then it can't be sure it has the
same value.
Another Fortran favorite is moving invariant expressions out
of loops. Again, aliasing could change that.
Even more, note that it is not allowed to change the DO variable
inside a DO loop. In C, programs are specifically allowed to
change the loop variable inside the loop, and often do that.
Many optimizations only become important as programs get larger,
so it isn't so easy to make a convincing example.
-- glen
glen herrmannsfeldt
(snip)
> It appears that my first example was wrong. Tobias showed a
> different example:
> int i;
> bar (&i);
> i = 5;
> foo ();
> if (i != 5) { /* .... */ exit(1); }
> Is this the main scenario you have in mind? So, if Fortran terms, if "i"
> is not set to "target", it is safe to optimize away the conditional. Is
> this what you are thinking of mainly?
That would do it. But then you might ask why one would do that?
It is a nice example, but doesn't really demonstrate the case
for real code.
(I did once, before 1990, write a C routine to do NAMELIST input.
It works pretty much the way you write, with one call giving the
name and pointer to a variable, (call as many times as needed)
and another that does the actual read. There would be no reason
to change the variables between calls, though.)
-- glen
glen herrmannsfeldt
(snip)
> subroutine doit( a, b )
> real, target :: a
> real :: b
> real :: d
> real, pointer :: c
> c => a
> d = a + 1
> call subc( c )
> b = 2 * a
> ...
> end subroutine
> If a does not have the target attribute, the two assignments
> trivially use the same value of a and that value can be left
> in a register, possibly moving the second assignment to before
> the call.
Note that Fortran and C have the VOLATILE attribute, and PL/I
the ABNORMAL attribute to warn the compiler that variables may
change at unexpected times.
-- glen
Arjen Markus
>
> - Tekst uit oorspronkelijk bericht weergeven -
Well, it is possible in principle, but there is no guarantee the
compiler
does do it :).
Regards,
Arjen
Daniel Carrera
:-)
I came up with another example that combines yours and Tobias, and I'm
very happy with the results:
Fortran:
function foobar()
integer :: a, b
integer :: foobar
integer, pointer :: ptr
integer, target :: c
ptr => c
call bar(ptr)
c = 3
a = 1 + c
call foo()
b = c*2
if (a > b) then
foobar = 4
else
foobar = 5
end if
end function
C / C++:
int foobar (void)
{
int a, b, c;
int *ptr;
ptr = &c;
bar (ptr);
c = 3;
a = 1 + c;
foo();
b = c*2;
if (a > b)
return 4;
else
return 5;
}
Then, when you run it through gfortran -O2 you get this:
foobar ()
{
integer(kind=4) c;
<bb 2>:
bar (&c);
foo ();
return 5;
}
You can see how gfortran optimized away almost the entire function, but
for C/C++ you get:
foobar ()
{
int c;
int b;
int D.2614;
int c.0;
<bb 2>:
bar (&c);
c = 3;
foo ();
c.0_5 = c;
b_6 = c.0_5 * 2;
if (b_6 <= 3)
goto <bb 3>;
else
goto <bb 4>;
<bb 3>:
<bb 4>:
# D.2614_1 = PHI <4(3), 5(2)>
return D.2614_1;
}
Cheers,
Daniel.
Arjen Markus
That is definitely impressive! And I mean that - creating this very
clear example
and creating a compiler that does this.
Regards,
Arjen
David Thompson
wrote:
> On 03/31/2011 11:38 AM, Daniel Carrera wrote:
> > Suppose that "a", "b" and "c" are arrays. Consider array addition:
> >
> > In Fortran:
> > a = b + c
> >
> > In C/C++:
> > for (i=0, i<10, i++)
> > {
> > a[i] = b[i] + c[i]
> > }
> >
Nits: semicolons not commas in for, and semicolon after assignment.
> > Would it be fair to say that the C/C++ version cannot be optimized to
> > the same extent as the Fortran version?
>
> Well, it really depends on the declaration - and sometimes on things
> which come in between (like in my other example, where "bar(&i)" caused
> a variable to escape).
>
>
> If your C example had:
>
> func(float *a, float b, float *c)
>
Nit: need '*' on b also.
> while Fortran had
>
> subroutine func(a, b, c)
> real :: a(10), b(10), c(10)
>
> then I'd agree that the C/C++ version cannot be optimized as well as the
> Fortran version. However, if (a, b, c) were restricted pointers in C or
> simply
> float a[10], b[10], c[10]
> there would be no difference.
>
Caution: if C or C++ has a[10] etc. *as local variables* the compiler
knows they can't alias (and similarly for Fortran). But if you write a
C or C++ routine with a 'parameter' (= Fortran dummy) that *looks*
like an array, *it isn't* -- it's actually a pointer-to-element, and
thus exactly the same case as above for good and ill.
<snip rest>
Ron Shepard
David Thompson <dave.th...@verizon.net> wrote:
> Caution: if C or C++ has a[10] etc. *as local variables* the compiler
> knows they can't alias (and similarly for Fortran).
Is this really true? You cannot have a pointer that points to a
local variable in C?
$.02 -Ron Shepard
JB
Sure you can; the part of the sentence to note is the "the compiler
knows" part. For local variables, the alias analysis problem is easily
brute-forced.
--
JB
Ron Shepard
wrote:
I do not understand your original point then. In C, the compiler
must allow for the possibility that a pointer in an expression can
point to that array in the same expression. Your original assertion
was that it did not.
In fortran, even if you have a pointer, the compiler knows that it
cannot point to that local array (unless it has the TARGET
attribute, of course). So memory optimizations can occur in fortran,
but not in C. In fortran there is the TARGET attribute, and in C
(at least some recent version) there is the restrict declaration,
and those change things (by making the fortran more like C, and C
more like fortran).
$.02 -Ron Shepard
JB
> In article <slrnips4r...@kosh.hut.fi>, JB <f...@bar.invalid>
> wrote:
>
>> On 2011-04-07, Ron Shepard <ron-s...@NOSPAM.comcast.net> wrote:
>> > In article <u1oqp6l1dvaiugb9g...@4ax.com>,
>> > David Thompson <dave.th...@verizon.net> wrote:
>> >
>> >> Caution: if C or C++ has a[10] etc. *as local variables* the compiler
>> >> knows they can't alias (and similarly for Fortran).
>> >
>> > Is this really true? You cannot have a pointer that points to a
>> > local variable in C?
>>
>> Sure you can; the part of the sentence to note is the "the compiler
>> knows" part. For local variables, the alias analysis problem is easily
>> brute-forced.
>
> I do not understand your original point then. In C, the compiler
> must allow for the possibility that a pointer in an expression can
> point to that array in the same expression. Your original assertion
> was that it did not.
Which original assertion? Unless I'm mistaken, my previous message was
my first message to this thread, so I don't recall where I asserted
anything like that. Can you refresh my memory?
> In fortran, even if you have a pointer, the compiler knows that it
> cannot point to that local array (unless it has the TARGET
> attribute, of course). So memory optimizations can occur in fortran,
> but not in C. In fortran there is the TARGET attribute, and in C
> (at least some recent version) there is the restrict declaration,
> and those change things (by making the fortran more like C, and C
> more like fortran).
The point was that for local variables, the compiler can easily
analyze whether some pointer is made to point to it, and if not,
safely optimize the code with the assumption that the variable is not
aliased.
--
JB
nm...@cam.ac.uk
>On 2011-04-08, Ron Shepard <ron-s...@NOSPAM.comcast.net> wrote:
>>
>> I do not understand your original point then. In C, the compiler
>> must allow for the possibility that a pointer in an expression can
>> In fortran, even if you have a pointer, the compiler knows that it
>> cannot point to that local array (unless it has the TARGET
>> attribute, of course). So memory optimizations can occur in fortran,
>> but not in C. In fortran there is the TARGET attribute, and in C
>> (at least some recent version) there is the restrict declaration,
>> and those change things (by making the fortran more like C, and C
>> more like fortran).
>
>The point was that for local variables, the compiler can easily
>analyze whether some pointer is made to point to it, and if not,
>safely optimize the code with the assumption that the variable is not
>aliased.
No, Ron Shephard is correct. You are correct in the very simplest
cases, but they are rarer than most people realise. For example:
double *global_array;
void weeble (const double *arg_array) {
int i;
double local_array[100];
for (i = 0; i < 100; ++i) {
local_array[i] = arg_array[i];
local_array[i] = operate(local_array);
global_array[i] = local_array[i];
}
}
When I have looked at practical codes, the number of cases where
a program COULD alias a local array were far higher than most
people believe.
Regards,
Nick Maclaren.
glen herrmannsfeldt
> In article <slrnips4r...@kosh.hut.fi>, JB <f...@bar.invalid>
(snip)
>> Sure you can; the part of the sentence to note is the "the compiler
>> knows" part. For local variables, the alias analysis problem is easily
>> brute-forced.
> I do not understand your original point then. In C, the compiler
> must allow for the possibility that a pointer in an expression can
> point to that array in the same expression. Your original assertion
> was that it did not.
double a[10],b[10],c[10];
int i;
for(i=0;i<10;i++) scanf("%f%f",a+i,b+i);
for(i=0;i<10;i++) c[i]=a[i]+b[i];
the compiler knows, even though a, b, and c are pointers
(notice their use in the scanf function call), that they
can't alias.
For extra challenge, consider the following C loop:
for(i=0;i<10;i++) i[c]=i[a]+i[b];
(Don't try that in Fortran.)
-- glen
glen herrmannsfeldt
> In article <slrniptd1...@kosh.hut.fi>, JB <f...@bar.invalid> wrote:
>>On 2011-04-08, Ron Shepard <ron-s...@NOSPAM.comcast.net> wrote:
>>> In fortran, even if you have a pointer, the compiler knows that it
>>> cannot point to that local array (unless it has the TARGET
>>> attribute, of course). So memory optimizations can occur in fortran,
>>> but not in C.
>>The point was that for local variables, the compiler can easily
>>analyze whether some pointer is made to point to it, and if not,
>>safely optimize the code with the assumption that the variable is not
>>aliased.
> cases, but they are rarer than most people realise. For example:
> double *global_array;
> void weeble (const double *arg_array) {
> int i;
> double local_array[100];
> for (i = 0; i < 100; ++i) {
> local_array[i] = arg_array[i];
> local_array[i] = operate(local_array);
> global_array[i] = local_array[i];
> }
> }
> When I have looked at practical codes, the number of cases where
> a program COULD alias a local array were far higher than most
> people believe.
I wonder, though, how many C programmers would instead write
three separate loops? (Closer to the array expression
in Fortran.) Now, which is easier to optimize on modern
processors, the separate loops or three assignments in one loop?
Even more, it is pretty hard to say which optimizations which
compiler will find that the other won't. In the test that I
showed a few weeks ago, gcc discovered the tail recursion,
did loop unrolling on the recursion itself, plus tail recursion
optimization. gfortran, given pretty much the same thing, didn't.
(Considerint how much code is in common between the two, that
is somewhat surprising.)
-- glen
JB
To be honest, I'm having trouble seeing where our supposed
disagreement is here. For the record, I didn't say that a C compiler
can always assume that a local variable doesn't alias. I said that the
compiler can figure out whether the function does something which
might introduce aliasing for local variables (rather than always
assumng that aliasing might happen, which a naive compiler might
do). As in your example where the operate() calls makes the address of
local_array escape, meaning that in the third statement of the loop,
the compiler must (in the absense of interprocedural optimization, at
least) assume that global_array and local_array may alias.
I'm sure you're correct that it's common that functions do something
which may introduce aliasing for local variables. Then again, I was
never arguing against that.
--
JB
nm...@cam.ac.uk
glen herrmannsfeldt <g...@ugcs.caltech.edu> wrote:
>
>I wonder, though, how many C programmers would instead write
>three separate loops? (Closer to the array expression
>in Fortran.) Now, which is easier to optimize on modern
>processors, the separate loops or three assignments in one loop?
Look, that was just an example! The point is that passing an array
to a function potentially aliases that array for ever and a day.
That is why inter-procedural optimisation is so much more effective
for C than Fortran - it starts from a lower point and can resolve
many of the aliasing issues.
Regards,
Nick Maclaren.
Arjen Markus
> In article <inmeu0$f9...@dont-email.me>,
... and more needed, I'd say, as a consequence of such
aliasing possibilities.
Regards,
Arjen
nm...@cam.ac.uk
Arjen Markus <arjen.m...@gmail.com> wrote:
>>
>> >I wonder, though, how many C programmers would instead write
>> >in Fortran.) =A0Now, which is easier to optimize on modern
>> >processors, the separate loops or three assignments in one loop?
>>
>> to a function potentially aliases that array for ever and a day.
>> That is why inter-procedural optimisation is so much more effective
>> for C than Fortran - it starts from a lower point and can resolve
>> many of the aliasing issues.
>
>aliasing possibilities.
Very much so. Without IPO, much of C and all of C++ are
essentially unoptimisable.
Regards,
Nick Maclaren.
glen herrmannsfeldt
> In article <inmeu0$f9t$1...@dont-email.me>,
> glen herrmannsfeldt <g...@ugcs.caltech.edu> wrote:
>>I wonder, though, how many C programmers would instead write
>>three separate loops? (Closer to the array expression
>>in Fortran.) Now, which is easier to optimize on modern
>>processors, the separate loops or three assignments in one loop?
> Look, that was just an example! The point is that passing an array
> to a function potentially aliases that array for ever and a day.
Yes, but even so, putting more than one assignment in the
loop increases the chance that aliased variables will be in
the loop.
> That is why inter-procedural optimisation is so much more effective
> for C than Fortran - it starts from a lower point and can resolve
> many of the aliasing issues.
And why is it that C can optimize recursive calls in ways that
Fortran can't (or doesn't)? It does seem that there are some
optmizations that C does that Fortran doesn't.
-- glen
nm...@cam.ac.uk
Simple. Fortran compilers could, if it were worth it. Very few
people use recursion in Fortran, and even fewer use it in
performance-critical code.
Regards,
Nick Maclaren.
Richard Maine
> Simple. Fortran compilers could, if it were worth it. Very few
> people use recursion in Fortran, and even fewer use it in
> performance-critical code.
Gee. That sounds a lot like something I recently said in an unrelated
thread (on why I thought stack limits were a bigger problem for Fortran
programmers than infinite recursion).
--
Richard Maine | Good judgment comes from experience;
email: last name at domain . net | experience comes from bad judgment.
domain: summertriangle | -- Mark Twain
nm...@cam.ac.uk
Richard Maine <nos...@see.signature> wrote:
>
>> Simple. Fortran compilers could, if it were worth it. Very few
>> people use recursion in Fortran, and even fewer use it in
>> performance-critical code.
>
>Gee. That sounds a lot like something I recently said in an unrelated
>thread (on why I thought stack limits were a bigger problem for Fortran
>programmers than infinite recursion).
Surprise, surprise! And, yes, I remembered your posting when I posted
that - but it wasn't why I did. Traditionally, Fortran designs use
iteration.
Regards,
Nick Maclaren.
glen herrmannsfeldt
(snip)
> Surprise, surprise! And, yes, I remembered your posting when I posted
> that - but it wasn't why I did. Traditionally, Fortran designs use
> iteration.
Well, linked-list and tree processing, especially tree processing,
tend to work well with recursion, and are much less often done
in Fortran than some other languages.
-- glen