A little array optimization

Thread view:

daniel.w.gelder@gmail.com - 23 Apr 2006 12:26 GMT

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

Reply to this Message

Adam Warner - 23 Apr 2006 15:20 GMT

On Sun, 23 Apr 2006 04:26:26 -0700, daniel.w.gelder wrote:

> 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:
[quoted text clipped - 21 lines]
> 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

Reply to this Message

Chris Uppal - 24 Apr 2006 09:17 GMT

> 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

Reply to this Message

A little array optimization

Free Magazines