Re: [boost] AlRangeExandrescu?

Subject: Re: [boost] AlRangeExandrescu?
From: Giovanni Piero Deretta (gpderetta_at_[hidden])
Date: 2009-07-27 17:39:26

On Mon, Jul 27, 2009 at 7:42 PM, Andrei
Alexandrescu<andrei_at_[hidden]> wrote:
> David Abrahams wrote:
>>
>> on Mon Jul 27 2009, Andrei Alexandrescu <andrei-AT-metalanguage.com>
>> wrote:
>>
>>> David Abrahams wrote:
>>>>
>>>> on Fri Jul 24 2009, Andrei Alexandrescu <andrei-AT-metalanguage.com>
>>>> wrote:
>>>>
>>>>>> Is popFront() mutable just for efficiency? Or is there something else
>>>>>> I'm missing?
>>>>>
>>>>> It's only efficiency. I was very attracted to popFront returning the
>>>>> new range (100% functional interface!) but I gave up for efficiency
>>>>> reasons. I didn't want iteration with ranges to be cool and iteration
>>>>> with other means to be efficient.
>>>>
>>>> Could you describe the efficiency problem in more detail?  I think it
>>>> might be solvable.
>>>
>>> Well a simple example is that a range in a contiguous array is a fat
>>> pointer,
>>> e.g. (begin,end). To bump a range in-place you need to change one
>>> pointer; returning a
>>> new range would have you copy two pointers. It turns out that the
>>> difference is
>>> sensible for some loops.
>>
>> If compilers can't optimize that overhead away, I'm disappointed in them
>> ;-(
>>
>> Did you check?
>
> I did, but not the trick with the proxy.
>

FWIW, I did a test today: with plain pointers, vector iterators and
lists there is no overhead in the non mutating next; in fact the
compiler (a recent GCC, at O3 optimization level) generate exactly the
same object code for a for  loop using  the non mutating next and the
inplace next. In fact it generates the exact same code of an hand
written loop using plain pointers.

Other containers are another story though, while I'm not surprised by
the inefficiency of map and set iterators (it generates calls to non
inlined functions), deque is a sore thumb: every copy constructor and
assignment in the source code is explicitly translated to a copy in
the generated assembler. Maybe it is because deque iterators are
fairly large and GCC gives up optimizing away moves to and from
memory.

Tomorrow I will do some tests with boost iterator adapters.

-- 
gpd