google / google/highway

contrib/algo: questions on Reduce and ShuffleSpan before implementing

Open
#3,374 1 comment 0 reactions 0 assignees View on GitHub
Dominant language
C++
Stars
5.8k
Forks
471
Avg merge
1d 6h
Merged PRs (30d)
81

Description

I've just finished AllOf/AnyOf/NoneOf (#3370) and I'd like to keep going
through the "Remaining STL functions for hwy/contrib/algo" list. EqualSpan
and ReverseSpan look unambiguous and I'm working on those now. Reduce and
ShuffleSpan both have choices in them that I'd rather have your answer on
than guess at, since either one changes the whole shape of the function.

Reduce

1. Does the functor take vectors, like Transform's func(d, v), or scalars?
If it takes vectors, combining the lanes at the end needs a rule too, so
either the same functor has to be applied across lanes (which means
requiring it to be associative and commutative) or the caller passes a
second scalar combiner. I'd rather not invent that API myself.

2. Is the initial value a parameter, like std::reduce's init, or is Reduce
only defined for count != 0?

3. Should the result be bit-identical across targets? For float addition it
won't be unless the summation order is pinned, and pinning it costs most
of the speedup. ReduceSum has the same property today, so I suspect the
answer is no, but it decides what the test can assert.

My instinct: one vector functor, documented as requiring associativity and
commutativity, an explicit init parameter, and no cross-target bit-identity
guarantee.

ShuffleSpan

1. Which RNG? contrib/algo doesn't depend on contrib/random today. Is it
fine to add that dependency, or should the caller pass in a generator or
a seed?

2. Same seed, same permutation on every target? That one decides the
algorithm: a Fisher-Yates that's reproducible across vector lengths is
basically scalar, while the fast vectorised approaches produce a
different permutation per target.

3. Does it need to be a uniform permutation, or is an approximate shuffle
acceptable? Unbiased index generation costs a rejection loop.

My instinct here is much weaker than on Reduce, so I'm happy to go whichever
way you prefer, or to leave ShuffleSpan alone if it isn't worth the
dependency.

Contributor guide

Open the contributing guide

Research direction

Start with the remaining STL-functions list in contrib/algo and compare the existing Transform and ReduceSum APIs and tests. Resolve the open Reduce and ShuffleSpan questions—functor and initialization semantics, reproducibility, RNG dependency, and uniformity—before defining implementation work; done is an agreed API and test contract.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
performance
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Active
Clarity
Needs clarification
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.