🔒 Locked

Fastest way to turn 0x000000AB into 0xABABABAB

Started by HaywireGuy Apr 30, 2005 at 4:36 AM 53 replies 12.3k views

Original Post

Apr 30, 2005 at 4:36 AM

Good day gurus, I have to admit I am an optimization freak who will do just about anything to make my codes run fast. Okay I am still struggling with ASM because of my limited knowledge on it, and VC compiler beats me at the fastest ASM routine I ever written, sad but true... So now one simple challenge here, I need to read a source (BYTE) buffer, write its content into another (DWORD) buffer in this manner: // Okay, the code might not compile, but you get the idea. // I'm converting from lpSrc to lpDst buffer. // LPBYTE lpSrc = 0xAB 0xCD 0xEF; LPDWORD lpDst = 0xABABABAB 0xCDCDCDCD 0xEFEFEFEF; If you were me, how would you have done it? I'll try to come up with one solution and post in my next post. Thanks in advanced!

HaywireGuy

Apr 30, 2005 at 4:51 AM

OK, this is my attempt (there might be some other instructions that do the
exact same thing, please tell me if I have done it the wrong way):

// Source/destination buffers...
mov esi, dword ptr [lpSrc]
mov edi, dword ptr [lpDst]

// Some loop goes here...

// Actual operation...
xor eax, eax // Clear register.
xor ebx, ebx // Clear register.
mov al, [esi] // Read source byte.
mov ebx, eax // ebx = 0x000000AB
shl eax, 8 // eax = 0x0000AB00
or ebx, eax // ebx = 0x0000ABAB
mov eax, ebx // eax = 0x0000ABAB
shl ebx, 16 // ebx = 0xABAB0000
or eax, ebx // eax = 0xABABABAB
mov [esi], eax // Store DWORD.

Okay, that's about the best I can give, what do you think? Any faster ways to
beat mine? 10 instructions to turn 0x000000AB into 0xABABABAB, I don't think
that is fast at all...

xor

Apr 30, 2005 at 5:00 AM

lpDst=0x1010101*lpSrc;

HaywireGuy

Apr 30, 2005 at 5:09 AM

Damn, I'm convinced my brain is not developed now! Okay that's very straight
forward, for that, I'll rate you up, thanks XOR!

xor ebx, ebx
mov eax, 0x01010101
mov bl, [esi]
mul ebx
mov [edi], eax

Okay, five instructions left, good stuff! Any faster ones? (I'm not sure how
would VC compiler translate the code XOR suggested, I'll take a look at it
later when I get to my own computer). Thanks a bunch!

xor

Apr 30, 2005 at 5:25 AM

I'm a bit an optimization freak myself.

HaywireGuy

Apr 30, 2005 at 5:45 AM

This can be slow, considering the fact that it is in a loop. Move the
0x01010101 out of the loop and it might speed things up a little. So the
modified code looks something like this:

mov ebx, 0x01010101

loop:

xor eax, eax
mov al, [esi]
mul ebx
mov [edi], eax

Yeh, removed one more instruction, four left!

Apr 30, 2005 at 6:09 AM

Maybe I'm way off here but I think there's a stall when changing register sizes: I.e

   mov ebx, 0x01010101  loop:    xor eax, eax    mov al, [esi]  ; <= Stall, switching from 32 to 8 bit register size    mul ebx    mov [edi], eax ; <= Stall, switching from 8 to 32 bit register size

I think this stall could be as much as 6 cycles (don't know if this apply to your processor).

   mov ecx, 0x01010101loop:    movzx eax, BYTE PTR[esi] ; No stall?    mul ecx    mov [edi], eax

I don't know if this is faster in practice or not. It's one instruction shorter, though.

Also consider doing alot of "pixels" in paralell.

Jan Wassenberg

Apr 30, 2005 at 7:10 AM

If you can assume SSE support, you could try pshufw+packuswb. That'd give you more registers and the opportunity to do other stuff in the meantime.

WRT partial register stall: P6+ have special hardware that avoids penalty if a partial reg merge is preceded by XOR. However, movzx is still better unless you care about speed on older CPUs.

Apr 30, 2005 at 7:23 AM

Thanks for the stall info!
I'm afraid most of my CPU knowledge (besides the instruction set) ended somewhere after Pentium Pro.

Jan Wassenberg

Apr 30, 2005 at 9:05 AM

hehe, yeah, knowledge of CPU internals grows obsolete fast. But the payoff is considerable :)

Apr 30, 2005 at 9:34 AM

Here's an actual completed loop:

	mov	ecx, 0x01010101loop:	lodsb	and	eax, 0x000000FF	jz	done	mul	ecx	stosd	jmp	loopdone:

I decided to just use the lodsx/stosx instructions because I didn't feel like manually incrementing the registers. This will convert the entire string assuming you have enough memory at the destination address.

Jan Wassenberg

Apr 30, 2005 at 10:52 AM

LODS and STOS are much slower than MOV+INC. The 32-bit AND after LODSB causes partial reg stall.

HaywireGuy

Apr 30, 2005 at 1:10 PM

Wow it's been just few hours' time. Let me first thank everyone for the input,
appreciate it.

Now eq, if I can remember it correctly, whenever there is a memory access the
instruction will stall for 3 clock cycles. So your reasoning seems logical.
Though I'm not sure if the stall is due to the switching of register sizes.

