Re: [eigen] On a flexible API for submatrices, slicing, indexing, maskin

On Thu, Dec 29, 2016 at 6:02 PM, Gael Guennebaud <gael.guennebaud@xxxxxxxxx> wrote:

On Thu, Dec 29, 2016 at 9:23 PM, Yuanchen Zhu <yuanchen.zhu@xxxxxxxxx> wrote:
Regarding the initial subject, I'm pretty satisfied with the current proposal of using:

range(start, stop);
range(start, stop, step);
range(start, stop , c<STOP>);

span(start, length);
span(start, length, step);
...
span(start, c<LENGTH>, c<STEP>);

I have a few concerns regarding the syntax of c<>:

Thank you for taking part in the discussions.

You're welcome. I'd love to see Eigen code become as succinct as (well-written) matlab/julia code.

First, using c<> to encode a compile time parameter is a rather novel convention, foreign to most programmers, engineers, matlab users, or basically anyone.

Yes, I'm also not 100% sure about it, but at least it has the great advantage of not disturbing the parameter orders. The implementation is also compatible with integral_constant defined with literals (using namespace boot::hana::literals): 3_c

Interesting. User literal changes the equation. To me range(1, n, 3_c) does look cleaner than range(1, n, c<3>). And most importantly the name space of user literals is significantly less populated than that of types. I would even argue it should be the default and preferred notation.

The downside is of course it's still a new convention.

Second, it begs the question of whether c<> can be used for any parameter of range and span. People will then take a pause for every parameter of every invocation of range and span, to consider if they want a static or dynamic value in the hope of producing more optimized code. They might write things like range(c<1>, ncols, c<3>). I feel this adds noise to both thinking and notation, compared with just range(1, ncols, 3).

Third, I feel we need to carefully weigh the syntax burden against the optimization opportunity it produces. Hence we need to examine what is returned by invoking operator () on these range descriptors. It might be the case that a particular static parameter will produce minimally more optimized code, in which case can we justify paying the extra syntax tax?

Right now, only static matrix size plays a role in determining the type of the returned block. Static matrix size is also a parameter to the Eigen matrix type, so it is probably already internalized by the user. I hope we don't add additional rules on static parameters usage with the new API, unless there is a really good reason.

Actually compile-time step is equally important as compile-time size. A typical use case is in a templated code where the step could turn out to be 1 (depending on the template arguments), in which case being able to write:

range(start,stop, c<Step>)

is key. In the future we might also be able to efficiently vectorize code with step==2. Compile-time step is already part of Eigen::Map and Eigen::Ref (see third template argument and class Eigen::Stride).

I see. I agree.

For the "start" argument, currently I don't really plan to allow for compile-time value, though the case start=0 is sometimes useful to figure-out alignment or for sparse matrices. This case is currently part of the Block API using specialized members (middleRows, leftCols, etc.)

I think the user will expect a compile-time start/stop to be valid usage, especially since span allows TWO of its parameters to be static. It is going to be a real hassle to remember what can be static and which cannot.

Also, sometimes people may just want to provide a pair of compile-time (first, last), and get in return a compile time sized matrix, especially in unit tests. In that case, my order of preference is:

M(range<2, 10, 2>) // pretty succinct

M(range(2_c, 10_c, 2_c)) // acceptable, especially if editor color code 2_c's as literals.

M(range(c<2>, c<10>, c<2>)) // Ugh! So much noise for so simple an _expression_

With these considerations, let me just throw around some more alternatives:

range(first, last, step = 1)
range<len>(first, last, step = 1)

The second line provides twice the same information, so you probably want to use a span in this case. Since compile-time step is important, I would rather consider:

range<STEP>(first, last, step = STEP)

span(first, len, step = 1)
span<len>(first, step = 1)

this would be OK if we don't plan on having compile-time step.

or

range(first, last)
range(first, last).step(10)

interesting, but a bit odd because I would expect it to return the 10th step of the given range??? Perhaps:

range(first, last).setStep(10)
range(first, last).setStep<2>()

but since in C++ optional arguments go last, I guess its fine to put the step in last position as in python.

Yeah I guess we can always just pick a convention.

Still, when you read old code, or debug a hard to track memory bug, do you ever get that nagging suspicion that you have the order of last and step wrong somewhere? I know I do.

Actually, I just though about another case that is not covered by the current proposal, that is templated code where the length (and/or step) could be either a compile-time or run-time value. For instance, with the block API we have:

A.block<Rows,Cols>(i,j,rows=Rows,cols=Cols)

this way one may write:

A.block<Dynamic,ColsAtCompileTime>(i,j,rows,actual_cols)

with ColsAtCompileTime being either Eigen::Dynamic (=-1) or a positive compile-time integer.

If we want to support this flexibility for both lengths and steps (and I think we do), then we first need to introduce a Eigen::DynamicStep=0 value because -1 is valid step whereas 0 is not, and then, following the current proposal, we could imagine something like:

span(start, c<LEN>(actual_len), c<STEP>(actual_step))

