Quick question about flow control!

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

User avatar
Stucky101
Posts: 141
Joined: Tue Mar 27, 2007 4:17 am UTC
Location: Park City, Utah, USA, North America, Earth, Sol, Orion Arm, The Milky Way, Universe A

Quick question about flow control!

Postby Stucky101 » Sun May 24, 2009 6:36 am UTC

Does this code take the same or close to the same amount of time to perform during runtime as the second code?

Code: Select all

if(timer_rate == 1)
         stimer = stimer + difftime(end, start) * timer_speed;
      else if(timer_rate == 2)
         mintimer = mintimer + difftime(end, start) * timer_speed;
      else if(timer_rate == 3)
         htimer = htimer + difftime(end, start) * timer_speed;
      else if(timer_rate == 4)
         dtimer = dtimer + difftime(end, start) * timer_speed;
      else if(timer_rate == 5)
         wtimer = wtimer + difftime(end, start) * timer_speed;
      else if(timer_rate == 6)
         mtimer = mtimer + difftime(end, start) * timer_speed;
      else if(timer_rate == 7)
         ytimer = ytimer + difftime(end, start) * timer_speed;



Code: Select all

stimer = stimer + difftime(end, start) * timer_speed;
"The earth is the cradle of humankind, but one cannot live in the cradle forever."
~Konstantin Tsiolkovsky, 1895

mrkite
Posts: 336
Joined: Tue Sep 04, 2007 8:48 pm UTC

Re: Quick question about flow control!

Postby mrkite » Sun May 24, 2009 8:28 am UTC

No.. because you can see that if timer_rate is 7, then there are 7 extraneous comparisons being made, combined with 6 jumps.

That's not necessarily a lot of extra time, but it is extra time.

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: Quick question about flow control!

Postby Berengal » Sun May 24, 2009 8:43 am UTC

The time complexity is the same, and if the compiler is smart the first code will only do a multiplication and an unconditional jump extra (possibly also an addition, depending on architecture). The runtime of the rest of the expression is probably going to be several orders of magnitude higher than that bit.
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

User avatar
Stucky101
Posts: 141
Joined: Tue Mar 27, 2007 4:17 am UTC
Location: Park City, Utah, USA, North America, Earth, Sol, Orion Arm, The Milky Way, Universe A

Re: Quick question about flow control!

Postby Stucky101 » Sun May 24, 2009 9:12 am UTC

mrkite wrote:No.. because you can see that if timer_rate is 7, then there are 7 extraneous comparisons being made, combined with 6 jumps.

That's not necessarily a lot of extra time, but it is extra time.

K thanks, I'll find a way around it.
"The earth is the cradle of humankind, but one cannot live in the cradle forever."

~Konstantin Tsiolkovsky, 1895

User avatar
mrbaggins
Posts: 1611
Joined: Tue Jan 15, 2008 3:23 am UTC
Location: Wagga, Australia

Re: Quick question about flow control!

Postby mrbaggins » Sun May 24, 2009 10:31 am UTC

If it usually needs to run the stimer line (IE: the first conditional is true) then in Java it's a null gain most of the time.

Java tends to preprocess conditionals. IE: It starts to work out the line inside as if it is true, even if it might not be. This is why in Java you should write conditionals so that they are true more often than they are false.

You're code could probably be made quicker by making each reference a pointer to a timer that is already configured the correct way... Depends on how your other code is set up though.
Why is it that 4chan is either infinitely awesome, infinitely bad, or "lolwut", but never any intermediary level?

Ended
Posts: 1459
Joined: Fri Apr 20, 2007 3:27 pm UTC
Location: The Tower of Flints. (Also known as: England.)

Re: Quick question about flow control!

Postby Ended » Sun May 24, 2009 12:10 pm UTC

In this situation you might want to use switch-case-break (it's a bit easier to see what's going on, and the compiler should hopefully optimize it).
Generally I try to make myself do things I instinctively avoid, in case they are awesome.
-dubsola

User avatar
Briareos
Posts: 1940
Joined: Thu Jul 12, 2007 12:40 pm UTC
Location: Town of the Big House

