Re: argv_ref patch 29: huge speedup to m4 input engine

[Eric Blake]

Eric Blake <ebb9 <at> byu.net> writes:

> Nearly a year after Bruno first profiled the m4 input engine, and
> suggested some ideas on how to make it more efficient by parsing a block
> rather than a character at a time, I have finally merged the patch into
> the master branch.  The idea is that repeatedly calling next_char() to
> grab one character at a time is a lot of overhead; grabbing a lookahead
> buffer, and using string scanning operations that can look a word at a
> time reduces this overhead.  It relies on the gnulib freadptr/freadseek
> extensions to grab lookahead buffers of files, and the gnulib memchr2
> extension to find the first of two bytes that could potentially start a
> quote delimiter.

I decided to port part of this back to branch-1.4.  Since that is the stable 
branch, I did not want to risk introducing freadptr or freadseek; but feel that 
memchr2 is safe.  Since much of m4's time is spent on reparsing macro 
expansions (and not the original file), this still gives something like a 15% 
improvement.

With this patch, I'm very close to declaring 1.4.13 ready to release; there are 
still some pending reports of compilation or test failures on obscure platforms 
that have been reported on the previous snapshot, but since they have not had 
much active feedback, I don't see them as showstoppers.  Do I need to post 
another snapshot first, to help reviewers?


From: Eric Blake <address@hidden>
Date: Thu, 19 Feb 2009 15:39:29 -0700
Subject: [PATCH] Speed up input engine, by searching for quotes by buffer.

* src/input.c (struct input_block): Add end pointer to string.
(push_string_finish, push_wrapup): Populate it.
(next_token): For quotes, attempt a buffer search.
* NEWS: Document this.

Signed-off-by: Eric Blake <address@hidden>
---
 ChangeLog   |    6 ++++++
 NEWS        |    2 ++
 src/input.c |   50 +++++++++++++++++++++++++++++++++++++++++++++++---
 3 files changed, 55 insertions(+), 3 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index a80dfea..edff0b8 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,11 @@
 2009-02-18  Eric Blake  <address@hidden>

+       Speed up input engine, by searching for quotes by buffer.
+       * src/input.c (struct input_block): Add end pointer to string.
+       (push_string_finish, push_wrapup): Populate it.
+       (next_token): For quotes, attempt a buffer search.
+       * NEWS: Document this.
+
        Speed up translit when from argument is short.
        * m4/gnulib-cache.m4: Import memchr2 module.
        * src/builtin.c (m4_translit): Use memchr2 when possible.
diff --git a/NEWS b/NEWS
index 31821b7..22ea347 100644
--- a/NEWS
+++ b/NEWS
@@ -13,6 +13,8 @@ Software Foundation, Inc.
 ** The `translit' builtin has been made more efficient when the second
    argument is short.

+** The input engine has been optimized for faster processing.
+
 ** The command line option `--debugfile', introduced in 1.4.7, now
    treats its argument as optional, in order to allow setting the debug
    output back to stderr when used without an argument; and order is now
diff --git a/src/input.c b/src/input.c
index a9471dc..63480be 100644
--- a/src/input.c
+++ b/src/input.c
@@ -1,7 +1,7 @@
 /* GNU m4 -- A simple macro processor

    Copyright (C) 1989, 1990, 1991, 1992, 1993, 1994, 2004, 2005, 2006,
-   2007, 2008 Free Software Foundation, Inc.
+   2007, 2008, 2009 Free Software Foundation, Inc.

    This file is part of GNU M4.

@@ -23,6 +23,8 @@

 #include "m4.h"

+#include "memchr2.h"
+
 /* Unread input can be either files, that should be read (eg. included
    files), strings, which should be rescanned (eg. macro expansion text),
    or quoted macro definitions (as returned by the builtin "defn").
@@ -82,6 +84,7 @@ struct input_block
       struct
        {
          char *string;         /* remaining string value */
+         char *end;            /* terminating NUL of string */
        }
        u_s;    /* INPUT_STRING */
       struct
@@ -276,8 +279,10 @@ push_string_finish (void)

   if (obstack_object_size (current_input) > 0)
     {
+      size_t len = obstack_object_size (current_input);
       obstack_1grow (current_input, '\0');
       next->u.u_s.string = (char *) obstack_finish (current_input);
+      next->u.u_s.end = next->u.u_s.string + len;
       next->prev = isp;
       isp = next;
       ret = isp->u.u_s.string; /* for immediate use only */
@@ -301,6 +306,7 @@ push_string_finish (void)
 void
 push_wrapup (const char *s)
 {
+  size_t len = strlen (s);
   input_block *i;
   i = (input_block *) obstack_alloc (wrapup_stack,
                                     sizeof (struct input_block));
@@ -308,7 +314,8 @@ push_wrapup (const char *s)
   i->type = INPUT_STRING;
   i->file = current_file;
   i->line = current_line;
-  i->u.u_s.string = (char *) obstack_copy0 (wrapup_stack, s, strlen (s));
+  i->u.u_s.string = (char *) obstack_copy0 (wrapup_stack, s, len);
+  i->u.u_s.end = i->u.u_s.string + len;
   wsp = i;
 }
 
@@ -951,10 +958,47 @@ next_token (token_data *td, int *line)
     }
   else
     {
+      bool fast = lquote.length == 1 && rquote.length == 1;
       quote_level = 1;
       while (1)
        {
-         ch = next_char ();
+         /* Try scanning a buffer first.  */
+         const char *buffer = (isp && isp->type == INPUT_STRING
+                               ? isp->u.u_s.string : NULL);
+         if (buffer && *buffer)
+           {
+             size_t len = isp->u.u_s.end - buffer;
+             const char *p = buffer;
+             do
+               {
+                 p = (char *) memchr2 (p, *lquote.string, *rquote.string,
+                                       buffer + len - p);
+               }
+             while (p && fast && (*p++ == *rquote.string
+                                  ? --quote_level : ++quote_level));
+             if (p)
+               {
+                 if (fast)
+                   {
+                     assert (!quote_level);
+                     obstack_grow (&token_stack, buffer, p - buffer - 1);
+                     isp->u.u_s.string += p - buffer;
+                     break;
+                   }
+                 obstack_grow (&token_stack, buffer, p - buffer);
+                 ch = to_uchar (*p);
+                 isp->u.u_s.string += p - buffer + 1;
+               }
+             else
+               {
+                 obstack_grow (&token_stack, buffer, len);
+                 isp->u.u_s.string += len;
+                 continue;
+               }
+           }
+         /* Fall back to a byte.  */
+         else
+           ch = next_char ();
          if (ch == CHAR_EOF)
            /* current_file changed to "" if we see CHAR_EOF, use
               the previous value we stored earlier.  */
-- 
1.6.1.2