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

proposal: Go 2: allow explicit conversion of bool to arbitrary numeric types #45320

Open
seebs opened this issue Mar 31, 2021 · 25 comments
Open

proposal: Go 2: allow explicit conversion of bool to arbitrary numeric types #45320

seebs opened this issue Mar 31, 2021 · 25 comments

Comments

@seebs
Copy link
Contributor

@seebs seebs commented Mar 31, 2021

In some cases, being able to do arithmetic or bitwise operations in which you can use a true-or-false value without a branch is highly appealing. It would be convenient to allow conversion of true and false to arbitrary integer types, producing the values 1 and 0 respectively. Conveniently, unless I get around to writing up my int0 proposal and convince someone that it's a good idea, every numeric type in Go can represent both of those values.

I've been told that the Go compiler is already smart enough to generate reasonable code for something like this:

int x
if cond {
  x = 1
}

However, even if the compiler can do it, it's a lot more code to read than something like int(cond) would be, and whether or not it's branchy is less obvious and I don't know whether it's safe to use this in code where a branch is Too Expensive. (Unfortunately, Google Groups has destroyed any once-functional Usenet searching, so I can't find the reference, but I seem to recall someone getting a 20% overall improvement in a PRNG by replacing if (z) { x += y } with x += y * z.)

I originally strongly disliked the thing where true and false weren't numeric values, but I've come to quite appreciate the need to make a conversion between booleans and numbers explicit. But "explicit" need not mean "verbose". Allowing int(a < b) to be 1 or 0 depending on whether a was or was not (respectively) less than b seems like it would simplify a lot of code without hurting anything.

@gopherbot gopherbot added this to the Proposal milestone Mar 31, 2021
@cespare
Copy link
Contributor

@cespare cespare commented Apr 1, 2021

Previous discussion at #9367 (and other discussions before that, I think).

Not sure it has ever gone through the modern proposal process, though.

@seebs
Copy link
Contributor Author

@seebs seebs commented Apr 1, 2021

I intentionally declined to propose converting integers to bools. I want to be able to bitwise-or bools and otherwise integrate them into integer expressions, but we already have != 0 if we want to go the other way, and it's clear and short.

@cespare
Copy link
Contributor

@cespare cespare commented Apr 1, 2021

(@seebs if you're responding to me, proposal #9367 is about converting bools to numeric types, just like this one.)

@ianlancetaylor ianlancetaylor changed the title Proposal: (Go 2?): Allow explicit conversion of bool to arbitrary numeric types proposal: Go 2: allow explicit conversion of bool to arbitrary numeric types Apr 1, 2021
@seebs
Copy link
Contributor Author

@seebs seebs commented Apr 1, 2021

One of the comments in it cited to the ambiguity of what bool(intValue) should mean as a weakness, which I agree it sort of is.

@smasher164
Copy link
Member

@smasher164 smasher164 commented Apr 1, 2021

Slightly off-topic but re the discussion in #9367, to be honest, the whole "true could be interpreted as both 0 and 1" argument seemed weak to me. The only example provided was exit statuses across operating systems, which is platform-specific anyways. For example, VMS treats 0 as a warning and 1 as a success, while POSIX treats nonzero as an error.

Explicitly converting between the zero value of bool to the zero value of int is predictable behavior. It also has the benefit of matching other languages' interpretation of a bool -> int conversion.

@martisch
Copy link
Contributor

@martisch martisch commented Apr 1, 2021

and whether or not it's branchy is less obvious and I don't know whether it's safe to use this in code where a branch is Too Expensive.

As far as I understand the proposal at least two reasons are given in favor of the proposal:

  1. knowing if there is a branch or not
    The Go spec does not mandate how bools are represented internally and the proposal does not force an implementation and therefore the implementation could use a branch with the same performance as the if version before. Which means the current situation is that an if might suggest there is a branch but the compiler may be smart enough to avoid it while with the proposal it is not clear from code there might be a branch and then there actually could be a branch used by the implementation.

  2. performance
    If performance is to be made as an argument then I think the proposal also needs the requirement that the conversion needs to be (or can be) faster or as fast than equivalent if version. However I would not think the performance or branchness requirement should be part of the language spec.

As noted in practice there likely isnt a performance benefit as the current compiler already optimises the existing pattern to convert a bool. If there is we can work on fixing those without changing the language.

Alternative Suggestion:

Instead of changing the language the std lib could contain a generic function that converts any integer type to bool and we make sure at least the Go GC implementation always inlines and optimises the if pattern in that generic function to branchless and performant on architectures that allow that.

@seebs
Copy link
Contributor Author

@seebs seebs commented Apr 1, 2021

I mean, it could be a function.

but is there any reason for which, I dunno, math.BoolAsInt32(true) is a better spelling than int32(true)? I seem to recall that, at least at the moment, function calls imply at least a nop even when inlined to allow the compiler to distinguish what code is executing... But conversions, when they're allowed at all, are also allowed to be completely free.

The primary goal here is to make the code more expressive and allow short but still-reasonably-clear code, but also to hint that this shouldn't be a branchy operation.

@martisch
Copy link
Contributor

@martisch martisch commented Apr 1, 2021

but is there any reason for which, I dunno, math.BoolAsInt32(true) is a better spelling than int32(true)

The difference is that a language change has a much higher bar to be acceptable then adding a new function in the std library. And a language change likely also doesnt have the upside to guarantee branchness as that is an implementation detail of the specific Go implementation. The main upside to making it a language change I can see currently then becomes it can potentially be shorter in writing.

but also to hint that this shouldn't be a branchy operation

Just because it is short and doesnt contain an if is I dont think a good hint whether it branches given existing Go language constructs . e.g. other conversions string(int) also involve branches and look the same from a syntax complexity.

@mvdan
Copy link
Member

@mvdan mvdan commented Apr 1, 2021

Instead of changing the language the std lib could contain a generic function that converts any integer type to bool

I was thinking this while I read the thread. Having to explicitly call a math or math/bits function would also mean that it would be harder to convert a boolean to an integer by accident.

@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Apr 1, 2021

I don't think it's useful to discuss performance in this issue. We are not going to make a language change of this sort for performance reasons. We would only make this change if it would provide a clear benefit for writing and, especially, reading Go code.

@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Apr 1, 2021

This proposal does seem very similar to #9367 and #6011. What has changed since then?

I'll note that it would seem odd to support converting from boolean to numeric but not support converting numeric to boolean. Are there any other one-way conversions in Go? (Other than converting to an interface type, for which the reverse conversion requires a type assertion.)

@docmerlin
Copy link

@docmerlin docmerlin commented Apr 1, 2021

@ianlancetaylor it makes it a lot easier to read branch free code, when you can use the normal algos instead of having to write things in asm.
It helps with math code when you can do a multiply by 1 or zero instead of having to add 5 or 6 extra lines and break up flow with a conditional.

@mvdan that would be a bit of a pain to read the code.
Having to do math.boolToNumeric(uint)(a<b) in a line with a lot of math is a lot more awkward than just uint(a<b)
It would also likely need to be a special cased code anyway if it was to avoid branching or other awkwardness, and always be inlined.

@randall77
Copy link
Contributor

@randall77 randall77 commented Apr 1, 2021

The compiler defines:

func b2i(b bool) int64 {
	if b {
		return 1
	}
	return 0
}

Which we then use lots of places. So although I think converting from bool to int is useful, it doesn't appear to me to require language changes - if you've only got a few instances, then math.boolToNumeric[uint](a<b) seems easy enough, and if you have lots of instances making a helper function to reduce repetition is also easy.

@docmerlin
Copy link

@docmerlin docmerlin commented Apr 1, 2021

@randall77 that defeats the purpose by introducing a branch (or similar flow control) and possibly a function call.

@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Apr 1, 2021

@docmerlin Please don't confuse a branch in the Go code with a branch in the generated machine code.

For example, when using the gccgo compiler, this Go function

func Cmp(a, b int) int {
	if a < b {
		return 0
	}
	return 1
}

compiles to this assembly code (ignoring the stack-splitting code):

	xorl	%eax, %eax
	cmpq	%rsi, %rdi
	setge	%al
	ret
@FiloSottile
Copy link
Contributor

@FiloSottile FiloSottile commented Apr 1, 2021

For cryptographic code it would be great to have a function to go from bool to int in guaranteed constant time. Maybe it can go in crypto/subtle along with all other constant time functions.

Packages like filippo.io/edwards25519 have to use int instead of bool, leaving all values other than 1 and 0 undefined, so that they can be used as inputs for crypto/subtle functions without branches.

We'd probably also need the other way around, because those values are also generate in constant time by masking and bit shifting.

@seebs
Copy link
Contributor Author

@seebs seebs commented Apr 1, 2021

Ohhh. I hadn't thought about the constant-time guarantee, but that does seem relevant. Although... Is the naive CPU code actually constant-time? I have no idea.

It seems like it'd be nice to be able to drop the extra nop, although it probably doesn't matter much.

@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Apr 1, 2021

This is a side comment, but the notion of guaranteed constant time in non-assembly code appears to require that the compiler never insert branches that aren't present in the source code. I doubt any compilers do that today but it's hardly impossible.

@FiloSottile
Copy link
Contributor

@FiloSottile FiloSottile commented Apr 1, 2021

Every cryptography engineer expects in fear the day that will inevitably happen, and secretly hopes to retire before then. There are occasionally rumors of LLVM-related sightings. A much more sinister prospect than quantum computers, which at least will require new exciting designs, it's considered indelicate to talk about it in polite cryptography circles.

@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Apr 1, 2021

Well, now I know the next GCC optimization that I should work on!

@FiloSottile
Copy link
Contributor

@FiloSottile FiloSottile commented Apr 1, 2021

ಠ_ಠ

@smasher164
Copy link
Member

@smasher164 smasher164 commented Apr 3, 2021

FWIW, neither performance nor knowing about branching are my reasons for supporting this proposal. I just think that some algorithms are easier to read when, for example, using the truth value of some decision procedure later in some function isn't obscured by control flow.

@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Apr 3, 2021

FWIW, neither performance nor knowing about branching are my reasons for supporting this proposal. I just think that some algorithms are easier to read when, for example, using the truth value of some decision procedure later in some function isn't obscured by control flow.

Understood. But it seems that b2i function like the one that @randall77 mentions above addresses that.

@rogpeppe
Copy link
Contributor

@rogpeppe rogpeppe commented May 5, 2021

Although it's been implied, I don't think anyone's explicitly said that the b2i function mentioned above does in fact generate branch-free code. For example in this code the line sum += b2i(x) compiles to just the single instruction ADDQ SI, BX.

@go101
Copy link

@go101 go101 commented May 9, 2021

This is good to avoid custom BoolToInt implementation: #44578

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