Java-Gaming.org    
Featured games (91)
games approved by the League of Dukes
Games in Showcase (578)
games submitted by our members
Games in WIP (498)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1] 2
  ignore  |  Print  
  Object creation vs. an if statment  (Read 7002 times)
0 Members and 1 Guest are viewing this topic.
Offline Z-Man
« Posted 2011-08-18 03:24:16 »

I got the idea for my Space game (it's a side scrolling spaceship game, like Galaga turned sideways) to reuse the "enemy" objects instead of removing them from use when I don't need them. So currently I have it set up so that I have an ArrayList that holds all the enemy aliens for that level (starts at 30 and increases as the levels go on). When an alien is hit by the users laser, the Alien is removed from the ArrayList so that it is not iterated over when updating and drawing. Then at the end of the level I add Aliens to the ArrayList until it's reached the number needed for the next level. My question is, would it be better to just reuse the Alien objects already in the ArrayList instead of removing them when they get hit? My problem is that reusing would require an isAlive() (or some kind of) check on each Alien for every draw and update. Also just a minor question, does anyone know of some good information on how the innards of Java work, like the JVM and the Garbage Collector. 
Offline namrog84

JGO Ninja


Medals: 46
Projects: 4


Keep programming!


« Reply #1 - Posted 2011-08-18 03:54:12 »

So currently I have it set up so that I have an ArrayList that holds all the enemy aliens for that level (starts at 30 and increases as the levels go on). When an alien is hit by the users laser, the Alien is removed from the ArrayList so that it is not iterated over when updating and drawing. Then at the end of the level I add Aliens to the ArrayList until it's reached the number needed for the next level.

I am a little confused.  Are you adding your alien to a secondary list to check if there has been enough aliens on current level?

Why not just use a simple int counter to keep track of how many aliens have spawned or been killed or whatever?


Although I do not have a super good understanding of the JVM and GC. I don't think you need to worry about it anymore, the way you are currently doing it.
If you were really concerned, you could just "null" out your variables before you remove it from the list. Because after its out of the Arraylist, you don't really have anyway to access that data/object anymore. So I think the GC cleans it up because of that.

Anyways, for the small quantity of enemies(a few hundred at most), its probably not a big deal either way. If it was for particles or something high quantity over long periods of time, then maybe an alternative to lots of "new" object calls?


"Experience is what you get when you did not get what you wanted"
Offline Z-Man
« Reply #2 - Posted 2011-08-18 04:21:50 »

There is one ArrayList, when an Alien is hit by the user's weapon the Alien is removed from the ArrayList. The ArrayList isn't just to have the number of Aliens, it holds Alien objects that have a draw method, the Aliens position, and a move method. But for a smaller number of Objects it wouldn't matter anyway?

The JVM and GC info isn't really for this specifically, I simply don't know a lot about them and would like to know more Smiley
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline counterp

Senior Member


Medals: 11



« Reply #3 - Posted 2011-08-18 08:03:56 »

It's called object caching pooling and I don't think you need to do this (premature optimization) because I doubt that creating your alien objects is very costly, or that you do it so often that it poses a problem. But if you want to know how to do it properly, just search 'object pooling.'

EDIT: yea sorry meant pooling
Offline princec

JGO Kernel


Medals: 282
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #4 - Posted 2011-08-18 10:09:21 »

Don't do object pooling - unless you've got something that takes a long time to construct. Also don't do it if it takes a lot of clean up work.
Consider it in cases where you might be generating thousands of them every second.

Cas Smiley

Offline Bonbon-Chan

JGO Coder


Medals: 12



« Reply #5 - Posted 2011-08-18 10:55:54 »

Don't do object pooling - unless you've got something that takes a long time to construct. Also don't do it if it takes a lot of clean up work.
Consider it in cases where you might be generating thousands of them every second.

Cas Smiley

I second that. Keep thing simple until you go speed problem. When you have problem, do some profiling, the problem may not even be object creation.

Well if it is for Android, object creation do cost a lot.

But just to speak of pooling, if you don't need sorted object, I should start with an array and not an ArrayList created with the maximum number object you want (if you don't care about memory  Wink). Then use the first part of the array as used objects and the second part as free objects (just use an index to keep that). To add an object, you use have to increase the index. To remove an object, swap in the array the last used object and the object to remove, and decrease the index.

