RE: [Boost-users] Re: MultiArray questions

From: Dr Mark H Phillips (mark_at_[hidden])
Date: 2004-01-28 18:46:07

On Wed, 2004-01-28 at 23:42, Ben Hutchings wrote:
> 
> 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.)

Thanks Ben!  This is very helpful!

So "if (i!=j) ..." uses a BEQ, "if (i<j) ..." uses a BCC, and I am 
guessing that "if (i==j) ..." uses a BNE.

>From what you've said below, BEQ and BCC (and probably BNE as well)
all take the same time.  But I would have thought BCC only has to
check the most significant bit (ie whether the result was negative
or not) whereas BEQ has to check that all the bits are 0, so I would
have thought BCC was faster.  But perhaps there are hardware
optimizations which make BEQ as fast as BCC.

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

Okay.  Point well made.

Thanks,

Mark.