1

Say you have a bunch of nested loops.

public void testMethod() {
    for(int i = 0; i<1203; i++){
                //some computation
        for(int k=2; k<123; k++){
                        //some computation
            for(int j=2; j<12312; j++){
                                //some computation
                for(int l=2; l<123123; l++){
                                        //some computation
                    for(int p=2; p<12312; p++){
                            //some computation
                    }
                }
            }
        }
    }

}

When the above code reaches the stage where the compiler will try to optimize it (I believe it's when the intermediate language needs to converted to machine code?), what will the compiler try to do? Is there any significant optimization that will take place?

I understand that the optimizer will break up the loops by means of loop fission. But this is only per loop isn't it? What I mean with my question is will it take any action exclusively based on seeing the nested loops? Or will it just optimize the loops one by one?

If the Java VM complicates the explanation then please just assume that it's C or C++ code.

4
  • Sharing your research helps everyone. Tell us what you've tried and why it didn’t meet your needs. This demonstrates that you’ve taken the time to try to help yourself, it saves us from reiterating obvious answers, and most of all it helps you get a more specific and relevant answer. Also see How to Ask – gnat May 29 '14 at 11:04
  • 1
    @gnat I understand that the optimizer will break up the loops by means of loop fission. But this is only per loop isn't it? What I mean with my question is will it take any action exclusively based on seeing the nested loops? Or will it just optimize the loops one by one? – Force444 May 29 '14 at 11:12
  • 2
    It cannot generalize the use of a loop, since an inner loop may not always happen the same amount of times or be subjected to the same condition each time, therefore it doesn't optimize from this point of view. However it does convert loop variables to register variables like the C++ compiler. – Neil May 29 '14 at 11:27
  • I hope you understand that the inner loop is the only one worth optimizing, and only if some computation inside it does almost nothing. Optimizing has benefit in code only to the proportion that the program counter actually spends time in it. Of course, compilers do a lot of unnecessary optimization. – Mike Dunlavey May 29 '14 at 13:16
2

An optimising compiler generally works on the basis that the innermost loop is the only one worth the effort. The strategies for optimising loops include unrolling, vectorisation, hoisting (calculations out of the loop), and so on. It may also change the code if it can determine that the loop will terminate early, or not at all. None of these are specific to nested loops.

The only optimisations I know of that are specific to nested loops are these.

  1. Loop exchange/inversion. for(x...){for(y...){...}} can be inverted into for(y...){for(x...){...}} if the compiler can determine that it is (a) equivalent (b) faster or (c) can be made faster.
  2. Vectorisation applied to the inner loop may be extended to vectorise multiple loops, depending on the instruction set available.
  3. If the inner loop can be unrolled or vectorised or deleted then the next loop becomes the inner loop, and is subject to the same optimisations.
  4. If an expression can be hoisted out of an inner loop, it can perhaps be hoisted further.

It's not easy to know which compilers currently implement which if any of these. I know that Fortran compilers were very early implementers of aggressive vectorisation on machines like Cyber and Cray, but I'm not in touch with that now. You would now look at compilers targeting GPUs.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.