Optimization Puzzle

Thx Sherlock! (j/k)

Ah... Win32 API / ANSI function calls... All the same to me really when you've programmed for a while...

Guess its a bad, lazy way of saying Non-DirectX function calls...

Cos they're all slow to me.... Well mostly...

Didn't REALLY wanna look at asm code mate... Inline asm is about all I can handle for now, due to its convenience...

Have you seen the asm code the complier produces???

If I was an asm nut, then sure I would have done that LONG ago...

No, MS Visual C++ is over complicated... And I'm sure theres a way to tame the damn complier...

At least I'll gain some control if I wanna do precise code timings...

Looking at convoluted complier generated asm is the LAST resort.

But its an idea that I might have to consider :-(

Easy there matey.

I did say I was lazy when it comes to the classification of differnt API's.

My problem, not yours... Not that it IS a problem...

Listen, I understand compliers are the BEST optimizers... That was NOT my point.

My point is that its difficult to time your code when the complier alters the code that you are trying to time.

If you have any ideas on how to temporarily disable that feature, then I'm interested...

If not... Go bug some other poor soul with incomplete and vague answers.

Plz answer the specific question:

Can you disable the compliers' feature to alter ones code...

A simple yes or no would suffice.

I'm experiementing with various code here and I wanna know which one works best.

Is that re-phrased question straight forward enough?

Quote:

And, for what it's worth, if someone doesn't know the difference between Win32 functions and ANSI functions, especially if they call themselves TerrorFLOP (the pun strikes terror in my heart), I doubt they're better at low level optimizations than a compiler (almost certainly coded by people who know the difference between Win32 and ANSI).

Even today's compilers are limited in some optimizations that they can do and still there's a need to develop better algorithms for compilers, especially for stuff like avoiding "optimization blockers", but if I'm not mistaken there's at least ONE problem related to that that's NP-Complete, so in that case the best optimization is (if someone created an algorithm for it) an aproximation, if required...
True optimization is, first and foremost, improving the algorithms. Then you can think if assembly is still worth it...

The general problem is that most people that try to do stuff in assembly don't know that much assembly and use quite often stuff that needs lots of CPI in few lines, or lots of lines when something can be written in a more terse way with simpler instructions... It's assembly. If you really wanted "ease of reading" +skill for your code you wouldn't be programming in assembly.

My advice is... If you really want to optimize try learning more assembly or try thinking in a different way to do that.

P.S. - I heard that Quake3 source code had an implementation of sqrt in assembly... Maybe you could look at it if you want ideas...

Let me clarify my problem clearly...

As it seems peeps, who shall forever remain anonymous (and thank God eh?) haven't really grasped my problem.

Compliers use what is called 'Loop Invariant Computations'.

What that means in layman terms, is that ANY code that you write within ANY loop that does NOT depend upon the looping index, is classified as an invariant.

Most optimizing compliers are constructed to detect such code in loops, and thus MOVE the invariant code OUT of the loop in order to increase speed:

Here is an example of my dilemma, the complier has re-written my test code;



for (register int i = 1000000000; i >= 0; --i)
{

}



to the following:




for (resgister int i = 1000000000; i >= 0; --i)
{
}



Do you see the problem? I wish to test the code, but when I build a Release version of the code, with all optimizations active, all I do is test a null loop.

Hence why when I test THIS function;


inline double Tools::Norm (const CSSE2Vector &A)
{
return double (sqrt ((A.x * A.x) + (A.y * A.y)));
}


I get a report back saying it’s just as FAST as a NULL function, which is obvious bull.

Now, can anyone tell me if there is a way to tell the complier NOT to perform a Loop Invariant Optimization.

Much Appreciated.

Although it is probably naive, the way I test code like this is to pass a random number to the function I want to test. I think this works when you want to compare two different functions because the generation of the random number is a common factor of the process. I guess you could also time the generation of the random number if you wanted a better estimate of the time that each function takes to perform its task.


-Josh

Thx k0n.

A helpful reply at last LOL...

The thing is, is that I agree with you that asm is tricky stuff.

Hence my reluctance to look at complier generated asm code...

Perhaps one day I'll jump straight into asm, but with today's high specs API's I guess I try to avoid such an endeavour.

However, the small piece of simple SSE2 asm that I wrote is hardly complex.

And the only reason why I've attempted asm is because of 'sqrt's apparent slowness.

Many books I’ve bought on C/C++ optimizations all hail the complier, but they also try to encourage us to use highly optimised SIMD instructions for critical code, and I suppose I agree.

I will look into those areas you mentioned... Thanks very much for your input... But c'mon, a handful of simple SIMD instructions gets beat by 'sqrt' in Release versions only???

(In Debug, my code wins big time!)

No... My complier is being too clever... Sure it’s helpful... But I want it to behave JUST a little so I can accurately test my code...

IF that is NOT possible (MS VC++ is complex and I've spent years on the damn thing... Well more on programming... But I guess I still have a lot to learn on the IDE)... Then sure I'll quit trying to time code...

Or perhaps invest in an expensive profiler...

But I ain't giving up just quite yet LOL!!!

Thanks Anyway :-)

Thx jjd...

You know, I actually thought of that...

I didn't run the tests though 'cos I thought it sounded a bit crazy (LOL.... No offence mate!)

Mmmm... Perhaps now that you have mentioned I'll give that idea a go...

However, I've a funny feeling that the ever so helpful complier will say;

'Great!!! Another code invariant that does not depend on the looping index'

and move the code according...

Sure, helpful in MOST situations, but not in code timing...

Last resort I guess is to somehow incorporate the looping index in the test code...

I might not get an accurate test... But at least it won't move the code so that it CAN be tested...

Gonna try some ideas now...

Thx!

TerrorFlop:
One thing you could try is to take the assembly the compiler generates (to call normal sqrt) and put that in an __asm block so that the compiler will treat it as the same "black box" and not optimize it. You could also try __declspec(noinline) in case the compiler is just unrolling and inlining the whole deal...

However, the BEST (and I highly recommend this if you're into this sort of thing) is to go to AMD's website and download CodeAnalyst. It allows you to 'record' portions of your code, and then it simulates everything that is happening on the processor during that time and shows you a graph of where all the cycles are going and which stages of the pipeline are stalling for each instruction. It takes a lot of practice to really understand everything that's happening, but the "Green is Good, Red is Bad" thing will be a good start :)

Anyway, regarding the "Compiler is the God of Optimization"... That would be great, wouldn't it? It makes sense, right? Unfortunately, the compiler is *terrible* at optimizing, and especially intrinsics. I mean jokingly bad. The only thing the compiler actually does is inline and unroll loops, so as to distort the sort of tests TerrorFlop is trying to run. The real genius is the processor, especially those AMDs. The re-arrangement of crappy code that that thing can do on the fly, it's indescribable what sort of genius went into producing that on silicon at 3 GHz.

Anyway back to TF: The test you're running... it's not a very good way to test SSE. The one thing the processor can't do is magically eliminate latency stalls, like using xmm0 as a destination and source to almost every instruction... it'll fill those stalls with out-of-order instructions, but if all you're doing is a tight loop that keeps stalling, there's not much it can hope to do. Do you need to use doubles? This can be written much faster with floats.

[edit] Another thing. I'm not sure about doubles, but for floats there are 2 instructions: sqrtps and rsqrtps. One is the full IEEE float sqrt, and the second is a 12-bit accurate inverse square root that runs about 7 times faster (so to eliminate the divide that is necessary to do a normalize). So, it's likely that the "meat" of your function, the square root, is occupying 80% of your cycles in both functions. See, this is the sort of thing CodeAnalyst is for.[/edit]

Thx Ajas.

You've certainly given me food for thought there and I'll check out CodeAnalyst.

Think I'll just give up anyway... (the other coding ideas I wrote still come up with ‘sqrt’ as fast as a bleeding NULL statement!!!)

You would have thought that accurately timing code would be pretty easy, but the complier can and does get in the way.

However testing 'sqrt's actual asm code directly sounds like a damn good idea...

The SSE2 code I wrote... And lets face it... It ain't complex (but yeah, I know a little bit about Intel’s CPU instruction re-ordering... Damn complex subject!!!)... IS fast...

I was simply bemused that 'sqrt' is 'faster' despite it having such a bad rep in most optimization books I've read.

And the fact that it’s as fast (apparently) as a NULL function sure as hell doesn't make sense.

But thx man... Gonna go rip out 'sqrt's innards and learn from its dark secrets LOL!

Anon said:

Just include the loop index in the arguments to the function. No more invariant.



Thx for the tip.... But even that does not appear to work. The complier still performs its magic... Somehow... :-(

(Which is damn useful 99.999% of the time... But not for accurately testing code)

__________________________________________________________
Optimizing Code Really F's U Up!!! DON'T DO IT!!! (LOL)

An extract from MSDN Online:

_______________________________________________________________________________
Often, some code inside a loop, which is repeated many times, does not change values during the loop's execution. These loop invariants can be calculated once before the loop runs. Removing or hoisting loop invariants generally improves speed without affecting size very much. For example, invariant hoisting can remove the arithmetic from the inside of this loop:

for (i=0;i<1000;i++) {
A = a + b; }

The product is

t = a+b;
for (i=0;i<1000;i++) {
A = t; }

This saves 999 addition operations at the cost of one temporary variable, which is likely to go into a register.
________________________________________________________________________________


So even trying to force code to be NON-invariant is pointless... The complier does what the hell it wants...

Most times thats helpful.... Most times...

Programmer 0 - Complier 1 :-(

Quote:

Original post by TerrorFLOP Thx Sherlock! (j/k) Ah... Win32 API / ANSI function calls... All the same to me really when you've programmed for a while...

for a while but not for long enough.

It is standard library call, heck, not even a call (i can bet it is inlined). In release mode with optimizations on is going to have equal or greater speed than whatever-you-can-ever-write.

anyway, if you need this sqrt to compute distance, chaces are you can do your work with squared radius and do not need sqrt at all.

p.s. benchmarks is worth precisely nothing when compiler is "more smart" than writer of benchmark, and it is certanly the case. Compiler will not compile things that is not necessary, that is. You need to do something useful with results(like, add them and print the sum), make all inputs different, etc. It's not just invariant, if result is going nowhere, no computation is done. Better yet benchmark your actual code. Chances are, compiler will optimize a lot of unnecessary code out there too.

Anyway, just forget about assembly-level optimizations. If you can not write benchmark, you surely can not make optimizations better than compiler can, as compiler cleanly "knows" more optimizations than you.

1. Putting hand-coded asm into your code makes it hard for the compiler to optimise the code around it, so unless it's a substantial chunk of asm any speed improvement may well be lost.

2. You might be better off using intrinsics in the source code (not asm) - e.g. here.

3. Your compiler probably supports generating SSE instructions anyway (even if it doesn't manage the vector forms) - why not just enable this flag in the compiler? Of course, you need to know that the target machine will support them.

4. If you really care about speed, use floats not doubles, which may require reworking your algorithms to handle the loss in precision.

5. doing sqrt(x*x + y*y) can generate precision problems when x and y are large - that's the point of the hypot function. It may be that the increased accuracy with hypot means you can use floats, not doubles.

I don't know whether the above suggestions will help - my own experience has been that trying to speed things up at this low level (SSE intrinsics, prefetching etc) invariably slows things down!

Dmytry...

I find your lack of IQ... Disturbing to say the least.

No wonder there has been posts from the moderators about peeps like you.

If I wish to time my code... Then that is entirely my business.

I've timed code before... And I shall do so... AGAIN.

There’s even code in the online MSDN (and several other books) which shows you how to implement code timing logic and I've implemented some of that code into my own timing routines. If you have a problem with other coders trying to time and experiment with their code... Then you have a serious problem dude.

With regards to the 'radius squared' issue... You have NO idea why I would choose to norm vectors do you?

Go check out Newton's Law Of Gravitation... The VECTOR version (since force IS a vector)... And you'll realize that the famous law utilizes norm cubes.

Anyway, WHY I'm I trying to explain myself to you.

If you've nothing constructive to say man... THEN DON'T SAY!!!

I'm sure the rest of the civilized world will get by just fine without your 'insights' (if indeed you can call it that).

Thx MrRowl.

Don't worry... I know what I'm doing with regards to my programming model.

I have to use double precision here as I'm doing a physics project based on star cluster formations.... So the numbers can get pretty big pretty quickly and I want to do the simulation using 'real' quantities.

I've been playing with SIMD for a few years now and your right, most of the time the complier does such a fine job at optimizations, that using SIMD yourself is a waste of time in MOST... But not all... cases. (Nowt wrong in experimenting of course... That’s how coders are supposed to come up with new ideas)

I already have a C / C++ version of the central time critical code up and running and its pretty fast... But because its time critical (i.e. the code needs to update the positions and velocities of 1000's of stellar objects each frame)... It does not hurt to see if you CAN make the code run just a little bit faster.

Having read SEVERAL books on the apparent slowness of 'sqrt', I thought I'd try a simple SIMD routine to see if I could beat it. The results remain inconclusive as the complier has a habit of totally altering the code you write.

There are #pragmas, directives and other coding constructs which can alter the behaviour of the complier... Which is why I approached this forum, to see if anyone knew how to stop the complier performing Loop Invariant Computations (the details of which are described above).

My central problem is not one of optimization per se... But more of a complier issue.

Quote:

Original post by TerrorFLOP If you've nothing constructive to say man... THEN DON'T SAY!!!

I don't like the way you talk to people here. Everyone is just trying to help you in solving your problem, mate. ;)

If that help ain't constructive... Then I don't wanna hear it.

Clapton... You read the moderators guidelines?

Firstly, insulting people like Dmytry who have ratings of 1597 is silly, because they're obviously helpful people and are trying to be constructive. They don't get those ratings by being jerks.

For testing, why not just use your actual code? You have two functions to test, so either use a simple search and replace, or create another function like this to use everywhere:



This way you'll know how it performs in your actual code.

tj963

[Edited by - tj963 on September 13, 2005 8:17:23 AM]

Quote:

Original post by TerrorFLOP Thx MrRowl. Don't worry... I know what I'm doing with regards to my programming model. I have to use double precision here as I'm doing a physics project based on star cluster formations.... So the numbers can get pretty big pretty quickly and I want to do the simulation using 'real' quantities.

i dont see what the size of your numbers has to do with using floats or not. do you really expect your floats to overflow? i doubt it.

also i do not really think the mantissa needs to be of double size. if anything i would consider using fixed point numbers for recording your positions, as they give uniform precision, instead of floats which concentrate their precision around the origin, which is quite undesirable for this application.

anyway, while im fine with you experimenting with your code, i think it is a waste of time. sqrt is slow, but that doesnt mean it is a bottleneck or that you can improve it.

optimisation of algorithms is probably much more important here. tell me, what approach do you wish to take for your simulation? just a naive one, which scales quadraticly with the amount of masses you want to simulate wont produce very interesting resuls given the amount of masses youll be able to get on screen, unless you have some sort of supercomputer. if i recall correctly there are methods, not too hard to implement, that can reduce timecomplexity to n*log(n)