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