Counting up vs. counting down

http://www.tedunangst.com/flak/post/counting-up-vs-counting-down

by ingve • 11 years ago

22 42 11 years ago

vog2• 11 years ago

There is a mistake in the code

    for (size_t i = numBurritos - 1; i >= 0; i++)
        if (wantBurrito(i))
            break;

Apart from the didactic bug that i >= 0 is always true for size_t, this is supposed to count down, so i++ should be replaced with i--:

    for (size_t i = numBurritos - 1; i >= 0; i--)
        if (wantBurrito(i))
            break;

tbirdz3• 11 years ago

Or, just use iterators.

random778• 11 years ago

Eh?

vog2• 11 years ago

That comment doesn't make any sense to me. Did I missing something?

There are iterators in C++, but not in C.

masklinn4• 11 years ago

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)

tbirdz3• 11 years ago

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.

alblue• 11 years ago

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 ...

gpvos• 11 years ago

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.

knodi1232• 11 years ago

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?

cperciva4• 11 years ago

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.

Lagged2Death2• 11 years ago

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.

Retric• 11 years ago

Technically no language was specified, so depending on specific casting rules is risky. This could easily just throw a compilation error.

eximius• 11 years ago

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').

scj2• 11 years ago

There's a more concise way of iterating in reverse.

  for (size_t i = numBurritos; i-- > 0;)
    if (wantBurrito(i))
      break;

Where an advantage is that many assembly languages have a "jump if zero" or "jump if not zero" instruction.

EDIT: It appears the article has been updated to reflect this method.

efaref• 11 years ago

I've seen this referred to as the "goes-to" operator:

    size_t i = num_burritos;
        while (i --> 0)           // Read: while 'i' goes to zero
            if (want_burrito(i))
                break;

While it sounds nice, I don't think it's a good idea.

Clearly the correct solution is to use a better language, e.g.:

    return next((burrito for burrito in reversed(burritos) if burrito.wanted()), None)

shogun21• 11 years ago

Code readability trumps cleverness.

notacoward2• 11 years ago

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.

pmikesell• 11 years ago

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.

Zikes• 11 years ago

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.

notacoward2• 11 years ago

True, that part's still a potential problem. I often avoid it with something like this (which I believe is more clear anyway).

   i = arraylength;
   while (i-- > 0)

In other cases it really does make more sense to count up. Another unconsidered possibility is that the "found" case might actually return from an iterator function, so you can put the "not found" case after the loop regardless of which way you're counting.

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.

cperciva4• 11 years ago

    for (size_t i = numBurritos - 1; i != -1; i--)

This will fail on a platform where sizeof(size_t) < sizeof(int). I admit that I don't know of any such platform, but I can't see any reason why it wouldn't be possible.

A better way to write this is

    for (size_t i = numBurritos - 1; i < numBurritos; i--)

phkahler• 11 years ago

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.

cperciva4• 11 years ago

Many 64-bit platforms have 32-bit int.

iamsohungry2• 11 years ago

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.

scj2• 11 years ago

The overflow flag is what you're looking for.

iamsohungry2• 11 years ago

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.

Double_Cast• 11 years ago

One solution is to make both bounds explicit, like set-builder notation would.

  for (size_t i = numBurritos - 1; 0 <= i && i < numBurritos; i--)

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.

rasz_pl• 11 years ago

I wonder if counting down messes up with efficient caching.

SamReidHughes2• 11 years ago

I've had great success with this solution:

    for (size_t i = n; i > 0; ) {
        i--;
        ...
    }

I'd have gone with "i-- > 0" if I wasn't feeling out the consequences of trying to avoid all integer overflow, though.

Counting up vs. counting down

Related Stories