Subject: memfastset.S

From: Matthew Wilcox <[email-masked]>
Date: Fri, 17 Apr 1998 07:53:16 +0100 (BST)

I've optimised Russell's code a bit.  I've changed rather a lot in fact,
but I've stuck to his structure rather than try to work out whether a
64-byte inner loop would be better, or whether it would make sense to
sacrifice more registers to make the inner loop smaller.  Here's the first
version, which I have tested in BBC BASIC's assembler and then rewritten in
GAS style, so typos may exist though I checked it three times.
It is definitely faster for large blocks of data since I removed an
instruction from the inner loop.  I suspect it to be faster for small
blocks of data as well, but have not tested this hypothesis.

/*
 * linux/arch/arm/lib/memfastset.S
 *
 * Copyright (C) 1995, 1996 Russell King
 * Copyright 1998 Matthew Wilcox
 */

#include <asm/assembler.h>
		.text
@ Prototype: void memsetl (unsigned long *d, unsigned long c, size_t n);

		.global	_memsetl
@ If this is quad-word aligned then Lloop_32 is in one cache line
_memsetl:
		stmfd	sp!, {lr}
		mov	lr, r1
		subs	r2, r2, #16
		blt	Lmod_4

		mov	r3, r1
		mov	ip, r1
		subs	r2, r2, #16
		bmi	Lmod_16
Lloop_32:
		stmia	r0!, {r1, r3, ip, lr}
		stmia	r0!, {r1, r3, ip, lr}
		subs	r2, r2, #32
		bge	Lloop_32

@		cmn	r2, #32
@		LOADREGS(eqfd, sp!, {pc})
@ at this point, we are up to 28 bytes away from the end of the buffer,
@ r2 is n-32 bytes, ie {-4, -8, ..., -28}; *OR* we've finished and r2
@ contains -32
Lmod_16:
		cmn	r2, #16
		stmgeia	r0!, {r1, r3, ip, lr}
		LOADREGS(eqfd, sp!, {pc})
		addlt	r2, r2, #16

@ now we are up to 12 bytes from end of buffer; r2 can be {-4, -8, -12, -16}
Lmod_4:
		adds	r2, r2, #8
		stmgeia	r0!, {r1, lr}
@ -8 & -16 are already done.  If it's non-zero, then it wasn't -8, if
@ it's -16, it won't be taken above 0.
		addnes	r2, r2, #6
		strgt	r1, [r0]

		LOADREGS(fd, sp, {pc})

And here's a completely untested optimisation which I came up with on the
tram on the way into work.  It should improve performance for 16-byte
aligned code.

/*
 * linux/arch/arm/lib/memfastset.S
 *
 * Copyright (C) 1995, 1996 Russell King
 * Copyright 1998 Matthew Wilcox
 */

#include <asm/assembler.h>
		.text
@ Prototype: void memsetl (unsigned long *d, unsigned long c, size_t n);

		.global	_memsetl
@ If this is quad-word aligned then Lloop_32 is in one cache line
_memsetl:
		stmfd	sp!, {lr}
		mov	lr, r1
		subs	r2, r2, #16
		blt	Lmod_4

		mov	r3, r1
		mov	ip, r1
		subs	r2, r2, #16
		bmi	Lmod_16
Lloop_32:
		stmia	r0!, {r1, r3, ip, lr}
		stmia	r0!, {r1, r3, ip, lr}
		subs	r2, r2, #32
		bge	Lloop_32

@		cmn	r2, #32
@		LOADREGS(eqfd, sp!, {pc})
@ at this point, we are up to 28 bytes away from the end of the buffer,
@ r2 is n-32 bytes, ie {-4, -8, ..., -28}; *OR* we've finished and r2
@ contains -32
Lmod_16:
		cmn	r2, #16
		stmgeia	r0!, {r1, r3, ip, lr}
		addlt	r2, r2, #16

@ now we are up to 12 bytes from end of buffer; r2 can be {-4, -8, -12, -16}
Lmod_4:
		cmn	r2, #16

		LOADREGS(eqfd, sp!, {pc})
		adds	r2, r2, #8
		stmgeia	r0!, {r1, lr}
		strne	r1, [r0]

		LOADREGS(fd, sp, {pc})

