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> > 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.
>> 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
> 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 .
>> 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk