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 3 of 4 — ← Prev page 1 2 [3] 4  Next page →

#53614

"David Brown" <david.brown@hesbynett.no> wrote in message 
news:m5ai1a$mqi$1@dont-email.me...
> On 28/11/14 17:54, Malcolm McLean wrote:

>> 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.

> 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.

They will need to find out if it's a bottleneck first.

-- 
Bartc 

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

#53594

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

>> No, gcc -O3 is the equivalent of viewing code through rose-tinted
>> specs.

> I really don't understand your problem here.

OK, so would you approach the issues the OP is having?

If that involves finding out what is taking the most time, or experimenting
with different approaches, then gcc -O0 is a tool that will let you measure 
the differences, and not produce distorted, unrealistic results.

For example, you have this sequence of code:

 A;
 B;
 C;

Which part takes the most time? Well, you might try commenting out one
section at a time:

 A;
 B;
 //C;

This is much faster (the same example I gave earlier), but with -O3, it
might be that B does something that is only relevant to C, so the the
compiler doesn't do B either. Or you duplicate one bit of code to see how
much slower it becomes:

 A;
 B;
 B;
 C;

(assuming this doesn't affect the working). Now again, -O3 might decide the
first B doesn't do anything useful and suppress it. Not exactly useful:
instead of concerning itself with localised optimisations, -O3 is doing much
more, but you don't know exactly what.

(BTW what is the -O0 option actually for?)

>  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,

> 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?

(In my case, so that I have the satisfaction that if my code performs well,
then it will be largely thanks to my efforts than because of the C compiler. 
In fact I now generate x64 code directly. This also means that if:

  a = f*x+f*y;

isn't automatically optimised to a = (x+y)*f, then I would be forced to make
that change myself, which makes the code more readable *and* faster. But
using gcc -O3, there would be no incentive, as that change is done
internally; the code is just as fast, but is not as readable.)

> 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; }
<snip>.
> 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.

That's not what I'm getting at. Suppose I wanted to find out how fast that 
routine was, or how it compares with another that does it a little 
differently.

If I did something as straightforward as calling foo() twice, the -O3 will
eliminate the first call if it's not needed (I've just tried it).

It happens that sometimes you want to a measure a bit of code compiled 
with -O3, or compare with something else, then simply switching to -O0 won't 
work. Then it becomes harder (because you want to apply -O3 to the code
being measured, but don't want the simple test harness to be optimised out 
of existence).

-- 
Bartc 

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

#53610

On 28/11/14 18:14, BartC wrote:
> "David Brown" <david.brown@hesbynett.no> wrote in message
> news:m5a455$tf3$1@dont-email.me...
>> On 28/11/14 14:46, BartC wrote:
> 
>>> No, gcc -O3 is the equivalent of viewing code through rose-tinted
>>> specs.
> 
>> I really don't understand your problem here.
> 
> OK, so would you approach the issues the OP is having?
> 
> If that involves finding out what is taking the most time, or experimenting
> with different approaches, then gcc -O0 is a tool that will let you
> measure the differences, and not produce distorted, unrealistic results.

"gcc -O0" /always/ produces distorted, unrealistic results.

Depending on the type of profiling he plans to use, it is quite possible
that he will find it easier with -O1 than with -O2 or -O3, but that's
okay to start with - you get the biggest jump from 0 to 1.

The first step when improving speed is to make sure you are getting good
measurements on realistic samples.  Make sure it is working properly
with -O2 (-O3 seldom helps significantly, and sometimes makes code
slower because it is bigger - but it might be worth trying).  If you
don't need very accurate floating point, use -ffast-math.

You also need to be very sure that you are compiling with appropriate
"cpu" and "tune" flags, based on your target processors.  You are not
going to get very good results if your compiler is limited to 386 + 387
instruction sets.  I have mentioned this several times, and seen
absolutely /no/ acknowledgement or consideration of the issue (from
"fir" or anyone else here).

And of course you should compile with a generous helping of warnings
(-Wall -Wextra to start with), to help spot errors or mistakes in the code.

This gives you your base timings, with a solid base for optimisation,
and now you can start looking in detail for the bottlenecks.  You might
do this using a profiler tool - alternatively, you disable selected
parts of the code by replacing them with reads and writes of volatile
variables so that the rest of the code still runs.

