Dr Mark H Phillips
On Sun, 2004-01-25 at 04:47, garcia wrote: <snip>
Why can't you change the != into
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.
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.
participants (2)
-
Ben Hutchings -
Dr Mark H Phillips