String.indexOf optimization
Ivan Gerasimov
ivan.gerasimov at oracle.com
Tue Apr 15 17:13:28 UTC 2014
Hi everyone!
On 04.04.2014 21:13, Martin Buchholz wrote:
> Summary:
>
> Many people (myself included) have looked at this problem. It's unlikely
> that String.indexOf will change. It's hard to beat the naive
> implementation in the typical case.
But we can try to speed up this naive implementation a little bit.
We can separate the special case: When the substring's length == 1.
This special case can be done fast, and in the general case we can now
assume substring's length is at least 2.
Here's the webrev with the implementation of this idea:
http://cr.openjdk.java.net/~igerasim/indexof/0/webrev/
I've done some benchmarking with JMH and found no performance
degradation on my machine.
Of course, more testcases should be created and they should be tried on
different machines to be treated as reliable.
Benchmark Mode Thr Cnt Sec Mean
Mean error Units
o.b.IndexOfBench.benchIndexOf_1_A avgt 1 20 5
704.739 9.104 nsec/op
o.b.IndexOfBench.benchIndexOf_1_B avgt 1 20 5 *573.879*
9.820 nsec/op
o.b.IndexOfBench.benchIndexOf_2_A avgt 1 20 5
668.455 9.882 nsec/op
o.b.IndexOfBench.benchIndexOf_2_B avgt 1 20 5 *476.062*
6.063 nsec/op
o.b.IndexOfBench.benchIndexOf_3_A avgt 1 20 5
155.227 1.796 nsec/op
o.b.IndexOfBench.benchIndexOf_3_B avgt 1 20 5 *152.850 *
1.512 nsec/op
o.b.IndexOfBench.benchIndexOf_4_A avgt 1 20 5
656.183 5.904 nsec/op
o.b.IndexOfBench.benchIndexOf_4_B avgt 1 20 5 *515.178*
9.107 nsec/op
o.b.IndexOfBench.benchIndexOf_5_A avgt 1 20 5
140.609 7.305 nsec/op
o.b.IndexOfBench.benchIndexOf_5_B avgt 1 20 5 *129.603*
1.654 nsec/op
o.b.IndexOfBench.benchIndexOf_6_A avgt 1 20 5
127.713 1.497 nsec/op
o.b.IndexOfBench.benchIndexOf_6_B avgt 1 20 5 *122.177*
1.186 nsec/op
o.b.IndexOfBench.benchIndexOf_7_A avgt 1 20 5
430.148 4.875 nsec/op
o.b.IndexOfBench.benchIndexOf_7_B avgt 1 20 5 *387.338*
10.904 nsec/op
o.b.IndexOfBench.benchIndexOf_8_A avgt 1 20 5
2064.563 28.885 nsec/op
o.b.IndexOfBench.benchIndexOf_8_B avgt 1 20 5 *1858.669*
24.343 nsec/op
Benchmarks ending with A use the current indexOf implementation, with B
use the modified version.
These numbers show from 1.4% up to 28% performance increase.
The full listing is below.
Suggestions about what else to test are welcome!
Sincerely yours,
Ivan
---------------------
/**
* Copyright (c) 2014, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
* under the terms of the GNU General Public License version 2 only, as
* published by the Free Software Foundation. Oracle designates this
* particular file as subject to the "Classpath" exception as provided
* by Oracle in the LICENSE file that accompanied this code.
*
* This code is distributed in the hope that it will be useful, but WITHOUT
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
* version 2 for more details (a copy is included in the LICENSE file that
* accompanied this code).
*
* You should have received a copy of the GNU General Public License
version
* 2 along with this work; if not, write to the Free Software Foundation,
* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
*
* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
* or visit www.oracle.com if you need additional information or have any
* questions.
*/
package org.benches;
import org.openjdk.jmh.annotations.*;
import org.openjdk.jmh.logic.BlackHole;
import java.util.concurrent.TimeUnit;
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@State(Scope.Benchmark)
public class IndexOfBench {
// |||
final static char[] source1 =
"abababcabcacabcabcabcabcaccbcabcacbcabcacbcbcabcbcbacbcabcbabacbcbacbcabcabcabcabcabcabcabcacbacbacbacabcabcacbacbcabcbcbcaabdacbacabcabacbacabca".toCharArray();
final static char[] source2 =
"acfacafacfacfacfacafcafcacadcacdacaccacacdacacfcafcafcfacdacadcadcadcdacfacfacdacadcacdcfacfacdacdacdcfacdacdacdacgshgshasdabdahghjgwdshacavcavsc".toCharArray();
final static char[] source3 =
"tyrtytfytytuytfytuytggfghgdytyftytfdytdshfgjhdfytsfuythgsfhgjhfghtuysdfthgfsdhgystfjhgsfguysthgfgjhgdfjhgsjdghfythgsdfjhggfabduikjhfjhkjhfkjhgkjh".toCharArray();
final static char[] target1 = "abd".toCharArray();
final static char[] source4 =
"ahhhahahahahhahahahahhahahahhhahahahahahahahahahahhahahahahahahahahallallalalalalalkakakakakakakakakkakmamamamabammamamamamamaakaklalalaoalalalao".toCharArray();
final static char[] source5 =
"hgjkhjhjkdghkjhdfkjhgkjhdkjdhgkjdfhgkjdhfgkjdfhgkjhdfkjghkdjghkdjfhgkjhkdjhgkjdfhjkghkdjfhgkjdfhgkjdfhgkjdfhkgabhfkjghdkfjhgkjdfhgkjdfhgkjdfhgkhh".toCharArray();
final static char[] target2 = "ab".toCharArray();
final static char[] source6 =
"lskgjsklfjgskldfjgklsfjdlgkjsdflkgjskldfgjsdklfgjsl;kdfgjskldfjglksdfjglksfjglksdfjgklsfdjgslkdfjglksjdflkgsjfalksjdflkfgjsdklfjglskdfjglksdfjghh".toCharArray();
final static char[] target3 = "a".toCharArray();
final static char[] source7 =
"lskgajabfagskldfjgklsabclgkjsdflkabsabcdgjsdklfabclbkdfgjskabfjglksdfjabcdfjglabcfjgklsfabgslkdfjglksjdabcdsjfabcdedflabcjsdklfjglskdfabcksdfjghh".toCharArray();
final static char[] target4 = "abcde".toCharArray();
final static char[] source8 =
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa".toCharArray();
final static char[] target5 = "aaaab".toCharArray();
@GenerateMicroBenchmark
public void benchIndexOf_1_A(BlackHole bh) {
bh.consume(indexOfA(source1, 0, source1.length, target1, 0,
target1.length, 0));
}
@GenerateMicroBenchmark
public void benchIndexOf_1_B(BlackHole bh) {
bh.consume(indexOfB(source1, 0, source1.length, target1, 0,
target1.length, 0));
}
@GenerateMicroBenchmark
public void benchIndexOf_2_A(BlackHole bh) {
bh.consume(indexOfA(source2, 0, source2.length, target1, 0,
target1.length, 0));
}
@GenerateMicroBenchmark
public void benchIndexOf_2_B(BlackHole bh) {
bh.consume(indexOfB(source2, 0, source2.length, target1, 0,
target1.length, 0));
}
@GenerateMicroBenchmark
public void benchIndexOf_3_A(BlackHole bh) {
bh.consume(indexOfA(source3, 0, source3.length, target1, 0,
target1.length, 0));
}
@GenerateMicroBenchmark
public void benchIndexOf_3_B(BlackHole bh) {
bh.consume(indexOfB(source3, 0, source3.length, target1, 0,
target1.length, 0));
}
@GenerateMicroBenchmark
public void benchIndexOf_4_A(BlackHole bh) {
bh.consume(indexOfA(source4, 0, source4.length, target2, 0,
target2.length, 0));
}
@GenerateMicroBenchmark
public void benchIndexOf_4_B(BlackHole bh) {
bh.consume(indexOfB(source4, 0, source4.length, target2, 0,
target2.length, 0));
}
@GenerateMicroBenchmark
public void benchIndexOf_5_A(BlackHole bh) {
bh.consume(indexOfA(source5, 0, source5.length, target2, 0,
target2.length, 0));
}
@GenerateMicroBenchmark
public void benchIndexOf_5_B(BlackHole bh) {
bh.consume(indexOfB(source5, 0, source5.length, target2, 0,
target2.length, 0));
}
@GenerateMicroBenchmark
public void benchIndexOf_6_A(BlackHole bh) {
bh.consume(indexOfA(source6, 0, source6.length, target3, 0,
target3.length, 0));
}
@GenerateMicroBenchmark
public void benchIndexOf_6_B(BlackHole bh) {
bh.consume(indexOfB(source6, 0, source6.length, target3, 0,
target3.length, 0));
}
@GenerateMicroBenchmark
public void benchIndexOf_7_A(BlackHole bh) {
bh.consume(indexOfA(source7, 0, source7.length, target4, 0,
target4.length, 0));
}
@GenerateMicroBenchmark
public void benchIndexOf_7_B(BlackHole bh) {
bh.consume(indexOfB(source7, 0, source7.length, target4, 0,
target4.length, 0));
}
@GenerateMicroBenchmark
public void benchIndexOf_8_A(BlackHole bh) {
bh.consume(indexOfA(source8, 0, source8.length, target5, 0,
target5.length, 0));
}
@GenerateMicroBenchmark
public void benchIndexOf_8_B(BlackHole bh) {
bh.consume(indexOfB(source8, 0, source8.length, target5, 0,
target5.length, 0));
}
// implementations
static int indexOfA(char[] source, int sourceOffset, int sourceCount,
char[] target, int targetOffset, int targetCount,
int fromIndex) {
if (fromIndex >= sourceCount) {
return (targetCount == 0 ? sourceCount : -1);
}
if (fromIndex < 0) {
fromIndex = 0;
}
if (targetCount == 0) {
return fromIndex;
}
char first = target[targetOffset];
int max = sourceOffset + (sourceCount - targetCount);
for (int i = sourceOffset + fromIndex; i <= max; i++) {
/* Look for first character. */
if (source[i] != first) {
while (++i <= max && source[i] != first);
}
/* Found first character, now look at the rest of v2 */
if (i <= max) {
int j = i + 1;
int end = j + targetCount - 1;
for (int k = targetOffset + 1; j < end && source[j]
== target[k]; j++, k++);
if (j == end) {
/* Found whole string. */
return i - sourceOffset;
}
}
}
return -1;
}
static int indexOfB(char[] source, int sourceOffset, int sourceCount,
char[] target, int targetOffset, int targetCount,
int fromIndex) {
if (fromIndex >= sourceCount) {
return (targetCount == 0 ? sourceCount : -1);
}
if (fromIndex < 0) {
fromIndex = 0;
}
if (targetCount == 0) {
return fromIndex;
}
char first = target[targetOffset];
char second = 0;
if (targetCount != 1) {
second = target[targetOffset + 1];
}
int max = sourceOffset + (sourceCount - targetCount);
for (int i = sourceOffset + fromIndex; i <= max; i++) {
/* Look for first character. */
if (source[i] != first) {
while (++i <= max && source[i] != first);
}
if (targetCount == 1) {
return (i <= max) ? i - sourceOffset : -1;
}
/* Found first character, now look at the rest of v2 */
if (i <= max && source[i + 1] == second) {
int j = i + 2;
int end = i + targetCount;
for (int k = targetOffset + 2; j < end && source[j]
== target[k]; j++, k++);
if (j == end) {
/* Found whole string. */
return i - sourceOffset;
}
}
}
return -1;
}
}
More information about the core-libs-dev
mailing list