Make String.split 10x faster.
Almost all uses of String.split in the Android codebase use trivial single
literal character separators. This patch optimizes that case to avoid the
use of regular expressions entirely.
The 10x speedup isn't the whole story, because the speedup is really
proportional to the number of separators in the input. 10x is easily
achievable, but the speedup could be arbitrarily high.
Before:
benchmark us logarithmic runtime
PatternSplitComma 84.8 XXXXXXXXXXXXXX||||||||||||||
PatternSplitLiteralDot 85.0 XXXXXXXXXXXXXX||||||||||||||
StringSplitComma 166.3 XXXXXXXXXXXXXXXXXXXXXXXXXXXX|
StringSplitHard 173.6 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
StringSplitLiteralDot 167.7 XXXXXXXXXXXXXXXXXXXXXXXXXXXX|
After:
benchmark us logarithmic runtime
PatternSplitComma 18.9 XXX|||||||||||||||||||||
PatternSplitLiteralDot 19.0 XXX|||||||||||||||||||||
StringSplitComma 18.8 XXX|||||||||||||||||||||
StringSplitHard 174.2 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
StringSplitLiteralDot 18.8 XXX|||||||||||||||||||||
(The benchmarks starting "Pattern" use a precompiled Pattern for performance.
Those starting "String" use String.split and would traditional entail a
temporary Pattern. As you can see, creating Patterns is very expensive for
us, and each one throws a finalizer spanner in the GC works too. The new
fast path avoids all this. I'll commit the benchmark -- along with all the
others I've ever used -- to http://code.google.com/p/dalvik this afternoon.)
Tests? We actually pass _more_ tests after this patch, because the increase
in performance means we don't hit timeouts.
Change-Id: I404298e21a78d72cf5ce6ea675844bf251e3825b
5 files changed