#28343 - ScottLininger - Fri Oct 29, 2004 10:06 pm
If I have a bit of code like this...
| Code: |
for(loop = 0; loop < 128*4; loop++)
{
// do something
} |
Is the compiler smart enough to replace the multiplication with a constant? (I know... one would simply put a constant in there... without magic numbers... this is kind of an academic question.)
Then what about something like this...
| Code: |
for(loop = 0; loop < myVar*4; loop++)
{
// do something
} |
If a variable used in the comparison is NOT changed anywhere inside the loop, is the compiler smart enough to replace with a constant?
I have a situation like example #2, and I'm wondering if I'd save some cycles by precalculating myVar*4 and putting into a temporary variable... it's just kind of ugly to have an extra line or two of code when it can be done inside the FOR block.
I think I need to learn more about assembly so I can figure this stuff out myself. ;)
-Scott
#28345 - jma - Fri Oct 29, 2004 10:32 pm
As far are 2 constants go -- yes, the compile will "fold" them into the proper constant. As for your variable, it might put the value in a register (if one is available) -- then again, it might not. Consider this, though:
| Code: |
| for(i = 0;i < strlen(some_string);++i) { ... } |
This is terrible code, because the strlen will be executed each iteration of the loop. So, more specifically to your variable multiple question, if "myVar *4" is not put into a register (more importantly the value located at the RAM address that myVar points to), then each iteration a load and a multiply will occur.
Jeff
_________________
massung@gmail.com
http://www.retrobyte.org
#28347 - sajiimori - Fri Oct 29, 2004 11:50 pm
...unless the compiler optimizes it to a shift, since it's a power of 2. If you can't afford a load+shift, then check the compiler output because you're entering the realm of cycle counting.
On the other hand, if the loop body is complicated enough to prevent caching the limit (or better yet inverting the loop), then the load+shift probably wouldn't be your bottleneck anyway.
#28360 - MumblyJoe - Sat Oct 30, 2004 3:29 am
| ScottLininger wrote: |
Then what about something like this...
| Code: | for(loop = 0; loop < myVar*4; loop++)
{
// do something
} |
If a variable used in the comparison is NOT changed anywhere inside the loop, is the compiler smart enough to replace with a constant?
|
Not really, because even if it doesn't change anywhere INSIDE the loop, there is no way for the compiler to know what the value of myVar is when the execution hits the loop, unless myVar is a constant (which I assume it isn't). Having said that, while the compiler can't know the value, it can know that it doesn't change and perform other optimisations.
Also, you can perform some optimisations yourself to allow things like this. If the compiler doesn't optimise correctly for what you want, and still performs the multiplication every time the for loop loops, you can just do the multiplication before the for loop as such:
| Code: |
const int tempval = myVar * 4;
for(loop = 0; loop < tempval; loop++)
{
// do something
}
|
I just tested this theory with this code however:
| Code: |
extern "C" {
void yours()
{
int myVar = 54;
myVar *= 10;
myVar++;
int val;
for(int loop = 0; loop < myVar*4; loop++)
{
val *= 2;
}
}
void mine()
{
int myVar = 54;
myVar *= 10;
myVar++;
int val;
const int tempval = myVar * 4;
for(int loop = 0; loop < tempval; loop++)
{
val*=2;
}
}
}//end of extern "C".
|
And I got this output (thumb code, optimised etc):
| Code: |
.code 16
.file "looptest.cpp"
.text
.align 2
.global yours
.code 16
.thumb_func
.type yours, %function
yours:
push {lr}
ldr r3, .L11
.L5:
sub r3, r3, #1
cmp r3, #0
bne .L5
@ sp needed for prologue
pop {r0}
bx r0
.L12:
.align 2
.L11:
.word 2164
.size yours, .-yours
.align 2
.global mine
.code 16
.thumb_func
.type mine, %function
mine:
push {lr}
ldr r3, .L22
.L17:
sub r3, r3, #1
cmp r3, #0
bne .L17
@ sp needed for prologue
pop {r0}
bx r0
.L23:
.align 2
.L22:
.word 2164
.size mine, .-mine
.ident "GCC: (GNU) 3.4.1"
|
Identical functions, clearly g++ is more clever that I give it credit for :P
Anyway, I'm done ranting, don't think I helped any anyway.
_________________
www.hungrydeveloper.com
Version 2.0 now up - guaranteed at least 100% more pleasing!
#28364 - MumblyJoe - Sat Oct 30, 2004 5:01 am
I just changed the code in my above post to this to make it more interesting:
| Code: |
extern "C" {
int yours(int& myVar)
{
int val = 1;
for(int loop = 0; loop < myVar*4; loop++)
{
val *= 2;
}
return val;
}
int mine(int& myVar)
{
int val = 1;
const int tempval = myVar * 4;
for(int loop = 0; loop < tempval; loop++)
{
val*=2;
}
return val;
}
}//end of extern "C". |
and got this output:
| Code: |
.code 16
.file "looptest.cpp"
.text
.align 2
.global yours
.code 16
.thumb_func
.type yours, %function
yours:
push {lr}
ldr r3, [r0]
lsl r3, r3, #2
mov r2, #1
cmp r3, #0
ble .L7
.L5:
sub r3, r3, #1
lsl r2, r2, #1
cmp r3, #0
bne .L5
.L7:
mov r0, r2
@ sp needed for prologue
pop {r1}
bx r1
.size yours, .-yours
.align 2
.global mine
.code 16
.thumb_func
.type mine, %function
mine:
push {lr}
ldr r3, [r0]
lsl r3, r3, #2
mov r2, #1
cmp r3, #0
ble .L17
.L15:
sub r3, r3, #1
lsl r2, r2, #1
cmp r3, #0
bne .L15
.L17:
mov r0, r2
@ sp needed for prologue
pop {r1}
bx r1
.size mine, .-mine
.ident "GCC: (GNU) 3.4.1" |
So yeah, it turns out that gcc already performs this optimisation (unless myVar is volatile, then you get a crapload of generated code). So pretty much you are right, gcc will optimise the multiplication out of the loop. Also as a bonus, it optimises the multiplications into shifts in this example :P
_________________
www.hungrydeveloper.com
Version 2.0 now up - guaranteed at least 100% more pleasing!
#28366 - sajiimori - Sat Oct 30, 2004 5:22 am
Now if only it realized that the whole loop could be reduced to a single shift, rather than shifting by 1 bit on each iteration...
Anybody seen any instances of a compiler (for any language) replacing a loop (that cannot be proven to iterate less than 2 times) with a constant-time procedure?
#28384 - poslundc - Sat Oct 30, 2004 3:37 pm
| sajiimori wrote: |
| Anybody seen any instances of a compiler (for any language) replacing a loop (that cannot be proven to iterate less than 2 times) with a constant-time procedure? |
I've seen compilers automatically unroll loops before, which I believe GCC is capable of with the -funroll-loops and -funroll-all-loops switches, although I don't believe they are very intelligent in their optimization.
Dan.
#28386 - sajiimori - Sat Oct 30, 2004 5:28 pm
Unrolling a loop can't change an algorithm from O(n) to O(1), it just avoids branches. The earlier example would be O(n) even if the loop were unrolled, because you still have to iterate more times as myVal gets larger.
Of course, if the compiler inlines the earlier code and the argument has a known value, then the whole thing can be replaced with a constant.
So, I should clarify that the number of iterations must be altogether unknown.
#28387 - sgeos - Sat Oct 30, 2004 5:36 pm
| sajiimori wrote: |
| Anybody seen any instances of a compiler (for any language) replacing a loop (that cannot be proven to iterate less than 2 times) with a constant-time procedure? |
Depending on who you use, a human compiler might be able to do it.
-Brendan
#28395 - poslundc - Sat Oct 30, 2004 7:51 pm
| sajiimori wrote: |
| Unrolling a loop can't change an algorithm from O(n) to O(1), it just avoids branches. The earlier example would be O(n) even if the loop were unrolled, because you still have to iterate more times as myVal gets larger. |
You're right, of course, but the trick is in the way you asked the question:
| Quote: |
| Anybody seen any instances of a compiler (for any language) replacing a loop (that cannot be proven to iterate less than 2 times) with a constant-time procedure? |
It doesn't matter if it's iterating more than two times: if it iterates a constant amount then it's already O(1).
Dan.
#28396 - sajiimori - Sat Oct 30, 2004 8:59 pm
I didn't specify that it should be constant, but I neglected to specify that it couldn't be, which is hopefully clear by now.
But really, it should have been clear from the beginning because O(n) has no meaning if there's no n!