From 3875526926123259521514de9c8d675e3797275a Mon Sep 17 00:00:00 2001 From: Kenneth Graunke Date: Fri, 15 Jul 2011 02:27:49 -0700 Subject: 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 --- src/glsl/s_expression.cpp | 64 ++++++++++++++++++++++++++++++++++------------- 1 file changed, 46 insertions(+), 18 deletions(-) (limited to 'src/glsl/s_expression.cpp') diff --git a/src/glsl/s_expression.cpp b/src/glsl/s_expression.cpp index a922a50d3b9..e704a3be20d 100644 --- a/src/glsl/s_expression.cpp +++ b/src/glsl/s_expression.cpp @@ -25,10 +25,13 @@ #include #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); -- cgit v1.2.3