Friday, August 30, 2019

Accidentally Quadratic Constant Folding

Neal Gafter:

Fixing the problem was fairly straightforward, using a technique I learned from the Cedar/Mesa compiler in the early ’80s. Rather than representing string constants in the compilers using strings, they are now represented using a data structure called Ropes. Concatenating two ropes requires only a small constant amount of memory.

Any compiler for a language that supports constant folding of string concatenation will run into this problem unless there is a similarly low-space representation of two concatenated strings. This is a technique that should be in the bag of tricks of any compiler writer.

Comments RSS · Twitter

Leave a Comment