Yeah, it's not the first time this question appears and it's not immediately obvious that Go compiler can do this optimization.
IIRC someone asked for this optimization on Github and it's there, but Go doesn't allow bool to int conversion therefore it can't do this optimization implicitly, which is quite unfortunate because some people might take branching in bitwise operations for granted even though there is no branching when integers are used. You might also want to check what GCC is doing, maybe it can optimize code better. https://godbolt.org/z/Eod5Ye Assembly looks smaller and when xor is removed it appears like the entire function is being optimized away perhaps because it's a constant expression that can be evaluated at compile time. But i'm not sure how good this assembly is without measuring actual performance. Hope this helps. вс, 22 нояб. 2020 г. в 11:54, christoph...@gmail.com <christophe.mees...@gmail.com>: > > Thank you Aleksey. That is indeed a working solution, and it works well. > Here are the two functions I wrote as suggested: > > func bool2int(b bool) int { > if b { > return 1 > } > return 0 > } > > func testBitHack(v int) bool { > return (bool2int(v==10) & bool2int(v==5) & bool2int(v==15)) == 0 > } > > Here is the Go assembly code of testBitHack > > "".testBitHack STEXT nosplit size=47 args=0x10 locals=0x0 > 0x0000 00000 (main.go:12) TEXT "".testBitHack(SB), > NOSPLIT|ABIInternal, $0-16 > 0x0000 00000 (main.go:12) FUNCDATA $0, > gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB) > 0x0000 00000 (main.go:12) FUNCDATA $1, > gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB) > 0x0000 00000 (main.go:13) MOVQ "".v+8(SP), AX > 0x0005 00005 (main.go:13) CMPQ AX, $10 > 0x0009 00009 (main.go:13) SETEQ CL > 0x000c 00012 (main.go:13) CMPQ AX, $5 > 0x0010 00016 (main.go:13) SETEQ DL > 0x0013 00019 (main.go:13) CMPQ AX, $15 > 0x0017 00023 (main.go:13) SETEQ AL > 0x001a 00026 (main.go:13) MOVBLZX DL, DX > 0x001d 00029 (main.go:13) MOVBLZX CL, CX > 0x0020 00032 (main.go:13) ANDQ DX, CX > 0x0023 00035 (main.go:13) MOVBLZX AL, AX > 0x0026 00038 (main.go:13) TESTQ AX, CX > 0x0029 00041 (main.go:13) SETEQ "".~r1+16(SP) > 0x002e 00046 (main.go:13) RET > > The function bool2int and its condition were effectively optimized away by > the Go compiler. That’s awesome. Good job. It’s a nice trick. > > > > > Le samedi 21 novembre 2020 à 11:41:03 UTC+1, aleksey...@gmail.com a écrit : >> >> To me your example appears somewhat confusing, int(bool(int())) is the >> fishiest part IMO. I assume bool(int()) is just (v^v1 != 0) in >> disguise and this is essentially >> >> (v^v1 != 0) & (v^v2 != 0) & (v^v3 != 0) >> >> Am i right? >> >> Go can't & bools, so >> >> func bool2int(b bool) int { // This is what Go compiler can optimize well >> if b { >> return 1 >> } >> return 0 >> } >> >> And this leaves us with >> >> bool2int(v^v1 != 0) & bool2int(v^v2 != 0) & bool2int(v^v3 != 0) >> >> Is that correct? >> >> https://godbolt.org/z/jq368G >> >> I don't see branching in relevant parts. v == v1 || v == v2 will of >> course branch because || is a condition. >> >> Does that answer your question or maybe I am missing something? >> >> пт, 20 нояб. 2020 г. в 11:27, christoph...@gmail.com >> <christoph...@gmail.com>: >> > >> > Go has a strict type separation between int and bool. For a normal usage >> > this is OK. I guess it also ease assembly portability because there is not >> > always a machine instruction to do so. >> > >> > For bit hacking, this is an unfortunate limitation. A handy feature of >> > bool <-> int conversion is that true is converted to 1 and any integer >> > different of zero to true. As a consequence, when we write int(bool(x)) we >> > get 0 when x is 0, and 1 when x is not 0. I checked the math/bits package >> > and there is not an equivalent function. >> > >> > Is there a way around this that avoids the conditional branching ? >> > >> > The use case I have to test if an integer is in a quite small constant set >> > of integers. With bool <-> int conversion, we can use binary operation >> > like this for instance which would be valid in C >> > >> > r := int(bool(v^v1))&int(bool(v^v2))&int(bool(v^v3)) >> > >> > This is to be compared with >> > >> > r := v==v1 || v==v2 || v==v3 >> > >> > The second form is of course more readable, but will also have a >> > conditional branch at each ||. If most tested integers are different from >> > v1, v2 and v3, the first form seam to me more efficient due to pipelining. >> > Though branching prediction can mitigate the penalty. >> > >> > The best I could do as valid Go alternative is this >> > >> > r := (v^v1)*(v^v2)*(v^v3) >> > >> > but the multiplication is obviously not efficient. >> > >> > Did I miss something ? >> > >> > -- >> > You received this message because you are subscribed to the Google Groups >> > "golang-nuts" group. >> > To unsubscribe from this group and stop receiving emails from it, send an >> > email to golang-nuts...@googlegroups.com. >> > To view this discussion on the web visit >> > https://groups.google.com/d/msgid/golang-nuts/a2b743d7-011d-481f-9a0f-3f00f4507328n%40googlegroups.com. > > -- > You received this message because you are subscribed to the Google Groups > "golang-nuts" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to golang-nuts+unsubscr...@googlegroups.com. > To view this discussion on the web visit > https://groups.google.com/d/msgid/golang-nuts/4381cff4-a79e-4b91-bf04-c7a2c95af309n%40googlegroups.com. -- You received this message because you are subscribed to the Google Groups "golang-nuts" group. To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/CAMteYTbzAqQmK_LufOjYHwEjXOsYrUjSLNG%2B4QpW1ShCL9wi-g%40mail.gmail.com.