When you have figured out the part of the code that is really the
problem, you can start to work on it.  Mostly you will be looking at
algorithmic or macro changes, such as (in this case) writing to an
off-screen bitmap and then transferring all the pixels in one system
call, rather than system calls for each pixel.  Using lookup tables for
sins is another such change, as would be changing floating point to
integer, or using vector processing.

If you really need to get the best from small code sections inside a
loop, then you may also want to examine the generated assembly code and
play with more detailed compiler optimisation settings (such as forcing
loop unrolling or autovectorisation).

At no point does gcc -O0 help.

> 
> For example, you have this sequence of code:
> 
> A;
> B;
> C;
> 
> Which part takes the most time? Well, you might try commenting out one
> section at a time:
> 
> A;
> B;
> //C;
> 
> This is much faster (the same example I gave earlier), but with -O3, it
> might be that B does something that is only relevant to C, so the the
> compiler doesn't do B either. Or you duplicate one bit of code to see how
> much slower it becomes:
> 
> A;
> B;
> B;
> C;
> 
> (assuming this doesn't affect the working). Now again, -O3 might decide the
> first B doesn't do anything useful and suppress it. Not exactly useful:
> instead of concerning itself with localised optimisations, -O3 is doing
> much
> more, but you don't know exactly what.
> 

When you have this :

x = A(w);
y = B(x);
z = C(y);

you change it to:

x = A(w);
y = B(x);
volatile v = y;

That skips C without letting the compiler skip B or A.

Similarly,

x = A(w);
volatile vx = x;
y = B(x);
volatile yy = y;
x = vx;
y = B(x);
z = C(y);

will let you do B twice.

This is not hard - and I believe I have suggested "volatile" multiple
times in these posts.

(If you prefer, you can replace volatile access with things like printf.)

> (BTW what is the -O0 option actually for?)

gcc -O0 used to be helpful with old, slow computers, as it is much
faster than when optimisation is enabled.  I can't really think of any
use these days.

It is common enough to prefer -O1 to -O2, since -O1 does less
re-arranging of your code, and can make debugging easier (when stepping
through the code, there will be less unexpected jumps, and breakpoints
are usually in the spot you expect them).  Compiling with -O1 can often
make the code several times faster than -O0, and does not take much
longer to compile.  Changing to -O2 (or -O3) seldom makes as big a
difference as going from -O0 to -O1.  And from -O1 upwards, you get
better static error checking than -O0.

> 
>>  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,
> 
>> 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?
> 
> (In my case, so that I have the satisfaction that if my code performs well,
> then it will be largely thanks to my efforts than because of the C
> compiler. In fact I now generate x64 code directly. This also means that
> if:
> 
>  a = f*x+f*y;
> 
> isn't automatically optimised to a = (x+y)*f, then I would be forced to
> make
> that change myself, which makes the code more readable *and* faster. But
> using gcc -O3, there would be no incentive, as that change is done
> internally; the code is just as fast, but is not as readable.)

If you want to generate better code, and it gives you a warm fuzzy
feeling, then there is no problem with that.  Be careful not to try
/too/ hard - if you do things like convert multiplications to shifts or
array accesses to pointers, you will hinder the compiler's optimisations
and error checking.  But you would typically be better off spending your
time on other parts of the code.

Note that if you are talking about floating point, the compiler cannot
change "a = f * x + f * y" into "a = (x + y) * f", unless you have
"-ffast-math" on, since the results of these expressions are not equal.


> 
>> 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; }
> <snip>.
>> 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.
> 
> That's not what I'm getting at. Suppose I wanted to find out how fast
> that routine was, or how it compares with another that does it a little
> differently.

The point is, you cannot possibly find out how fast that routine is when
using -O0, because you are testing and timing slow and unrealistic code.
 And you can't tell how it compares to something a little different.

For example, by testing at -O0 you would conclude that changing fooDiv
to 16 would make no difference to the speed of the code.  But with -O1
or more, you would find that change made a /huge/ difference - and you
would know that the algorithmic change of fooDiv is worth doing
(assuming it did not affect the correctness of the program, of course).

If you are interested in writing fast code, you are not going to compile
the final version with -O0.  So there is no point in examining a -O0
version for speed bottlenecks, even if you think it is easier to do
speed checks with -O0 than -O2.  (It's like the guy who loses his car
keys in the dark, and searches for them under the lamppost where it is
easier to see, rather than in the dark spot where he dropped them.)

