Loop unrolling

[AtW]

Loop unrolling these days is executing in parallel on multiple cores.

HTH

[VectraMan]

At least they taught what loop unrolling / rolling is on his course. Unlike most courses nowadays which consist of "using powerpoint"

Or worse, Java.



Loop unrolling would work pre Pentium 4 (I think that was the one). That's because the jump would stall the clever look ahead / out of order execution stuff. But with the P4 the clever stuff would guess the most likely outcome of a jump before it got there and assume you'd continue round the loop - no penalty at all for looping, just a small penalty for the exit case. It'd probably be faster not unrolled because there was less code to load.

I went to an Intel course once where they taught this. And what worked on the pre-P4 course (I'm racking my brain trying to remember the names) they told us to forget for the P4.

[Scary]

At least they taught what loop unrolling / rolling is on his course. Unlike most courses nowadays which consist of "using powerpoint"

On a Computer Science/Software Engineering curriculum? I don't think so.

[bobhope]

At least they taught what loop unrolling / rolling is on his course. Unlike most courses nowadays which consist of "using powerpoint"

[AtW]

It's usually better to let the compiler (optimiser) decide. You should be able to tell it whether you prefer space or speed too.

The Art of Optimisations is pretty much lost

[Churchill]

Exactly. Usually. Not always... sometimes unrolling or employing SIMD ops (which compilers still suck at) are effective. Sometimes very effective, in the SIMD case. But only after profiling.

I use the supplied intinsics rather than rely on the compiler - however, Intel's performance libraries are pretty sweet.

Then we're into, can you prove it in 'O notation'. It's like, err, how's about trying the 'stopwatch method'?

I listened to a podcast about "Critical Software Development" by Martin Thomas. Apparently we(C & C++) developers shouldn't be allowed anywhere near it... Oh well...

[DimPrawn]

Hey Threaded, leave them kids alone, all in all you're just another brick in the wall...

[threaded]

It does work in the right places. I used it on a tight inner loop for a 3D render engine that was looping through every pixel on the screen many times a second. Of course, the code inside the loop was absolutely optimised to minimise the number of cycles (about 10) so the loop overhead was actually significant.

I agree it's not something you'd expect in a normal business software application.

But it is not all you did? I would imagine you needed to ensure the code and data was nicely aligned and didn't cross page/cache boundaries, etc. etc.. It essentially ended up a very hand crafted affair, and most of what you did is contrary to what the 'books' say.

My point is that the theoretical model of a computer taught on CompSci courses is so far from reality, that the schools build their courses and education on a theoretical model that is so borked, that they then teach things that are not only wrong, but exactly the opposite of what happens in the real world. And that without real lab experience like you have in real science and engineering disciplines you eventually end up with these people behind building the totally screwed IT systems you meet at clients.

At a client they had this parallel application. They'd hand un-rolled loops and done all sorts, and it was getting slower and slower. This was blamed on the extra features that'd been added at the same time...

I rolled them loops up, and the thing started running super-linear.

Then we're into, can you prove it in 'O notation'. It's like, err, how's about trying the 'stopwatch method'?

[OwlHoot]

I had some plonker try and tell me 'loop unrolling' was a good way to up the speed of this application we were looking at.

I enquired if they'd ever actually really tried it... Of course not.

So with my "let me show you what experience is" hat on, flicked the compile flag, recompiled, run, and, lo and behold, it slowed everything right down.

Turned out it was some tulip they were taught on their degree about improving performance.

Give me strength! They don't half teach some flipping rubbish on these computer science courses.

A lot depends how large the caches are, whether they be memory v. disk or, at a lower level address translation caches and prefetch caches etc.

[d000hg]

Exactly. Usually. Not always... sometimes unrolling or employing SIMD ops (which compilers still suck at) are effective. Sometimes very effective, in the SIMD case. But only after profiling.

[Scary]

It's usually better to let the compiler (optimiser) decide. You should be able to tell it whether you prefer space or speed too.

[d000hg]

It does work in the right places. I used it on a tight inner loop for a 3D render engine that was looping through every pixel on the screen many times a second. Of course, the code inside the loop was absolutely optimised to minimise the number of cycles (about 10) so the loop overhead was actually significant.

I agree it's not something you'd expect in a normal business software application.

[threaded]

I had some plonker try and tell me 'loop unrolling' was a good way to up the speed of this application we were looking at.

I enquired if they'd ever actually really tried it... Of course not.

So with my "let me show you what experience is" hat on, flicked the compile flag, recompiled, run, and, lo and behold, it slowed everything right down.

Turned out it was some tulip they were taught on their degree about improving performance.

Give me strength! They don't half teach some flipping rubbish on these computer science courses.