Well it is a really basic one but it works. There is plenty of post about this subject.
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 605
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #6 - Posted 2011-08-18 11:05:55 »

That might actually ruin your performance, because upon removal you'd have to search through the array. Sad

It wouldn't surprise me if that linear search would be much slower than the object-allocation you're trying to prevent.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline pitbuller
« Reply #7 - Posted 2011-08-18 12:38:52 »

That might actually ruin your performance, because upon removal you'd have to search through the array. Sad

It wouldn't surprise me if that linear search would be much slower than the object-allocation you're trying to prevent.
On some special case you know index of object you want remove.
Offline Z-Man
« Reply #8 - Posted 2011-08-18 13:45:36 »

Don't do object pooling - unless you've got something that takes a long time to construct. Also don't do it if it takes a lot of clean up work.
Consider it in cases where you might be generating thousands of them every second.

Cas Smiley
I should start with an array and not an ArrayList created with the maximum number object you want (if you don't care about memory  Wink). Then use the first part of the array as used objects and the second part as free objects (just use an index to keep that). To add an object, you use have to increase the index. To remove an object, swap in the array the last used object and the object to remove, and decrease the index.

Well it is a really basic one but it works. There is plenty of post about this subject.
The problem is that I don't know the maximum number because it changes every level. I also don't have a level cap in place so the levels can go on to infinity... or until your computer runs out of RAM and the program crashes. However it would get so hard by then that it is very unlikely that you would make it that far.

So, it seems that you all agree not to do object pooling in this case. Thanks for the input on my idea, I really appreciate it Smiley
Offline JL235

JGO Coder


Medals: 10



« Reply #9 - Posted 2011-08-18 13:57:34 »

That might actually ruin your performance, because upon removal you'd have to search through the array. Sad

It wouldn't surprise me if that linear search would be much slower than the object-allocation you're trying to prevent.
I don't see why you would need to perform any search. When an alien is killed, you will be removing it from the game's list of aliens. This will happen if you are object pooling or not. If you are object pooling, then you push the alien object onto a stack; no search needed. When you go to make a new object, you check the stack size, pop the top element if it is there, or create a new alien if it is empty; again no search needed.

I also wouldn't worry too much about memory. You will never get the memory back, unless you clear the object-pool. But lets say the most number of aliens you have on screen at once is 1,000; then you will only have 1,000 persisting in the object pool (when they all die). If you never clear the pool, then you have 1,000 objects sticking around forever. I would expect each Alien object to be relatively small, in terms of memory, and so keeping them around would take up barely any ram. This is only an issue if the alien objects are each holding something large, like if they each have their own _unique_ image.

If memory is an issue, then just clear the pool between levels, or set a cap on how many it will hold at one time.

To implement this in the Alien, you should move the constructor code out from the constructor, and into an 'initialize' method. This method wipes the current state, and sets it up as a new, clean Alien. The constructor will call initialize when it is created, and you call initialize when you re-use an Alien object.

When you brake a Java application down into the simple operations you can perform; object-creation is the most expensive (or one of the most expensive) you can do. However I would not expect any real speed difference. You can see a speed difference in applications that continuously make millions, upon millions, of objects. But you will almost certain _not_ be doing this. Your code will probably only be using around 0.1%, so any speed up/down will have no effect at all. What you gain from object-pooling is reducing GC pauses!

So how do you investigate this problem further? First if your game runs smooth, today, then GC pauses is not an issue. If you game is pausing regularly, then it might be caused by the GC, but might not (could be waiting on network/file latency, bad timers, buggy code, etc). The best way to find out if garbage collection is to blame is to profile your application, and watching the memory levels whilst it is running. This will go up as objects are created, and drop when the GC is run. If this is run say once a minute, then it's nothing to worry about, unless it's a long pause. If it is run every second, then you should probably do something about it. Next step is to work out what is the cause; which are objects are you creating the most of, and then letting go. To find this out you can more explicitly profile your memory usage, and sort this by number of objects. The best tool you can use for this is the excellent JVisualVM, which comes with the JDK. You'll find it in the 'bin' folder in the JDK's home on Windows. This is also built into NetBeans, and I would expect Eclipse has these tools as well.

Profiling, to verify the cause of the problem, should be your first port of call.

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Bonbon-Chan

JGO Coder


Medals: 12



« Reply #10 - Posted 2011-08-18 14:18:55 »

That might actually ruin your performance, because upon removal you'd have to search through the array. Sad

It wouldn't surprise me if that linear search would be much slower than the object-allocation you're trying to prevent.

In my mind, you don't have to search for object. I supposed that Aliens is deal in a loop something like :
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
  int i =0;
  while(i<alienPool.size())
  {
     Alien alien = alienPool.get(i);

     ...

     if(alien.getLife()<=0)
     {
        alienPool.remove(i);
     }
     else
     {
        ...

        i++;
     }
  }


It is a basic example. It doesn't suit a lot of case. It just to give an idee of how it can be done. That kind of optimization is highly depend of what you need (too complex = loss in performance, too simple = can't do what you want or even loss in performance).
Offline theagentd
« Reply #11 - Posted 2011-08-19 05:41:51 »

