Use x86 SSE instructions for clear_page, copy_page

The attached patch (against kernel 2.6.8.1) enables using SSE instructions for copy_page and clear_page.

A user-space test on my Pentium III 850 MHz shows a 3x speedup for clear_page (compared to the default "rep stosl"), and a 50% speedup for copy_page (compared to the default "rep movsl"). For a Pentium-4, the speedup is about 50% in both the clear_page and copy_page cases.

The attached (admittedly perverse) user-space program "malloc-fork-load.c" takes 30 sec with stock kernel 2.6.8.1, which improves to about 15 sec when running a kernel with the attached kernel patch applied.

Notes: I cannot replace clear_page and copy_page with their SSE equivalents at compile-time, because clear_page is used before the CPU is fully set up (in particular the CR4.OSFXSR bit, without which SSE instructions kill the kernel with an invalid operand exception). The current function-pointer based approach could be extended to include the current MMX-based improvements for AMD CPUs as well. If a function pointer is considered too wasteful for a boot-time initialization issue, a "memcpy" approach similar to the "apply_alternatives()" code modifications would be possible.

Please test.

Jens Maurer

diff -urN -X /home/jmaurer/Linux/excludes-for-diff.txt linux-2.6.8.1.orig/arch/i386/Kconfig linux-2.6.8.1/arch/i386/Kconfig
@@ -419,6 +419,11 @@
 	depends on MCYRIXIII || MK7
 	default y
 
+config X86_USE_SSE
+	bool
+	depends on MPENTIUMIII || MPENTIUMM || MPENTIUM4
+	default y
+
 config X86_OOSTORE
 	bool
 	depends on (MWINCHIP3D || MWINCHIP2 || MWINCHIPC6) && MTRR

diff -urN -X /home/jmaurer/Linux/excludes-for-diff.txt linux-2.6.8.1.orig/arch/i386/kernel/setup.c linux-2.6.8.1/arch/i386/kernel/setup.c
@@ -1241,13 +1241,46 @@
 }
 
 static int no_replacement __initdata = 0;
-
+
+#ifdef CONFIG_X86_USE_SSE
+
+static void std_clear_page(void *page)
+{
+	int d0, d1;
+	asm volatile("cld\n\t"
+		     "rep; stosl"
+		     : "=&c" (d0), "=&D" (d1)
+		     : "a" (0), "0" (PAGE_SIZE/4), "1" (page)
+		     : "memory");
+}
+
+static void std_copy_page(void *to, void *from)
+{
+	int d0, d1, d2;
+	asm volatile("cld\n\t"
+		     "rep; movsl"
+		     : "=&c" (d0), "=&D" (d1), "=&S" (d2)
+		     : "0" (PAGE_SIZE/4), "1" (to), "2" (from)
+		     : "memory");
+}
+
+void (*__sse_clear_page)(void *) = &std_clear_page;
+void (*__sse_copy_page)(void *, void *) = &std_copy_page;
+EXPORT_SYMBOL(__sse_clear_page);
+EXPORT_SYMBOL(__sse_copy_page);
+#endif
+
 void __init alternative_instructions(void)
 {
 	extern struct alt_instr __alt_instructions[], __alt_instructions_end[];
+	extern void activate_sse_replacements(void);
 	if (no_replacement)
 		return;
 	apply_alternatives(__alt_instructions, __alt_instructions_end);
+
+#ifdef CONFIG_X86_USE_SSE
+	activate_sse_replacements();
+#endif
 }
 
 static int __init noreplacement_setup(char *s)

diff -urN -X /home/jmaurer/Linux/excludes-for-diff.txt linux-2.6.8.1.orig/arch/i386/lib/Makefile linux-2.6.8.1/arch/i386/lib/Makefile
@@ -7,4 +7,5 @@
 	bitops.o
 
 lib-$(CONFIG_X86_USE_3DNOW) += mmx.o
+lib-$(CONFIG_X86_USE_SSE) += sse.o
 lib-$(CONFIG_HAVE_DEC_LOCK) += dec_and_lock.o

diff -urN -X /home/jmaurer/Linux/excludes-for-diff.txt linux-2.6.8.1.orig/include/asm-i386/page.h linux-2.6.8.1/include/asm-i386/page.h
@@ -21,6 +21,15 @@
 #define clear_page(page)	mmx_clear_page((void *)(page))
 #define copy_page(to,from)	mmx_copy_page(to,from)
 
+#elif defined(CONFIG_X86_USE_SSE)
+
+#include <asm/sse.h>
+
+extern void (*__sse_clear_page)(void *);
+extern void (*__sse_copy_page)(void *, void*);
+#define clear_page(page)	(*__sse_clear_page)(page)
+#define copy_page(to,from)	(*__sse_copy_page)(to,from)
+
 #else
 
 /*

diff -urN -X /home/jmaurer/Linux/excludes-for-diff.txt linux-2.6.8.1.orig/include/asm-i386/sse.h linux-2.6.8.1/include/asm-i386/sse.h
@@ -0,0 +1,34 @@
+/*
+ * linux/include/asm-i386/sse.h
+ *
+ * Copyright 2004 Jens Maurer
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ *
+ */
+
+#ifndef _ASM_SSE_H
+#define _ASM_SSE_H
+
+/*
+ *	SSE helper operations
+ */
+
+#include <linux/types.h>
+
+extern void sse_clear_page(void *page);
+extern void sse_copy_page(void *to, void *from);
+
+#endif

#include <stdlib.h>
#include <unistd.h>
#include <sys/mman.h>

#define N 20240
#define SIZE 4096

