Algum compilador JIT da JVM gera código que usa instruções de ponto flutuante vetorizadas?

95

Digamos que o gargalo do meu programa Java realmente sejam alguns loops apertados para calcular um monte de produtos de ponto vetorial. Sim, fiz o perfil, sim, é o gargalo, sim é significativo, sim é assim que o algoritmo é, sim, executei o Proguard para otimizar o código de bytes, etc.

O trabalho é, essencialmente, produtos escalares. Como em, tenho dois float[50]e preciso calcular a soma dos produtos em pares. Eu sei que os conjuntos de instruções do processador existem para realizar esse tipo de operação rapidamente e em massa, como SSE ou MMX.

Sim, provavelmente posso acessá-los escrevendo algum código nativo em JNI. A ligação do JNI acabou sendo muito cara.

Eu sei que você não pode garantir o que um JIT irá compilar ou não. Alguém ouviu falar de um código de geração de JIT que usa essas instruções? Em caso afirmativo, há algo sobre o código Java que ajuda a torná-lo compilável dessa maneira?

Provavelmente um "não"; vale a pena perguntar.

Sean Owen
fonte
4
A maneira mais fácil de descobrir é provavelmente obter o JIT mais moderno que puder encontrar e fazer com que ele produza a montagem gerada -XX:+UnlockDiagnosticVMOptions -XX:+PrintAssembly -XX:+LogCompilation. Você precisará de um programa que execute o método vetorizável vezes suficientes para torná-lo "quente".
Louis Wasserman
1
Ou dê uma olhada na fonte. download.java.net/openjdk/jdk7
Bill de
1
"Em breve" para um jdk perto de você: mail.openjdk.java.net/pipermail/hotspot-compiler-dev/2012-July/…
Jonathan S. Fisher
3
Na verdade, de acordo com este blog , JNI pode ser bastante rápido se usado "corretamente".
ziggystar
2
Uma postagem de blog relevante sobre isso pode ser encontrada aqui: psy-lob-saw.blogspot.com/2015/04/… com a mensagem geral de que a vetorização pode acontecer, e acontece. Além de vetorizar casos específicos (Arrays.fill () / equals (char []) / arrayCopy), a JVM se auto-vetoriza usando a paralelização de nível de superpalavra. O código relevante está em superword.cpp e o documento em que ele se baseia está aqui: groups.csail.mit.edu/cag/slp/SLP-PLDI-2000.pdf
Nitsan Wakart

Respostas:

44

Então, basicamente, você deseja que seu código seja executado mais rapidamente. JNI é a resposta. Eu sei que você disse que não funcionou para você, mas deixe-me mostrar que você está errado.

Aqui está Dot.java:

import java.nio.FloatBuffer;
import org.bytedeco.javacpp.*;
import org.bytedeco.javacpp.annotation.*;

@Platform(include = "Dot.h", compiler = "fastfpu")
public class Dot {
    static { Loader.load(); }

    static float[] a = new float[50], b = new float[50];
    static float dot() {
        float sum = 0;
        for (int i = 0; i < 50; i++) {
            sum += a[i]*b[i];
        }
        return sum;
    }
    static native @MemberGetter FloatPointer ac();
    static native @MemberGetter FloatPointer bc();
    static native @NoException float dotc();

    public static void main(String[] args) {
        FloatBuffer ab = ac().capacity(50).asBuffer();
        FloatBuffer bb = bc().capacity(50).asBuffer();

        for (int i = 0; i < 10000000; i++) {
            a[i%50] = b[i%50] = dot();
            float sum = dotc();
            ab.put(i%50, sum);
            bb.put(i%50, sum);
        }
        long t1 = System.nanoTime();
        for (int i = 0; i < 10000000; i++) {
            a[i%50] = b[i%50] = dot();
        }
        long t2 = System.nanoTime();
        for (int i = 0; i < 10000000; i++) {
            float sum = dotc();
            ab.put(i%50, sum);
            bb.put(i%50, sum);
        }
        long t3 = System.nanoTime();
        System.out.println("dot(): " + (t2 - t1)/10000000 + " ns");
        System.out.println("dotc(): "  + (t3 - t2)/10000000 + " ns");
    }
}