Re: Quick question about flow control!

Postby Briareos » Sun May 24, 2009 2:24 pm UTC

Ended wrote:In this situation you might want to use switch-case-break (it's a bit easier to see what's going on, and the compiler should hopefully optimize it).
I was going to say.
Sandry wrote:Bless you, Briareos.

Blriaraisghaasghoasufdpt.
Oregonaut wrote:Briareos is my new bestest friend.

Rysto
Posts: 1460
Joined: Wed Mar 21, 2007 4:07 am UTC

Re: Quick question about flow control!

Postby Rysto » Sun May 24, 2009 7:51 pm UTC

Ended wrote:In this situation you might want to use switch-case-break (it's a bit easier to see what's going on, and the compiler should hopefully optimize it).

Chances are the compiler will compile it to an if-else chain anyway.

Carnildo
Posts: 2023
Joined: Fri Jul 18, 2008 8:43 am UTC

Re: Quick question about flow control!

Postby Carnildo » Sun May 24, 2009 8:38 pm UTC

Rysto wrote:
Ended wrote:In this situation you might want to use switch-case-break (it's a bit easier to see what's going on, and the compiler should hopefully optimize it).

Chances are the compiler will compile it to an if-else chain anyway.

If the compiler writer is competent, it will optimize to either an if-else chain or a jump table, whichever is faster.

User avatar
phlip
Restorer of Worlds
Posts: 7573
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: Quick question about flow control!

Postby phlip » Mon May 25, 2009 7:17 am UTC

Carnildo wrote:whichever is faster.

Well, a jump table is almost always faster than chained if/elses (in the pathological case, very very slighlty slower), and it's also almost always bigger (at best, very slightly smaller, depending on the architecture). Now, in some cases, it'll be slightly bigger and plenty faster, and in other cases it'll be slightly faster and plenty bigger. But which is better depends not only on the individual case, but also on whether you're optimising for size or for speed.

But really: this typically isn't worth worrying about. I'd bet that the calculation you're performing on the timer would dwarf the if/elses in terms if processing time anyway. I'd still recommend using select, but only because of readability, not speed.

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

Grumpy Code Monkey
Posts: 99
Joined: Tue Feb 19, 2008 4:10 pm UTC
Location: Blue Texas

Re: Quick question about flow control!

Postby Grumpy Code Monkey » Tue May 26, 2009 8:29 pm UTC

Stucky101 wrote:Does this code take the same or close to the same amount of time to perform during runtime as the second code?


The only way to know for sure is to profile both versions.

I'm assuming all the timers are of the same type (time_t?); if so, you could clean things up a bit by using an array:

Code: Select all

time_t timers[7];
...
timers[timer_rate-1] = timers[timer_rate-1] + difftime(end, start) * timer_speed;


No unnecessary comparisons, fewer lines of code, etc.

User avatar
Stucky101
Posts: 141
Joined: Tue Mar 27, 2007 4:17 am UTC
Location: Park City, Utah, USA, North America, Earth, Sol, Orion Arm, The Milky Way, Universe A

Re: Quick question about flow control!

Postby Stucky101 » Wed May 27, 2009 1:49 am UTC

Grumpy Code Monkey wrote:
Stucky101 wrote:Does this code take the same or close to the same amount of time to perform during runtime as the second code?


The only way to know for sure is to profile both versions.

I'm assuming all the timers are of the same type (time_t?); if so, you could clean things up a bit by using an array:

Code: Select all

time_t timers[7];
...
timers[timer_rate-1] = timers[timer_rate-1] + difftime(end, start) * timer_speed;


No unnecessary comparisons, fewer lines of code, etc.

Oh well that's a great suggestion. I've never really had any reason to optimize anything I've made, mainly because it's all been small stuff in the past. I guess I should start getting used to optimizing though.

