String.indexOf optimization

[Zoltan Sziladi]

Martin, yes, we're talking about that method.

Other than tightening that code some... if we find some algorithm that
outperforms the naive implementation under certain conditions (let's say
when the searched pattern is longer than 10 characters), would it be worth
including it as a special case? (For example naive would run normally but
if pattern is longer than 10 characters then the other algorithm would
run). Or do you think that would just make the code too complicated without
enough benefits?

Regards,
Zoltan

On Mon, Jan 12, 2015 at 12:11 PM, Martin Buchholz <martinrb at google.com>
wrote:

> If there's a clean improvement in the java code, it's worth putting in.
> You can try benchmarking with -Xint.
> Are we talking about this method?
>
>     static int indexOf(char[] source, int sourceOffset, int sourceCount,
>             char[] target, int targetOffset, int targetCount,
>             int fromIndex) {
>
> It does look like we can tighten the code up a little...
>
>
> On Thu, Jan 8, 2015 at 3:05 PM, Zoltan Sziladi <kissziszi at gmail.com>
> wrote:
>
>> Thanks for the info.
>> So that basically means we have 2 implementations of indexOf currently,
>> one
>> is in HotSpot, the other is in the JDK itself, which rarely gets executed.
>> Aside from this later fact, isn't it still worth improving the JDK
>> implementation if it is possible? I know that the intrinsified method gets
>> executed most of the time, but still, if we can improve the JDK
>> implementation also, why not? I don't know much about other JVMs but maybe
>> a few don't intrinsify it?
>>
>> Is there any existing test suite which is considered conclusive enough
>> that
>> if an implementation beats the naive algorithm in those testcases then it
>> could be considered as a replacement in the JDK?
>>
>> Regards,
>> Zoltan
>>
>>
>> On Thu, Jan 8, 2015 at 12:42 PM, Vitaly Davidovich <vitalyd at gmail.com>
>> wrote:
>>
>> > The java impl you saw would be called by (a) interpreter, (b) if you
>> > explicitly disable intrinsification of this function, or (c) some other
>> JVM
>> > that doesn't intrinsify this method (or any method).
>> >
>> > People don't usually disable intrinsics; if they do, it's because they
>> hit
>> > some JIT bug and may disable it.
>> >
>> > On Thu, Jan 8, 2015 at 3:34 PM, Zoltan Sziladi <kissziszi at gmail.com>
>> > wrote:
>> >
>> >> Hi,
>> >>
>> >> Thanks everyone for all the info.
>> >> So, just to go step by step in understanding this.
>> >> Andrew said HotSpot would ignore my implementation. So why is there an
>> >> implementation of indexOf at all in the JDK, if that's not the code
>> that's
>> >> executed? Is it just a default fallback? When is the indexOf function
>> not
>> >> intrinsified? When do people usually disable intrinsification?
>> >> Sorry if these are newbie questions, I'm new to this part of Java.
>> >>
>> >> Regards,
>> >> Zoltan
>> >>
>> >> On Tue, Jan 6, 2015 at 1:28 AM, Andrew Haley <aph at redhat.com> wrote:
>> >>
>> >> > Hi,
>> >> >
>> >> > On 05/01/15 18:59, Zoltan Sziladi wrote:
>> >> >
>> >> > > This discussion was a long time ago, I was just reading through it
>> to
>> >> > check
>> >> > > again what was the last state of the discussion about the
>> >> String.indexOf.
>> >> > > There is one part which I still do not understand, hopefully
>> someone
>> >> > could
>> >> > > shed some light on it. A few emails ago Martin mentioned
>> >> > >
>> >> > > "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."
>> >> > >
>> >> > > Then Ivan asked what that actually meant, whether hotspot actually
>> >> > replaced
>> >> > > the jdk implementation with a low level optimized C implementation,
>> >> but I
>> >> > > never saw an answer to that.
>> >> >
>> >> > You can have a look at an implementation of
>> >> MacroAssembler::string_indexof
>> >> > in
>> >> >
>> >> >
>> >> >
>> >>
>> http://hg.openjdk.java.net/jdk9/jdk9/hotspot/file/b6b89b8f8531/src/cpu/x86/vm/macroAssembler_x86.cpp
>> >> >
>> >> > > Can someone please explain this? If we somehow found an algorithm
>> that
>> >> > beat
>> >> > > the naive implementation in the average case, would it be possible
>> to
>> >> > just
>> >> > > implement it in the JDK?
>> >> >
>> >> > No, because HotSpot would ignore it.  Any speed improvements have to
>> be
>> >> > done in the architecture-dependent files.
>> >> >
>> >> > Andrew.
>> >> >
>> >> >
>> >>
>> >
>> >
>>
>
>