On Thu, Sep 4, 2008 at 1:36 AM, David Abrahams <dave@boostpro.com> wrote:
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@boostpro.com> 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
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) ? And why you can do without it in filter_strided_iterator?
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.
Eh? I never claimed it did! Barring heavy optimizations of indirect call, an any_iterator will always be much slower than a plain iterator. Any_iterator is not about performance, but is useful as a compilation firewalls and for ease of use. You want to make the buffer as small as possible, so the smaller your iterators are, the more likely they are to fit in the buffer.
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.
Hum, I've entered the discussion with the with the explicit aim to reduce the size of iterators adapters and ranges while trying not to make them slower than they are right now. Making them faster was not the aim. (for the record, I think too that the exception approach is a bit of a dead end). I think your point is: do not bother with size expansion, because when the size will be big enough to be a problem, performance will already have reached the floor. My counterpoint is that every layer add more or less a constant overhead, while the size expansion grows quadratically, also, in situations were performance is not a problem, you might still care about the size. -- gpd