Having (performance-critical) paths controlled by throwing/catching Exceptions is one of the worst anti-patterns around.
didn’t realise that removing objects caused such a performance hit for ArrayLists, so if you need to remove an object on a list where order doesn’t matter with a lower performance hit, how would you do it?
here my attempt not sure if its right
int index; // index of entity that needs removing
int last = myArrayList.size() - 1; // index of last entity in the list
myArrayList.set(index, myArrayList.get(last));
myArrayList.remove(last);
is that how you’d do it or is there another way?
Thats not the case here; this is because if I was to do if (index >= internalList.size()) {…} that would simply add another bound checking statement ontop of what the JVM does already…
Benchmark it, you’ll see…
DP
We (IMI) broke down and switched just about everything over to http://javolution.org/ collections.
I’ll never look back 
</knock wood>
My collection buffer/list/map thing was rather specialised; so it didn’t warrant moving everything to javolution although I have heard a few good things about it.
It doesn’t matter now anyway, I literally have a flat GC profile with yourkit.com; the list grows exponentially to start off with, but once it settles down, its fine…
DP
Horrible on so many levels, but its fast ;D
public class Bag{
private int capacity;
public Object []data;
public int size=0;
public Bag(){
this(10);
}
public Bag(int capacity){
this.capacity=capacity;
data=new Object[capacity];
}
public Object remove(int i){
Object o=data[i];
data[i]=data[--size];
data[size]=null;//kev was right... it really should be there for being dynamic n stuff
return o;
}
public void add(Object o){
size++;
if(size>capacity){
capacity=(capacity * 3)/2 + 1;
Object []oldData=data;
data=new Object[capacity];
System.arraycopy(oldData, 0, data, 0, oldData.length);
}
data[size-1]=o;
}
public static void main(String[]args){
Bag b=new Bag();
for(int i=0;i<5;i++)
b.add(new Integer(i));
System.out.println("\nbag contains:");
for(int i=0;i<b.size;i++)
System.out.println(b.data[i]);
for(int i=0;i<b.size;i++){
int k=((Integer)b.data[i]).intValue();
if(k%2==0){
System.out.println("remove:"+i+" -> "+b.data[i]);
b.remove(i--);
}else{
System.out.println("keep:"+i+" -> "+b.data[i]);
}
}
System.out.println("\nbag contains:");
for(int i=0;i<b.size;i++)
System.out.println(b.data[i]);
for(int i=0;i<b.size;i++){
int k=((Integer)b.data[i]).intValue();
if(k%2==1){
System.out.println("remove:"+i+" -> "+b.data[i]);
b.remove(i--);
}else{
System.out.println("keep:"+i+" -> "+b.data[i]);
}
}
System.out.println("\nbag contains:");
for(int i=0;i<b.size;i++)
System.out.println(b.data[i]);
}
}
import java.util.*;
public class ListWalk3{
ArrayList al=new ArrayList();
LinkedList ll=new LinkedList();
Bag bag=new Bag();
int numberOfElements=5000;
private void fill(){
System.out.println("filling");
for(int i=0;i<numberOfElements;i++){
Integer in=new Integer(i*10);
al.add(in);
ll.add(in);
bag.add(in);
}
System.out.println("done");
}
private void test(){
int repeat=5;
int runs=50000;
int iruns=10000;
long start,stop;
double[]sums=new double[3];
for(int r=0;r<repeat;r++){
start=System.currentTimeMillis();
for(int r2=0;r2<iruns;r2++){
for(int i=al.size()-1;i>=0;--i){
Object o=al.get(i);
}
}
stop=System.currentTimeMillis();
System.out.println("iterate[ArrayList backward] "+(double)(stop-start)/1000.0+" seconds");
sums[0]+=(double)(stop-start)/1000.0;
start=System.currentTimeMillis();
for(int r2=0;r2<iruns;r2++){
ListIterator itr=ll.listIterator();
while(itr.hasNext()){
Object o=itr.next();
}
}
stop=System.currentTimeMillis();
System.out.println("iterate[LinkedList listIterator] "+(double)(stop-start)/1000.0+" seconds");
sums[1]+=(double)(stop-start)/1000.0;
start=System.currentTimeMillis();
for(int r2=0;r2<iruns;r2++){
for(int i=bag.size-1;i>=0;--i){
Object o=bag.data[i];
}
}
stop=System.currentTimeMillis();
System.out.println("iterate[Bag] "+(double)(stop-start)/1000.0+" seconds");
sums[2]+=(double)(stop-start)/1000.0;
}
double[]sums2=new double[3];
double[]sums3=new double[3];
Integer in=new Integer(23);
for(int r=0;r<repeat;r++){
//add
start=System.currentTimeMillis();
for(int r2=0;r2<runs;r2++)
al.add(in);
stop=System.currentTimeMillis();
System.out.println("add[ArrayList] "+(double)(stop-start)/1000.0+" seconds");
sums2[0]+=(double)(stop-start)/1000.0;
start=System.currentTimeMillis();
for(int r2=0;r2<runs;r2++)
ll.add(in);
stop=System.currentTimeMillis();
System.out.println("add[LinkedList] "+(double)(stop-start)/1000.0+" seconds");
sums2[1]+=(double)(stop-start)/1000.0;
start=System.currentTimeMillis();
for(int r2=0;r2<runs;r2++)
bag.add(in);
stop=System.currentTimeMillis();
System.out.println("add[Bag] "+(double)(stop-start)/1000.0+" seconds");
sums2[2]+=(double)(stop-start)/1000.0;
//rem
start=System.currentTimeMillis();
for(int r2=0;r2<runs;r2++)
al.remove(0);
stop=System.currentTimeMillis();
System.out.println("rem[ArrayList] "+(double)(stop-start)/1000.0+" seconds");
sums3[0]+=(double)(stop-start)/1000.0;
start=System.currentTimeMillis();
for(int r2=0;r2<runs;r2++)
ll.remove(0);
stop=System.currentTimeMillis();
System.out.println("rem[LinkedList] "+(double)(stop-start)/1000.0+" seconds");
sums3[1]+=(double)(stop-start)/1000.0;
start=System.currentTimeMillis();
for(int r2=0;r2<runs;r2++)
bag.remove(0);
stop=System.currentTimeMillis();
System.out.println("rem[Bag] "+(double)(stop-start)/1000.0+" seconds");
sums3[2]+=(double)(stop-start)/1000.0;
}
String []labels={
"ArrayList :",
"LinkedList:",
"Bag :"};
System.out.println("\n\n"+numberOfElements+" elements\n");
System.out.println("\niterate "+iruns+" times");
for(int i=0;i<3;i++)
System.out.println(labels[i]+(sums[i]/repeat));
System.out.println("\nadd "+runs+" times");
for(int i=0;i<3;i++)
System.out.println(labels[i]+(sums2[i]/repeat));
System.out.println("\nrem "+runs+" times");
for(int i=0;i<3;i++)
System.out.println(labels[i]+(sums3[i]/repeat));
System.out.println("\nsum");
for(int i=0;i<3;i++)
System.out.println(labels[i]+" "+((sums[i]+sums2[i]+sums3[i])/repeat));
}
public static void main(String[]args){
ListWalk3 lw=new ListWalk3();
lw.fill();
lw.test();
}
}
iterate 10000 times
ArrayList :3.3147999999999995
LinkedList:6.014799999999999
Bag :0.7909999999999999
add 50000 times
ArrayList :0.01
LinkedList:0.13200000000000003
Bag :0.0062
rem 50000 times
ArrayList :15.0418
LinkedList:0.016
Bag :0.01
sum
ArrayList : 18.3666
LinkedList: 6.162799999999999
Bag : 0.8071999999999999
Couldnt be arsed to use bigger values for add/remove (for more meaningful results), since AL’s remove took bloody ages.
I wanted to know what this would mean in reality… so I took my (opengl accelerated) fuzetsu prototype and replaced the ArrayLists with Bag. With about 1600 bullets I got 80fps instead of 60fps (on a 500mhz machine!).
Really awesome ;D
edit: Btw with 1.5.0_07 and up using a get() wrap for the direct array acess is about equally fast. With 1.5.0_06 and earlier its about 30% slower.
this Bag class is really good and fast for gaming, totally blows ArrayList away for performance, gonna swap over from ArrayList to Bag
Mem usage difference?
Holy macarony, that’s awesome. ;D
I would guess that it’ll be the same. It’s basically doing what an ArrayList/Vector does, but not caring about ordering.
It’s funny that there isn’t something like this in java.util already. There’s lots of times you just want a collection of things without caring about order or set qualities.
Give me a wee while and I’ll knock up a version that implements java.util.Collection.
And there it is.
Untested though, who wants to make some unit tests? The behaviour should be identical to an ArrayList apart from the ordering, so it’d be pretty easy to test by performing some operations on a Bag and an ArrayList, dumping their contents to a arrays, sorting the arrays and testing if they are identical.
edit: Broken version removed
Why removefoo() instead of remove()? And there is some remove() some way down, which is sorta odd…
And over in clear()… calling Arrays.fill() looks nice n all, but it does more than necessary. From 0 to <size would be enough (everything after that is null anyways… see remove()).
indexOf() condition should be array[[b][/b]i].equals(o) instead of ==. Also… its important to do it this way around, because null.equals(something) wouldnt be nice
contains() can be written as return indexOf(o) >= 0; or return indexOf(o) != -1; (Either way there shouldnt be that == comparison loop.)
edit: oops… array[[b][/b]i] can be null aswell… so there has to be some check and seperate loops.
[quote=“oNyx,post:34,topic:28392”]
== is a lot faster than. equals, and works with null. So if that’s the behavior you want (very common in games), there’s no reason to change it. =)
[quote=“Markus_Persson,post:35,topic:28392”]
Well, yea, but its different stuff. Maybe other methods should be used for that… containsReference() and indexOfReference() perhaps?
Unexpected behaviour leads to weird bugs n glitches 
Well, yes, it’s already Strange Stuff, as it’s not quite a List, and not quite a Set. (and definitely not a Map)
Wah! looks like I should have checked through it more thoroughly. Cleaned-up version forthcoming.
There you are then:
removefoo embarrassment removed :
clear() only clears what it needs to
indexOf() object equality test is now as specified by the Collection interface
Constructors suggested by the Collection interface added
ensureCapacity() method added.
As someone who was bitten by this little humdinger, I could not agree more.
edit: Keep on scrollin’ pardner, a less buggy version can be found below.
Wow, that is really neat :D. far out, well done.
May I use the version you have been working on bleb? I can’t find a link.
‘Bag’ is a really funny name for this by the way - very suitable.
List, Map, Set all have some kind of level of respect, but a ‘Bag’ like a plastic bag is a peice of crap, its just useful for chucking stuff in. 8)
Thanks,
Keith
PS: does that version support generics?
EDIT: oops, now I see it as an attachment. Many thanks :).