Array and ArrayList performances for an expanding number of items (not a question)

Processing
1

At last I decided to take the time to write some code to test wether ArrayList of regular arrays are the fastest for stuff like particles (my own objects, with an expanding array size).
My test code is not very interesting but I think the answer will be for those who have the same needs and who never tested it. It turns out that with a growing array (at the end I have >30 000 items in the array), ArrayList is way faster than regular arrays.
With the ArrayList, walking through 30162 instances of my class takes around 400 milliseconds, when the same amout of instances require over 2000 milliseconds.
ArrayList wins, then.

Here is the ArrayList tryout :

ArrayList<poin> allPoints;
int cx,cy;
int begining;

void setup(){
  begining = millis();
  size(640,640);
  cx=width/2;cy=height/2;
  allPoints = new ArrayList(0); 
}

void draw(){
  background(255);
  int t=millis();
  ArrayList<poin> newAllPoints=new ArrayList();
  for(poin p:allPoints){
    p.avance();
    if(p.alive){
      newAllPoints.add(p);
    }
  }
  float ang=TWO_PI/frameCount;
  for(float a=0;a<TWO_PI;a+=ang){
    newAllPoints.add(new poin(cx, cy, a));
  }
  allPoints=newAllPoints;
  float ecouled=millis()-t;
  println(allPoints.size(), ecouled, allPoints.size()/(ecouled/1000));
  if(allPoints.size()>30000){println("total time : "+(millis()-begining));noLoop();}
}

class poin{
  float x,y,a;boolean alive=true;
  poin(float x, float y, float a){
  this.x=x;this.y=y;this.a=a;
  }
  void avance(){
    if(x<0||y<0||x>width||y>height)alive=false;
    x+=cos(a)*2;y+=sin(a)*2;
    point(x,y);
  }
}

and now the regular Array tryout :

poin[] allPoints;
int cx,cy;
int begining;

void setup(){
  begining = millis();
  size(640,640);
  cx=width/2;cy=height/2;
  allPoints = new poin[0]; 
}

void draw(){
  background(255);
  int t=millis();
 poin[] newAllPoints = new poin[0];  
  for(poin p:allPoints){
    p.avance();
    if(p.alive){
      newAllPoints = (poin[]) append(newAllPoints, p); 
    }
  }
  float ang=TWO_PI/frameCount;
  for(float a=0;a<TWO_PI;a+=ang){
      newAllPoints = (poin[]) append(newAllPoints, new poin(cx, cy, a));  
  }
  allPoints=newAllPoints;
  float ecouled=millis()-t;
  println(allPoints.length, ecouled,allPoints.length/(ecouled/1000));
  if(allPoints.length>30000){println("total time : "+(millis()-begining));noLoop();}
}

class poin{
  float x,y,a;boolean alive=true;
  poin(float x, float y, float a){
  this.x=x;this.y=y;this.a=a;
  }
  void avance(){
    if(x<0||y<0||x>width||y>height)alive=false;
    x+=cos(a)*2;y+=sin(a)*2;
    point(x,y);
  }
}

I can’t say if it stays true with P5js.

5 Likes
2

Did you test whether append is the problem?

I mean, would in a non-growing scenario the ArrayList still be faster when we don’t change the number of items?

3

I didn’t test that, I maybe should :slight_smile:

1 Like
4

p5.js doesn’t have ArrayLists, so there isn’t a comparable benchmarking problem. JavaScript arrays also serve as arraylists.

In general, arrays may be slightly faster for a fixed size, ArrayLists are almost always faster for continual resizing. An ArrayList is actually backed by an array, but they manage periodic size reallocation for you (which is expensive) in ways that usually prevent it from having to happen every operation – for example, upping the allocation by increasing chunk sizes to minimize the frequency of copying.

That said, you did the right thing – when in doubt, test, as the specific ways you use it in your code matter a lot for the performance profile.

2 Likes