Is ArrayList.size() method cached?

Question

I was wondering, is the size() method that you can call on a existing ArrayList<T> cached? Or is it preferable in performance critical code that I just store the size() in a local int?

I would expect that it is indeed cached, when you don't add/remove items between calls to size().

Am I right?

update
I am not talking about inlining or such things. I just want to know if the method size() itself caches the value internally, or that it dynamically computes every time when called.

Answer 1

The obvious implementation of ArrayList would be to store the size internally in a field. I would be very surprised if it ever had to be computed, even after resizing.

Answer 2

Why would it need to be? ArrayList implements a List interface that is backed by an array, after all.

I would assume it to just have a size member, that is incremented when you insert things and decremented when you remove, and then it just returns that.

I haven't looked at more than the API docs now, though.

Answer 3

I don't think I'd say it's "cached" as such - but it's just stored in a field, so it's fast enough to call frequently.

The Sun JDK implementation of size() is just:

public int size() {
    return size;
}

Answer 4

I don't know the answer for sure, but my guess would be: no. There is no way for a Java compiler, short of special casing ArrayList, to know that the functions you invoke will be non-mutating and that, as a result, the invocation of size() should return the same value. Therefore, I find it highly unlikely that a Java compiler will factor out repeated calls to size() and store them in a temporary value. If you need that level of optimization then you should store the value in a local variable yourself. Otherwise, yes, you will pay for the function invocation overhead associated with calling the size() method. Note, though, that the size() method is O(1) for an ArrayList (though the function call overhead is pretty hefty). Personally, I would factor out any calls to size() from loops and manually store them in a local where applicable.

Edit
Even though such an optimization cannot be performed by a Java compiler, it has been aptly pointed out that the JIT can inline the implementation of ArrayList.size() such that it only costs the same as a field access, without any additional method call overhead, so in effect the costs are negligible, although you might still save slightly by manually saving in a temporary (which could potentially eliminate a memory lookup and instead serve the variable out of a CPU register).

Answer 5

Yes.

A quick look at the Java source would tell you the answer.

Answer 6

This is the implementation in OpenJDK version:

/**
 * Returns the number of elements in this list.
 *
 * @return the number of elements in this list
 */
public int size() {
    return size;
}

So it's as good as a method call is going to get. It's not very likely that HotSpot caches the value returned by this method, so if you're really THAT concerned, you can cache it yourself. Unless your profiling has shown that this is a bottleneck, though (not very likely), you should just concern yourself with readability rather than whether a simple method call that returns the value of a field is cached or not.

Answer 7

If caching the result of the size() method would noticeably improve performance (which it sometimes does - I regularly see ArrayList.size() as the top compiled method in my -Xprof output) then consider converting the whole list to an array for an even greater speedup.

Here's one trick that can work if you iterate over the list regularly but only rarely update it:

class FooProcessor {

    private Foo[] fooArray = null;
    private List<Foo> fooList = new ArrayList<Foo>();

    public void addFoo(Foo foo) {
       fooList.add(foo);
       fooArray = null;
    }

    public void processAllFoos() {
        Foo[] foos = getFooArray();
        for (int i = 0; i < foos.length; ++ i) {
            process(foos[i]);
        }
    }

    private void getFooArray() {
        if (fooArray == null) {
            Foo[] tmpArray = new Foo[fooList.size()];
            fooArray = fooList.toArray(tmpArray);
        }
        return fooArray;
    }

}