25

For my matrix class I want to do some sort of operator overloading (probably using expression templates) on range-v3 views for + - / * % . For example if I want to get a view of the sum of two columns, I want to write 

col_1 + col_2

instead of

rv::zip_with([](auto c1, auto c2) {return c1 + c2;}, col_1, col_2);

Probably some ideas from this paper can be used to avoid constructing too many temporaries. Here is the code that I want to write:

//simple example
//what I want to write
auto rangeview =    col_1 + col_2;
//what I can write
auto rangeview =    rv::zip_with([](auto c1, auto c2) {
                        return c1 + c2;
                    }, col_1, col_2);


//itermediate
//what I want to write
auto rangeview =    col_1 + col_2 + col_3;
//what I can write
auto rangeview =    rv::zip_with([](auto c1, auto c2, auto c3) {
                        return c1 + c2 + c3;
                    }, col_1, col_2, col_3);


//advanced
//what I want to write
auto rangeview =    10*col_1 + 20*col_2 - 30*col_3;
//what I can write
auto rangeview =    rv::zip_with([](auto c1, auto c2, auto c3) {
                        return 10.0*c1 + 20.0*c2 - 30.0*c3;
                    }, col_1, col_2, col_3);


//more advanced with elementwise multiplication
//what I want to write
auto rangeview =    10*col_1 + 20*col_2 - col_2 % col_3;
//what I can write
auto rangeview =    rv::zip_with([](auto c1, auto c2, auto c3) {
                        return 10.0*c1 + 20.0*c2 - c2*c3;
                    }, col_1, col_2, col_3);
Zig Razor
  • 3,381
  • 2
  • 15
  • 35
Porsche9II
  • 629
  • 5
  • 17
  • 6
    This is a really, really broad question. What you're asking for is effectively an library for expression template - and there are many large libraries that try to solve this kind of problem in various domains. – Barry Feb 21 '19 at 23:25
  • And what about the intermediate example (just adding arbitrary number of views)? Still too broad? – Porsche9II Feb 22 '19 at 14:16
  • What is wrong with regular operator overloading? – Serge Feb 23 '19 at 20:00
  • With regular overloading you have to construct temporaries as explained in the paper (page 11) from above . – Porsche9II Feb 24 '19 at 18:19
  • You can simplify a bit by using `std::plus<>` (or `ranges::plus`). – L. F. Jul 14 '19 at 12:02
  • boost::yap or boost::lambda may give you some ideas. – Red.Wave Sep 26 '19 at 18:14
  • You've linked a paper promoting a library that does this already. The paper describes how it does addition, you just have to repeat that for the other operations you want. It will be *really tedious* to write it yourself. – Caleth Oct 02 '20 at 08:12

3 Answers3

1

Range views are supposedly lazy; Is it not why they are called views in the first place? So why not to return the resulting view in a user defined operand of your own? They'll ideally get evaluated, once the final range is iterated in a for loop or an algorithm.

IMHO not everything can be provided by the std or any other general purpose library. Some little tweaks are necessary using any tool:

decltype(auto) operator+(column const& col_1, column const& col_2){
    return rv::zip_transform( [] (auto c1, auto c2)
                                 {return c1 + c2;},
                             rv::all(col_1),
                             rv::all(col_2) );
};

A scalar * vector multiplication operator can be separately defined in a similar manor too. Then the linear combination of columns is written just as it is mathematically written. The actual calculations will wait till a for loop or an algorithm like std::fold or std::foreach traverses the range.

Lazy scalar * vector product becomes:

