Skip to content

Instantly share code, notes, and snippets.

@carlobaldassi
Last active August 29, 2015 14:13
Show Gist options
  • Save carlobaldassi/683bcf2ec8b9a10687e2 to your computer and use it in GitHub Desktop.
Save carlobaldassi/683bcf2ec8b9a10687e2 to your computer and use it in GitHub Desktop.
NullableVector performance with random access
module NV
immutable NullableVector{T}
isnull::BitVector
values::Vector{T}
end
@inline Base.length(nv::NullableVector) = length(nv.isnull)
@inline function Base.getindex(nv::NullableVector{Float64}, i::Integer)
if nv.isnull[i]
return Nullable{Float64}()
else
@inbounds x = Nullable{Float64}(nv.values[i])
return x
end
end
@inline function Base.unsafe_getindex(nv::NullableVector{Float64}, i::Integer)
if Base.unsafe_getindex(nv.isnull, i)
return Nullable{Float64}()
else
@inbounds x = nv.values[i]
return Nullable{Float64}(x)
end
end
function f1(nv::NullableVector{Float64}, I::Vector{Int})
s, n = 0.0, 0
for i in I
nv_i = nv[i]
#nv_i = Base.unsafe_getindex(nv, i)
if !isnull(nv_i)
s += get(nv_i)
n += 1
end
end
return s / n
end
function f2(nv::NullableVector{Float64}, I)
s, n = 0.0, 0
for i in I
if !isnull(nv[i])
#if !isnull(Base.unsafe_getindex(nv, i))
#s += get(Base.unsafe_getindex(nv, i))
s += get(nv[i])
n += 1
end
end
return s / n
end
function g1(v::Vector{Float64}, I)
s, n = 0.0, 0
for i in I
v_i = v[i]
if !isnan(v_i)
s += v_i
n += 1
end
end
return s / n
end
function g2(v::Vector{Float64}, I)
s, n = 0.0, 0
for i in I
if !isnan(v[i])
s += v[i]
n += 1
end
end
return s / n
end
function h1(v::Vector{Nullable{Float64}}, I)
s, n = 0.0, 0
for i in I
v_i = v[i]
if !isnull(v_i)
s += get(v_i)
n += 1
end
end
return s / n
end
function h2(v::Vector{Nullable{Float64}}, I)
s, n = 0.0, 0
for i in I
if !isnull(v[i])
s += get(v[i])
n += 1
end
end
return s / n
end
function bench(p = 0.01)
N = 50_000_000
v = randn(N)
m = bitpack(Bool[rand() < p for i = 1:N])
nv = NullableVector(m, copy(v))
vn = Nullable{Float64}[m[i] ? Nullable{Float64}(v[i]) : Nullable{Float64}() for i = 1:length(v)]
ii = randperm(N)
@printf("NullableVector{Float64} w/ One GetIndex Call\n")
f1(nv, ii)
@time f1(nv, ii)
@time f1(nv, ii)
@time f1(nv, ii)
@printf("NullableVector{Float64} w/ Two GetIndex Calls\n")
f2(nv, ii)
@time f2(nv, ii)
@time f2(nv, ii)
@time f2(nv, ii)
@printf("Vector{Float64} w/ One GetIndex Call\n")
g1(v, ii)
@time g1(v, ii)
@time g1(v, ii)
@time g1(v, ii)
@printf("Vector{Float64} w/ Two GetIndex Calls\n")
g2(v, ii)
@time g2(v, ii)
@time g2(v, ii)
@time g2(v, ii)
@printf("Vector{Nullable{Float64}} w/ One GetIndex Call\n")
h1(vn, ii)
@time h1(vn, ii)
@time h1(vn, ii)
@time h1(vn, ii)
@printf("Vector{Nullable{Float64}} w/ Two GetIndex Calls\n")
h2(vn, ii)
@time h2(vn, ii)
@time h2(vn, ii)
@time h2(vn, ii)
nothing
end
end
@carlobaldassi
Copy link
Author

results for various null density levels:

julia-0.4> include("nullablerand.jl")

