simd: expose portable mask bit extraction or iteration for Mask8s

[llxisdsh]

Go version

go version go1.27rc1 windows/amd64

Output of go env in your module/workspace:

set AR=ar
set CC=gcc
set CGO_CFLAGS=-O2 -g
set CGO_CPPFLAGS=
set CGO_CXXFLAGS=-O2 -g
set CGO_ENABLED=1
set CGO_FFLAGS=-O2 -g
set CGO_LDFLAGS=-O2 -g
set CXX=g++
set GCCGO=gccgo
set GO111MODULE=on
set GOAMD64=v1
set GOARCH=amd64
set GOAUTH=netrc
set GOBIN=C:\Users\8\go\bin
set GOCACHE=C:\Users\8\AppData\Local\go-build
set GOCACHEPROG=
set GODEBUG=
set GOENV=C:\Users\8\AppData\Roaming\go\env
set GOEXE=.exe
set GOEXPERIMENT=
set GOFIPS140=off
set GOFLAGS=
set GOGCCFLAGS=-m64 -mthreads -Wl,--no-gc-sections -fmessage-length=0 -ffile-prefix-map=C:\Users\8\AppData\Local\Temp\go-build1360496246=/tmp/go-build -gno-record-gcc-switches
set GOHOSTARCH=amd64
set GOHOSTOS=windows
set GOINSECURE=
set GOMOD=E:\code\cc\go.mod
set GOMODCACHE=C:\Users\8\go\pkg\mod
set GONOPROXY=
set GONOSUMDB=
set GOOS=windows
set GOEXE=.exe
set GOEXPERIMENT=
set GOFIPS140=off
set GOFLAGS=
set GOGCCFLAGS=-m64 -mthreads -Wl,--no-gc-sections -fmessage-length=0 -ffile-prefix-map=C:\Users\8\AppData\Local\Temp\go-build1360496246=/tmp/go-build -gno-record-gcc-switches
set GOHOSTARCH=amd64
set GOHOSTOS=windows
set GOINSECURE=
set GOMOD=E:\code\cc\go.mod
set GOMODCACHE=C:\Users\8\go\pkg\mod
set GONOPROXY=
set GONOSUMDB=
set GOOS=windows
set GOEXPERIMENT=
set GOFIPS140=off
set GOFLAGS=
set GOGCCFLAGS=-m64 -mthreads -Wl,--no-gc-sections -fmessage-length=0 -ffile-prefix-map=C:\Users\8\AppData\Local\Temp\go-build1360496246=/tmp/go-build -gno-record-gcc-switches
set GOHOSTARCH=amd64
set GOHOSTOS=windows
set GOINSECURE=
set GOMOD=E:\code\cc\go.mod
set GOMODCACHE=C:\Users\8\go\pkg\mod
set GONOPROXY=
set GONOSUMDB=
set GOOS=windows
set GOGCCFLAGS=-m64 -mthreads -Wl,--no-gc-sections -fmessage-length=0 -ffile-prefix-map=C:\Users\8\AppData\Local\Temp\go-build1360496246=/tmp/go-build -gno-record-gcc-switches
set GOHOSTARCH=amd64
set GOHOSTOS=windows
set GOINSECURE=
set GOMOD=E:\code\cc\go.mod
set GOMODCACHE=C:\Users\8\go\pkg\mod
set GONOPROXY=
set GONOSUMDB=
set GOOS=windows
set GOHOSTOS=windows
set GOINSECURE=
set GOMOD=E:\code\cc\go.mod
set GOMODCACHE=C:\Users\8\go\pkg\mod
set GONOPROXY=
set GONOSUMDB=
set GOOS=windows
set GOMODCACHE=C:\Users\8\go\pkg\mod
set GONOPROXY=
set GONOSUMDB=
set GOOS=windows
set GONOPROXY=
set GONOSUMDB=
set GOOS=windows
set GOPACKAGESDRIVER=
set GOTMPDIR=
set GOTOOLCHAIN=auto
set GOTOOLDIR=C:\Program Files\Go\pkg\tool\windows_amd64
set GOVCS=
set GOVERSION=go1.27rc1
set GOWORK=
set PKG_CONFIG=pkg-config

What did you do?

This is API usability feedback for the experimental Go 1.27 simd package, not a compiler crash report.

I am prototyping a vector-size-agnostic hash table using the new portable simd package.

The core probing operation is:

1. Load a vector of tag bytes.
2. Compare all lanes against a broadcast tag.
3. Convert the resulting mask into lane indexes.
4. Probe only matching lanes.

With simd/archsimd, this is direct:

words := archsimd.LoadUint8x32Array((*[32]uint8)(ptr))
bits := words.Equal(archsimd.BroadcastUint8x32(tag)).ToBits()

for bits != 0 {
    lane := bits.TrailingZeros()
    bits &= bits - 1
    // check entry at lane
}

With portable simd, I can produce a simd.Mask8s:

