Why isn't ArrayList.size() compiled by hotspot?

Newbie & Debugging Questions
#1

Hi,

I notice that the ArrayList.size() method is never compiled but is always interpreted on my windows vista jre 6u17 box. I know this because when I run with the -Xprof profiling option it is taking 6% of the time spent in my game loop method and it is listed under the ‘interpreted’ heading. Why can’t this method be compiled? I tried google but it didn’t come up with anything. Is it because the ArrayList.size() method is declared by the Collection interface and hotspot can’t compile those methods?

Thanks,
Keith

#2

I found some stuff here which says that interface methods are somehow treated differently, under the ‘methods’ heading:

http://wikis.sun.com/display/HotSpotInternals/PerformanceTechniques

#3

Almost every method in ArrayList is an overridden/implemented interface method (from List and Collection), so size() wouldn’t be slower than anything else.

Did you actually benchmark the difference without a running profiler? Profilers tend to change the performance characteristics.


for(int i=0; i<list.size(); i++)
{
    //
}

vs.


final int size = list.size();
for(int i=0; i<size; i++)
{
    //
}
#4

Thanks for the reply.

Looks like you’re right, when I do the below benchmark, while the ‘final int size’ method is a little faster, when I profile the test code ArrayList.size() never comes up as an expensive method.

Here’s the results of the below test for me:

test 1, with ArrayList.size() first
ArrayList.size(), averageNanosElapsed == 10718391
final int size,   averageNanosElapsed == 9684406
test 2, with ArrayList.size() second
final int size,   averageNanosElapsed == 9456993
ArrayList.size(), averageNanosElapsed == 10827086

	public static void main(String[] args){
		int numObjects = 5000000;
		ArrayList list = new ArrayList(numObjects);
		for (int i = 0; i < numObjects; i++){
			list.add(new Object());
		}
		// warm the JIT
		{
			int numTests = 10;
			long averageNanosElapsed = 0;
			for (int j = 0; j < numTests; j++){
				long startNanos = System.nanoTime();
				long count = -Long.MAX_VALUE;
				for (int i = 0; i < list.size(); i++){
					count += i;
				}
				long endNanos = System.nanoTime();
				long nanosElapsed = endNanos - startNanos;
	//			System.out.println("ArrayList.size(), nanosElapsed == "+nanosElapsed);
				averageNanosElapsed += nanosElapsed;
			}
			averageNanosElapsed /= numTests;
	//		System.out.println("ArrayList.size(), averageNanosElapsed == "+averageNanosElapsed);
			averageNanosElapsed = 0;
			for (int j = 0; j < numTests; j++){
				long startNanos = System.nanoTime();
				long count = -Long.MAX_VALUE;
				final int size = list.size();
				for (int i = 0; i < size; i++){
					count += i;
				}
				long endNanos = System.nanoTime();
				long nanosElapsed = endNanos - startNanos;
	//			System.out.println("final int size,   nanosElapsed == "+nanosElapsed);
				averageNanosElapsed += nanosElapsed;
			}
			averageNanosElapsed /= numTests;
	//		System.out.println("final int size,   averageNanosElapsed == "+averageNanosElapsed);
		}

		// run the tests
		System.out.println("test 1, with ArrayList.size() first");
		{
			int numTests = 100;
			long averageNanosElapsed = 0;
			for (int j = 0; j < numTests; j++){
				long startNanos = System.nanoTime();
				long count = -Long.MAX_VALUE;
				for (int i = 0; i < list.size(); i++){
					count += i;
				}
				long endNanos = System.nanoTime();
				long nanosElapsed = endNanos - startNanos;
//				System.out.println("ArrayList.size(), nanosElapsed == "+nanosElapsed);
				averageNanosElapsed += nanosElapsed;
			}
			averageNanosElapsed /= numTests;
			System.out.println("ArrayList.size(), averageNanosElapsed == "+averageNanosElapsed);
			averageNanosElapsed = 0;
			for (int j = 0; j < numTests; j++){
				long startNanos = System.nanoTime();
				long count = -Long.MAX_VALUE;
				final int size = list.size();
				for (int i = 0; i < size; i++){
					count += i;
				}
				long endNanos = System.nanoTime();
				long nanosElapsed = endNanos - startNanos;
//				System.out.println("final int size,   nanosElapsed == "+nanosElapsed);
				averageNanosElapsed += nanosElapsed;
			}
			averageNanosElapsed /= numTests;
			System.out.println("final int size,   averageNanosElapsed == "+averageNanosElapsed);
		}
		System.out.println("test 2, with ArrayList.size() second");
		{
			int numTests = 100;
			long averageNanosElapsed = 0;
			for (int j = 0; j < numTests; j++){
				long startNanos = System.nanoTime();
				long count = -Long.MAX_VALUE;
				final int size = list.size();
				for (int i = 0; i < size; i++){
					count += i;
				}
				long endNanos = System.nanoTime();
				long nanosElapsed = endNanos - startNanos;
//				System.out.println("final int size,   nanosElapsed == "+nanosElapsed);
				averageNanosElapsed += nanosElapsed;
			}
			averageNanosElapsed /= numTests;
			System.out.println("final int size,   averageNanosElapsed == "+averageNanosElapsed);

			averageNanosElapsed = 0;
			for (int j = 0; j < numTests; j++){
				long startNanos = System.nanoTime();
				long count = -Long.MAX_VALUE;
				for (int i = 0; i < list.size(); i++){
					count += i;
				}
				long endNanos = System.nanoTime();
				long nanosElapsed = endNanos - startNanos;
//				System.out.println("ArrayList.size(), nanosElapsed == "+nanosElapsed);
				averageNanosElapsed += nanosElapsed;
			}
			averageNanosElapsed /= numTests;
			System.out.println("ArrayList.size(), averageNanosElapsed == "+averageNanosElapsed);

		}
	}