int main()
{
int k;

  for(k = 0; k < 10; k++) {
    int i = 0;
    int pid;
    unsigned char *mem = mmap(0, N*SIZE, PROT_READ|PROT_WRITE,
  			MAP_PRIVATE|MAP_ANONYMOUS, 0, 0);
    if(mem == MAP_FAILED)
      perror("mmap");
    printf("pagesize: %d\n", getpagesize());
    for(i = 0; i < N; i++)
      mem[i*SIZE] = i*1000000007ul;
    printf("pages allocated\n");
    pid = fork();
    if(pid == 0) {
      /* child */
      for(i = 0; i < N; i++)
        mem[i*SIZE+1] = i;          /* force copy */
      printf("copy complete\n");
      exit(0);
    } else if(pid == -1) {
      perror("fork");
    } else {
      /* parent */
      waitpid(pid, NULL, 0);
    }
    munmap(mem, N*SIZE);

}
}

we used to have code like this in 2.4 but it got removed: the non temperal store code is faster in a microbenchmark but has the fundamental problem that it evics the data from the cpu cache; the actual USE of the data thus is a LOT more expensive, result is that the overall system performance goes down ;(

Did SSE clear_page() suffered from this issue too ?

Andrey Panin		| Linux and UNIX system administrator
[email protected]		| PGP key: wwwkeys.pgp.net

yes especially clear_page; the kernel only calls clear_page when it's *just about* to use it, so it's actually the worst case example ;(

(and clear_page gains the most because non-temperal stores avoid the write allocate so it like halves the memory bandwidth)

Hm... With the current clear_page, we are filling 4KB of my Pentium-III's 16 KB L1 d-cache (i.e. 25%) with zeroes. I'm not sure that we will use all of this data right away.

I would like to point out that the current arch/i386/lib/mmx.c uses MMX movntq instructions #ifdef CONFIG_MK7 . Apparently, bypassing the cache was considered a good idea in that case.

What is a set of useful benchmarks to find out which approach is better? We should have some real-world programs that show significant oprofile hits in clear_page or copy_page. It might very well be that the results on Pentium-III and Pentium-4 are different, for example that SSE is only useful for a Pentium-III, and only for clear_page.

Jens Maurer

Time kernel builds on an otherwise totally idle machine. Do multiple runs so that the cache gets loaded and you're testing the memory accesses rather than disk reads.

I've applied Denis Vlasenko's patch that allows runtime switching between "rep stosl" and SSE instructions.

I'm using this script to perform the kernel build:

rm mm/*.o kernel/*.o
make SUBDIRS="mm kernel"

Hardware: Pentium III 850 MHz with 256 MB RAM

Results of "time" using "rep stosl":

real    1m19.038s  1m18.099s  1m18.612s  1m18.630s
user    1m07.258s  1m07.056s  1m07.198s  1m07.052s
sys     0m10.062s  0m10.205s  0m10.141s  0m10.209s

oprofile result for "rep stosl" (obtained on a separate run):

samples  %        app name                 symbol name
497537   71.9851  cc1                      (no symbols)
37358     5.4051  vmlinux-2.6-sse          zero_page_std
6933      1.0031  vmlinux-2.6-sse          __copy_to_user_ll
6010      0.8695  libc-2.3.3.so            _int_malloc
5940      0.8594  vmlinux-2.6-sse          copy_page_std
5262      0.7613  vmlinux-2.6-sse          mark_offset_tsc

Results using SSE instructions (writes do not use the caches):

real    1m16.724s  1m16.281s  1m16.681s  1m16.681s  1m16.207s
user    1m07.938s  1m07.752s  1m07.905s  1m07.916s  1m07.846s
sys     0m07.517s  0m07.866s  0m07.715s  0m07.753s  0m07.684s

oprofile result for SSE (obtained on a separate run):

501243   74.5966  cc1                      (no symbols)
21533     3.2046  vmlinux-2.6-sse          zero_page_sse
8166      1.2153  vmlinux-2.6-sse          __copy_to_user_ll
5797      0.8627  libc-2.3.3.so            _int_malloc
5344      0.7953  vmlinux-2.6-sse          copy_page_sse
4757      0.7080  libc-2.3.3.so            __GI_memset
4490      0.6682  vmlinux-2.6-sse          mark_offset_tsc

Interpretation:
Real time is about 2 sec lower, user CPU is about 0.7-0.9 sec higher, system CPU is about 2.3 sec lower.
Results from test runs fluctuate by about 0.2 sec, thus the measured differences appear to be significant, and in favor of using SSE instructions for clear_page(). copy_page() was not used enough (compared to clear_page) to give a clear picture.

It looks like a future patch should allow for independent "rep stosl"/SSE configuration for clear_page() and copy_page().

Jens Maurer

besides the cache arguments Arjan raised, you are also corrupting SSE registers big way. You are saving/clearing/restoring the TS but that's not enough - what if e.g. a pagefault happened while userspace code executed SSE code? You are corrupting those registers.

check out raid6_before_sse()/raid6_after_sse() how to write proper SSE code for the kernel.

Ingo

doh - should read before i write. The code is perfectly fine.

Arjan's cache arguments remain. What i'd suggest to test is the precise speed of compiling the kernel, fully done in ramfs. (if you dont have enough RAM for this then compile a portion of the kernel.) For the testing, add a /proc/sys switch to turn the SSE functions on/off runtime, hence you can eliminate the effects of page placement. If the compilation timings are stable enough then you can try the runtime switch to see whether it has any effect. There should be a small but visible change (in one direction or the other), as compilation brings in lots of new pages and copies around stuff too.

Ingo