470,815 Members | 1,738 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 470,815 developers. It's quick & easy.

unrolling nested for-loop

V
Hello:

Consider the following nested for loop:

uint64 TABLE[8][256];

for (i=0; i<=7; i++)
for (j=1; j<=7; j++)
for (k=1; k<=(1<<j)-1; k++)
TABLE [i][((1<<j)+k)] = (TABLE[i][(1<<j)]) ^ (TABLE[i][k]);

I understand that unrolling just the inner most for-loop would give me
best performance and this is required for my project. But I'm unable
to figure out how to unroll just the innermost for-loop.

Can someone please help!

Thanks!
Jun 27 '08 #1
9 3383
V wrote:
Hello:

Consider the following nested for loop:

uint64 TABLE[8][256];
Better to use standard types, uint64_t.

All caps for variable names isn't a good idea, all caps is usually used
for macros.
for (i=0; i<=7; i++)
for (j=1; j<=7; j++)
for (k=1; k<=(1<<j)-1; k++)
TABLE [i][((1<<j)+k)] = (TABLE[i][(1<<j)]) ^ (TABLE[i][k]);

I understand that unrolling just the inner most for-loop would give me
best performance and this is required for my project. But I'm unable
to figure out how to unroll just the innermost for-loop.
Have you profiled the code?
Can someone please help!
Your compiler probably can. Loop unrolling is a common optimisation.
Check the assembly output for your code with various optimisation settings.

--
Ian Collins.
Jun 27 '08 #2
V
I have tried to use compile time option to unroll this and checked its
assembly code, but it doesn't seem to have unrolled the loop.

Any suggestions?

Thanks.
Jun 27 '08 #3
V wrote:
I have tried to use compile time option to unroll this and checked its
assembly code, but it doesn't seem to have unrolled the loop.

Any suggestions?
A better compiler?

The most important thing to do is to profile your application and see if
there really is a bottleneck in this code. At the moment, manual
unrolling of this loop looks like premature micro-optimisation.

If there is an issue and your compiler isn't up the job, just repeat the
inner assignment N times and change the inner loop to increment its
counter by N. This assumes the limit is a multiple of N. Something
like (untested)

for (k=1; k<=(1<<j)-1; k += 2)
{
TABLE [i][((1<<j)+k)] = (TABLE[i][(1<<j)]) ^ (TABLE[i][k]);
TABLE [i][((1<<j)+k+1)] = (TABLE[i][(1<<j)]) ^ (TABLE[i][k+1]);
}

--
Ian Collins.
Jun 27 '08 #4
On May 10, 7:44*am, V <vishal.st...@gmail.comwrote:
I have tried to use compile time option to unroll this and checked its
assembly code, but it doesn't seem to have unrolled the loop.

Any suggestions?

Thanks.
I'm not surprised. The inner loop is very complicated. Is there any
way of simplifying it?

Perhaps a rethink of what you're trying to achieve might help.

What factor of speedup do you need?

--
Bartc
Jun 27 '08 #5
Bart wrote:
On May 10, 7:44 am, V <vishal.st...@gmail.comwrote:
>I have tried to use compile time option to unroll this and checked its
assembly code, but it doesn't seem to have unrolled the loop.

Any suggestions?

Thanks.

I'm not surprised. The inner loop is very complicated. Is there any
way of simplifying it?
The first compiler I tried was happy to unroll the loop, it's not that
hard (for a machine!).

--
Ian Collins.
Jun 27 '08 #6
Antoninus Twink wrote:
On 10 May 2008 at 8:02, Ian Collins wrote:
>This assumes the limit is a multiple of N. Something like (untested)

for (k=1; k<=(1<<j)-1; k += 2)
{
TABLE [i][((1<<j)+k)] = (TABLE[i][(1<<j)]) ^ (TABLE[i][k]);
TABLE [i][((1<<j)+k+1)] = (TABLE[i][(1<<j)]) ^ (TABLE[i][k+1]);
}

This fails when j=1.
I know, that why I said "This assumes the limit is a multiple of N", N
== 2 in this case.

--
Ian Collins.
Jun 27 '08 #7
On May 10, 12:35*pm, Ian Collins <ian-n...@hotmail.comwrote:
Bart wrote:
On May 10, 7:44 am, V <vishal.st...@gmail.comwrote:
I have tried to use compile time option to unroll this and checked its
assembly code, but it doesn't seem to have unrolled the loop.
Any suggestions?
Thanks.
I'm not surprised. The inner loop is very complicated. Is there any
way of simplifying it?

The first compiler I tried was happy to unroll the loop, it's not that
hard (for a machine!).
Looking at the code again, it just initialies a 2048-element table (of
64-bit values).

If that's all it ever does, then it only needs to be done once, and
speed should not be an issue.

I think more context is needed.

--
Bartc
Jun 27 '08 #8
Bart wrote:
) Looking at the code again, it just initialies a 2048-element table (of
) 64-bit values).

Not quite. If you look closer you will see that it depends on the first
elements of each of the 8 arrays.

However, unrolling the outermost loop might improve efficiency
because it is a constant (8-fold) unrolling and could give rise to better
pipelining.
SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
Jun 27 '08 #9
V wrote:
) Hello:
)
) Consider the following nested for loop:
)
) uint64 TABLE[8][256];
)
) for (i=0; i<=7; i++)
) for (j=1; j<=7; j++)
) for (k=1; k<=(1<<j)-1; k++)
) TABLE [i][((1<<j)+k)] = (TABLE[i][(1<<j)]) ^ (TABLE[i][k]);
)
) I understand that unrolling just the inner most for-loop would give me
) best performance and this is required for my project. But I'm unable
) to figure out how to unroll just the innermost for-loop.

In this case, it may be that unrolling the outermost loop would be best,
because the inner to loops don't depend on the outer.

(I took the liberty of adding another peephole optimization in how
j is used, even though the compiler should recognize it by itself)

for (j=2; j<=128; j<<=1) {
for (k=1; k<=j-1; k++) {
TABLE[0][j+k] = TABLE[0][j] ^ TABLE[0][k]
TABLE[1][j+k] = TABLE[1][j] ^ TABLE[1][k]
/* ... */
TABLE[7][j+k] = TABLE[7][j] ^ TABLE[7][k]
}
}

This has the added advantage of removing a level of indirection in
the table accesses, because TABLE[0] through TABLE[7] now are constant.
SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
Jun 27 '08 #10

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

reply views Thread by Glen | last post: by
34 posts views Thread by Jacek Generowicz | last post: by
6 posts views Thread by Andy Baker | last post: by
8 posts views Thread by Robert W. | last post: by
7 posts views Thread by patrick j | last post: by
3 posts views Thread by jdurancomas | last post: by
5 posts views Thread by Calvin Spealman | last post: by
3 posts views Thread by Cousson, Benoit | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.