String.indexOf optimization
Martin Buchholz
martinrb at google.com
Tue Apr 15 22:53:00 UTC 2014
Hi Ivan,
There's already an indexOf(int, int) that allows a user to explicitly
search for a char (or character).
Hotspot seems to have some intrinsification of String.indexOf, which
confuses me.
Hotspot seems the right place to provide more optimizations for this, since
there has been a fair amount of work creating high-performance low-level
implementations of this idea in C.
On Tue, Apr 15, 2014 at 10:13 AM, Ivan Gerasimov
<ivan.gerasimov at 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/
>
> 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