Time complexity of System.arraycopy(...)?

I did some investigation and later decided to write a test code, here is what I have.

My testing code is given below:

import org.junit.Test; public class ArrayCopyTest { @Test public void testCopy() { for (int count = 0; count < 3; count++) { int size = 0x00ffffff; long start, end; Integer[] integers = new Integer[size]; Integer[] loopCopy = new Integer[size]; Integer[] systemCopy = new Integer[size]; for (int i = 0; i < size; i++) { integers[i] = i; } start = System.currentTimeMillis(); for (int i = 0; i < size; i++) { loopCopy[i] = integers[i]; } end = System.currentTimeMillis(); System.out.println("for loop: " + (end - start)); start = System.currentTimeMillis(); System.arraycopy(integers, 0, systemCopy, 0, size); end = System.currentTimeMillis(); System.out.println("System.arrayCopy: " + (end - start)); } } } 

It produces result shown below

for loop: 47 System.arrayCopy: 24 for loop: 31 System.arrayCopy: 22 for loop: 36 System.arrayCopy: 22 

So, Bragboy is correct.

Here's some relevant source code from OpenJDK 8 (openjdk-8-src-b132-03_mar_2014). I found it with help from Java native method source code (note: instructions there are confusing; I just searched the source for relevant identifiers). I think Captain Ford's comment is correct; i.e., there are (many) cases where iterating each element isn't necessary. Note that not iterating each element doesn't necessarily mean O(1), it just means "faster". I think that, regardless, an array copy must be fundamentally O(x), even if x isn't the number of items in the array; i.e., however you do it, copying gets more expensive with more elements in the array, and if you have a Very Big array, it will take a linearly Long Time. Caveat: I don't know for certain that this is the actual source code for the Java you are running; only that this is the only implementation I could find in the OpenJDK 8 source. I think that this is a cross-platform implementation, but I might be wrong -- I definitely haven't figured out how to build this code. See also: Differences between Oracle JDK and Open JDK. The following comes from: /openjdk/hotspot/src/share/vm/oops/objArrayKlass.cpp

// Either oop or narrowOop depending on UseCompressedOops. template <class T> void ObjArrayKlass::do_copy(arrayOop s, T* src, arrayOop d, T* dst, int length, TRAPS) { BarrierSet* bs = Universe::heap()->barrier_set(); // For performance reasons, we assume we are that the write barrier we // are using has optimized modes for arrays of references. At least one // of the asserts below will fail if this is not the case. assert(bs->has_write_ref_array_opt(), "Barrier set must have ref array opt"); assert(bs->has_write_ref_array_pre_opt(), "For pre-barrier as well."); if (s == d) { // since source and destination are equal we do not need conversion checks. assert(length > 0, "sanity check"); bs->write_ref_array_pre(dst, length); Copy::conjoint_oops_atomic(src, dst, length); } else { // We have to make sure all elements conform to the destination array Klass* bound = ObjArrayKlass::cast(d->klass())->element_klass(); Klass* stype = ObjArrayKlass::cast(s->klass())->element_klass(); if (stype == bound || stype->is_subtype_of(bound)) { // elements are guaranteed to be subtypes, so no check necessary bs->write_ref_array_pre(dst, length); Copy::conjoint_oops_atomic(src, dst, length); } else { // slow case: need individual subtype checks // note: don't use obj_at_put below because it includes a redundant store check T* from = src; T* end = from + length; for (T* p = dst; from < end; from++, p++) { // XXX this is going to be slow. T element = *from; // even slower now bool element_is_null = oopDesc::is_null(element); oop new_val = element_is_null ? oop(NULL) : oopDesc::decode_heap_oop_not_null(element); if (element_is_null || (new_val->klass())->is_subtype_of(bound)) { bs->write_ref_field_pre(p, new_val); *p = *from; } else { // We must do a barrier to cover the partial copy. const size_t pd = pointer_delta(p, dst, (size_t)heapOopSize); // pointer delta is scaled to number of elements (length field in // objArrayOop) which we assume is 32 bit. assert(pd == (size_t)(int)pd, "length field overflow"); bs->write_ref_array((HeapWord*)dst, pd); THROW(vmSymbols::java_lang_ArrayStoreException()); return; } } } } bs->write_ref_array((HeapWord*)dst, length); } 

Just to sum up relevant comments on another question (flagged as a duplicate of this one).

Surely, it's just adding to the new array with all the entries of the other? Which would be O(n) where n is the number of values to be added.

bragboy's answer agrees of course, but then I had thought that the only way to get a sure answer was to find the source code to get a canonical answer, but that isn't possible. Here is the declaration for System.arraycopy();

public static native void arraycopy(Object src, int src_position, Object dst, int dst_position, int length); 

It's native, written in the language of the operating system, which means that the implementation of arraycopy() is platform dependant.

So, in conclusion it's likely O(n), but maybe not.

I don't understand how Kowser's answer answers his own question. I thought to check the time complexity of an algorithm You have to compare its running time for inputs of different sizes, like this:

import org.junit.Test; public class ArrayCopyTest { @Test public void testCopy() { int size = 5000000; for (int count = 0; count < 5; count++) { size = size * 2; long start, end; Integer[] integers = new Integer[size]; Integer[] systemCopy = new Integer[size]; start = System.currentTimeMillis(); System.arraycopy(integers, 0, systemCopy, 0, size); end = System.currentTimeMillis(); System.out.println(end - start); } } } 

Output:

10 22 42 87 147