59

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?

0

9 Answers 9

107

For ArrayList, yes — you are correct that the operations take (roughly) the same time.

For other implementations of List — for example, a naïve linked list* — counting the size might take a very long time, while you only actually care whether it is greater than zero.

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

  1. This is bad programming practice 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 is 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.

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

4
  • 6
    "the" LinkedList (a.k.a java.util.LinkedList) also stores its size so the size() call is just as fast as for ArrayList, but the general point is still very valid. Oct 2, 2009 at 11:34
  • @dtszzs:The run time is not same,thats what i tested and just making me uncomfortable.. Oct 2, 2009 at 11:52
  • 4
    @Sam Rudolph: how did you test it? There are thousands of ways to get such microbenchmarks wrong. Oct 2, 2009 at 12:29
  • @Joachim - yes, good point about the java.util.LinkedList, I've revised that section to be clearer. Oct 2, 2009 at 13:41
74

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.

1
  • 2
    @JLR:Yes I accept your point,There was flaw,as tested both the methods in 2 separate projects and both are giving,very much similar result. Thanx for Clearing my doubt Oct 3, 2009 at 6:44
17

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.

0
10

.size() has to look at the entire list, while .isEmpty() can stop at the first one.

Obviously implementation dependent, but as has been said before, if you don't need to know the actual size, why bother counting all the elements?

6

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.

1
  • no actually just not i ran the two cases in separate programs just to Clear the doubt and result is same size() is taking 10 times more runtime than isEmpty() Oct 2, 2009 at 12:19
2

Counting items in a linked list can be very slow.

3
  • @spdenme:but its not counting,its just returning a value? Oct 2, 2009 at 11:37
  • In your example you have an ArrayList Oct 2, 2009 at 11:39
  • List is an interface. How it is implemented affects the relative performance of those two methods. Since size() is a frequently called method, most implementations decide the cost of maintaing a size field is worthwhile. Oct 2, 2009 at 11:47
2

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).

2
  • but6 if u see there implementation,those looks very very simple? Oct 2, 2009 at 11:50
  • The ones you look at, yes. But as @dtsazza explained pretty well: implementation is not the only important thing, intent and readability are important as well. And there might be other Collectons implementations where size() might not be implemented so easily (WeakHashMap or other dynamic collections). Oct 2, 2009 at 12:28
1

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.

0

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.