Articles

Seeing Escape Analysis Working

Posted on

you may have heard of a compiler analysis phase called escape analysis. Ele informa uma otimização chamada substituição escalar de agregados que remove alocação desnecessária de objetos Java. Eu acho que as pessoas muitas vezes têm um mal-entendido sobre o que esta otimização realmente faz e uma sub-apreciação do que é capaz de fazer. Podemos conhecê-la melhor vendo-a a funcionar na prática.

Context

i’ll be showing how the GraalVM compiler, as part of GraalVM and configured for just-in-time compilation in hosted configuration, applies escape analysis and scalar replacement of aggregates. O compilador GraalVM é mais poderoso a este respeito do que o compilador just-in-time mais comum que você provavelmente está acostumado a, C2 em HotSpot.

Note que cada vez que eu digo compilador neste artigo, eu estou significando compilação just-in-time, de modo que o tipo de compilação que acontece em tempo de execução no JVM. Não me refiro ao compilador javac.

vou mostrar como o compilador entende nossos programas de exemplo, olhando para uma das estruturas de dados que ele usa durante a compilação, sua representação intermediária mais elevada. Este é um grafo que capta o Significado de um programa Java como ele é otimizado e transformado antes que a conversão para código de máquina comece. Isso provavelmente parece muito avançado, mas eu acho que para a maioria das pessoas com alguma experiência em Java é realmente uma maneira acessível de entender o que o compilador está fazendo.

Esta representação intermediária é diferente de uma árvore de sintaxe abstrata, ou AST, que é uma representação sintática do texto no seu programa. Também é diferente de um gráfico de chamadas,que apenas diz a você Que métodos chamam que outros métodos.Vou usar uma ferramenta chamada Seafoam, da equipa de implementação de linguagem do Shopify, para criar diagramas das estruturas de dados despejadas do Graal. Você também poderia usar uma ferramenta chamada o Visualizador de Grafos Ideal do Oracle Labs.

Terminology

