NullableVector performance with random access

nullablerand.jl

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

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)