cmd/compile: optimize code generation for typical bool->int conversion patterns

[gopherbot]

by sjbogdan:

Need a compiler level support for fast bool to numeric types ( int, byte, float )
conversion.

Possible syntax : var flag = false
1) flag.( int )
2) int ( flag )

Right now, except for "if" blocks, there is no way to make a conversion.
It is important for high speed computing with "bit magic".

Classic example ( pseudo code ) :

if a > 0 {
  b = sin ( a )
} else {
  b = 0.0
}

Compiler would generate a faster (virtual) assembly code with ( because there won't be
jmp* commands ) :

b = ( a > 0 ).( float64 )  *  sin ( a )


The conversion should be cheap & fast, thus I though about interface-like type
transition. The values are always 0 or 1, which might be hardcoded into numeric types
definition.

[robpike]

Comment 1:

The compiler could provide speed without new syntax just by generating better code.

Labels changed: added priority-later, performance, removed priority-triage.

Status changed to Accepted.

[cznic]

Comment 2:

Ad 'except for "if" blocks, there is no way to make a conversion':
    bool2int := map[bool]int{true: 1}
    ...
    myInt := bool2int[myBool] // "conversion"
I suggest to think about the possibility that the compiler would recognize map literals
of the above form, when the're proven to be never mutated, and optimize reading a value
from 'bool2int' map(s) into proper (faster) assembly code - without any map access at
all.
It has the little advantage of not extending the language syntax. Which I think should
not be done for the sole purpose of generating faster code while no semantic changes are
brought by it to the language.
PS: In a more general approach, every 'map[bool]T' can, and probably should - if it's
not the case already, be rewritten by the compiler into [2]T behind the scenes while
translating access to such "maps" into indexing the array by the ordinal number of the
bool value.

[gopherbot]

Comment 3 by sjbogdan:

Map doesn't have a "canonical" realization, thus it isn't much different from a
class/type.
<code>
package main
func main() {
    var (
        a = 3
        b int
    )
    
    if a > 0 {
        b = 1.0
    } else {
        b = 0.0
    }
    
    print ( b )
}
</code>
go tool 6g -S 1.go > 1.asm
<code>
--- prog list "main" ---
0000 (1.go:3) TEXT    main+0(SB),$8-0
0001 (1.go:3) LOCALS  ,$0
0002 (1.go:5) MOVQ    $3,AX
0003 (1.go:9) CMPQ    AX,$0                     # stores result into compare register C0
0004 (1.go:9) JLE     ,7                        # jumps to address 0007 if C0 true/false
0005 (1.go:10) MOVQ    $1,AX
0006 (1.go:9) JMP     ,8                        # direct jump to address 0008 ( almost
goto )
0007 (1.go:12) MOVQ    $0,AX
0008 (1.go:15) MOVQ    AX,(SP)
0009 (1.go:15) CALL    ,runtime.printint+0(SB)
0010 (1.go:16) RET     ,
</code>
Map solution is 200 lines ( with map definition ), and is 15 lines "map code" instead of
6-line "if block" with "raw jumps".
----
> The compiler could provide speed without new syntax just by generating better code.
From the language user perspective neither solution 1) nor 2) introduces new syntax. Can
you explain what do you mean or how it will work ? What will compiler optimize ?

[rsc]

Comment 4:

What Rob is suggesting is that the compiler recognize
if cond {
   x = 1
} else {
   x = 0
}
and compile it to a sequence without jumps. That might happen.

[gopherbot]

Comment 5 by sjbogdan:

>compile it to a sequence without jumps
It is a bad idea. There are different cases where "hot" registers give the performance
gain, compiler won't be able to handle all of them.
The whole point of the thread/issue is to handle a golang bool as a "multiplicative"
value (int) with register.
max (x, y) :
r = x ^ ((x ^ y) & -(x < y));
( x < y ) will be stored in a ( compare ) register, won't be saved into a variable,
thus ( ideally ) won't leave L1 cache. Cache / register techniques are highly optimized,
although even gcc ( compiling c/c++ ) can't always produce good asm code for "if blocks".
From the very beginning computer bit was designed as int. Is there a low level / asm
expert to give an opinion how it should be built ? ( or to prevent implementing bad
ideas ). I'm not rushing the issue, but I think it's important to resolve it in the
early stage.

[robpike]

Comment 6:

Deferring to Go 1.3.

Labels changed: added go1.3maybe, removed go1.2maybe.

[robpike]

Comment 7:

Labels changed: removed go1.3maybe.

[rsc]

Comment 8:

Labels changed: added go1.3maybe.

[rsc]

Comment 9:

Labels changed: added release-none, removed go1.3maybe.

[rsc]

Comment 10:

Labels changed: added repo-main.

[gopherbot]

Comment 11 by bronze1man:

I think go can provide a package with some function to do those stuff.
Those function can be inline to do that stuff.
I think this way will not add new syntax and finish this job..

[griesemer]

Comment 12:

Issue #7657 has been merged into this issue.

[griesemer]

Comment 13:

