9

Why is indexOf significantly faster than contains if the latter is merely a wrapper of the first one?

Code from the Java API:

public boolean contains(CharSequence s) {
     return indexOf(s.toString()) > -1;
}

The chosen answer in this thread shows a short test, which shows the difference.

The chosen answer in this thread states that the overhead of the additional method call does not matter. So, why the difference?

Please read my edit: Almost everyone is saying the micro-benchmark is flawed. Strange thing is, it reflects exactly my use-case.

Actually, I was not doubting that indexOf is faster than contains (for my use-case) in the first place, I just wanted to know why.

My intention was never to write a benchmark! I was just searching for the most-efficient way to test if a string contains another one (for my application which has nothing to do with a benchmark but a 'real-life situation').

Community
  • 1
  • 1
Willi Mentzel
  • 27,862
  • 20
  • 113
  • 121

3 Answers3

17

The contains method is implemented as:

public boolean contains(CharSequence s) {
    return indexOf(s.toString()) > -1;
}

Which means that it may be slower if CharSequence s is not a java.lang.String because calling s.toString() will result in the allocation and initialization of a new string instance. If s is a string - then there should not be any measurable difference.

PS: The test from here is flawed: https://stackoverflow.com/a/18340277/2588800 Java initially execute in "interpreted" mode, which is quite slow, and when it detects that a piece of codes gets executed a lot of times it compiles it to native code in order to speed it up (read about JIT compilation).

As you can see contains internally calls indexOf, which means that indexOf eventually will get compiled to native. So when he tests the indexOf (notice that he tests it after contains) it might have already been compiled to native code. And that's the reason for the time difference. Try to reverse the order of that tests - first test indexOf and then contains and I bet you'll see just the opposite results.

JMH to the rescue

Benchmark                            Mode  Cnt   Score   Error   Units
StringSearchBenchmark.testContains  thrpt  500  22,071 ± 0,269  ops/us
StringSearchBenchmark.testIndexOf   thrpt  500  22,654 ± 0,233  ops/us

As you can see the difference is negligible and might be casued by the additional method calls (indexOf() + toString()) and load on the system.

Source-Code:

@Fork(1)
@State(Scope.Benchmark)
@OutputTimeUnit(TimeUnit.MICROSECONDS)
@Measurement(iterations = 500, time = 50, timeUnit = TimeUnit.MILLISECONDS)
@Warmup(iterations = 10)
@BenchmarkMode(Mode.Throughput)
public class StringSearchBenchmark {
    private static final String STATE = "absdefghijklmnopqrstuvwxyzabsdefghijklmnopqrstuvwxyzabsdefghijklmnopqrstuvwxyzabsdefghijklmnopqrstuvwxyz";
    private static final String SEARCH_TERM = "abcd";

    @Benchmark
    public void testContains(Blackhole sink) {
        sink.consume(STATE.contains(SEARCH_TERM));
    }

    @Benchmark
    public void testIndexOf(Blackhole sink) {
        sink.consume(STATE.indexOf(SEARCH_TERM));
    }
}
Community
  • 1
  • 1
Svetlin Zarev
  • 14,713
  • 4
  • 53
  • 82
  • Even if I switch the order of indexOf and contains, indexOf is still faster. In the benchmark i linked, the passed value is also alreday a string! Or is "test" internally a CharSequence? – Willi Mentzel Aug 19 '16 at 11:03
  • I modified it a bit and I can see that contains is faster :) Which obviously cant be true as it internally calls indexOf. You cant make conclusions based on flawed micro benchmarks. Her eis the gist: https://gist.github.com/SvetlinZarev/ff6d64306343501427be5f266f0329d6 – Svetlin Zarev Aug 19 '16 at 11:24
  • may the benchmark flawed or not... it is exaclty the use-case that i need for my application :D – Willi Mentzel Aug 19 '16 at 11:25
  • Then make a proper micro benchmark. Take a look at JMH and the benchmark from my answer. – Svetlin Zarev Aug 19 '16 at 11:26
  • No! the benchmark is 1:1 what I need in my application (reflects the use-case). My application is NOT about writing a benchmark, my appliation is about testing a bunch of strings for a substring! – Willi Mentzel Aug 19 '16 at 11:29
  • But that benchmark does not measure anything. The results are without meaning. – Svetlin Zarev Aug 19 '16 at 11:42
  • I don't see why :( my application works the same. iterate over an array and test elements for substring occurence. pls explain – Willi Mentzel Aug 19 '16 at 11:47
  • @SventlinZarev Pls explain further! Like I said the benchmark matches my real life use case... how can it not be accurate? I understand everythign else (interpreted.. native), but I don't have the choice in my program either. the jvm does what it wants. – Willi Mentzel Aug 25 '16 at 08:35
  • As explained in the answer, Java does a huge amount of stuff on startup, and optimises the code over time (e.g. compiling to native). Attempting to run a benchmark test without warming up the JVM means that whichever test is first will run slower. If you re-order the tests, you'll get a different answer! I don't see how that's helpful to you. – ipsi Aug 25 '16 at 09:30
  • I don't know how to explain it. That sample on one hand does not perform warmup. Also it does not take into account GC, JIT effects, etc. It just measures something, but no one can tell what exactly it measures. Also I gave a you a slightly different version of that test that shows the opposite results. This proves that this test measures **nothing**. It's difficult to perform correct micro benchmarks and I already gave you one that shows that there is no difference between the execution speed of both methods. Even more - if look at the source code, you'll see that they are equivalent – Svetlin Zarev Aug 25 '16 at 09:31
  • @ipsi If I only change the order: they still have a different execution time on some runs, so it cannot be reproduced really. even with warmup – Willi Mentzel Aug 26 '16 at 11:24
