Optimize foldings of repeated sorted values, if the reducer is distributive

[Rudxain]

I go into further detail here

I'm aware this optimization may be considered "too niche", but I believe it makes more sense for a compiler to do this automatically than for a human to explicitly use this algorithm at runtime.

I'm also aware of the fact that it would be unlikely for an optimizer to infer that a dynamically-generated list has all of its values sorted and that the set of unique values is small relative to the list length.

However, it's much easier to apply this optimization if the list contents are statically-known. Yes, the optimizer might prefer to do constant-folding, but if the list is big enough it might be better to fold at runtime, where this optimization shines

[nikic]

I have no idea what you're asking for here. Can you please provide a code sample and how you expect it to be optimized?

[Rudxain]

TLDR: Instead of sum(0 0 1 1 1 2 2 3 3 3 3 4 4) being calculated as 0+0+1+1+1+2+2+3+3+3+3+4+4, it gets optimized to 0*2 + 1*3 + 2*2 + 3*4 + 4*2. It works better for ints, but can be applied to floats if accuracy isn't important. Same principle applies to products, not just sums

[abhishek-kaushik22]

Not going into the implementation details, what happens if the list is all distinct? This optimization depends heavily on the use case and not something general a compiler can implement. And you probably should use std::reduce anyway and let the compiler vectorize it which will be faster than this.

[Rudxain]

what happens if the list is all distinct?

Unfortunately, the optimization doesn't apply (because of overhead), and constant-folding (or something more appropriate) should take its place.

vectorize it

That applies if the list isn't, say, a 1GB bitvec. It'll be faster to do a binary-search than SIMD, even if the SIMD is parallelized.

Essentially, the algorithm becomes faster as the entropy drops. That's why bools are faster than u8s, even when the byte-size of the list is the same (it should be faster even if there are more bools than ints)

[abhishek-kaushik22]

@Rudxain Interesting.

I might be wrong, but I still feel like implementing this is way too complex for any possible benefits that might come from this optimization. Do you have any benchmarks that might require this optimization?

[Rudxain]

Do you have any benchmarks that might require this optimization?

Not yet 🙁