Problem and solution [LWN.net]

Problem and solution

Posted Apr 5, 2008 12:08 UTC (Sat) by emk (subscriber, #1128) [Link]

It took me a second, too, because it's using a strange (incorrect) looping idiom. Here, size_t is an unsigned type, so it can never be negative. If i == 0, and you write --i, it wraps around to a huge positive value. To fix it, try:

while (i > 0) {

Thanks to the unsigned nature of size_t, it's surprisingly hard to loop backwards over STL vectors without tripping over this bug. You could choose to use reverse iterators, which are clunky but safer:

vector<MyThingy>::const_reverse_iterator iter = stuff.rbegin();
for (; iter != stuff.rend(); ++iter) {
    /* do something with */ *iter;
}

Also, I have no idea why the original function returns i. Was there a break somewhere in the original loop? Without one, i would always equal 0 (assuming the loop terminated successfully).

Problem and solution

Posted Apr 6, 2008 12:55 UTC (Sun) by olecom (guest, #42886) [Link]

> while (i > 0) { stuff[--i];
when using predecrement, use

i=max+1; do { --i; } while(i);

Problem and solution

Posted Apr 6, 2008 13:20 UTC (Sun) by olecom (guest, #42886) [Link]

> > while (i > 0) { stuff[--i];
> when using predecrement, use
>
> i=max+1; do { --i; } while(i);

Also beware on input!

max -- is maximum linear address
i   -- geek counter, counts downto zero including;
       thus, number of loops is (max + 1)

better is to have *all* counts downto zero,
i.e. zero address access and

i = max /* number of loops is (max + 1) */
do {
  /* use */ stuff[i];
} while (--i);

Problem and solution

Posted Apr 6, 2008 15:20 UTC (Sun) by man_ls (subscriber, #15091) [Link]

What if the array is empty? You would be doing one iteration, while the above idiom (while (i>0) {--i;}) skips the loop and works fine.

Problem and solution

Posted Apr 7, 2008 5:11 UTC (Mon) by olecom (guest, #42886) [Link]

> What if the array is empty?

Same thing -- check your input. `if' for check, `while' for loop/iterations.

Mixing the two isn't a good thing, worst optimization ever.
_____

Problem and solution

Posted Apr 7, 2008 6:17 UTC (Mon) by man_ls (subscriber, #15091) [Link]

It depends. Quite often it doesn't matter much, and the compact version can be better (at least it takes less time to write). You know what they say about premature optimization, don't you?

By the way, with Java your best optimization is to write while (i != 0) instead of while (i > 0), because otherwise the JVM will perform arithmetic comparisons instead of logical. (Yes, it is pitiful.) I believe they have fixed it now, but it would be nice to know for sure.

just correct loops (Problem and solution)

Posted Apr 7, 2008 8:28 UTC (Mon) by olecom (guest, #42886) [Link]

> It depends. Quite often it doesn't matter much, and the compact version
> can be better (at least it takes less time to write).

All was about decrement-after-check access in the loop.

> You know what they say about premature optimization, don't you?

Those loops are quite fine for me, YMMV.
BTW, i'm in to system programming, so i don't know what Java is, really .:)

-- 
sed 'sed && sh + olecom = love' << ''
-o--=O`C
 #oo'L O
<___=E M

Problem and solution

Posted Apr 10, 2008 15:13 UTC (Thu) by DennisJ (subscriber, #14700) [Link]

Supposing a signed type had been used for the counter, and nothing changed to the loop
condition, the last pass through the loop would have done something to stuff[-1] which is also
unlikely to be what the author wanted.

So isn't 'while(i>0)' the correct solution following an incorrect analysis?