A sick idea - mmapped file output

[Billinghurst, David (CRTS)]

SGI origin 200 / irix6.5 / cc

       usr     sys     wall
stupid  934     42      1000
clever  635     46      700
signal  529     44      588


and with gcc 2.95.2

        usr     sys     wall
stupid  840     36      895
clever  564     46      628
signal  607     44      672


> -----Original Message-----
> From:	Zack Weinberg [SMTP:zackw@stanford.edu]
> Sent:	Friday, 3 November 2000 16:41
> To:	gcc@gcc.gnu.org
> Subject:	A sick idea - mmapped file output
> 
> The standalone preprocessor has a performance problem on its output
> end.  We do lots and lots of short fputs calls, and this can take up
> to 50% of total CPU time.  The sensible thing to do is to bypass
> stdio; we already do that on the input end, so there are no additional
> portability concerns.
> 
> We get some nice performance wins by loading large headers with mmap
> instead of read, because the kernel can then read ahead while we
> process the file, instead of having to get everything into memory
> before read(2) returns.  So I was trying to think of a way to do the
> equivalent on the write end.  The basic problem with mmap for output
> is we don't know how much space we need ahead of time, and mmap won't
> extend the file for you.  Even if you request a mapping bigger than
> the file, you get lethal signals if you try to write past the end.
> 
> However, you can anticipate running off the end and extend the file
> with ftruncate.  POSIX and SUS don't guarantee that this works, but
> assuming it does, this is indeed faster than write(2) - until you run
> out of mapping, at which point you have a problem.  Or, even cleverer,
> you can catch the signal and extend it then, but this doesn't seem to
> be any faster than anticipating the end (not surprising; signals ain't
> cheap).  
> 
> Appended to this message is a test program.  I am interested to know:
> 
> - Does it compile on your system?
> - Does it generate three identical files, each 32MB, when run?  They
>   will be named mmapexpt.{stu,cle,hcl}.  The actual contents of each
>   file are not interesting, and they're binary garbage, so don't cat
>   them.
> - What's the timing report say?
> - Do you have any suggestions for what to do when you run off the end
>   of the mapping?  Bonus points if your idea doesn't involve MAP_FIXED,
>   and/or if it works with the signal approach.
> 
> Here's what I get on my i386-linux box.  All numbers are in ticks.
> Expect variances of +-20 ticks either way on all these numbers.
> 
>         usr     sys     wall
> stupid  614     28      644
> clever  508     19      538
> signal  500     17      523
> 
> You may notice that the program does not munmap the files before
> exiting.  (There are commented-out munmap calls in the code.)  This is
> because munmap is surprisingly expensive, at least on my machine.
> System time for the 'clever' and 'signal' tests goes up to 80 ticks or
> so when they're left in.  I'm guessing this is because munmap has to
> blow away TLB entries and so on before it returns, but _exit can do it
> in the background.
> 
> zw
> 
> /* Experimental fast output routine.  The idea is as follows:
>    we have a huge block of memory (address space is cheap) mapped to the
>    output file.  The output file is not actually as large as the mapped
>    block.  The generator code blindly writes into the mapped block; if
>    it runs past the end of the file, the program will get a SIGBUS.
>    The signal handler then calls ftruncate to make the file bigger, and
>    we return to the generator.  */
> 
> #include <sys/types.h>
> #include <sys/mman.h>
> #include <unistd.h>
> #include <fcntl.h>
> #include <signal.h>
> #include <stdlib.h>
> #include <stdio.h>
> #include <sys/times.h>
> 
> #define CHUNK (32 * 1024)
> #define MAPSZ (64 * 1024 * 1024)
> #define ITERATIONS (MAPSZ / 2)
> 
> /* These variables are modified only by the signal handler and the
>    setup code, so they need not be volatile.  */
> 
> static int fd;
> static char *base;
> static off_t extent;
> static off_t limit;
> 
> void
> sigbus (unused)
>      int unused;
> {
>   extent *= 2;
>   if (extent > limit)
>     /* XXX What do we do when we run out of address space?  */
>     abort ();
> 
>   ftruncate (fd, extent);
> }
> 
> /* Generate lots of random text.  Accepts a pointer to the buffer,
>    returns a pointer to where it stopped writing.  */
> 
> char *
> hc_generate (p)
>      char *p;
> {
>   int n;
> 
>   for (n = 0; n < ITERATIONS; n++)
>     *p++ = (rand() % 256);
>   return p;
> }
> 
> void
> hyperclever()
> {
>   char *p;
>   struct sigaction sa;
>  
>   fd = open ("mmapexpt.hcl", O_RDWR|O_CREAT|O_TRUNC, 0666);
>   ftruncate (fd, CHUNK);
>   base = mmap (0, MAPSZ + 4096, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);
>   extent = CHUNK;
>   limit = MAPSZ;
> 
>   sigemptyset (&sa.sa_mask);
>   sa.sa_handler = sigbus;
>   sa.sa_flags = SA_RESTART;
>   sigaction (SIGBUS, &sa, NULL);
> 
>   p = hc_generate (base);
> 
>   signal (SIGBUS, SIG_DFL);
>   ftruncate (fd, p - base);
>   /*  munmap (base, MAPSZ); */
>   close (fd);
> }
> 
> /* Less clever approach which doesn't use signal handlers.  Same
> principle,
>    though.  */
> 
> char *
> cl_generate (char *p)
> {
>   int i, j;
>   char *base = p;
>   char *hiwat = p + extent;
> 
>   i = 0;
>   for (;;)
>     {
>       for (j = 0; j < 4096 && i < ITERATIONS; j++, i++)
> 	*p++ = (rand() % 256);
> 
>       if (i >= ITERATIONS)
> 	return p;
> 
>       if (p >= hiwat)
> 	{
> 	  extent *= 2;
> 	  if (extent > limit)
> 	    abort ();
> 	  ftruncate (fd, extent);
> 	  hiwat = base + extent;
> 	}
>     }
> }
> 
> void
> clever()
> {
>   char *p;
> 
>   fd = open ("mmapexpt.cle", O_RDWR|O_CREAT|O_TRUNC, 0666);
>   ftruncate (fd, CHUNK);
>   base = mmap (0, MAPSZ + 4096, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);
>   extent = CHUNK;
>   limit = MAPSZ;
> 
>   p = cl_generate (base);
> 
>   ftruncate (fd, p - base);
>   /*  munmap (base, MAPSZ); */
>   close (fd);
> }
> 
> /* And for comparison, this one uses stdio.  */
> 
> void
> stupid ()
> {
>   int n;
>   FILE *fp = fopen ("mmapexpt.stu", "w");
> 
>   for (n = 0; n < ITERATIONS; n++)
>     {
>       int c = (rand() % 256);
>       putc_unlocked (c, fp);
>     }
>   fclose (fp);
> }
> 
> /* Driver. */
> 
> int
> main(void)
> {
>   struct tms a, b;
>   clock_t aw, bw;
>   int randseed = times(&a);
> 
>   setvbuf (stdout, 0, _IOLBF, 0);
> 
>   fputs("\tusr\tsys\twall\n", stdout);
> 
>   srand(randseed);
>   aw = times(&a);
>   stupid();
>   bw = times(&b);
> 
>   printf ("stupid\t%d\t%d\t%d\n",
> 	  b.tms_utime - a.tms_utime,
> 	  b.tms_stime - a.tms_stime,
> 	  bw - aw);
> 
>   srand(randseed);
>   aw = times(&a);
>   clever();
>   bw = times(&b);
> 
>   printf ("clever\t%d\t%d\t%d\n",
> 	  b.tms_utime - a.tms_utime,
> 	  b.tms_stime - a.tms_stime,
> 	  bw - aw);
> 
>   srand(randseed);
>   aw = times(&a);
>   hyperclever();
>   bw = times(&b);
> 
>   printf ("signal\t%d\t%d\t%d\n",
> 	  b.tms_utime - a.tms_utime,
> 	  b.tms_stime - a.tms_stime,
> 	  bw - aw);
> 
>   return 0;
> }