Draft: Extend the TranformedRangeView to allow constructing the iterators directly

Summary

The TransformedRangeView is a utility to transform a range (or its iteratoors) during traversal with a function. This is very useful to write special iterations. But when writing containers, one has to implement the begin() and end() function that directly return the iterators. This was not possible with the TransformedRangeViewIterators before, since there a function pointer was stored and not the function itself, making it unusable with lambda expressions, for example. And resulting in lifetime issues when this is overseen.

This MR stores the function directly, in a RegularOptional wrapper, that extends the type by copy/move assignment and default constructability functionality. This was not possible with standard lambda expressions, for example.

added feature label

assigned to @carsten.graeser

That's a breaking change.

But maybe OK, since the class is in Impl.

As far as I can see, this change will have a huge impact, because a TransformedRangeView now copies the callback when creating iterators. The decision to use pointers here was deliberately, because it allows to pass lambdas with nontrivial capture as callback:

auto createFooRange()
{
  // Setup internal data
  return transformedRangeView(Dune::range(size), [data=std::move(data)] (auto i) {
    return computeValue(data,i);
  });
}

here the data may e.g. be a large vector. Notice that this is currently inefficient already, because the lambda is not properly moved, but copied once. With the proposed patch it will be copied each time you create an iterator.

One could use reference_wrapper when creating iterators to prevent this. But I don't like this either, because it double wraps to implement something trivial: First we wrap a pointer to make it look like a value, then we wrap the value to allow empty state. This will probably also have a performance impact: While operator* of std::optional is not checked, it has to set a flag on assignment. If you use transformedRangeView in an inner loop, you do this many times.

Another issue: It would be nice, if transformedRangeView() works with mutable callbacks, to allow the above pattern for mutable containers. This is currently not possible but could probably be made working. With the proposed patch it's impossible.

Thus I'd rather suggest to follow what was already outlined in the comment: Allow to either use a plain pointer or use a wrapper if you want to copy the lambda. It seems that the already existing PointerProxy almost does the job.

When using PointerProxy we would just move the problem, because then you have to use the "regular_box" wrapper there in order to make it a regular type that is needed in the iterator.

Sure, multiple copies is not a good idea. I will think about an alternative. The RegularOptional works already like a pointer - has similar interface. One could improve the implementation of the box-class to always fallback to the original type if it is already a regular type. Then the reference_wrapper could be used directly without double wrapping.

Creating iterators in the hot-loop of an algorithm is probably not a good idea in general. Typically, the iterators are created outside and then just incremented. Only if you use the post-increment you would create multiple copies. This might indeed be a performance break.

I will look for alternatives.

Creating iterators in the hot-loop of an algorithm is probably not a good idea in general.

I don't see any reason why this should be true, unless you use iterators that are deliberately expensive. The latter applies to the TransformedRangeIterator after this patch, but not before.

The RegularOptional works already like a pointer - has similar interface.

Then the solution should be easy: Make FunctionPointer instead of F a template parameter of the iterator class, maybe rename it to FunctionStorage. Then the user can decide to use FunctionPointer=const F* or FunctionPointer=RegularOptional<F> depending on the application. Additionally we can provide a convenience factory method transformIterator(it, f) that switches between the two depending on l- or r-valuedness of f.

Creating iterators in the hot-loop of an algorithm is probably not a good idea in general.

Sorry, my statement was bullshit. std algorithms do this everywhere. Iterators should be cheap to create and to copy.

I'm using TrandformedRangeView in several critical places and thus did some measurements. So far it seems that you really don't have to pay for it in contrast to a raw implementation of the feature without the syntactic candy. Hence I'd like to keep this zero-overhead property.

In contrast, I did not measure your patch. But I fear, that the compiler might not figure out how to optimize this away if the number of layers increases. Thus I'd always opt for the more lightweight storage (i.e. a raw pointer) where possible.

