December 2010


Options: Use Monospaced Font
Show Text Part by Default
Show All Mail Headers

Message: [<< First] [< Prev] [Next >] [Last >>]
Topic: [<< First] [< Prev] [Next >] [Last >>]
Author: [<< First] [< Prev] [Next >] [Last >>]

Print Reply
Sean Luke <[log in to unmask]>
Reply To:
MASON Multiagent Simulation Toolkit <[log in to unmask]>
Fri, 31 Dec 2010 15:26:10 -0500
text/plain (55 lines)
I'm investigating the possibility of migrating from Bag to ArrayList  

MASON has Bag because when MASON was created, ArrayList was very very  
slow.  Due to a potent stupidity on part of Sun's java library coding  
monkeys, ArrayList's get() and set() methods require a non-inlinable  
method call. For example, ArrayList's get() method does this:

     public Object get(int index) {
	return elementData[index];

     private void RangeCheck(int index) {
	if (index >= size)
	    throw new IndexOutOfBoundsException(
		"Index: "+index+", Size: "+size);

get() can be inlined, but RangeCheck() could not, because it throws an  
exception.  And RangeCheck is called *every* time get() is called so  
get() still effectively requires a non-inlined method call every time  
you call it.  This could trivially be fixed like this:

      public Object get(int index) {
	if (index >= size) RangeCheck(index);
	return elementData[index];

Boom!  Radical speed increases.  To make things even faster, Bag also  
allows direct access to its arrays if you're careful.

BUT: As of Java 1.6 (maybe 1.5), methods can now be inlined even if  
they potentially throw exceptions.  This is a big deal because it  
makes ArrayList's get() and set() methods etc. as fast as Bag's  
methods.  In fact, due to HotSpot's weirdness in compiling, they're  
actually can be somewhat faster now.  And IN FACT, they're even  
slightly faster in certain microbenchmarks than accessing the array  
directly!  Clearly HotSpot's team has worked hard to tune HotSpot for  
ArrayList while Java's library team has sat around on their rear ends  
neglecting to fix ten-year-old code stupidities.

As a result, I think ArrayList's successful inlining in 1.6 means that  
there's no good reason to keep Bag.  Changing MASON wholesale from Bag  
to ArrayList would be painful for everyone, hardly backward  
compatible.  If we did it, we'd probably have two simultaneous kinds  
of MASON available for one version revision, one using Bag and one  
using ArrayList.

So opinions on what to do?  How to do it?  Or whether to do it?