Re: [eigen] New indexing/slicing API: almost ready to be merged

[ Thread Index | Date Index | More lists.tuxfamily.org/eigen Archives ]



On Fri, Jan 13, 2017 at 5:43 AM, Gael Guennebaud <gael.guennebaud@xxxxxxxxx> wrote:

(Sorry in advance, this email is, again, way longer than I expected)

Alright, let me share a few remaining details and concerns that would be nice to address for 3.4 regarding this indexed/slicing feature. There are 6 topics, skip the ones you don't care much.


1) ---------- Block-like shortcuts ---------- 

The "block API" has pretty convenient shortcuts as: topRightCorner, middleRows, leftCols, etc. that ease readability and reduce redundancy. It would be nice to elegantly cover all these shortcuts with the new API. Since each dimension is now treaded independently, we only have to cover four cases corresponding to all, segment(i,n), head(n), and tail(n). The first two are well covered by all and seqN/seq. For the last two we have:

head(n) <--> seqN(0,n)

tail(n) <--> seqN(placeholders::end-n,n) or seq(placeholders::end-n,placeholders::last)

whereas "seqN(0,n)" reads OK, something as simple and frequent as taking the last n element should be easier to write/read. Here, using either seq or seqN we have to repeat ourself which is never good. So I think we should really add an alias for seqN(placeholders::end-n,n), and for symmetry, adding an alias for seqN(0,n) might be a good idea too. What about:

  firstN(n), firstN<N>, firstN<N>(n)
  lastN(n), lastN<N>, lastN<N>(n)

The "firstN<N>(n)" version is for hybrid fixed/dynamic values (see point 6).

This way, A. topRightCorner(rows,cols) becomes:

​​
  A(firstN(rows), lastN(cols));

If you want the top-right-corner with opposite corner at (i,j) (very common but cumbersome with topRightCorner()):

  A(seq(0,i), seq(j,last))

Pretty readable, no redundancy, no need for additional shorcuts taking a bound instead of a size.

​Yeah I am totally for it.

I do think those capitalized "N"s are a little jarring to the eyes.. first(n) and last(n) reads perfectly clearly by themselves. Now last(n) collides with last, but I'd argue for renaming either of them, e.g., maybe use head(n) and tail(n).

Also, for what it's worth, I do prefer 'seqn' to 'seqN'. I feel the word "seq" is already short enough that adding an extra letter differentiates it enough. Of course I do realize that 'N' helps emphasizing the difference between seq and seqN so it helps with maintaining correctness. In the future I would probably use a + iota(n) * d for all seqN usage cases.


2) ---------- placeholders ----------

I currently wrote:

  placeholders::all
  placeholders::last
  placeholders::end = last+1

I used "placeholders" to be consistent with std::placeholders, but I'm not sure that's a good idea.

I put "all" in this namespace, but so far it does not really behave as a placeholders. It more like:

Eigen::NoChange -> used in mat.resize(rows,NoChange)
Eigen::Default -> used in some_solver.setSomeParameter(Default)

Then perhaps, Eigen::placeholders::all should be moved and renamed as Eigen::All??  This choice might also be conditioned by the next topic.

​I agree "placeholders"​ is not a great names. I don't have any better idea. The std library does puts custom literals like piecewise_construct right in the top level namespace.
 


3) ---------- Reverse and Replicate ----------

Another very desirable feature to have for 3.4 would be to cover Reverse and Replicate features. This is already possible when the indices are stored in a Eigen::ArrayXi:

  MatrixXd A;
  ArrayXi rows, cols;
  A(rows.reverse(),cols.replicate(10));

but ideally we would like to be able to do it for seq/seqN and "All", we could have (for convenience say A is a 3D multi-dim array ;) ):

   A(All.reverse(), All.replicate(10), seqN(0,fix<N>).replicate(fix<10>))

I actually find it confusing that I can reverse an All literal. I would much prefer to let 'All' just have a simple meaning, and leave the _expression_ of more complex sequences to explicit seq and seqn's with end or last symbols.
 
it's weird to add members to "All" but if you chain free-functions this does not read nicely:

   replicate(reverse(All), 10)

and I'd like to avoid fancy pipe syntax: "All | reverse() | replicate(10)".

This question also depends on how we really want to define the identifier "All". If we defined it as:

  static const decltype(seq(fix<0>,last)) All;

then writing All.reverse() suddenly makes sense, but we won't be able to use "All" in other contexts.

Perhaps we can simply omit the "All" and do:

   A(reverse(), replicate(10)) <-->  A.colwise().reverse().rowwise().replicate(10)

??


Now, what if I want to pick column j and replicate it 10 times horizontally ? That's already possible:

   A(All, seqN(j,10,fix<0>))
   A(All, ArrayXi::Constant(10,j))

Would replicate(j,10) be more readable? (as in replicate(All,10))


4) ---------- make seq/seqN usable as alternatives to LinSpaced ----------

It would be nice if seq/seqN could also be used as an alternative to the current LinSpaced method. If we only want to use them for filling an existing arrays of integers, then it might be enough to add an operator= overload to DenseBase. If we want them to be used in expressions as a NullaryExpr, we need a way to specify the scalar type (perhaps even floating-point types), and whether we want an Array or a Matrix. What about reusing the .array()/.matrix() methods of ArrayBase/MatrixBase, and specify the scalar type as a template argument:

  ArrayXd = cos(seq<double>(0,M_PI,0.1).array());
  VectorXd = seqN<double>(0,20,0.1).matrix().transpose() * mat;

