flâneur

Accidentally Quadratic

accidentallyquadratic.tumblr.com · 4,404 words · saved by 1 readers

I just fixed a bug in the implementation of constant folding in the C# and VB.Net compilers. They used to require O(n^2) space. Now they require O(n) space. The naive approach to implementing string concatenation for an expression such as "S1" + "S2" + "S3" is to recursively visit the left-hand and right-hand operands and compute their constant string values, and then concatenate these strings to produce the constant string for the concatenation. It seems obviously correct and the only reasonable way to do it. But it has a serious problem. The concatenation operation is left associative, so for a long sequence of n concatenations, each of size k, we would produce intermediate results of size k, 2k, 3k, and so on up to nk. The total amount of space needed to represent this collection of strings is O(k n^2). For moderately-sized values of n, this would cause the compilers to run out of memory and crash. This is not merely a theoretical problem, as we had been getting customer reports o

Accidentally Quadratic Constant Folding Neal Gafter writes: I just fixed a bug in the implementation of constant folding in the C# and VB.Net compilers. They used to require O(n^2) space. Now they require O(n) space. The naive approach to implementing string concatenation for an expression such as "S1" + "S2" + "S3" is to recursively visit the left-hand and right-hand operands and compute their constant string values, and then concatenate these strings to produce the constant string for the concatenation. It seems obviously correct and the only reasonable way to do it. But it has a…

saved by

related reading