and let the span function figure-out whether the compile-time value is truly a compile-time value, or whether it should get the run-time value passed as argument.

Yeah I agree you probably need something like c<STEP>(actual_step) for generic code. Although I'd argue you should still allow c<STEP> and c(step) to work.

Here is another related idea: Instead of using a generic c<N> to provide step or length, make both of them named parameters. This way we even remove artificial conceptual separation of range and span (which is yet another convention to memorize). Otherwise, when you see span(3, 10), you will always have a nagging suspicion: is this 3..10 or 3..12?

Here're some examples:

V(span(i, j)) // first..last

V(span(i, j, step(s))) // dynamic step

V(span(i, j, step<S>)) // static step

V(span(i, j, step<S>(s))) // support both dynamic and static step

V(span(i, len(n))) // dynamic span length

V(span(i, len<N>)) // static span length

V(span(i, len<N>(n)) // support both dynamic and static span length

V(span(i, len<N>, step(s))) // static size, dynamic step

V(span(i, len(n), step<S>(s))) // dynamic size, static/dynamic step.

...

We now have a simple consistent rule to remember: non-index parameters, len and step, are always named, and can be dynamic, or static, or both. This syntax adds a little verbosity, but avoids lots of confusion and greatly improves readability, imo. The simplest case, span(i, j), is also now identical to Armadillo's syntax.

We may or may not want support static indices. If we do, i and j can be supplied as compile time constants using the user suffix syntax, e.g., 3_c, as you described before. Alternatively, we can have the rule that indices can be supplied as template parameters to span. Consider:

V(span<3, 6>) vs V(span(3_c, 6_c))

V(span<3, 6>(step(s)) vs V(span(3_c, 6_c, step(s)))

V(span<3, 6>(step<2>)) vs V(span(3_c, 6_c, step<2>))

V(span<4>(len(n)) vs V(span(4_c, len(n))

V(span<6>(len<8>, step(s))) vs V(span(6_c, len<8>, step(s));

All except the first row look too noisy to me, so maybe we should just not support static indices...

In a parallel note, I would love for people to brainstorm more alternative names for range and span, since those are just about used everywhere, and the convention is all over the place. For example, armadillo's span takes in (first, last) instead of (first, len), and boost::range has an irange(first, last) function for integer range, and gsl::span takes in (first, len).

Yes, that's the main purpose of this thread and wiki-page!

gael

and forget about the "iota"-based API. What remains unclear to me is how to expose this compact 'c' function. I also have to generalize the proof-of concept demo to be sure that we can generalize it to multi-dimensional tensors.

gael

I'm currently experimenting with an API like:

range(start,stop); // step==1
range(start,stop,step); // run-time step
range(start,stop,c<STEP>); // compile-time step

span(start,len); // step==1
span(start,len,step); // run-time step
span(start,len,c<STEP>); // compile-time step
span(start,c<LEN>); // compile-time length and step==1
span(start,c<LEN>,c<STEP>); // compile-time length and step
span(start,c<LEN>,step); // compile-time length and runtime step

And the usage remains the same, e.g.:

B = A(range(...), span(...));

Some remarks:

The key advantage here is that the argument order never change! For the "range" case, it would be ok to write range<STEP>(start,stop), but for the "span" case since the length needs also to be defined at compile-time this is unmanageable.

Another advantage compared to the demo on the wiki is that the "bounds-based" and "length-based" variants are similar, no odd API like the iota(len) stuff... Of course, this is also a drawback because there might be some naming confusions between 'range' versus 'span'. It might not be 100% obvious that one is based on 'bounds' and the other on a 'length', but here is the rationale:
- 'range' is (for me) more related to the notions of interval, limits, gamut, etc. that are naturally defined by their 'bounds'.
- 'span' is related to the notion of period of time, distance, width, extent, etc. and thus the notion of 'length' here.

Compared to the demo on the wiki page, here the 'step' is moved to the last argument. This is not matlab friendly, but in c/c++ optional arguments go last, so this makes more sense.

Another issue is that this approach is very compact only if we accept to define a Eigen::c and that the user import it in its current scope and use c++14 (perhaps c++11 with Yuanchen trick?). Otherwise it can become as verbose and unreadable as:

Eigen::span(start, Eigen::Index_c<LEN>(), Eigen::Index_c<STEP>())

Finally, we also have to decide whether the 'stop' argument should be an inclusive or an exclusive upper bound... To figure this out, I'll prepare a set of examples to see what's the most convenient. My intuition is that even though we are used of the STL's exclusive 'end', an inclusive upper bound would be more symmetric with the inclusive lower bound, and thus indexing from the end should be easier...

OK, one more: with this approach we could easily enable compile-time start/stop with range to figure out the length at compile time: range(c<START>, c<STOP>) , but I don't really see the needs for it as IMO if the size can be known at compile-time, then you probably better know it than the bounds, especially if you have to think about whether the upper bound is inclusive or exclusive.

What do you all think about it?

gael