rust-lang / rust-lang/rust

What should SIMD bitmasks look like?

Open
#126,217 6 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

A-SIMD C-discussion PG-portable-simd T-compiler T-opsem
Dominant language
Rust
Stars
119k
Forks
16.1k
PR merge metrics
PR metrics pending

Description

The portable-simd intrinsics simd_bitmask and simd_bitmask_select work with a bit-efficient representation of a SIMD vector of bool. Specifically they actually support two representations: as an integer of sufficient size, and as an array of u8.
However, the exact format of the array-based bitmask is endianess-dependent in subtle ways, so much so that portable-simd stopped using that format. The integer-based format is pretty simple (albeit still being endianess-dependent) but does not scale to vectors of arbitrary size.

IMO we should only have one format supported by the low-level intrinsics, and leave it to higher-level code like portable-simd to convert that to other formats if needed. That one format probably has to be the array-based one, since that is the only way to actually support vectors of arbitrary size. But what should that format look like? Currently it is endianess-dependent, and then portable-simd has to do some work to convert that into an endianess-independent format and back. Can we make the intrinsic directly use an endianess-independent format? (It is extremely rare for our intrinsics to behave in an endianess-dependent way.)

What are the key constraints the format has to satisfy? Without knowing those, here's a completely naive proposal:
the array must be big enough to contain at least as many bits as the vector has elements (but that's just a lower bound, arbitrarily bigger arrays are allowed), and then vector elements are mapped to bits in the array as follows: the vector element i is represented in array element i / 8, in the bit i % 8, where bits are indexed from most significant to least significant. So for instance the vector [-1, -1, -1, 0, 0, 0, 0, 0, 0, -1] becomes the bitmask [0b11100000, 0b01_000000], simply filling in the vector elements left-to right bit-for-bit and then padding with 0 until the array is full. I don't know if that format is any good -- probably it is not -- but it is certainly easy to explain. :)

Cc @calebzulawski @workingjubilee @programmerjake @rust-lang/opsem

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start with the portable-simd intrinsics simd_bitmask and simd_bitmask_select, then read Rust PR #126171 and portable-simd PR #423 for the endian-dependent representation and its replacement. Determine the constraints an array-based format must satisfy and reach agreement on one representation; done means the format and rationale are clearly specified.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
compilers
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.