Hacker News Reader

Comment by atq2119 | Hacker News Reader

Neat, though they look unoptimized at a glance. For example, I'd expect the strlen loop to be rotated so that there is only a single backwards branch instruction per iteration. Basically, you want the loop structure to be:

        count = 0
        goto check
    body:
        count++, ptr++
    check:
        if *ptr != 0 goto body

(The initial jump could be a copy of the check instead)

View on HN

  > count++, ptr++

Also, you should avoid this; it adds a extra addition per iteration for no real benefit. Try:

    p = ptr - 1  # also avoid branching[0] over p++
  body:
    p++
    if *p != 0 goto body
    return p - ptr

0: I assume a single addition is cheaper than a unconditional branch, which is probable, but not nearly as big a difference as with conditional branches.

GCC did something like this to one of my loops last month and it took me about half an hour to figure out what was going on.

Simplified, the loop was something like this:

    for (int j = 0; j != 5000; j++) {
        foo();

        if (bar()) {
            baz();
        } else {
            quux();
        }

        corge();
    }

The straightforward way to compile this is as follows:

        j = 0
    1:  if (j == 5000) goto 2
        foo()
        t = bar()
        if (!t) goto 3
        baz()
        goto 4
    3:  quux()
    4:  corge()
        j++
        goto 1
    2:

Imagine my surprise when I found that GCC had instead emitted the equivalent of the following:

        j = 0
        goto 6
    3:  quux()
    4:  corge()
        j++
        if (j == 5000) goto 2
    6:  foo()
        t = bar()
        if (!t) goto 3
        baz()
        goto 4
    2:

It took me a while to understand what was going on, though you can work out that the two are equivalent. Note that the straightforward version runs 9 “instructions” each iteration when bar() is true and 8 when bar() is false. But the optimized version runs 8 when bar() is true and 7 when bar() is false.

By rotating the loop to put the two-branched if-else conditional at the end, as you explain, you get the jump back to the top for free! (The extra jump is still there, but it's executed once, to enter the loop, instead of on every iteration.) And in this case this might matter significantly because the whole inner loop was only 12 instructions, so it might be speeding the whole program up by a measurable percentage.

That said, it's probably better to start by teaching people the straightforward version.

(The program was http://canonical.org/~kragen/sw/dev3/kmregion.h, a simple arena allocator about 10× faster for small allocations than malloc/free, if you're curious.)

They’re for teaching sophomores, so I don’t think optimizations would help.

Reply on news.ycombinator.com