words := simd.LoadUint8s(tags)
mask := words.Equal(simd.BroadcastUint8s(tag))

But I could not find a portable way to extract set lane indexes from simd.Mask8s.
The only practical path seems to be mask.ToArch() plus architecture-specific type switches:

switch m := mask.ToArch().(type) {
case archsimd.Mask8x16:
    bits := uint64(m.ToBits())
case archsimd.Mask8x32:
    bits := uint64(m.ToBits())
case archsimd.Mask8x64:
    bits := m.ToBits()
}

What did you see happen?

The current portable simd.Mask8s API does not appear to provide a portable way to extract or iterate over the selected lanes.

For workloads such as hash-table probing, byte search, parsers, and scanners, the comparison mask is usually not the final result. The caller needs the lane indexes represented by the mask.

The portable simd.Mask8s API exposes operations such as And, Or, ToInt8s, and ToArch, but I could not find a direct portable way to enumerate or extract selected lanes.

The only practical workaround I found is to call mask.ToArch() and then switch on architecture-specific mask types such as archsimd.Mask8x16, archsimd.Mask8x32, and archsimd.Mask8x64, using their ToBits methods. That makes the probing loop architecture-specific again, which reduces the usefulness of the portable, vector-size-agnostic API for this class of workloads.

What did you expect to see?

I expected simd.Mask8s to provide a portable way to extract or enumerate selected lanes.

One possible API would be:

func (Mask8s) ToBits() uint64

This would be enough because current portable vectors are at least 128 bits and commonly 128/256/512 bits; for Mask8s, that is up to 64 lanes.
Alternatively, a width-independent iterator-style API would also work:

func (Mask8s) FirstSet() int
func (Mask8s) Clear(i int) Mask8s

func (Mask8s) NextSet(start int) int

The important part is not the exact API name, but that portable simd.Mask8s should let callers efficiently enumerate selected lanes without converting to simd/archsimd.

This came up while implementing a generic open-addressed hash table. The portable API can express the vector comparison, but without portable mask extraction the probing loop still has to be architecture-specific.

[cagedmantis]

@dr2chase @JunyangShao

[llxisdsh]

@gabyhelp
@cagedmantis

The fix for 80176 does not seem to cover this issue. I'll keep it open as a reminder for now.

[dr2chase]

The tricky cases is when we incorporate SVE (up to 2048 bits, or 256 uint8s) or RVV (up to 65536 bits, or 8192 bytes), and a mask's bits no longer fit in an uint64. My first guess at how to do this would be to add one more type, say, "Mask8sIterator" or perhaps a range-func method Mask8s.Set(), so for range someMask.Set() { ... }.

I coded up an example for masks of 8-bit elements, here: https://go.dev/cl/796640
The test (bottom of simd_test.go) is coded in a way that was supposed to not result in any bounds checks or growslice, but there was still a check for a growSlice, though it did look like the potential rangefunc iterator overheads were all optimized away.

[llxisdsh]

The tricky cases is when we incorporate SVE (up to 2048 bits, or 256 uint8s) or RVV (up to 65536 bits, or 8192 bytes), and a mask's bits no longer fit in an uint64. My first guess at how to do this would be to add one more type, say, "Mask8sIterator" or perhaps a range-func method , so .Mask8s.Set()``for range someMask.Set() { ... }

I coded up an example for masks of 8-bit elements, here: https://go.dev/cl/796640 The test (bottom of simd_test.go) is coded in a way that was supposed to not result in any bounds checks or growslice, but there was still a check for a growSlice, though it did look like the potential rangefunc iterator overheads were all optimized away.
@dr2chase

I did a few small local experiments around the proposed Set iterator.

One observation is that the best iteration strategy depends on mask density.

For an already compact bitset, I compared lane scanning:

for i := range N {
    if (bits>>i)&1 != 0 {
        yield(i)
    }
}

with set-bit iteration:

for bits != 0 {
    i := bits.TrailingZeros()
    bits &= bits - 1
    yield(i)
}

On my machine, go1.27rc1/windows/amd64 ( AMD Ryzen Threadripper 3970X 32-Core Processor ), the rough results were:

32-bit mask, empty:      scan ~17 ns,  tzcnt ~0.5 ns
32-bit mask, one bit:    scan ~17 ns,  tzcnt ~1.5 ns
32-bit mask, three bits: scan ~17 ns,  tzcnt ~3.0 ns
32-bit mask, full:       scan ~17 ns,  tzcnt ~31 ns

So TrailingZeros-style iteration is much faster for empty/sparse masks, while lane scanning can be faster for full/dense masks.

For the emulated Mask8s representation, where selected lanes are stored as 0x00/0xff bytes in two uint64 words, I also tested a chunk-level iterator that first uses a movemask-style compression step:

bits := movemask8(x.a) | (movemask8(x.b) << 8)

and then lets the caller iterate the compact bitset.

Rough numbers:

