Re: [boost] lifetime of ranges vs. iterators

Subject: Re: [boost] lifetime of ranges vs. iterators
From: Giovanni Piero Deretta (gpderetta_at_[hidden])
Date: 2008-09-05 10:27:58

On Fri, Sep 5, 2008 at 3:38 PM, David Abrahams <dave_at_[hidden]> wrote:
>
> on Fri Sep 05 2008, "Giovanni Piero Deretta" <gpderetta-AT-gmail.com> wrote:
>
>> 2008/9/4 David Abrahams <dave_at_[hidden]>:
>>>>>> But iterators like filter_iterator that need to know iteration
>>>>>> boundaries, can store a range instead of an iterator, so they can
>>>>>> benefit from the compression.
>>>>>
>>>>> Oh, I totally missed that; sorry!  Let's see...
>>>>>
>>>>>  strided_iterator<int*,5> stores range<int*>
>>>>>
>>>>>  sizeof(range<int*>) == 2*sizeof(int*)
>>>>>
>>>>>  filter_iterator<strided_iterator<int*,5> > stores
>>>>>    range<strided_iterator<int*,5> >
>>>>>
>>>>>  range<strided_iterator<int*,5> > is represented as
>>>>>
>>>>>    unique_data<strided_iterator<int*,5> >::type start;
>>>>>    unique_data<strided_iterator<int*,5> >::type finish;
>>>>>    common_data<strided_iterator<int*,5> >::type common;
>>>>>
>>>>>  unique_data<strided_iterator<int*,5> >::type == int*
>>>>>  common_data<strided_iterator<int*,5> >::type == int*
>>>>>
>>>>>  so its size is 3*sizeof(int*)
>>>>>
>>>>> ??  Did I get that right?
>>>>>
>>>>>
>>>>> If so, it seems like there's still redundant storage.  finish and common
>>>>> will be representing essentially the same information.  If I were to
>>>>> write a filter_strided_iterator adapter and apply it to int*, it would
>>>>> have the size of 2 int*s.
>>>>> a
>>>>
>>>> What information is contained in common that is not also contained in
>>>> finish (i've never implemented a strided iterator, I'm trying to
>>>> understand) ?
>>>
>>> My point is that there is essentially the same information in
>>> common and finish, but that you can't eliminate it because the
>>> abstractions don't allow it.  A strided_iterator implementation and test
>>> are attached.
>>>
>>
>> Hum, I have been thinking about this for a while, and the more I think
>> about it, the more it seems to me that that strided_iterator
>> implementation is not optimal.
>> Again, I've never needed one, so I'm not sure about the use case. I'll
>> try to reconstruct the problems from the hints you left in this
>> thread:
>>
>> Basically a strided iterator is an adaptor that visit every Nth
>> element in a range, where N is a compile time constant.
>
> Well, whether to make it a compile-time constant or a runtime one is a
> design decision you can make either way, but that's basically it.  You
> might use it to traverse the diagonal of a matrix, for example.

Ok.

>
>> From your
>> implementation I gather that the underlying range must be a random
>> access range. A straight forward implementation is a thin wrapper
>> around a random access iterator, you just replace operators ++ and --
>> with  +=N (with similar changes for operators + and -).
>>
>> The problem is that you want to visit ranges whose size is not an even
>> multiple of N, the above scheme wouldn't work, because before
>> comparison with endpoint, you would have already moved the iterator
>> beyond that end point. If the endpoint is one past the end of the base
>> range, you have UB.
>>
>> The solution used in your implementation is to actually store the
>> unstrided endpoint and position the internal  iterator at that end
>> point if the next increment would go beyond the boundary.
>> This requires a conditional branch in increment, and makes the
>> semantics of the iterator a bit surprising: you have to know the
>> boundaries of the iteration when you construct the begin iterator and
>> two iterators over the same underlying sequence with same stride and
>> phase, but constructed with different end positions, will actually be
>> iterating with diffent ranges (one iterator  can't reach the end
>> position of the other iterator).
>>
>> Now, the obvious solution is not to store the end position but instead
>> to use a base+offset representation which are only combined together
>> at dereference time.
>
> You're completely right about that, and there are even additional
> reasons that you didn't mention, as I realized a couple days ago.  I
> didn't want to bring it up, though, because it doesn't change the
> fundamental reality.  Just replace strided_iterator by another layer of
> filter_iterator.

Hum, but as long as an iterator contains only a range, you can always
encapsulate it with no space overhead. a
filter_iterator<filter_iterator<T* > >  has sizeof(T*2) (assuming a
stateless predicate), which is optimal.

>
>> [ in fact, searching the archives, it seems you are aware of this
>> implementation, so I guess there is some problems I'm missing if you
>> didn't use it]
>
> No, it's just that I've forgotten more in my life than I ever knew.

:)

> Remember, I forgot that you only need to store the endpoint of the
> underlying range (and not the beginning) if you implement
> filter_iterator correctly.
>
>> Assuming sizeof(size_t) == sizeof(void*), the size of this iterator is
>> the same as the size of your implementation.
>>
>> Now a base and range size are the only informations you need to
>> reconstruct begin and end
>>
>> begin.base = range.base;
>> begin.offset= 0;
>> end.base = range.base;
>> end.offset = range.lenght;
>>
>> Thus sizeof(strided_range) can be sizeof(void*)*2 which is optimal.
>
> Yes, but that doesn't change anything fundamental about the issue I'm
> trying to point at.

well it changes the fact that you need to provide another
counterexample, because a filtered_iterator<strided_iterator> has no
redundant information.

>
>> This doesn't of course prove that storing a range would lead to
>> optimal representation for all iterator adaptors, but at least is
>> enough for guaranteeing an optimal (in term of space)
>> filter_iterator<strided_iterator>.
>>
>> Am I missing something?
>
> You may be missing that the issue I'm describing applies more generally
> than in the single case of my
> filter_iterator<broken_strided_iterator<int*> > example.  It fails to
> optimize any case where the outer iterator and inner iterator are
> storing essentially the same information.

Yes, I must missing it, because, as I see it, as long as the
information can be espressed as a range, the outer iterator need only
a single instance of a range of the underlying iterator. If that range
representation is optimal, no information is duplicated.

The optimization breaks down when you need more than two iterators to
the same range, but I would like to see an example of such a beast
(yeah, I lack fantasy :) ).

And hey, I'm sure that beast exist, but if the optimization covers 90%
of the cases for little a little cost (you need to specialize it
associated_range and implement the optimal range for your iterators),
I think it is a win. Associated_range might actually be useful beyond
iterator nesting. And the optimization is optional, if
associated_range is not specialized, or the associated_range doesn't
guarantee optimal compression, everything will still work, but
redundant information will be stored.

-- 
gpd