String.indexOf optimization (original) (raw)

Ivan Gerasimov ivan.gerasimov at oracle.com
Fri Apr 18 08:32:22 UTC 2014

On 16.04.2014 2:53, Martin Buchholz wrote:

Hi Ivan,

There's already an indexOf(int, int) that allows a user to explicitly search for a char (or character). Sure. What I meant was not to introduce a special function for searching a single character, but to restrict the general case loop to search for a substring of at least 2 characters. Having this condition hold, we can enter the loop only when two starting characters match, and this can save us a few nanoseconds in many cases.

Hotspot seems to have some intrinsification of String.indexOf, which confuses me.

Does it mean that that the java implementation of indexOf is never compiled? When hotspot replaces the jdk implementation with its own one? Is it ever worth to try to optimize the java implementation?

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. The hotspot's intrinsic is already optimized for searching substrings of different length.

Sincerely yours, Ivan

On Tue, Apr 15, 2014 at 10:13 AM, Ivan Gerasimov <ivan.gerasimov at oracle.com <mailto: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/ <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.benchIndexOf1A avgt 1 20 5 704.739 9.104 nsec/op o.b.IndexOfBench.benchIndexOf1B avgt 1 20 5 573.8799.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.0626.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.1789.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.6031.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.1771.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.33810.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.66924.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 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)); } @GenerateMicroBenchm

More information about the core-libs-dev mailing list