A sick idea - mmapped file output

["Zack Weinberg" <zackw at stanford dot edu>]

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;
}