Why is list.size()>0 slower than list.isEmpty() in Java?

Question

Why is list.size()>0 slower than list.isEmpty() in Java? On other words why isEmpty() is preferable over size()>0?

When I look at the implementation in ArrayList, then it looks like the speed should be the same:

ArrayList.size()

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

ArrayList.isEmpty()

    /**
     * Returns <tt>true</tt> if this list contains no elements.
     *
     * @return <tt>true</tt> if this list contains no elements
     */
    public boolean isEmpty() {
        return size == 0;
     }

If we just write a simple program to get the time take by both the methods, that case size() will take more isEmpty() in all cases, why this so?

Here is my TestCode;

import java.util.List;
import java.util.Vector;

public class Main {
    public static void main(String[] args) {
        List l=new Vector();
        int i=0;
        for(i=0;i<10000;i++){
            l.add(new Integer(i).toString());
        }
        System.out.println(i);
        Long sTime=System.nanoTime();
        l.size();
        Long eTime=System.nanoTime();
        l.isEmpty();
        Long eeTime=System.nanoTime();
        System.out.println(eTime-sTime);
        System.out.println(eeTime-eTime);
    }
}

Here eTime-sTime>eeTime-eTime in all cases. Why?

Answer 1

Counting items in a linked list can be very slow.

Answer 2

For ArrayLists, yes - you're right that the operations take (roughly) the same time.

For other implementations of list - naive linked lists*, for example - counting the size might take a very long time, while you only actually care whether it's greater than zero.

So if you absolutely know that the list is an implementation of ArrayList and will never ever change then it doesn't really matter; but:

1. this is bad programming practice anyway to tie yourself down to a specific implementation.
2. If things change a few years down the line with code restructuring, testing will show that "it works" but things are running less efficiently than before
3. Even in the best case, size() == 0 is still not faster than isEmpty(), so there's no compelling reason to ever use the former.
4. isEmpty is a clearer definition of what it is you actually care about and are testing, and so makes your code a bit more easily understandable.

(Also, I'd revise the usage of NULL in your question title; the question itself, and these operations, have nothing to do with whether any object references are null.)

* I originally wrote LinkedList here, implictly referencing java.util.LinkedList, though that particular implementation does store its length explicitly, making size() an O(1) operation here. A more naive linked list operation might not do this, and in the more general sense there's no efficiency guarantee on implementations of List.

Answer 3

Given those two implementations, the speed should be the same, that much is true.

But those are by far not the only possible implementations for these methods. A primitive linked list (one that doesn't store the size separately) for example could answer isEmpty() much faster than a size() call.

More importantly: isEmpty() describes your intent exactly, while size()==0 is unnecessarily complex (not hugely complex of course, but any unnecessary complexity at all should be avoided).

Answer 4

You said:

Here eTime-sTime>eeTime-eTime in all cases Why?

First off, it's probably because of your testing code. You can't test the speed of calling l.size() and l.isEmpty() at the same time, since they both query the same value. Most likely calling l.size() has loaded the size of your list into your cpu cache and calling l.isEmpty() is a lot faster as a result.

You could try calling l.size() a couple of million times and l.isEmpty() a couple of million times in two separate programs but in theory the compiler could just optimize away all those calls since you're not actually doing anything with the results.

In any case, the performance difference between the two will be negligible, especially once you do the comparison you need to do to see if the list is empty (l.size() == 0). Most likely the generated code will look almost completely similar. As some other posters noted, you want to optimize for readability in this case, not speed.

edit: I tested it myself. It's pretty much a toss-up. size() and isEmpty() used on Vector gave differing results on long runs, neither beat the other consistently. When run on an ArrayList size() seemed faster, but not by much. This is most likely due to the fact that access to Vector is synchronized, so what you're really seeing when trying to benchmark access to these methods is synchronisation overhead, which can be very sensitive.

The thing to take away here is that when you're trying to optimize a method call with a couple nanoseconds difference in execution time, then you're doing it wrong. Get the basics right first, like using Longs where you should be using long.

Answer 5

Your testing code is flawed.

Just reverse the order, i.e call isEmpty first and size > 0 second and you'll get the opposite result. This is due to class loading, caching, etc.

Answer 6

I'm sorry, but your benchmark is flawed. Take a look at Java theory and practice: Anatomy of a flawed microbenchmark for a general description on how to approach benchmarks.

---

Update: for a proper benchmark you should look into Japex.

Answer 7

It is impossible to say in general which is faster, because it depends on which implementation of interface List you are using.

Suppose we're talking about ArrayList. Lookup the source code of ArrayList, you can find it in the file src.zip in your JDK installation directory. The source code of the methods isEmpty and size looks as follows (Sun JDK 1.6 update 16 for Windows):

public boolean isEmpty() {
    return size == 0;
}

public int size() {
    return size;
}

You can easily see that both expressions isEmpty() and size() == 0 will come down to exactly the same statements, so one is certainly not faster than the other.

If you're interested in how it works for other implementations of interface List, look up the source code yourself and find out.

Answer 8

According to PMD ( static ruleset based Java source code analyzer ) isEmpty() is preferred. You can find the PMD ruleset here. Search for "UseCollectionIsEmpty" rule.

http://pmd.sourceforge.net/rules/design.html

According to me it also helps in keeping the entire source code consistent rather than half of the folks using isEmpty() and the rest using size()==0.