Quick algorithm wanted

[Disruptive]

Hi

In my efforts to speed things up somewhat I would like to output an integer (1) if x > Xmax or x < 0, but if x is between the limits 0 to Xmax then will return. Obviously I can write withif then and have done so, but as this routine is being called billions of times any potential time saving is appreciated. Are the any inbuild heaviside functions into c?? or anything suitable?

Thanks

 

[sedj]

switch/case ?

--------------------------------------------------
Free Java/J2EE Database Connection Pooling Software

http://www.primrose.org.uk

 

[Disruptive]

not suitable...prob too slow!

I am dealing with real numbers.

 

[cpjust]

switch or if/else are the fastest ways I know.

You can figure out what the most likely scenarios will be and order your if/else statement from most likely to least likely.

For example, if more numbers are likely to be between 0 and Xmax, and then out of the rest more are likely to be > Xmax, do this:

...
if ( (x <= Xmax) && (x >= 0) )
{
   /* Do nothing? */
}
else
{
   printf( "1" );
}
...

 

[Salem]

Well calling printf() just to output one character is sure to hose performance if you're calling it with any regularity at all (in billions of runs).

Use putchar() if you're just outputting a char, or puts() if you're outputting a fixed string.

How big are the output files you're generating?

> Obviously I can write withif then and have done so
Once again, I see you're focussing on the minutia which the compiler will surely figure out the best way of doing it for your machine rather than tackling the big picture performance problems.

As per previous posts, are you going to post any details of a profiling run for example?


--

 

[lionelhill]

Realistically, this is a very simple straightforward bit of code, so it's 99.99% certain the compiler will do it in absolutely the most efficient way possible. The people who write compilers are really, really top-notch at assembly and low-level algorithm writing, and you won't out-do them.

The only way you can out-do standard features of a language is if you can identify something in your data or your application that is non-standard, and optimise to handle your personal non-standard case. Note that this is the exact opposite of the normal advice (i.e., the normal: keep things general so they can be reapplied).

For example, if you have a stream of real numbers like this, are they related to each other in any way? If they're a stream of measured temperatures, where you expect long periods over Xmax but no sudden changes, you may not need to check every number; you could just check every 100 numbers and then scan backwards and forwards from a change to find exactly the point it went over Xmax. I doubt this is your application, but it illustrates the general idea.

Always look and see if you actually need to do what you're doing anyway, and if so, whether you've accidentally done it (or nearly done it) somewhere already.

And do make sure you've turned off all possible safety checks on your code. No range checking, no stack checking, etc. (but of course only after you know the code is rock-solid and reliable). Extra checks do take time.

You really need to think big about optimisation. As an example, the leaps in strength in chess playing programs haven't happened because someone optimised an inner loop. They've happened because someone's devised a new algorithm where they realised you only need to go round much the same inner loop ten times rather than a thousand.

 

[Diancecht]

Optimizing a C if-else, in my humble opinion, is freak: as lionell points out, try to optimize the whole algorithm, for sure there are more "perfomance leaks" than in a simple if, that will be translated as a simple bz in assembler.

Maybe having a look at this gives you some ideas:

http://www.abarnett.demon.co.uk/tutorial.html

Cheers,
Dian

 

[xwb]

If you want really unreadable code try

((x <= Xmax) && (x >= 0) ) || printf( "1" );

It is the same as an if statement. Have a look at the obfuscated C contest winners if you want some warped ideas.

 

[sedj]

Disruptive :

I have to say - these "speed ups" you are after just do not exist. You cannot speed up an if/else statement - its just not possible, for all the reasons that people have posted over all of your posts.
If your code is slow, then you need to address the general algorithms your code employs, rather than attempting to speed up the actual generated machine code that a C if/else statement generates.
You could move into ASM, but I doubt you can write better ASM than your compiler.
I mean - asking how to speed up fmod ..... its like people filing bug reports against a compiler when their code is actually incorrect. Just get used to the fact that if your code is slow, then the answer is either :

1) Your code is running as quick as it can, on your processor - if you want it quicker - then buy a bigger boat.
2) Your actual programmes alg's are carp - instead of asking how to speed up an if/else, then how about rewriting the algorithm ?
3) Learn ASM properly, and write the lot in ASM. But if your alg is carp, then your programme will still be carp.


--------------------------------------------------
Free Java/J2EE Database Connection Pooling Software

http://www.primrose.org.uk

 

[denc4]

i have seen compiler generated assembly code a lot of times and it always strikes me how needlesly often it accesses memory. Whereas human written assembly code the processor registers are used whenever possible, a compiler accesses a variable 99% of the time from its address in memory. This reduces program speed when a variable is accessed often, i think they call this phenomenon temporal locality of reference.