Removing Unnecessary Synchronization in Java
Sérgio Soares
Gente
SincronizaçãoMétodos/blocos onde apenas um
thread executa por vez baseado em monitores
Garantir execuções seguras
MotivaçãoSincronizações desnecessárias
objetos acessíveis apenas por um thread
overhead 26-60% do tempo de execução
“remover” sincronização
Possíveis soluçõesIdentificar objetos acessíveis apenas
por um thread verificação manual tediosa e erro-prone mudanças futuras do programa forçam
uma nova análiseDefinir versões não sincronizadas do
referido objeto duplicação de código
Remover em tempo de compilação a sincronização quando a otimização for possível
Programa de otimização (compilador) identifica situações passíveis da
remoção de sincronização rescreve parte do programa removendo
as sincronizações desnecessárias
A solução proposta
Identificando situações de otimização
Excluir os objetos que não podem ser thread-local objetos armazenados na heap
s-escaping (stack-escaping) objetos acessíveis apenas por variáveis
locais na pilha de apenas um threads-local
s-escaping e s-local algoritmo 1
A CB
Pilha do Thread 1
Pilha do Thread 2
A é s-localB é s-escapeC é s-escape
Heap
A CB
Pilha do Thread 1
Pilha do Thread 2
A é s-localB é s-localC é s-escape
Heap
s-escaping e s-local algoritmo 2
Algoritmo 2s-escaping
objetos armazenados na heap ou acessíveis por mais de uma pilha (thread)
s-local objetos acessíveis apenas por uma única
pilha (thread) objetos acessíveis apenas por objetos s-
local do heap
ProblemaIdentificar objetos acessíveis apenas
por objetos s-local do heap pode levar a algoritmos complexos transitividade de acessibilidade tipos de dados recursivos
Simplificação: objetos acessíveis por mais de um nível de referência de um objeto s-local são s-escaping
f-escaping
Objetos referenciados por atributos de objetos s-escaping
A análiseEstágio 1
detectar objetos s-escapingEstágio 2
detectar objetos f-escaping
Restrições da linguagemUm subconjunto de comandos/expressõesx = y atribuição a variávelx.f = y atribuição a atributo de objetoy = x.f acesso a atributoC.f = y atribuição a atributo de classey = C.f acesso a atributo de classex = new T criação de objetofoo(a1, ..., an) chamada de métodousados para implementar construções de Java como exceções, arrays, retorno de métodos
Retorno de métodoso = hashtable.put(x, y)
put(hashtable, x, y, o)
Detectando objetos s-escaping
Define conjuntos s-escape(x)
é vazio inicialmente (representa falso) e durante a análise pode conter o booleano true {T}, indicando que a variável é s-escaping
AS(x)conjunto das variáveis de um métodos que
referenciam o objeto referenciado por x
Inicia a análise pelo método main e vai analisando os métodos conforme aparecem as chamadas aos mesmos
Aplicar as regras para cada tipo de comando atribuição acesso a atributos chamada de métodos
Detectando objetos s-escaping
Atribuição unir (merge) os Alias Set e a
propriedade s-escape das variáveis
x = y
AS(x) AS(y)s-escape(x) s-escape(y)
Detectando objetos s-escaping
Análise flow-insensitive
AS(x) 1 AS(y)
Acesso a atributos (incluindo estáticos) a variável passa a ser s-escaping pois
indica que o heap tem uma referência para a mesma ou que a mesma tem uma referência para o heap
y = x.f ou x.f = y
s-escape(y) {T}
Detectando objetos s-escaping
Chamada de métodos propaga as restrições impostas aos parâmetros
formais dentro do método para os parâmetros reais (depois de analisar o método)
foo(a0, ..., an)
i [0...n] s-escape(ai) s-escape(pi)i tal que connected(pi, returnfoo) AS(ai) 1
AS(an)
Detectando objetos s-escaping
an é o parâmetro real que recebe oretorno do método se houver retorno
AS(x.f) conjunto de variáveis que referenciam o
objeto em x.ff-escape(x)
conjunto vazio ou {T} indicando, quando true, que o objeto referenciado por x também é referenciado pelo atributo de um objeto s-escaping
Detectando objetos f-escaping
Atribuição unir (merge) os Alias Set e a propriedade f-
escape das variáveis e dos seus atributosx = yAS(x) AS(y)f-escape(x) f-escape(y)se s-escape(x) s-escape(y) =
f fields(x, y) AS(x.f) 2 AS(y.f)
Detectando objetos f-escaping
AS(x) 2 AS(y)
*
Acesso a atributosx.f = y ou y = x.f
se s-escape(x) = AS(x.f) 2 AS(y)
se nãof-escape(y) {T}
Detectando objetos f-escaping
FieldAccess(x.f, y)
O que acontecerá com os Alias Set dos atributos de x.f e de y quando aplicar 2 na recursão?
O mesmo código já passou pela fase 1
Acesso a atributos estáticosC.f = y ou y = C.f
f-escape(y) {T}
Detectando objetos f-escaping
Chamada de métodosRegra 1 - propagar a propriedade f-escape dos
parâmetros formais e seus atributos para os parâmetros reais e seus atributos
foo(a0, ..., an)
i [0...n] f-escape(ai) f-escape(pi)se s-escape(ai) =
i fields(pi) f-escape(ai.f) f-escape(pi.f)
Detectando objetos f-escaping
Chamada de métodosRegra 2 - propagar as restrições entre
parâmetros retornados e variáveis que recebem o retorno
foo(a0, ..., an)
i tal que connected(pi, returnfoo) AS(ai) 2 AS(an)
Detectando objetos f-escaping
Chamada de métodosRegra 3 - propagar as restrições entre
parâmetros e atributos de outros parâmetros onde haja atribuição entre eles (trata-se como acesso a atributo)
foo(a0, ..., an)
f,pi,pj tal que connected(pi.f, pj) FieldAccess (ai.f, aj)
Detectando objetos f-escaping
Detectando objetos f-escaping
Chamada de métodosRegra 4 - propagar propriedades entre atributos de
parâmetros que referenciam um mesmo objetofoo(a0, ..., an)
f,h,pi,pj tal que connected(pi.f, pj.h)se s-escape(ai) s-escape(aj) =
AS(ai.f) 2 AS(an.h)se não se s-escape(ai) =
f-escape(ai.f) {T}
class Handle { private Object ref = null; synchronized void attach(Object o) { this.ref = o; }}
Exemplo
class Sample { static Handle globalHandle = null; static m() { Handle h1 = createHandle(); Handle h2 = createHandle(); Object o1 = new Object(); Object o2 = new Object(); h1.attach(o1); h2.attach(o2); globalHandle = h2; } static Handle createHandle() { return new Handle(); }}
ExemploVamos analisar o método m da classe Sample
h1
h2
o1
o2
Fase 1 - identificando s-escaping
return
this
o
s
s
s
s
Alias Sets do método m
Alias Set do método createHandle
Alias Sets do método attach
Fase 2 - identificando f-escaping
h1
h2
o1
o2
return
this o
s,f
s,f
s
s
ref
ref
Alias Sets do método m
Alias Set do método createHandle
Alias Sets do método attach
ConclusãoOtimizar o uso dos objetos que não
são f-escape e que possuem métodos sincronizados otimizar h1
OtimizaçãoDefinir uma nova subclasse (clone) da
classe do objeto a ser otimizado sem sincronizar os métodos como na classe original (Handle)
Substituir no método analisado a instanciação do objeto referenciado por h1 pela nova classe (clone) pode ser necessário duplicar factory
methods
Na classe cloneDefinir um construtor que invoca o
construtor da superclasse (classe a ser otimizada)
Copiar os métodos da superclasse removendo o qualificador synchronized
Remover qualificadores finalAlterar os qualificadores private para protected
A classe clone
class Handle$Unsync extends Handle{ public Handle$Unsync() { super(); } public void attach(Object o) { this.ref = o; }}
A classe e o método otimizadosclass Sample { // ... static m() { Handle h1 = createHandle$Clone1(); Handle h2 = createHandle(); // ... } static Handle createHandle$Clone1() { return new Handle$Unsync(); } // ...}
BibliografiaRemoving Unnecessary
Synchronization in Java. Jeff Bogda and Urs Holzle. Departament of Computer Science. University of California