String.indexOf optimization (original) (raw)

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.benchIndexOf1A avgt 1 20 5 704.739 9.104 nsec/op o.b.IndexOfBench.benchIndexOf1B avgt 1 20 5 * 573.879* 9.820 nsec/op o.b.IndexOfBench.benchIndexOf2A avgt 1 20 5 668.455 9.882 nsec/op o.b.IndexOfBench.benchIndexOf2B avgt 1 20 5 476.062 6.063 nsec/op o.b.IndexOfBench.benchIndexOf3A avgt 1 20 5 155.227 1.796 nsec/op o.b.IndexOfBench.benchIndexOf3B avgt 1 20 5 * 152.850 * 1.512 nsec/op o.b.IndexOfBench.benchIndexOf4A avgt 1 20 5 656.183 5.904 nsec/op o.b.IndexOfBench.benchIndexOf4B avgt 1 20 5 515.178 9.107 nsec/op o.b.IndexOfBench.benchIndexOf5A avgt 1 20 5 140.609 7.305 nsec/op o.b.IndexOfBench.benchIndexOf5B avgt 1 20 5 129.603 1.654 nsec/op o.b.IndexOfBench.benchIndexOf6A avgt 1 20 5 127.713 1.497 nsec/op o.b.IndexOfBench.benchIndexOf6B avgt 1 20 5 122.177 1.186 nsec/op o.b.IndexOfBench.benchIndexOf7A avgt 1 20 5 430.148 4.875 nsec/op o.b.IndexOfBench.benchIndexOf7B avgt 1 20 5 * 387.338* 10.904 nsec/op o.b.IndexOfBench.benchIndexOf8A avgt 1 20 5 2064.563 28.885 nsec/op o.b.IndexOfBench.benchIndexOf8B 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 benchIndexOf1A(BlackHole bh) { bh.consume(indexOfA(source1, 0, source1.length, target1, 0, target1.length, 0)); } @GenerateMicroBenchmark public void benchIndexOf1B(BlackHole bh) { bh.consume(indexOfB(source1, 0, source1.length, target1, 0, target1.length, 0)); } @GenerateMicroBenchmark public void benchIndexOf2A(BlackHole bh) { bh.consume(indexOfA(source2, 0, source2.length, target1, 0, target1.length, 0)); } @GenerateMicroBenchmark public void benchIndexOf2B(BlackHole bh) { bh.consume(indexOfB(source2, 0, source2.length, target1, 0, target1.length, 0)); } @GenerateMicroBenchmark public void benchIndexOf3A(BlackHole bh) { bh.consume(indexOfA(source3, 0, source3.length, target1, 0, target1.length, 0)); } @GenerateMicroBenchmark public void benchIndexOf3B(BlackHole bh) { bh.consume(indexOfB(source3, 0, source3.length, target1, 0, target1.length, 0)); } @GenerateMicroBenchmark public void benchIndexOf4A(BlackHole bh) { bh.consume(indexOfA(source4, 0, source4.length, target2, 0, target2.length, 0)); } @GenerateMicroBenchmark public void benchIndexOf4B(BlackHole bh) { bh.consume(indexOfB(source4, 0, source4.length, target2, 0, target2.length, 0)); } @GenerateMicroBenchmark public void benchIndexOf5A(BlackHole bh) { bh.consume(indexOfA(source5, 0, source5.length, target2, 0, target2.length, 0)); } @GenerateMicroBenchmark public void benchIndexOf5B(BlackHole bh) { bh.consume(indexOfB(source5, 0, source5.length, target2, 0, target2.length, 0)); } @GenerateMicroBenchmark public void benchIndexOf6A(BlackHole bh) { bh.consume(indexOfA(source6, 0, source6.length, target3, 0, target3.length, 0)); } @GenerateMicroBenchmark public void benchIndexOf6B(BlackHole bh) { bh.consume(indexOfB(source6, 0, source6.length, target3, 0, target3.length, 0)); } @GenerateMicroBenchmark public void benchIndexOf7A(BlackHole bh) { bh.consume(indexOfA(source7, 0, source7.length, target4, 0, target4.length, 0)); } @GenerateMicroBenchmark public void benchIndexOf7B(BlackHole bh) { bh.consume(indexOfB(source7, 0, source7.length, target4, 0, target4.length, 0)); } @GenerateMicroBenchmark public void benchIndexOf8A(BlackHole bh) { bh.consume(indexOfA(source8, 0, source8.length, target5, 0, target5.length, 0)); } @GenerateMicroBenchmark public void benchIndexOf8B(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