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 19:36:59

on Wed Sep 03 2008, "Giovanni Piero Deretta" <gpderetta-AT-gmail.com> wrote:

> On Wed, Sep 3, 2008 at 7:21 PM, David Abrahams <dave_at_[hidden]> wrote:
>>
>> on Wed Sep 03 2008, "Giovanni Piero Deretta" <gpderetta-AT-gmail.com> wrote:
>>
>>>
>>> Do you think we are breaking the iterator abstraction? How? Or I've
>>> misunderstood the question?
>>
>> Well, if we add "Factorable" or something like it, the iterator
>> abstraction gets broken down into smaller bits for the purpose of
>> storage, complicating some code [like a generic range for example ;-)]
>> and it imposes an extra coding duty on writers of high-quality iterator
>> adaptors.  I'm asking if its worth it.
>>
>>> We are simply trying to come up with a simple and clean trick to keep
>>> iterator size under control.
>>
>> Really?  IIUC so far we're only discussing compressing the size of
>> ranges, unless we're willing to pay for indirection inside of iterators
>> (I'm not).
>
> 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

>> I don't understand why you would implement any_iterator yourself when
>> there are so many extant implementations, but maybe it's none of my
>> business.
>>
>
> Mostly for experimenting. I'll might end up using something third
> party in real code.
>
>>> Currently the iterators I use are often over 400 bytes, which is a bit
>>> to big :), thus the need to squeeze their size down as much as
>>> possible. A hundred bytes could be enough [1].
>>
>> Again, have you measured?
>>
>
> If you mean the size, yes, I've measured it. If you mean my assertion
> that 100 byte SBO may be optimal, then I wont' let facts interfere
> with my opinions :)

I meant measured that a type-erased 100 byte iterator improves
performance over a bald 400-byte iterator.

> Now, honestly, I'm trying to rationalize the fear that I had for a
> while that complex iterator adaptor sequences really can grow large.
> For example, the current filter_iterator double its size at every
> stacking. If you couple it with a relatively heavy predicate, the
> stack usage might start to really matter. On heavy threaded
> applications, stack usage is a somewhat limited resource.

And I'm trying to say that the point of GP is to raise coding to the
highest possible level of abstraction *without loss of efficiency*.  If
we can't achieve "relative efficiency" as described in
http://www.stepanovpapers.com/BYTE_com.htm, I don't think we're doing
the job right.  So far, unless I'm mistaken, we're still missing the
mark by a fairly wide margin.

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