The System.arraycopy() Magic

[P. S. This article is now two hardware generations obsolete. It's point is now even more valid than when it was written.]

If you've used Java's System.arraycopy() to copy array elements, you've probably noticed that it is brilliantly fast on PCs. Here I'll show why, but first, consider an example of its use.

A Typical System.arraycopy() Use

Let's write a little program for the local animal shelter. We'll create a Dog class that identifies breed, name, weight and other dog characteristics. Then we'll create an array: 

        Dog[] dogs = new Dog[100];
That will lists all the dogs in the shelter. Of course even if 100 is the shelter's current capacity, you'll have to have a mechanism for expanding that array as sooner or later the shelter will be expanded (or just over-filled). Here's a fragment that will expand the array. 

        Dog[] temp = new Dog[150];
        System.arraycopy(dogs, 0, temp, 0, 100);
        dogs = temp;
That copies from dogs, starting at element 0, to temp, starting at element 0, 100 total elements. It's a typical use of System.arraycopy(). Of course, for our shelter the speed of this little bit of code is irrelevant. But let's scale up.

Based on the success of this little program, you're now going to have an array that tracks every dog in every shelter in the EU. Congratulations! And don't change the basic methodology. Using a System.arraycopy() for millions of Dog references will be virtually instantaneous.

System.arraycopy Builds on REPZ MOVS

Why is that method so fast on a PC? It maps down to a basic instruction in the Intel architecture: REPZ MOVS. The REPZ prefix means "repeat until zero" and the MOVS instruction copies a value from one location to another. This is what happens under the covers.

A register is a storage location within the CPU. Lets say you have an address register named "source" and another named "dest". Then you have a count register named "count".

Programming in assembler you would load these registers with the addresses of your source array and destination array, and you'd put the number of elements to be moved into the count array. Then you'd be ready for a rapid move.

In a loop, you'd copy the value at the address in "source" to the address in "dest". Then you'd increment both addresses. Now decrement the count register. and repeat, stopping when the count register gets down to zero. In C that would look like this: 


        do { *dest++ = *source++ } while ( --count > 0 );

In pseudo-assembler, it would be this: 


        start_move:
            MOV source, dest ; copy value from source to dest
            INCR source ; increment register
            INCR dest
            DECR count ; decrement, setting zero flag
            JNZ start_move ; jump if count is non-zero
That is exactly what the REPZ MOVS instruction does - copy a value, increment source and dest registers, decrement the count register and keep going until the count reaches zero. It executes the entire loop without needing any more instructions.

System.arraycopy() - a Speed King

Timing my machine shows that it only takes about two clock cycles to copy each value. That would be two milliseconds per million values at 1GHz.

How does Java take advantage of this instruction? Did Sun hire assembler programmers for each machine type?

Probably not. They didn't have to.

Going back to the early days of PCs, the C compiler business was very competitive. One of the benchmark tests used to compare compilers was the speed of the library function copy(). The C compiler vendors eventually hand-coded copy() in assembler to take advantage of the Intel REPZ MOVS instruction. Since then, C++ inherited that old hand code, and Java also inherited it.

Summary

Did you ever wonder why you never noticed even a slight pause when your ArrayList needed to expand? That's the magic of System.arraycopy().

© 2005 by Martin Rinehart

Java consultant home page icon

Back to Articles