Re: Advice on iterator vs. index efficiency

[Tim Prince <tprince at computer dot org>]

Neal Becker wrote:
> me22 wrote:
> 
>> On 05/10/2007, Neal Becker <ndbecker2@gmail.com> wrote:
>>> Based on advice from some time back, I write algorithms to use iterators
>>> rather than index-based loops.  Often, this requires jumping through
>>> considerable hoops.
>>>
>>> I'm just wondering, with current gcc loop optimizations, it this advice
>>> still relevant?
>>>
>>> Is there (in general) a difference in speed for these 2 styles?  What
>>> about if the containers are multi-dimensional and loops are nested?
>> I remember seeing that for the simple begin-to-end loop over a vector,
>> gcc actually ends up compiling the iterator and index versions to the
>> exact same code.
>>
>> In general, I'd say that if there would be a difference, the iterator
>> one might be faster as moving to the "next" might be simpler than
>> descending some data structure to an index.
>>
>> Of course, I have no idea how pointers versus indices affects alias
>> analysis, or how much importance you'd place in the generality of
>> iterators.
>>
>> ~ Scott
>>
> 
> I was wondering if gcc would see that the index version is just incrementing
> through, and avoid the nested index calculations.  This seems to be
> supported by your statement that they generate the same code.
> 

It can't be identical code, as the termination test is != in one case,
and < in the other.  A conversion could be made by calculating the
number of iterations, Fortran style, but people more familiar than I
with the intent of STL maintain that this is incorrect.  In the 32-bit
pointer case, they maintain that, since there is no checking for the
case where the starting pointer is beyond the end, it must wrap around
in memory.  I haven't seen a 64-bit compiler attempt to implement this,
as it would not work; a typical "64-bit" machine supports only 48 bits
of address.
So it seems unlikely that combining inner and outer STL loops into one
would be valid.