I had another question related to the same program. What I'm doing is making a gravity simulation (just for the fun of it). My plan is to use Newton's Universal Law of Gravitation to find the force acting on each object placed on a 2D plane. Once I find the force I'll divide that by its mass to find the acceleration then adjust the velocity accordingly. Essential what I want in the end is a gigantic 6,000,000 Mm x 6,000,000 Mm (that's about 1,000,000 Mm further than Pluto from the sun) in which you can simulate gravity on both a small scale with satellites and space debris and on a large scale with planets, suns, and moons (the ultimate test of its accuracy will be to create our own solar system within the sim and see how well it predicts the orbits of the planets).

So my question is, since time will be a crucial element in determining the distance traveled by an object in one loop, should I use ctime to find the time or figure out the frames per second (I'm not exactly sure how the frames per second thing works but I heard people talking about finding time that way).
"The earth is the cradle of humankind, but one cannot live in the cradle forever."

~Konstantin Tsiolkovsky, 1895

User avatar
mrbaggins
Posts: 1611
Joined: Tue Jan 15, 2008 3:23 am UTC
Location: Wagga, Australia

Re: Quick question about flow control!

Postby mrbaggins » Wed May 27, 2009 4:04 am UTC

Never use fps, as it will differ on everyone's machine.

If you want your simulation to make predictions, it will have to use a 'real world' clock.

Also, on the theory side of things, satellites (Man made, that is) and debris have little to no effect. Definitely not on a scale that hundreds of years care about. Of course, they ARE affected, but this would be a different set of calcs than say the effect of saturn on jupiter. (IE: Satellites/debris are one sided calculations, whereas planets/moons are two sided)
Why is it that 4chan is either infinitely awesome, infinitely bad, or "lolwut", but never any intermediary level?

User avatar
Stucky101
Posts: 141
Joined: Tue Mar 27, 2007 4:17 am UTC
Location: Park City, Utah, USA, North America, Earth, Sol, Orion Arm, The Milky Way, Universe A

Re: Quick question about flow control!

Postby Stucky101 » Wed May 27, 2009 5:21 am UTC

mrbaggins wrote:Never use fps, as it will differ on everyone's machine.

If you want your simulation to make predictions, it will have to use a 'real world' clock.

Also, on the theory side of things, satellites (Man made, that is) and debris have little to no effect. Definitely not on a scale that hundreds of years care about. Of course, they ARE affected, but this would be a different set of calcs than say the effect of saturn on jupiter. (IE: Satellites/debris are one sided calculations, whereas planets/moons are two sided)

Well in a way you are right. Do satellites affect the orbits of planets? Well for the purpose of not being precise down to the last nanometer, no they absolutely do not. But in terms of the equation Image the calculations will be accurate whether you have a die spinning around a planet or a planet spinning around a sun. So pretty much the reason I want to use the same equation for everything is because I don't see a reason not to. You could maybe say to optimize the code, but I don't see how adding an if statement to see if an objects mass is below a certain amount would optimize anything.
"The earth is the cradle of humankind, but one cannot live in the cradle forever."

~Konstantin Tsiolkovsky, 1895

User avatar
Zabaron
Posts: 113
Joined: Wed Jun 04, 2008 3:33 am UTC
Location: Georgia

Re: Quick question about flow control!

Postby Zabaron » Wed May 27, 2009 6:40 am UTC

Because, if you know an object is too small to affect anything, you don't have to calculate the force it exerts on everything else. Thus, if there are n objects in your system, you can avoid calculating F n-1 times at the cost of a single if statement.

-Zabaron
I love deadlines. I love that wooshing sound they make as they fly by. -Douglas Adams

User avatar
Stucky101
Posts: 141
Joined: Tue Mar 27, 2007 4:17 am UTC
Location: Park City, Utah, USA, North America, Earth, Sol, Orion Arm, The Milky Way, Universe A

Re: Quick question about flow control!

Postby Stucky101 » Wed May 27, 2009 6:57 am UTC

Zabaron wrote:Because, if you know an object is too small to affect anything, you don't have to calculate the force it exerts on everything else. Thus, if there are n objects in your system, you can avoid calculating F n-1 times at the cost of a single if statement.

-Zabaron

True. For now I'll just do it my way, unless I run into problems. The thing is I'm not sure where the cut off point should be. Also, if I do use it I'd probably have to use it for both mass and distance.
"The earth is the cradle of humankind, but one cannot live in the cradle forever."

~Konstantin Tsiolkovsky, 1895

User avatar
mrbaggins
Posts: 1611
Joined: Tue Jan 15, 2008 3:23 am UTC
Location: Wagga, Australia

Re: Quick question about flow control!

Postby mrbaggins » Wed May 27, 2009 7:26 am UTC

Just another random, possibly useful optimisation note. (It's useful if you've never seen it, and a reminder if you have)

When working out distances, leave everything squared. So, when working out the distance between two objects, don't sqrt() to get the answer. Why? Because sqrt is intensive, and when you stick it back into your formula, you're just squaring it back again anyway!

So, say you were working in 2D. Object A is over here with mass 200, Object B is over here with mass 2000.
F=G(m1m2/r2)
F=9.8(200)(2000)/r2

Distance is where the square root is normally used....
r = ((x1 - x2)2 + (y1 - y2)2)1/2
But the formula for gravity only needs distance squared. So just store the distance as distanceSquared instead.
r2 = (x1 - x2)2 + (y1 - y2)2
Then use it directly in the formula.

I need to learn the math tag thingy for these forums.
Why is it that 4chan is either infinitely awesome, infinitely bad, or "lolwut", but never any intermediary level?

Grumpy Code Monkey
Posts: 99
Joined: Tue Feb 19, 2008 4:10 pm UTC
Location: Blue Texas

Re: Quick question about flow control!

Postby Grumpy Code Monkey » Wed May 27, 2009 6:35 pm UTC

Stucky101 wrote: I've never really had any reason to optimize anything I've made, mainly because it's all been small stuff in the past. I guess I should start getting used to optimizing though.


First rule of optimization: don't do it.
Second rule of optimization: don't do it yet.

First worry about getting it correct. Then worry about making it clear. Then worry about making it maintainable. Then you can worry about making it fast.

Optimize from the outside in; make sure your overall algorithm and choice of data structure are right for the problem. Then you can look for ways to tighten up the implementation (removing invariant statements from loops, unrolling loops, using lookup tables, etc.). There's a point where gains in speed come at a cost in clarity (see http://en.wikipedia.org/wiki/Duff's_device for an example); you should avoid this kind of low-level trickery unless you're not meeting a hard performance requirement and you've done everything else you can at a higher level.

