CODEWITHSUNDEEP
algorithmloopslanguage-agnostic
Anycorn
Anycorn

Reputation: 51545

efficient loop collapse

in certain applications, I have need to collapse nested loops into one while retaining individual index information. 

for j in N:
  for i in M:
    ... A(i,j) ...

// Collapse the loops
for ij in MN:
  ... A(i,j) ...

so have looked at the obvious ways to recover i,j from ij using division/modulo (expensive operation) and using if statements (breaks vectorization, branch prediction problems).in the end i came up with the following (using C-style comparisons):

j += (i == m)
i *= (i != m)
++i, ++ij

is there perhaps a even better way to do that? thanks

Upvotes: 2

Views: 2191

Answers (3)

Bogi
Bogi

Reputation: 2608

I am not sure why do you want to collapse loops. Make sure the most inner loop has a high trip count (by loop inversion) and make sure your data is sequential in memory. I've seen algorithms run 10 times faster when these two conditions are met.

Upvotes: 0

Will
Will

Reputation: 75673

In general, it offers no performance advantage to collapse the loop as described.

Compilers do sometimes collapse such loops, but typically in unexpected ways.

In particular languages, or on particular platforms, you can speed up loops in general by:

  • counting downwards
  • making the function called in the body 'inline', or having the code in the loop body rather than a separate function
  • configuring the compiler - typically via command-line options - to 'unroll' loops and to remove frame pointers and such

But in all cases you have to have profiled your code to see that such efforts are warranted.

Generally, in my experience, nested loops like this are dominated by:

  1. containers; avoid boxing and bounds checking if possible and you know you're safe
  2. the cost of invoking other methods in them; use 'inline' if thats available
  3. pipeline stalls by bad locality of reference; rearrange your memory if possible
  4. pipeline stalls by second conditions; fewer ifs and indirect references is better

But that might not be applicable advice on your problem domain and platform. Profile!

Upvotes: 8

Luka Rahne
Luka Rahne

Reputation: 10467

Going other way might be cheaper.

for j in N:
  for i in M:
    ij=j*i+j

Upvotes: 0

Related Questions