#5

I always do this, but use ‘private int size = list.size();’

What is the difference between final and private in this setting? I have only come across the final keyword a few times, and never used it.

#6

The difference is that ‘private’ results in a compile error.

http://java.sun.com/docs/books/tutorial/java/

#7

Private can only be used outside of methods within the class, not within methods. i.e.


class Klass
{
    private int foo; // outside a method
    
    public void method() { }
}

Private states that the field cannot be accessed by instances of a different class, regardless of if it’s inherited or not. I believe instances of the same class can access private variables of other instances of the same class (although personally I don’t advise this). Missing out the private makes the field ‘package private’. This means only instances of classes in the same package can access the variable. Other alternatives are protected and public; they are known as ‘access modifiers’ (or something like that).

As a general rule, you should always make all fields private. Doing anything else is exposing how the class works to the outside, and typically leads to less maintainable code.

Making the variable final means it’s value must be declared when it is initialized, and can only be declared once. These are also known as constants. I personally try to make all my variables final, unless I know they must be changed to something else. This is because I often find very few variables actually need to change, and so find it easier to understand my old code knowing that most variables stay the same. i.e. If a field is non-final then I need to read all of my class to see if it’s altered anywhere, however if it is final then I don’t need to. Following this now means the converse, that any non-final field will (or at least should) be altered somewhere in my class. However I would stress this is just my personal preference (I’ve used several functional languages which have inspired it), and unlike using private for all fields, most people don’t do this.

#8

100% agree on this one. In fact, sometimes I wish class fields and method arguments were final by default and there was a “nonfinal” modifier instead. It would save a lot of typing. Same goes for the @NotNull annotation.

#9

hah, sorry - know that about private not being alowed inside methods - was not thinking while I was typing it :slight_smile: What I ment was the final keyword.

Ok, so thats interesting and usefull to know.

For me, in the case of game the Update() method, I usualy add/remove entries from my ArrayLists while i’m itterating through the ArrayList (hence why I use a for, not a foreach) so I would want to be able to reset the value of size as the loop goes.

However, If createing a size variable before the loop gives slightly better performance over constantly using the ArrayList.size() method I’ll make sure I stick to doing that in future.

Chears for clarifying guys

#10

Note that if you don’t take any precautions, like iterating backwards, or adjusting the counter, you’ll be skipping elements when removing during iterating.

#11

This is basicaly how i’m doing it at the moment, and it seems to be working fine.


ArrayList<Projectile> Projectiles;

....

Update(int deltaTime)
{
    int size = Projectiles.size();

    for(int i = 0; i < size; i++)
    {
        if(Projectiles.get(i).EXPIRED)
        {
              Projectiles.remove(i);
              size--;
        }
        else
        {
              Projectiles.get(i).Update(deltaTime);
        }
    }
}

Projectile.EXPIRED is set to false by default, and is set to true during the projectiles Update() method if the projectile has hit something or reaches its life limet.