> 
> If I did something as straightforward as calling foo() twice, the -O3 will
> eliminate the first call if it's not needed (I've just tried it).
> 
> It happens that sometimes you want to a measure a bit of code compiled
> with -O3, or compare with something else, then simply switching to -O0
> won't work. Then it becomes harder (because you want to apply -O3 to the
> code
> being measured, but don't want the simple test harness to be optimised
> out of existence).
> 

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

#53617

"David Brown" <david.brown@hesbynett.no> wrote in message 
news:m5ajt5$ue1$1@dont-email.me...

> This is not hard - and I believe I have suggested "volatile" multiple
> times in these posts.
>
> (If you prefer, you can replace volatile access with things like printf.)
>
>> (BTW what is the -O0 option actually for?)

I haven't used volatile yet. But I don't think it is quite the same as 
printf.

If I execute a=b a billion times in a loop, then print the value of a, then 
gcc -O3 will only do the assignment once.

-- 
Bartc 

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

#53620

On 28/11/14 21:16, BartC wrote:
> "David Brown" <david.brown@hesbynett.no> wrote in message
> news:m5ajt5$ue1$1@dont-email.me...
> 
>> This is not hard - and I believe I have suggested "volatile" multiple
>> times in these posts.
>>
>> (If you prefer, you can replace volatile access with things like printf.)
>>
>>> (BTW what is the -O0 option actually for?)
> 
> I haven't used volatile yet. But I don't think it is quite the same as
> printf.
> 

No, volatile is not the same as printf!  But sometimes they can be used
to get the same effect.

A volatile access tells the compiler that the read or write must be
visible outside the program - thus when you read a volatile variable
three times, the compiler must generate code to read it three times.
And when you tell it to write something to a volatile variable, it has
to do so - and that means calculating the value that you ask to store.

Access to volatiles is considered to be something outside of what the
compiler can see - just like the output of a printf, or a system call.
So the compiler can't re-order volatiles (but it /can/ re-order other
code with respect to volatiles, just as it can with respect to printf or
system calls!).

> If I execute a=b a billion times in a loop, then print the value of a,
> then gcc -O3 will only do the assignment once.
> 

But if "a" is volatile, it will write it "a" billion times (but without
re-reading b).  Or if "b" is volatile, it will read it a billion times
(but only store the last value to "a").

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

#53551

W dniu piątek, 28 listopada 2014 01:56:56 UTC+1 użytkownik Bart napisał:
> "David Brown" <david.brown@hesbynett.no> wrote in message
> news:m58d4p$o83$1@dont-email.me...
> > On 27/11/14 23:07, BartC wrote:
> 
> >>
> >> For each iteration, it will effectively add (head_x, head_y, head_z) to
> >> dir.
> >> So instead of the above, why not initialise dir in ...B. Then after the
> >> call
> >> to table_normalize(&dir), do:
> >>
> >>   dir.x += head.x;
> >>   dir.y += head.y;
> >>   dir.z += head.z;
> >>
> >> which saves a multiply (actually, three multiplies).
> >>
> >
> > Doing this transformation is risky - you will build up rounding errors,
> > and lose precision.  Floating point does not work like "real" mathematics!
> 
> I think in this application, and for an inner loop of a thousand or so, it's
> probably not critical. (And 32-bits floats are used anyway which is already
> half the precision gone.)
> 
> (I have tested my idea, using floats and gcc -O0, and just that part of the
> loop the OP showed, but minus the sqrt calculation. My simplifications made
> it about 20% faster. It will be a tiny part of the whole app, but it all
> adds up.
> 
> Maybe gcc -O3 will do that job; maybe not.  Sometimes these simplications 
> in the source makes it easier to see where more pieces can come together and 
> more intermediate steps can be eliminated.
> 
> One note on that method: in the original, 'dir' is reset on each inner loop
> iteration. My way, because the scaling would modify it, the scaled version
> has to be created in a different 'dir'. 'dir' also needs to be initialised
> to ogon-head to avoid it being out of step, a consequence of the 0-based
> index.)
> 
mul to +=dx may be faster i think but not much (not tested yet), also float precission probably will suffice here, 

lets rethink it a bit

