On Tue, Apr 15, 2014 at 10:13 AM, Ivan Gerasimov
<ivan.gerasi...@oracle.com <mailto:ivan.gerasi...@oracle.com>> wrote:
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/
<http://cr.openjdk.java.net/%7Eigerasim/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 <http://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));
}
@GenerateMicroBenchm
