cmd/compile: optimize maps with bool keys

[zigo101]

In programming, sometimes it is less verbose by using a map with bool key than using an if-else block. For example:

    if condition {
        counter++
    } else {
        counter--
    }

vs.

var boolToInt = map[bool]int{true: 1, false: 0}
...

    counter += boolToInt[condition]

Or

    if condition {
        f(...)
    } else {
        g(...)
    }

vs.

var boolToFunc = map[bool]func(...){true: f, false: g}
...

    boolToFunc[condition](...)

However, currently, the map form is much less efficient than the if-else block form:

package main

import (
    "testing"
)

func f(x bool) int {
    if x {
        return 1
    } else {
        return 0
    }
}

var m = map[bool]int{true: 1, false: 0}
func g(x bool) int {
    return m[x]
}

var fr, gr int

func Benchmark_f(b *testing.B) {
    for i := 0; i < b.N; i++ {
        fr = f(true)
        fr = f(false)
    }
}

func Benchmark_g(b *testing.B) {
    for i := 0; i < b.N; i++ {
        gr = g(true)
        gr = g(false)
    }
}

Benchmark_f-4       1000000000           0.7478 ns/op
Benchmark_g-4       19250287            60.28 ns/op

Maps with bool keys could contain at most two entries, so I think it will be not hard to make optimizations for them. If this could be implemented, it will be much helpful to improve performance for some Go programs.

[ianlancetaylor]

This isn't an API change, so moving it out of the proposal process. This is a feature request for the compiler.

[davecheney]

Why don’t you want to use the f version? Seems easier than adding edge cases in the map implementation? It would be extremely difficult for the compiler to use constant propogration to optimise g to the point that f has been

btw, I’m pretty confident that f have been optimised into a loop that assigns fr = 0

[zigo101]

Why don’t you want to use the f version?

Verbose, in particular there are many occurrences of such if-else blocks.

The f function is just for benchmark purpose here. In reality, it may be a code snippet and the arguments to its calls may be not constants.

[zigo101]

I admit that we could use small functions to replace the maps, by harming a little gracefulness.

var m = func(condiiton bool) {
    if condition {
        counter++ // or f(...)
    } else {
        counter-- // or g(...)
    }
}

However, it gives people the impression that maps with bool keys are not recommended to be used generally. So I don't think this optimization is an edge case, at least it doesn't belong to the edgest ones. It makes the map use cases more complete.

Though, if it increases the code maintenance cost much, I agree that it should not be implemented.

[davecheney]

However, it gives people the impression that maps with bool keys are not recommended to be used generally.

I don't think this interpretation is incorrect.

[networkimprov]

cc @mdempsky

[zigo101]

If booleans can be converted to integers, or there is simple builtin way to do this, then this optimization will become not very necessary:

var functions = []func(...){g, f}
...

    functions[int(condition])(...)

[networkimprov]

cc @josharian

[mdempsky]

If booleans can be converted to integers, or there is simple builtin way to do this, then this optimization will become not very necessary:

What about:

func BoolToInt(x bool) int {
    v := 0
    if x {
        v = 1
    }
    return v
}

[zigo101]

It is ok and actually often acceptable to use a custom bool-to-int function, though it would be better that Go could provide a cleaner and simpler way.

BTW, the bool-to-int+slice solution is a little less performant than the optimized map-with-bool-key solution, for bound checking reason.

[mdempsky]

If you add &1 to the index expression, the bounds check will go away.

SSA should probably be able to handle bounds checking phi operands though. I imagine there's already a feature request issue for this.

Alternatively, it should be able to recognize that that bool-to-int promotion gives a value in the range [0, 1].

[zigo101]

Now, it looks only the &1+array way eliminates bound checking, other ways don't:

package main

func BoolToInt(x bool) int {
    v := 0
    if x {
        v = 1
    }
    return v
}

var functions = [...]func(){func(){}, func(){}}
var bs = []bool{true, false, false, true}

func main() {
    for _, b := range bs {
        functions[BoolToInt(b)&1]()
    }
}

Though it is not the cleanest and most efficient solution, now I think the optimization for maps with bool keys is not very essential in practice. On the other hand, it would be still great if the optimization could be supported, for aesthetics perfection.

So please fell free to close this issue, or keep it open if it is still worth being implemented.