julia-0.4> NV.bench(0.0)
NullableVector{Float64} w/ One GetIndex Call
elapsed time: 1.146188245 seconds (0 bytes allocated)
elapsed time: 1.151216665 seconds (0 bytes allocated)
elapsed time: 1.154522892 seconds (0 bytes allocated)
NullableVector{Float64} w/ Two GetIndex Calls
elapsed time: 1.523406065 seconds (0 bytes allocated)
elapsed time: 1.531938419 seconds (0 bytes allocated)
elapsed time: 1.537242369 seconds (0 bytes allocated)
Vector{Float64} w/ One GetIndex Call
elapsed time: 0.553870195 seconds (0 bytes allocated)
elapsed time: 0.558312912 seconds (0 bytes allocated)
elapsed time: 0.559405782 seconds (0 bytes allocated)
Vector{Float64} w/ Two GetIndex Calls
elapsed time: 0.554607352 seconds (0 bytes allocated)
elapsed time: 0.557769018 seconds (0 bytes allocated)
elapsed time: 0.564174947 seconds (0 bytes allocated)
Vector{Nullable{Float64}} w/ One GetIndex Call
elapsed time: 0.5614622 seconds (0 bytes allocated)
elapsed time: 0.566100534 seconds (0 bytes allocated)
elapsed time: 0.565256886 seconds (0 bytes allocated)
Vector{Nullable{Float64}} w/ Two GetIndex Calls
elapsed time: 0.558627486 seconds (0 bytes allocated)
elapsed time: 0.563106164 seconds (0 bytes allocated)
elapsed time: 0.562701764 seconds (0 bytes allocated)

julia-0.4> NV.bench(0.01)
NullableVector{Float64} w/ One GetIndex Call
elapsed time: 1.150051923 seconds (0 bytes allocated)
elapsed time: 1.24187693 seconds (0 bytes allocated)
elapsed time: 1.15390715 seconds (0 bytes allocated)
NullableVector{Float64} w/ Two GetIndex Calls
elapsed time: 1.515997756 seconds (0 bytes allocated)
elapsed time: 1.530931078 seconds (0 bytes allocated)
elapsed time: 1.533823367 seconds (0 bytes allocated)
Vector{Float64} w/ One GetIndex Call
elapsed time: 0.557882411 seconds (0 bytes allocated)
elapsed time: 0.559283549 seconds (0 bytes allocated)
elapsed time: 0.558107822 seconds (0 bytes allocated)
Vector{Float64} w/ Two GetIndex Calls
elapsed time: 0.553486253 seconds (0 bytes allocated)
elapsed time: 0.559940933 seconds (0 bytes allocated)
elapsed time: 0.559007651 seconds (0 bytes allocated)
Vector{Nullable{Float64}} w/ One GetIndex Call
elapsed time: 0.558259622 seconds (0 bytes allocated)
elapsed time: 0.565396847 seconds (0 bytes allocated)
elapsed time: 0.564465371 seconds (0 bytes allocated)
Vector{Nullable{Float64}} w/ Two GetIndex Calls
elapsed time: 0.56205272 seconds (0 bytes allocated)
elapsed time: 0.56407918 seconds (0 bytes allocated)
elapsed time: 0.573541347 seconds (0 bytes allocated)

julia-0.4> NV.bench(0.1)
NullableVector{Float64} w/ One GetIndex Call
elapsed time: 1.139535742 seconds (0 bytes allocated)
elapsed time: 1.149858357 seconds (0 bytes allocated)
elapsed time: 1.148761751 seconds (0 bytes allocated)
NullableVector{Float64} w/ Two GetIndex Calls
elapsed time: 1.460584872 seconds (0 bytes allocated)
elapsed time: 1.477932682 seconds (0 bytes allocated)
elapsed time: 1.483934502 seconds (0 bytes allocated)
Vector{Float64} w/ One GetIndex Call
elapsed time: 0.554665429 seconds (0 bytes allocated)
elapsed time: 0.556376832 seconds (0 bytes allocated)
elapsed time: 0.558535168 seconds (0 bytes allocated)
Vector{Float64} w/ Two GetIndex Calls
elapsed time: 0.553768081 seconds (0 bytes allocated)
elapsed time: 0.558001195 seconds (0 bytes allocated)
elapsed time: 0.557609126 seconds (0 bytes allocated)
Vector{Nullable{Float64}} w/ One GetIndex Call
elapsed time: 0.592140405 seconds (0 bytes allocated)
elapsed time: 0.598327515 seconds (0 bytes allocated)
elapsed time: 0.597642932 seconds (0 bytes allocated)
Vector{Nullable{Float64}} w/ Two GetIndex Calls
elapsed time: 0.603696063 seconds (0 bytes allocated)
elapsed time: 0.604752132 seconds (0 bytes allocated)
elapsed time: 0.604166621 seconds (0 bytes allocated)