Ended
Posts: 1459
Joined: Fri Apr 20, 2007 3:27 pm UTC
Location: The Tower of Flints. (Also known as: England.)

Re: Quick question about flow control!

Postby Ended » Wed May 27, 2009 7:15 pm UTC

Stucky101 wrote:
mrbaggins wrote:Never use fps, as it will differ on everyone's machine.

If you want your simulation to make predictions, it will have to use a 'real world' clock.

Also, on the theory side of things, satellites (Man made, that is) and debris have little to no effect. Definitely not on a scale that hundreds of years care about. Of course, they ARE affected, but this would be a different set of calcs than say the effect of saturn on jupiter. (IE: Satellites/debris are one sided calculations, whereas planets/moons are two sided)

Well in a way you are right. Do satellites affect the orbits of planets? Well for the purpose of not being precise down to the last nanometer, no they absolutely do not. But in terms of the equation Image the calculations will be accurate whether you have a die spinning around a planet or a planet spinning around a sun. So pretty much the reason I want to use the same equation for everything is because I don't see a reason not to.

Just a heads up: let's say you have a large satellite which weighs 1000kg, at an earth-radius away from the earth. The acceleration on the earth due to the satellite is around 10-21 ms-2, far smaller than the machine epsilon in double precision (around 10-16). So you'll need to be using a BigDecimal class or equivalent for the satellite to have any effect at all on the earth. I'd advise starting out by just modeling planets (which is a very hard thing to do with much accuracy over long time intervals, even without worrying about hugely different mass scales).

Caveat: it's your project and experimentation is fun and useful, so try out whatever you want ;)
Generally I try to make myself do things I instinctively avoid, in case they are awesome.
-dubsola

