Re: [boost] lifetime of ranges vs. iterators

Subject: Re: [boost] lifetime of ranges vs. iterators
From: David Abrahams (dave_at_[hidden])
Date: 2008-09-03 13:09:04

on Wed Sep 03 2008, Arno Schödl <aschoedl-AT-think-cell.com> wrote:

>> > rng | filtered( funcA ) 
>> >     | filtered( funcB ) 
>> >     | filtered( funcC ) 
>> >     | filtered( funcD ) 
>> >     | filtered( funcE )
>
>> 1. _Do_ they write that?  
>
> Why not? They did for transform_range, and the notation is getting easier...

Yes, I never contested that they *could* write it.

I'm still asking you the same question: what real life computations
demand a solution to this problem?

>> 2. If they do that, I believe they are still paying an enormous
>>    unnecessary runtime penalty even with your optimization because of
>>    the endpoint checks in each layer of the composite iterator or
>>    range.  The only way IIUC to avoid such a penalty is to compress the
>>    filter adapters into one, essentially by using expression
>>    templates.
>
> See answer to 4.
>
>> 3. I am not yet convinced that you are suffering a significant
>>    performance penalty due to the wasted space in real applications.
>>    Have you measured it?  Unless you're actually *storing* lots of
>>    these stacked iterators or passing them around by value in your
>>    inner loops, it seems unlikely to make much of a difference.
>
> Giovanni has seen the quadratic stack expansions. 

Sure, but that does not necessarily amount to a significant performance
penalty.

> If you are worried about performance of pointers, why not worry about
> the performance of wrappers around pointers?

I actually am a bit worried about it.  However, as I am trying to tell
you, I don't believe that what we're talking about here addresses the
whole underlying problem.  You're talking about eliminating redundancy
across pairs of iterators, but AFAICT not the redundancy through the
vertical "stack."

>> 4. I can understand wanting to improve these components so that they
>>    can be efficient under more conditions, and avoiding the redundant
>>    storage would undoubtedly be a real improvement.  However, I think
>>    there's a deeper inefficiency in stacking all those filter iterators
>>    together, and it's neither a range library's job, nor I think is it
>>    possible in this case, to protect users from "blissful unawareness"
>>    of performance implications.
>
> The design we came up with addresses the general problem of stacking
> range_adaptors that must store their end, like
> difference_range/filter_range/union_range/[other algorithms that I cannot think
> of now], in any combination. 

OK, let me try to spell this out.

Let's suppose for a moment that you build a
filter_iterator<strided_iterator<int*,5>, F>.  A strided_iterator is one
that visits every Nth element.  Unless you know that there are an even
multiple of N elements, it needs to store an endpoint because otherwise
the iterator might stride right past the last stored location.

  Thus sizeof(strided_iterator<int*,5>) == 2*sizeof(int*)

and its increment operator looks like:

  if (pos <= end - N)
      pos += N;
  else
      pos = end;

Now as you know, a filter_iterator also needs to store an endpoint.  So
assuming F is empty and EBO is used to eliminate its storage, then

  sizeof(filter_iterator<strided_iterator<int*,5>, F>) 
  == 2*sizeof(strided_iterator<int*,5>)
  == 2*2*sizeof(int*)

and the filter iterator's increment looks like:

  do {
      ++pos2;
  }
  while (pos2 != end2 && !f(*pos2));

Now if we expand the incrementation of pos2, it's

  do {
      if (pos <= end - N)
          pos += N;
      else
          pos = end;
  }
  while (pos2 != end2 && !f(*pos2));

Whereas it should only be:

  do {
      if (pos <= end - N)
          pos += N;
      else
          pos = end;
          break;
  }
  while (!f(*pos2));

No approach that only addresses the space wasted across pairs of
iterators can help with these issues, so I think a more fundamental look
at the problem is called for.  And again, I think the problem is very
much like what happens with segmented iterators so its worth looking
there for inspiration.  It may be that, as with segmented iterators, a
more general form for the algorithms is called for.

> If you have thought up expression templates that cover all of these in
> a unified fashion with better performance than stacked iterators, I'd
> be very happy and try to implement that instead.

Again, I'm not ready for answers yet.  I'm only just now discovering the
questions.

>> I'm not yet convinced we're solving a real problem here,
>
> I have enough of that stuff in my code that I am convinced we do.

That fact alone does not make it a real problem in my book.

>> and if it _is_ real, I am not quite convinced the general approach of
>> squeezing out redundant storage would address all of the problem.
>
> It does not, you already mentioned the superfluous end checks. As I
> said, if you have the whole solution, let me know.

I'm not there yet, but I know enough about the problem now that I
wouldn't "buy" a partial solution.

-- 
Dave Abrahams
BoostPro Computing
http://www.boostpro.com