Mon, 06 Mar 2023 11:27:57 +0000 encoding: avoid quadratic time complexity when json-encoding non-UTF8 strings
Arseniy Alekseyev <aalekseyev@janestreet.com> [Mon, 06 Mar 2023 11:27:57 +0000] rev 50400
encoding: avoid quadratic time complexity when json-encoding non-UTF8 strings Apparently the code uses "+=" with a bytes object, which is linear-time, so the whole encoding is quadratic-time. This patch makes us use a bytearray object, instead, which has a(n amortized-)constant-time append operation. The encoding is still not particularly fast, but at least a 10MB file takes tens of seconds, not many hours to encode.
(0) -30000 -10000 -3000 -1000 -300 -100 -10 -1 +1 +10 +30 +100 +300 +1000 tip