google / google/highway

Changes to Compress implementation (including whether new [Non]PartitioningCompress ops should be added)

Open
#3,142 3 comments 0 reactions 0 assignees View on GitHub
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.