pre-compressed bitset loop:   ~4.7 ns/op
BitChunks + movemask:         ~5.9 ns/op
lane-level Set iterator:      ~11.5 ns/op

All were 0 allocs/op.

So I would not say there is one universally fastest implementation for Set. For dense masks, scanning lanes is reasonable. For sparse masks, especially hash-table probing, byte search, scanners, parsers, validation, etc., exposing a compact chunk is much closer to the current fast path because callers can use O(popcount) iteration.

A possible lower-level API could be:

type Mask8sChunk struct {
    Base int
    Bits uint64
}

func (Mask8s) BitChunks() iter.Seq[Mask8sChunk]

or:

func (Mask8s) BitChunks() func(yield func(base int, bits uint64) bool)

Set would remain the convenient general API. BitChunks would be a lower-level primitive for callers that care about the iteration strategy.

This also scales to SVE/RVV: masks wider than 64 lanes can yield multiple uint64 chunks, while smaller vectors can yield one compact chunk similar to ToBits.

[aclements]

The hardware generally doesn't provide efficient iteration access to vectors or masks like this. They're almost, but not quite, entirely unlike arrays. We should check the SVE and RVV instructions, but my guess is that we'd have to write the mask to memory to do this, and if we're going to do that, we should just provide that as the API: a slice-based scalable equivalent of the "mask to uint64" operation.

[dr2chase]

One caveat for memory based is that in practice, on currently available hardware, the masks can fit in a uint64. 512/8 is 64, and 512 is the largest SVE implementation anywhere. Worst case for Arm64 is 2048, or 4 times that, and supporting more than 2048 bits in the portable simd layer is perhaps problematic because some full rearrangements (LookupOrZero) are not expressible for longer vector lengths. We must either leave that out of the portable layer (if we intend to support longer vectors on RVV, if any of commercial interest are ever built to that size) or cap the supported length for RVV.

[llxisdsh]

Thanks for the discussion. I do not have a strong requirement for the exact API shape. My main goal is to make the vector-size-agnostic hash-table probing workload from the original report possible with portable SIMD, while preserving sparse-mask performance.

I prototyped several API shapes locally using an AVX2 archsimd.Mask8x32. The mask was constructed outside the timed region using LoadUint8x32Array(...).Equal(...). These prototypes therefore measure the API and iteration overhead after hardware mask compression, not the eventual lowering cost on arm64/SVE/RVV.

The baseline was compact-bit iteration:

word := uint64(mask.ToBits())
for word != 0 {
    lane := bits.TrailingZeros64(word)
    word &= word - 1
    consume(lane)
}

The alternatives were implemented as follows:

• BitChunks yielded one nonzero (base, uint64) pair through a range function.
• StoreBits wrote one compact word into caller-owned [1]uint64 storage and returned the number of words.
• AppendBits appended one word to a preallocated [1]uint64 buffer.
• Set followed the CL 796640 shape: scan all 32 lane bits and yield each selected lane.

Results on go1.27rc2/windows/amd64, AMD Ryzen Threadripper 3970X 32-Core Processor:

Mask density	Direct bits	BitChunks	StoreBits	AppendBits	Set
empty	~2.07 ns	~2.07 ns	~2.86 ns	~2.87 ns	~12.6 ns
one bit	~2.43 ns	~2.74 ns	~3.50 ns	~3.58 ns	~13.6 ns
three bits	~4.26 ns	~4.46 ns	~5.43 ns	~5.68 ns	~16.2 ns
half set	~17.73 ns	~17.87 ns	~18.51 ns	~18.82 ns	~22.26 ns
full	~34.3 ns	~34.5 ns	~35.1 ns	~35.5 ns	~17.5 ns

All cases were 0 allocs/op. For the half-set case, I additionally ran Direct and Set 20 times at one second per run:

Direct: 17.73 +/- 0.10 ns/op
Set:    22.26 +/- 0.19 ns/op

As expected, Set is attractive for dense masks, especially a full mask. Compact words are much better for empty and sparse masks because callers can use O(popcount) iteration. Empty and sparse masks are particularly important for hash-table probing.

For additional reference, I compared the complete load/compare/iterate path at the same 256-bit width:

Mask density	Direct archsimd switch	Portable simd + ToArch switch
empty	~2.38 ns	~3.73 ns
one bit	~3.13 ns	~5.08 ns
three bits	~4.88 ns	~7.39 ns
half set	~17.1 ns	~20.8 ns
full	~30.8 ns	~33.9 ns

These are only API-shape experiments, so an actual SIMD implementation may produce different results. Still, they suggest that a compact-word primitive would be valuable in addition to a convenient lane iterator. The exact form could be caller-provided storage, append-style storage, or a chunk iterator.

Current vector widths need one word, while wider SVE/RVV masks could produce more words, independently of the eventual maximum vector-width decision.

I would be happy to test an actual prototype or CL against the end-to-end hash-table workload and report the results.

@dr2chase @aclements