RFR: 8254807: Optimize startsWith() for String.substring() [v5]

[Xin Liu]

On Wed, 18 Nov 2020 10:11:34 GMT, Xin Liu <xliu at openjdk.org> wrote:

>> hello, 
>> 
>> May I ping to review this patch?  
>> 
>> Many business-oriented Java applications manipulate strings a lot.  Comparing to arithmetic scalar, string as oop is more expensive.  furthermore, many string objects need to be allocated on heap, so they increase workload of GC.  
>> 
>> By analyzing the construction of string object, I found that one source is String.substring().  My target is to eliminate substring  as many as possible.  This is the first attempt for me to enable substring optimization. If it works out, I will apply the api-substitution approach on other APIs such as String.charAt, StringBuilder::append, and even String.split(). 
>> 
>> thanks you in advance.
>
> hi, Vladimir, 
> 
> Thank you for taking time to review it. 
> 
> I would like to call out that I plan to optimize substring().  My single aim to cut off a use of substring in this PR.
> This is a gateway patch. I plan to apply a series of API substitutions for substrings. eg. StringBuilder::append, String.split and String.charAt etc. 
> 
>> _Mailing list message from [Vladimir Ivanov](mailto:vladimir.x.ivanov at oracle.com) on [hotspot-compiler-dev](mailto:hotspot-compiler-dev at openjdk.java.net):_
>> 
>> Hi Xin,
>> 
>> > the optimization transforms code from s=substring(base, beg, end); s.startsWith(prefix)
>> > to substring(base, beg, end) | base.startsWith(prefix, beg).
>> > it reduces an use of substring. hopefully c2 optimizer can remove the used substring()
>> 
>> It would be very helpful to see a more elaborate description of intended
>> behavior to understand better what is the desired goal of the enhancement.
>> 
>> Though it looks attractive to address the problem in the JIT-compiler,
>> it poses some new challenges which makes proposed approach questionable.
>> I understand your desire to rely on existing String-related
>> optimizations, but coalescing multiple concatenations differs
>> significantly from your case.
>> 
>> Some of the concerns/questions I had while briefly looking through the
>> patch:
>> 
>> - You introduce a call to a method (String::startsWith(String, int))
>> which is not present in bytecode. It means (unless the method is called
>> from different places) there won't be any profiling info present, and
>> even if there is, it is unrelated to the call site being compiled. If
>> the code is recompiled at some point (e.g., it hits an uncommon trap in
>> startsWith(String,int) overload), there won't be any re-profiling
>> happening. So, it can hit the very same condition on the consequent
>> recompilations.
>> 
> Thank you to raise this! I didn't consider the profiling data before. 
> it is an issue. Maybe it can explain why I observe only 80% performance of hand-craft code. 
> 
> TBH, I haven't had a clear and solid answer for it yet. 
> The transformation actually won't alter control-flow. Perhaps, I can find a way to amend methoddata from the old method.
> Or, is that possible I request to reprofile it after I modify some bytecodes?
> 
>> - "s.startsWith(prefix)" call node is reused and rewired to call
>> unrelated method "base.startsWith(prefix, beg)". Will the new target
>> method be taken into account during inlining? I would be much more
>> comfortable seeing fresh call populated using standard process
>> (involving CallGenerators et al) which then substitutes the original
>> node. That way you make it less fragile longer term.
>> 
> I can make that happen. actually, I generated a brand-new call-generator in early revision of this patch. 
> I drop it because it requires more code.
> 
>> - "hopefully c2 optimizer can remove the used substring()"
>> If everything is inlined in the end, it can happen, but it's fragile.
>> Instead, you could teach C2 that the method is "pure" (no interesting
>> side effects to care about) and cut the call early. It already happens
>> for boxing methods (see LateInlineCallGenerator::_is_pure_call for
>> details).
>> 
> I do have the exact logic in early revision. I remarked substring() as late-inlining candidate and pure. 
> I delete it because I found substring() is "always" inlined and c2 optimizer can do the deadcode elimination job if nobody uses it. 
> I understand your concern.  I can improve it in the future. 
> 
>> Overall, if you want to keep the enhancement C2-specific, I'd suggest to
>> look into intrinsifying String::startsWith(String, int) and not relying
>> on its bytecodes at all. That way you would avoid fighting against the
>> rest of the JVM in some situations.
>> 
> Because this optimization isn't one-off thing for startsWith, I can't intrinsify it. 
> I'd like to explore an extensible approach.
> 
>> Best regards,
>> Vladimir Ivanov

Vladimir is correct. I found one potential issue is that I can't inline "startsWith(String, int)" which is the overload of original "startsWith". _string_late_inlines still records the old callGenerator which associates with old callNode. I need to update the record and make sure the new callnode is considered in inline_string_calls(). working on it.

-------------

PR: https://git.openjdk.java.net/jdk/pull/974