it-swarm-pt.tech

O System.arraycopy () do Java é eficiente para pequenas matrizes?

O System.arraycopy() do Java é eficiente para matrizes pequenas ou o fato de ser um método nativo torna provavelmente menos eficiente do que um loop simples e uma chamada de função?

Os métodos nativos incorrem em sobrecarga de desempenho adicional para atravessar algum tipo de ponte do sistema Java?

52
Gravity

Expandindo um pouco o que Sid escreveu, é muito provável que System.arraycopy é apenas um JIT intrínseco; significando que quando o código chama System.arraycopy, provavelmente chamará uma implementação específica do JIT (depois que o JIT marcar System.arraycopy como "hot") que não é executado através da interface JNI, portanto não incorre na sobrecarga normal dos métodos nativos.

Em geral, a execução de métodos nativos tem alguma sobrecarga (passando pela interface JNI, também algumas operações internas da JVM não podem acontecer quando métodos nativos estão sendo executados). Mas não é porque um método está marcado como "nativo" que você o está executando na JNI. O JIT pode fazer algumas coisas loucas.

A maneira mais fácil de verificar é, como foi sugerido, escrevendo um pequeno benchmark, tomando cuidado com as advertências normais de Java microbenchmarks (aqueça o código primeiro, evite código sem efeitos colaterais), pois o O JIT apenas o otimiza como não operacional, etc).

27
vanza

Aqui está o meu código de referência:

public void test(int copySize, int copyCount, int testRep) {
    System.out.println("Copy size = " + copySize);
    System.out.println("Copy count = " + copyCount);
    System.out.println();
    for (int i = testRep; i > 0; --i) {
        copy(copySize, copyCount);
        loop(copySize, copyCount);
    }
    System.out.println();
}

public void copy(int copySize, int copyCount) {
    int[] src = newSrc(copySize + 1);
    int[] dst = new int[copySize + 1];
    long begin = System.nanoTime();
    for (int count = copyCount; count > 0; --count) {
        System.arraycopy(src, 1, dst, 0, copySize);
        dst[copySize] = src[copySize] + 1;
        System.arraycopy(dst, 0, src, 0, copySize);
        src[copySize] = dst[copySize];
    }
    long end = System.nanoTime();
    System.out.println("Arraycopy: " + (end - begin) / 1e9 + " s");
}

public void loop(int copySize, int copyCount) {
    int[] src = newSrc(copySize + 1);
    int[] dst = new int[copySize + 1];
    long begin = System.nanoTime();
    for (int count = copyCount; count > 0; --count) {
        for (int i = copySize - 1; i >= 0; --i) {
            dst[i] = src[i + 1];
        }
        dst[copySize] = src[copySize] + 1;
        for (int i = copySize - 1; i >= 0; --i) {
            src[i] = dst[i];
        }
        src[copySize] = dst[copySize];
    }
    long end = System.nanoTime();
    System.out.println("Man. loop: " + (end - begin) / 1e9 + " s");
}

public int[] newSrc(int arraySize) {
    int[] src = new int[arraySize];
    for (int i = arraySize - 1; i >= 0; --i) {
        src[i] = i;
    }
    return src;
}

Nos meus testes, chamar test() com copyCount = 10000000 (1e7) ou superior permite que o aquecimento seja alcançado durante a primeira chamada copy/loop, Então use testRep = 5 é suficiente; Com copyCount = 1000000 (1e6), o aquecimento precisa de pelo menos 2 ou 3 iterações para que testRep seja aumentado para obter resultados utilizáveis.

Com a minha configuração (CPU Intel Core 2 Duo E8500 a 3.16GHz, Java SE 1.6.0_35-b10 e Eclipse 3.7.2), parece que no benchmark:

  • Quando copySize = 24, System.arraycopy() e o loop manual levam quase o mesmo tempo (às vezes um é muito mais rápido que o outro, outras vezes é o contrário),
  • Quando copySize <24, o loop manual é mais rápido que System.arraycopy() (ligeiramente mais rápido com copySize = 23, muito mais rápido com copySize <5),
  • Quando copySize> 24, System.arraycopy() é mais rápido que o loop manual (um pouco mais rápido com copySize = 25, a relação tempo de loop/tempo de arraycopy aumenta como copySize aumenta).

Nota: não falo inglês, desculpe todos os meus erros de gramática/vocabulário.

24
Ethaniel

Esta é uma preocupação válida. Por exemplo, em Java.nio.DirectByteBuffer.put(byte[]), o autor tenta evitar uma cópia JNI para um pequeno número de elementos

// These numbers represent the point at which we have empirically
// determined that the average cost of a JNI call exceeds the expense
// of an element by element copy.  These numbers may change over time.
static final int JNI_COPY_TO_ARRAY_THRESHOLD   = 6;
static final int JNI_COPY_FROM_ARRAY_THRESHOLD = 6;

Para System.arraycopy(), podemos examinar como o JDK o usa. Por exemplo, em ArrayList, System.arraycopy() é sempre usada, nunca "cópia elemento por elemento", independentemente do comprimento (mesmo que seja 0). Como ArrayList é muito consciente do desempenho, podemos derivar que System.arraycopy() é a maneira mais eficiente de copiar matrizes, independentemente do comprimento.

17
irreputable

System.arraycopy use uma operação memmove para mover palavras e Assembly para mover outros tipos primitivos em C nos bastidores. Por isso, faz o possível para se mover o máximo possível de eficiência.

7
lichenbo

Os códigos de bytes são executados nativamente de qualquer maneira, portanto é provável que o desempenho seja melhor que um loop.

Portanto, no caso de um loop, seria necessário executar códigos de bytes, o que acarretaria uma sobrecarga. Enquanto a cópia do array deve ser uma cópia direta.

5
Sid Malani

Em vez de confiar em especulações e informações possivelmente desatualizadas, executei alguns benchmarks usando paquímetro . De fato, o Caliper vem com alguns exemplos, incluindo um CopyArrayBenchmark que mede exatamente essa questão! Tudo o que você precisa fazer é executar

mvn exec:Java -Dexec.mainClass=com.google.caliper.runner.CaliperMain -Dexec.args=examples.CopyArrayBenchmark

Meus resultados são baseados na VM do servidor Java HotSpot (TM) de 64 bits do servidor, 1.8.0_31-b13, em execução em um MacBook Pro de meados de 2010 (macOS 10.11.6 com um Intel Arrandale i7) , 8 GiB RAM). Não acredito que seja útil publicar os dados brutos de tempo. Em vez disso, resumirei as conclusões com as visualizações de suporte.

Em suma:

  • Escrever um loop manual for para copiar cada elemento em uma matriz recém-instanciada nunca é vantajoso, mesmo para matrizes tão curtas quanto 5 elementos.
  • Arrays.copyOf(array, array.length) e array.clone() são ambos consistentemente rápidos. Essas duas técnicas são quase idênticas no desempenho; qual você escolhe é uma questão de gosto.
  • System.arraycopy(src, 0, dest, 0, src.length) é quase tão rápido quanto Arrays.copyOf(array, array.length) e array.clone(), mas não de maneira consistente. (Veja o caso de 50000 ints.) Por causa disso, e pela verbosidade da chamada, eu recomendaria System.arraycopy() se você precisar de um controle fino sobre quais elementos são copiados para onde.

Aqui estão os gráficos de tempo:

Timings for copying arrays of length 5Timings for copying arrays of length 500Timings for copying arrays of length 50000

3
200_success