Efficient bitmask twiddling

[Oliver Smith]

In the process of developing a piece of middleware, I need to translate from a bit-array into a bitmask. I am struggling to find a way to express this in go that doesn't result in terrible performance.

The approaches I would try in most other languages were along the lines of:

```

mask = (bool1 << bitno1) | (bool2 << bitno2);

// or

mask = (bool1 ? value1 : 0) | (bool2 ? value2 : 0);

```

but instead, after reading several old (circa 1.5) posts, I'd landed at

```

func maskIfTrue(mask uint, predicate bool) uint {

  if predicate {

    return mask

  }

  return 0

}

mask = maskIfTrue(mask1, bool1) | maskIfTrue(mask2, bool2)

```

Here is a (boiled-down & reduced) comparison of the go implementation vs a simple C implementation compiled with -O0 and -Os: 

The go version is branch-crazy.

Is there some way I can write this that will produce simpler/efficient code and also not be code salad? I don't have control over the relative ordering of the bools or the bitfield values, and this is a hot path?

Go branchiness:

```

        nop

        cmpb    1(AX), $0

        jeq     featToMask_pc94

        movl    $2, DX

featToMask_pc19:

        nop

        cmpb    2(AX), $0

        jeq     featToMask_pc90

        movl    $4, BX

featToMask_pc30:

        nop

```

The "FeatToMask" C transliteration when compiled with optimization *disabled* (-O0) looks similar, but even -O1 fixes that:

```

FeatToMask:

        mov     eax, edi

        movzx   eax, ah

        mov     esi, edi

        shr     esi, 16

        mov     ecx, edi

        shr     ecx, 24

        mov     rdx, rdi

        shr     rdx, 32

        shr     rdi, 40

        or      eax, esi

        or      eax, ecx

        or      eax, edx

        or      eax, edi

        movzx   eax, al

        ret

```

and with -Os you get down to something better than the naive-C-implementation at the top of the source

```

FeatToMask:

        mov     QWORD PTR [rsp-8], rdi

        mov     al, BYTE PTR [rsp-7]

        or      al, BYTE PTR [rsp-6]

        or      al, BYTE PTR [rsp-5]

        or      eax, DWORD PTR [rsp-4]

        or      al, BYTE PTR [rsp-3]

        movzx   eax, al

        ret

```

[Oliver Smith]

Do godbolt links get eaten? https://godbolt.org/z/vbeobs

[Rob Pike]

It's not a bit array, it's a bool array. Can you make it a bit array and use bit != 0 for the boolean elsewhere?

-rob

--
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/a85f9dd6-e9f5-4410-a451-7b28671ee417n%40googlegroups.com.

[Aleksey Tulinov]

https://godbolt.org/z/6n7G8q

I'm actually not sure how good this assembly is, it would be
interesting to hear from you, but it looks promising.

вт, 1 сент. 2020 г. в 22:54, Oliver Smith <oliver...@superevilmegacorp.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...@googlegroups.com.

> To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/ea364cef-3998-469c-8742-3bc794733535n%40googlegroups.com.