Simple function inlining with Go generate and “inliner”

[Steven Wiley]

Hi all,

One of the attractions of Go is its speed. However, in order to maximize speed in critical blocks, from time to time I have had to inline functions by hand, and that means typing in repetitious code, which is hard to read, maintain, and get right in the first place.

After reading Rob Pike's blog entry on the new generate tool, I decided write a program, “inliner”, that can be used with generate to inline functions, and potentially produce code that no sane programmer would want to type in by hand. While I was at it, I also added a feature to unwind simple static integer loops, and a mechanism for 'smart' easy to read assertion statements.

Inliner can be found on here: https://github.com/srwiley/Inliner

I am aware that this might overlap with other efforts to introducing some kind of template facility to the language, usually in the context of generics. However, function inlining and loop unwinding by this method starts with syntactically correct Go code that produces the same result as the inlined version, just usually not as fast. So, (unlike the assertion feature), it does not create a sub-dialect of Go. The speed increases can be significant, as shown by the results of test benchmarks:

Benchmark1_2xLocalNotInlined 3000000 411 ns/op

Benchmark1_2xLocalInlined 30000000 48.2 ns/op

Benchmark2_2xLoopedNotInlined 1000000 2330 ns/op

Benchmark2_2xLoopedInlined 1000000 1489 ns/op

Benchmark2_2xLoopedUnwound 10000000 206 ns/op

Benchmark3_1xLoopNotUnwound 10000000 147 ns/op

Benchmark3_1xLoopUnwound 30000000 48.6 ns/op

Benchmark4_2xLoopNotUnwound 20000000 79.7 ns/op

Benchmark4_2xLoopUnwound 200000000 9.57 ns/op

More details can be found in the readme file, but here is a simple example inlining a local function. Notice that the inlined function name, “bar_” ends with an underscore. This tells inliner to attempt to inline the function.

Source:

func Foo() {
 sum := 0.0
 bar_ := func(x float64) {
    sum *= x
 }
 bar_(1.0)
 bar_(2.0)
 bar_(3.0)
 fmt.Println("sum:", sum)
}

Inlined:

func Foo() {
 sum := 0.0
 /* bar_ := func(x float64) {
 sum *= x
 } /* inlined func */
 sum *= (1.0) // inlined bar_(1.0)
 sum *= (2.0) // inlined bar_(2.0)
 sum *= (3.0) // inlined bar_(3.0)
 fmt.Println("sum:", sum)
}

More complex examples, tests, and benchmarks can be found in the testfiles folder in the repository. Inliner uses the Go “ast” package to parse the source code and can handle nested functions, loops, and code blocks. It will perform multiple passes through the code until all inlines are resolved.

C language has an inline keyword, which by my understanding is a compiler hint. Using inliner and generate, you can be sure that your function will really be inlined, so it gives the programmer the freedom to write succinct, but inefficient code in the most time critical loops, with assurance that it will generate ugly repetitious but efficient code.

Thoughts anyone?

[pierre...@gmail.com]

Good work, I have been thinking about something like this too when I realised that Go sometimes does not inline what I think would be inlinable.

[Johann Höchtl]

Actually the go implementation inliner/optimizer should be much smarter (what code does gcc produce?) and, for a reason or the other, the designers of golang decided against macros.
 

[Steven Wiley]

Thanks for the complement Pierre.

Yes, Johann, I agree that some of this stuff the compiler can and probably will do. I am not sure about what the code actually complies to. I'm not really that much of an assembly person, so I just go by benchmarks. But I do know that in real world physical simulation examples inlining can be a big help, at least for now. But this way it is clear to the coder what is being inlined and what is not. After a brief glance at some of the C blogs, they seem to still be arguing about what the inline keyword really should do. 

Also this way is that it does not require that templates be added to the code. Once the compiler catches up, you just have to remove the build directives and you are good to go. I agree with the idea of keeping templates out of the language itself, unless a really clean solution can be found.

But having said that, probably the most commonly useful feature of inliner, asserts, does break Go syntax, but it is just something that I find myself wanting to type all of the time. In effect the assert feature is adding two new keywords, "affirm_" and "deny_". Affirm_ checks that a boolean is true, or that the argument is not nil. Deny_ does the opposite. In event of failure, the default action is return, but if a second string argument is present, that is what is executed, so breaks and continues are possible also:

Source:

// The expected sum is 100 after all the breaks and continues

func runAssertFlowTest() (sum int) {

    var numStr []string

    sum = 5

loop:

    for i := 0; i < 16; i++ {

        deny_(i == 10, "continue")

        numStr = append(numStr, strconv.Itoa(i))

        affirm_(numStr)

        deny_(i == 14, "break loop")

    }

    affirm_(len(numStr) == 14)

    for _, s := range numStr {

        n, err := strconv.Atoi(s)

        deny_(err, "break")

        affirm_(n >= 0)

        sum += n

    }

    return

}

Inlined:

// The expected sum is 100 after all the breaks and continues

func runAssertFlowTest() (sum int) {

    var numStr []string

    sum = 5

loop:

    for i := 0; i < 16; i++ {

        /* deny_(i == 10, "continue") /* inlined assert */

        if i == 10 {

            continue

        } /* */

        numStr = append(numStr, strconv.Itoa(i))

        /* affirm_(numStr) /* inlined assert */

        if numStr == nil {

            return

        } /* */

        /* deny_(i == 14, "break loop") /* inlined assert */

        if i == 14 {

            break loop

        } /* */

    }

    /* affirm_(len(numStr) == 14) /* inlined assert */

    if (len(numStr) == 14) == false {

        return

    } /* */

    for _, s := range numStr {

        n, err := strconv.Atoi(s)

        /* deny_(err, "break") /* inlined assert */

        if err != nil {

            break

        } /* */

        /* affirm_(n >= 0) /* inlined assert */

        if (n >= 0) == false {

            return

        } /* */

        sum += n

    }

    return

}

The source just makes for cleaner code, IMHO. Unfortunately, I cannot think of an alternative in straight Go that does not involve typing a lot of if loops or doing something less straight forward.