Nevertheless I really want those free transformed iterators, since I had to hack around their lack a few times. Once we figured out how to implement the storage, we should export this to Dune::.... Since the iterators are no longer an implementation detail of the range we should also rename this to Dune::TransformedIterator or Dune::transformedIterator() (keeping the class in Dune::Impl::). The latter gives a bit more flexibility if we later want to modify the implementation as proposed here.

Have a look at !1390 (merged). This changes the meaning of the template parameter F to be pointer-like. The main intend is to correctly call transformations where operator() is non-const from non-const range and iterator. But it maybe also allows what you intended to do by passing an optional as F as suggested above.

You are faster than me. I had all these changes nearly ready, but you have already uploaded the MR :-)

I tested !1390 (merged) and indeed you can use it to create free TransformedRangeIterators storing an std::optional. But there's still a fundamental problem when using it with lambdas to generate iterators on the fly:

If you directly define the lambda when creating the iterator, the type of the lambdas and thus of the transformed iterators is different, such that you cannot compare them. I.e. the following does not work (assuming you have a factory function transformedIterator():

auto it = transformedIterator(Dune::range(0,42).begin(), [](auto x) { return 2*x; });
auto end = transformedIterator(Dune::range(0,42).end(), [](auto x) { return 2*x; });
for(; it!=end; ++it)
  std::cout << *it << std::endl;

You can of course first define a lambda using auto f = [](...) {...}; and the pass f to both iterators, but this is probably not what you intended, because if there's a single f outliving the iterators, you could use the existing version and store a pointer.

Ideally one should be able to generate those iterators independently in the begin() and end() method of a custom container because this can save a lot of work. A possible fix would be to allow comparison as long as the underlying iterator is the same.

I gave it a quick try: Templateing the other iterator and making all specializations friend with each other indeed solves the problem. The question which then directly comes up is, why I need a transformation at all for the end iterator. One may even add comparison against the non-transformed version of the iterator to avoid having to pass a dummy transformation.

For both features, comparison with other template instances and comparison with unwrapped iterator, we may discuss if we really want that. I'm tempted to say yes.

@simon.praetorius See !1392 (closed) for the respective patch. This demonstrates the non-invasive on-the-fly generation of free TransformedRangeIterator from (different) lambdas in the test. This may serve as a base for what you intended here.

However, it uses a plain std::optional, while you proposed a regular one, so it's probably an incomplete solution and thus marked as draft. It also does not make the functionality public so far. Since I don't oversee the implications of std::optional vs a regular one, I'll leave the rest to you.

There's one more thing I noticed: I originally did not use the iterator facades, because they do not allow for proper treatment of proxy-iterators, since they hardwire value_type* as pointer. This should be fixable by using the PointerProxy there, too. I just noticed that the same approach is used in the std::iterator_interface proposal (the modern incarnation of iterator facades), where the helper is called proxy_arrow_result.

!1396 (merged) contains the improved facades and on top of this cleans up the TransformedRangeIterator. By the way I simplified the function storage even more: We now check for value- and pointer semantics before applying the transformation. Thus we can store a raw pointer, a callback by value, a callback wrapped into an std::optional. This is demonstrated by the test.

mentioned in merge request !1389 (merged)

marked this merge request as draft

With !1396 (merged) merged, this should now be easy. E.g. the rangeutilitiestest.cc defines

auto transformedIterator = [](auto&& it, auto&& f) {
  using It = std::decay_t<decltype(it)>;
  using F = std::decay_t<decltype(f)>;
  using TIt = Dune::Impl::TransformedRangeIterator<It, F, Dune::ValueTransformationTag>;
  return TIt(std::forward<decltype(it)>(it), std::forward<decltype(f)>(f));
};

which allows to use transformedIterator(baseIt, [](auto&& v) { return ...; }) or transformedIterator(baseIt, std::optional([](auto&& v) { return ...; })). So it essentially remains to decide on how to expose this publicly.