Some observations:
1) It is trivial to "convert" from any comparable non-boolean value x to a boolean
value; the operation is called comparison ==. There's absolutely no need for a different
syntax. We want people to write x != 0 which is very clear; we don't want people to
write bool(x).
2) It is trivial to "convert" from a boolean value to any other value using an if (or
switch) statement. If necessary, it can be enclosed in a function.
3) Go provides built-in conversions between types where it otherwise would be hard to
impossible, extremely inefficient, or implementation-dependent to do a conversion (with
the notable exception of string(a_rune_value); but there have been suggestions to remove
this one). For bool->numeric, and numeric->bool this is not the case; the code is
obvious, trivial, and reasonably efficient.
4) It would be a sensible compiler optimization to produce specialized code for patterns
of the form b := x != 0, etc. Also, a function of the form
func toInt(b bool) int {
   if b {
      return 1
   }
   return 0
}
is not to hard to optimize by converting the if statement into a conditional move, and
inline the function call away.
It seems not justified to add special conversions (and certainly not special notation)
for going from bools to numeric values and vice versa; and it's certainly not in the
spirit of Go.
Leaving as "Thinking" for now, just in case somebody makes a truly compelling argument;
but I suggest this issue be closed eventually as "WorkingAsIntended".

Status changed to Thinking.

[FlorianUekermann]

Comment 14:

We could just add a function for this to the math package. The package uses unsafe
anyway so it should be easy to achieve optimal speed without demanding much from the
compiler. "Kronecker delta" comes to mind as possible name or just Bool2XXX
Other than that: I'm in favor of allowing conversion to integer types in the language
(and maybe floats if it is actually faster than just doing "float(int(true))"). Its
obvious what it does and really nice to have, especially for people who aren't aware
which optimizations the compiler does atm. The other direction ("bool(1)") doesn't make
much sense to me because it is not obvious (to me) how to map every value and it is easy
and fast to do a normal comparison as pointed out earlier.

[MichaelTJones]

Comment 15:

(Perhaps not the best place for design discussions, but...)
What you're asking for here is essentially Iverson bracket notation as originally
created for APL and further popularized by Donald Knuth in mathematical papers and the
book Concrete Mathematics. 
The idea is that "[p]", where p is a proposition ("bool" expression to Go) represents a
number and has two possible values:
[ false ] = 0
[ true ] = 1
Examples would be:
x += [n > 4]
c := [n < limit]*p(n)
z += [IsPrime(k)]
I would love this feature. It is simple to understand, easy to implement, and very
efficient to generate code for.
As it happens, it _could_ be added to Go without changing the meaning of any valid Go
program. Go now has "[]" to mean "a slice" and "[ <index> ]" to mean subscripting
and map references. But it has no use of "[ <boolean expression ]" for anything.
Note that it would NOT give subtly different meanings to "a += slice[b]" because
<slice>[<numeric expression>]" and monadic "[ <boolean expression> ]"
are completely distinct. The parser would complain about "boolean in integer context" in
this case. However, the expression "a += slice[[b]]" would be legal and would mean
either "a += slice[0]" or "a += slice[1]" depending on the truth of boolean expression
b. If b were a numeric expression, this would not parse and yield the complaint "numeric
in boolean context"

[cznic]

Comment 16:

#15: Consider
        c := [foo]*bar
If foo is an integer constant and bar is a type then c is a slice of pointers to bar.
But if foo is a boolean constant an bar is a mumeric type the c is a number.
So far, Go is very readable without a mental "symbol table" and this proposal makes that
worse.

[MichaelTJones]

Comment 17:

That's a fair point. I was also thinking about a map of bool values as a bad example too.
Sad though, since Iverson's idea is so beautiful in mathematics and in APL, it would be
unfortunate to copy his work and introduce a different notation.
One thing from his idea that I did not mention but is very important in the math
context, is the notion of "[p]" being "very strongly zero" (as DEK phrases it) to mean
that a false predicate essentially suppresses the evaluation of things it is multiplied
by, so that "sum [n > 0]/n" never divides by zero. In a coding sense this is an analog
to the "shortcut" && and || logical evaluation operators of the C-language family.
Adding this WOULD be a big psychological step for some users, since && and || puzzle
some people.

[cespare]

@griesemer as far as the language change proposal goes, it seems this was already hashed out and rejected in #9367.

Since this original issue was both about a new syntax and also about generating fast code, perhaps it would be best to instead make this issue only about generating fast code from the if statement. It seems that we're most of the way there after CL 22711 and eventually the compiler ought be better about recognizing the pattern as typically written.

[griesemer]

@cespare Good point - I forgot about #9367. Will change title.

[bradfitz]

/cc @randall77

[randall77]

Tip can now handle a few patterns like

x := 0
if b {
  x = 1
}

Hopefully we can do a more robust transformation pass in the future.

[josharian]

Doesn't seem important for 1.9. Moving to 1.10.

[lukescott]

I would like to be able to do comparisons with bool, such as:

true > false
true >= true

If you could do the conversion you could do something like this:

int(true) > int(false)
int(true) >= int(true)

But if you could do the comparison directly that would be nice.

Currently you have to do something like this:

// true > false:

func boolInt(b bool) (n int) {
    if b {
        n = 1
    }
    return
}

boolInt(true) > boolInt(false)
boolInt(true) >= boolInt(true)

My use case in particular - I have a "deleted" flag within a struct and I want to use sort to push the deleted items to the end of the slice. Currently the best work-around for me is to simply use uint8 instead of bool to avoid the conversion entirely. Although with a deleted flag the preferred choice is obviously bool.

[randall77]

@lukescott a > b with a, b boolean is equivalent to a & !b

[ianlancetaylor]

I think this issue has been transformed into one about a compiler performance improvement. I think it's going to be confusing to discuss language change proposals on the same issue.

[stemar94]

@lukescott and a >= b is equivalent to a | !b

[aclements]

@randall77, what's the status of the compiler optimizations for this? I know we get some patterns now. Is it robust enough to consider this done, or is there still clear work to do?

[randall77]

We do the simple cases. Let's close this, people can open new issues with particular examples if they aren't handled correctly.