Embed Size (px)
Citation preview
Desempenho poliglota Melhoria de performance independente de
linguagem ou plataforma
Fabio Galuppo, M.Sc. http://fabiogaluppo.com e http://simplycpp.com/
Engenheiro de Software BM&FBovespa
http://www.bmfbovespa.com.br
Microsoft MVP Visual C++
http://bit.ly/desempenho_poliglota
Fabio Razzo Galuppo, M.Sc. Novembro 1973
• Mestrado em Engenharia Elétrica (Universidade Presbiteriana Mackenzie)
– Ciência da Computação - Inteligência Artificial
• Por mais de 10 anos premiado com Microsoft MVP em Visual C++
• Engenheiro de Software (Programador)
• Matemática Aplicada
• Linguagens de programação prediletas: – C++
– F#
– Haskell
• Rock’n’Roll – E boa música em geral
• http://fabiogaluppo.com
• https://github.com/fabiogaluppo
• http://simplycpp.com
Fab
io G
alu
pp
o -
htt
p:/
/mem
ber
.acm
.org
/~fa
bio
galu
pp
o -
fab
ioga
lup
po
@ac
m.o
rg
Fab
io G
alu
pp
o -
htt
p:/
/mem
ber
.acm
.org
/~fa
bio
galu
pp
o -
fab
ioga
lup
po
@ac
m.o
rg
𝑁 = 8 → 𝐶𝑜𝑛𝑡𝑎𝑔𝑒𝑚 = 8
𝑁 = 8 → 𝐶𝑜𝑛𝑡𝑎𝑔𝑒𝑚 = 3
3 = 𝑙𝑜𝑔28
Fab
io G
alu
pp
o -
htt
p:/
/mem
ber
.acm
.org
/~fa
bio
galu
pp
o -
fab
ioga
lup
po
@ac
m.o
rg
lg 𝑁
𝑁
Imperativo
𝑁2
𝑁3
Fab
io G
alu
pp
o -
htt
p:/
/mem
ber
.acm
.org
/~fa
bio
galu
pp
o -
fab
ioga
lup
po
@ac
m.o
rg
2 𝑁 + 𝑙𝑔 𝑁 − 1
Fab
io G
alu
pp
o -
htt
p:/
/mem
ber
.acm
.org
/~fa
bio
galu
pp
o -
fab
ioga
lup
po
@ac
m.o
rg
4 𝑁3
Fab
io G
alu
pp
o -
htt
p:/
/mem
ber
.acm
.org
/~fa
bio
galu
pp
o -
fab
ioga
lup
po
@ac
m.o
rg
Funcional
𝑁
𝑁2
𝑂(𝑁 lg 𝑁) ~1.2 𝑁 lg 𝑁
Composição
𝑂(𝑁) ~2 𝑁
Fab
io G
alu
pp
o -
htt
p:/
/mem
ber
.acm
.org
/~fa
bio
galu
pp
o -
fab
ioga
lup
po
@ac
m.o
rg
‘Big-Oh’ (O) Omega (Ω) Theta (Θ)
• Upper bound – ‘Big-Oh’ (O) – análogo a ≤
𝑔 𝑁 = 𝑂 𝑓 𝑛 𝑞𝑢𝑎𝑛𝑑𝑜 𝑎 𝑝𝑟𝑜𝑝𝑜𝑟çã𝑜 𝑔 𝑛
𝑓 𝑛é 𝑑𝑒𝑙𝑖𝑚𝑖𝑡𝑎𝑑𝑎 𝑝𝑜𝑟 𝑐𝑖𝑚𝑎 𝑞𝑢𝑎𝑛𝑑𝑜 𝑁 𝑡𝑒𝑛𝑑𝑒 𝑎𝑜 𝑖𝑛𝑓𝑖𝑛𝑖𝑡𝑜
• Lower bound – Omega (Ω) – análogo a ≥
𝑔 𝑁 = Ω 𝑓 𝑛 𝑞𝑢𝑎𝑛𝑑𝑜 𝑎 𝑝𝑟𝑜𝑝𝑜𝑟çã𝑜 𝑔 𝑛
𝑓 𝑛é 𝑑𝑒𝑙𝑖𝑚𝑖𝑡𝑎𝑑𝑎 𝑝𝑜𝑟 𝑏𝑎𝑖𝑥𝑜 𝑞𝑢𝑎𝑛𝑑𝑜 𝑁 𝑡𝑒𝑛𝑑𝑒 𝑎𝑜 𝑖𝑛𝑓𝑖𝑛𝑖𝑡𝑜
• Theta (Θ) – análogo a = 𝑔 𝑁 = Θ 𝑓 𝑛 𝑞𝑢𝑎𝑛𝑑𝑜 𝑓𝑜𝑟 𝑔 𝑁 = 𝑂 𝑓 𝑛 𝑒 𝑔 𝑁 = Ω 𝑓 𝑛
Fab
io G
alu
pp
o -
htt
p:/
/mem
ber
.acm
.org
/~fa
bio
galu
pp
o -
fab
ioga
lup
po
@ac
m.o
rg
O
Ω
Θ
Worst case • Strong guarantees, maybe unrealistic data
Average case • “Typical” input data
‘Big-Oh’ (O) Omega (Ω) Theta (Θ)
Fab
io G
alu
pp
o -
htt
p:/
/mem
ber
.acm
.org
/~fa
bio
galu
pp
o -
fab
ioga
lup
po
@ac
m.o
rg
𝑓1 𝑁 = 𝑁2 𝑓2 𝑁 = 3𝑁 + 10 𝑓3 𝑁 = 𝑁 + 2
𝑓2 𝑁 = 𝑂 𝑓3 𝑁 ∧ 𝑓2 𝑁 = 𝑂 𝑓3 𝑁 ⇒ 𝑓2 𝑁 = Θ 𝑓3 𝑁
𝑓2 𝑁 = 𝑂 𝑓1 𝑁
relação antisimétrica
𝑓1 𝑁 = Ω 𝑓3 𝑁
Dominância
• 𝐸𝑥𝑝𝑜𝑛𝑒𝑐𝑖𝑎𝑙 𝑑𝑜𝑚𝑖𝑛𝑎 𝑃𝑜𝑙𝑖𝑛𝑜𝑚𝑖𝑎𝑙
• 𝑁𝑎 𝑑𝑜𝑚𝑖𝑛𝑎 𝑁𝑏 𝑞𝑢𝑎𝑛𝑑𝑜 𝑎 > 𝑏
• 𝑃𝑜𝑙𝑖𝑛𝑜𝑚𝑖𝑎𝑙 𝑑𝑜𝑚𝑖𝑛𝑎 𝐿𝑜𝑔𝑎𝑟𝑖𝑡𝑚𝑜
𝑙𝑔 𝑁 < 𝑁 < 𝑙𝑔2𝑁 < 𝑁 < 𝑁 𝑙𝑔 𝑁 < 𝑁2 < 2𝑁 < 𝑁! < 2𝑁2
< 22𝑁< 𝑁2𝑁
regras de senso comun
Fab
io G
alu
pp
o -
htt
p:/
/mem
ber
.acm
.org
/~fa
bio
galu
pp
o -
fab
ioga
lup
po
@ac
m.o
rg
Função e Função Inversa 𝒇 𝒇−𝟏
lg 𝑁 2𝑁
𝑁 𝑁2
𝑁 1
𝑁
𝑁 lg 𝑁 2𝑁
𝑁
𝑁2 𝑁
𝑁3 𝑁3
2𝑁 lg 𝑁
𝑁! 𝑁!−1 “!−𝟏” deve ser uma aproximação
Fab
io G
alu
pp
o -
htt
p:/
/mem
ber
.acm
.org
/~fa
bio
galu
pp
o -
fab
ioga
lup
po
@ac
m.o
rg
𝑓 ∘ 𝑓−1 = 𝑖𝑑 (lg ∘ 2𝑥)(𝑁) = 𝑁
“!−1” Inversa do Fatorial
Γ−1
Γ N = (N − 1)! Γ N + 1 = N!
Approximated Inverse Gamma
http://fssnip.net/rw
Fab
io G
alu
pp
o -
htt
p:/
/mem
ber
.acm
.org
/~fa
bio
galu
pp
o -
fab
ioga
lup
po
@ac
m.o
rg
CLRS Problem 1.1 • http://answers-by-me.blogspot.com.br/2010/07/clrs-2e-problem-1-1.html
“I couldn't find how to achieve the value for n lg(n) for 1 second.”
“Sorry, I'm not good at this type of math. I asked the computer. Wolfram Alpha is really good at this stuff.”
lg 𝑁 = 106 𝑁 = 2106
Fab
io G
alu
pp
o -
htt
p:/
/mem
ber
.acm
.org
/~fa
bio
galu
pp
o -
fab
ioga
lup
po
@ac
m.o
rg
lg 𝑁 = 106 ∗ 60 𝑁 = 26∗107
• 1 segundo
• 1 minuto
𝑁! = 106 𝑁 = 106!−1
• 1 segundo
𝑓 𝑛 𝑐𝑜𝑚𝑝𝑙𝑒𝑥𝑖𝑡𝑦
𝑥 𝑖𝑛𝑠𝑡𝑟𝑢𝑐𝑡𝑖𝑜𝑛𝑠
𝑠𝑒𝑐𝑜𝑛𝑑
= 𝑡 𝑛 𝑠𝑒𝑐𝑜𝑛𝑑(𝑠) Equação do Problema
Alguma observação?
lg 𝑁
1
2
4 1 ∗ 2 ∗ 2 ∗ 2 = 23
Fab
io G
alu
pp
o -
htt
p:/
/mem
ber
.acm
.org
/~fa
bio
galu
pp
o -
fab
ioga
lup
po
@ac
m.o
rg
Know Thy Complexities!
• http://bigocheatsheet.com/
Fab
io G
alu
pp
o -
htt
p:/
/mem
ber
.acm
.org
/~fa
bio
galu
pp
o -
fab
ioga
lup
po
@ac
m.o
rg
Know Thy Machine!
Fab
io G
alu
pp
o -
htt
p:/
/mem
ber
.acm
.org
/~fa
bio
galu
pp
o -
fab
ioga
lup
po
@ac
m.o
rg
Medindo o tempo de execução
Fab
io G
alu
pp
o -
htt
p:/
/mem
ber
.acm
.org
/~fa
bio
galu
pp
o -
fab
ioga
lup
po
@ac
m.o
rg
stop_watch sw; … auto us = sw.elapsed_us().count(); sw.restart(); … auto ms = sw.elapsed_ms().count();
Análise Empírica
• Medir o tempo de execução com variações no tamanho de entrada (N)
Fab
io G
alu
pp
o -
htt
p:/
/mem
ber
.acm
.org
/~fa
bio
galu
pp
o -
fab
ioga
lup
po
@ac
m.o
rg
“Framework” para Análise Empírica
Fab
io G
alu
pp
o -
htt
p:/
/mem
ber
.acm
.org
/~fa
bio
galu
pp
o -
fab
ioga
lup
po
@ac
m.o
rg
https://github.com/fabiogaluppo/samples/tree/master/fragments/Measure
Preparar
Executar
Coletar
Análise dos dados
Fab
io G
alu
pp
o -
htt
p:/
/mem
ber
.acm
.org
/~fa
bio
galu
pp
o -
fab
ioga
lup
po
@ac
m.o
rg
Standard plot: T(N) x N Log-log plot: : log(T(N)) x log(N)
Tempo de execução estimado
Fab
io G
alu
pp
o -
htt
p:/
/mem
ber
.acm
.org
/~fa
bio
galu
pp
o -
fab
ioga
lup
po
@ac
m.o
rg
𝐿𝑒𝑖 𝑑𝑎 𝑃𝑜𝑡ê𝑛𝑐𝑖𝑎: 𝑎𝑁𝑏
Wrapping up
Fab
io G
alu
pp
o -
htt
p:/
/mem
ber
.acm
.org
/~fa
bio
galu
pp
o -
fab
ioga
lup
po
@ac
m.o
rg
Considerações sobre medição
• Medir com precisão é um grande desafio
• Efeitos independentes do sistema – Algoritmo e sua complexidade – Quantidade de dados (N) – Influência o expoente e a constante na lei da potência
• Efeitos dependentes do sistema – Hardware
• CPU, Memória, Cache, …
– Software • Compilador, Máquina virtual, GC, … • Sistema operacional, Rede, …
– Influência a constante na lei da potência
𝐿𝑒𝑖 𝑑𝑎 𝑃𝑜𝑡ê𝑛𝑐𝑖𝑎: 𝑎𝑁𝑏
Fab
io G
alu
pp
o -
htt
p:/
/mem
ber
.acm
.org
/~fa
bio
galu
pp
o -
fab
ioga
lup
po
@ac
m.o
rg
Ref.: http://algs4.cs.princeton.edu/14analysis/
Medindo código gerenciado
Fab
io G
alu
pp
o -
htt
p:/
/mem
ber
.acm
.org
/~fa
bio
galu
pp
o -
fab
ioga
lup
po
@ac
m.o
rg
Medindo tarefas em paralelo
Fab
io G
alu
pp
o -
htt
p:/
/mem
ber
.acm
.org
/~fa
bio
galu
pp
o -
fab
ioga
lup
po
@ac
m.o
rg
time_point
time_line_segment_1D
Desempenho poliglota Melhoria de performance independente de
linguagem ou plataforma
Fabio Galuppo, M.Sc. http://fabiogaluppo.com e http://simplycpp.com/
Engenheiro de Software BM&FBovespa
http://www.bmfbovespa.com.br
Microsoft MVP Visual C++
http://bit.ly/desempenho_poliglota