screen sizes are as screen sizes (4000x is a practical max i think so this is 23-12 = 11 bits lasting for 'subpixel' precision

if i count one bit of error after 4000 additions i should get error of 12 bits (?) it means 2 pixel range? comparing to the calculation in higher precision?

if all results in just streatching wiev by two pixels it is not to much important
worse it would be if it would be some fluctuations, but the fluctuations are probably not the case

not sure how addition would help to propagate this error compared to the multiply by i version (?)

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

#53552

W dniu piątek, 28 listopada 2014 08:37:26 UTC+1 użytkownik fir napisał:
> W dniu piątek, 28 listopada 2014 01:56:56 UTC+1 użytkownik Bart napisał:
> > "David Brown" <david.brown@hesbynett.no> wrote in message
> > news:m58d4p$o83$1@dont-email.me...
> > > On 27/11/14 23:07, BartC wrote:
> > 
> > >>
> > >> For each iteration, it will effectively add (head_x, head_y, head_z) to
> > >> dir.
> > >> So instead of the above, why not initialise dir in ...B. Then after the
> > >> call
> > >> to table_normalize(&dir), do:
> > >>
> > >>   dir.x += head.x;
> > >>   dir.y += head.y;
> > >>   dir.z += head.z;
> > >>
> > >> which saves a multiply (actually, three multiplies).
> > >>
> > >
> > > Doing this transformation is risky - you will build up rounding errors,
> > > and lose precision.  Floating point does not work like "real" mathematics!
> > 
> > I think in this application, and for an inner loop of a thousand or so, it's
> > probably not critical. (And 32-bits floats are used anyway which is already
> > half the precision gone.)
> > 
> > (I have tested my idea, using floats and gcc -O0, and just that part of the
> > loop the OP showed, but minus the sqrt calculation. My simplifications made
> > it about 20% faster. It will be a tiny part of the whole app, but it all
> > adds up.
> > 
> > Maybe gcc -O3 will do that job; maybe not.  Sometimes these simplications 
> > in the source makes it easier to see where more pieces can come together and 
> > more intermediate steps can be eliminated.
> > 
> > One note on that method: in the original, 'dir' is reset on each inner loop
> > iteration. My way, because the scaling would modify it, the scaled version
> > has to be created in a different 'dir'. 'dir' also needs to be initialised
> > to ogon-head to avoid it being out of step, a consequence of the 0-based
> > index.)
> > 
> mul to +=dx may be faster i think but not much (not tested yet), also float precission probably will suffice here, 
> 
> lets rethink it a bit
> 
> screen sizes are as screen sizes (4000x is a practical max i think so this is 23-12 = 11 bits lasting for 'subpixel' precision
> 
> if i count one bit of error after 4000 additions i should get error of 12 bits (?) it means 2 pixel range? comparing to the calculation in higher precision?
> 
> if all results in just streatching wiev by two pixels it is not to much important
> worse it would be if it would be some fluctuations, but the fluctuations are probably not the case
> 
> not sure how addition would help to propagate this error compared to the multiply by i version (?)

(add)

not sure but from this it seems to me that both addition and multiply provide the same error (of the length of multiplier, for i=4096 it would be 12 bits) 
the way to eliminate this error would be
to get correct values for left and right pixels then carefully do linear value between them not to lost bits), but in practice i do rough graphics and this one pixel stretch on 2000 pixels is not important to me

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

#53568

On 28/11/2014 07:37, fir wrote:
> W dniu piątek, 28 listopada 2014 01:56:56 UTC+1 użytkownik Bart napisał:

>>
>> I think in this application, and for an inner loop of a thousand or so, it's
>> probably not critical. (And 32-bits floats are used anyway which is already
>> half the precision gone.)

> lets rethink it a bit
>
> screen sizes are as screen sizes (4000x is a practical max i think so this is 23-12 = 11 bits lasting for 'subpixel' precision
>
> if i count one bit of error after 4000 additions i should get error of 12 bits (?) it means 2 pixel range? comparing to the calculation in higher precision?

If you start with 0.0, and add 0.1 4000 times, you'll get 400.015 
instead of 400.0 (multiplying seems to give an exact value, not sure 
why). While adding 0.3 4000 times gives 1199.9993 instead of 1200.0000. 
It depends on the numbers.

However if you start with 1000000.0 and add 0.1 4000 times, you'll get 
1000500.0 instead of 1000400.0.

So you do need be aware of this stuff.

-- 
Bartc

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

#53643

W dniu piątek, 28 listopada 2014 12:02:03 UTC+1 użytkownik Bart napisał:
> On 28/11/2014 07:37, fir wrote:
> > W dniu piątek, 28 listopada 2014 01:56:56 UTC+1 użytkownik Bart napisał:
> 
> >>
> >> I think in this application, and for an inner loop of a thousand or so, it's
> >> probably not critical. (And 32-bits floats are used anyway which is already
> >> half the precision gone.)
> 
> > lets rethink it a bit
> >
> > screen sizes are as screen sizes (4000x is a practical max i think so this is 23-12 = 11 bits lasting for 'subpixel' precision
> >
> > if i count one bit of error after 4000 additions i should get error of 12 bits (?) it means 2 pixel range? comparing to the calculation in higher precision?
> 
> If you start with 0.0, and add 0.1 4000 times, you'll get 400.015 
> instead of 400.0 (multiplying seems to give an exact value, not sure 
> why). While adding 0.3 4000 times gives 1199.9993 instead of 1200.0000. 
> It depends on the numbers.
> 
> However if you start with 1000000.0 and add 0.1 4000 times, you'll get 
> 1000500.0 instead of 1000400.0.
> 
> So you do need be aware of this stuff.
> 
Im also not sure how it works - but may say that it would be better to get know
one day

(as i say floats it self carry error even with no operations, here both (say its x*a or x+=da in loop) left and right sides carry an error (x-errror and a-error and da-error) could someone explain why adding brings the more final error than multiply? if it brings

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

#53644

On 11/29/14 1:52 AM, fir wrote:

> (as i say floats it self carry error even with no operations, here
> both (say its x*a or x+=da in loop) left and right sides carry an
> error (x-errror and a-error and da-error) could someone explain why
> adding brings the more final error than multiply? if it brings

Repeated addition multiplies any error by the number of additions, while 
multiplication error is one-time computational error.

-- 
Morris Dovey
http://www.iedu.com/Solar/

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

#53645

W dniu sobota, 29 listopada 2014 09:03:24 UTC+1 użytkownik Morris Dovey napisał:
> On 11/29/14 1:52 AM, fir wrote:
> 
> > (as i say floats it self carry error even with no operations, here
> > both (say its x*a or x+=da in loop) left and right sides carry an
> > error (x-errror and a-error and da-error) could someone explain why
> > adding brings the more final error than multiply? if it brings
> 
> Repeated addition multiplies any error by the number of additions, while 
> multiplication error is one-time computational error.
> 

probably only sometimes

(and probably not in this case mentioned) 
(not sure though)

say x is value represented on 23 bits
and has an error of 0.30 on its invisible (cutted) bits i mean x is a bit to low

multipliing it by 4000 would bring an undervalue of 4000*.3 it is 1200 (this is
quite big error of 11 bits) (if i am not mistaken) - but it is an starting error of unprecise storage not calculations

changing to +da will involve dividing x by 4000, this is exact on 23 bits and has
some undervalue on invisible bits (at least 0.3 but probably may be random more like 0.6 for example) - adding it will be probably exact acssing of 4000 undervalues of 0.6 so it will bring the different result than multiply but probably not worse than last (24) bit
- maybe it could turn 0.3 * 4000 undervalue into some other 0.x*4000 undervalue or some 0.x * 4000 overvalue 
if last bit of the da is rounded up

so (if my thinking here is good as it can have some hole) one under/over value 
in the case with multiply is changed into some other random last bit under/overvalue but it is all in the range of last (first invisible) bit

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

#53647

ps after all this thread proved to be some fail, as it was opened to get maybe some hints/talk abous some algorythmic improvements over the nanooptimistation (not nanooptymisations itself or other things) got no answer here - but this is
in some way understood as i cannot probably expect someone to get involved in special kind of procedure i am working on (not common language things), I also feel tired (afret two weeks of hard coding) so gor not so much energy
- but anyway thing is itself interesting 
(will back to it after some time, now i will leave it)

 

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

#53650

On 29/11/2014 11:12, fir wrote:
> ps after all this thread proved to be some fail, as it was opened to get maybe some hints/talk abous some algorythmic improvements over the nanooptimistation (not nanooptymisations itself or other things) got no answer here - but this is
> in some way understood as i cannot probably expect someone to get involved in special kind of procedure i am working on (not common language things), I also feel tired (afret two weeks of hard coding) so gor not so much energy
> - but anyway thing is itself interesting
> (will back to it after some time, now i will leave it)

You've only posted fragments of code, or the odd function, so it's 
difficult to suggest anything other than micro-optimisations.

And given a posted function, we're not in a position to be to be able, 
for example, to eliminate that function, or to eliminate that 
square-root opetation; we don't have the big picture.

How many floating point operations are done per pixel? You haven't told 
us. What *are* the entire set of floating point ops done? We don't know. 
(Pehaps if all written in one place, you can see a way of simplifying it.)

(Also the pixel-based processing you seem to be doing *is* slow. At 
higher resolutions I would start basing these things on scalable vector 
graphics, where the vertex/face calculations are less affected by output 
resolution (and the eventual pixel-processing needed is simpler). And 
where there are also existing libraries to help out.)


-- 
Bartc

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

#53651

W dniu sobota, 29 listopada 2014 13:10:17 UTC+1 użytkownik Bart napisał:
> On 29/11/2014 11:12, fir wrote:
> > ps after all this thread proved to be some fail, as it was opened to get maybe some hints/talk abous some algorythmic improvements over the nanooptimistation (not nanooptymisations itself or other things) got no answer here - but this is
> > in some way understood as i cannot probably expect someone to get involved in special kind of procedure i am working on (not common language things), I also feel tired (afret two weeks of hard coding) so gor not so much energy
> > - but anyway thing is itself interesting
> > (will back to it after some time, now i will leave it)
> 
> You've only posted fragments of code, or the odd function, so it's 
> difficult to suggest anything other than micro-optimisations.
> 
> And given a posted function, we're not in a position to be to be able, 
> for example, to eliminate that function, or to eliminate that 
> square-root opetation; we don't have the big picture.
> 
> How many floating point operations are done per pixel? You haven't told 
> us. What *are* the entire set of floating point ops done? We don't know. 
> (Pehaps if all written in one place, you can see a way of simplifying it.)
> 
> (Also the pixel-based processing you seem to be doing *is* slow. At 
> higher resolutions I would start basing these things on scalable vector 
> graphics, where the vertex/face calculations are less affected by output 
> resolution (and the eventual pixel-processing needed is simpler). And 
> where there are also existing libraries to help out.)
> 

I posted all, this is really whole code of the loop, - imo it is possible to say some hints for 'algorithmic' optimistation (imo that would be interpolation but not final color interpolation but probably something like texture coordinate interpolation (then i will not lost color information only very slight change in texture coordinate calculations) - but this is all quite hard and i personally got tired with this
(and working when overworked do not work in my case - i thhink i will leave it and may get back to it in december)

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

#53652

W dniu sobota, 29 listopada 2014 13:10:17 UTC+1 użytkownik Bart napisał:
> On 29/11/2014 11:12, fir wrote:
> > ps after all this thread proved to be some fail, as it was opened to get maybe some hints/talk abous some algorythmic improvements over the nanooptimistation (not nanooptymisations itself or other things) got no answer here - but this is
> > in some way understood as i cannot probably expect someone to get involved in special kind of procedure i am working on (not common language things), I also feel tired (afret two weeks of hard coding) so gor not so much energy
> > - but anyway thing is itself interesting
> > (will back to it after some time, now i will leave it)
> 
> You've only posted fragments of code, or the odd function, so it's 
> difficult to suggest anything other than micro-optimisations.
> 
> And given a posted function, we're not in a position to be to be able, 
> for example, to eliminate that function, or to eliminate that 
> square-root opetation; we don't have the big picture.
> 
> How many floating point operations are done per pixel? You haven't told 
> us. What *are* the entire set of floating point ops done? We don't know. 
> (Pehaps if all written in one place, you can see a way of simplifying it.)
> 
> (Also the pixel-based processing you seem to be doing *is* slow. At 
> higher resolutions I would start basing these things on scalable vector 
> graphics, where the vertex/face calculations are less affected by output 
> resolution (and the eventual pixel-processing needed is simpler). And 
> where there are also existing libraries to help out.)
> 
what do you mean scalable vector graphics? you mean something lice corel draw?

from my experience cpu graphics for medium (say 1024x786) or larger resolutions is not quite obtainable 
or just not obtainable - i cannot make even any simpler things work fluid when simple clear_frame() takes 8-10-20 ms
(this seem to be linear (or even a bit worse than linear) slowdown 
usually in higres frame takes just 4x-6x-8x-10x times worse), that is pain

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

#53658

On 29/11/2014 13:22, fir wrote:
> W dniu sobota, 29 listopada 2014 13:10:17 UTC+1 użytkownik Bart napisał:

>> (Also the pixel-based processing you seem to be doing *is* slow. At
>> higher resolutions I would start basing these things on scalable vector
>> graphics, where the vertex/face calculations are less affected by output
>> resolution (and the eventual pixel-processing needed is simpler). And
>> where there are also existing libraries to help out.)
>>
> what do you mean scalable vector graphics? you mean something lice corel draw?

I'm not familiar with Corel Draw since 1990s but I believe it is along 
those lines. But also things like CAD software. In such a system, a 
sphere is represented by a wireframe network of vertices and faces, 
where you can reduce the number of faces to make it faster, at a cost of 
reducing apparent roundness.

But the advantage is that most of the work needed in rendering such 
objects can be taken care of with libraries such as OpenGL (and 
DirectX), which can also make use of special graphics hardware.

(I'm looking at an OpenGL demo now, of 125 smooth-shaded touching 
spheres in a 5x5x5 matrix, taking up 80% of the display, and it's doing 
60fps at 800x600 with a perspective transformation, using a mouse to 
rotate the model.)

> from my experience cpu graphics for medium (say 1024x786) or larger resolutions is not quite obtainable
> or just not obtainable - i cannot make even any simpler things work fluid when simple clear_frame() takes 8-10-20 ms
> (this seem to be linear (or even a bit worse than linear) slowdown

I think the libraries I mentioned will take care of this stuff, and 
allow things such as double-buffering (display one region of video 
memory while updating the other, then instantly swap). But if you are 
not interested in using someone else's libraries I can understand that.

Also, have you thought of using threads? I've never used them, but if 
each can run on a separate core, then they can be put to work rendering 
alternate frames (or even different parts of the same frame).

-- 
Bartc

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

#53660

W dniu sobota, 29 listopada 2014 17:59:01 UTC+1 użytkownik Bart napisał:
> On 29/11/2014 13:22, fir wrote:
> > W dniu sobota, 29 listopada 2014 13:10:17 UTC+1 użytkownik Bart napisał:
> 
> >> (Also the pixel-based processing you seem to be doing *is* slow. At
> >> higher resolutions I would start basing these things on scalable vector
> >> graphics, where the vertex/face calculations are less affected by output
> >> resolution (and the eventual pixel-processing needed is simpler). And
> >> where there are also existing libraries to help out.)
> >>
> > what do you mean scalable vector graphics? you mean something lice corel draw?
> 
> I'm not familiar with Corel Draw since 1990s but I believe it is along 
> those lines. But also things like CAD software. In such a system, a 
> sphere is represented by a wireframe network of vertices and faces, 
> where you can reduce the number of faces to make it faster, at a cost of 
> reducing apparent roundness.
> 
> But the advantage is that most of the work needed in rendering such 
> objects can be taken care of with libraries such as OpenGL (and 
> DirectX), which can also make use of special graphics hardware.
> 
> (I'm looking at an OpenGL demo now, of 125 smooth-shaded touching 
> spheres in a 5x5x5 matrix, taking up 80% of the display, and it's doing 
> 60fps at 800x600 with a perspective transformation, using a mouse to 
> rotate the model.)
> 
> > from my experience cpu graphics for medium (say 1024x786) or larger resolutions is not quite obtainable
> > or just not obtainable - i cannot make even any simpler things work fluid when simple clear_frame() takes 8-10-20 ms
> > (this seem to be linear (or even a bit worse than linear) slowdown
> 
> I think the libraries I mentioned will take care of this stuff, and 
> allow things such as double-buffering (display one region of video 
> memory while updating the other, then instantly swap). But if you are 
> not interested in using someone else's libraries I can understand that.
> 
> Also, have you thought of using threads? I've never used them, but if 
> each can run on a separate core, then they can be put to work rendering 
> alternate frames (or even different parts of the same frame).
> 
used them a bit

they are not hard i used it like

int SecondThread(void* data)
{
             renderRayTraceFrame_(pixels_y/2+0,pixels_y,1);

  return 0;
}


void renderRayTraceFrame()
{

  int tid = StartThread((void*)SecondThread);

   renderRayTraceFrame_(0, pixels_y/2-0,0);

  WaitThread(tid, 3200);

}

where

int StartThread(void * function)
  {
       DWORD ThreadID;
       static int data[10];

       CreateThread(NULL, 0, (LPTHREAD_START_ROUTINE) function, (void*) data, 0, &ThreadID);

       return ThreadID;
  }

  void WaitThread(int tid, int ile)
  {

      WaitForSingleObject((void*)tid, ile);
     CloseHandle((HANDLE)tid);

  }
  

(this is maybe a bit of hack attitude to the problem as i was not studying the theme)

1) it worked correct (nearly 2x speedup )
2) a bit more debugging in case of mistakes etc
3) you need to be carful for each 'branch' of code not to use (write) the same static data - but ic could revrite the code eben by copy and paste and add
'2' to everything ;0 

got no much experience as i noticed that
with multithreading code is les flexible
to chhanges etc -so it is for me not to use it on on living code (code that is still subject of other optimisations etc)
it is ev good to do it but at the end
(though i got not much experience, i decided programming is sufficiently hard to me on 1 core, right now)

sse would be nise esp that on my new machine i got avx and 8-float registers but it is also hard I will not manage to learn it quick

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

#53661

On Saturday, November 29, 2014 4:59:01 PM UTC, Bart wrote:
> 
> > what do you mean scalable vector graphics? you mean something lice
> > corel draw?
> 
> I'm not familiar with Corel Draw since 1990s but I believe it is along 
> those lines. But also things like CAD software. In such a system, a 
> sphere is represented by a wireframe network of vertices and faces, 
> where you can reduce the number of faces to make it faster, at a cost of 
> reducing apparent roundness.
> 
> But the advantage is that most of the work needed in rendering such 
> objects can be taken care of with libraries such as OpenGL (and 
> DirectX), which can also make use of special graphics hardware.
> 
Whilst those are, in a sense, vector graphics, that's not how the
term is usually used.
Vector graphics are contrasted with bitmapped graphics. In bitmapped
graphics, the colour value at each pixel is stored. That means that
any image can be represented, but the image cannot be scaled or
otherwise manipulated without progressive loss of information.
Vector graphics describe lines and regions by equations, so they
scale to machine arithmetic resolution. There's also usually some
system for imposing hierarchy, so you can do a manipulation like
"move the bird a bit to the left" without damaging the rest of
the image.

3D systems usually use polygon models which are transformed from
3D space to screen space at a late stage in rendering. Curves can't
be represented, but there are various cheats to make polygonal
approximations of curved surfaces look more continuous. You can
however represent curves exactly and do the calculations properly,
which seems to be fir's approach. They're both technically vector
graphics, the 3D equivalent of bitmapped graphics is voxel 
representations where each cube of 3D space is set to a value,
usually with hierarchy so only the surfaces of objects are stored
with high resolution.

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

#53662

On 29/11/2014 18:55, Malcolm McLean wrote:
> On Saturday, November 29, 2014 4:59:01 PM UTC, Bart wrote:

>> In such a system, a
>> sphere is represented by a wireframe network of vertices and faces,
>> where you can reduce the number of faces to make it faster, at a cost of
>> reducing apparent roundness.
>>
>> But the advantage is that most of the work needed in rendering such
>> objects can be taken care of with libraries such as OpenGL (and
>> DirectX), which can also make use of special graphics hardware.
>>
> Whilst those are, in a sense, vector graphics, that's not how the
> term is usually used.

> 3D systems usually use polygon models which are transformed from
> 3D space to screen space at a late stage in rendering. Curves can't
> be represented, but there are various cheats to make polygonal
> approximations of curved surfaces look more continuous. You can
> however represent curves exactly and do the calculations properly,
> which seems to be fir's approach. They're both technically vector
> graphics,

I'm not sure if anyone knows exactly what fir is doing. From the 
snippets of code I've seen, and from the demo, he might have a model 
that stores the centres of spheres and their radii. But then it appears 
this is directly rendered into the pixels that have to represent the 
sphere, depending on the viewpoint and lighting model. (With the 
background being another task to do.)

If the application will only ever deal with spheres, then it might as 
well stay like this (and maybe there are libraries that work solely with 
spheres). (It's not clear if he's testing bounding boxes/spheres in his 
code. If not that's another speedup technique.)

By vector graphics I mean having an intermediate step where the spheres 
exist as some 3D surface in a format favoured by libraries such as 
OpenGL. The main advantage is being to offload most of the work. Also 
the library might be able to use any hardware acceleration that is 
available. The end result is that transformable 3D data is being 
processed this side of the library, not pixels apart from the ones in 
any texture maps that are used.

-- 
Bartc

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

#53663

BartC wrote:
>
> I'm not sure if anyone knows exactly what fir is doing.

Having a bit of a laugh at the expense of those who still converse with him?

-- 
Ian Collins

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

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

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

csiph-web