This is so that I get the rest of the Update cycle to set all the particle effects, etc for the before the particle is culled from the ArrayList.

#12

You’ve got the bug I just warned you about.

let’s imagine we have a List containing: “A”,“B”,“C”,“D”,“E”

let’s say you want to remove element “C” and “D”

Just run this code:


System.out.println("before: "+list);
for(int i=0; i<list.size(); i++)
   if(list.get(i).equals("C") || list.get(i).equals("D"))
      list.remove(i);
System.out.println("after: "+list);

And now think really hard why “D” is still there.

#13

You seem to be concerned with speed in this thread (hence the benchmarking up at the top). So if your adding/removing whilst iterating then it would be far more efficient to use a LinkedList and an iterator, instead of an ArrayList and a for loop. LinkedLists are built for random insertion and removal because Arraylists are very inneficient at performing these tasks (they need to copy lots of array elements around, rather then just update a couple of references). The LinkedList has a method for creating a ListIterator, which allows you to both add and remove elements as your iterate.

It’ll also avoid this current issue with you needing to take into account the indexes changing as you iterate through the list.

#14

Yes, you want to go backwards, so that as you remove elements the ones that get shifted (in terms of indices) have already been “looked at.”

#15

You missed the part where the thread got derailed.

#16

The point still stands, it’s really inneficient to use an ArrayList for this.

Switch Projectiles to a LinkedList, and then use an iterator instead…

Update(int deltaTime)
{
    final Iterator<Projectile> it = Projectiles.iterator();
    
    while ( it.hasNext() ) {
    {
        final Projectile p = it.next();
        
        if( p.EXPIRED )
        {
              it.remove();
        }
        else
        {
              p.Update( deltaTime );
        }
    }
}
#17

Or make your own implementation of an ArrayList that only resizes once at the end of the loop.

#18

I agree this probably would probably be more efficient then the standard ArrayList, and would work very well if your removing or adding lots of items that are directly next to each other. However with random insertion and removal I’m really skeptical it would be more efficient then a LinkedList.

If you removed more then one item, which were not next to each other, the arraylist would become fragmented. You would still need to copy the internal array multiple times in order to repack it down correctly. If performing this after the loop you could do this more efficiently by copying only from the current index up to the end of the current fragment, rather then from the current index right to the end which it does currently. But adding would add the same issue, you would need to again copy small chunks of the array around in order to make the space needed between the chunks.

By moving the copying to the end of the loop you’d have reduced each large array copy down to a smaller array copy. However updating 2 or 3 references would still probably be much cheaper then a small array copy. Finally all that management requires added overhead. But I’d be interested if anyone did build this.

I can’t remember what it’s called, but I’ve seen an alternative to the ArrayList built out of chained blocks of arrays. Random insertion and removal is more efficient then the ArrayList, whilst having faster random access then a LinkedList. But it doesn’t sound like the user needs fast random access, so I’d still recommend a LinkedList.

#19 

Object[] myArray = new Object[1000];
int size = 1000;
for (int i = 0; i < myArray.length; i++)
{
    if (myArray[i].markedForDeletion)
    {
        myArray[i] = null;
        size--;
    }
}
Object[] resizedArray = new Object[size];
int offset = 0;
for (int i = 0; i < resizedArray.length; i++)
{
    if (myArray[i+offset] != null)
    {
        resizedArray[i] = myArray[i+offset];
    }
    else
    {
        offset++;
    }
}

That’s not particularly slow; just 2*n.

A faster implementation (but you won’t end up with exact size).


Object[] myArray = new Object[1000];
Object[] newArray = new Object[1000]; //or some sort of intelligently found estimate
int j = 0;
for (int i = 0; i < myArray.length; i++)
{
    if (!myArray[i].markedForDeletion)
    {
        newArray[j] = myArray[i];
        j++;
    }
}

Neither are slow. Using a LinkedList would, in fact, waste more memory (probably, depending upon how many entities are being removed) and would be slower. The above puts more stress on the gc, but that’s unlikely to be an issue.

#20

[quote=“Demonpants,post:19,topic:35317”]
You can have the LinkedList cache it’s nodes after being used, and then re-use them later.

However I just made some hacky benchmarks comparing LinkedList to an array, and I have to concede resizing the array after is faster. I found this with both large and small collections, and when removing very many and very few items. If you got System.arraycopy involved for copying segments in bulk (rather then manually moving them) it should be even faster.