Jan, the SSE approach might be more appealing but I'm not going to assume
that. Simply because I do not have the knowledge of SSE. You said that "movzx
is better unless I care about older processors", what was the processor movzx
instruction first appear in? Is Pentium 2 a reasonable requirement? Another
thing is Jan, why would LODS and STOS be slower than MOV+INC? They seemed
simpler and the increment of source/destination buffer is done internally in
the processor...

Ra, the LODSB and STOSD do look appealing too, the only concern I have in the
code is that conditional branch (JZ) is strongly discouraged by Intel's
optimization guidelines. I might have missed something there, please advice me
if that's the case.

Thanks again for those great tips, you guys rock!

Apr 30, 2005 at 1:19 PM

Quote:
Original post by Jan Wassenberg
LODS and STOS are much slower than MOV+INC. The 32-bit AND after LODSB causes partial reg stall.

True, but they're not so bad on a 386 and they force the pairing of AND/JZ on processors that support it. [wink]

I don't know anything about Intel discouraging conditional jumps inside loops. I'm assuming the branch prediction will figure it out after a few iterations. If you multiply without changing any flags then you can negate the conditional and move it to the bottom of the loop.

If you want to be pedantic:

	; [constant] is expected to hold 0x01010101	; this version writes 0x00000000 to the destination for the terminator	xor	ebx, ebx	nop				; pairing :|l:	xor	eax, eax	mov	al, [esi + ebx]		; this will NOT stall on processors that recognize XOR/MOV 8-bit, but if it does					; it'll still be faster than MOVZX on older processors	mov	ecx, eax	mul	[constant]	mov	[edi + ebx * 4], eax	inc	ecx	inc	ebx	loop	l

EDIT: Right, JCXNZ doesn't exist. I don't know what I was thinking.

[Edited by - Ra on April 30, 2005 1:19:47 PM]

Jan Wassenberg

Apr 30, 2005 at 1:33 PM

Quote:
You said that "movzx
is better unless I care about older processors", what was the processor movzx
instruction first appear in?

386. The issue is more rather that MOVZX was slow in everything before P6, so it was avoided there.

Quote:
Is Pentium 2 a reasonable requirement?

hm, you might lose a bit more machines than you'd like - many people are still running old P2 400-class rigs. Personally I'd require P5-MMX and write off the rest.

Quote:
Another thing is Jan, why would LODS and STOS be slower than MOV+INC? They seemed simpler and the increment of source/destination buffer is done internally in the processor...

In current microarchitecture, complex instructions are penalized. They don't fit into the RISC mold and are actually emulated inside the processor (via microcode); hence, decode is complicated and latency is typically 5+ cycles.

Quote:
the only concern I have in the
code is that conditional branch (JZ) is strongly discouraged by Intel's
optimization guidelines.

Right. The issue is branch prediction; if the CPU gets it wrong (50% of the time if condition is random), the penalty is considerable. However, not every program is straight-line ;) In this case, it's unavoidable, but fortunately consistently taken/not taken branches (in a loop) are correctly predicted after the first go.

Quote:
If you multiply without changing any flags then you can negate the conditional and move it to the bottom of the loop.

Yeah, that's usually an improvement. 2 problems with the current code: JECXZ isn't available in negated form, and you need to increment edi (preferably via LEA, so as not to trash the flags).

Jan Wassenberg

Apr 30, 2005 at 1:54 PM

Whee, real-time posting :)

Quote:
It's very avoidable; look at the edited code.

I meant that loops with an unknown number of iterations will require a conditional jump (obviously). As far as branch prediction is concerned, it doesn't matter whether there's JZ+JMP or JNZ.

Oh BTW, pairing is only an issue with programs being optimized for P5 ;)

// update after changed code:
The INC+LOOP idea is clever, but you've really got to avoid the slow CISC instructions . All other things equal, setting flags by testing eax followed by JNZ will be fastest.

Apr 30, 2005 at 1:59 PM

Quote:
Original post by Jan Wassenberg
Yeah, that's usually an improvement. 2 problems with the current code: JECXZ isn't available in negated form, and you need to increment edi (preferably via LEA, so as not to trash the flags).

ESI and EDI don't need to be incremented in this code; the memory address that's read is incremented through EBX. I might have missed an increment while I was editing it before, but the current assembly doesn't need it.

Thanks to Google I also assumed JCXNZ existed, which it doesn't. That's been changed to an INC ECX/LOOP set.

Quote:
Original post by Jan Wassenberg
Oh BTW, pairing is only an issue with programs being optimized for P5 ;)

I'm caught in a dream world where Intel doesn't change their optimization schemes so much that you need entirely different assembly for each processor. I end up optimizing for the 386 by avoiding a MOVZX and the Pentium by poking at pairing. [depressed]

Jan Wassenberg

Apr 30, 2005 at 2:15 PM

Quote:
I'm caught in a dream world where Intel doesn't change their optimization schemes so much that you need entirely different assembly for each processor

hehe, no free lunch for us ;)

Fruny

Apr 30, 2005 at 2:19 PM

Quote:
I'm caught in a dream world where Intel doesn't change their optimization schemes so much that you need entirely different assembly for each processor.

That's why us peons use compilers. [smile]

Raduprv

Apr 30, 2005 at 5:12 PM

Obviously, the fastest way to convert 0x000000AB into 0xABABABAB is:
mov eax,ABABABABh; :D

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.