How to efficiently remove an ArrayList element?

Question

In my game engine, there are Particles, all of these particles have a slightly different lifespan. Every update, their life is shortened and when it reaches 0 it is removed from an ArrayList meaning it will no longer be updated or rendered. Although under normal game play I experience no problems with this approach, when I have a large large number of particles (around 100,000) there is major lag when creating and removing (but not updating) the particles.

Because of that lag, I am looking to improve the efficiency of this setup. I have tried only removing so many per update and leaving the rest for the next update but that didn't provide too great of results.

package com.burksnet.code.games.rain.entity.particle;

import com.burksnet.code.games.rain.entity.Entity;
import com.burksnet.code.games.rain.graphics.Screen;
import com.burksnet.code.games.rain.graphics.Sprite;
import com.burksnet.code.games.rain.level.Level;

public class Particle extends Entity {

    private Sprite sprite;
    private int life;

    private double speed = 2;

    public static int maxParticleCount = 2500000;

    protected double xa, ya;
    //Life is how long it lives, x, y, and level are obvious.
    public Particle(int x, int y, int life, Level level) {
        super(level);
        //The sprite to be rendered.
        sprite = Sprite.particleNormal;
        this.x = x;
        this.y = y;
        this.life = life;

        //how it will move. effectively randomly.
        this.xa = random.nextGaussian() /2 * speed;
        this.ya = random.nextGaussian() /2 * speed;

    }

    //Renders the particle on screen.
    public void render(Screen screen) {
        if(life <= 0 ) return;
        screen.renderSprite(x, y, sprite, true);
    }

    //Updates it.
    public void update() {
        if(life <= 0 ){
            //Removes the item from the level, making it no longer be rendered or updated. See the method below.
            level.remove(this);
        }
        this.x += xa;
        this.y += ya;
        life--;
    }

}

Level.remove(Particle e) below

public void remove(Particle e) {
    particles.remove(e);
}

Level.add(Particle e) below. Is used when a particle is created so it may be updated and rendered.

public void add(Particle e) {
    particles.add(e);
}

I guess it is definitely possible this is just a pure limitation that cannot be overcome but I hope that is not the case.

Answer 1

Let's take a look at what happens when you remove an item from the middle of an ArrayList.

       +---+---+---+---+---+
Start  | 1 | 2 | 3 | 4 | 5 |
       +---+---+---+---+---+
Step 1 | 1 | 2 |   | 4 | 5 |
       +---+---+---+---+---+
Step 2 | 1 | 2 | 4 |   | 5 |
       +---+---+---+---+---+
Step 3 | 1 | 2 | 4 | 5 |   |
       +---+---+---+---+---+

As you can see, most of the time spent is not in removin the item itself, but moving the items that come after it into their new places. This is why, for a list of 100,000 records, removing will take a long time.

If you don't need random access (the use of get(i)), then you can look into using a LinkedList instead. If you do need get(i), then you're going to need to make some tough decisions.

Answer 2

The problem seems to lie in the way that you're iterating and updating the particles. You'll want to use a LinkedList and iterate over it in your Level. I would recommend refactoring the update() method to return a boolean to signal when the Entity should be removed from the level.

public class Particle {
    public boolean update() {
        if (life <= 0) {
            return false; // remove me!
        }
        this.x += xa;
        this.y += ya;
        life--;
        return true; // update successful
    }
}

public class Level {
    public boolean update() {
        Iterator<Particle> it = particles.iterator();
        while (it.hasNext()) {
            Particle p = it.next();
            if (!p.update()) {
                it.remove(); // Remove is O(1) with LinkedList
            }
        }
        return true; // update successful
    }
}

Answer 3

I am guessing there are several things that are contributing to the lag you are seeing.

The size of your data structure

Each double takes up 8 bytes of memory. Do you really need a 64 bit floating point value for your coordinates and your speed?

I don't know what's in your Entity class, but a quick computation leads me to (conservatively) guess that each Particle object will take up at least 32 bytes of memory. This will be roughly 3 MB of heap for 100,000 Particles. If the Particle objects are removed often during gameplay, the JVM's garbage collector could contribute a significant amount to the lag.

Your use of floating point math

This is used when calculating your xa and ya coordinates

Consider using integer math instead as this could provide a noticable improvement to the performance of your game.

Adding and removing from an ArrayList

As you've pointed out, adding and removing from an ArrayList can be expensive. For add, there is the potential to have to reallocate memory to accommodate the newly added element. For remove, all of the elements that came after the one removed have to be copied back one place in the list.

One thing you could do if you choose to stay with ArrayList is to construct one with an initial capacity that is close to whatever you think your max number of particles is. This has the downside of reserving a big chunk of heap right away, but will avoid having to reallocate often. The default initial capacity for an ArrayList is 10.

You might consider a different List implementation that provides better performance for adds/removes. LinkedList fits the bill as does possibly an ordered Map like a TreeMap.

Gather solid data about your app by profiling it

One of the best things you can do is to profile your app while it is running to see where the CPU cycles are being spent and heap is being allocated. Don't pre-optimize if you can help it. Measure first! Good luck!

Answer 4

class Array {
  public Static void main(string args[]) {
    ArrayList<String> lst=new ArrayList<String>();
    lst.add("abc");
    lst.add("xyz");
    lst.add("pqr");
    Iterator<String> itr=lst.Iterator();
    while(itr.hasNext()) {
      String ele=itr.next();
      if(ele.equals("xyz") {
        itr.remove();
      }
      System.out.println(ele);  
    }
  }
}