Even if you get an overall loss in performance from using pooling, it might still be worth it if it eliminates GC stuttering. While experimenting with particles I implemented caching which slowed down the performance a little, but eliminated my huge stuttering problems. Needless to say, I was creating 100.000s of objects per second, not 100. For hundred or even thousand objects, you probably don't need pooling. Just don't load stuff like images or textures in your Alien's constructor.

Myomyomyo.
Offline Mads

JGO Ninja


Medals: 24
Projects: 3


One for all!


« Reply #12 - Posted 2011-08-19 10:51:55 »

Premature optimization is never something you should do, if your program runs smoothly on your machine. When it works, then you can begin to optimize, if that's what you want to do. Make the game first though Tongue

Offline theagentd
« Reply #13 - Posted 2011-08-20 16:00:56 »

I really need to stop optimizing all the time. I obviously keep my code readable, but damn, do I get stuck. Probably the reason why I've almost never finished a whole game. I need a deadline or a new attitude to complete my games.  Emo

Myomyomyo.
Offline ra4king

JGO Kernel


Medals: 322
Projects: 2
Exp: 4 years


I'm the King!


« Reply #14 - Posted 2011-08-21 09:55:12 »

Try changing to attitude to first making a playable version. THEN start optimizing and adding features.

Offline Skarion

Senior Member


Medals: 2
Projects: 1



« Reply #15 - Posted 2011-08-21 12:23:19 »

If you decide to remove from list, use a LinkedList and an Array/HashMap if you decide to not remove from list (as to make access swifter).

Remove from list if you need to loop through list often and/or it's seldom that all possible aliens are currently alive.

Keep in list if you don't need to loop through often and/or most of the time the maximum amount of aliens are shown in screen.

If you have to kill many thousands of enemies each loop then I'd suggest what's earlier suggested in this thread.

Try changing to attitude to first making a playable version. THEN start optimizing and adding features.

Sometimes you need to understand the required optimization as to be able to continue adding features. Refactoring is often the soul of good programming 'cause otherwise the time required to implement each feature will turn exponential.

Though just the kind of optimization he asks about is of course not needed to be implemented at this stage.  Tongue

Quote
It is a basic example. It doesn't suit a lot of case. It just to give an idee of how it can be done. That kind of optimization is highly depend of what you need (too complex = loss in performance, too simple = can't do what you want or even loss in performance).

The get and remove both cause gigantic optimization problems.

