Algorithm is accidentally quadratic

[yurikhan]

Hello there!

So today I tried to push a 2.5 megabyte file to my team’s Git server and it said “the pre-receive hook timed out after 120 seconds”.

I asked the CI priests (don’t laugh, it’s their official job description) what the 🔥 it could be doing, and they said “the only thing we do on JSON files is this” and supplied a small script involving the Python version of json_minify.

I ran it on my file. It finished in 76 minutes 12 seconds.

So I looked at the algorithm and found the cause.

• On the top level, it has a loop going through “interesting” places in the input, where “interesting” is defined as “a potential string delimiter, comment delimiter, or a newline”. It also maintains several flags reflecting the syntax at current position.
• If the current syntax is “inside string” and it finds a double quote, it might be a closing delimiter. So it checks if there is an even number (incl. zero) of backslashes preceding the double quote. If so, it is indeed a closing string delimiter.
• The way it checks for an even number of backslashes is… curious. It searches for the regular expression \\*$ in the whole substring from position 0 to current. This succeeds always before the end, and matches the longest span of backslashes, but it tries every possible starting position from 0 to the current position, unless the regular expression engine is smart enough to notice the anchor at the end and match backwards. (Spoiler warning: Most of them are not.)

As a proof of concept, I made this change:

         if val == '"' and not (in_multi or in_single):
-            escaped = end_slashes_re.search(string, 0, match.start())
+            pos = match.start()
+            while pos > 0 and string[pos - 1] == '\\':
+                pos -= 1

             # start of string or unescaped quote character to end string
-            if not in_string or (escaped is None or len(escaped.group()) % 2 == 0):  # noqa
+            if not in_string or ((match.start() - pos) % 2 == 0):  # noqa
                 in_string = not in_string
             index -= 1  # include " character in next catch

and it passed all existing tests and processed my 2.5M file in 0.697 seconds. It is definitely a lot less pythonic than the original way, but it sure does the job.

You might want to review all ports where this check is done via the same regexp, and verify which of them exhibit quadratic complexity.

There is nothing peculiar about my JSON file; just generate one that has a moderately large number of double quote characters.

[getify]

This is a great point, thank you for finding it. Just for posterity, would you be willing to post a PR for the python code? I'm going to look at the JS code versions. But I'm not really familiar with the other language ports enough to do those reviews.

[getify]

I think this problem could exist in the JS version, here:

JSON.minify/minify.json.js

Line 35 in 0827b7f

tmp2 = lc.match(/(\\)*$/);

Although, the regex is rooted to the end with $, so I was assuming that the regex works backward from the end, rather than from the start.

[getify]

I also wonder if the current regex approach could work fine if we limit the "left hand context" string to a max length, say 250 characters. We could pick a large enough number that we know there wouldn't be a string of \ characters that long, but whatever that fixed number is, it wouldn't be anywhere near as long as the O(n) growth of the length of the string as it gets toward 2.5mb.

[getify]

Now I'm wondering if that regex might work better with + instead of *. Could you possibly check to see if that addresses the quadratic growth issue? I really thought I knew that $ rooted the regex to start its backtracking from the end rather than from the start.

[yurikhan]

Just for posterity, would you be willing to post a PR for the python code?

No problem. I don’t know how your release machinery works so I leave it to you.

the regex is rooted to the end with $, so I was assuming that the regex works backward from the end, rather than from the start.

For some regexen, backward matching might be possible, but greediness, backtracking, backreferences, UTF-8, and any combinations of the above make the general case complex, and I’m not surprised not all implementations bother with that.

Measure.

Now I'm wondering if that regex might work better with + instead of *. Could you possibly check to see if that addresses the quadratic growth issue?

Yes I could, and no it doesn’t.

[getify]

Thanks for checking/validating my questions about the RE.

It seems like maybe the least disruptive (least risky) fix is what I suggested, simply performing the regex check against a fixed chunk of the final X number of characters of the left-hand context... I think 100 characters is plenty large enough heuristically to ensure no non-pathological inputs would be negatively affected.

In JS, I can do:

tmp2 = lc.slice(-100).match(/(\\)*$/);

Could you check to see how that affects the performance, and how it compares to the loop approach you took?

[yurikhan]

In JS, I can do:

tmp2 = lc.slice(-100).match(/(\\)*$/);

Yes, it is slightly faster than doing the backward loop. However, this would make it fail on inputs that contain a string value containing 50 escaped backslashes followed by an escaped double quote.

[getify]

However, this would make it fail on inputs that contain a string value containing 50 escaped backslashes followed by an escaped double quote.

Right, but if we pick a large enough fixed number (100, 250, 1000, whatever), we know we're not going to hit any real (non-pathological) such inputs. It's a performance-optimization heuristic.

What do you think the smallest number is that we're safe there?

If we were really worried about that obscure breakage case, we could have a strategy of checking to see if the matched string is the same length as the fixed number (all filled with \s), and in that crazy corner case, we could try to match again with double the number of leftward characters.

BTW, I'm preferring the regex approach (with some heuristic) over switching to looping logic, not only because I think the regex engine can loop faster than user code can, but because a regex is more "portable" across languages than looping syntax, so it might be easier to port this fix (and for any future ports).

[yurikhan]

What do you think the smallest number is that we're safe there?

I am strictly pro-correctness in this kind of issues. (I don’t even fully accept the premise of the tool — in my opinion, comments are invalid in JSON and if you want comments you should be using YAML at source and re-serialize it to JSON at build time.)

we could have a strategy of checking to see if the matched string is the same length as the fixed number (all filled with \s), and in that crazy corner case, we could try to match again with double the number of leftward characters.

I think that leads to a loop of exponentially increasing fixed numbers and harder to follow code.

because a regex is more "portable" across languages than looping syntax

Only across those that have a regular expression engine built in or readily available, and if you can persuade it to perform.

[yurikhan]

An elegant solution could be a reversed view on the left context, and forward-matching on that view. However, Python does not provide reversed string views, and doing a reverse string copy on each iteration is still quadratic.