Changes to Compress implementation (including whether new [Non]PartitioningCompress ops should be added)
- Dominant language
- C++
- Stars
- 5.8k
- Forks
- 471
- Avg merge
- 1d 6h
- Merged PRs (30d)
- 81
Description
The default Compress implementations in x86_128-inl.h (for SSE2/SSSE3/SSE4/AVX2 targets), x86_256-inl.h, ppc_vsx-inl.h (for at least PPC8/PPC9), arm_neon-inl.h, loongarch_lsx-inl.h, loongarch_lasx-inl.h, wasm_128-inl.h, and wasm_256-inl.h should be deduplicated and moved into generic_ops-inl.h.
In addition, it is possible to reimplement I16/U16/I32/U32/F32 Compress on PPC10 to do `TableLookupBytes(v, detail::CompressOrExpandIndicesFromMask(d, mask))` instead of using the generic implementation, although `TableLookupBytes(v, detail::CompressOrExpandIndicesFromMask(d, mask))` is not guaranteed to be partitioning on PPC10 (due to `detail::CompressOrExpandIndicesFromMask(d, mask)`, which is a wrapper around the PPC10 xxgenpcvbm/xxgenpcvhm/xxgenpcvwm instructions, returning implementation-defined indices in the bytes past the first `CountTrue(d, mask) * sizeof(TFromD)` bytes of the result returned by `detail::CompressOrExpandIndicesFromMask`).
One of the main reasons why I16/U16/I32/U32/F32 Compress was not reimplemented to use `TableLookupBytes(v, detail::CompressOrExpandIndicesFromMask(d, mask))` was that the default generic implementation of Compress is likely more efficient for a partitioning compress on PPC10 (which can take advantage of the fact that the index to the compress table can be easily obtained using vextracthm/vextractdm on little-endian PPC10).
There are some use cases for adding a new compress op without partitioning guarantees on PPC10, including in the implementation of ops such as CompressBlendedStore where we only care about the first `CountTrue(d, mask)` lanes of the compress result and where doing a compress using `TableLookupBytes(v, detail::CompressOrExpandIndicesFromMask(d, mask))` is more efficient for I16/U16/I32/U32/F32 vectors.
In addition, on SVE targets, it is also possible to efficiently implement partitioning compress using `detail::Splice(CompressNot(v, mask), Compress(v, mask), FirstN(d, CountTrue(d, mask)))`.
On RVV targets, it is possible to implement partitioning compress using `detail::SlideUp(Compress(v, mask), CompressNot(v, mask), CountTrue(d, mask))`.
There is a use case for both a compress op with partitioning guarantees and a compress op without partitioning guarantees, as there are performance benefits to having both a compress op without partitioning guarantees and a compress op with partitioning guarantees on a few targets such as PPC10, SVE, and RVV.
Should new PartitioningCompress or NonPartitioningCompress ops be added?
Contributor guide
Research direction
Start by comparing the Compress implementations in x86_128-inl.h, x86_256-inl.h, ppc_vsx-inl.h, arm_neon-inl.h, loongarch_lsx-inl.h, loongarch_lasx-inl.h, wasm_128-inl.h, and wasm_256-inl.h with generic_ops-inl.h. Review the PPC10, SVE, and RVV cases described in the issue, then determine whether partitioning and non-partitioning operations are needed; done means the implementation is deduplicated and the operation design is resolved.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp, wasm
- Domain
- performance
- Issue type
- Refactor
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Quiet
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100