e Dot.h:

float ac[50], bc[50];

inline float dotc() {
    float sum = 0;
    for (int i = 0; i < 50; i++) {
        sum += ac[i]*bc[i];
    }
    return sum;
}

Podemos compilar e executar isso com JavaCPP usando este comando:

$ java -jar javacpp.jar Dot.java -exec

Com uma CPU Intel (R) Core (TM) i7-7700HQ a 2,80 GHz, Fedora 30, GCC 9.1.1 e OpenJDK 8 ou 11, recebo este tipo de resultado:

dot(): 39 ns
dotc(): 16 ns

Ou cerca de 2,4 vezes mais rápido. Precisamos usar buffers NIO diretos em vez de arrays, mas o HotSpot pode acessar os buffers NIO diretos tão rápido quanto os arrays . Por outro lado, desenrolar manualmente o loop não fornece um aumento mensurável no desempenho, neste caso.

Samuel Audet
fonte
3
Você usou OpenJDK ou Oracle HotSpot? Ao contrário da crença popular, eles não são os mesmos.
Jonathan S. Fisher
@exabrial Isto é o que "java -version" retorna nesta máquina agora: versão java "1.6.0_22" OpenJDK Runtime Environment (IcedTea6 1.10.6) (fedora-63.1.10.6.fc15-x86_64) Servidor VM OpenJDK de 64 bits (versão 20.0-b11, modo misto)
Samuel Audet
1
Esse loop provavelmente tem uma dependência de loop transportado. Você pode obter mais velocidade desenrolando o loop duas ou mais vezes.
3
O @Oliv GCC vetoriza o código com SSE, sim, mas para dados tão pequenos, a sobrecarga da chamada JNI infelizmente é muito grande.
Samuel Audet
2
No meu A6-7310 com JDK 13, obtenho: ponto (): 69 ns / dotc (): 95 ns. Java vence!
Stefan Reich
39

Para abordar parte do ceticismo expresso por outros aqui, sugiro que qualquer pessoa que queira provar a si mesma ou outra pessoa use o seguinte método:

  • Crie um projeto JMH
  • Escreva um pequeno trecho de matemática vetorizável.
  • Execute seu benchmark alternando entre -XX: -UseSuperWord e -XX: + UseSuperWord (padrão)
  • Se nenhuma diferença no desempenho for observada, seu código provavelmente não foi vetorizado
  • Para ter certeza, execute seu benchmark de forma que ele imprima o conjunto. No linux você pode aproveitar o perfasm profiler ('- prof perfasm'), dar uma olhada e ver se as instruções que você espera são geradas.

Exemplo:

@Benchmark
@CompilerControl(CompilerControl.Mode.DONT_INLINE) //makes looking at assembly easier
public void inc() {
    for (int i=0;i<a.length;i++)
        a[i]++;// a is an int[], I benchmarked with size 32K
}

O resultado com e sem o sinalizador (no laptop Haswell recente, Oracle JDK 8u60): -XX: + UseSuperWord: 475,073 ± 44,579 ns / op (nanossegundos por op) -XX: -UseSuperWord: 3376,364 ± 233,211 ns / op

