Does dividing an array into halfs improve performance or processing time?

Question

I'm curious about this.

I understand it will cost O(n) time to iterate through all the items in an array. Will dividing the array into half as shown below, improve the performance in any way?

final int[] array = new int[] {1, 2, 3, 4, 5, 6, 7};

for (int frontIndex = 0, rareIndex = array.length - 1; frontIndex <= array.length / 2; ++frontIndex, --rearIndex) {

  if (frontIndex != rearIndex) {
    int rearValue = array[rearIndex];
    System.out.println(rearValue);
  }

  int frontValue = array[frontIndex];
  System.out.println(frontValue);
}

It's still `O(n)`. OK, sure, it's `O(n/2)` but we still drop the constant from the big-O notation as we're only interested in the way it's affected by `n`. In this case, it's still linear growth. Whether or not the *runtime* is faster we cannot say exactly as this is too simple of an example. It's entirely possible that if you used a normal loop, the compiler produces a more efficient code. — VLAZ, Oct 12 '20 at 14:55
You are still doing the same amount of work, just visiting the elements in a different order. — 0x5453, Oct 12 '20 at 15:00
Consider that `O(n)` doesn't mean the algorithm will take `n` units of time to perform. It's just an order of the magnitude of the time it will take to perform an algorithm on `n` elements, for a very big `n`. — Federico klez Culloca, Oct 12 '20 at 15:08
Only way to _potentially_ make it faster would be to process the two halves **in parallel**. You'd have to program it specifically that way: Java doesn't do that for you for free. Also you'd have to run it on a multiprocessor system. And you'll only see the benefit if the system is willing to allocate two processors simultaneously to your program, which isn't necessarily guaranteed. — Kevin Anderson, Oct 12 '20 at 15:14
In fact, it's likely to _decrease_ performance if you do it like this (in a single thread) due to breaking cache locality. See for example https://stackoverflow.com/questions/12065774/why-does-cache-locality-matter-for-array-performance — k314159, Oct 12 '20 at 15:25

Stephen C · Accepted Answer · 2020-10-12T15:31:50.493

It is unlikely to make the code faster.

If you add up the number of increments, tests and array fetches in your version and compare them with equivalent counts in the simpler version of the code, I think that you will get the same numbers ... or close enough that it makes very little difference.
Your more complicated version of the code is likely to be harder for a JIT compiler to optimize. For example it is less likely for the JIT compiler to decide that it could unroll the loop.
It is possible that the different memory access pattern could lead to more cache misses, more pipeline stalls and therefore reduced performance.

Note that analysis of the above would need careful and detailed examination of the native code generated by the JIT compiler. Too much work.

^{I disagree with @VLAZ's comment that this is O(n/2) vs O(n). Firstly, they are the same thing. Secondly, it depends on what you count as a unit of computation. VLAZ seems to be counting loop iterations, but he is missing the fact that the loop body is doing more than twice the work as in the simple version.}

Next, this smells of premature optimization. Standard advice is to leave the optimization to the compiler. First get the code function complete and working. Then measure the performance. Only hand optimize your code if the measurement shows that you do have a performance problem. Then use a profiler to figure out the hotspots / performance bottlenecks. Then optimize the bottlenecks, and don't bother optimizing code that has minimal effect on performance. (Do the math!)

Finally, the only way to know for sure is to write a micro-benchmark to compare the performance of the two versions. If you are going to do that:

Don't put print statements in the loop. (The time taken to print N numbers is many orders of magnitude larger than the looping.)
Use an existing benchmarking framework like JMH.
Read: How do I write a correct micro-benchmark in Java? ... to avoid the embarrassing mistakes that people typically make when they doing this kind of thing for the first time.

I agree with you disagreement on what I said. I didn't phrase it properly - it's the loops done but not the actual work done. I was trying to emphasise that the number of loops isn't indicative for big-O notation. You can also search only part of the array and break out of the loop but it's still going to remain a `O(n)` operation. But yes, I should have clarified that it's also not `O(n/2)` in terms of array access, as it's still visiting everything in the array. — VLAZ, Oct 12 '20 at 15:21

Does dividing an array into halfs improve performance or processing time?

1 Answers1