stephentyrone
Posts: 778
Joined: Mon Aug 11, 2008 10:58 pm UTC
Location: Palo Alto, CA

Re: Quick question about flow control!

Postby stephentyrone » Wed May 27, 2009 10:36 pm UTC

Ended wrote:Just a heads up: let's say you have a large satellite which weighs 1000kg, at an earth-radius away from the earth. The acceleration on the earth due to the satellite is around 10-21 ms-2, far smaller than the machine epsilon in double precision (around 10-16). So you'll need to be using a BigDecimal class or equivalent for the satellite to have any effect at all on the earth.


Your conclusion is correct, but not for the reason you give. A value being smaller than machine epsilon doesn't make it unrepresentable, it just means that it will have little/no effect if it is added to a second value that is on the order of 1.0. You can multiply by it or add it to a similarly scaled value without any undue loss of precision.

The conclusion is still correct for a naive implementation of orbital equations in double precision, though, as the satellite will have negligible effect on the model because the ratio of its gravitational acceleration on the earth to that of the sun (~0.005 m/s^2) is smaller than machine epsilon.
GENERATION -16 + 31i: The first time you see this, copy it into your sig on any forum. Square it, and then add i to the generation.

Ended
Posts: 1459
Joined: Fri Apr 20, 2007 3:27 pm UTC
Location: The Tower of Flints. (Also known as: England.)

Re: Quick question about flow control!

Postby Ended » Wed May 27, 2009 10:44 pm UTC

stephentyrone wrote:The conclusion is still correct for a naive implementation of orbital equations in double precision, though, as the satellite will have negligible effect on the model because the ratio of its gravitational acceleration on the earth to that of the sun (~0.005 m/s^2) is smaller than machine epsilon.
Ah yes, this was what I was trying to get at, thanks.
Generally I try to make myself do things I instinctively avoid, in case they are awesome.
-dubsola

User avatar
Emu*
Posts: 689
Joined: Mon Apr 28, 2008 9:47 am UTC
Location: Cardiff, UK
Contact:

Re: Quick question about flow control!

Postby Emu* » Thu May 28, 2009 12:36 am UTC

Would these crazy formulae be suitable for calculation using CUDA-capable GPUs?
Cosmologicon wrote:Emu* implemented a naive east-first strategy and ran it for an hour, producing results that rivaled many sophisticated strategies, visiting 614 cells. For this, Emu* is awarded Best Deterministic Algorithm!

Ended
Posts: 1459
Joined: Fri Apr 20, 2007 3:27 pm UTC
Location: The Tower of Flints. (Also known as: England.)

Re: Quick question about flow control!

Postby Ended » Thu May 28, 2009 1:07 am UTC

Emu* wrote:Would these crazy formulae be suitable for calculation using CUDA-capable GPUs?

You mean the planetary motion stuff? Yes indeed, although the OP's celestial-mechanics-type problem is probably not as good a fit as an n-body problem with many thousands of similar particles would be. The CUDA SDK contains an example code for the latter type of system; also this guy has a research-grade n-body code which can run on the GPU.
Generally I try to make myself do things I instinctively avoid, in case they are awesome.
-dubsola

Carnildo
Posts: 2023
Joined: Fri Jul 18, 2008 8:43 am UTC

Re: Quick question about flow control!

Postby Carnildo » Thu May 28, 2009 2:26 am UTC

Grumpy Code Monkey wrote:Then you can look for ways to tighten up the implementation (removing invariant statements from loops, unrolling loops, using lookup tables, etc.).

Don't do this. Every compiler for a performance-oriented language is better at this sort of low-level optimization than you are. For example, an unrolled loop saves a conditional branch instruction (and the resulting potential pipeline flush), but it takes more space, increasing the odds of a cache miss -- and in certain cases, a compiler can turn a rolled loop into a series of SIMD instructions.

stephentyrone
Posts: 778
Joined: Mon Aug 11, 2008 10:58 pm UTC
Location: Palo Alto, CA

Re: Quick question about flow control!

Postby stephentyrone » Thu May 28, 2009 6:02 am UTC

Every compiler for a performance-oriented language is better at this sort of low-level optimization than you are.