julia-0.4> NV.bench(0.5)
NullableVector{Float64} w/ One GetIndex Call
elapsed time: 1.303342041 seconds (0 bytes allocated)
elapsed time: 1.230132294 seconds (0 bytes allocated)
elapsed time: 1.303892015 seconds (0 bytes allocated)
NullableVector{Float64} w/ Two GetIndex Calls
elapsed time: 1.314977126 seconds (0 bytes allocated)
elapsed time: 1.431401299 seconds (0 bytes allocated)
elapsed time: 1.363359195 seconds (0 bytes allocated)
Vector{Float64} w/ One GetIndex Call
elapsed time: 0.55433741 seconds (0 bytes allocated)
elapsed time: 0.555873428 seconds (0 bytes allocated)
elapsed time: 0.554827365 seconds (0 bytes allocated)
Vector{Float64} w/ Two GetIndex Calls
elapsed time: 0.552833005 seconds (0 bytes allocated)
elapsed time: 0.55589714 seconds (0 bytes allocated)
elapsed time: 0.554077712 seconds (0 bytes allocated)
Vector{Nullable{Float64}} w/ One GetIndex Call
elapsed time: 0.779385348 seconds (0 bytes allocated)
elapsed time: 0.780717765 seconds (0 bytes allocated)
elapsed time: 0.778200042 seconds (0 bytes allocated)
Vector{Nullable{Float64}} w/ Two GetIndex Calls
elapsed time: 0.859718395 seconds (0 bytes allocated)
elapsed time: 0.818399247 seconds (0 bytes allocated)
elapsed time: 0.825060995 seconds (0 bytes allocated)

julia-0.4> NV.bench(1.0)
NullableVector{Float64} w/ One GetIndex Call
elapsed time: 0.571799323 seconds (0 bytes allocated)
elapsed time: 0.560864147 seconds (0 bytes allocated)
elapsed time: 0.55581117 seconds (0 bytes allocated)
NullableVector{Float64} w/ Two GetIndex Calls
elapsed time: 0.467057655 seconds (0 bytes allocated)
elapsed time: 0.487368138 seconds (0 bytes allocated)
elapsed time: 0.488164056 seconds (0 bytes allocated)
Vector{Float64} w/ One GetIndex Call
elapsed time: 0.561767431 seconds (0 bytes allocated)
elapsed time: 0.564563401 seconds (0 bytes allocated)
elapsed time: 0.564999271 seconds (0 bytes allocated)
Vector{Float64} w/ Two GetIndex Calls
elapsed time: 0.558057504 seconds (0 bytes allocated)
elapsed time: 0.566488551 seconds (0 bytes allocated)
elapsed time: 0.564020264 seconds (0 bytes allocated)
Vector{Nullable{Float64}} w/ One GetIndex Call
elapsed time: 0.596757108 seconds (0 bytes allocated)
elapsed time: 0.60627829 seconds (0 bytes allocated)
elapsed time: 0.592553742 seconds (0 bytes allocated)
Vector{Nullable{Float64}} w/ Two GetIndex Calls
elapsed time: 0.761548558 seconds (0 bytes allocated)
elapsed time: 0.769526483 seconds (0 bytes allocated)
elapsed time: 0.771952209 seconds (0 bytes allocated)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment