Mesa (master): glsl: Avoid massive ralloc_strndup overhead in S-Expression parsing.

[Kenneth Graunke]

Module: Mesa
Branch: master
Commit: 3875526926123259521514de9c8d675e3797275a
URL:    http://cgit.freedesktop.org/mesa/mesa/commit/?id=3875526926123259521514de9c8d675e3797275a

Author: Kenneth Graunke <kenneth at whitecape.org>
Date:   Fri Jul 15 02:27:49 2011 -0700

glsl: Avoid massive ralloc_strndup overhead in S-Expression parsing.

When parsing S-Expressions, we need to store nul-terminated strings for
Symbol nodes.  Prior to this patch, we called ralloc_strndup each time
we constructed a new s_symbol.  It turns out that this is obscenely
expensive.

Instead, copy the whole buffer before parsing and overwrite it to
contain \0 bytes at the appropriate locations.  Since atoms are
separated by whitespace, (), or ;, we can safely overwrite the character
after a Symbol.  While much of the buffer may be unused, copying the
whole buffer is simple and guaranteed to provide enough space.

Prior to this, running piglit-run.py -t glsl tests/quick.tests with GLSL
1.30 enabled took just over 10 minutes on my machine.  Now it takes 5.

NOTE: This is a candidate for stable release branches (because it will
      make running comparison tests so much less irritating.)

Signed-off-by: Kenneth Graunke <kenneth at whitecape.org>

---

 src/glsl/s_expression.cpp |   64 ++++++++++++++++++++++++++++++++------------
 src/glsl/s_expression.h   |    2 +-
 2 files changed, 47 insertions(+), 19 deletions(-)

diff --git a/src/glsl/s_expression.cpp b/src/glsl/s_expression.cpp
index a922a50..e704a3b 100644
--- a/src/glsl/s_expression.cpp
+++ b/src/glsl/s_expression.cpp
@@ -25,10 +25,13 @@
 #include <assert.h>
 #include "s_expression.h"
 
-s_symbol::s_symbol(const char *tmp, size_t n)
+s_symbol::s_symbol(const char *str, size_t n)
 {
-   this->str = ralloc_strndup (this, tmp, n);
-   assert(this->str != NULL);
+   /* Assume the given string is already nul-terminated and in memory that
+    * will live as long as this node.
+    */
+   assert(str[n] == '\0');
+   this->str = str;
 }
 
 s_list::s_list()
@@ -36,22 +39,26 @@ s_list::s_list()
 }
 
 static void
-skip_whitespace(const char *& src)
+skip_whitespace(const char *&src, char *&symbol_buffer)
 {
-   src += strspn(src, " \v\t\r\n");
+   size_t n = strspn(src, " \v\t\r\n");
+   src += n;
+   symbol_buffer += n;
    /* Also skip Scheme-style comments: semi-colon 'til end of line */
    if (src[0] == ';') {
-      src += strcspn(src, "\n");
-      skip_whitespace(src);
+      n = strcspn(src, "\n");
+      src += n;
+      symbol_buffer += n;
+      skip_whitespace(src, symbol_buffer);
    }
 }
 
 static s_expression *
-read_atom(void *ctx, const char *& src)
+read_atom(void *ctx, const char *&src, char *&symbol_buffer)
 {
    s_expression *expr = NULL;
 
-   skip_whitespace(src);
+   skip_whitespace(src, symbol_buffer);
 
    size_t n = strcspn(src, "( \v\t\r\n);");
    if (n == 0)
@@ -70,44 +77,65 @@ read_atom(void *ctx, const char *& src)
 	 expr = new(ctx) s_int(i);
    } else {
       // Not a number; return a symbol.
-      expr = new(ctx) s_symbol(src, n);
+      symbol_buffer[n] = '\0';
+      expr = new(ctx) s_symbol(symbol_buffer, n);
    }
 
    src += n;
+   symbol_buffer += n;
 
    return expr;
 }
 
-s_expression *
-s_expression::read_expression(void *ctx, const char *&src)
+static s_expression *
+__read_expression(void *ctx, const char *&src, char *&symbol_buffer)
 {
-   assert(src != NULL);
-
-   s_expression *atom = read_atom(ctx, src);
+   s_expression *atom = read_atom(ctx, src, symbol_buffer);
    if (atom != NULL)
       return atom;
 
-   skip_whitespace(src);
+   skip_whitespace(src, symbol_buffer);
    if (src[0] == '(') {
       ++src;
+      ++symbol_buffer;
 
       s_list *list = new(ctx) s_list;
       s_expression *expr;
 
-      while ((expr = read_expression(ctx, src)) != NULL) {
+      while ((expr = __read_expression(ctx, src, symbol_buffer)) != NULL) {
 	 list->subexpressions.push_tail(expr);
       }
-      skip_whitespace(src);
+      skip_whitespace(src, symbol_buffer);
       if (src[0] != ')') {
 	 printf("Unclosed expression (check your parenthesis).\n");
 	 return NULL;
       }
       ++src;
+      ++symbol_buffer;
       return list;
    }
    return NULL;
 }
 
+s_expression *
+s_expression::read_expression(void *ctx, const char *&src)
+{
+   assert(src != NULL);
+
+   /* When we encounter a Symbol, we need to save a nul-terminated copy of
+    * the string.  However, ralloc_strndup'ing every individual Symbol is
+    * extremely expensive.  We could avoid this by simply overwriting the
+    * next character (guaranteed to be whitespace, parens, or semicolon) with
+    * a nul-byte.  But overwriting non-whitespace would mess up parsing.
+    *
+    * So, just copy the whole buffer ahead of time.  Walk both, leaving the
+    * original source string unmodified, and altering the copy to contain the
+    * necessary nul-bytes whenever we encounter a symbol.
+    */
+   char *symbol_buffer = ralloc_strdup(ctx, src);
+   return __read_expression(ctx, src, symbol_buffer);
+}
+
 void s_int::print()
 {
    printf("%d", this->val);
diff --git a/src/glsl/s_expression.h b/src/glsl/s_expression.h
index c9dc676..642af19 100644
--- a/src/glsl/s_expression.h
+++ b/src/glsl/s_expression.h
@@ -129,7 +129,7 @@ public:
    void print();
 
 private:
-   char *str;
+   const char *str;
 };
 
 /* Lists of expressions: (expr1 ... exprN) */