Revisiting fast mapslices

[bramtayl]

I was working on updating JuliennedArrays for 0.7 and I had some thoughts. Once we're over the 1.0 hill, it might be worth considering the (mostly, I think?) non-breaking infrastructure improvements that could lead to a fast mapslices.

1) There's been a ton of great work on constant propagation, but I think we still need #26050?

2) We need a cutoff to distinguish "large" tuples from "small tuples". It's usually faster to iterate over large tuples and unroll over small tuples. I think Tim Holy had a PR for this.

3) Type stable boolean indexing on small tuples with mixed type, e.g. (1, 2.0, "three")[(true, false, true]). This is only one of many operations that could become type-stable by unrolling small tuples (other examples include reduce, find, flatten, product, filter). This could all be done with lispy tuple iteration. If I understand correctly, creating a unified interface could unify lispy tuple iteration that is scattered across Base.

4) Formalized reduction functions. This would look something like

struct Reduce{F}
       f::F
end
(r::Reduce)(x) = reduce(r.f, x)
const sum = Reduce(+)

etc. Knowing whether some function is an reduction of another function would enable some crucial optimizations; compare the performance of mapslices and mapreducedims.

None of this is critical but none of it is too breaking (I don't think). Just worth thinking about.

[andyferris]

Nice package name!

I agree, we need more stuff like #4. I feel like I’m ready to ascend to the next plane of higher order programming and be able to reason more about the operations, introspect composed functions (and higher order functions), and so-on.

At least some of the tuple stuff might be feasible already without too many compiler improvements. E.g. much of the NamedTuple API seems to work well to me already.

[stillyslalom]

Any updates/thoughts on this? mapslices is still unduly slow (see here).

[bramtayl]

Constant propagation is still disabled by recursion, so to do this we'd still need TypedBools in Base (e.g. #23658 for an early prototype). And ideally, JuliennedArrays (or whatever else we want to call it) wouldn't have a pre-defined eltype, so it would be nice to have either ArrayLike (#34196) or a Trait based system. There's been significant resistance on both fronts, and I'm not sure what to do next to move this forward.

[bramtayl]

I can make a PR for type stable tuple selection with TypedBools, but I'd want some confirmation from higher-ups that I wouldn't be wasting my time.

[stillyslalom]

It might be easiest to combine efforts with @simonbyrne's PR #32310, since that already has affirmation from a number of higher-ups.

[bramtayl]

It seems like the outstanding issue from that PR is an eltype issue that could have been solved by ArrayLike, unless I'm mistaken.