Counting up vs. counting down(tedunangst.com)
tedunangst.com
Counting up vs. counting down
http://www.tedunangst.com/flak/post/counting-up-vs-counting-down
11 comments
There is a mistake in the code
for (size_t i = numBurritos - 1; i >= 0; i++)
if (wantBurrito(i))
break;
for (size_t i = numBurritos - 1; i >= 0; i--)
if (wantBurrito(i))
break;There's a more concise way of iterating in reverse.
EDIT: It appears the article has been updated to reflect this method.
for (size_t i = numBurritos; i-- > 0;)
if (wantBurrito(i))
break;
EDIT: It appears the article has been updated to reflect this method.
I've seen this referred to as the "goes-to" operator:
Clearly the correct solution is to use a better language, e.g.:
size_t i = num_burritos;
while (i --> 0) // Read: while 'i' goes to zero
if (want_burrito(i))
break;
Clearly the correct solution is to use a better language, e.g.:
return next((burrito for burrito in reversed(burritos) if burrito.wanted()), None)While counting up instead of down does allow the use of "i >= arraylength" construct to check whether an item was found, it's still not as clear as using an explicit "found" boolean. Once you do that, it doesn't matter whether you count up or down. Also, Python's for...else construct is nice for this sort of thing.
Fun fact: I usually count down unless there's a code-specific reason to count up. It's one of the biggest "tells" that I wrote a piece of code, and it exists because I'm old enough to have worked with compilers stupid enough that they really did produce more efficient code that way. Nowadays I wouldn't generally recommend it, because AFAIK nobody has made a production-level compiler that dumb for quite a while.
Fun fact: I usually count down unless there's a code-specific reason to count up. It's one of the biggest "tells" that I wrote a piece of code, and it exists because I'm old enough to have worked with compilers stupid enough that they really did produce more efficient code that way. Nowadays I wouldn't generally recommend it, because AFAIK nobody has made a production-level compiler that dumb for quite a while.
The common counting down problem he's referring to is where an unsigned iterator can never be <0, so it introduces an infinite loop. Setting a found boolean does nothing to alleviate that situation.
Additionally, "found" may never be true if you don't find what you're looking for. Instead, you would want a boolean for whether or not you've searched all array elements.
True, that part's still a potential problem. I often avoid it with something like this (which I believe is more clear anyway).
The "counting down can cause an infinite loop" problem does exist, but I've also seen cases where counting up can fail too (e.g. index incremented twice within a loop either accidentally or deliberately), or where confusion of whether to use "i" or "i-1" caused bugs. It's probably even easier for a static analyzer to catch a counting-down bug than a counting-up bug, so I'm not really sure that a preference for counting up is all that helpful.
i = arraylength;
while (i-- > 0)
The "counting down can cause an infinite loop" problem does exist, but I've also seen cases where counting up can fail too (e.g. index incremented twice within a loop either accidentally or deliberately), or where confusion of whether to use "i" or "i-1" caused bugs. It's probably even easier for a static analyzer to catch a counting-down bug than a counting-up bug, so I'm not really sure that a preference for counting up is all that helpful.
Code readability trumps cleverness.
The infinite loop on unsigned integers exemplifies a failure in C's type system: integer wraparound is so rarely desirable behavior that a range error on wraparound would prevent many such errors from failing silently.
There's an argument to be made that this check would hurt performance (and I buy that argument--given C's goals and the time when it was made, the type system compromises it made make sense). But it would be nice if processor manufacturers made add/sub instructions that detected wraparound, which would allow languages to implement such checks performantly.
There's an argument to be made that this check would hurt performance (and I buy that argument--given C's goals and the time when it was made, the type system compromises it made make sense). But it would be nice if processor manufacturers made add/sub instructions that detected wraparound, which would allow languages to implement such checks performantly.
The overflow flag is what you're looking for.
But checking this flag takes another instruction, no? I'm thinking more along the lines of some sort of interrupt being thrown automatically if the operation overflows.
for (size_t i = numBurritos - 1; i != -1; i--)
A better way to write this is
for (size_t i = numBurritos - 1; i < numBurritos; i--)I seriously wonder what's wrong with using an int and the original count down construct. You have to think about it on 16 or 32 bit platforms, but this statement from the link:
>> Especially consider the case of an index into a string (char *) on a 64 bit platform. size_t is the appropriate type for an index because the limited range of int is not nearly enough.
That's just bull in most applications. Even if you could run 1 trillion iterations per second, the loop would take 2^23 seconds to complete or about 97 days. In general if you're not doing "big data" and int will index an array just fine thank you. And that's indexing bytes, it should index any other type just fine in any case - assuming of course that a pointer and int are the same size.
>> Especially consider the case of an index into a string (char *) on a 64 bit platform. size_t is the appropriate type for an index because the limited range of int is not nearly enough.
That's just bull in most applications. Even if you could run 1 trillion iterations per second, the loop would take 2^23 seconds to complete or about 97 days. In general if you're not doing "big data" and int will index an array just fine thank you. And that's indexing bytes, it should index any other type just fine in any case - assuming of course that a pointer and int are the same size.
Many 64-bit platforms have 32-bit int.
I've had great success with this solution:
for (size_t i = n; i > 0; ) {
i--;
...
}
The terminal operation on the clever code compares the size_t to -1. But if it's unsigned this will never be true either, and so the test may be optimised away.
This probably demonstrates the point where clever code is more likely to have bugs ...
This probably demonstrates the point where clever code is more likely to have bugs ...
But if it's unsigned this will never be true either...
Conceptually, it works through promotion. -1 is cast to unsigned/size_t before the test, which then succeeds. At the assembly level, a 32-bit -1 is 0xFFFFFFFF, which is also the result of the underflow of i, so it works at that level, too.
At any rate, it worked in the compiler I tried it with.
Conceptually, it works through promotion. -1 is cast to unsigned/size_t before the test, which then succeeds. At the assembly level, a 32-bit -1 is 0xFFFFFFFF, which is also the result of the underflow of i, so it works at that level, too.
At any rate, it worked in the compiler I tried it with.
Are you really sure? I think the -1 will be coerced to unsigned int, instead of the other way around. That would make it work.
what does it mean for -1 to be coerced into something unsigned? Wouldn't that be equivalent to 1?
I, too, fail to understand how this is clever. Can someone enlighten me?
I, too, fail to understand how this is clever. Can someone enlighten me?
`-1` will underflow, so you'll effectively have a SIZE_MAX. The counting down will similarly underflow, reach SIZE_MAX and stop the iteration.
Wouldn't it be clearer to just put `i != SIZE_MAX` then? I understand that anyone experienced with C probably wouldn't be confused by this, but you might as well sacrifice a couple characters in exchange for saving brain cycles, right?
I don't know if it'd be clearer. It'd be a better representation of what actually happens but would read very strangely. `!= -1` would make a reader think "shouldn't go below 0" and only on closer inspection would you wonder what actually happens, `!= SIZE_MAX` would probably make any reader stop and scratch their head.
Whether that's a good thing is up for debate.
Whether that's a good thing is up for debate.
if you are thinking about "<0" on an unsigned type, you better be scratching your head already.
I'd expect anyone experienced with C would say that making such casual, deliberate use of the underflow for such a trivial purpose is pretty foolish, the mark of a developer too clever for his own good. I thought the author was perhaps suggesting this with sarcasm: "Wizened sourcerers" and "full clever." But maybe not.
C's variable promotion system is invisible and silent and in my experience a frequent source of bugs in exactly this case (tests in for loops), which is why there's enough meat here for a blog post. It's usually easy to avoid the promotion issue by using the same type for the loop variable and its test condition. In cases like this, sometimes it's better to just use a straightforward and obvious while() loop instead of a correct but tortured for() loop. That makes the relationship between the loop variable updates and the loop body controllable and explicit.
C's variable promotion system is invisible and silent and in my experience a frequent source of bugs in exactly this case (tests in for loops), which is why there's enough meat here for a blog post. It's usually easy to avoid the promotion issue by using the same type for the loop variable and its test condition. In cases like this, sometimes it's better to just use a straightforward and obvious while() loop instead of a correct but tortured for() loop. That makes the relationship between the loop variable updates and the loop body controllable and explicit.
In C++, underflows of unsigned types are specified in the Standard. -1 is equivalent to the largest value your unsigned type can hold. This means that you can rely on this behaviour.
It depends on the relative sizes of size_t and int. If size_t is at least as large as int, the coercion goes in favour of size_t.
As everyone has so aptly explained, it probably will work. But it is certainly not obvious that it works and should probably be avoided (unless you are a 'wizened sorcerer').
Or, just use iterators.
That comment doesn't make any sense to me. Did I missing something?
There are iterators in C++, but not in C.
There are iterators in C++, but not in C.
Iterators are a technique and are not bound to any particular programming language. Iterators abstract the idea of iterating through data. Instead of keeping track of the array index and thinking of it in terms of counting up or down, you instead create an iterator that will abstract this for you. You can create iterators to traverse the array in forward, backwards, every odd number, whatever way you want. Then you write your client code to operate on an iterator, and so completely separate the traversal of the sequence from the action to be performed on each element. Another useful abstraction in this context are list comprehensions (map, filter, reduce, etc.).
You can create iterators in any language, and I was referring to the abstract concept of iterators, not the particular form of iterators found in C++'s standard library.
You can create iterators in any language, and I was referring to the abstract concept of iterators, not the particular form of iterators found in C++'s standard library.
Sure, you can write iterators in C, but nobody wants to drag all that complexity just for a reverse loop. In a language like Python of course, iterators are native and idiomatic.
The complexity is already there, iterators just help you manage it better. Even "just a reverse loop" is more complex than you might think, as evidenced by the article above.
How do they help you manage it better in C?
The article uses C examples but a more general language for the title and text, so if iterators are available in the language "use iterators" is in fact an excellent way to handle it (and you can probably build C iterators, though I don't know how convenient and efficient they'd be)
Eh?
I wonder if counting down messes up with efficient caching.
But this loops infinitely if sizeof(numBurritos) == sizeof(size_t) where size_t is unsigned, because the entire space of possible values returns True. This failure mode exists whether we increment or decrement over unsigned values.
The root problem here isn't decrementing. The root problem is the unsigned value. So maybe it's best practice to use signed values whenever possible. This way, the existence of negative values guarantees the existence of a sentinel.