RE: [Boost-users] Re: MultiArray questions

From: Ben Hutchings (ben.hutchings_at_[hidden])
Date: 2004-01-28 08:12:58

Dr Mark H Phillips <mark_at_[hidden]> wrote:
> On Sun, 2004-01-25 at 04:47, garcia wrote:
<snip> 
> > >Why can't you change the != into <?  Ie, do:
> > >
> > >  for(index i = 0; i < 3; ++i)
> > >    for(index j = 0; j < 4; ++j)
> > >      for(index k = 0; k < 2; ++k)
> > >        A[i][j][k] = values++;
> > >
> > >or can you?  This would be more efficient I should think, and
> > >requiring that index types be ordered shouldn't be too onerous
> > >should it?
> > >
> > You can change the != into a < if you like.  I don't see any
> > good reason why one should be more efficient than the other.  I
> > personally use != because it more closely matches how I write
> > for loops using iterators.  
> > So in short, that's a matter of personal preference.
> 
> I would have thought < was more efficient.  Isn't "i != j"
> implemented, at machine level, more or less by "i > j || i < j".
> So one compare would be cheaper than two.  Or have I got this
> wrong?
<snip>

A test for i != j typically compiles to an instruction sequence like:
    CISC:              RISC:
    CMP j,i            LD r1,i
    BEQ test_failed    LD r2,j
                       SUB. r0,r1,r2
                       BEQ test_failed
(CMP is a subtraction which doesn't store its result but sets
condition flags.  BEQ is branch-if-equal.  RISC processors need to
have all arithmetic operands in registers, but generally they have a
lot of registers so the variables may well be in registers already,
making the LDs unnecessary.)

A test for i < j (assuming i and j are unsigned) would be like:
    CISC:              RISC:
    CMP i,j            LD r1,i
    BCC test_failed    LD r2,j
                       SUB. r0,r2,r1
                       BCC test_failed
(BCC is branch-if-carry-flag-clear.  Order of arguments varies
between assembly languages, so don't worry too much about that.)

These instruction sequences usually have identical timing properties
(the exact time taken depends on caching and branch prediction).
Theoretically, an architecture which had a combined comparison and
conditional branch could make != a little faster since it requires only
bitwise comparison whereas < requires carrying between bits (longer
signal propagation time).  However, the world is moving away from such
architectures - even x86 processors are designed to make the simple
instructions run fast, not the complex ones.

For a generic algorithm that uses iterators, comparing with < requires
that the iterators be random-access.  If this isn't essential to the
algorithm, it would be better to use !=.  So it's a good habit to use
i != j as the loop condition if i can definitely never be greater than
j.