Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #53499 > unrolled thread

harder case for optimization

Back to article view | Back to comp.lang.c

Contents

  harder case for optimization fir <profesor.fir@gmail.com> - 2014-11-27 00:42 -0800
    Re: harder case for optimization "BartC" <bc@freeuk.com> - 2014-11-27 11:34 +0000
      Re: harder case for optimization David Brown <david.brown@hesbynett.no> - 2014-11-27 13:29 +0100
      Re: harder case for optimization Malcolm McLean <malcolm.mclean5@btinternet.com> - 2014-11-27 05:58 -0800
        Re: harder case for optimization Malcolm McLean <malcolm.mclean5@btinternet.com> - 2014-11-27 06:36 -0800
      Re: harder case for optimization fir <profesor.fir@gmail.com> - 2014-11-27 12:26 -0800
    Re: harder case for optimization "BartC" <bc@freeuk.com> - 2014-11-27 22:07 +0000
      Re: harder case for optimization fir <profesor.fir@gmail.com> - 2014-11-27 14:49 -0800
        Re: harder case for optimization "BartC" <bc@freeuk.com> - 2014-11-28 00:05 +0000
      Re: harder case for optimization David Brown <david.brown@hesbynett.no> - 2014-11-28 00:46 +0100
        Re: harder case for optimization "BartC" <bc@freeuk.com> - 2014-11-28 00:55 +0000
          Re: harder case for optimization David Brown <david.brown@hesbynett.no> - 2014-11-28 07:20 +0100
            Re: harder case for optimization Malcolm McLean <malcolm.mclean5@btinternet.com> - 2014-11-28 00:41 -0800
              Re: harder case for optimization fir <profesor.fir@gmail.com> - 2014-11-28 01:54 -0800
                Re: harder case for optimization Malcolm McLean <malcolm.mclean5@btinternet.com> - 2014-11-28 02:19 -0800
                  Re: harder case for optimization fir <profesor.fir@gmail.com> - 2014-11-28 04:05 -0800
                    Closed captioning (Was: harder case for something or other) gazelle@shell.xmission.com (Kenny McCormack) - 2014-11-28 12:15 +0000
                    Re: harder case for optimization fir <profesor.fir@gmail.com> - 2014-11-28 06:11 -0800
                Re: harder case for optimization gazelle@shell.xmission.com (Kenny McCormack) - 2014-11-28 12:18 +0000
                  Re: harder case for optimization fir <profesor.fir@gmail.com> - 2014-11-28 04:42 -0800
                    Re: harder case for optimization gazelle@shell.xmission.com (Kenny McCormack) - 2014-11-28 16:37 +0000
                      Re: harder case for optimization fir <profesor.fir@gmail.com> - 2014-11-28 08:48 -0800
                        Re: harder case for optimization Kaz Kylheku <kaz@kylheku.com> - 2014-11-28 16:51 +0000
                          Re: harder case for optimization fir <profesor.fir@gmail.com> - 2014-11-28 10:38 -0800
              Re: harder case for optimization David Brown <david.brown@hesbynett.no> - 2014-11-28 11:34 +0100
            Re: harder case for optimization "BartC" <bc@freeuk.com> - 2014-11-28 11:21 +0000
              Re: harder case for optimization fir <profesor.fir@gmail.com> - 2014-11-28 04:23 -0800
              Re: harder case for optimization David Brown <david.brown@hesbynett.no> - 2014-11-28 13:58 +0100
                Re: harder case for optimization "BartC" <bc@freeuk.com> - 2014-11-28 13:46 +0000
                  Re: harder case for optimization David Brown <david.brown@hesbynett.no> - 2014-11-28 16:25 +0100
                    Re: harder case for optimization fir <profesor.fir@gmail.com> - 2014-11-28 08:18 -0800
                      Re: harder case for optimization David Brown <david.brown@hesbynett.no> - 2014-11-28 20:17 +0100
                    Re: harder case for optimization Malcolm McLean <malcolm.mclean5@btinternet.com> - 2014-11-28 08:54 -0800
                      Re: harder case for optimization David Brown <david.brown@hesbynett.no> - 2014-11-28 20:22 +0100
                        Re: harder case for optimization Malcolm McLean <malcolm.mclean5@btinternet.com> - 2014-11-28 11:29 -0800
                        Re: harder case for optimization Kaz Kylheku <kaz@kylheku.com> - 2014-11-28 19:51 +0000
                          Re: harder case for optimization David Brown <david.brown@hesbynett.no> - 2014-11-28 20:58 +0100
                          Re: harder case for optimization Melzzzzz <mel@zzzzz.com> - 2014-11-28 21:03 +0100
                            Re: harder case for optimization Kaz Kylheku <kaz@kylheku.com> - 2014-11-28 20:11 +0000
                              Re: harder case for optimization Melzzzzz <mel@zzzzz.com> - 2014-11-28 21:31 +0100
                        Re: harder case for optimization "BartC" <bc@freeuk.com> - 2014-11-28 20:06 +0000
                    Re: harder case for optimization "BartC" <bc@freeuk.com> - 2014-11-28 17:14 +0000
                      Re: harder case for optimization David Brown <david.brown@hesbynett.no> - 2014-11-28 20:54 +0100
                        Re: harder case for optimization "BartC" <bc@freeuk.com> - 2014-11-28 20:16 +0000
                          Re: harder case for optimization David Brown <david.brown@hesbynett.no> - 2014-11-28 21:56 +0100
          Re: harder case for optimization fir <profesor.fir@gmail.com> - 2014-11-27 23:37 -0800
            Re: harder case for optimization fir <profesor.fir@gmail.com> - 2014-11-27 23:54 -0800
            Re: harder case for optimization BartC <bc@freeuk.com> - 2014-11-28 11:01 +0000
              Re: harder case for optimization fir <profesor.fir@gmail.com> - 2014-11-28 23:52 -0800
                Re: harder case for optimization Morris Dovey <mrdovey@iedu.com> - 2014-11-29 02:03 -0600
                  Re: harder case for optimization fir <profesor.fir@gmail.com> - 2014-11-29 00:38 -0800
    Re: harder case for optimization fir <profesor.fir@gmail.com> - 2014-11-29 03:12 -0800
      Re: harder case for optimization BartC <bc@freeuk.com> - 2014-11-29 12:09 +0000
        Re: harder case for optimization fir <profesor.fir@gmail.com> - 2014-11-29 04:18 -0800
        Re: harder case for optimization fir <profesor.fir@gmail.com> - 2014-11-29 05:22 -0800
          Re: harder case for optimization BartC <bc@freeuk.com> - 2014-11-29 16:58 +0000
            Re: harder case for optimization fir <profesor.fir@gmail.com> - 2014-11-29 09:35 -0800
            Re: harder case for optimization Malcolm McLean <malcolm.mclean5@btinternet.com> - 2014-11-29 10:55 -0800
              Re: harder case for optimization BartC <bc@freeuk.com> - 2014-11-29 21:00 +0000
                Re: harder case for optimization Ian Collins <ian-news@hotmail.com> - 2014-11-30 11:25 +1300
                  Re: harder case for optimization BartC <bc@freeuk.com> - 2014-11-29 22:56 +0000
                    Re: harder case for optimization Ian Collins <ian-news@hotmail.com> - 2014-11-30 12:00 +1300
                      Re: harder case for optimization fir <profesor.fir@gmail.com> - 2014-11-29 16:01 -0800
                    Re: harder case for optimization fir <profesor.fir@gmail.com> - 2014-11-29 16:21 -0800
                      Re: harder case for optimization fir <profesor.fir@gmail.com> - 2014-11-29 16:52 -0800
                        Re: harder case for optimization fir <profesor.fir@gmail.com> - 2014-11-29 17:14 -0800
              Re: harder case for optimization glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-11-30 00:20 +0000
                Re: harder case for optimization Malcolm McLean <malcolm.mclean5@btinternet.com> - 2014-11-29 16:43 -0800
          Re: harder case for optimization Kaz Kylheku <kaz@kylheku.com> - 2014-11-29 17:29 +0000
    Re: harder case for optimization fir <profesor.fir@gmail.com> - 2014-12-05 02:12 -0800

