Making my List.filter faster on Scala?

Question

I'm making a game with Scala.

My game has several pools for keeping enemies. They are immutable Lists because they are initialized to a size that should be enough (because creating new enemy instances during the game is very expensive).

My game knows if an enemy is alive by asking enemy.isVisible. So my CollisionHandler works like:

1. Combine all live enemies to a list
2. Get live bullets
3. Space partition these and do collision detection for bullets and enemies in the same space partition

What supprised me was that according to the profiler, step 1 takes most of the time. And what that step does is basically say:

def allActiveEnemies = List(enemyType1.getAllActive, enemyType2.getAllActive, ... ).flatten

the flatten there doesn't seem expensive but instead it's get getAllActive calls. They are implemented in my Pooled trait like this:

trait Pooled[T <: Entity] {
    var pool = List[T]()
    val INITIAL_POOL_SIZE:Int

    def initPool() {
        for(i<-1 to INITIAL_POOL_SIZE)
        {
            addToPool(disable(createNew))
        }
    }

    def getAllActive:List[T] = pool.filter(e => e.isVisible)
}

(I omitted most of the trait because I don't think it's relevant here.)

pool.filter is what burns like 45% of the total time spent in CollisionHandler, which seems really strange.

Any suggestions to make things faster here?

Maybe using ArrayLists instead of List? Maybe using some sorting and mutable collections? Or am I simply doing something horribly wrong?

Thanks!

Answer 1

How large are these pools? You do know that every time you make a list, you have to create a new object to hold each entry. You could cut down on this a little by using a view on the filter (i.e. pool.view.filter(e => e.isVisible); then return Seq[T]). Generally, I think your strategy should be to not do extra filtering work each time. Keep track of your active enemies in a Set or something; then you have them when you need them.