contrib/algo: questions on Reduce and ShuffleSpan before implementing
- 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
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