[Mesa-dev] [PATCH 0/2] glsl: avoid quadratic behavior during preprocessing

[Nicolai Hähnle]

Hi all,

The GLSL preprocessor operates by successively appending preprocessed
pieces to a string via ralloc_str_append and friends. Each of these
functions calls realloc() every time it is used, which is potentially
quadratic behavior.

This doesn't seem to be a problem usually because the system allocator
can avoid copies most of the time. But when building with the address
sanitizer, realloc actually copies the memory every single time, and
both time spent in memcpy() and total memory usage goes through the
roof (according to top, arb_shader_atomic_counters-max-counters uses a
cool 2.5GB of RAM when asan is enabled, which is how this came to my
attention in the first place).

This series adds a simple stringbuf utility which implements appends
by internally keeping a linked list of buffers that are then concatenated
once at the end.

It doesn't seem to be worth the effort to modify other users of the
ralloc append functions, since most of them only concatenate a small
number of pieces.

Please review!
Thanks,
Nicolai
--
 src/compiler/glsl/glcpp/glcpp-parse.y |  99 +++++--------
 src/compiler/glsl/glcpp/glcpp.h       |   7 +-
 src/compiler/glsl/glcpp/pp.c          |  45 +++---
 src/util/Makefile.sources             |   2 +
 src/util/stringbuf.c                  | 185 ++++++++++++++++++++++++
 src/util/stringbuf.h                  |  97 +++++++++++++
 6 files changed, 343 insertions(+), 92 deletions(-)