Adventures in the land of substrings and RegExps.
Few weeks ago a bug was filed against Dart SDK citing “very low performance of String.substring”. Here is a core of microbenchmark developer submitted together with the issue:
Depending on your background you might also be surprised by a non-linear growth in Dart run times: increasing input string size by a factor of \(2\) (\(25000\) to \(50000\)) increases running time by a factor of \(4\) (\(244\) to \(949\) milliseconds).
Most of the time is spent doing a substring operation, so why Dart VM’s substring is so much slower than V8’s? They must be implemented completely differently - and indeed they are.
Dart VM implements String.substring(start, end) in a very straightforward manner: it allocates a new String object of length end - start + 1 and copies string contents into this new string. Formally speaking this is an \(O(n)\) implementation - also known as linear time - it requires amount of operations proportional to the length of a substring.
If we assuming that initial length of the string s is \(N\) the the first iteration of the loop creates a substring of length \(N - 1\), next iteration creates substring of length \(N - 2\) and so on, until the last iteration creates a substring of length \(1\). This means the loop requires