Pseudocode I'd recommend if to remove is:

1  
2  
3  
4  
5  
6  
7  
8  
// Clone as to avoid synchronization errors.
// You are not allowed to modify a list you are looping through.
list = alienPool.clone();
for(alien : list){
    if(!alien.isAlive()){
        alienPool.remove(alien);
    }
}
Offline theagentd
« Reply #16 - Posted 2011-08-21 13:30:15 »

If you decide to remove from list, use a LinkedList and an Array/HashMap if you decide to not remove from list (as to make access swifter).
LinkedList is actually quite slow as it creates an Entry object for each element. It's slightly faster to just implement your own linked list (as in keeping a reference to the next object). For a list of inactive recycled objects I would use an ArrayList and always remove the last object to avoid an System.arraycopy for the whole array on each remove. This was the fastest I could come up with, but it obviously can't handle sorting in any way.

Try changing to attitude to first making a playable version. THEN start optimizing and adding features.
Right, I gotta stop drawing that line at "compilable".

Myomyomyo.
Offline Skarion

Senior Member


Medals: 2
Projects: 1



« Reply #17 - Posted 2011-08-21 13:37:26 »

LinkedList is actually quite slow as it creates an Entry object for each element. It's slightly faster to just implement your own linked list (as in keeping a reference to the next object). For a list of inactive recycled objects I would use an ArrayList and always remove the last object to avoid an System.arraycopy for the whole array on each remove. This was the fastest I could come up with, but it obviously can't handle sorting in any way.

LinkedList is a LOT faster when removing compared to ArrayList (LinkedList just removes the next/past position while ArrayList need to restructure everything). ArrayList is quicker to add.

If problem is that you will have to remove lots of aliens, LinkedList is prefered.

http://download.oracle.com/javase/tutorial/collections/implementations/list.html

And there are problems you will meet if trying to just remove the last object when avoiding an System.arraycopy.
Offline JL235

JGO Coder


Medals: 10



« Reply #18 - Posted 2011-08-21 16:20:24 »

LinkedList is actually quite slow as it creates an Entry object for each element. It's slightly faster to just implement your own linked list (as in keeping a reference to the next object). For a list of inactive recycled objects I would use an ArrayList and always remove the last object to avoid an System.arraycopy for the whole array on each remove. This was the fastest I could come up with, but it obviously can't handle sorting in any way.

LinkedList is a LOT faster when removing compared to ArrayList (LinkedList just removes the next/past position while ArrayList need to restructure everything). ArrayList is quicker to add.

If problem is that you will have to remove lots of aliens, LinkedList is prefered.

http://download.oracle.com/javase/tutorial/collections/implementations/list.html

And there are problems you will meet if trying to just remove the last object when avoiding an System.arraycopy.
Actually this is a common myth. Random removal from an ArrayList, even though it has to copy the whole array around, is still faster then random removal from a LinkedList. It's due to the fact that you have to search through the linked list, to find the element to remove, which is much more expensive then using arraycopy. There was a topic on here earlier this year (or last year) where this was discussed in detail.

Removal from the beginning of the list, sure that is faster. But removal of random elements across the whole list, on average, is much slower. Even then there are plenty of tricks to allow array based data-structures out perform linked lists. For example if you are mostly removing from the head, then alter your code to flip how your objects are laid out, so you remove from the end instead. Now the ArrayList becomes much faster again. You can also cache updates, or use lists of arrays to beat the linked list in other corner cases.

Further, very heavy linked list usage will put heavy amounts of stress on the GC. For example if you are using a linked list as the basis for a particle system, then this can cause noticeable stuttering.

The only real advantage of the linked list as a data structure, is if you keep direct references to the nodes in the list, as it allows you to remove then without any searching. You can also do other funky stuff, like swap whole sections of a list, or have the end of one list point into the middle of another, by just altering a couple of references. All (or at least most) of these cannot be efficiently done with java.util.LinkedList. That class is pretty much useless.

