0

I have seen people say to cache the values of size for a list or length for an array when iterating, to save the time of checking the length/size over and over again.

So

for (int i = 0; i < someArr.length; i++) // do stuff
for (int i = 0; i < someList.size(); i++) // do stuff

Would be turned into

for (int i = 0, length = someArr.length; i < length; i++) // do stuff
for (int i = 0, size = someList.size(); i < size; i++) // do stuff

But since Array#length isn't a method, just a field, shouldn't it not have any difference? And if using an ArrayList, size() is just a getter so shouldn't that also be the same either way?

Scrapper142
  • 566
  • 1
  • 3
  • 12
  • 3
    I think the performance loss is negligible, but I would love an explaination tho – Aditya Arora Jan 28 '22 at 04:09
  • There are many implementations of List. How long would `size()` take if the List is a [LinkedList](https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/LinkedList.html) containing thousands (or millions) of elements? – VGR Jan 28 '22 at 05:36
  • 1
    @VGR you wouldn't want to iterate a LinkedList this way in the first place. What would it do with `i`? Traverse the entire list up to `i` on each iteration? – Tim Moore Jan 28 '22 at 10:59
  • Does this answer your question? [What is the Cost of Calling array.length](https://stackoverflow.com/questions/1208320/what-is-the-cost-of-calling-array-length) – Tim Moore Jan 28 '22 at 11:00
  • @TimMoore Agreed, it’s a good argument for using a for-each loop. – VGR Jan 28 '22 at 12:32
  • 1
    @VGR `LinkedList` stores the size in a field, just like `ArrayList`. So the `size()` method is not the problem when iterating over `LinkedList` this way… – Holger Feb 11 '22 at 13:04
  • 1
    @user16320675 `array.length` never changes. It looks like a field access, but in reality, it’s not. There’s a dedicated bytecode instruction, `arraylength` for getting the length but no way to change to change an array length at all. – Holger Feb 11 '22 at 13:06
  • 1
    @user16320675 if `someArr` changes, you *want* use the changed `someArr.length`, as only using the corresponding length guarantees that you are staying within the bounds. And this has a true impact on the optimizer, as this makes the difference between generating extra code for bounds checks or relying on the known invariant that the loop never exceeds the bounds. Which implies that it doesn’t matter whether you use `length = someArr.length` or access `someArr.length` each time; what matters, is whether the JIT/HotSpot optimizer can prove that `someArr` never changes, in either case. – Holger Feb 11 '22 at 13:14
  • isn't accessing a local length variable also a field fetch? – Scrapper142 Feb 11 '22 at 18:03

2 Answers2

3

It is possible the JIT compiler will do some of those optimizations for itself. Hence, doing the optimizations by hand may be a complete waste of time.

It is also possible (indeed likely) that the performance benefit you are going to get from hand optimizing those loops is too small to be worth the effort. Think of it this way:

  • Most of the statements in a typical program are only executed rarely
  • Most loops will execute in a few microseconds or less.
  • Hand optimizing a program takes in the order of minutes or hours of developer time.
  • If you spend minutes to get a execution speedup that is measured in microseconds, you are probably wasting your time. Even thinking about it too long is wasting time.

The corollary is that:

  • You should benchmark your code to decide whether you need to optimize it.
  • You should profile your code to figure out which parts of your code is worth spending optimization effort on.
  • You should set (realistic) performance goals, and stop optimization when you reach those goals.

Having said all of that:

  • theArr.length is very fast, probably just a couple of machine instructions
  • theList.size() will probably also be very fast, though it depends on what List class you are using.
  • For an ArrayList the size() call is probably a method call + a field fetch versus a field fetch for length.
  • For an ArrayList the size() call is likely to be inlined by the JIT compiler ... assuming that the JIT compiler can figure that out.
  • The JIT compiler should be able to hoist the length fetch out of the loop. It can probably deduce that it doesn't change in the loop.
  • The JIT compiler might be able to hoist the size() call, but it will be harder for it to deduce that the size doesn't change.

What this means is that if you do hand optimize those two examples, you will most likely get negligible performance benefit.

Stephen C
  • 698,415
  • 94
  • 811
  • 1,216
1

In general the loss is negligible. Even a LinkedList.size() will use a stored count, and not iterate over all nodes.

For large sizes you may assume the conversion to machine code may catch up, and optimize it oneself.

If inside the loop the size is changed (delete/insert) the size variable must be changed too, which gives us even less solid code.

The best would be to use a for-each

for (Bar bar: bars) { ... }

You might also use the somewhat more costing Stream:

barList.forEach(bar -> ...);
Stream.of(barArray).forEach(bar -> ...);

Streams can be executed in parallel.

barList.parallelStream().forEach(bar -> ...);

And last but not least you may use standard java code for simple loops:

Arrays.setAll(barArray, i -> ...);

We are talking here about micro-optimisations. I would go for elegance.

Most often the problem is the used algorithm & datastructurs. List is notorious, as everything can be a List. However Set or Map often provide much higher power/expressiveness.

If a complex piece of software is slow, profile the application. Check the break lines: java collections versus database queries, file parsing.

Joop Eggen
  • 107,315
  • 7
  • 83
  • 138