tree f63bd19e0797e8263f25748e4a23ee139a3b051f
parent c5a274a7e81a9ae7d3270bb132c9e0949d80fb03
author Elliott Hughes <enh@google.com> 1270855873 -0700
committer Elliott Hughes <enh@google.com> 1270855873 -0700

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