Offline counterp

Senior Member


Medals: 11



« Reply #19 - Posted 2011-08-21 16:24:43 »

You should be removing as often as you're adding (initial filling of the list aside), so you're calling each method an equal amount of times.  Too bad ArrayList is sooooo unbelievably slow in removing so even though adding to LinkedList is pretty slow, it's better. (There's a reason people don't use ArrayList as a queue, or at least I hope they don't lol)

But there are better alternatives, like:

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  
public class Entry { // Alien extends Entry

   public Entry next;
   public Entry last;

}

...


public class ObjectPool<E extends Entry> {

   private Entry source;
   private Entry last;

   public final Entry pop() {
      if (source == null)
         return null;
      Entry e = source;
      source = e.next;
      return e;
   }

   public final void add(E e) {
      if (source == null) {
         source = last = e;
         return;
      }
      last.next = last = e;
   }

   public final void remove(E e) {
      if (e == source) {
         source = last = null;
      } else if (e == last) {
         e.last.next = null;
         last = null;
      } else {
         e.last.next = e.next;
      }
   }

}


something I threw together quickly, has the bare necessities, almost 2x faster adding than linked list, over 3x faster removing than linked list

(I hope we're talking in a theoretical situation where you would actually need to use object pooling, and not for this alien game necessarily)
Offline JL235

JGO Coder


Medals: 10



« Reply #20 - Posted 2011-08-21 17:54:42 »

You should be removing as often as you're adding (initial filling of the list aside), so you're calling each method an equal amount of times.  Too bad ArrayList is sooooo unbelievably slow in removing so even though adding to LinkedList is pretty slow, it's better.
My (crude) benchmark disagrees with you...
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  
import java.util.*;

public class Main
{
    public static void main( String[] args )
    {
        final boolean isArrayList = true;
        final int max = 10000;
        final Random rand = new Random( 0 );
       
        for ( int i = 0; i < 10; i++ ) {
            final List<Integer> ls = isArrayList ?
                    new ArrayList<Integer>() :
                    new LinkedList<Integer>();
           
            for ( int j = 0; j < max; j++ ) {
                ls.add( j );
            }
           
            final long start = System.currentTimeMillis();
            for ( int j = 0; j < max; j++ ) {
                final int index = rand.nextInt( ls.size() );
               
                ls.remove( index );
            }
            System.out.println( System.currentTimeMillis() - start );
        }
    }
}

I am randomly removing all items, and when using an ArrayList, it is more then twice as fast then using a LinkedList, on my PC.

Again, on average, ArrayList is faster.

Offline counterp

Senior Member


Medals: 11



« Reply #21 - Posted 2011-08-21 18:02:14 »

You're not doing it right...

You're using the LinkedList as a list instead of a queue.

Use pop/poll methods
Offline Skarion

Senior Member


Medals: 2
Projects: 1



« Reply #22 - Posted 2011-08-21 18:10:35 »

I tried to check the validity of your response.

The error of your checking seems to be as that ArrayList tries to use the int you giving it as an index while the LinkedList tries to find and remove it.

I did a little more hideus testing (as to avoid other reasons to affect the time effect than just the removing).

My thinking is that Random, using Integers (instead of objects) and other such things may tweak the results, so  I made sure to avoid those things when creating the test.

Quote
   public Test(){
      List mainList = createList();
      Object[] toRemove = mainList.subList(4923, 44323).toArray();
      ArrayList<Object> aList = new ArrayList<Object>();
      LinkedList<Object> lList = new LinkedList<Object>();
      for(Object o : mainList.toArray()){
         aList.add(o);
         lList.add(o);
      }
      remove(aList, toRemove);
      remove(lList, toRemove);
   }
   
   private ArrayList<String> createList(){
      ArrayList<String> a = new ArrayList<String>();
      for(int i = 0; i<100000;i++){
         a.add(NameGenerator.newString());
      }
      return a;
   }
   
   private void remove(List<Object> list, Object[] toRemove){
      Long time = System.currentTimeMillis();
      for(Object o : toRemove){
         list.remove(o);
      }
      System.out.println(System.currentTimeMillis()-time);
   }

Which gives me that LinkedList is 2-4 times quicker than an ArrayList is.

Three attempts:
ArrayList: 5462, 8187, 8110
LinkedList: 2213, 3329, 3328
Offline counterp

Senior Member


Medals: 11



« Reply #23 - Posted 2011-08-21 18:14:04 »

That doesn't make sense, arraylist should be faster in removing specific objects.
Offline Skarion

Senior Member


Medals: 2
Projects: 1



« Reply #24 - Posted 2011-08-21 18:15:57 »

That doesn't make sense, arraylist should be faster in removing specific objects.

According to Oracle/Sun ArrayList shouldn't be if the list is large enough.

For example according to the link I gave above.

Ran a bit of automatic testing and with 10 retrying with the same code:

ArrayList: 7782
LinkedList: 3250
ArrayList: 8078
LinkedList: 3344
ArrayList: 7968
LinkedList: 2641
ArrayList: 7609
LinkedList: 3234
ArrayList: 8203
LinkedList: 3500
ArrayList: 7515
LinkedList: 3297
ArrayList: 7625
LinkedList: 3203
ArrayList: 7610
LinkedList: 3234
ArrayList: 7953
LinkedList: 2704
ArrayList: 7953
LinkedList: 3297
Offline counterp

Senior Member


Medals: 11



« Reply #25 - Posted 2011-08-21 18:18:05 »

Wait, nevermind, forgot ArrayList is completely shifted duhh

anyways,

LinkedList pop/poll is waaaaaaaaaaay faster than removing a specific object which is what you're gonna be using in the case of an object pool anyways
Offline Skarion

Senior Member


Medals: 2
Projects: 1



« Reply #26 - Posted 2011-08-21 18:21:15 »

LinkedList pop/poll is waaaaaaaaaaay faster than removing a specific object which is what you're gonna be using in the case of an object pool anyways

I would've preferred to use a specific removal instead of pop/poll myself, makes it easier in the long run and as long as you aren't doing hideus things there shouldn't be any extensive CPU demands. In case the goal is to loop through often and not too many kills each loop that is.
Offline counterp

Senior Member


Medals: 11



« Reply #27 - Posted 2011-08-21 18:24:20 »

oh wait were you guys talking about the list storing live aliens?

I was talking about the object pool lol.
Offline JL235

JGO Coder


Medals: 10



« Reply #28 - Posted 2011-08-21 20:23:42 »

I tried to check the validity of your response.

The error of your checking seems to be as that ArrayList tries to use the int you giving it as an index while the LinkedList tries to find and remove it.
Not true. The signature for the List.remove which removes by index is clearly defined. It is 'int', not 'Integer', and that is what I am passing in (so it binds tighter).

However to remove the ambiguity, I have changed my example to store String instead of Integer.
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  
import java.util.*;

public class Main
{
    public static void main( String[] args )
    {
        final boolean isArrayList = false;
        final int max = 10000;
        final Random rand = new Random( 0 );
        final String[] strs = new String[ max ];
       
        for ( int j = 0; j < max; j++ ) {
            strs[j] = String.valueOf(j);
        }
       
        for ( int i = 0; i < 10; i++ ) {
            final List<String> ls = isArrayList ?
                    new ArrayList<String>() :
                    new LinkedList<String>();
           
            for ( int j = 0; j < max; j++ ) {
                ls.add( strs[j] );
            }
           
            final long start = System.currentTimeMillis();
            for ( int j = 0; j < max; j++ ) {
                final int index = rand.nextInt( ls.size() );
               
                ls.remove( index );
            }
            System.out.println( System.currentTimeMillis() - start );
        }
    }
}

The results are the same, when removing by index, ArrayList is on average faster then LinkedList.

Your test also does not take into account 'random' removals. Instead by using sublist, it is skewed towards one half of the list. This gives LinkedList an unfair advantage (unless a skewed random removal is what you are trying to test). So I have altered your test to create a random list of elements, and remove them. This gives a much better spread of removals.
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  
    public static void test2()
    {
        final int max = 25000;
        final boolean isArrayList = false;
       
        List<String> mainList = createList(max);
        final String[] toRemove = new String[max];
        final Random random = new Random(0);
       
        for ( int i = 0; i < max; i++ ) {
            final int index = random.nextInt( mainList.size() );
            toRemove[i] = mainList.remove( index );
        }
       
        mainList = createList(max);
        final List<String> list = isArrayList ?
                new ArrayList<String>() :
                new LinkedList<String>();
       
        for ( int i = 0; i < 10; i++ ) {
            for ( String o : mainList ){
                list.add(o);
            }
       
            remove(list, toRemove);
        }
    }
   
    private static ArrayList<String> createList( int length ){
        final ArrayList<String> a = new ArrayList<String>();
     
        for ( int i = 0; i<length; i++ ){
            a.add( String.valueOf(i) );
        }
       
        return a;
    }
   
    private static void remove(List<String> list, String[] toRemove){
        long time = System.currentTimeMillis();
     
        for ( final String o : toRemove){
            list.remove(o);
        }
     
        System.out.println(System.currentTimeMillis()-time);
    }

With very large data sets, I found the ArrayList is faster. With smaller ones, the Linked List is marginally faster. But either way, you really shouldn't be searching for objects in a List.

My overall point stands. For removal by index, ArrayList is faster then LinkedList, on average. For some special cases, LinkedList is faster, but generally there are better alternatives.

Wait, nevermind, forgot ArrayList is completely shifted duhh

anyways,

LinkedList pop/poll is waaaaaaaaaaay faster than removing a specific object which is what you're gonna be using in the case of an object pool anyways
Disagree. The ArrayList will trounce the Linked List, easily, when used as a stack. Pretty much all stack implementations are essentially arrays underneath.

The ArrayDeque will also handle this job much faster then the ArrayList.

Offline Skarion

Senior Member


Medals: 2
Projects: 1



« Reply #29 - Posted 2011-08-21 21:15:32 »

Not true. The signature for the List.remove which removes by index is clearly defined. It is 'int', not 'Integer', and that is what I am passing in (so it binds tighter).

Tested it out and also made a new version which would include a little more randomness and less special cases.

My conclusion is that you seem to be correct, so if you are to remove things at a random position ArrayList is better than LinkedList.

If to have numbers then ArrayList seems to be in my tests about 10% faster than LinkedList at least when removing 500-30,000 objects in a 100,000 size list.

Thanks for teaching me something new.  Smiley
Pages: [1] 2
  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.

xsi3rr4x (27 views)
2014-04-15 18:08:23

BurntPizza (22 views)
2014-04-15 03:46:01

UprightPath (38 views)
2014-04-14 17:39:50

UprightPath (20 views)
2014-04-14 17:35:47

Porlus (36 views)
2014-04-14 15:48:38

tom_mai78101 (61 views)
2014-04-10 04:04:31

BurntPizza (119 views)
2014-04-08 23:06:04

tom_mai78101 (219 views)
2014-04-05 13:34:39

trollwarrior1 (186 views)
2014-04-04 12:06:45

CJLetsGame (193 views)
2014-04-01 02:16:10
List of Learning Resources
by Longarmx
2014-04-08 03:14:44

Good Examples
by matheus23
2014-04-05 13:51:37

Good Examples
by Grunnt
2014-04-03 15:48:46

Good Examples
by Grunnt
2014-04-03 15:48:37

Good Examples
by matheus23
2014-04-01 18:40:51

Good Examples
by matheus23
2014-04-01 18:40:34

Anonymous/Local/Inner class gotchas
by Roquen
2014-03-11 15:22:30

Anonymous/Local/Inner class gotchas
by Roquen
2014-03-11 15:05:20
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!