A montagem do hot loop é um pouco demais para formatar e colar aqui, mas aqui está um trecho (hsdis.so não está formatando algumas das instruções do vetor AVX2, então executei com -XX: UseAVX = 1): -XX: + UseSuperWord (com '-prof perfasm: intelSyntax = true')

  9.15%   10.90%  │││ │↗    0x00007fc09d1ece60: vmovdqu xmm1,XMMWORD PTR [r10+r9*4+0x18]
 10.63%    9.78%  │││ ││    0x00007fc09d1ece67: vpaddd xmm1,xmm1,xmm0
 12.47%   12.67%  │││ ││    0x00007fc09d1ece6b: movsxd r11,r9d
  8.54%    7.82%  │││ ││    0x00007fc09d1ece6e: vmovdqu xmm2,XMMWORD PTR [r10+r11*4+0x28]
                  │││ ││                                                  ;*iaload
                  │││ ││                                                  ; - psy.lob.saw.VectorMath::inc@17 (line 45)
 10.68%   10.36%  │││ ││    0x00007fc09d1ece75: vmovdqu XMMWORD PTR [r10+r9*4+0x18],xmm1
 10.65%   10.44%  │││ ││    0x00007fc09d1ece7c: vpaddd xmm1,xmm2,xmm0
 10.11%   11.94%  │││ ││    0x00007fc09d1ece80: vmovdqu XMMWORD PTR [r10+r11*4+0x28],xmm1
                  │││ ││                                                  ;*iastore
                  │││ ││                                                  ; - psy.lob.saw.VectorMath::inc@20 (line 45)
 11.19%   12.65%  │││ ││    0x00007fc09d1ece87: add    r9d,0x8            ;*iinc
                  │││ ││                                                  ; - psy.lob.saw.VectorMath::inc@21 (line 44)
  8.38%    9.50%  │││ ││    0x00007fc09d1ece8b: cmp    r9d,ecx
                  │││ │╰    0x00007fc09d1ece8e: jl     0x00007fc09d1ece60  ;*if_icmpge

Divirta-se atacando o castelo!

Nitsan Wakart
fonte
1
Do mesmo artigo: "a saída do desmontador JITed sugere que não é realmente tão eficiente em termos de chamar as instruções SIMD mais ideais e sua programação. Uma busca rápida pelo código-fonte do compilador JVM JIT (Hotspot) sugere que isso se deve a a inexistência de códigos de instrução SIMD compactados. " Os registros SSE estão sendo usados ​​no modo escalar.
Aleksandr Dubinsky,
1
@AleksandrDubinsky alguns casos são cobertos, outros não. Você tem um caso concreto no qual está interessado?
Nitsan Wakart,
2
Vamos inverter a questão e perguntar se a JVM autovetorizará quaisquer operações aritméticas. você pode dar um exemplo? Eu tenho um loop que tive que puxar e reescrever usando intrínsecos recentemente. No entanto, em vez de esperar por autovectorização, gostaria de ver suporte para vetorização / intrínseca explícita (semelhante a agner.org/optimize/vectorclass.pdf ). Melhor ainda seria escrever um bom back-end Java para Aparapi (embora a liderança desse projeto tenha alguns objetivos errados). Você trabalha no JVM?
Aleksandr Dubinsky
1
@AleksandrDubinsky Espero que a resposta expandida ajude, se não, talvez um e-mail ajudasse. Observe também que "reescrever usando intrínsecos" implica que você alterou o código JVM para adicionar novos intrínsecos, é isso que você quer dizer? Suponho que você quisesse substituir seu código Java por chamadas em uma implementação nativa via JNI
Nitsan Wakart,
1
Obrigado. Esta deve ser a resposta oficial. Acho que você deve remover a referência ao artigo, pois está desatualizado e não demonstra vetorização.
Aleksandr Dubinsky de
26

Nas versões HotSpot começando com Java 7u40, o compilador de servidor fornece suporte para autovetorização. De acordo com JDK-6340864

No entanto, isso parece ser verdade apenas para "loops simples" - pelo menos por enquanto. Por exemplo, a acumulação de uma matriz ainda não pode ser vetorizada JDK-7192383

