Optimise memset on i386

I've been working on a project involving fast boot speeds, which are timed from post-BIOS (this is an axiom of the project and not something I get to change). As such I've been working on optimising GRUB, and have been digging into it with this general debugging pattern (probably not optimal, I'm just showing it as an example of my approach in case anyone else is trying to do similar things):

#include <grub/time.h>
#include <grub/env.h>

void
grub_function (void)
{
char *value, *valueend;

  value = grub_malloc (16384);
  *value = '\0';
  valueend = value;

  grub_snprintf (valueend, 100, "%lld", grub_get_time_ms ());
  valueend = grub_strchr (valueend, '\0');

/* do slow stuff */

  grub_snprintf (valueend, 100, "%lld", grub_get_time_ms ());
  valueend = grub_strchr (valueend, '\0');

/* do more slow stuff */

  grub_snprintf (valueend, 100, "%lld", grub_get_time_ms ());
  valueend = grub_strchr (valueend, '\0');

grub_env_set ("identifying_name", value);
grub_free (value);
}

This seems lightweight enough that it doesn't interfere much with timings, and the approach of stuffing things into an environment variable is useful because you can get millisecond-precision timings even for video initialisation.

With this approach, one of the most noticeable time sinks is that setting a graphical video mode (I'm using the VBE backend) takes ages:
1.6 seconds, which is a substantial percentage of this project's total boot time. It turns out that most of this is spent initialising
double-buffering: doublebuf_pageflipping_init calls grub_video_fb_create_render_target_from_pointer twice, and each call takes a little over 600 milliseconds. Now, grub_video_fb_create_render_target_from_pointer is basically just a big grub_memset to clear framebuffer memory, so this equates to under two frames per second. What's going on?

It turns out that write caching is disabled on video memory when GRUB is running, so we take a cache stall on every single write, and it's apparently hard to enable caching without implementing MTRRs. People who know more about this than I do tell me that this can get unpleasantly CPU-specific at times, although I still hold out some hope that it's possible in GRUB.

However, there's a way to substantially speed things up without that. The naïve implementation of grub_memset writes a byte at a time, and for that matter on i386 it compiles to a poorly-optimised loop rather than using REP STOS or similar. grub_memset is an inner loop practically by definition, and it's worth optimising. We can fix both of these weaknesses by importing the optimised memset from GNU libc: since it writes four bytes at a time except (sometimes) at the start and end, it should take about a quarter the number of cache stalls. And, indeed, measurement bears this out: instead of taking over 600 milliseconds per call to grub_video_fb_create_render_target_from_pointer (I think it was actually 630 or so, though I neglected to write that down), GRUB now takes about 160 milliseconds per call. Much better!

The optimised memset is LGPLv2.1 or later, and I've preserved that notice, but as far as I know this should be fine for use in GRUB; it can be upgraded to LGPLv3, and that's just GPLv3 with some additional permissions. It's already assigned to the FSF due to being in glibc.

2010-06-23 Colin Watson <[email protected]>

* conf/any-emu.rmk (kernel_img_SOURCES): Add kern/string.c.
* conf/common.rmk (grub_mkdevicemap_SOURCES): Likewise. (grub_probe_SOURCES): Likewise. (grub_fstest_SOURCES): Likewise. (grub_script_check_SOURCES): Likewise. (grub_editenv_SOURCES): Likewise.
* conf/mips-qemu-mips.rmk (kernel_img_SOURCES): Likewise.
* conf/mips-yeeloong.rmk (kernel_img_SOURCES): Likewise.
* conf/powerpc-ieee1275.rmk (kernel_img_SOURCES): Likewise.
* conf/sparc64-ieee1275.rmk (kernel_img_SOURCES): Likewise. (grub_setup_SOURCES): Likewise.
* conf/tests.rmk (example_unit_test_SOURCES): Likewise.

* conf/i386-coreboot.rmk (kernel_img_SOURCES): Add kern/i386/string.c.
* conf/i386-ieee1275.rmk (kernel_img_SOURCES): Likewise.
* conf/i386-multiboot.rmk (kernel_img_SOURCES): Likewise.
* conf/i386-pc.rmk (kernel_img_SOURCES): Likewise. (grub_setup_SOURCES): Likewise.
* conf/i386-qemu.rmk (kernel_img_SOURCES): Likewise.
* conf/x86-efi.rmk (kernel_img_SOURCES): Likewise.

* kern/i386/string.c: New file.
* kern/misc.c (grub_memset): Move to ...
* kern/string.c (grub_memset): ... here.
* kern/misc.c (memset): Move to ...
* kern/string.c (memset): ... here.

=== modified file 'conf/any-emu.rmk'

@@ -6,7 +6,7 @@ kernel_img_SOURCES = kern/device.c kern/
 	kern/err.c kern/list.c kern/command.c		\
 	kern/corecmd.c kern/file.c kern/fs.c kern/main.c kern/misc.c	\
 	kern/parser.c kern/partition.c kern/term.c			\
-	kern/rescue_reader.c kern/rescue_parser.c			\
+	kern/rescue_reader.c kern/rescue_parser.c kern/string.c		\
 									\
 	kern/emu/main.c kern/emu/mm.c kern/emu/misc.c			\
 	kern/emu/getroot.c kern/emu/time.c kern/emu/hostdisk.c		\

=== modified file 'conf/common.rmk'

@@ -7,7 +7,8 @@ sbin_UTILITIES += grub-mkdevicemap
 grub_mkdevicemap_SOURCES = gnulib/progname.c util/grub-mkdevicemap.c \
 	util/deviceiter.c \
 	util/misc.c kern/emu/misc.c \
-	kern/env.c kern/err.c kern/list.c kern/misc.c kern/emu/mm.c
+	kern/env.c kern/err.c kern/list.c kern/misc.c kern/string.c \
+	kern/emu/mm.c
 
 ifeq ($(target_cpu)-$(platform), sparc64-ieee1275)
 grub_mkdevicemap_SOURCES += util/ieee1275/ofpath.c util/ieee1275/devicemap.c

@@ -27,7 +28,7 @@ util/grub-probe.c_DEPENDENCIES = grub_pr
 grub_probe_SOURCES = gnulib/progname.c util/grub-probe.c	\
 	kern/emu/hostdisk.c util/misc.c kern/emu/misc.c kern/emu/getroot.c kern/emu/mm.c	\
 	kern/device.c kern/disk.c kern/err.c kern/misc.c	\
-	kern/partition.c kern/file.c kern/list.c	\
+	kern/partition.c kern/file.c kern/list.c kern/string.c	\
 	\
 	fs/affs.c fs/cpio.c fs/fat.c fs/ext2.c fs/hfs.c		\
 	fs/hfsplus.c fs/iso9660.c fs/udf.c fs/jfs.c fs/minix.c	\

@@ -49,6 +50,7 @@ util/grub-fstest.c_DEPENDENCIES = grub_f
 grub_fstest_SOURCES = gnulib/progname.c util/grub-fstest.c kern/emu/hostfs.c \
 	util/misc.c kern/emu/misc.c kern/emu/mm.c 	\
 	kern/file.c kern/device.c kern/disk.c kern/err.c kern/misc.c	\
+	kern/string.c							\
 	disk/host.c disk/loopback.c kern/list.c kern/command.c		\
 	lib/arg.c commands/extcmd.c normal/datetime.c normal/misc.c	\
 	lib/hexdump.c lib/crc.c commands/blocklist.c commands/ls.c 	\

@@ -92,7 +94,7 @@ grub_script_check_SOURCES = gnulib/progn
 	util/grub-script-check.c util/misc.c kern/emu/misc.c kern/emu/mm.c \
 	script/main.c script/script.c script/function.c script/lexer.c \
 	kern/err.c kern/list.c \
-	kern/misc.c kern/env.c grub_script.tab.c \
+	kern/misc.c kern/env.c kern/string.c grub_script.tab.c \
 	grub_script.yy.c
 grub_script_check_CFLAGS = $(GNULIB_UTIL_CFLAGS)
 grub_script_check_DEPENDENCIES = grub_script.tab.h

@@ -160,7 +162,7 @@ DISTCLEANFILES += grub_fstest_init.c
 
 # for grub-editenv
 bin_UTILITIES += grub-editenv
-grub_editenv_SOURCES = gnulib/progname.c util/grub-editenv.c lib/envblk.c util/misc.c kern/emu/misc.c kern/emu/mm.c kern/misc.c kern/err.c
+grub_editenv_SOURCES = gnulib/progname.c util/grub-editenv.c lib/envblk.c util/misc.c kern/emu/misc.c kern/emu/mm.c kern/misc.c kern/err.c kern/string.c
 CLEANFILES += grub-editenv
 
 # Needed for genmk.rb to work

=== modified file 'conf/i386-coreboot.rmk'

@@ -16,7 +16,7 @@ kernel_img_SOURCES = kern/i386/coreboot/
 	kern/rescue_parser.c kern/rescue_reader.c \
 	kern/time.c kern/list.c  kern/command.c kern/corecmd.c \
 	kern/$(target_cpu)/dl.c kern/parser.c kern/partition.c \
-	kern/i386/tsc.c kern/i386/pit.c \
+	kern/i386/tsc.c kern/i386/pit.c kern/i386/string.c \
 	kern/generic/rtc_get_time_ms.c \
 	kern/generic/millisleep.c \
 	kern/env.c \

=== modified file 'conf/i386-ieee1275.rmk'

@@ -19,6 +19,7 @@ kernel_img_SOURCES = kern/i386/ieee1275/
 	kern/$(target_cpu)/dl.c kern/parser.c kern/partition.c \
 	kern/env.c \
 	kern/time.c kern/list.c  kern/command.c kern/corecmd.c \
+	kern/i386/string.c \
 	kern/generic/millisleep.c \
 	kern/ieee1275/ieee1275.c \
 	term/ieee1275/ofconsole.c \

=== modified file 'conf/i386-multiboot.rmk'

@@ -18,7 +18,7 @@ kernel_img_SOURCES = kern/i386/coreboot/
 	kern/rescue_parser.c kern/rescue_reader.c \
 	kern/time.c kern/list.c kern/handler.c kern/command.c kern/corecmd.c \
 	kern/$(target_cpu)/dl.c kern/parser.c kern/partition.c \
-	kern/i386/tsc.c kern/i386/pit.c \
+	kern/i386/tsc.c kern/i386/pit.c kern/i386/string.c \
 	kern/generic/rtc_get_time_ms.c \
 	kern/generic/millisleep.c \
 	kern/env.c \

=== modified file 'conf/i386-pc.rmk'

@@ -46,7 +46,7 @@ kernel_img_SOURCES = kern/i386/pc/startu
 	kern/time.c kern/list.c kern/command.c kern/corecmd.c \
 	kern/$(target_cpu)/dl.c kern/i386/pc/init.c kern/i386/pc/mmap.c \
 	kern/parser.c kern/partition.c \
-	kern/i386/tsc.c kern/i386/pit.c \
+	kern/i386/tsc.c kern/i386/pit.c kern/i386/string.c \
 	kern/generic/rtc_get_time_ms.c \
 	kern/generic/millisleep.c \
 	kern/env.c \

@@ -66,7 +66,7 @@ util/i386/pc/grub-setup.c_DEPENDENCIES =
 grub_setup_SOURCES = gnulib/progname.c util/i386/pc/grub-setup.c	\
 	util/misc.c kern/emu/misc.c kern/emu/getroot.c			\
 	kern/emu/hostdisk.c kern/device.c kern/disk.c kern/err.c	\
-	kern/misc.c kern/partition.c kern/file.c			\
+	kern/misc.c kern/partition.c kern/file.c kern/i386/string.c	\
 	kern/emu/mm.c kern/fs.c kern/env.c kern/list.c fs/fshelp.c	\
 									\
 	fs/affs.c fs/cpio.c fs/ext2.c fs/fat.c fs/hfs.c			\

=== modified file 'conf/i386-qemu.rmk'

@@ -25,7 +25,7 @@ kernel_img_SOURCES = kern/i386/qemu/star
 	kern/rescue_parser.c kern/rescue_reader.c \
 	kern/time.c kern/list.c  kern/command.c kern/corecmd.c \
 	kern/$(target_cpu)/dl.c kern/parser.c kern/partition.c \
-	kern/i386/tsc.c kern/i386/pit.c \
+	kern/i386/tsc.c kern/i386/pit.c kern/i386/string.c \
 	kern/generic/rtc_get_time_ms.c \
 	kern/generic/millisleep.c \
 	kern/env.c \

=== modified file 'conf/mips-qemu-mips.rmk'

@@ -11,7 +11,7 @@ kernel_img_SOURCES = kern/$(target_cpu)/
 	kern/$(target_cpu)/$(target_machine)/init.c 		\
 	kern/disk.c kern/dl.c kern/err.c kern/file.c kern/fs.c 		\
 	kern/misc.c kern/mm.c kern/term.c 	\
-	kern/rescue_parser.c kern/rescue_reader.c \
+	kern/rescue_parser.c kern/rescue_reader.c kern/string.c \
 	kern/list.c  kern/command.c kern/corecmd.c	\
 	kern/parser.c kern/partition.c kern/env.c kern/$(target_cpu)/dl.c 	\
 	kern/generic/millisleep.c kern/generic/rtc_get_time_ms.c kern/time.c    \

=== modified file 'conf/mips-yeeloong.rmk'

@@ -15,7 +15,7 @@ kernel_img_SOURCES = kern/$(target_cpu)/
 	kern/$(target_cpu)/$(target_machine)/init.c 		\
 	kern/disk.c kern/dl.c kern/err.c kern/file.c kern/fs.c 		\
 	kern/misc.c kern/mm.c kern/term.c 	\
-	kern/rescue_parser.c kern/rescue_reader.c \
+	kern/rescue_parser.c kern/rescue_reader.c kern/string.c \
 	kern/list.c  kern/command.c kern/corecmd.c	\
 	kern/parser.c kern/partition.c kern/env.c kern/$(target_cpu)/dl.c 	\
 	kern/generic/millisleep.c kern/generic/rtc_get_time_ms.c kern/time.c    \

=== modified file 'conf/powerpc-ieee1275.rmk'

@@ -12,7 +12,7 @@ kernel_img_SOURCES = kern/powerpc/ieee12
 	kern/ieee1275/ieee1275.c kern/main.c kern/device.c 		\
 	kern/disk.c kern/dl.c kern/err.c kern/file.c kern/fs.c 		\
 	kern/misc.c kern/mm.c kern/term.c 	\
-	kern/rescue_parser.c kern/rescue_reader.c \
+	kern/rescue_parser.c kern/rescue_reader.c kern/string.c \
 	kern/list.c  kern/command.c kern/corecmd.c	\
 	kern/ieee1275/init.c 						\
 	kern/ieee1275/mmap.c						\

=== modified file 'conf/sparc64-ieee1275.rmk'

@@ -25,7 +25,7 @@ kernel_img_SOURCES = kern/sparc64/ieee12
 	kern/ieee1275/ieee1275.c kern/main.c kern/device.c		\
 	kern/disk.c kern/dl.c kern/err.c kern/file.c kern/fs.c		\
 	kern/misc.c kern/mm.c kern/term.c			\
-	kern/rescue_parser.c kern/rescue_reader.c \
+	kern/rescue_parser.c kern/rescue_reader.c kern/string.c \
 	kern/list.c  kern/command.c kern/corecmd.c	\
 	kern/sparc64/ieee1275/ieee1275.c 				\
 	kern/sparc64/ieee1275/init.c 					\

@@ -48,7 +48,7 @@ util/sparc64/ieee1275/grub-setup.c_DEPEN
 grub_setup_SOURCES = util/sparc64/ieee1275/grub-setup.c			\
 	util/ieee1275/ofpath.c util/misc.c kern/emu/hostdisk.c		\
 	kern/emu/misc.c kern/emu/getroot.c kern/emu/mm.c kern/device.c	\
-	kern/disk.c kern/err.c kern/misc.c 				\
+	kern/disk.c kern/err.c kern/misc.c kern/string.c 		\
 	kern/partition.c kern/file.c kern/fs.c kern/env.c kern/list.c	\
 	fs/fshelp.c							\
 									\

=== modified file 'conf/tests.rmk'

@@ -21,7 +21,7 @@ functional_test_mod_LDFLAGS = $(COMMON_L
 
 # Rules for unit tests
 check_UTILITIES += example_unit_test
-example_unit_test_SOURCES = tests/example_unit_test.c kern/list.c kern/misc.c tests/lib/test.c tests/lib/unit_test.c
+example_unit_test_SOURCES = tests/example_unit_test.c kern/list.c kern/misc.c kern/string.c tests/lib/test.c tests/lib/unit_test.c
 example_unit_test_CFLAGS  = -Wno-format
 
 # Rules for functional tests

=== modified file 'conf/x86-efi.rmk'

@@ -26,7 +26,7 @@ kernel_img_SOURCES = kern/$(target_cpu)/
 	kern/env.c symlist.c kern/efi/efi.c kern/efi/init.c kern/efi/mm.c \
 	term/efi/console.c disk/efi/efidisk.c \
 	kern/time.c kern/list.c  kern/command.c kern/corecmd.c \
-	kern/i386/tsc.c kern/i386/pit.c \
+	kern/i386/tsc.c kern/i386/pit.c kern/i386/string.c \
 	kern/generic/rtc_get_time_ms.c \
 	kern/generic/millisleep.c
 ifeq ($(target_cpu),x86_64)

=== added file 'kern/i386/string.c'

=== modified file 'kern/misc.c'

@@ -506,26 +506,6 @@ grub_strndup (const char *s, grub_size_t
   return p;
 }
 
-void *
-grub_memset (void *s, int c, grub_size_t n)
-{
-  unsigned char *p = (unsigned char *) s;
-
-  while (n--)
-    *p++ = (unsigned char) c;
-
-  return s;
-}
-#ifndef APPLE_CC
-void *memset (void *s, int c, grub_size_t n)
-  __attribute__ ((alias ("grub_memset")));
-#else
-void *memset (void *s, int c, grub_size_t n)
-{
-  return grub_memset (s, c, n);
-}
-#endif
-
 grub_size_t
 grub_strlen (const char *s)
 {

=== added file 'kern/string.c'

Thanks,

Colin Watson                                       [[email protected]]

On non-device memory GRUB should take advantage of cache. On MIPS enabling/disabling cache is done by using a different address. So we have all infrastructure necessary for differentiating cacheable/non-cacheable is present. Enabling cache on video memory is however more of a trouble. One of the reasons is that cache nmishandling produces difficult bugs.

It's ok to use this code but be sure to mention its origin. It's also ok to keep its license unless big divergeance is to be expected.

Did you test it on x86_64?

Regards
Vladimir 'φ-coder/phcoder' Serbinenko

Regards
Vladimir 'φ-coder/phcoder' Serbinenko

void
grub_memset (void *p, int c, grub_size_t len)
{
grub_uint8_t pattern8 = c;
if (len >= 3 * sizeof (unsigned long))

    {
      unsigned long patternl = 0;
      int i;
      for (i = 0; i < sizeof (unsigned long); i++)
	patternl |= ((unsigned long) pattern8) << (8 * i);
      while (len > 0 && (((grub_addr_t) p) & (sizeof (unsigned long) - 1)))
	{
	  *(grub_uint8_t *) p = pattern8;
	  p = (grub_uint8_t *) p + 1;
	}
      while (len >= sizeof (unsigned long))
	{
	  *(unsigned long *) p = patternl;
	  p = (unsigned long *) p + 1;
	}
    }
  while (len > 0)
    {
      *(grub_uint8_t *) p = pattern8;
      p = (grub_uint8_t *) p + 1;
    }
}

Thanks for this, and sorry for my delay.

I haven't compared the disassembly, but once I fixed up your code it performed within about 10% of the optimised version I posted before, so about 640ms original, 160ms with i386-specific memset, and 176ms with your generic memset. Even though that isn't quite equivalent, I don't think that 16ms is going to be a major problem, and so I would suggest going with the generic version. Please check the following.

2010-07-23 Vladimir Serbinenko <[email protected]> 2010-07-23 Colin Watson <[email protected]>

* kern/misc.c (grub_memset): Optimise to reduce cache stalls.

=== modified file 'kern/misc.c'

@@ -518,12 +518,39 @@ grub_strndup (const char *s, grub_size_t
 }
 
 void *
-grub_memset (void *s, int c, grub_size_t n)
+grub_memset (void *s, int c, grub_size_t len)
 {
-  unsigned char *p = (unsigned char *) s;
+  void *p = s;
+  grub_uint8_t pattern8 = c;
 
-  while (n--)
-    *p++ = (unsigned char) c;
+  if (len >= 3 * sizeof (unsigned long))
+    {
+      unsigned long patternl = 0;
+      grub_size_t i;
+
+      for (i = 0; i < sizeof (unsigned long); i++)
+	patternl |= ((unsigned long) pattern8) << (8 * i);
+
+      while (len > 0 && (((grub_addr_t) p) & (sizeof (unsigned long) - 1)))
+	{
+	  *(grub_uint8_t *) p = pattern8;
+	  p = (grub_uint8_t *) p + 1;
+	  len--;
+	}
+      while (len >= sizeof (unsigned long))
+	{
+	  *(unsigned long *) p = patternl;
+	  p = (unsigned long *) p + 1;
+	  len -= sizeof (unsigned long);
+	}
+    }
+
+  while (len > 0)
+    {
+      *(grub_uint8_t *) p = pattern8;
+      p = (grub_uint8_t *) p + 1;
+      len--;
+    }
 
   return s;
 }

Colin Watson                                       [[email protected]]

[snip]

patternl |= patternl << 8;
patternl |= patternl << 16;
patternl |= patternl << 32;
patternl |= patternl << 64;

The latter is unfortunately not the case. At least gcc 4.5.0 prints a warning but still produces code.

$ cat <<EOF >f.c
unsigned long f(unsigned long x)
{
  x |= x << 32;
  x |= x << 64;
  return x;
}

$ gcc -O3 -S f.c
x.c: In function ‘f’:
x.c:3: warning: left shift count >= width of type
x.c:4: warning: left shift count >= width of type

$ cat f.s
...
        pushl   %ebp
        movl    $32, %ecx
        movl    %esp, %ebp
        movl    8(%ebp), %eax
        popl    %ebp
        movl    %eax, %edx
        sall    %cl, %edx
        movl    $64, %ecx
        orl     %eax, %edx
        movl    %edx, %eax
        sall    %cl, %eax
        orl     %edx, %eax
        ret

Regards,
Christian Franke

Ok then, a compile-time conditional should fix that.

unsigned long patternl = pattern8;
if (8 < sizeof patternl) patternl |= patternl << 8;

if (16 < sizeof patternl) patternl |= patternl << 16;
if (32 < sizeof patternl) patternl |= patternl << 32;
if (64 < sizeof patternl) patternl |= patternl << 64;

I'm pretty confident in gcc's ability to optimize this version. I hope.

Thanks to Seth for pointing out my obvious bug.

unsigned long patternl = pattern8;

if (1 < sizeof patternl) patternl |= patternl << 8;
if (2 < sizeof patternl) patternl |= patternl << 16;
if (4 < sizeof patternl) patternl |= patternl << 32;
if (8 < sizeof patternl) patternl |= patternl << 64;

I no longer have the system on which I benchmarked this. However, since N is always either 4 or 8 on current targets, this can only amount to micro-optimisation which I don't think can possibly matter much; we're talking a handful of cycles at most. Do we really need to spend time bikeshedding this? The important thing is taking only a cache stall per long rather than a cache stall per byte; anything else is likely to be noise.

Colin Watson                                       [[email protected]]

Go ahead.

Regards
Vladimir 'φ-coder/phcoder' Serbinenko