decltype(auto) operator*(range_value_t<column> const coef, column& col) {
    return rv::transform(rv::all(col),[=,coef](auto x){return coef*x});
};
Red.Wave
  • 2,790
  • 11
  • 17
  • This works fine and I currently use a similar appraoch in my code. But things like `10*col_1 + 20*col_2 - 30*col_3` will generate more temporaries than `rv::zip_with([](auto c1, auto c2, auto c3) {return 10.0*c1 + 20.0*c2 - 30.0*c3;}, col_1, col_2, col_3);` – Porsche9II Apr 26 '22 at 07:52
  • Even lazy evaluation is not cost free. Any lazy lib would store the scalar and a view of the vector for multiplication. The simplest solution is to `return rv::transform` with a coefficient capturing lambda as functor. If the dimensions of your matrix are countable with fingers, this approach is not suitable. Perhap small-value optimization can help if this is going to be a very generiy library. – Red.Wave Apr 26 '22 at 08:01
  • `rv::all` is supposed to get a view of original - probably container - view. Roughly speaking it is just a pair of [begin,end) iterators. So long as you use views, the temporaries remain compact. – Red.Wave Apr 26 '22 at 08:52
  • Do you have a working Compiler Explorer example using zip_transform? – Porsche9II Apr 27 '22 at 12:47
  • Not yet. I need to wait for a year or so. Ranges.v3 is missing some features. But zip family, hopefully comes with C++23. – Red.Wave Apr 27 '22 at 15:19
  • Inner product becomes `rv::zip_transform([](auto x, auto y){return x*y;},rv::all(vec1), rv::all(vec2)) | rv::fold([](auto v1, auto v2){return x+y;})` – Red.Wave Apr 27 '22 at 15:36
0

You main concern seem to be with (possible huge) temporaries that could be created. This can be solved with a concept called expression templates, but there is not really a one size fits all solution here. Best bet is probably switch to a matrix library that supports that. Unless you are developing a library or want to invest in this you probably want to steer away from writing your own expression templates. An easier method for getting closer, but without a lot of operator overloading/expression templates could be using range based for loop with custom iteration type (not as syntactically sugery as expression templates but much easier to implement):

Pseudocode:

*resultype* result;//perhaps alloc on this line or make zip handle it..
for (auto z : zip(result, col_1, col_2, col_3)) {
  z[0] = 10.0*z[1] + 20.0*z[2] - 30.0*z[3];
}

This is on the idea stage, but will be a bit shorter (and imho a bit more pleasing to read) than the lambda style. How to implement the zip class I leave out of this answer.

darune
  • 10,480
  • 2
  • 24
  • 62
0

I agree with @darune, unless you have a strong need, you should use a library, and in particular Eigen. Most of the operations you want to support are illustrated on This link.

Dilan
  • 2,610
  • 7
  • 23
  • 33
Mike MacNeil
  • 27
  • 3
  • I am using Armadillo for my numeric matrices - but I need this functionality for cell matrices where each cell is a std::variant of std::string, double, bool, ... – Porsche9II Oct 02 '20 at 11:29
  • Is this something like a dataframe? From above you've got `10.0*c1 + 20.0*c2 - c2*c3;`, you're doing that for std::string or std::bool? – Mike MacNeil Oct 02 '20 at 17:37
  • Just think of it as an Excel-Cell-Matrix where some columns are numeric but others not... – Porsche9II Oct 04 '20 at 13:24
  • 1
    Ah alright, well in that case you would need to implement your own expression templates to avoid copies, which are not straightforward and take some effort (this is what both Eigen and Armadillo are doing). But copies are also not a terrible thing, for example numpy runs really quickly and makes copies everywhere. The expression templates are more useful when you need to do certain operators millions of times over. – Mike MacNeil Oct 04 '20 at 17:45
  • @Porsche9II the spreadsheet programs do cache values (actually there are cases where re-evaluating is paused, e.g. as spreadsheet is included as MIME object into another document.) They use concept of "formula" object. Also spreadsheets typically have relative AND absolute addressing, it's behaviour that is standard from very first spreadsheet program ever.. E.g. in Excel formula that contains "A1" differs in behaviour from "$A$1". The former would change if you copy to other cell – Swift - Friday Pie Jul 27 '21 at 06:32