Page 2 of 4 — ← Prev page 1 [2] 3 4  Next page →

#53589

In article <0864ef43-e3af-4842-b581-2a7f4a80d376@googlegroups.com>,
fir  <profesor.fir@gmail.com> wrote:
>W dniu piątek, 28 listopada 2014 13:18:46 UTC+1 użytkownik Kenny McCormack napisał:
>> In article <41a8d4a7-894a-4b15-b29b-0c25835f07d1@googlegroups.com>,
>> fyr  <profesor.fir@gmail.com> wrote:
>> ...
>> >- playn symplyfyyng
>> >- heavyer algorytmyc (ynterpolatyons.cache structures)
>> >- c-level 'mycro'optymystatyons
>> >- more cores
>> >- asm/sse
>> >
>> 
>> Fyxed yt for you.
>> 
>this is kind of realy weak (simple-mind) humour

If it teaches you how to spell optimization, it will have been worth it.

-- 
(The Republican mind, in a nutshell)
You believe things that are incomprehensible, inconsistent, impossible
because we have commanded you to believe them; go then and do what is
unjust because we command it. Such people show admirable reasoning. Truly,
whoever is able to make you absurd is able to make you unjust. If the
God-given understanding of your mind does not resist a demand to believe
what is impossible, then you will not resist a demand to do wrong to that
God-given sense of justice in your heart. As soon as one faculty of your
soul has been dominated, other faculties will follow as well. And from this
derives all those crimes of religion which have overrun the world.

(Alternative condensed translation)
"Those who can make you believe absurdities, can make you commit atrocities".

[toc] | [prev] | [next] | [standalone]

#53590

W dniu piątek, 28 listopada 2014 17:37:11 UTC+1 użytkownik Kenny McCormack napisał:
> In article <0864ef43-e3af-4842-b581-2a7f4a80d376@googlegroups.com>,
> fir  <profesor.fir@gmail.com> wrote:
> >W dniu piątek, 28 listopada 2014 13:18:46 UTC+1 użytkownik Kenny McCormack napisał:
> >> In article <41a8d4a7-894a-4b15-b29b-0c25835f07d1@googlegroups.com>,
> >> fyr  <profesor.fir@gmail.com> wrote:
> >> ...
> >> >- playn symplyfyyng
> >> >- heavyer algorytmyc (ynterpolatyons.cache structures)
> >> >- c-level 'mycro'optymystatyons
> >> >- more cores
> >> >- asm/sse
> >> >
> >> 
> >> Fyxed yt for you.
> >> 
> >this is kind of realy weak (simple-mind) humour
> 
> If it teaches you how to spell optimization, it will have been worth it.
> 
such kind simple mind-ness is never "worth it"

[toc] | [prev] | [next] | [standalone]

#53591

On 2014-11-28, fir <profesor.fir@gmail.com> wrote:
> such kind simple mind-ness is never "worth it"

A prime example being everything you've posted to this newsgroup so far.

[toc] | [prev] | [next] | [standalone]

#53596

W dniu piątek, 28 listopada 2014 17:51:53 UTC+1 użytkownik Kaz Kylheku napisał:
> On 2014-11-28, fir <profesor.fir@gmail.com> wrote:
> > such kind simple mind-ness is never "worth it"
> 
> A prime example being everything you've posted to this newsgroup so far.

