Boost logo

Boost :

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" <> wrote:

> On Wed, Sep 3, 2008 at 7:21 PM, David Abrahams <dave_at_[hidden]> wrote:
>> on Wed Sep 03 2008, "Giovanni Piero Deretta" <> 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.

>> 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, 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

Boost list run by bdawes at, gregod at, cpdaniel at, john at