A little array optimization

[daniel.w.gelder]

I have a stack class for a certain purpose which never needs to store
more than a few dozen doubles and was written like this:

static final double[] doubleStack = new double[128];
static int doubleStackIndex = 0;

// pushes and pops doubles.
public final static void pushDouble(double d)
{
doubleStack[(doubleStackIndex++) & 127] = d;
}
public final static double popDouble()
{
return doubleStack[(--doubleStackIndex) & 127];
}


I noticed that making doubleStack final and putting the & in the
expression gives a consistent 13% speed boost in the code:

for (int i = 0; i < 1000000; i++)
{ pushDouble(10); popDouble(); }

So that's one way to make arrays faster. Are there any other ones
anyone knows about? I'm about to write a very optimized program and
could use any tricks.

Enjoy
Dan

 

[Adam Warner]

I have a stack class for a certain purpose which never needs to store
more than a few dozen doubles and was written like this:

static final double[] doubleStack = new double[128];
static int doubleStackIndex = 0;

// pushes and pops doubles.
public final static void pushDouble(double d)
{
doubleStack[(doubleStackIndex++) & 127] = d;
}
public final static double popDouble()
{
return doubleStack[(--doubleStackIndex) & 127];
}


I noticed that making doubleStack final and putting the & in the
expression gives a consistent 13% speed boost in the code:

for (int i = 0; i < 1000000; i++)
{ pushDouble(10); popDouble(); }

So that's one way to make arrays faster. Are there any other ones
anyone knows about? I'm about to write a very optimized program and
could use any tricks.

That's a great optimisation for an object cache but a highly dangerous one
for a stack. You will silently corrupt your data if you overflow (i.e.
wrap around) the stack. This can sneak up on you with recursive data
structures.

If you have an Object stack that doesn't hold null you should be able to
increase the performance of the Object stack with a top of stack field.
When the field is null you can set it (push) without having to modify the
Object array. When the field is not null you can return and null it (pop)
without having to modify the Object array. Thus a push/pop/push/pop/...
stream never touches the Object array holding any remaining elements.

When you benchmark always remember to calculate and print a result to
avoid the code being optimised away. For example (untested):

long time=System.nanoTime();
pushDouble(0);
for (int i=0; i<1000000000; ++i) {
pushDouble(popDouble()+1);
}
double elapsedTime=(System.nanoTime()-time)/1000000000.0;
System.out.println("Elapsed time is "+elapsedTime+"s with result "+
popDouble());

Regards,
Adam

 

[Chris Uppal]

So that's one way to make arrays faster. Are there any other ones
anyone knows about? I'm about to write a very optimized program and
could use any tricks.

Run with the -server option if you are not doing so already. It does many of
the optimisations that you'd have to do "by hand" using -client.

And be /very, very/ careful about how you measure performance. Remember that
the JITer takes time to warm up. Remember that replacing the code for a
running method is harder than replacing the body of a method which has returned
(and will be called again later).

-- chris