0

s is a string with a length of up to 100000 characters.

When I run the first loop:

for (int i = 0; i + 9 < s.length(); i++)

I get a runtime of 14ms for a test set.

When I run the second loop instead of the first:

for (int i = 0; i < s.length() - 9; i++)

it consistently takes about 2 times more (28ms) than the first loop for the same test set.

Does the structure of the first loop allow for some kind of optimization?

rahs
  • 1,759
  • 2
  • 15
  • 31
  • 5
    Also, are you sure you found actual performance differences and not just tested incorrectly? This might help to build a proper setup: [How do I write a correct micro-benchmark in Java?](//stackoverflow.com/q/504103) – Tom Dec 17 '20 at 05:13
  • 1
    @JohannesKuhn I came across this question on a competitive coding website so my original intention wasn't to find a good benchmark. I was more specifically looking to see if there was some optimization difference that I wasn't seeing. However, I would think Stephen's answer addresses that. Looking at the answers, I see there is likely no obvious optimization difference in these loops, so my question is not relevant anymore and I wouldn't mind if it were closed. – rahs Dec 17 '20 at 20:12

2 Answers2

4

First of all, there is a strong possibility that what you think you are seeing is actually due to a badly written benchmark. I strongly advise you to carefully read following Q&A and follow the advice therein:

Secondly, what you are saying doesn't correspond to my intuition. However, if the effect is real, one would need to do an in-depth analysis of the native code produced by the JIT compiler to understand the reason for the difference.

Finally, this smells of "premature optimization". As a general rule, the JIT compiler can do a better (more consistent, more reliable) job of optimizing than a human can. If there are simple optimizations like the one that you are trying, the JIT compiler will find them. Micro-optimization like this is generally a waste of (your) time.

So if you are going to try optimize, then you need to do it Scientifically.

  1. Get the application / library working first.
  2. Write a realistic benchmark for the code. One that matches how the code is likely to be used for real.
  3. Set yourself some measurable performance goals. ("As fast as possible" is not measurable).
  4. Run the benchmark to see if you already meet the goals. If yes, don't waste any further time on optimizing.
  5. Now run the benchmark using a performance profiler to identify the performance hot spots; i.e. the methods, etc that the application spends most of its time executing.
  6. Pick one hotspot, and look for possible ways to make it faster. Implement on possible optimization ... and run the benchmarks again to see if it improved things.
  7. Repeat steps 4 through 6 until you either meet the performance goal or run out of hotspots that can be optimized.
Stephen C
  • 698,415
  • 94
  • 811
  • 1,216
  • I don't think he/she is trying to optimize an existing code. This looks more like he/she is curious in what is actually happening. All I could say is that different JIT can do different optimization so it's not really useful to study them. – Jai Dec 17 '20 at 05:43
  • 1
    Well, if this is purely "curiosity driven", the OP really needs to learn how to do micro-benchmarking the right way. – Stephen C Dec 17 '20 at 05:46
0

I do not think that the preformance problem with this for...loop definition. To check it, you have to provide the full compilable code; to check every aspects.

But you can easily check the answer moving all calculatio to the beginning:

for (int = 0, total = s.length() - 9; i < total; i++) {
    // ...
}

P.S. for (A; B; C) where A is calculated only once at the beginning of the loop; B and C are calculated on each loop iteration.

Oleg Cherednik
  • 17,377
  • 4
  • 21
  • 35