Friday, August 30, 2019 [Tweets] [Favorites]

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.


Stay up-to-date by subscribing to the Comments RSS Feed for this post.

Leave a Comment