System.arraycopy speed

[Rob Shepherd]

I am wondering whether or not...

System.arraycopy() is a costly operation?

maybe for primitive[] is would take time but for Object[] it is surely just moving
reference data isn't it?

How many bytes makes up typical object reference data?

I am thinking about using ArrayList to make a FIFO

add(object) to enqueue

and

remove(0) to dequeue

but for every action there is a System.arraycopy

Or should i implement a circular queue type fixed length array?

 

[Roedy Green]

System.arraycopy() is a costly operation?

It is slightly slower than the equivalent for loop. It loses speed
because of its generality.

 

[Roedy Green]

How many bytes makes up typical object reference data?

usually 4 in a 32 bit addressing machine.

 

[Michael Borgwardt]

I am wondering whether or not...

System.arraycopy() is a costly operation?

define "costly". It *does* mean a native call, which is always overhead.
I once did a benchmark and found that it was slower than a "manual" loop-copy
for array slices smaller than a thousand elements or so.

maybe for primitive[] is would take time but for Object[] it is surely
just moving reference data isn't it?

Why do you believe that primitives are bigger than references (they're not)?

How many bytes makes up typical object reference data?

usually 32 or 64 bit - i.e. usually *bigger* than a primitive.

I am thinking about using ArrayList to make a FIFO

add(object) to enqueue

and

remove(0) to dequeue

but for every action there is a System.arraycopy

Or should i implement a circular queue type fixed length array?

That would be a great example of what NOT to do - sacrificing not just
clarity but *stability* for most likely irrelevant performance gains.

Most likely it doesn't matter at all because you'll be spending 95%
of the time on something you never thought about, but you can avoid the
arraycopy operations by using LinkedList instead.

 

[Michael Borgwardt]

It is slightly slower than the equivalent for loop. It loses speed
because of its generality.

No, it's in fact much faster for large arrays (nowadays even
somewhat faster for all but the smallest arrays) because it
uses a system copy routine.

Try out for yourself:

/**
* Benchmarks System.arraycopy() vs. a for loop
* Expects as command line arguments paris of array size and
* number of repetitions of the benchmark.
*
* @author Michael Borgwardt
*/
public class CopyTest
{
static byte[] in;
static byte[] out;

public static void main(String[] args)
{
try
{
for(int n=0; n<args.length/2; n++)
{
int size = Integer.parseInt(args[n*2]);
int iterations = Integer.parseInt(args[n*2+1]);

in = new byte[size];
out = new byte[size];

long arraycopyTime = 0;
long loopcopyTime = 0;

long before = System.currentTimeMillis();
for(int i=0; i<iterations; i++)
{
System.arraycopy(in, 0, out, 0, size);
}
arraycopyTime = System.currentTimeMillis() - before;
before = System.currentTimeMillis();
for(int i=0; i<iterations; i++)
{
for(int j=0; j<in.length; j++)
{
out[j] = in[j];
}
}
loopcopyTime = System.currentTimeMillis() - before;
System.out.println("Array size: "+size+", Repetitions: "+iterations);
System.out.println("Loop: "+loopcopyTime +"ms, System.arrayCopy:
"+arraycopyTime+"ms");
}
}
catch(Exception e)
{
e.printStackTrace();
}
}
}

 

[Rob Shepherd]

It is slightly slower than the equivalent for loop. It loses speed
because of its generality.

No, it's in fact much faster for large arrays (nowadays even
somewhat faster for all but the smallest arrays) because it
uses a system copy routine.

Try out for yourself:
[CHOP]
{
for(int j=0; j<in.length; j++)
{
out[j] = in[j];
}
}
[CHOP]

surely this would hotspot compile fairly simply?

it is just byte primitives, what about for objects that are dynamcally allocated and
placed into the arrays, there could be not much HS compiling done with that...

That would slow your loop example down wouldn't it?

Regards

Rob

 

[Michael Borgwardt]

surely this would hotspot compile fairly simply?

it is just byte primitives, what about for objects that are dynamcally
allocated and placed into the arrays, there could be not much HS
compiling done with that...

That would slow your loop example down wouldn't it?

Whether it's object references or primitives matters not one bit, certainly
not for whether the code can be "hotspot compiled". What *could* matter
is whether the compiler or the system routine can figure out that it's
repeatedly copying stuff that's the same (and in fact all zeroes, just
like the target array). But then the times should be close to zero and not
vary with array size, which they do.

 

[Roedy Green]

No, it's in fact much faster for large arrays (nowadays even
somewhat faster for all but the smallest arrays) because it
uses a system copy routine.

Knowledge keeps no better than fish. It seems like yesterday someone
posted benchmarks showing the opposite.

I was thinking about how I would have implemented arraycopy in
assembler. You could do the moves 32 bits at a pop in a Pentium, even
for byte arrays, with the tail end handled 16-bits then 8-bits at a
time. Since objects would likely be paragraph aligned in the JVM,
moves from one array to another should be very fast, so long at they
were both from offset 0 or a multiple of 16.

 

[JScoobyCed]

[ This is posted for future reference -- i.e. somebody looks for the results
of the benchmark, but too lazy to run it -- ]
For information about the benchmark(see previous thread from
M. Borgwardt), here are my results on a P4-2.8Ghz/1024 Mo:

/***********************/
Array size: 1000, Repetitions: 5
Loop: 0ms, System.arrayCopy:0ms

Array size: 1000, Repetitions: 500
Loop: 15ms, System.arrayCopy:0ms

Array size: 100000, Repetitions: 50
Loop: 31ms, System.arrayCopy:15ms

Array size: 100000, Repetitions: 500
Loop: 360ms, System.arrayCopy:31ms

Array size: 100000, Repetitions: 5000
Loop: 3640ms, System.arrayCopy:250ms
/********************************/

JScoobyCed
-------------

 

[Yu SONG]

[ This is posted for future reference -- i.e. somebody looks for the results
of the benchmark, but too lazy to run it -- ]
For information about the benchmark(see previous thread from
M. Borgwardt), here are my results on a P4-2.8Ghz/1024 Mo:

/***********************/
Array size: 1000, Repetitions: 5
Loop: 0ms, System.arrayCopy:0ms

Array size: 1000, Repetitions: 500
Loop: 15ms, System.arrayCopy:0ms

Array size: 100000, Repetitions: 50
Loop: 31ms, System.arrayCopy:15ms

Array size: 100000, Repetitions: 500
Loop: 360ms, System.arrayCopy:31ms

Array size: 100000, Repetitions: 5000
Loop: 3640ms, System.arrayCopy:250ms
/********************************/

Should also consider the following tests

Array size: 5, Repetitions: 1000
Array size: 500, Repetitions: 1000
Array size: 50, Repetitions: 100000
Array size: 500, Repetitions: 100000
Array size: 5000, Repetitions: 100000


--
Song

/* E-mail.c */
#define User "Yu.Song"
#define Warwick "warwick.ac.uk"
int main() {
printf("Yu Song's E-mail: %s@%s", User, Warwick);
return 0;}

Further Info. : http://www.dcs.warwick.ac.uk/~esubbn/
_______________________________________________________