By default seq/seqN  would always construct an ArithmeticSequence with Index as the scalar type.


5) ---------- use symbolic index ----------
  
The symbolic indices 'last' and 'end' could also be used as indices to operator(), e.g.:

  A(last,end/2)  <-->  A(A.rows()-1, A.cols()/2)

That's a simple addition. I don't see any harm is doing so.


6) ---------- fix<N> ----------

I propose to apply this technique to pass compile-time integer parameters everywhere else it makes sense. A typical example is the block methods for which you currently have to write in templated code:

mat.template block<N,M>(i,j)

or, if only the number of rows is fixed:

mat.template block<N,Dynamic>(i,j,N,m)

With the new strategy:

mat.block(i,j,fix<N>,fix<M>)
mat.block(i,j,fix<N>,m)

no more "template" weirdness that nobody knowns about the first time they try to call this block overload. (side story: I've heard that the std committee chose a free function for get<N>(tuple<...>)  instead of letting it be a member function mostly because of this c++ weirdness).

Now, what if I pass fix<N> to a function foo(Index) that does not expect a compile-time value? That depends:

  foo(fix<N>)   // OK in C++14, equivalent to foo(N), no overhead. Does not compile in C++98/11

  foo(fix<N>())   // OK in both C++14 and C++98, no overhead

No big deal here.


There is however still one missing feature that is the ability to pass both a compile-time value 'N' AND a runtime value 'n' as a fallback in case 'N' means the compile-time value is undefined. Typical use case:

template<typename Derived> void foo(const MatrixBase<Derived> &mat) {
  const int N = Derived::RowsAtCompileTime==Dynamic ? Dynamic : Derived::RowsAtCompileTime/2;
  const int n = mat.rows()/2;
  if(N==Dynamic)
    mat( seq(0,n, j)
  else
    mat( seq(0,fix<N>, j)
}

the branch can be omitted by extending Eigen::fix such that fix<N>(n) returns something like:

template<int N> struct fixed_or_dynamic { Index m_value; };

Then we can merge the two branches:

mat( seq(0,fix<N>(n), j)

and it is up to the callee to either use N or n thanks to some helper. With this strategy fixed_or_dynamic<N> always has to store and pass a runtime value because depending on the context "undefined at compile-time" can be represented by either Eigen::Dynamic==-1 for sizes, or by Eigen::DynamicIndex==0xffffff for values that can be negative such as increments. In practice, I believe the compiler is able to get rid of it, so I don't think this is much a concern.

The other option would be to add two variants of fix<N>(n) for signed and unsigned quantities, that is, shortcuts to internal::variable_if_dynamic and internal::variable_if_dynamicindex that we already have in Eigen to declare members that can either store a runtime value or be empty if known at compile-time:


Here, I don't think we need to go that far because the object returned by fix is not supposed to be stored at all.


gael


On Wed, Jan 11, 2017 at 6:09 PM, Gael Guennebaud <gael.guennebaud@xxxxxxxxx> wrote:

On the user side, it provides the following static variables and functions:

  fix<N> // for fixed size parameters
  seq(start, stop [, incr])
  seqN(start, size [, incr])
  placeholders::all
  placeholders::last
  placeholders::end = last+1

PLEASE, do everyone agree on this? From the last discussions, I've introduced a placeholders namespace to ease importing the whole Eigen namespace. The user can then cherry pick the placeholders they frequently use:

  using Eigen::placeholders::last;

or all of them, or make aliases... Perhaps we can find a shorter name for this namespace?

Each parameter of the new DenseBase::operator() is compatible with:
  - a single integer
  - Eigen::all
  - any return-type of seq and seqN
  - any type providing a size() and operator[](integer) members
  - plain C array like A({2,3,4}) in c++11 (and not too old clang)

Some remarks:

 - expressions of booleans (aka masking) is not supported yet. It could be by first converting it to an array of indices if there is a high demand.

- The last and end symbols can be used as the start, stop, and size parameters of seq and seqN

- They support any arithmetic operations, including, e.g.,  end/2+1, and supporting sqrt(end) is a matter of 5 lines of code max.

- fix<N> can be used as the size and incr parameters of seq and seqN


Regarding some internal implementation details:

 - The return type of operator() is a old good Eigen::Block if possible. This means that A.tail(a) is strictly equivalent to A(seq(a,last)), there are more equivalence example in the unit test.

 - seq(a,b,d) is just an alias to seqN(a,(b-a+d)/d,d) where (b-a+d)/d can be a symbolic _expression_ if a and/or b are based on the last/end symbols. (the c++11 implementation of seq is trivial, the c++98 is horrible)

 - to support arbitrary expressions on last/end symbols I've implemented a minimalistic _expression_ template engine specialized for expressions of Index types. In C++14 it can support an arbitrary number of symbols, might become handy in the future. There is an example there:



gael



Mail converted by MHonArc 2.6.19+ http://listengine.tuxfamily.org/