4

As others have said, the benchmark was heavily flawed - performance testing of Java code does not work like that - you must warm it up to ensure that all classes have been loaded and parsed, that all objects have been loaded into memory, and that any compiling down to native code, e.g. via HotSpot, has been done. A naïve benchmark where you just run the code once in the main method is not really going to fly. A much better choice is to use something like JMH. Given the following test:

package com.stackoverflow.example;

import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.runner.Runner;
import org.openjdk.jmh.runner.RunnerException;
import org.openjdk.jmh.runner.options.Options;
import org.openjdk.jmh.runner.options.OptionsBuilder;

@OutputTimeUnit(TimeUnit.MICROSECONDS)
@Measurement(time = 250, timeUnit = TimeUnit.MILLISECONDS)    
public class MyBenchmark {

    private static final String[] names = new String[]{"jack", "jackson", "jason", "jadifu"};

    public static void main(String[] args) throws RunnerException {
        Options opt = new OptionsBuilder()
                .include(MyBenchmark.class.getSimpleName())
                .forks(1)
                .build();

        new Runner(opt).run();
    }

    @Benchmark
    public void contains() {
        names[0].contains("ja");
    }

    @Benchmark
    public void containsExplicit() {
        names[0].indexOf("ja".toString());
    }

    @Benchmark
    public void indexOf() {
        names[0].indexOf("ja");
    }

    @Benchmark
    public void matches() {
        names[0].matches(".*ja.*");
    }
}

I get the following results:

Benchmark                      Mode  Cnt     Score    Error   Units
MyBenchmark.contains          thrpt   20   219.770 ±  2.032  ops/us
MyBenchmark.containsExplicit  thrpt   20  1820.024 ± 20.583  ops/us
MyBenchmark.indexOf           thrpt   20  1828.234 ± 18.744  ops/us
MyBenchmark.matches           thrpt   20     3.933 ±  0.052  ops/us

Now, that's fairly interesting, as it still suggests that contains is significantly slower than indexOf. However, if I change the test up, very slightly, to the following:

@Benchmark
public void contains() {
    assert names[0].contains("ja");
}

@Benchmark
public void containsExplicit() {
    assert names[0].indexOf("ja".toString()) == 0;
}

@Benchmark
public void indexOf() {
    assert names[0].indexOf("ja") == 0;
}

@Benchmark
public void matches() {
   assert names[0].matches(".*ja.*");
}

I get the following results:

Benchmark                      Mode  Cnt    Score   Error   Units
MyBenchmark.contains          thrpt   20  220.480 ± 1.266  ops/us
MyBenchmark.containsExplicit  thrpt   20  219.962 ± 2.329  ops/us
MyBenchmark.indexOf           thrpt   20  219.706 ± 2.401  ops/us
MyBenchmark.matches           thrpt   20    3.766 ± 0.026  ops/us

In this, we're getting the same result for contains, but indexOf has slowed down to match contains. That's a very interesting result. Why is this happening?

Probably due to HotSpot recognising that the result of the indexOf call is never inspected, and since it's taking a final class (String), HotSpot is likely able to guarantee that there are no side effects to the call. So if we're not looking at the result and there are no side effects to the call, why are we making it? HotSpot is able to realise that a method call is pointless, and remove it altogether, which could be what's happening here. It would certainly explain the order of magnitude difference.

Why doesn't this work for contains, though? I can only assume that it's because contains accepts a CharSequence, not a String, which is an abstract class, and that's just enough to prevent HotSpot from optimising the method call away.

This also indicates that micro-benchmarks are hard in Java - there is a lot going on beneath the surface to optimise your running code, and a few shortcuts can result in extremely inaccurate benchmarks.

ipsi
  • 2,049
  • 18
  • 23
  • 1
    One should not use cycles within the @Benchmark. Remove the `for` cycles and test again. Also `second` is a too big time frame for such a test - switch to microseconds or milliseconds. Also the JVM might ignore the asserts from the second fragment and hence optimize away the whole loop, which is what;s happening in the first fragment – Svetlin Zarev Aug 19 '16 at 10:19
  • I've made the changes you suggested. It definitely makes it easier to read. I'm pretty sure the JVM is not ignoring the assert. You have to run with `-ea`, but otherwise `assert` seems to force HotSpot to not optimise away the whole call. – ipsi Aug 19 '16 at 10:29
  • @ipsi Really interesting! But why indexOf("ja".toString())... "ja" is a String already? – Willi Mentzel Aug 25 '16 at 08:37
  • It's how the contains method works internally, but I suspect it's not doing much here. Either the compiler, or HotSpot, will optimise that part of the call away. Would have to fiddle with the code a bit more to prevent that optimisation. – ipsi Aug 25 '16 at 09:31
1

indexOf is sample of intrinsic method in Hotspot JVM. It means that java code from java.lang.String is not used at all for this method. There is special native version of this method. You can find list of such methods here: do_intrinsic(_indexOf

sibnick
  • 3,995
  • 20
  • 20