assignment - copy array javascript
¿Por qué clone() es la mejor manera de copiar arrays? (5)
Es una pena para mí, pero no sabía que:
Deberías usar el clon para copiar matrices, porque esa es generalmente la forma más rápida de hacerlo.
como Josh Bloch afirma en este blog: http://www.artima.com/intv/bloch13.html
Siempre usé System.arraycopy(...) . Ambos enfoques son nativos, así que probablemente sin profundizar en las fuentes de las bibliotecas no puedo entender por qué es así.
Mi pregunta es simple: ¿por qué es la forma más rápida? ¿Cuál es la diferencia con La diferencia se explica here , pero no responde a la pregunta de por qué Josh Bloch considera System.arraycopy ?clone() como la forma más rápida.
En cuanto a la copia, System.arrayCopy es el más rápido, entonces y ahora.
-
System.arrayCopyno crea una nueva matriz y no se puede superar en velocidad de copia sinSystem.arrayCopy. -
Arrays.copyOfsimplemente crea una matriz y llama aarrayCopy. Conveniencia. -
Array.clonees altamente eficiente, pero necesita vaciar los datos copiados a todo el caché de la CPU.
Si puede codificar de una manera que reutilice el array con arrayCopy , arrayCopy . De lo contrario, personalmente recomiendo copyOf dada la tendencia ascendente de los cpu cores y porque el clon se considera antiguo y problematic en general, el punto principal del http://www.artima.com/intv/bloch13.html que inició esta pregunta.
Contrariamente a lo que se piensa, los bucles de copia reales (tipo marcado o no) no son bytecode de Java y no son optimizables por hotspot. Los bucles están codificados en C ++ y son implementaciones jvm de bajo nivel.
Respuesta larga:
Esta respuesta se basa y enlaza con el código fuente de OpenJDK 8, que, por lo que sé, debería ser el mismo para Sun.
Copia de matriz es quizás más complicada de lo que piensa la mayoría de la gente. A nivel de código C, se puede dividir en tres casos:
- Las matrices primitivas se copian directamente con un bucle de copia .
- Las matrices de objetos de la misma clase, o subclase a la matriz de super clase, también se copian directamente .
- De lo contrario, entre matrices de diferentes clases, se realiza una verificación de tipo en cada elemento .
La velocidad absoluta de copiar una matriz variará mucho dependiendo del tipo de matriz. Sin embargo, la velocidad relativa de los tres métodos de clonación no lo hace, ya que todos se resuelven en el mismo bucle de copia, un C ++ en línea o un bucle de ensamblaje. Por lo tanto, la diferente velocidad se debe principalmente a los gastos generales y otros factores.
System.arrayCopyes esencialmente verificaciones de tipo y de longitud, y luego directamente al bucle de copia. En mis propias pruebas,arrayCopysiempre es más rápido que los otros dos métodos más allá de cualquier margen de error.Arrays.copyOfsimplemente llama aSystem.arrayCopy- después de crear una nueva matriz. Tenga en cuenta que no llama a Array.clone. Contrariamente al comment de Radiodef, no hay ninguna indicación de que Java 8 omita la inicialización de cero.Array.clonees interesante. Llama directamente a la asignación del montón y al bucle de copia, con controles mínimos. Por lo tanto, la creación de su matriz debería ser más rápida queArrays.copyOf, y su copia tan rápida comoSystem.arrayCopysi no es más rápida.
Pero en mis pruebas, Array.clone es un poco más lento que copyOf .
Sospecho que es debido a la barrera de la memoria después de la copia. Al igual que un constructor, el clone se asegurará de que los datos copiados sean visibles para todos los subprocesos, lo que ni System.arrayCopy ni Array.copyOf hacen. Esto significa que Array.clone necesita dedicar tiempo a esperar el caché de la CPU para actualizar.
Si esto es cierto, el resultado de Array.clone vs Arrays.copyOf depende de si la descarga de caché del clone es más rápida que la sobrecarga de copyOf , y debe ser dependiente de la plataforma.
Aparte de esto, dado que la clonación siempre da como resultado una matriz del mismo tipo, los tres métodos utilizan en última instancia el mismo bucle de copia.
Si solo desea copiar, arrayCopy siempre es más rápido, simplemente porque no crea una nueva matriz. Para el resto, si la lista de correo de Java es algo para pasar, la elección entre Arrays.copyOf y Array.clone debería ser en gran medida una cuestión de gustos .
Mi resultado de la prueba jmh y el código de abajo.
- Pruebas unidireccionales devuelven una matriz copiada
- Las pruebas bidireccionales sobrescriben el origen de la copia, lo que obliga al siguiente clon a copiar datos "nuevos".
-
NoCloneno clona nada y es un criterio para asegurarse de que más alto sea más rápido.
Como se indicó, Clone y CopyOf es una carrera cerrada y su millaje puede variar.
/* # Run complete. Total time: 00:06:44
Benchmark Mode Cnt Score Error Units
MyBenchmark.ArrayCloneByteOneWay thrpt 20 1048588.503 ± 2608.862 ops/s
MyBenchmark.ArrayCloneByteTwoWay thrpt 20 523782.848 ± 1613.823 ops/s
MyBenchmark.ArrayCloneObjOneWay thrpt 20 260903.006 ± 1311.827 ops/s
MyBenchmark.ArrayCloneObjTwoWay thrpt 20 129448.639 ± 1179.122 ops/s
MyBenchmark.ArraysCopyOfByteOneWay thrpt 20 1065995.804 ± 2197.919 ops/s
MyBenchmark.ArraysCopyOfByteTwoWay thrpt 20 533025.610 ± 2831.955 ops/s
MyBenchmark.ArraysCopyOfObjOneWay thrpt 20 266134.565 ± 1536.756 ops/s
MyBenchmark.ArraysCopyOfObjTwoWay thrpt 20 130821.380 ± 274.325 ops/s
MyBenchmark.NoClone thrpt 20 308776528.157 ± 2546848.128 ops/s
MyBenchmark.SystemArrayCopyByteOneWay thrpt 20 1232733.367 ± 8439.409 ops/s
MyBenchmark.SystemArrayCopyByteTwoWay thrpt 20 859387.983 ± 1919.359 ops/s
MyBenchmark.SystemArrayCopyObjOneWay thrpt 20 239532.442 ± 775.193 ops/s
MyBenchmark.SystemArrayCopyObjTwoWay thrpt 20 167235.661 ± 503.141 ops/s
*/
import java.util.Arrays;
import java.util.Random;
import org.openjdk.jmh.annotations.*;
@Fork(2) @Warmup(iterations = 5, time = 1) @Measurement(iterations = 10, time = 1)
public class Q46230557 {
private static final int ARRAY_SIZE = 8192;
@State(Scope.Thread) public static class Data {
public byte[] bytes = new byte[ ARRAY_SIZE ];
public Object[] objs = new Object[ ARRAY_SIZE ];
@Setup public void setup() {
final Random RNG = new Random();
RNG.nextBytes( bytes );
for ( int i = 0 ; i < ARRAY_SIZE ; i++ )
objs[i] = RNG.nextInt();
}
}
@Benchmark public byte[] NoClone( final Data data ) {
return data.bytes;
}
@Benchmark public byte[] SystemArrayCopyByteOneWay( final Data data ) {
final byte[] dest = new byte[ ARRAY_SIZE ];
System.arraycopy( data.bytes, 0, dest, 0, ARRAY_SIZE );
return dest;
}
@Benchmark public byte[] SystemArrayCopyByteTwoWay( final Data data ) {
final byte[] buf = new byte[ ARRAY_SIZE ];
System.arraycopy( data.bytes, 0, buf, 0, ARRAY_SIZE );
System.arraycopy( buf, 0, data.bytes, 0, ARRAY_SIZE );
return data.bytes;
}
@Benchmark public byte[] ArraysCopyOfByteOneWay( final Data data ) {
return Arrays.copyOf( data.bytes, ARRAY_SIZE );
}
@Benchmark public byte[] ArraysCopyOfByteTwoWay( final Data data ) {
final byte[] buf = Arrays.copyOf( data.bytes, ARRAY_SIZE );
return data.bytes = Arrays.copyOf( buf, ARRAY_SIZE );
}
@Benchmark public byte[] ArrayCloneByteOneWay( final Data data ) {
return data.bytes.clone();
}
@Benchmark public byte[] ArrayCloneByteTwoWay( final Data data ) {
final byte[] buf = data.bytes.clone();
return data.bytes = buf.clone();
}
@Benchmark public Object[] SystemArrayCopyObjOneWay( final Data data ) {
final Object[] dest = new Object[ ARRAY_SIZE ];
System.arraycopy( data.objs, 0, dest, 0, ARRAY_SIZE );
return dest;
}
@Benchmark public Object[] SystemArrayCopyObjTwoWay( final Data data ) {
final Object[] buf = new Object[ ARRAY_SIZE ];
System.arraycopy( data.objs, 0, buf, 0, ARRAY_SIZE );
System.arraycopy( buf, 0, data.objs, 0, ARRAY_SIZE );
return data.objs;
}
@Benchmark public Object[] ArraysCopyOfObjOneWay( final Data data ) {
return Arrays.copyOf( data.objs, ARRAY_SIZE );
}
@Benchmark public Object[] ArraysCopyOfObjTwoWay( final Data data ) {
final Object[] buf = Arrays.copyOf( data.objs, ARRAY_SIZE );
return data.objs = Arrays.copyOf( buf, ARRAY_SIZE );
}
@Benchmark public Object[] ArrayCloneObjOneWay( final Data data ) {
return data.objs.clone();
}
@Benchmark public Object[] ArrayCloneObjTwoWay( final Data data ) {
final Object[] buf = data.objs.clone();
return data.objs = buf.clone();
}
}
La diferencia en el rendimiento proviene de omitir el paso donde la matriz se pone a cero.
public static int[] copyUsingArraycopy(int[] original)
{
// Memory is allocated and zeroed out
int[] copy = new int[original.Length];
// Memory is copied
System.arraycopy(original, 0, copy, 0, original.length);
}
public static int[] copyUsingClone(int[] original)
{
// Memory is allocated, but not zeroed out
// Unitialized memory is then copied into
return (int[])original.clone();
}
Sin embargo, en los casos en que el rendimiento de la copia de una matriz hace una diferencia significativa, generalmente es mejor emplear doble búfer.
int[] backBuffer = new int[BUFFER_SIZE];
int[] frontBuffer = new int[BUFFER_SIZE];
...
// Swap buffers
int[] temp = frontBuffer;
frontBuffer = backBuffer;
backBuffer = temp;
System.arraycopy(frontBuffer, 0, backBuffer, 0, BUFFER_SIZE);
Me gustaría hacer algunas observaciones sobre por qué clone() es la forma más rápida de copiar una matriz que System.arraycopy(..) u otras:
1. clone() no tiene que hacer la comprobación de tipo antes de copiar una matriz de origen a la de destino como se indica here . Simplemente asigna nuevo espacio de memoria y le asigna los objetos. Por otro lado, System.arraycopy(..) comprueba el tipo y luego copia una matriz.
2. clone() también rompe la optimización para eliminar la reducción a cero redundante. Como sabe, cada matriz asignada en Java debe inicializarse con 0s o valores predeterminados respectivos. Sin embargo, JIT puede evitar poner a cero esta matriz si ve que la matriz se llena justo después de la creación. Eso lo hace definitivamente más rápido en comparación con el cambio de los valores de copia con 0s existentes o valores predeterminados respectivos. Al usar System.arraycopy(..) pasa una cantidad significativa de tiempo en borrar y copiar la matriz inicializada. Para ello he realizado algunas de las pruebas de referencia.
@BenchmarkMode(Mode.Throughput)
@Fork(1)
@State(Scope.Thread)
@Warmup(iterations = 10, time = 1, batchSize = 1000)
@Measurement(iterations = 10, time = 1, batchSize = 1000)
public class BenchmarkTests {
@Param({"1000","100","10","5", "1"})
private int size;
private int[] original;
@Setup
public void setup() {
original = new int[size];
for (int i = 0; i < size; i++) {
original[i] = i;
}
}
@Benchmark
public int[] SystemArrayCopy() {
final int length = size;
int[] destination = new int[length];
System.arraycopy(original, 0, destination, 0, length);
return destination;
}
@Benchmark
public int[] arrayClone() {
return original.clone();
}
}
Salida:
Benchmark (size) Mode Cnt Score Error Units
ArrayCopy.SystemArrayCopy 1 thrpt 10 26324.251 ± 1532.265 ops/s
ArrayCopy.SystemArrayCopy 5 thrpt 10 26435.562 ± 2537.114 ops/s
ArrayCopy.SystemArrayCopy 10 thrpt 10 27262.200 ± 2145.334 ops/s
ArrayCopy.SystemArrayCopy 100 thrpt 10 10524.117 ± 474.325 ops/s
ArrayCopy.SystemArrayCopy 1000 thrpt 10 984.213 ± 121.934 ops/s
ArrayCopy.arrayClone 1 thrpt 10 55832.672 ± 4521.112 ops/s
ArrayCopy.arrayClone 5 thrpt 10 48174.496 ± 2728.928 ops/s
ArrayCopy.arrayClone 10 thrpt 10 46267.482 ± 4641.747 ops/s
ArrayCopy.arrayClone 100 thrpt 10 19837.480 ± 364.156 ops/s
ArrayCopy.arrayClone 1000 thrpt 10 1841.145 ± 110.322 ops/s
De acuerdo con las salidas, System.arraycopy(..) que el clone es casi el doble de rápido de System.arraycopy(..)
3. Además, el uso del método de copia manual como clone() da como resultado resultados más rápidos porque no tiene que realizar ninguna llamada a VM (a diferencia de System.arraycopy() ).
Por un lado, clone() no tiene que hacer la comprobación de tipos que hace System.arraycopy() .
Quiero corregir y complementar las respuestas anteriores.
- Object.clone usa una implementación System.arraycopy sin marcar para arreglos;
- La principal mejora de rendimiento de Object.clone, es la inicialización de la memoria RAW directamente. En el caso de System.arraycopy, también intenta combinar la inicialización de la matriz con la operación de copia, como podemos ver en el código fuente, pero también realiza diferentes comprobaciones adicionales para esto, a diferencia de Object.clone. Si solo desactivas esta función (ver más abajo), entonces el rendimiento sería mucho más cercano (particularmente en mi hardware).
- Una cosa más interesante es sobre Young vs Old Gen. En el caso de que cuando la matriz de origen esté alineada y dentro de Old Gen, ambos métodos tengan un rendimiento cercano.
- Cuando copiamos matrices primitivas, System.arraycopy siempre utiliza generate_unchecked_arraycopy.
- Depende de las implementaciones dependientes de hardware / sistema operativo, así que no confíe en los puntos de referencia y suposiciones, verifique su propiedad.
Explicación
En primer lugar, el método de clonación y System.arraycopy son intrínsecos. Object.clone y System.arraycopy utilizan generate_unchecked_arraycopy. Y si profundizamos, podríamos ver que después de ese HotSpot seleccionamos una implementación concreta, dependiente del sistema operativo, etc.
Largamente Veamos el código de Hotspot . En primer lugar, veremos que Object.clone (LibraryCallKit :: inline_native_clone) utiliza generate_arraycopy, que se usó para System.arraycopy en el caso de -XX: -ReduceInitialCardMarks . De lo contrario, lo hace LibraryCallKit :: copy_to_clone, que inicializa la nueva matriz en la memoria RAW (si -XX: + ReduceBulkZeroing, que está habilitada de forma predeterminada). En contraste, System.arraycopy utiliza genera_arraycopy directamente, intenta verificar ReduceBulkZeroing (y muchos otros casos) y elimina la puesta a cero de la matriz, con las comprobaciones adicionales mencionadas y también realizaría verificaciones adicionales para asegurarse de que todos los elementos estén inicializados, a diferencia de Object.clone. Finalmente, en el mejor de los casos, ambos utilizan generate_unchecked_arraycopy.
A continuación muestro algunos puntos de referencia para ver este efecto en la práctica:
- El primero es solo un punto de referencia simple, la única diferencia con la respuesta anterior, que los arreglos no están ordenados; Vemos que la copia de arrays es más lenta (pero no dos veces), resultados: https://pastebin.com/ny56Ag1z ;
- En segundo lugar, agrego la opción -XX: -ReduceBulkZeroing y ahora veo que el rendimiento de ambos métodos es muy cercano. Resultados - https://pastebin.com/ZDAeQWwx ;
- También asumo que tendremos la diferencia entre Old / Young, debido a la alineación de las matrices (es una característica de Java GC, cuando llamamos GC, la alineación de las matrices cambia, es fácil de observar usando JOL ). Me sorprendió que el rendimiento se convierta en el mismo, en general, y en una baja de calificación para ambos métodos. Resultados - https://pastebin.com/bTt5SJ8r . Para quienes creen en números concretos, el rendimiento de System.arraycopy es mejor que Object.clone.
Primer punto de referencia:
import org.openjdk.jmh.annotations.*;
import org.openjdk.jmh.runner.Runner;
import org.openjdk.jmh.runner.options.OptionsBuilder;
import java.util.concurrent.ThreadLocalRandom;
import java.util.concurrent.TimeUnit;
@State(Scope.Benchmark)
@BenchmarkMode(Mode.All)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
public class CloneVsArraycopy {
@Param({"10", "1000", "100000"})
int size;
int[] source;
@Setup(Level.Invocation)
public void setup() {
source = create(size);
}
@Benchmark
public int[] clone(CloneVsArraycopy cloneVsArraycopy) {
return cloneVsArraycopy.source.clone();
}
@Benchmark
public int[] arraycopy(CloneVsArraycopy cloneVsArraycopy) {
int[] dest = new int[cloneVsArraycopy.size];
System.arraycopy(cloneVsArraycopy.source, 0, dest, 0, dest.length);
return dest;
}
public static void main(String[] args) throws Exception {
new Runner(new OptionsBuilder()
.include(CloneVsArraycopy.class.getSimpleName())
.warmupIterations(20)
.measurementIterations(20)
.forks(20)
.build()).run();
}
private static int[] create(int size) {
int[] a = new int[size];
for (int i = 0; i < a.length; i++) {
a[i] = ThreadLocalRandom.current().nextInt();
}
return a;
}
}
Al ejecutar esta prueba en mi PC, obtuve esto: https://pastebin.com/ny56Ag1z . La diferencia no es tan grande, pero sigue existiendo.
El segundo punto de referencia solo agrego una configuración -XX: -ReduceBulkZeroing y obtuve estos resultados https://pastebin.com/ZDAeQWwx . No vemos que para Young Gen la diferencia es mucho menor también.
En el tercer punto de referencia, cambié solo el método de configuración y habilité la opción ReducirBulkZeroing de nuevo:
@Setup(Level.Invocation)
public void setup() {
source = create(size);
// try to move to old gen/align array
for (int i = 0; i < 10; ++i) {
System.gc();
}
}
La diferencia es mucho menor (tal vez en el intervalo de error) - https://pastebin.com/bTt5SJ8r .
Renuncia
También podría estar equivocado. Usted debe comprobar por su cuenta.
en adición
Creo que es interesante ver el proceso de los puntos de referencia:
# Benchmark: org.egorlitvinenko.arrays.CloneVsArraycopy.arraycopy
# Parameters: (size = 50000)
# Run progress: 0,00% complete, ETA 00:07:30
# Fork: 1 of 5
# Warmup Iteration 1: 8,870 ops/ms
# Warmup Iteration 2: 10,912 ops/ms
# Warmup Iteration 3: 16,417 ops/ms <- Hooray!
# Warmup Iteration 4: 17,924 ops/ms <- Hooray!
# Warmup Iteration 5: 17,321 ops/ms <- Hooray!
# Warmup Iteration 6: 16,628 ops/ms <- What!
# Warmup Iteration 7: 14,286 ops/ms <- No, stop, why!
# Warmup Iteration 8: 13,928 ops/ms <- Are you kidding me?
# Warmup Iteration 9: 13,337 ops/ms <- pff
# Warmup Iteration 10: 13,499 ops/ms
Iteration 1: 13,873 ops/ms
Iteration 2: 16,177 ops/ms
Iteration 3: 14,265 ops/ms
Iteration 4: 13,338 ops/ms
Iteration 5: 15,496 ops/ms
Para Object.clone
# Benchmark: org.egorlitvinenko.arrays.CloneVsArraycopy.clone
# Parameters: (size = 50000)
# Run progress: 0,00% complete, ETA 00:03:45
# Fork: 1 of 5
# Warmup Iteration 1: 8,761 ops/ms
# Warmup Iteration 2: 12,673 ops/ms
# Warmup Iteration 3: 20,008 ops/ms
# Warmup Iteration 4: 20,340 ops/ms
# Warmup Iteration 5: 20,112 ops/ms
# Warmup Iteration 6: 20,061 ops/ms
# Warmup Iteration 7: 19,492 ops/ms
# Warmup Iteration 8: 18,862 ops/ms
# Warmup Iteration 9: 19,562 ops/ms
# Warmup Iteration 10: 18,786 ops/ms
Podemos observar la degradación de rendimiento aquí para System.arraycopy. Vi una imagen similar para Streams y hubo un error en los compiladores. Supongo que también podría ser un error en los compiladores. De todos modos, es extraño que después de 3 bajas de rendimiento de calentamiento.
ACTUALIZAR
¿Qué es sobre la comprobación de tipos?
import org.openjdk.jmh.annotations.*;
import org.openjdk.jmh.runner.Runner;
import org.openjdk.jmh.runner.options.OptionsBuilder;
import java.util.concurrent.ThreadLocalRandom;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicLong;
@State(Scope.Benchmark)
@BenchmarkMode(Mode.All)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
public class CloneVsArraycopyObject {
@Param({"100"})
int size;
AtomicLong[] source;
@Setup(Level.Invocation)
public void setup() {
source = create(size);
}
@Benchmark
@CompilerControl(CompilerControl.Mode.DONT_INLINE)
public AtomicLong[] clone(CloneVsArraycopyObject cloneVsArraycopy) {
return cloneVsArraycopy.source.clone();
}
@Benchmark
@CompilerControl(CompilerControl.Mode.DONT_INLINE)
public AtomicLong[] arraycopy(CloneVsArraycopyObject cloneVsArraycopy) {
AtomicLong[] dest = new AtomicLong[cloneVsArraycopy.size];
System.arraycopy(cloneVsArraycopy.source, 0, dest, 0, dest.length);
return dest;
}
public static void main(String[] args) throws Exception {
new Runner(new OptionsBuilder()
.include(CloneVsArraycopyObject.class.getSimpleName())
.jvmArgs("-XX:+UnlockDiagnosticVMOptions", "-XX:+PrintInlining", "-XX:-ReduceBulkZeroing")
.warmupIterations(10)
.measurementIterations(5)
.forks(5)
.build())
.run();
}
private static AtomicLong[] create(int size) {
AtomicLong[] a = new AtomicLong[size];
for (int i = 0; i < a.length; i++) {
a[i] = new AtomicLong(ThreadLocalRandom.current().nextLong());
}
return a;
}
}
No se observa la diferencia - pastebin.com/ufxCZVaC . Supongo que una explicación es simple, ya que System.arraycopy es muy intrínseca en ese caso, la implementación real estaría simplemente en línea sin ningún tipo de mecanografía, etc.
Nota
Estuve de acuerdo con Radiodef que podría encontrar interesante para leer la publicación del blog , el autor de este blog es el creador (o uno de los creadores) de JMH .