Java-Gaming.org Hi !
Featured games (83)
games approved by the League of Dukes
Games in Showcase (513)
Games in Android Showcase (120)
games submitted by our members
Games in WIP (577)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Why isn't ArrayList.size() compiled by hotspot?  (Read 2722 times)
0 Members and 1 Guest are viewing this topic.
Offline CommanderKeith
« Posted 2010-05-23 05:39:57 »

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

Offline CommanderKeith
« Reply #1 - Posted 2010-05-23 09:25:51 »

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

Online Riven
« League of Dukes »

JGO Overlord


Medals: 817
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #2 - Posted 2010-05-23 10:34:25 »

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.

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


vs.

1  
2  
3  
4  
5  
final int size = list.size();
for(int i=0; i<size; i++)
{
    //
}

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline CommanderKeith
« Reply #3 - Posted 2010-05-23 12:20:14 »

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:
1  
2  
3  
4  
5  
6  
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



1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
57  
58  
59  
60  
61  
62  
63  
64  
65  
66  
67  
68  
69  
70  
71  
72  
73  
74  
75  
76  
77  
78  
79  
80  
81  
82  
83  
84  
85  
86  
87  
88  
89  
90  
91  
92  
93  
94  
95  
96  
97  
98  
99  
100  
101  
102  
103  
104  
105  
106  
107  
108  
109  
110  
   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);

      }
   }

Offline Dreamcatchermatt

Junior Duke





« Reply #4 - Posted 2010-05-23 12:38:47 »


1  
2  
3  
4  
5  
final int size = list.size();
for(int i=0; i<size; i++)
{
    //
}


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.
Online Riven
« League of Dukes »

JGO Overlord


Medals: 817
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #5 - Posted 2010-05-23 12:41:48 »

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.

The difference is that 'private' results in a compile error.

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

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline JL235

JGO Coder


Medals: 10



« Reply #6 - Posted 2010-05-23 13:12:35 »

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.
Private can only be used outside of methods within the class, not within methods. i.e.
1  
2  
3  
4  
5  
6  
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.

Offline Spasi
« Reply #7 - Posted 2010-05-23 13:37:03 »

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.

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.
Offline Dreamcatchermatt

Junior Duke





« Reply #8 - Posted 2010-05-23 15:22:19 »

hah, sorry - know that about private not being alowed inside methods - was not thinking while I was typing it Smiley 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
Online Riven
« League of Dukes »

JGO Overlord


Medals: 817
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #9 - Posted 2010-05-23 15:26:41 »

I usualy add/remove entries from my ArrayLists while i'm itterating through the ArrayList

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.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Dreamcatchermatt

Junior Duke





« Reply #10 - Posted 2010-05-23 15:52:37 »

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

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
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.
Online Riven
« League of Dukes »

JGO Overlord


Medals: 817
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #11 - Posted 2010-05-23 15:57:41 »

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


let's imagine we have a List<String> containing: "A","B","C","D","E"

let's say you want to remove element "C" and "D"

Just run this code:
1  
2  
3  
4  
5  
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.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline JL235

JGO Coder


Medals: 10



« Reply #12 - Posted 2010-05-23 16:39:49 »

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.

Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Reply #13 - Posted 2010-05-23 17:18:59 »

This is basicaly how i'm doing it at the moment, and it seems to be working fine.
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."

See my work:
OTC Software
Offline Nate

JGO Kernel


Medals: 149
Projects: 4
Exp: 14 years


Esoteric Software


« Reply #14 - Posted 2010-05-24 05:54:36 »

You seem to be concerned with speed in this thread (hence the benchmarking up at the top). So if your adding/removing whilst iterating
You missed the part where the thread got derailed.

Offline JL235

JGO Coder


Medals: 10



« Reply #15 - Posted 2010-05-24 09:22:23 »

You missed the part where the thread got derailed.
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...
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
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 );
        }
    }
}

Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Reply #16 - Posted 2010-05-24 14:35:04 »

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

See my work:
OTC Software
Offline JL235

JGO Coder


Medals: 10



« Reply #17 - Posted 2010-05-24 14:59:58 »

Or make your own implementation of an ArrayList that only resizes once at the end of the loop.
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.

Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Reply #18 - Posted 2010-05-24 16:54:48 »

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
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).
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
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.

See my work:
OTC Software
Offline JL235

JGO Coder


Medals: 10



« Reply #19 - Posted 2010-05-24 17:31:29 »

The above puts more stress on the gc, but that's unlikely to be an issue.
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.

Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Reply #20 - Posted 2010-05-25 00:50:59 »

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.
Yeah, unfortunately LinkedList has rarely been the right option for me. Anytime I put it in because I assume it'll be faster it doesn't turn out to be at all. I'm sure there are some situations where it's the best option, but this probably is rarely games.

See my work:
OTC Software
Offline Nate

JGO Kernel


Medals: 149
Projects: 4
Exp: 14 years


Esoteric Software


« Reply #21 - Posted 2010-05-25 03:02:46 »

If it ain't broke...

Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Reply #22 - Posted 2010-05-26 00:01:01 »

If it ain't broke...
FIX IT!

Then fix it again!

Make sure it'll never break!

Ever!

See my work:
OTC Software
Offline zammbi

JGO Coder


Medals: 4



« Reply #23 - Posted 2010-05-26 02:13:28 »

If it ain't broke...
Then it doesn't have enough features!

Current project - Rename and Sort
Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

Longarmx (52 views)
2014-10-17 03:59:02

Norakomi (44 views)
2014-10-16 15:22:06

Norakomi (33 views)
2014-10-16 15:20:20

lcass (38 views)
2014-10-15 16:18:58

TehJavaDev (68 views)
2014-10-14 00:39:48

TehJavaDev (68 views)
2014-10-14 00:35:47

TehJavaDev (60 views)
2014-10-14 00:32:37

BurntPizza (73 views)
2014-10-11 23:24:42

BurntPizza (45 views)
2014-10-11 23:10:45

BurntPizza (86 views)
2014-10-11 22:30:10
Understanding relations between setOrigin, setScale and setPosition in libGdx
by mbabuskov
2014-10-09 22:35:00

Definite guide to supporting multiple device resolutions on Android (2014)
by mbabuskov
2014-10-02 22:36:02

List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!