Escape analysis is an analysis process. It detects if an object is visible outside of a compilation unit (a compilation unit is usually a method plus any other methods inline into it. Um objeto pode tornar-se visível fora de uma unidade de compilação por ser devolvido, ou passado como argumento para outro método, ou escrito para um campo, ou similar.

a substituição Escalar de agregados usa o resultado da análise de escape e trabalha em objetos que não escapam da unidade de compilação, ou apenas escapam dela em alguns ramos. Ele substitui objetos (agregados) com valores simples (escalares) semelhantes em efeito às variáveis locais. Veremos isto mais concretamente mais tarde.

Object allocation

we’ll work with a simple Vector class that holds double x and y fields. Ele tem um construtor, getters, e um método add que retorna um novo objeto que é este Vector adicionado a outro.

eu tenho um main método que executa um loop e chama um

sum

método que utiliza

add

a soma de dois gerada aleatoriamente vetores. O loop está lá para obter o código quente o suficiente para desencadear uma compilação just-in-time, a aleatorização está lá para que os valores não são perfilados para ser efetivamente constante, e o método separado sum está lá para criar um bloco de código puro para olhar ao olhar para como o código é compilado.

vou compilar e executar isto usando GraalVM CE em Java 8 20.3.0 em macOS em AMD64. Eu desligo uma otimização chamada substituição on-stack porque esta otimização torna a compilação um pouco mais complicada e mais difícil de entender. I then use Graal’s

dump

option to ask it to dump out its intermediate representation data structures.

podemos agora usar a Seafoam para ver como o compilador entende o método sum, mesmo antes de executar a análise de fuga. O arquivo sum.bgv contém a estrutura de dados que o compilador descartou para nós.

% seafoam sum.bgv:14 render

o que estamos a ver aqui? Este grafo é a maneira que Graal entende o método sum enquanto ele está compilando. É um código Java, mas livre das restrições de uma representação textual. As operações são representadas como nós (as caixas, diamantes e ovais) e as relações entre as operações são representadas como bordas (as setas). A seta vermelha grossa significa que uma operação deve acontecer antes da outra. A seta mais fina significa que a saída da operação é usada como entrada para outra operação.Dissemos que o programa estava livre das restrições de uma representação textual. Veja a operação adicionar no nó 14, por exemplo. Sabemos que isso precisa acontecer depois de carregarmos os dois valores dos dois campos x, e antes de armazenarmos o valor no campo x no nó 19, mas não nos importamos se isso acontece antes ou depois dos dois campos y são carregados. No código fonte textual Java, tudo é escrito em uma ordem linear. O grafo relaxa esta restrição e codifica apenas as restrições que a especificação da linguagem Java realmente requer. O compilador é então livre para escolher a ordem final em que tudo corre.Ao ler este gráfico, podemos ver que criamos um novo Vector, depois carregamos os dois campos de entrada’ x e y, adicionamo-los juntos e armazenamo-los no novo Vector que criamos antes de o devolver. Existem alguns detalhes extras no grafo, como o null check, a barreira de campo final, e mais porque este é um grafo de compilador real, mas vamos ignorar aqueles para este artigo para mantê-lo curto.

a chave para ver aqui agora é que há um ponto definido onde o novo objeto Vector é criado.

basic scalar replacement

Let’s look at the same method right after escape analysis and scalar replacement of aggregates have run.

% seafoam sum.bgv:15 render

agora o gráfico foi ainda mais relaxado de como ele aparece no texto. Em vez de uma operação New Vector nós agora a decompusemos em uma operação genérica para alocar um objeto, tomando o valor dos campos desse objeto. Já não há StoreField aqui.

este método em particular, este não tenha conseguido nada útil – o gráfico foi relaxada, mas ele não revelou quaisquer realmente útil otimizações. Isso é porque o único objeto que atribuímos realmente precisa ser alocado porque deixa o método. A análise de fuga foi executada, mas o objecto escapou, por isso não houve substituição escalar de agregados.

para levar isso adiante, vamos olhar para um método que resume três objetos Vector.

private static Vector sum(Vector a, Vector b, Vector c) {return a.add(b).add(c);}

o grafo antes da análise de escape e substituição escalar de agregados tem a mesma estrutura que o método anterior. Temos duas operações New Vector. O resultado de a.add(b) é escrito no primeiro objeto novo, e então lido novamente para o posterior .add(c). Podemos ver como isso é um desperdício – o objeto intermediário nunca é visível fora da unidade de compilação porque ele não é armazenado ou passado em qualquer lugar – então por que alocá-lo e por que armazenar campos nele que nós apenas imediatamente ler para fora novamente?

se olharmos para o gráfico após a análise de escape e a substituição escalar dos agregados, veremos que o intermediário Vector foi removido inteiramente. Há apenas um Alloc, Não dois. O agregado dos campos do objeto intermediário foi substituído pelos valores escalares das arestas que ligam diretamente o produtor e o consumidor, sem fazer um intermediário StoreField e depois LoadField.

a eficácia da substituição escalar

alguns exemplos mais mostrarão como esta optimização é um pouco mais poderosa do que as pessoas frequentemente assumem.

se somarmos uma matriz de Vector objectos, estaremos logicamente a criar um Vector por iteração.

private static Vector sum(Vector first, Vector... rest) {Vector sum = first;for (Vector vector : rest) {sum = sum.add(vector);}return sum;}

este gráfico é agora bastante complicado, mas o ponto chave é que você pode ver uma operação New Vector dentro do laço (dentro do círculo formado de setas vermelhas grossas.)

após análise de escape parcial e substituição escalar de agregados executar não há agora New Vector dentro do loop. Não há uma única alocação no final para a final que é retornado, e os valores para x e y são construídas por acumulação de valores (os pequenos laços em torno de nós 33 e 92, e nós 36 e 93. Isso significa nenhuma memória é alocada mais no interior do loop deste método.

às Vezes as pessoas falam sobre objetos que não escapar de uma unidade de compilação a ser alocada na pilha. É por isto que isso é um mal-entendido. Este método de soma de dois objetos, mas apenas retorna o x componente.

private static double sumX(Vector a, Vector b) {return a.add(b).getX();}

antes que a análise de escape funcione este método parece exatamente como o original sum, exceto que o campo x é então carregado e devolvido. O campo y é armazenado mas nunca utilizado, e o intermediário Vector não escapa da unidade de compilação.

após a análise de escape e a substituição escalar de agregados, podemos ver um ponto importante a ser notado – depois que o objeto foi substituído por escalares, não havia nenhum consumidor do valor y, de modo que o código para gerá-lo não tinha nada para conectá-lo ao grafo e então ele foi removido.

se estivéssemos literalmente alocando o objeto na pilha, armazenando o objeto no mesmo formato apenas na memória da pilha ao invés de pilha de memória, ainda teríamos que gerar o valor intermediário y. Nós não distribuímos o objeto em qualquer lugar – nós o substituímos por bordas dataflow em vez disso.

Note que a alocação de pilha de objetos é realmente uma coisa, e está sendo proposto para HotSpot padrão e C2, mas é para um propósito ligeiramente diferente que não vamos entrar aqui por simplicidade.Pode reescrever alguns destes métodos para acumular os x e os y em variáveis locais e não criar objectos intermédios Vector? Por exemplo, você pode reescrever o sum sobre um array de Vector objetos como este:

este grafo é realmente mais eficiente do que o grafo de nossa soma com objetos intermediários Vector antes da análise de escape. Não há alocação dentro do loop.

mas se olharmos para trás para o nosso loop de soma anterior com objetos intermediários Vector após análise de fuga e substituição escalar de agregados, eles parecem basicamente o mesmo. Não houve nenhum benefício em reescrever este método a partir da versão de alto nível com simples objetos intermediários Vector para a versão otimizada manualmente.

(bem na verdade talvez exista-a versão otimizada manualmente é mais rápida de compilar e executar mais rapidamente, enquanto é interpretada até que seja compilado.)

Partial escape analysis

Something that Graal can do that C2 cannot, and a key advantage of GraalVM, is partial escape analysis. Em vez de determinar um valor binário de se um objeto escapa da unidade de compilação ou não, isso pode determinar em que Ramos um objeto escapa dele, e mover a alocação do objeto para apenas aqueles ramos onde ele escapa.

Este imaginária método de soma de dois objectos e, em seguida, com base em uma condição s ele passa como um parâmetro para outro método, chamado de blackhole, que faz com que ele escape, ou adiciona um terceiro vetor, e, em seguida, retorna-lo.

o intermediário Vector armazenado em x escapa no primeiro ramo, mas não no segundo.

impedimos blackhole de ser alinhado, especificando -XX:CompileCommand=dontinline,Vector.blackhole.

antes da análise de escape parcial correr podemos ver New Vector para x sendo executado para ambos os ramos.

após análise de escape parcial e substituição escalar dos agregados, o intermediário New Vector desapareceu. Em vez disso, no ramo onde ele escapa temos o objeto Alloc, que refere os valores que ele deveria ter de x e y, e no outro ramo onde o objeto não escapa os valores para x e y são apenas usados diretamente.

a alocação foi transferida para apenas o ramo onde ela é realmente necessária.

Esperemos que tudo o que o ajude a compreender o que é a análise de fuga e a substituição escalar dos agregados, vendo-o a funcionar na prática. Também espero que ele mostra que não é realmente alocação stack e é realmente algo mais poderoso do que isso, e que ele mostra o que extra o compilador GraalVM pode fazer por você.

More information

graal’s partial escape analysis algorithm is described in Partial Escape Analysis and Scalar Replacement for Java.

eu escrevi mais sobre esses grafos de compilador e como lê-los na compreensão de Grafos Graais Básicos.

Autor: Chris Seaton

Chris é um Investigador Sênior Engenheiro de Pessoal) em Shopify, onde ele trabalha com a Linguagem de programação Ruby, e um Visitante na Universidade de Manchester.

He was formerly a Research Manager at the Oracle Labs Virtual Machine Research Group, where he led the TruffleRuby implementation of Ruby, and worked on other language and virtual machine projects. Antes disso, ele completou um PhD em Manchester, onde pesquisou linguagens de programação e paralelismo irregular, e um MEng na Universidade de Bristol em linguagens com sintaxe mutável e semântica.

In his spare time he’s Squadron Leader of the Cheshire Yeomanry squadron of the Queen’s Own Yeomanry, Cheshire’s historic reserve light cavalry squadron.

Deixe uma resposta

O seu endereço de email não será publicado.