Introduction¶
To achieve performant program is not easy¶
Many core computer science fields are involved...¶
- Hardware part: CPU architecture
- Operating systems
- Software part: compiler
We just introduce some basic and usual tricks to get performance.
Statistics - correlation coefficient¶
$$
\rho = \frac{\sum_{n}^{i=1} (X_i - \bar{X})(Y_i - \bar{Y})}{\sqrt{\sum_{n}^{i=1} (X_i - \bar{X})^2}\sqrt{\sum_{n}^{i=1} (Y_i - \bar{Y})^2}}
$$
Correlation¶
In [1]:
x = [2, 3, 4, 5, 6, 2, 3, 4, 5]
y = [32, 32, 5, 42, 6, 17, 19, 20, 24]
Out[1]:
Correlation¶
$$
\rho = \frac{\sum_{n}^{i=1} (X_i - \bar{X})(Y_i - \bar{Y})}{\sqrt{\sum_{n}^{i=1} (X_i - \bar{X})^2}\sqrt{\sum_{n}^{i=1} (Y_i - \bar{Y})^2}}
$$
In [2]:
n = length(x)
x̄ = sum(x) / n
ȳ = sum(y) / n
Out[2]:
In [3]:
x̂ = x .- x̄
ŷ = y .- ȳ
Out[3]:
Correlation¶
$$
\rho = \frac{\sum_{n}^{i=1} (X_i - \bar{X})(Y_i - \bar{Y})}{\sqrt{\sum_{n}^{i=1} (X_i - \bar{X})^2}\sqrt{\sum_{n}^{i=1} (Y_i - \bar{Y})^2}}
$$
In [4]:
ρ = sum(x̂ .* ŷ) / (sqrt(sum(x̂.^2))*sqrt(sum(ŷ.^2)))
Out[4]:
Abstraction with function¶
In [5]:
function correlation()
n = length(x)
@assert length(y) == n "Not matched sample size"
x̄ = sum(x) / n
ȳ = sum(y) / n
x̂ = x .- x̄
ŷ = y .- ȳ
ρ = sum(x̂ .* ŷ) / (sqrt(sum(x̂.^2))*sqrt(sum(ŷ.^2)))
return ρ
end
Out[5]:
Benchmark¶
In [6]:
using BenchmarkTools
In [7]:
correlation()
Out[7]:
In [8]:
@btime correlation()
Out[8]:
Benchmark¶
In [9]:
@benchmark correlation()
Out[9]:
Avoid global variables¶
In [10]:
function correlation(x, y)
n = length(x)
@assert length(y) == n "Not matched sample size"
x̄ = sum(x) / n
ȳ = sum(y) / n
x̂ = x .- x̄
ŷ = y .- ȳ
ρ = sum(x̂ .* ŷ) / (sqrt(sum(x̂.^2))*sqrt(sum(ŷ.^2)))
return ρ
end
Out[10]:
In [11]:
correlation(x, y)
Out[11]:
Avoid global variables¶
In [12]:
@btime correlation(x, y)
Out[12]:
In [13]:
@benchmark correlation(x, y)
Out[13]:
Avoid copy things¶
Copy drive program to allocate new memory space¶
In [14]:
x[2:8]
Out[14]:
In [15]:
@btime x[2:8]
Out[15]:
Avoid copy things¶
In [16]:
x_ = 5x .+ 1
Out[16]:
In [17]:
@btime x_ = 5x .+ 1
Out[17]:
View, copy and deepcopy¶
In [18]:
@btime x[2:8];
In [19]:
@btime view(x, 2:8);
View, copy and deepcopy¶
In [20]:
largeX = rand(100_000)
@btime largeX[10:10_010]; # get 10000 elements
In [21]:
@btime view(largeX, 10:10_010);
View, copy and deepcopy¶
In [22]:
X1 = [[1, 2, 3], [4, 5]]
Out[22]:
In [23]:
X2 = copy(X1) # shallow copy
Out[23]:
In [24]:
X2[1] === X1[1]
Out[24]:
View, copy and deepcopy¶
In [25]:
X3 = deepcopy(X1)
Out[25]:
In [26]:
X3[1] === X1[1]
Out[26]:
View, copy and deepcopy¶
In [27]:
@btime X2 = copy(X1);
In [28]:
@btime X3 = deepcopy(X1);
Avoid copy things¶
In [29]:
function correlation(x, y)
n = length(x)
@assert length(y) == n "Not matched sample size"
x̄ = sum(x) / n
ȳ = sum(y) / n
x̂ŷ = (x .- x̄).*(y .- ȳ)
x̂ = (x .- x̄).^2
ŷ = (y .- ȳ).^2
ρ = sum(x̂ŷ) / (sqrt(sum(x̂))*sqrt(sum(ŷ)))
return ρ
end
Out[29]:
In [30]:
correlation(x, y)
@benchmark correlation(x, y)
Out[30]:
Memory pre-allocation¶
In [31]:
function prealloc(X)
Y = similar(X, 10, 10)
# Y = Array{SOMETYPE}(undef, 10, 10)
# Y = fill(π, (2, 3, 4))
# do something
Y
end
Out[31]:
Memory storage order of arrays is column-major in Julia¶
In [32]:
function row_major(X)
s = 0.
for i = 1:size(X, 1)
for j = 1:size(X, 2)
s += X[i, j]
end
end
s
end
Out[32]:
In [33]:
X = rand(10_000, 10_000)
row_major(X)
@btime row_major(X)
Out[33]:
Memory storage order of arrays is column-major in Julia¶
In [34]:
function col_major(X)
s = 0.
for j = 1:size(X, 2)
for i = 1:size(X, 1)
s += X[i, j]
end
end
s
end
Out[34]:
In [35]:
col_major(X)
@btime col_major(X)
Out[35]:
Type stability¶
In [36]:
function type_instable(x)
if x > 1
return 5
else
return 5.0
end
end
Out[36]:
In [37]:
@code_warntype type_instable(4)
Union splitting¶
ret1 = function1(args...)
ret2 = function2(ret1, ...)
ret3 = function3(ret1, ret2, ...)Returns value of Any or Union{...}¶
Union splitting¶
ret1 = function1(args...) # ret1 isa Union{A,B}
if ret1 isa A
ret2 = function2_specialized_for_A(ret1, ...)
ret3 = function3_specialized_for_A(ret1, ret2, ...)
...
else
ret2 = function2_specialized_for_B(ret1, ...)
ret3 = function3_specialized_for_B(ret1, ret2, ...)
...
endRef: Union splitting
Type stability¶
In [38]:
@code_warntype correlation(x, y)
Achieving type stable¶
There are some convenient functions to get type information.
In [39]:
X = rand(3, 4)
eltype(X)
Out[39]:
From parametric methods...
In [40]:
function foo(A::Array{T}) where {T}
return zero(T)
end
Out[40]:
In [41]:
foo(rand(3,4))
Out[41]:
Achieving type stable¶
There are some ways to generate objects with known type information.
In [42]:
zero(Float64)
Out[42]:
In [43]:
one(Int64)
Out[43]:
In [44]:
zero(Bool)
Out[44]:
Boundary check¶
In [45]:
@btime col_major(X)
Out[45]:
In [46]:
function col_major2(X)
s = 0.
for j = 1:size(X, 2)
@inbounds for i = 1:size(X, 1)
s += X[i, j]
end
end
s
end
Out[46]:
In [47]:
col_major2(X)
@btime col_major2(X)
Out[47]:
Parallelism and concurrency¶
CPU-bound jobs¶
- Threading
- Multiprocess
I/O-bound jobs¶
- Threading
- Multitasking
Design principles¶
Write API (functions) as generic as possible.¶
Design types as specific and dynamic as possible.¶
If you are not sure how specific a type will be, let it be general.¶
Write API (functions) as generic as possible¶
In [48]:
function matrix_multiply(X, Y) # not "this" generic
n = size(X, 2)
@assert size(Y, 1) == n "Dimension dismatched!"
Z = similar(X, size(X, 1), size(Y, 2))
for i = 1:size(Z, 1), j = 1:size(Z, 2)
Z[i, j] = X[i, :] * Y[:, j]
end
return Z
end
Out[48]:
In [49]:
function matrix_multiply(X::Array, Y::Array) # good? generic?
n = size(X, 2)
@assert size(Y, 1) == n "Dimension dismatched!"
Z = similar(X, size(X, 1), size(Y, 2))
for i = 1:size(Z, 1), j = 1:size(Z, 2)
Z[i, j] = X[i, :] * Y[:, j]
end
return Z
end
Out[49]:
Write API (functions) as generic as possible¶
In [50]:
function matrix_multiply(X::AbstractArray{T,2}, Y::AbstractArray{T,2}) where {T} # generic
n = size(X, 2)
@assert size(Y, 1) == n "Dimension dismatched!"
Z = similar(X, size(X, 1), size(Y, 2))
for i = 1:size(Z, 1), j = 1:size(Z, 2)
Z[i, j] = X[i, :] * Y[:, j]
end
return Z
end
Out[50]:
Design types as "specific" and dynamic as possible¶
In [51]:
struct Point
x
y
end
In [ ]:
struct Point
x::Number
y::Number
end
Design types as "specific" and dynamic as possible¶
In [53]:
x = Point(2, 3.4)
Out[53]:
In [54]:
typeof(x)
Out[54]:
In [55]:
typeof(x).uid
Out[55]:
In [56]:
y = Point(2., 3.4)
Out[56]:
In [57]:
typeof(x).uid
Out[57]:
Design types as "specific" and dynamic as possible¶
In [1]:
struct Point{T<:Number}
x::T
y::T
end
In [2]:
x = Point(2, 3)
Out[2]:
In [3]:
y = Point(2., 3.)
Out[3]:
Design types as "specific" and dynamic as possible¶
In [4]:
typeof(x)
Out[4]:
In [5]:
typeof(x).uid
Out[5]:
In [6]:
typeof(y)
Out[6]:
In [7]:
typeof(y).uid
Out[7]:
Advanced in hardware part¶
Memory hierarchy¶
Register/cache volume is limited.¶
Cache miss¶
- L1 cache: ~32K
- L2 cache: 256K
- L3 cache: 3072K
Page fault¶
Advanced in software part¶
Overview of a compiler¶
Compile time¶
Runtime¶
Compiler in details¶
Julia compiler¶
Julia compiler¶
Julia runtime¶
Julia JIT compiler¶
