Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

cmd/compile: optimize maps with bool keys #44578

Open
go101 opened this issue Feb 24, 2021 · 12 comments
Open

cmd/compile: optimize maps with bool keys #44578

go101 opened this issue Feb 24, 2021 · 12 comments

Comments

@go101
Copy link

@go101 go101 commented Feb 24, 2021

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.

@gopherbot gopherbot added this to the Proposal milestone Feb 24, 2021
@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Feb 24, 2021

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

@ianlancetaylor ianlancetaylor changed the title proposal: optimize maps with bool keys cmd/compile: optimize maps with bool keys Feb 24, 2021
@ianlancetaylor ianlancetaylor removed this from the Proposal milestone Feb 24, 2021
@ianlancetaylor ianlancetaylor added this to the Unplanned milestone Feb 24, 2021
@davecheney
Copy link
Contributor

@davecheney davecheney commented Feb 25, 2021

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

@go101
Copy link
Author

@go101 go101 commented Feb 25, 2021

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.

@go101
Copy link
Author

@go101 go101 commented Feb 25, 2021

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
Copy link
Contributor

@davecheney davecheney commented Feb 25, 2021

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
Copy link

@networkimprov networkimprov commented Feb 28, 2021

@go101
Copy link
Author

@go101 go101 commented Mar 13, 2021

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
Copy link

@networkimprov networkimprov commented Mar 13, 2021

@mdempsky
Copy link
Member

@mdempsky mdempsky commented Mar 16, 2021

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
}

@go101
Copy link
Author

@go101 go101 commented Mar 16, 2021

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
Copy link
Member

@mdempsky mdempsky commented Mar 16, 2021

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

@go101
Copy link
Author

@go101 go101 commented Mar 16, 2021

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
7 participants