Vedran
fonte
A vetorização também existe no JDK6 para alguns casos, embora o conjunto de instruções SIMD de destino não seja tão amplo.
Nitsan Wakart
3
O suporte à vetorização do compilador no HotSpot foi muito melhorado recentemente (junho de 2017) devido às contribuições da Intel. Em termos de desempenho, o ainda não lançado jdk9 (b163 e posterior) atualmente vence o jdk8 devido a correções de bugs que permitem o AVX2. Os loops devem cumprir algumas restrições para que a autovetorização funcione, por exemplo, use: contador interno, incremento do contador constante, uma condição de terminação com variáveis ​​invariantes do loop, corpo do loop sem chamadas de método (?), Sem desdobramento manual do loop! Os detalhes estão disponíveis em: cr.openjdk.java.net/~vlivanov/talks/…
Vedran
O suporte vetorizado fundido-múltiplo-add (FMA) não parece bom atualmente (em junho de 2017): é vetorização ou FMA escalar (?). No entanto, a Oracle aparentemente acabou de aceitar a contribuição da Intel para o HotSpot que permite a vetorização FMA usando AVX-512. Para o deleite dos fãs da autovetorização e daqueles que têm a sorte de ter acesso ao hardware AVX-512, isso pode (com alguma sorte) aparecer em uma das próximas compilações do EA jdk9 (além do b175).
Vedran
Um link para apoiar a declaração anterior (RFR (M): 8181616: Vetorização FMA em x86): mail.openjdk.java.net/pipermail/hotspot-compiler-dev/2017-June/…
Vedran
2
Um pequeno benchmark que demonstra a aceleração por um fator de 4 em inteiros por meio de vetorização de loop usando instruções AVX2: prestodb.rocks/code/simd
Vedran
6

Aqui está um bom artigo sobre como experimentar as instruções Java e SIMD escritas por meu amigo: http://prestodb.rocks/code/simd/

O resultado geral é que você pode esperar que o JIT use algumas operações SSE no 1.8 (e algumas mais no 1.9). Embora você não deva esperar muito e precise ter cuidado.

kokosing
fonte
1
Ajudaria se você resumisse alguns dos principais insights do artigo ao qual está vinculado.
Aleksandr Dubinsky,
4

Você pode escrever o kernel OpenCl para fazer a computação e executá-lo a partir de java http://www.jocl.org/ .

O código pode ser executado na CPU e / ou GPU e a linguagem OpenCL também suporta tipos de vetor, portanto, você deve ser capaz de tirar vantagem explicitamente, por exemplo, das instruções SSE3 / 4.

Mikael Lepistö
fonte
4

Dê uma olhada na comparação de desempenho entre Java e JNI para uma implementação ideal de micro-kernels computacionais . Eles mostram que o compilador do servidor Java HotSpot VM suporta a autovetorização usando o paralelismo de nível de superpalavra, que é limitado a casos simples de paralelismo dentro do loop. Este artigo também lhe dará alguma orientação se o tamanho dos dados é grande o suficiente para justificar a rota JNI.

Paul Jurczak
fonte
3

Suponho que você escreveu esta pergunta antes de descobrir sobre o netlib-java ;-) ele fornece exatamente a API nativa que você precisa, com implementações otimizadas para máquina, e não tem nenhum custo no limite nativo devido à fixação de memória.

fommil
fonte
1
Sim, muito tempo atrás. Eu esperava mais ouvir que isso é traduzido automagicamente para instruções vetorizadas. Mas claramente não é tão difícil fazer isso acontecer manualmente.
Sean Owen
-4

Eu não acredito que a maioria das VMs sejam inteligentes o suficiente para esse tipo de otimizações. Para ser justo, a maioria das otimizações é muito mais simples, como mudar em vez de multiplicação quando é uma potência de dois. O projeto mono introduziu seu próprio vetor e outros métodos com apoios nativos para ajudar no desempenho.

mP.
fonte
3
Atualmente, nenhum compilador de hotspot Java faz isso, mas não é muito mais difícil do que as coisas que eles fazem. Eles usam instruções SIMD para copiar vários valores de matriz de uma vez. Você só precisa escrever um pouco mais de correspondência de padrões e código de geração de código, o que é bastante simples depois de fazer alguns desdobramentos de loop. Acho que o pessoal da Sun ficou preguiçoso, mas parece que agora vai acontecer na Oracle (yay Vladimir! Isso deve ajudar muito nosso código!): Mail.openjdk.java.net/pipermail/hotspot-compiler-dev/ …
Christopher Manning