Gente
Removing Unnecessary
Synchronization in Java
Sérgio Soares
Sincronização
Métodos/blocos onde apenas um thread
executa por vez
baseado em monitores
Garantir execuções seguras
Motivação
Sincronizações desnecessárias
objetos acessíveis apenas por um thread
overhead 26-60% do tempo de execução
“remover” sincronização
Possíveis soluções
Identificar objetos acessíveis apenas por
um thread
verificação manual tediosa e erro-prone
mudanças futuras do programa forçam uma
nova análise
Definir versões não sincronizadas do
referido objeto
duplicação de código
A solução proposta
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
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 thread
s-local
s-escaping e s-local
algoritmo 1
A
B
C
A é s-local
B é s-escape
C é s-escape
Pilha do
Thread 1
Pilha do
Thread 2
Heap
s-escaping e s-local
algoritmo 2
A
B
C
A é s-local
B é s-local
C é s-escape
Pilha do
Thread 1
Pilha do
Thread 2
Heap
Algoritmo 2
s-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 slocal do heap
Problema
Identificar 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álise
Estágio 1
detectar objetos s-escaping
Estágio 2
detectar objetos f-escaping
Restrições da linguagem
Um subconjunto de comandos/expressões
x = y
x.f = y
y = x.f
C.f = y
y = C.f
x = new T
foo(a1, ..., an)
atribuição a variável
atribuição a atributo de objeto
acesso a atributo
atribuição a atributo de classe
acesso a atributo de classe
criação de objeto
chamada de método
usados para implementar construções de Java
como exceções, arrays, retorno de métodos
Retorno de métodos
o = 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
Detectando objetos s-escaping
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 sescape das variáveis
x = y
AS(x)  AS(y)
s-escape(x)  s-escape(y)
AS(x) 1 AS(y)
Análise flow-insensitive
Detectando objetos s-escaping
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)
an é o parâmetro real que recebe o
retorno do método se houver retorno
Detectando objetos f-escaping
AS(x.f)
conjunto de variáveis que referenciam o
objeto em x.f
f-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 fescape das variáveis e dos seus atributos
x = y
AS(x)  AS(y)
f-escape(x)  f-escape(y)
se s-escape(x)  s-escape(y) =  AS(x) 2 AS(y)
f  fields(x, y)
*
AS(x.f) 2 AS(y.f)
Detectando objetos f-escaping
Acesso a atributos
x.f = y ou y = x.f
se s-escape(x) = 
AS(x.f) 2 AS(y)
se não
FieldAccess(x.f, y)
f-escape(y)  {T}
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
Detectando objetos f-escaping
Acesso a atributos estáticos
C.f = y ou y = C.f
f-escape(y)  {T}
Detectando objetos f-escaping
Chamada de métodos
Regra 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étodos
Regra 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étodos
Regra 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
Chamada de métodos
Regra 4 - propagar propriedades entre atributos de
parâmetros que referenciam um mesmo objeto
foo(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}
Exemplo
class Handle {
private Object ref = null;
synchronized void attach(Object o) {
this.ref = o;
}
}
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();
}
}
Exemplo
Vamos analisar o método m da classe
Sample
Fase 1 - identificando
s-escaping
Alias Sets do
método m
Alias Set do método
createHandle
Alias Sets do método
attach
h1
h2
o2
o1
s
s
s
this
return
o
s
Fase 2 - identificando
f-escaping
ref
h1
Alias Sets do
método m
h2
o2
Alias Set do método
createHandle
Alias Sets do método
attach
o1
s
s,f
s,f
return
this
ref
o
s
Conclusão
Otimizar o uso dos objetos que não são fescape e que possuem métodos
sincronizados
otimizar h1
Otimização
Definir 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 clone
Definir um construtor que invoca o
construtor da superclasse (classe a ser
otimizada)
Copiar os métodos da superclasse
removendo o qualificador synchronized
Remover qualificadores final
Alterar 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
otimizados
class Sample {
// ...
static m() {
Handle h1 = createHandle$Clone1();
Handle h2 = createHandle();
// ...
}
static Handle createHandle$Clone1() {
return new Handle$Unsync();
}
// ...
}
Bibliografia
Removing Unnecessary Synchronization in
Java. Jeff Bogda and Urs Holzle.
Departament of Computer Science.
University of California