From: byer@adobe.com (Scott Byer)
Subject: Re: 64-bit CPUs (was DEC's alpha is "way fast")
Reply-To: byer@adobe.com (Scott Byer)
Organization: Adobe Systems Incorporated
Date: Tue, 17 Nov 1992 20:56:12 GMT

Volker Herminghaus-Shirai writes

> 'cuse me but how is your strcpy routine going to find the end of
> the string? Strncpy is OK, but strcpy?

Use the instruction intended for just such an emergency :-)

'CMPBGE' is what it's called on the Alpha.  And there are some nice
examples of it's use in the architecture handbook.

Assuming that the source and destination address are mis-aligned
in the same way ( source & 0x07 == destination & 0x07 ) the inner
loop to strcpy becomes:

	<preamble - gets to an aligned point,
		    preloads R3 with first aligned quadword>
Loop:
	STQ	R3,0(R2)
	LDA	R2,8(R2)
	LDQ	R3,0(R1)
	LDA	R1,8(R1)
	CMPBGE	R31,R3,R4
	BEQ	R4,Loop

	<postamble - copy the right masked portion of the last
		     quadword, based on the set bits in R4, which 
		     indicate where the comparison failed>

That's 6 instructions for 8 bytes, a win over byte-by-byte (at 16
instructions per 8 bytes).  If the source and destination are
mis-aligned differently, then it's and extra three instructions -
two shifts and an or - in the inner loop (and a couple of extra
instructions in the preamble).  And that would handle the fully
general un-aligned move case.

BUT!  In order to get memory bandwidth, memory must be interleaved
(Non-interleaved DRAM won't exactly keep up with a 150MHz clock!).
byte-by-byte copying only copies one byte for every two memory
cycles, or a minimum of 16 memory cycles for 8 bytes.  The inner
loop on the Alpha RISC architecture requires only 2 memory cycles,
and so is instruction limited at 9 cycles.  This assumes no
wait-states.

At a higher clock rate, there are likely to be latency problems,
requiring at least one wait state.  With one wait state, the 'smart'
algorithm on the RISC architecture is not penalized (the number of
cycles required for the memory accesses is stil below the cycles
required to execute the loop's instructions), but the CISC loop
suffers a serious set-back.  The 'move (a0)+,(a1)+' instruction
cannot be completed in less than three cycles (read, wait, write),
plus a minimum of one cycle for the branch (the wait state for the
write can overlap with the execution of the branch and doesn't
count), giving 32 cycles for 8 bytes moved.

There is time taken for the preamble and postamble to the inner
loop, so that for small strings the CISC architecture will come
out ahead.  I would suspect (I haven't written and counted
requirements for the entire routine) that the inner loop must be
hit at least twice for the RISC architecture to win, making strcpy's
greather than 16 bytes a win.

Note also that this is the worst of the string operations in terms
of RISC instruction count compared to that of CISC.  strlen is
probably the best, with an inner loop of just four instructions,
and virtually no preamble or postamble.

As a final note - the smart algorithm must be used on the Alpha,
as there are no byte- or word- load instructions.  The 'dumb' C
algorithm of 'while (*to++ = *from++);' that translates into the
one move instruction on the 68k gets translated into a really ugly
mess on the Alpha, with shifts and masks.  The default verion of
Unix 'compress', for example, makes the Flamingo perform like a
Sparc 2.

--
Scott Byer                             NeXTMail: byer@mv.us.adobe.com
Adobe Systems Incorporated               These are *my* opinions, and  
1585 Charleston Road, P.O. Box 7900        do not necessarily reflect
Mountain View, CA 94039-7900             the opinions of my employer.
---------------------------------------------------------------------
Newsgroups: comp.sys.next.advocacy