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 <[email protected]> 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 <[email protected]> --- 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 <[email protected]> + 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 _______________________________________________ M4-patches mailing list [email protected] http://lists.gnu.org/mailman/listinfo/m4-patches
