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"