-- 
Set Alias$Case Set Alias$[ |||| |MSet Alias$Otherwise Set Alias$[ \ Matthew
"" |MSet Alias$When If %0=%%0 Then Set Alias$[ "" ||MIf %0=%%0    \ Wilcox
Then Set Alias$Otherwise Set Alias$[ |||||||||||||||| ||MIf       \
%0=%%0 Then Set Alias$When Set Alias$[ ||||||||||||||||
unsubscribe: body of `unsubscribe linux-arm' to [email-masked]

---

From: Russell King - ARM Linux Admin <[email-masked]>
Date: Fri, 17 Apr 1998 09:52:05 +0100 (BST)

> blocks of data as well, but have not tested this hypothesis.

I presume that you did check out where it was used ;)

You have to be careful how many registers you use in LDMs/STMs on the A5000.
I have found that generally using more than 4 causes floppy FIQ underruns
(since a LDM/STM effectively locks out FIQs for (worst case) (n+1)S+1N
cycles, plus on top of that you've got the VIDC DMA, sound DMA and DRAM
refresh.  This is enough to push the FIQ response time over the limit.
To prove this, I went to the trouble of using a logic analyser on my A5000!
Hence, I think that sticking to 4 registers is a must.

It'll give us a bit more speed on the console though ;)

The critical one is in string.S - memset, which is used for general purpose
memory setting, and memzero for pages and other things needing a quick
zero'ing of an aligned piece of memory with 32-byte granularity.
   _____
  |_____| ------------------------------------------------- ---+---+-
  |   |        Russell King       [email-masked]      --- ---
  | | | |  http://www.arm.uk.linux.org/~rmk/armlinux.html    /  /  |
  | +-+-+                                                     --- -+-
  /   |               THE developer of ARM Linux              |+| /|\
 /  | | |                                                     ---  |
    +-+-+ -------------------------------------------------  /\\\  |

---

From: Russell King - ARM Linux Admin <[email-masked]>
Date: Fri, 17 Apr 1998 11:29:25 +0100 (BST)

> 		LOADREGS(eqfd, sp!, {pc})

Yet another thought:

Lmod_4:         tst     r2, #8
                stmneia r0!, {r1, lr}
                tst     r2, #4
                strne   r1, [r0]
                LOADREGS(fd, sp!, {pc})

That's one more instruction removed ;)
   _____

---

From: Russell King - ARM Linux Admin <[email-masked]>
Date: Fri, 17 Apr 1998 10:54:25 +0100 (BST)

> @ it's -16, it won't be taken above 0.
				^^^ is this correct?
> 		LOADREGS(fd, sp, {pc})
			was  ^^^ sp!, {pc}) is what you meant here?

Surely you can make this optimisation as well:

> @ now we are up to 12 bytes from end of buffer; r2 can be {-4, -8, -12}
> Lmod_4:
> 		adds	r2, r2, #8
> 		stmgeia	r0!, {r1, lr}
> 		strne	r1, [r0]
> 
> 		LOADREGS(fd, sp!, {pc}}
			was  ^^^ sp!, {pc}) is what you meant here?
   _____

---

From: Matthew Wilcox <[email-masked]>
Date: Fri, 17 Apr 1998 13:19:38 +0100 (BST)

Russell King - ARM Linux Admin
> > @ it's -16, it won't be taken above 0.

It is, yes.  It makes both -4 and -12 positive, while leaving -16 below
zero and -8 on zero.  So greater than stores 4 bytes more.  Bingo.
Remember, that's the tested one ;-)  For maximum confuse-a-catness, you
could make it 5 or 7 instead.

> 			was  ^^^ sp!, {pc}) is what you meant here?

Almost certainly.  As i explained, I converted it from a BBC Basic
assembler format, so there are typos.  I should've supplied the BBC
Basic version as well, I guess.  Sorry.

> Surely you can make this optimisation as well:

Depends if you ever call it with zero as a parameter.  Your previous
code coped with that, so I didn't want to rock the boat.

> 			was  ^^^ sp!, {pc}) is what you meant here?

yep.  Sorry.

---

From: Matthew Wilcox <[email-masked]>
Date: Fri, 17 Apr 1998 13:33:49 +0100 (BST)

> That's one more instruction removed ;)

Yes, though it's slower for the case where it's quad-word aligned.  Mmm,
forgot to optimise for the ARM2's 1N+3S properties.  Anyone think this is
important?  ;-)