this 'notice' is both untrue and primitive minded, I know you can produce tons of it this is cheap stuff

[toc] | [prev] | [next] | [standalone]

#53563

On 28/11/14 09:41, Malcolm McLean wrote:
> On Friday, November 28, 2014 6:21:01 AM UTC, David Brown wrote:
>>
>> A golden rule is never to bother testing speed at -O0.  It's like trying
>> to tune your car engine to go faster while restricting yourself to first
>> gear. 
>>
> That refers to micro-optimisation.
> 

Yes.

> Algorithmic optimisation will show up regardless of optimisation settings,
> and is your first consideration.
> 

Yes, I mentioned that too - and I agree with you entirely.  Perhaps I
was not clear enough?  I suppose it is one of these things that can
never be emphasised enough.

>> A golden rule is never to bother testing speed at -O0.  It's like trying
>> to tune your car engine to go faster while restricting yourself to first
>> gear.  Time your code with -O2 and -O3, along with appropriate "cpu" and
>> "tune" flags, before bothering to think about these sorts of
>> micro-optimisations.  (Of course, macro optimisations - changing
>> algorithms, using off-screen buffers, etc., will have a bigger effect
>> and can be done any time.)

[toc] | [prev] | [next] | [standalone]

#53572

"David Brown" <david.brown@hesbynett.no> wrote in message
news:m5947m$i1k$1@dont-email.me...
> On 28/11/14 01:55, BartC wrote:

> A golden rule is never to bother testing speed at -O0.  It's like trying
> to tune your car engine to go faster while restricting yourself to first
> gear.

I think you're wrong. And optimising isn't like tuning a car. Trying to
figure out bottlenecks using gcc -03 is a waste of time.

For example, look at an earlier thread of the OP's, where the optimisation
effort was aimed at some FP code in a specific function. Why that function?
Because if all that FP code was commented out, and the function returned a
constant, then the app was 3 times faster.

Wrong! Because gcc -O3 was smart enough to see that the complex calculations
needed for the arguments to that function were no longer needed, so it
suppressed them! You can't play around with adding or removing bits of code,
because you've got no idea what gcc -O3  will get up to.

And if you have a blocks of code A; B; C; where the compiler can see that B
is not needed, then while it can be good that it only compiles it as A; C;,
it would be far better if programmers found that out themselves. Then with
A; C; it can be possible to spot further reductions that the compiler can't.

Also, on the simple micro-benchmarks I use, gcc -O3 generally eliminates
them completely! It can in fact require considerable ingenuity to fool the
compiler into thinking the benchmark does something useful and necessary,
but even then you can't be certain that it hasn't taken some short-cuts and 
therefore is giving misleading results.

Actually, you can take an algorithm of any complexity, that might take
minutes or hours to run, but if you remove the printf at the end to show the
result, then gcc -O3 will give you a runtime of 0 seconds. Great, that's one
easy way of optimising it! Obviously that's not what you want.

-- 
Bartc 

[toc] | [prev] | [next] | [standalone]

#53577