Only if you suck at it. (Almost everyone sucks at it)

If you are interested in getting good at it, the key is to apply the scientific method. Don't ever apply an "optimization" because someone told you it was beneficial. Measure baseline performance rigorously. Try an experiment to improve performance. Measure performance again. Consider any effects that could be confounding your performance measurements. Come up with experiments that you can conduct to show that they are not. Rinse and repeat.

Very few people have the patience for this. If you don't, you're better off letting the compiler do it for you.
GENERATION -16 + 31i: The first time you see this, copy it into your sig on any forum. Square it, and then add i to the generation.

User avatar
PM 2Ring
Posts: 3715
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Sydney, Australia

Re: Quick question about flow control!

Postby PM 2Ring » Thu May 28, 2009 8:35 am UTC

Ended wrote:I'd advise starting out by just modeling planets (which is a very hard thing to do with much accuracy over long time intervals, even without worrying about hugely different mass scales).

This.

With a naive implementation using Newton's equations to simulate just one planet around the sun, it's quite likely that even a single orbit won't close, unless you use a really tiny time increment. And it gets worse, the more eccentric the orbit is. There are techniques that can be used to improve this, though. For example, you can use the naive algorithm to calculate the planet's position & velocity at the end of the time increment, then use linear interpolation to find the position & velocity at the middle of the time increment. Then use this midpoint data to recalculate the forces. Or something like that... :)

I wrote C code for this about a decade ago, so I may be misremembering. I'll search my archives for the code, if you're interested. I was mostly interested in investigating Hoffman transfer orbits, and in the end I decided to calculate the orbits using Kepler's equation. It was a lot faster than using Newton's equations.

http://mathworld.wolfram.com/KeplersEquation.html

Carnildo
Posts: 2023
Joined: Fri Jul 18, 2008 8:43 am UTC

Re: Quick question about flow control!

Postby Carnildo » Thu May 28, 2009 10:35 am UTC

PM 2Ring wrote:
Ended wrote:I'd advise starting out by just modeling planets (which is a very hard thing to do with much accuracy over long time intervals, even without worrying about hugely different mass scales).

This.

With a naive implementation using Newton's equations to simulate just one planet around the sun, it's quite likely that even a single orbit won't close, unless you use a really tiny time increment. And it gets worse, the more eccentric the orbit is. There are techniques that can be used to improve this, though. For example, you can use the naive algorithm to calculate the planet's position & velocity at the end of the time increment, then use linear interpolation to find the position & velocity at the middle of the time increment. Then use this midpoint data to recalculate the forces. Or something like that... :)

I wrote C code for this about a decade ago, so I may be misremembering....


It's been about that long since my numerical analysis class, but that's about right: you're essentially performing a double integration on the acceleration function, and when you integrate, errors accumulate dramatically. Find a numerical analysis textbook and look up methods for integration or for solving ordinary differential equations, and translate the Fortran code into the language of your choice, adapting appropriately.

stephentyrone
Posts: 778
Joined: Mon Aug 11, 2008 10:58 pm UTC
Location: Palo Alto, CA

Re: Quick question about flow control!

Postby stephentyrone » Thu May 28, 2009 3:11 pm UTC

If you want the orbits to have any physical accuracy, what you are going to be looking for are what's called Symplectic Methods, which are used (loosely speaking) because they conserve the same quantities as the differential equations you are trying to model (the wikipedia article has a somewhat longer more accurate description of what exactly they conserve).

"Geometric numerical integration" By Ernst Hairer, Christian Lubich, Gerhard Wanner is a decent book on the subject, if you've had some numerical analysis in the past or have a pretty solid background in ODEs. If you haven't, it will be gibberish to you.

"real" orbital mechanics simulations generally use very complex schemes; it's a fascinating subject, but don't expect to understand the whole of it anytime soon. There's nothing stopping you from just jumping in and writing your own tools to play around with in the meantime.
GENERATION -16 + 31i: The first time you see this, copy it into your sig on any forum. Square it, and then add i to the generation.


Return to “Coding”

Who is online

Users browsing this forum: No registered users and 10 guests