W dniu piątek, 28 listopada 2014 12:21:42 UTC+1 użytkownik Bart napisał:
> "David Brown" <david.brown@hesbynett.no> wrote in message
> news:m5947m$i1k$1@dont-email.me...
> > On 28/11/14 01:55, BartC wrote:
> 
> > A golden rule is never to bother testing speed at -O0.  It's like trying
> > to tune your car engine to go faster while restricting yourself to first
> > gear.
> 
> I think you're wrong. And optimising isn't like tuning a car. Trying to
> figure out bottlenecks using gcc -03 is a waste of time.
> 
> For example, look at an earlier thread of the OP's, where the optimisation
> effort was aimed at some FP code in a specific function. Why that function?
> Because if all that FP code was commented out, and the function returned a
> constant, then the app was 3 times faster.
> 
> Wrong! Because gcc -O3 was smart enough to see that the complex calculations
> needed for the arguments to that function were no longer needed, so it
> suppressed them! You can't play around with adding or removing bits of code,
> because you've got no idea what gcc -O3  will get up to.
> 
> And if you have a blocks of code A; B; C; where the compiler can see that B
> is not needed, then while it can be good that it only compiles it as A; C;,
> it would be far better if programmers found that out themselves. Then with
> A; C; it can be possible to spot further reductions that the compiler can't.
> 
> Also, on the simple micro-benchmarks I use, gcc -O3 generally eliminates
> them completely! It can in fact require considerable ingenuity to fool the
> compiler into thinking the benchmark does something useful and necessary,
> but even then you can't be certain that it hasn't taken some short-cuts and 
> therefore is giving misleading results.
> 
> Actually, you can take an algorithm of any complexity, that might take
> minutes or hours to run, but if you remove the printf at the end to show the
> result, then gcc -O3 will give you a runtime of 0 seconds. Great, that's one
> easy way of optimising it! Obviously that's not what you want.
> 
thats not true, in general is to better change and watch the physical final change,
 if i would want co copmile final with -o0 i would need to test -o0, but if i would compile final with -O3 i need to observe how behaves -O3 (in those my example it was just my mistake of wrong deduction (that returning 0 was offing the function body - it offed much more,
but taking care of such things make testing with -O3 still usable)

[toc] | [prev] | [next] | [standalone]

#53580

On 28/11/14 12:21, BartC wrote:
> "David Brown" <david.brown@hesbynett.no> wrote in message
> news:m5947m$i1k$1@dont-email.me...
>> On 28/11/14 01:55, BartC wrote:
> 
>> A golden rule is never to bother testing speed at -O0.  It's like trying
>> to tune your car engine to go faster while restricting yourself to first
>> gear.
> 
> I think you're wrong. And optimising isn't like tuning a car. Trying to
> figure out bottlenecks using gcc -03 is a waste of time.
> 
> For example, look at an earlier thread of the OP's, where the optimisation
> effort was aimed at some FP code in a specific function. Why that function?
> Because if all that FP code was commented out, and the function returned a
> constant, then the app was 3 times faster.
> 
> Wrong! Because gcc -O3 was smart enough to see that the complex
> calculations
> needed for the arguments to that function were no longer needed, so it
> suppressed them! You can't play around with adding or removing bits of
> code,
> because you've got no idea what gcc -O3  will get up to.

Of course you know what gcc -O3 is up to - it asks the compiler to put a
lot of effort into making the code as fast as possible, even if it makes
it significantly bigger (although because of caches, branch prediction,
and other cpu features, -O2 code or even -Os code can be faster -
tweaking flags can lead to measurable changes).

If you have code that can be eliminated or simplified, you want the
compiler to eliminate it or simplify it.  That is part of the job of an
optimising compiler - it lets you write code that is clear, flexible and
maintainable, and the compiler handles most of the micro-optimisations.

Profiling code to find the /real/ bottlenecks is not an easy job - there
are many techniques and tricks involved.  In a case like you are
describing, the usual method is to use a volatile write to store the
function arguments, ensuring that they are calculated.

But dropping down to -O0 just mixes a wide range of different
pessimatisations into the problem.  You have no idea whether the speed
changes you see are due to real code changes, or just poor code
generation when optimisations are disabled.  And you have no idea
whether all your work is of any use - or if you would have got the same
effect through a simple -O2 switch rather than hours of deep thought.

> 
> And if you have a blocks of code A; B; C; where the compiler can see that B
> is not needed, then while it can be good that it only compiles it as A; C;,
> it would be far better if programmers found that out themselves. Then with
> A; C; it can be possible to spot further reductions that the compiler
> can't.

If you want to get the best from your compiler, you need to learn to
work with it - and you need to learn how to get the best from it.  In
cases like this, very often it is a matter of making sure your functions
are "static" where possible, and limiting their interaction with other
code - if the compiler knows all about A, B, and C, then it can quite
happily see that by eliminating B it can then combine A and C.  And then
perhaps it can make use of inlining to improve the code, leading to
constant propagation and then more code elimination and strength
reduction.  The compiler can do the job /better/ than the programmer in
many cases - at least while the programmer is concerned about writing
clear and maintainable code.

> 
> Also, on the simple micro-benchmarks I use, gcc -O3 generally eliminates
> them completely! 

Great - then you have found the run-time actually required for the
problem at hand.  Alternatively, you haven't written proper benchmarks
that actually reflect the final code.  Usually the process is as simple
as reading the test function's input from a volatile variable, and
writing its output to a volatile variable.

> It can in fact require considerable ingenuity to fool the
> compiler into thinking the benchmark does something useful and necessary,
> but even then you can't be certain that it hasn't taken some short-cuts
> and therefore is giving misleading results.

Sometimes it takes a lot of effort to get such benchmarks right - but
that's usually a sign that they are not very realistic benchmarks.  In
many cases, a couple of "volatile" qualifiers is all you need.  And it
is typically more useful to spend a bit of effort and ingenuity here,
than waste it completely on nonsense "optimisations" that make no
difference to the real code when the compiler's optimisations are
enabled.  (Often such hand-optimisations are worse than useless, with
people trying to use "optimisation tips" that have long since been
outdated by modern compilers.)

> 
> Actually, you can take an algorithm of any complexity, that might take
> minutes or hours to run, but if you remove the printf at the end to show
> the
> result, then gcc -O3 will give you a runtime of 0 seconds. Great, that's
> one
> easy way of optimising it! Obviously that's not what you want.
> 

[toc] | [prev] | [next] | [standalone]

#53581

"David Brown" <david.brown@hesbynett.no> wrote in message
news:m59rgr$rkh$1@dont-email.me...
> On 28/11/14 12:21, BartC wrote:

>> because you've got no idea what gcc -O3  will get up to.
>
> Of course you know what gcc -O3 is up to - it asks the compiler to put a
> lot of effort into making the code as fast as possible, even if it makes
> it significantly bigger (although because of caches, branch prediction,
> and other cpu features, -O2 code or even -Os code can be faster -
> tweaking flags can lead to measurable changes).
>
> If you have code that can be eliminated or simplified, you want the
> compiler to eliminate it or simplify it.  That is part of the job of an
> optimising compiler - it lets you write code that is clear, flexible and
> maintainable, and the compiler handles most of the micro-optimisations.

No, gcc -O3 is the equivalent of viewing code through rose-tinted specs. For
example, I've had code generators producing atrocious-looking C code with
far too many unnecessary temporary assignments, gotos everywhere, a right
mess. Yet when compiled with gcc -O3  it was just as fast as perfectly
written C!

Compiled with no optimisation, there would likely have been a performance
penalty which would have required those issues to be addressed.

You're arguing that it doesn't matter how bad the code is, or how
unnecessary or  long-winded it is, provided the compiler can somehow sort
out the essence of what it's trying to do. Maybe in some cases it can do
that; in others it can't. Or the code initially compiles fine, until it's
extended then it doesn't work as well because no-one ever bothered to attend
to the original code properly as it seemed to run fine.

(For a real example, see the OP's first post in the 'how to optymize this'
thread, 16-Nov-2014. That dimColor() had a lot of potential to be
simplified, but because gcc -O3 cut right through all that code and gave
good results anyway, that opportunity would have been passed over.)

> But dropping down to -O0 just mixes a wide range of different
> pessimatisations into the problem.  You have no idea whether the speed
> changes you see are due to real code changes, or just poor code
> generation when optimisations are disabled.  And you have no idea
> whether all your work is of any use - or if you would have got the same
> effect through a simple -O2 switch rather than hours of deep thought.

You wouldn't spend hours, that's the point of quickly testing different
fragments of code, often in a simple loop, a process which gcc -O3 renders
next to impossible.

In the past I've spent a lot of time comparing how my fast the code is from
my code generator, to that produced by gcc -O3. But because gcc likes to
optimise by eliminating code, I simply end up comparing how long my code
takes to do something, with how long gcc takes *not* to do it! I considered
that 'cheating'.

(Actually now when I need to benchmark something, I often do that by running
it on my own compiler. That only has a simple optimiser but which can 
usually be relied on to execute the code it's told to execute (and which 
might be what I'm trying to measure!). Something you can't rely on with 
gcc -O3 which tends to throw out the baby with the bathwater. While using 
gcc -O0 might generate poor code which is not typical of what is going to be 
in the production code which will use -O2 or -O3.)

-- 
Bartc 

[toc] | [prev] | [next] | [standalone]

#53587

On 28/11/14 14:46, BartC wrote:
> "David Brown" <david.brown@hesbynett.no> wrote in message 
> news:m59rgr$rkh$1@dont-email.me...
>> On 28/11/14 12:21, BartC wrote:
> 
>>> because you've got no idea what gcc -O3  will get up to.
>> 
>> Of course you know what gcc -O3 is up to - it asks the compiler to
>> put a lot of effort into making the code as fast as possible, even
>> if it makes it significantly bigger (although because of caches,
>> branch prediction, and other cpu features, -O2 code or even -Os
>> code can be faster - tweaking flags can lead to measurable
>> changes).
>> 
>> If you have code that can be eliminated or simplified, you want
>> the compiler to eliminate it or simplify it.  That is part of the
>> job of an optimising compiler - it lets you write code that is
>> clear, flexible and maintainable, and the compiler handles most of
>> the micro-optimisations.
> 
> No, gcc -O3 is the equivalent of viewing code through rose-tinted
> specs. For example, I've had code generators producing
> atrocious-looking C code with far too many unnecessary temporary
> assignments, gotos everywhere, a right mess. Yet when compiled with
> gcc -O3  it was just as fast as perfectly written C!
> 
> Compiled with no optimisation, there would likely have been a
> performance penalty which would have required those issues to be
> addressed.

I really don't understand your problem here.  It doesn't matter how
"optimal" the source code is, if the generated result is the same thanks
to the compiler's optimiser.  I want to write my source code in the
clearest way I can, and let the optimiser turn it into the best object
code.  If I were writing a code generator, I would want to generate the
most convenient code using the simplest algorithms and let the C
compiler turn it into great object code - what is the point in spending
time and effort writing (and testing and debugging) a complex code
generator to produce neat or elegant C code, when I could rely on the
tried and tested optimisation from gcc?

> 
> You're arguing that it doesn't matter how bad the code is, or how 
> unnecessary or  long-winded it is, provided the compiler can somehow
> sort out the essence of what it's trying to do. Maybe in some cases
> it can do that; in others it can't. Or the code initially compiles
> fine, until it's extended then it doesn't work as well because no-one
> ever bothered to attend to the original code properly as it seemed to
> run fine.

Yes, I am arguing that from the performance viewpoint, it doesn't matter
how bad the code is if the compiler can generate good results from it.
That means you can concentrate on other aspects of the code rather than
micro-optimising it - you can write code that is clear, flexible, and
maintainable.  Or if it is from a code generator, you can make your code
generator as clear as possible without worrying about the speed of the
generated C code.

To take a very simple example, suppose I want a function that divides an
integer by 13 - and I want that code to run as fast as possible.  The
simple, clear way is this:

int foo(int x) { return x / 13; }

Maybe I would want to allow for some future flexibility:

static const int fooDiv = 13;
int foo(int x) { return x / fooDiv; }

Compiled (by gcc 4.9 on 64-bit Linux) with -O0 gives:

  11              	foo:
  12              	.LFB0:
  13              		.cfi_startproc
  14 0000 55       		pushq	%rbp
  15              		.cfi_def_cfa_offset 16
  16              		.cfi_offset 6, -16
  17 0001 4889E5   		movq	%rsp, %rbp
  18              		.cfi_def_cfa_register 6
  19 0004 897DFC   		movl	%edi, -4(%rbp)
  20 0007 B90D0000 		movl	$13, %ecx
  20      00
  21 000c 8B45FC   		movl	-4(%rbp), %eax
  22 000f 99       		cltd
  23 0010 F7F9     		idivl	%ecx
  24 0012 5D       		popq	%rbp
  25              		.cfi_def_cfa 7, 8
  26 0013 C3       		ret


The work is done by the slow "idivl" instruction.

Compiled with -O1 or above gives:


   5              	foo:
   6              	.LFB16:
   7              		.cfi_startproc
   8 0000 BA4FECC4 		movl	$1321528399, %edx
   8      4E
   9 0005 89F8     		movl	%edi, %eax
  10 0007 F7EA     		imull	%edx
  11 0009 C1FA02   		sarl	$2, %edx
  12 000c C1FF1F   		sarl	$31, %edi
  13 000f 89D0     		movl	%edx, %eax
  14 0011 29F8     		subl	%edi, %eax
  15 0013 C3       		ret


The division is now handled by much faster instructions (a multiply and
some shifts).


It is completely and utterly pointless to spend time and effort trying
to figure out the right C code to replace "x / 13" with a multiplication
and shifts.  It would be time consuming, error-prone, and need
re-written if "fooDiv" were ever changed to a different value than 13.
So rather than "hand optimising" the C code so that it uses faster
instructions with -O0, I let the compiler do its job and enable the
optimiser.


I am in no way claiming that gcc's optimisers are perfect, or can turn
any old source code into fast object code.  But they are pretty good,
and you should let them do their job so that you can put your effort
into the rest of the code.

> 
> (For a real example, see the OP's first post in the 'how to optymize
> this' thread, 16-Nov-2014. That dimColor() had a lot of potential to
> be simplified, but because gcc -O3 cut right through all that code
> and gave good results anyway, that opportunity would have been passed
> over.)

Compilers are unlikely to be able to transform floating point code into
scaled integer code, since it is extremely difficult to guarantee
identical results - but "-O2 --fast-math" certainly improves the
generated code significantly over "-O0".  (With --fast-math, gcc can
re-arrange floating point expressions and thus bring out the common
factor of "f * 0.3 + 0.7".)

And if the result (with -O2 or -O3) is good enough, then it is far
/better/ to have the source code written in a way that makes sense to
the programmer (using floating point or whatever) than to write
something that is hard to understand just to get faster results at -O0.

There is still scope for macro optimisations, such as algorithmic
changes (in this case, converting to scaled integers rather than
floats).  But let the compiler handle the details of the micro
optimisations.

> 
>> But dropping down to -O0 just mixes a wide range of different 
>> pessimatisations into the problem.  You have no idea whether the
>> speed changes you see are due to real code changes, or just poor
>> code generation when optimisations are disabled.  And you have no
>> idea whether all your work is of any use - or if you would have got
>> the same effect through a simple -O2 switch rather than hours of
>> deep thought.
> 
> You wouldn't spend hours, that's the point of quickly testing
> different fragments of code, often in a simple loop, a process which
> gcc -O3 renders next to impossible.
> 
> In the past I've spent a lot of time comparing how my fast the code
> is from my code generator, to that produced by gcc -O3. But because
> gcc likes to optimise by eliminating code, I simply end up comparing
> how long my code takes to do something, with how long gcc takes *not*
> to do it! I considered that 'cheating'.

If your code does nothing, then gcc is right in generating nothing.

> 
> (Actually now when I need to benchmark something, I often do that by 
> running it on my own compiler. That only has a simple optimiser but
> which can usually be relied on to execute the code it's told to
> execute (and which might be what I'm trying to measure!). Something
> you can't rely on with gcc -O3 which tends to throw out the baby with
> the bathwater. While using gcc -O0 might generate poor code which is
> not typical of what is going to be in the production code which will
> use -O2 or -O3.)
> 

Baring bugs in the compiler, gcc (and any other compiler) will always
generate code that does what it is told.  But with higher optimisation
levels, you have to be more careful that your C code really says what
you think it says.  If the code has different results under different
optimisation levels (other than speed and size differences), then your
code is wrong.

Benchmarking code that is not realistic for the final results, is
pointless.  Benchmarking code that is intentionally poor, is pointless.
 Massaging your source code in order to improve only non-optimised code
generation is pointless.

[toc] | [prev] | [next] | [standalone]

#53588

W dniu piątek, 28 listopada 2014 16:25:48 UTC+1 użytkownik David Brown napisał:
> On 28/11/14 14:46, BartC wrote:
> > "David Brown" <david.brown@hesbynett.no> wrote in message 
> > news:m59rgr$rkh$1@dont-email.me...
> >> On 28/11/14 12:21, BartC wrote:
> > 
> >>> because you've got no idea what gcc -O3  will get up to.
> >> 
> >> Of course you know what gcc -O3 is up to - it asks the compiler to
> >> put a lot of effort into making the code as fast as possible, even
> >> if it makes it significantly bigger (although because of caches,
> >> branch prediction, and other cpu features, -O2 code or even -Os
> >> code can be faster - tweaking flags can lead to measurable
> >> changes).
> >> 
> >> If you have code that can be eliminated or simplified, you want
> >> the compiler to eliminate it or simplify it.  That is part of the
> >> job of an optimising compiler - it lets you write code that is
> >> clear, flexible and maintainable, and the compiler handles most of
> >> the micro-optimisations.
> > 
> > No, gcc -O3 is the equivalent of viewing code through rose-tinted
> > specs. For example, I've had code generators producing
> > atrocious-looking C code with far too many unnecessary temporary
> > assignments, gotos everywhere, a right mess. Yet when compiled with
> > gcc -O3  it was just as fast as perfectly written C!
> > 
> > Compiled with no optimisation, there would likely have been a
> > performance penalty which would have required those issues to be
> > addressed.
> 
> I really don't understand your problem here.  It doesn't matter how
> "optimal" the source code is, if the generated result is the same thanks
> to the compiler's optimiser.  I want to write my source code in the
> clearest way I can, and let the optimiser turn it into the best object
> code.  If I were writing a code generator, I would want to generate the
> most convenient code using the simplest algorithms and let the C
> compiler turn it into great object code - what is the point in spending
> time and effort writing (and testing and debugging) a complex code
> generator to produce neat or elegant C code, when I could rely on the
> tried and tested optimisation from gcc?
> 
if you mean that optymizer is working sufficiently good i may say that it is 
not the case of my experience - hand way of changing testing and repeating 
for me prove to gave quite noticable improvement
(my initial approach to rendering those textured dome at start began with 100-150 ms (with standard sin() wich is killingly slow -O3 seemed to not repair that), then through tabelarising it i go through 30 ms, 25 ms, 20 ms, then bow i gor 6-10 ms
(still twice to much to be happy

on optymised inner loop small changes make big differencies

for example
changing this which is 9ms frame
   int xc = CastToInt(512 + dir.x*511.5);
   int yc = CastToInt(512 + dir.y*511.5);
    color=  working_buffer[yc*working_buffer_size_x + xc];

into 
     int xc = 512 + CastToInt ( dir.x*511.5 );
     int yc = 512 + CastToInt ( dir.y*511.5 );
    color=  working_buffer[yc*working_buffer_size_x + xc];

made 7 ms frame then into

     int ycc =  512*((working_buffer_size_x+1)) + 512*(CastToInt_ ( (dir.y*working_buffer_size_x + dir.x)));

working_buffer[ycc];

(or something like that as i tested it before and changed the line not sure if exactly this)

made 5ms (though this last one is giving incorrect results - but only tested for speed)

if i would rely on -O3 i would have 100 ms instead of 10 ms
(still i almost sure it can be bring 
down to 4-5 ms which would be the final right result but that consumes time)

[toc] | [prev] | [next] | [standalone]

#53601

On 28/11/14 17:18, fir wrote:
> W dniu piątek, 28 listopada 2014 16:25:48 UTC+1 użytkownik David Brown napisał:
>> On 28/11/14 14:46, BartC wrote:
>>> "David Brown" <david.brown@hesbynett.no> wrote in message 
>>> news:m59rgr$rkh$1@dont-email.me...
>>>> On 28/11/14 12:21, BartC wrote:
>>>
>>>>> because you've got no idea what gcc -O3  will get up to.
>>>>
>>>> Of course you know what gcc -O3 is up to - it asks the compiler to
>>>> put a lot of effort into making the code as fast as possible, even
>>>> if it makes it significantly bigger (although because of caches,
>>>> branch prediction, and other cpu features, -O2 code or even -Os
>>>> code can be faster - tweaking flags can lead to measurable
>>>> changes).
>>>>
>>>> If you have code that can be eliminated or simplified, you want
>>>> the compiler to eliminate it or simplify it.  That is part of the
>>>> job of an optimising compiler - it lets you write code that is
>>>> clear, flexible and maintainable, and the compiler handles most of
>>>> the micro-optimisations.
>>>
>>> No, gcc -O3 is the equivalent of viewing code through rose-tinted
>>> specs. For example, I've had code generators producing
>>> atrocious-looking C code with far too many unnecessary temporary
>>> assignments, gotos everywhere, a right mess. Yet when compiled with
>>> gcc -O3  it was just as fast as perfectly written C!
>>>
>>> Compiled with no optimisation, there would likely have been a
>>> performance penalty which would have required those issues to be
>>> addressed.
>>
>> I really don't understand your problem here.  It doesn't matter how
>> "optimal" the source code is, if the generated result is the same thanks
>> to the compiler's optimiser.  I want to write my source code in the
>> clearest way I can, and let the optimiser turn it into the best object
>> code.  If I were writing a code generator, I would want to generate the
>> most convenient code using the simplest algorithms and let the C
>> compiler turn it into great object code - what is the point in spending
>> time and effort writing (and testing and debugging) a complex code
>> generator to produce neat or elegant C code, when I could rely on the
>> tried and tested optimisation from gcc?
>>
> if you mean that optymizer is working sufficiently good i may say that it is 
> not the case of my experience - hand way of changing testing and repeating 
> for me prove to gave quite noticable improvement
> (my initial approach to rendering those textured dome at start began with 100-150 ms (with standard sin() wich is killingly slow -O3 seemed to not repair that), then through tabelarising it i go through 30 ms, 25 ms, 20 ms, then bow i gor 6-10 ms
> (still twice to much to be happy
> 
> on optymised inner loop small changes make big differencies
> 
> for example
> changing this which is 9ms frame
>    int xc = CastToInt(512 + dir.x*511.5);
>    int yc = CastToInt(512 + dir.y*511.5);
>     color=  working_buffer[yc*working_buffer_size_x + xc];
> 
> into 
>      int xc = 512 + CastToInt ( dir.x*511.5 );
>      int yc = 512 + CastToInt ( dir.y*511.5 );
>     color=  working_buffer[yc*working_buffer_size_x + xc];
> 
> made 7 ms frame then into
> 
>      int ycc =  512*((working_buffer_size_x+1)) + 512*(CastToInt_ ( (dir.y*working_buffer_size_x + dir.x)));
> 
> working_buffer[ycc];
> 
> (or something like that as i tested it before and changed the line not sure if exactly this)
> 
> made 5ms (though this last one is giving incorrect results - but only tested for speed)
> 
> if i would rely on -O3 i would have 100 ms instead of 10 ms
> (still i almost sure it can be bring 
> down to 4-5 ms which would be the final right result but that consumes time)
> 

It is difficult to help you when you can't read a post, and don't
understand optimisation.  But I'll try to write the same thing again,
with slightly different words.

The compiler is not allowed to change the results of the code when you
change the optimisation flags.

("-ffast-math" is different - although it's primary use is to increase
speed, it also changes some of the code's behaviour by allowing rougher
floating point behaviour.)

So there are no compiler optimisation flags that will change floating
point arithmetic into integer arithmetic.  If you want to do that, you
must do it yourself.

The compiler's optimiser will do its best to improve the code without
changing the effect of the code or the results.

[toc] | [prev] | [next] | [standalone]

#53592

On Friday, November 28, 2014 3:25:48 PM UTC, David Brown wrote:
>
> It is completely and utterly pointless to spend time and effort trying
> to figure out the right C code to replace "x / 13" with a multiplication
> and shifts.  It would be time consuming, error-prone, and need
> re-written if "fooDiv" were ever changed to a different value than 13.
>
if we've got a #define for fooDiv, that implies that it's an arbitrary parameter
of some sort. Maybe we've got 50-100 reals 1-100, and we want a nice
number of bins to hold the distribution.
Now, let's say that the / 13 is the bottleneck in this particular code, which
makes sense because we're even discussing optimisation.

You know and I know that if we replace 13 by 16, we can have a >>= 4
instruction, which is very likely to be faster. But does the newbie programmer
know that? if he backcracks, the optimisation will become clear.  

[toc] | [prev] | [next] | [standalone]

#53602

On 28/11/14 17:54, Malcolm McLean wrote:
> On Friday, November 28, 2014 3:25:48 PM UTC, David Brown wrote:
>>
>> It is completely and utterly pointless to spend time and effort trying
>> to figure out the right C code to replace "x / 13" with a multiplication
>> and shifts.  It would be time consuming, error-prone, and need
>> re-written if "fooDiv" were ever changed to a different value than 13.
>>
> if we've got a #define for fooDiv, that implies that it's an arbitrary parameter
> of some sort. Maybe we've got 50-100 reals 1-100, and we want a nice
> number of bins to hold the distribution.
> Now, let's say that the / 13 is the bottleneck in this particular code, which
> makes sense because we're even discussing optimisation.
> 
> You know and I know that if we replace 13 by 16, we can have a >>= 4
> instruction, which is very likely to be faster. But does the newbie programmer
> know that? if he backcracks, the optimisation will become clear.  
> 

Dividing by 16 is easier and faster for the compiler than dividing by 13
- but that won't help if you want to divide by 13, or perhaps change
fooDiv to 17 instead.

The point is that the /compiler/ will handle all this.  You give it your
source code in a simple and clear manner.  You write it the same way,
whether you are dividing by 13, 16, or anything else.  It is the
/compiler's/ job to turn it into efficient object code.

As a programmer, you can then test the resulting code and see if you are
satisfied with it.  If it is too slow, you can go back to the code and
make /algorithmic/ and /macro/ changes - such as making fooDiv into a
number that is easier for division, as long as that is correct for the
program.

I expect that any programmer who is capable of "hand-optimising" a
division into a multiplication knows that dividing by 16 is easier than
dividing by 13.

[toc] | [prev] | [next] | [standalone]

#53604

On Friday, November 28, 2014 7:22:41 PM UTC, David Brown wrote:
> On 28/11/14 17:54, Malcolm McLean wrote:
>
> I expect that any programmer who is capable of "hand-optimising" a
> division into a multiplication knows that dividing by 16 is easier than
> dividing by 13.
>
Sure. But if no-one backcracks multiply and divides any longer, 
on the basis that the compiler does all that for you, eventually
the knowledge will be lost.

[toc] | [prev] | [next] | [standalone]

#53609

On 2014-11-28, David Brown <david.brown@hesbynett.no> wrote:
> I expect that any programmer who is capable of "hand-optimising" a
> division into a multiplication knows that dividing by 16 is easier than
> dividing by 13.

A programmer who *doesn't* know that / 13 can be turned into a multiplication
thinks that dividing by 13 is an utter disaster compared to 16. :)

[toc] | [prev] | [next] | [standalone]

#53611

On 28/11/14 20:51, Kaz Kylheku wrote:
> On 2014-11-28, David Brown <david.brown@hesbynett.no> wrote:
>> I expect that any programmer who is capable of "hand-optimising" a
>> division into a multiplication knows that dividing by 16 is easier than
>> dividing by 13.
> 
> A programmer who *doesn't* know that / 13 can be turned into a multiplication
> thinks that dividing by 13 is an utter disaster compared to 16. :)
> 

Indeed.

And on some systems, dividing by 13 is still a disaster because the
multiplication and shifts needed are slow.

[toc] | [prev] | [next] | [standalone]

#53613

On Fri, 28 Nov 2014 19:51:39 +0000 (UTC)
Kaz Kylheku <kaz@kylheku.com> wrote:

> On 2014-11-28, David Brown <david.brown@hesbynett.no> wrote:
> > I expect that any programmer who is capable of "hand-optimising" a
> > division into a multiplication knows that dividing by 16 is easier
> > than dividing by 13.
> 
> A programmer who *doesn't* know that / 13 can be turned into a
> multiplication thinks that dividing by 13 is an utter disaster
> compared to 16. :)

Heh, compilers do that for us ;)
I just look into generated constant and that's it ...
What surprised me is that Java doesn't do division
by multiplication even when it performs pretty advanced
optimization's. 
gcc does integer division by multiplication, but it does not
do that for floats. So eg if one writes x/13.5 it will
generate division instruction , which is much slower than x*(1.0/13.5).

[toc] | [prev] | [next] | [standalone]

#53616

On 2014-11-28, Melzzzzz <mel@zzzzz.com> wrote:
> gcc does integer division by multiplication, but it does not
> do that for floats.

With good reason: it wouldn't be equivalent in terms of the result,
and other considerations, like perhaps the exact ranges of inputs under which
an overflow would occur.

However, GCC has an option for looser floating-point math: -ffast-math. Try
that; see if it still refuses.

[toc] | [prev] | [next] | [standalone]

#53618

On Fri, 28 Nov 2014 20:11:25 +0000 (UTC)
Kaz Kylheku <kaz@kylheku.com> wrote:

> On 2014-11-28, Melzzzzz <mel@zzzzz.com> wrote:
> > gcc does integer division by multiplication, but it does not
> > do that for floats.
> 
> With good reason: it wouldn't be equivalent in terms of the result,
> and other considerations, like perhaps the exact ranges of inputs
> under which an overflow would occur.
> 
> However, GCC has an option for looser floating-point math:
> -ffast-math. Try that; see if it still refuses.

You are right! I compiled with -O3 and gcc generates divsd, but
with -Ofast it generates mulsd ;)
So -Ofast (and -ffast-math particularly) is for inaccurate
optimizations.

[toc] | [prev] | [next] | [standalone]

Page 2 of 4 — ← Prev page 1 [2] 3 4  Next page →

Back to top | Article view | comp.lang.c

csiph-web