Skip to content

Instantly share code, notes, and snippets.

@carlobaldassi

carlobaldassi/bitarray_perf_comparison.txt

Created June 1, 2013 19:22
Show Gist options
  • Save carlobaldassi/5691454 to your computer and use it in GitHub Desktop.
Save carlobaldassi/5691454 to your computer and use it in GitHub Desktop.
Download ZIP
BitArray performance comparisons
Raw
bitarray_perf_comparison.txt
b = BitArray(10_000_017); fill!(b, true)
2x4 DataFrame:
Function Elapsed Relative Replications
[1,] "oldfill" 0.703632 3.394 1000
[2,] "newfill" 0.207316 1.0 1000
b1 = randbool(10_000_117); b2 = randbool(10_000_017); copy!(b1, b2)
2x4 DataFrame:
Function Elapsed Relative Replications
[1,] "oldcopy" 0.834918 2.37655 1000
[2,] "newcopy" 0.351316 1.0 1000
b = randbool(10_000_117); convert(Array{Int}, b)
2x4 DataFrame:
Function Elapsed Relative Replications
[1,] "oldconvert" 11.2007 7.20337 10
[2,] "newconvert" 1.55492 1.0 10
a = rand(0:1, 1_000_017); convert(BitArray, a)
2x4 DataFrame:
Function Elapsed Relative Replications
[1,] "oldconvert" 2.0255 1.58136 20
[2,] "newconvert" 1.28086 1.0 20
a = {rand(0:1) for i = 1:1_017}; convert(BitArray, a)
2x4 DataFrame:
Function Elapsed Relative Replications
[1,] "oldconvert" 0.320322 1.16844 10
[2,] "newconvert" 0.274146 1.0 10
b = BitArray(10_000_017); bitarray_rand_fill!(b)
2x4 DataFrame:
Function Elapsed Relative Replications
[1,] "oldrandfill" 2.39907 1.20137 1000
[2,] "newrandfill" 1.99694 1.0 1000
b = randbool(10_000); I = rand(1:10_000, 10_000); b[I]
2x4 DataFrame:
Function Elapsed Relative Replications
[1,] "oldgetindex" 1.43322 6.71223 1000
[2,] "newgetindex" 0.213524 1.0 1000
b = randbool(100, 100); I1 = rand(1:100, 100); I2 = rand(1:100, 100); b[I1,I2]
2x4 DataFrame:
Function Elapsed Relative Replications
[1,] "oldgetindex" 1.9024 1.10048 1000
[2,] "newgetindex" 1.72869 1.0 1000
b = randbool(1_000_000); I = randbool(1_000_000); b[I]
2x4 DataFrame:
Function Elapsed Relative Replications
[1,] "oldgetindex" 1.18848 2.19207 10
[2,] "newgetindex" 0.542172 1.0 10
b = randbool(1_000_000); I = bitunpack(randbool(1_000_000)); b[I]
2x4 DataFrame:
Function Elapsed Relative Replications
[1,] "oldgetindex" 0.704441 4.51643 10
[2,] "newgetindex" 0.155973 1.0 10
b = randbool(1_000_017); I = randbool(1_000_017); b[I] = true
2x4 DataFrame:
Function Elapsed Relative Replications
[1,] "oldsetindex" 2.86153 1.0 50
[2,] "newsetindex" 2.90139 1.01393 50
b = randbool(1_000_017); I = bitunpack(randbool(1_000_017)); b[I] = true
2x4 DataFrame:
Function Elapsed Relative Replications
[1,] "oldsetindex" 10.048 1.04502 100
[2,] "newsetindex" 9.61514 1.0 100
b = randbool(1_000_000); I = randbool(1_000_000); X = randbool(nnz(I)); b[I] = X
2x4 DataFrame:
Function Elapsed Relative Replications
[1,] "oldsetindex" 0.806377 1.0 10
[2,] "newsetindex" 0.879788 1.09104 10
b = randbool(1_000_000); I = bitunpack(randbool(1_000_000)); X = randbool(nnz(I)); b[I] = X
2x4 DataFrame:
Function Elapsed Relative Replications
[1,] "oldsetindex" 0.419165 1.26231 10
[2,] "newsetindex" 0.332061 1.0 10
b = randbool(1_000_000); I = bitunpack(randbool(1_000_000)); X = bitunpack(randbool(nnz(I))); b[I] = X
2x4 DataFrame:
Function Elapsed Relative Replications
[1,] "oldsetindex" 0.123026 1.02952 10
[2,] "newsetindex" 0.119498 1.0 10
b = randbool(1_000_000); -b
2x4 DataFrame:
Function Elapsed Relative Replications
[1,] "oldunaryminus" 4.38952 1.46101 200
[2,] "newunaryminus" 3.00445 1.0 200
b = randbool(1_000_017); ~b
2x4 DataFrame:
Function Elapsed Relative Replications
[1,] "oldbitnot" 18.0818 9.30296 10000
[2,] "newbitnot" 1.94367 1.0 10000
b = randbool(1_000_017); flipbits!(b)
2x4 DataFrame:
Function Elapsed Relative Replications
[1,] "oldflipbits" 6.47089 3.20978 100000
[2,] "newflipbits" 2.01599 1.0 100000
b = randbool(1_000_017); x = 2; (div(b,x),mod(b,x))
2x4 DataFrame:
Function Elapsed Relative Replications
[1,] "olddivmod" 6.25411 4.4016 20
[2,] "newdivmod" 1.42087 1.0 20
b = randbool(1_000_017); x = 2.0; (div(b,x),mod(b,x))
2x4 DataFrame:
Function Elapsed Relative Replications
[1,] "olddivmod" 13.6185 7.50146 40
[2,] "newdivmod" 1.81545 1.0 40
b1 = randbool(1_000_017); b2 = randbool(1_000_017; (b1&b2, b1|b2, b1$b2)
2x4 DataFrame:
Function Elapsed Relative Replications
[1,] "oldandorxor" 8.56246 18.8855 1000
[2,] "newandorxor" 0.453389 1.0 1000
b1 = randbool(1_000_017); b2 = randbool(1_000_017); b1 .^ b2
2x4 DataFrame:
Function Elapsed Relative Replications
[1,] "oldpow" 2.80608 16.3882 1000
[2,] "newpow" 0.171226 1.0 1000
b = randbool(1_000_017); x = -2.0; b .^ x
2x4 DataFrame:
Function Elapsed Relative Replications
[1,] "oldpow" 1.67773 5.53508 10
[2,] "newpow" 0.303108 1.0 10
b = randbool(1_000_017); a = rand(0:5, 1_000_017); b .^ a
2x4 DataFrame:
Function Elapsed Relative Replications
[1,] "oldpow" 1.65294 2.11172 20
[2,] "newpow" 0.782746 1.0 20
a = rand(1_000_017); x = 0.5; a .< x
2x4 DataFrame:
Function Elapsed Relative Replications
[1,] "oldlt" 1.2469 1.61651 200
[2,] "newlt" 0.771353 1.0 200
a = rand(1_000_017); b = rand(1_000_017); a .< b
2x4 DataFrame:
Function Elapsed Relative Replications
[1,] "oldlt" 1.56158 1.69547 200
[2,] "newlt" 0.921032 1.0 200
b = [falses(100_000_000), randbool(17)]; (findnext(b, 1), findnext(b, 100_000_010))
2x4 DataFrame:
Function Elapsed Relative Replications
[1,] "oldfindnext" 3.23528 1.26685 1000
[2,] "newfindnext" 2.55381 1.0 1000
b = [trues(100_000_000), randbool(17)]; (findnextnot(b, 1), findnextnot(b, 100_000_010))
2x4 DataFrame:
Function Elapsed Relative Replications
[1,] "oldfindnextnot" 3.98593 1.47118 1000
[2,] "newfindnextnot" 2.70935 1.0 1000
b = randbool(1_000_017)]; find(b)
2x4 DataFrame:
Function Elapsed Relative Replications
[1,] "oldfind" 5.98756 10.8875 100
[2,] "newfind" 0.54995 1.0 100
b = [trues(9_999_900), randbool(117)]; all(b)
2x4 DataFrame:
Function Elapsed Relative Replications
[1,] "oldall" 3.38011 2.52766 10000
[2,] "newall" 1.33725 1.0 10000
b = [trues(9_999_900), randbool(117)]; any(b)
2x4 DataFrame:
Function Elapsed Relative Replications
[1,] "oldany" 2.70628 1.6008 10000
[2,] "newany" 1.69058 1.0 10000
Raw
bitperf.jl
module BitPerf
using Benchmark
const _msk64 = ~uint64(0)
macro _mskr(l) :(_msk64 >>> (64-$(esc(l)))) end
macro _div64(l) :($(esc(l)) >>> 6) end
macro _mod64(l) :($(esc(l)) & 63) end
macro _msk_end(l) :(@_mskr @_mod64 $(esc(l))) end
num_bit_chunks(n::Int) = @_div64 (n+63)
const bitcache_chunks = 1024 # this can be changed
const bitcache_size = 64 * bitcache_chunks # do not change this
import Base.getindex_unchecked, Base.setindex_unchecked,
Base.get_chunks_id, Base.bitarray_rand_fill!, Base.to_index,
Base.indices, Base.gen_cartesian_map,
Base.promote_array_type, Base.dumpbitcache,
Base.findnextnot
#function getindex_unchecked(pBc::Ptr{Uint64}, i::Integer)
#i1, i2 = get_chunks_id(i)
#u = uint64(1)
#return (unsafe_load(pBc, i1) >>> i2) & u == u
#end
#
#function setindex_unchecked(pBc::Ptr{Uint64}, x, i::Integer)
#x = convert(Bool, x)
#i1, i2 = get_chunks_id(i)
#u = uint64(1) << i2
#c = unsafe_load(pBc, i1)
#if x
#c |= u
#else
#c &= ~u
#end
#unsafe_store!(pBc, c, i1)
#end
# this is unsafe in 2 ways:
# 1) no boundary checking
# 2) calling functions must keep a reference to the
# original Array to avoid garbage collection
# (e.g. A=UnsafeArray(A) is dangerous)
# it must be used with care!
immutable UnsafeArray{T} <: AbstractArray
p::Ptr{T}
l::Int
function UnsafeArray(A::Array{T})
new(pointer(A), length(A))
end
end
UnsafeArray{T}(A::Array{T}) = UnsafeArray{T}(A)
Base.getindex(uA::UnsafeArray, i::Int) = unsafe_load(uA.p, i)
Base.setindex!{T}(uA::UnsafeArray{T}, x, i::Int) = unsafe_store!(uA.p, x, i)
Base.setindex!{T}(uA::UnsafeArray{T}, x, r::Range1) = for i in r unsafe_store!(uA.p, x, i); end
Base.length(uA::UnsafeArray) = uA.l
Base.start(uA::UnsafeArray) = 1
Base.next(uA::UnsafeArray, ind::Int) = (uA[ind], ind+1)
Base.done(uA::UnsafeArray, ind::Int) = ind > length(uA)
# see comments on UsafeArray
immutable UnsafeBitArray <: AbstractArray
p::Ptr{Uint64}
l::Int
function UnsafeBitArray(B::BitArray)
new(pointer(B.chunks), length(B))
end
end
Base.getindex(uB::UnsafeBitArray, i::Int) = getindex_unchecked(uB.p, i)
Base.setindex!(uB::UnsafeBitArray, x, i::Int) = setindex_unchecked(uB.p, x, i)
Base.length(uB::UnsafeBitArray) = uB.l
unsafe{T}(A::Array{T}) = UnsafeArray(A)
unsafe(B::BitArray) = UnsafeBitArray(B)
unsafechunks(B::BitArray) = unsafe(B.chunks)
function new_fill!(B::BitArray, x)
y = convert(Bool, x)
Bc = unsafechunks(B)
if !y
for i = 1:length(Bc)
Bc[i] = 0
end
else
lB = length(B)
if lB == 0
return B
end
lBc = length(Bc)
for i = 1:lBc-1
Bc[i] = _msk64
end
Bc[end] = @_msk_end length(B)
end
return B
end
function dotest_fill()
const b = BitArray(10_000_017)
oldfill() = fill!(b, true)
newfill() = new_fill!(b, true)
@assert oldfill().chunks == newfill().chunks
println("b = BitArray(10_000_017); fill!(b, true)")
println(compare([oldfill, newfill], 1000))
end
function new_copy!(dest::BitArray, src::BitArray)
destc = unsafechunks(dest)
srcc = unsafechunks(src)
nc_d = length(destc)
nc_s = length(srcc)
nc = min(nc_s, nc_d)
if nc == 0
return dest
end
for i = 1:nc-1
destc[i] = srcc[i]
end
if length(src) >= length(dest)
destc[nc] = srcc[nc]
else
msk_s = @_msk_end length(src)
msk_d = ~msk_s
destc[nc] = (msk_d & destc[nc]) | (msk_s & srcc[nc])
end
return dest
end
function dotest_copy()
const b1 = randbool(10_000_117)
const b2 = randbool(10_000_017)
const c1 = copy(b1)
const c2 = copy(b2)
oldcopy() = copy!(b1, b2)
newcopy() = new_copy!(c1, c2)
@assert oldcopy().chunks == newcopy().chunks
println("b1 = randbool(10_000_117); b2 = randbool(10_000_017); copy!(b1, b2)")
println(compare([oldcopy, newcopy], 1000))
end
function new_convert{T,N}(::Type{Array{T,N}}, B::BitArray{N})
A = Array(T, size(B))
uB = unsafe(B)
if isbits(T)
uA = UnsafeArray(A)
for i = 1:length(A)
uA[i] = uB[i]
end
else
for i = 1:length(A)
A[i] = uB[i]
end
end
return A
end
function dotest_convert1()
const b = randbool(10_000_117)
oldconvert() = convert(Array{Int}, b)
newconvert() = new_convert(Array{Int}, b)
@assert oldconvert() == newconvert()
println("b = randbool(10_000_117); convert(Array{Int}, b)")
println(compare([oldconvert, newconvert], 10))
end
function dotest_convert2()
const b = randbool(100_117)
oldconvert() = convert(Array{BigInt}, b)
newconvert() = new_convert(Array{BigInt}, b)
@assert oldconvert() == newconvert()
println("b = randbool(10_000_117); convert(Array{BigInt}, b)")
println(compare([oldconvert, newconvert], 100))
end
macro convert_to_bitarray(Bc, A, l)
quote
ind = 1
for i = 1:length($(esc(Bc)))-1
u = uint64(1)
c = uint64(0)
for j = 1:64
if bool($(esc(A))[ind])
c |= u
end
ind += 1
u <<= 1
end
$(esc(Bc))[i] = c
end
u = uint64(1)
c = uint64(0)
for j = 0:@_mod64($(esc(l))-1)
if bool($(esc(A))[ind])
c |= u
end
ind += 1
u <<= 1
end
$(esc(Bc))[end] = c
end
end
function convert_to_bitarray_frombits(Bc::UnsafeArray{Uint64}, A::Array, l::Int)
uA = unsafe(A)
@convert_to_bitarray(Bc, uA, l)
end
function convert_to_bitarray_fromnonbits(Bc::UnsafeArray{Uint64}, A::Array, l::Int)
@convert_to_bitarray(Bc, A, l)
end
new_convert{T,N}(::Type{BitArray}, A::AbstractArray{T,N}) = new_convert(BitArray{N},A)
function new_convert{T,N}(::Type{BitArray{N}}, A::AbstractArray{T,N})
B = BitArray(size(A))
l = length(B)
if l == 0
return B
end
Bc = unsafechunks(B)
if isa(A, Array) && isbits(T)
convert_to_bitarray_frombits(Bc, A, l)
else
convert_to_bitarray_fromnonbits(Bc, A, l)
end
return B
end
function dotest_convert3()
const a = rand(0:1, 10_000_017)
oldconvert() = convert(BitArray, a)
newconvert() = new_convert(BitArray, a)
@assert oldconvert() == newconvert()
println("a = rand(0:1, 1_000_017); convert(BitArray, a)")
println(compare([oldconvert, newconvert], 20))
end
function dotest_convert4()
const a = {rand(0:1) for i = 1:1_000_017}
oldconvert() = convert(BitArray, a)
newconvert() = new_convert(BitArray, a)
@assert oldconvert() == newconvert()
println("a = {rand(0:1) for i = 1:1_017}; convert(BitArray, a)")
println(compare([oldconvert, newconvert], 10))
end
function new_bitarray_rand_fill!(B::BitArray)
if length(B) == 0
return B
end
Bc = unsafechunks(B)
for i = 1:length(Bc)-1
Bc[i] = rand(Uint64)
end
msk = @_msk_end length(B)
Bc[end] = msk & rand(Uint64)
return B
end
function dotest_randfill()
const b = BitArray(10_000_017)
oldrandfill() = (srand(1); bitarray_rand_fill!(b))
newrandfill() = (srand(1); new_bitarray_rand_fill!(b))
@assert oldrandfill().chunks == newrandfill().chunks
println("b = BitArray(10_000_017); bitarray_rand_fill!(b)")
println(compare([oldrandfill, newrandfill], 1000))
end
function new_getindex{T<:Real}(B::BitArray, I::AbstractVector{T})
X = BitArray(length(I))
lB = length(B)
uX = UnsafeBitArray(X) # this is faster than unsafe(X)
uB = unsafe(B)
ind = 1
for i in I
# faster X[ind] = B[i]
i = to_index(i)
if i < 1 || i > lB
throw(BoundsError())
end
uX[ind] = uB[i]
ind += 1
end
return X
end
function dotest_getindex1()
const I = rand(1:10_000, 10_000)
const b = randbool(10_000)
oldgetindex() = getindex(b, I)
newgetindex() = new_getindex(b, I)
@assert oldgetindex().chunks == newgetindex().chunks
println("b = randbool(10_000); I = rand(1:10_000, 10_000); b[I]")
println(compare([oldgetindex, newgetindex], 1000))
end
let getindex_cache = nothing
global new_getindex
function new_getindex(B::BitArray, I::Union(Real,AbstractVector)...)
I = indices(I)
X = BitArray(index_shape(I...))
uX = unsafe(X)
if is(getindex_cache,nothing)
getindex_cache = Dict()
end
gen_cartesian_map(getindex_cache, ivars -> quote
uX[ind] = B[$(ivars...)]
ind += 1
end, I, (:B, :uX, :ind), B, uX, 1)
return X
end
end
function dotest_getindex2()
const I1 = rand(1:100, 100)
const I2 = rand(1:100, 100)
const b = randbool(100, 100)
oldgetindex() = getindex(b, I1, I2)
newgetindex() = new_getindex(b, I1, I2)
@assert oldgetindex().chunks == newgetindex().chunks
println("b = randbool(100, 100); I1 = rand(1:100, 100); I2 = rand(1:100, 100); b[I1,I2]")
println(compare([oldgetindex, newgetindex], 1000))
end
function new_getindex_bool_1d(B::BitArray, I::AbstractArray{Bool})
n = sum(I)
X = BitArray(n)
lI = length(I)
if lI != length(B)
throw(BoundsError())
end
uX = UnsafeBitArray(X) # this is faster than unsafe(X)
uB = unsafe(B)
ind = 1
for i = 1:length(I)
if I[i]
uX[ind] = uB[i]
ind += 1
end
end
return X
end
new_getindex(B::BitVector, I::AbstractVector{Bool}) = new_getindex_bool_1d(B, I)
function dotest_getindex3()
const I = randbool(1_000_000)
const b = randbool(1_000_000)
oldgetindex() = getindex(b, I)
newgetindex() = new_getindex(b, I)
@assert oldgetindex().chunks == newgetindex().chunks
println("b = randbool(1_000_000); I = randbool(1_000_000); b[I]")
println(compare([oldgetindex, newgetindex], 10))
end
function dotest_getindex4()
const I = bitunpack(randbool(1_000_000))
const b = randbool(1_000_000)
oldgetindex() = getindex(b, I)
newgetindex() = new_getindex(b, I)
@assert oldgetindex().chunks == newgetindex().chunks
println("b = randbool(1_000_000); I = bitunpack(randbool(1_000_000)); b[I]")
println(compare([oldgetindex, newgetindex], 10))
end
function new_setindex_bool_scalar_1d(A::BitArray, x, I::AbstractArray{Bool})
if length(I) > length(A)
throw(BoundsError())
end
x = bool(x)
uA = unsafe(A)
for i = 1:length(I)
if I[i]
uA[i] = x
end
end
A
end
new_setindex!(A::BitArray, x, I::AbstractVector{Bool}) = new_setindex_bool_scalar_1d(A, x, I)
function dotest_setindex1()
const I = randbool(1_000_017)
const b = randbool(1_000_017)
oldsetindex() = setindex!(b, true, I)
newsetindex() = new_setindex!(b, true, I)
@assert oldsetindex().chunks == newsetindex().chunks
println("b = randbool(1_000_017); I = randbool(1_000_017); b[I] = true")
println(compare([oldsetindex, newsetindex], 50))
end
function dotest_setindex2()
const I = bitunpack(randbool(1_000_0017))
const b = randbool(1_000_0017)
oldsetindex() = setindex!(b, true, I)
newsetindex() = new_setindex!(b, true, I)
@assert oldsetindex().chunks == newsetindex().chunks
println("b = randbool(1_000_017); I = bitunpack(randbool(1_000_017)); b[I] = true")
println(compare([oldsetindex, newsetindex], 100))
end
function new_setindex_bool_vector_1d(A::BitArray, X::AbstractArray, I::AbstractArray{Bool})
if length(I) > length(A)
throw(BoundsError())
end
uA = unsafe(A)
c = 1
for i = 1:length(I)
if I[i]
uA[i] = X[c]
c += 1
end
end
A
end
new_setindex!(A::BitArray, X::AbstractArray, I::AbstractVector{Bool}) = new_setindex_bool_vector_1d(A, X, I)
function dotest_setindex3()
const I = randbool(1_000_000)
const b = randbool(1_000_000)
const X = randbool(nnz(I))
oldsetindex() = setindex!(b, X, I)
newsetindex() = new_setindex!(b, X, I)
@assert oldsetindex().chunks == newsetindex().chunks
println("b = randbool(1_000_000); I = randbool(1_000_000); X = randbool(nnz(I)); b[I] = X")
println(compare([oldsetindex, newsetindex], 10))
end
function dotest_setindex4()
const I = bitunpack(randbool(1_000_000))
const b = randbool(1_000_000)
const X = randbool(nnz(I))
oldsetindex() = setindex!(b, X, I)
newsetindex() = new_setindex!(b, X, I)
@assert oldsetindex().chunks == newsetindex().chunks
println("b = randbool(1_000_000); I = bitunpack(randbool(1_000_000)); X = randbool(nnz(I)); b[I] = X")
println(compare([oldsetindex, newsetindex], 10))
end
function dotest_setindex5()
const I = bitunpack(randbool(1_000_000))
const b = randbool(1_000_000)
const X = bitunpack(randbool(nnz(I)))
oldsetindex() = setindex!(b, X, I)
newsetindex() = new_setindex!(b, X, I)
@assert oldsetindex().chunks == newsetindex().chunks
println("b = randbool(1_000_000); I = bitunpack(randbool(1_000_000)); X = bitunpack(randbool(nnz(I))); b[I] = X")
println(compare([oldsetindex, newsetindex], 10))
end
function new_unary_minus(B::BitArray)
A = zeros(Int, size(B))
l = length(B)
if l == 0
return A
end
Bc = unsafechunks(B)
uA = unsafe(A)
ind = 1
for i = 1:length(Bc)-1
u = uint64(1)
c = Bc[i]
for j = 1:64
if c & u != 0
uA[ind] = -1
end
ind += 1
u <<= 1
end
end
u = uint64(1)
c = Bc[end]
for j = 0:@_mod64(l-1)
if c & u != 0
uA[ind] = -1
end
ind += 1
u <<= 1
end
return A
end
function dotest_unaryminus()
const b = randbool(1_000_000)
oldunaryminus() = -b
newunaryminus() = new_unary_minus(b)
@assert oldunaryminus() == newunaryminus()
println("b = randbool(1_000_000); -b")
println(compare([oldunaryminus, newunaryminus], 200))
end
function new_bitnot(B::BitArray)
C = similar(B)
if isempty(B)
return C
end
Bc = unsafechunks(B)
Cc = unsafechunks(C)
for i = 1:length(Bc)-1
Cc[i] = ~Bc[i]
end
msk = @_msk_end length(B)
Cc[end] = msk & ~Bc[end]
return C
end
function dotest_bitnot()
const b = randbool(1_000_017)
oldbitnot() = ~b
newbitnot() = new_bitnot(b)
@assert oldbitnot().chunks == newbitnot().chunks
println("b = randbool(1_000_017); ~b")
println(compare([oldbitnot, newbitnot], 10000))
end
function new_flipbits!(B::BitArray)
Bc = unsafechunks(B)
if !isempty(Bc)
for i = 1:length(Bc)-1
Bc[i] = ~Bc[i]
end
msk = @_msk_end length(B)
Bc[end] = msk & ~Bc[end]
end
return B
end
function dotest_flipbits()
const b = randbool(1_000_017)
const c = copy(b)
oldflipbits() = flipbits!(b)
newflipbits() = new_flipbits!(c)
@assert oldflipbits().chunks == newflipbits().chunks
println("b = randbool(1_000_017); flipbits!(b)")
println(compare([oldflipbits, newflipbits], 100000))
end
for (nf,fb,f) in ((:new_div,:unsafe_div,:div),
(:new_mod,:unsafe_mod,:mod))
@eval begin
function ($fb)(uF::UnsafeArray, uB::UnsafeBitArray, x::Number)
for i = 1:length(uF)
uF[i] = ($f)(uB[i], x)
end
end
function ($fb)(F::Array, uB::UnsafeBitArray, x::Number)
for i = 1:length(F)
F[i] = ($f)(uB[i], x)
end
end
function ($nf)(B::BitArray, x::Number)
T = promote_array_type(typeof(x), Bool)
F = Array(T, size(B))
uB = unsafe(B)
uF = isbits(T) ? unsafe(F) : F
($fb)(uF, uB, x)
return F
end
end
end
function dotest_divmod1()
const b = randbool(1_000_017)
const x = 2
olddivmod() = (div(b, x), mod(b, x))
newdivmod() = (new_div(b, x), new_mod(b, x))
@assert olddivmod() == newdivmod()
println("b = randbool(1_000_017); x = 2; (div(b,x),mod(b,x))")
println(compare([olddivmod, newdivmod], 20))
end
function dotest_divmod2()
const b = randbool(1_000_017)
const x = 2.0
olddivmod() = (div(b, x), mod(b, x))
newdivmod() = (new_div(b, x), new_mod(b, x))
@assert olddivmod() == newdivmod()
println("b = randbool(1_000_017); x = 2.0; (div(b,x),mod(b,x))")
println(compare([olddivmod, newdivmod], 40))
end
function dotest_divmod3()
const b = randbool(40_017)
const x = BigFloat(2.0)
olddivmod() = (div(b, x), mod(b, x))
newdivmod() = (new_div(b, x), new_mod(b, x))
@assert olddivmod() == newdivmod()
println("b = randbool(40_017); x = BigFloat(2.0); (div(b,x),mod(b,x))")
println(compare([olddivmod, newdivmod], 10))
end
for (nf,f) in ((:new_and,:&), (:new_or,:|), (:new_xor,:$))
@eval begin
function ($nf)(A::BitArray, B::BitArray)
F = BitArray(promote_shape(size(A),size(B))...)
Ac = unsafechunks(A)
Bc = unsafechunks(B)
if !isempty(Ac) && !isempty(Bc)
Fc = unsafechunks(F)
for i = 1:length(Fc) - 1
Fc[i] = ($f)(Ac[i], Bc[i])
end
msk = @_msk_end length(F)
Fc[end] = msk & ($f)(Ac[end], Bc[end])
end
return F
end
end
end
function dotest_andorxor()
const b1 = randbool(1_000_017)
const b2 = randbool(1_000_017)
oldandorxor() = (b1 & b2, b1 | b2, b1 $ b2)
newandorxor() = (new_and(b1,b2), new_or(b1,b2), new_xor(b1,b2))
@assert oldandorxor() == newandorxor()
println("b1 = randbool(1_000_017); b2 = randbool(1_000_017; (b1&b2, b1|b2, b1\$b2)")
println(compare([oldandorxor, newandorxor], 1000))
end
function new_pow(A::BitArray, B::BitArray)
F = BitArray(promote_shape(size(A),size(B))...)
Ac = unsafechunks(A)
Bc = unsafechunks(B)
if !isempty(Ac) && !isempty(Bc)
Fc = unsafechunks(F)
for i = 1:length(Fc) - 1
Fc[i] = Ac[i] | ~Bc[i]
end
msk = @_msk_end length(F)
Fc[end] = msk & (Ac[end] | ~Bc[end])
end
return F
end
function dotest_pow1()
const b1 = randbool(1_000_017)
const b2 = randbool(1_000_017)
oldpow() = b1 .^ b2
newpow() = new_pow(b1,b2)
@assert oldpow().chunks == newpow().chunks
println("b1 = randbool(1_000_017); b2 = randbool(1_000_017); b1 .^ b2")
println(compare([oldpow, newpow], 1000))
end
macro unsafe_pow(F, uB, u, z, uerr, zerr)
quote
for i = 1:length($(esc(uB)))
if $(esc(uB))[i]
if uerr == nothing
$(esc(F))[i] = $(esc(u))
else
throw(uerr)
end
else
if zerr == nothing
$(esc(F))[i] = $(esc(z))
else
throw(zerr)
end
end
end
end
end
unsafe_pow(uF::UnsafeArray, uB::UnsafeBitArray, u, z, uerr, zerr) = @unsafe_pow(uF, uB, u, z, uerr, zerr)
unsafe_pow(F::Array, uB::UnsafeBitArray, u, z, uerr, zerr) = @unsafe_pow(F, uB, u, z, uerr, zerr)
function new_pow{T<:Number}(B::BitArray, x::T)
if x == 0
return ones(typeof(true ^ x), size(B))
elseif T <: Real && x > 0
return convert(Array{T}, B)
else
z = nothing
u = nothing
zerr = nothing
uerr = nothing
try
z = false .^ x
catch err
zerr = err
end
try
u = true .^ x
catch err
uerr = err
end
if zerr == nothing && uerr == nothing
S = promote_type(typeof(z), typeof(u))
elseif zerr == nothing
S = typeof(z)
else
S = typeof(u)
end
F = Array(S, size(B))
uB = unsafe(B)
uF = isbits(F) ? unsafe(F) : F
unsafe_pow(uF, uB, u, z, uerr, zerr)
return F
end
end
function dotest_pow2()
const b = randbool(1_000_017)
const x = -2.0
oldpow() = b .^ x
newpow() = new_pow(b,x)
@assert oldpow() == newpow()
println("b = randbool(1_000_017); x = -2.0; b .^ x")
println(compare([oldpow, newpow], 10))
end
function dotest_pow3()
const b = randbool(1_000_017)
const x = BigFloat(-2)
oldpow() = b .^ x
newpow() = new_pow(b,x)
@assert oldpow() == newpow()
println("b = randbool(1_000_017); x = BigFloat(-2); b .^ x")
println(compare([oldpow, newpow], 10))
end
function dumpbitcache(Bc::UnsafeArray{Uint64}, C::UnsafeArray{Bool}, ind::Int, nc::Int)
cind = 1
for i = 1:nc
u = uint64(1)
c = uint64(0)
for j = 1:64
if C[cind]
c |= u
end
cind += 1
u <<= 1
end
Bc[ind] = c
ind += 1
end
return ind
end
# note: purposedly unhygenic macro: exp is an expression which
# depends on "ind" and yields a Bool
macro bitcache_body(exp, l, ind, C)
quote
left = $(esc(l)) - $(esc(ind)) + 1
for j = 1:min(bitcache_size, left)
$(esc(C))[j] = $exp
ind += 1
end
C[left+1:bitcache_size] = false
return ind
end
end
function bitcache_new_pow{T}(A::UnsafeBitArray, B::Array{T}, l::Int, ind::Int, C::UnsafeArray{Bool})
@bitcache_body(bool(A[ind] .^ B[ind]), l, ind, C)
end
function new_pow{T<:Integer}(A::BitArray, B::Array{T})
F = BitArray(promote_shape(size(A),size(B)))
l = length(F)
if l == 0
return F
end
C = Array(Bool, bitcache_size)
uC = unsafe(C)
uA = unsafe(A)
Fc = unsafechunks(F)
lFc = length(Fc)
indr = 1
indw = 1
for i = 1:div(l + bitcache_size - 1, bitcache_size)
indr = bitcache_new_pow(uA, B, l, indr, uC)
nc = min(bitcache_chunks, lFc - indw + 1)
indw = dumpbitcache(Fc, uC, indw, nc)
end
return F
end
function dotest_pow4()
const b = randbool(1_000_017)
const a = rand(0:5, 1_000_017)
oldpow() = b .^ a
newpow() = new_pow(b,a)
@assert oldpow() == newpow()
println("b = randbool(1_000_017); a = rand(0:5, 1_000_017); b .^ a")
println(compare([oldpow, newpow], 20))
end
for (cachef, scalarf) in ((:bitcache_new_eq , :(==)),
(:bitcache_new_lt , :< ),
(:bitcache_new_neq, :!= ),
(:bitcache_new_le , :<= ))
for (sigA, sigB, expA, expB) in ((:(AbstractArray{T}), :(AbstractArray{S}), :(A[ind]), :(B[ind])),
(:(AbstractArray{T}), :(UnsafeArray{S}), :(A[ind]), :(B[ind])),
(:(AbstractArray{T}), :S, :(A[ind]), :B),
(:(UnsafeArray{T}), :(AbstractArray{S}), :(A[ind]), :(B[ind])),
(:(UnsafeArray{T}), :(UnsafeArray{S}), :(A[ind]), :(B[ind])),
(:(UnsafeArray{T}), :S, :(A[ind]), :B),
(:T, :(AbstractArray{S}), :A, :(B[ind])),
(:T, :(UnsafeArray{S}), :A, :(B[ind])))
@eval function ($cachef){T,S}(A::$sigA, B::$sigB, l::Int, ind::Int, C::UnsafeArray{Bool})
@bitcache_body(($scalarf)($expA, $expB), l, ind, C)
end
end
end
for (f, cachef) in ((:new_eq, :bitcache_new_eq ),
(:new_lt, :bitcache_new_lt ),
(:new_neq, :bitcache_new_neq),
(:new_le, :bitcache_new_le ))
for (sigA, sigB, shape) in ((:(AbstractArray{T}), :(AbstractArray{S}), :(promote_shape(size(A), size(B)))),
(:T, :(AbstractArray{S}), :(size(B))),
(:(AbstractArray{T}), :S, :(size(A))))
@eval begin
function ($f){T,S}(A::$sigA, B::$sigB)
F = BitArray($shape)
l = length(F)
if l == 0
return F
end
C = Array(Bool, bitcache_size)
uC = unsafe(C)
Fc = unsafechunks(F)
lFc = length(Fc)
uA = isa(A, Array) && isbits(T) ? unsafe(A) : A
uB = isa(B, Array) && isbits(S) ? unsafe(B) : B
indr = 1
indw = 1
for i = 1:div(l + bitcache_size - 1, bitcache_size)
indr = ($cachef)(uA, uB, l, indr, uC)
nc = min(bitcache_chunks, lFc - indw + 1)
indw = dumpbitcache(Fc, uC, indw, nc)
end
return F
end
end
end
end
function dotest_lt1()
const a = rand(1_000_017)
const x = 0.5
oldlt() = a .< x
newlt() = new_lt(a, x)
@assert oldlt().chunks == newlt().chunks
println("a = rand(1_000_017); x = 0.5; a .< x")
println(compare([oldlt, newlt], 200))
end
function dotest_lt2()
const a = rand(1_000_017)
const b = rand(1_000_017)
oldlt() = a .< b
newlt() = new_lt(a, b)
@assert oldlt().chunks == newlt().chunks
println("a = rand(1_000_017); b = rand(1_000_017); a .< b")
println(compare([oldlt, newlt], 200))
end
function dotest_lt3()
const a = [BigInt(i) for i=rand(1:10,1_000_017)]
const b = [BigInt(i) for i=rand(1:10,1_000_017)]
oldlt() = a .< b
newlt() = new_lt(a, b)
@assert oldlt().chunks == newlt().chunks
println("a = [BigInt(i) for i=rand(1:10,1_000_017)]; b = [BigInt(i) for i=rand(1:10,1_000_017)]; a .< b")
println(compare([oldlt, newlt], 100))
end
function dotest_lt4()
const a = [BigInt(i) for i=rand(1:10,10_017)]
const b = rand(10_017)
oldlt() = a .< b
newlt() = new_lt(a, b)
@assert oldlt().chunks == newlt().chunks
println("a = [BigInt(i) for i=rand(1:10,10_017)]; b = rand(10_017); a .< b")
println(compare([oldlt, newlt], 100))
end
function dotest_lt5()
const a = [BigInt(i) for i=rand(1:10,10_017)]
const x = 0.5
oldlt() = a .< x
newlt() = new_lt(a, x)
@assert oldlt().chunks == newlt().chunks
println("a = [BigInt(i) for i=rand(1:10,1_000_017)]; x = 0.5; a .< x")
println(compare([oldlt, newlt], 100))
end
function new_findnext(B::BitArray, start::Integer)
Bc = unsafechunks(B)
if start <= 0
throw(BoundsError())
end
if start > length(B)
return 0
end
chunk_start = @_div64(start-1)+1
mask = _msk64 << @_mod64(start-1)
c = Bc[chunk_start]
if c & mask != 0
return (chunk_start-1) << 6 + trailing_zeros(c & mask) + 1
end
for i = chunk_start+1:length(Bc)
c = Bc[i]
if c != 0
return (i-1) << 6 + trailing_zeros(c) + 1
end
end
return 0
end
function dotest_findnext()
const b = [falses(100_000_000), randbool(17)]
oldfindnext() = (findnext(b, 1), findnext(b, 100_000_010))
newfindnext() = (new_findnext(b, 1), new_findnext(b, 100_000_010))
@assert oldfindnext() == newfindnext()
println("b = [falses(100_000_000), randbool(17)]; (findnext(b, 1), findnext(b, 100_000_010))")
println(compare([oldfindnext, newfindnext], 1000))
end
function new_findnextnot(B::BitArray, start::Integer)
Bc = unsafechunks(B)
l = length(Bc)
if start <= 0
throw(BoundsError())
end
if start > length(B)
return 0
end
chunk_start = @_div64(start-1)+1
mask = ~(_msk64 << @_mod64(start-1))
c = Bc[chunk_start] | mask
if c != _msk64
return (chunk_start-1) << 6 + trailing_ones(c) + 1
end
for i = chunk_start+1:l-1
c = Bc[i]
if c != _msk64
return (i-1) << 6 + trailing_ones(c) + 1
end
end
c = Bc[l]
if c != @_msk_end length(B)
return (l-1) << 6 + trailing_ones(c) + 1
end
return 0
end
function dotest_findnextnot()
const b = [trues(100_000_000), randbool(17)]
oldfindnextnot() = (findnextnot(b, 1), findnextnot(b, 100_000_010))
newfindnextnot() = (new_findnextnot(b, 1), new_findnextnot(b, 100_000_010))
@assert oldfindnextnot() == newfindnextnot()
println("b = [trues(100_000_000), randbool(17)]; (findnextnot(b, 1), findnextnot(b, 100_000_010))")
println(compare([oldfindnextnot, newfindnextnot], 1000))
end
function new_find(B::BitArray)
l = length(B)
nnzB = nnz(B)
I = Array(Int, nnzB)
if nnzB == 0
return I
end
uI = unsafe(I)
# note: using unsafechunks(B) degrades performance by ~10x
# here (for mysterious reasons)
#Bc = unsafechunks(B)
Bc = UnsafeArray(B.chunks)
Bcount = 1
Icount = 1
for i = 1:length(Bc)-1
u = uint64(1)
c = Bc[i]
for j = 1:64
if c & u != 0
uI[Icount] = Bcount
Icount += 1
end
Bcount += 1
u <<= 1
end
end
u = uint64(1)
c = Bc[end]
for j = 0:@_mod64(l-1)
if c & u != 0
uI[Icount] = Bcount
Icount += 1
end
Bcount += 1
u <<= 1
end
return I
end
function dotest_find()
const b = randbool(1_000_017)
oldfind() = find(b)
newfind() = new_find(b)
@assert oldfind() == newfind()
println("b = randbool(1_000_017)]; find(b)")
println(compare([oldfind, newfind], 100))
end
function new_all(B::BitArray)
if length(B) == 0
return true
end
# note: using unsafechunks or even
# unsafe_load(pBc, i) degrades
# performance a bit
Bc = B.chunks
pBc = pointer(Bc)
for i = 1:length(Bc)-1
if unsafe_load(pBc) != _msk64
return false
end
pBc += sizeof(Uint64)
end
if unsafe_load(pBc) != @_msk_end length(B)
return false
end
return true
end
function dotest_all()
const b = [trues(9_999_900), randbool(117)]
oldall() = all(b)
newall() = new_all(b)
@assert oldall() == newall()
println("b = [trues(9_999_900), randbool(117)]; all(b)")
println(compare([oldall, newall], 10000))
end
function new_any(B::BitArray)
if length(B) == 0
return false
end
Bc = unsafechunks(B)
for i = 1:length(Bc)
if Bc[i] != 0
return true
end
end
return false
end
function dotest_any()
const b = [falses(9_999_900), randbool(117)]
oldany() = any(b)
newany() = new_any(b)
@assert oldany() == newany()
println("b = [trues(9_999_900), randbool(117)]; any(b)")
println(compare([oldany, newany], 10000))
end
function dotest(;nobig=true)
dotest_fill()
dotest_copy()
dotest_convert1()
nobig || dotest_convert2()
dotest_convert3()
dotest_convert4()
dotest_randfill()
dotest_getindex1()
dotest_getindex2()
dotest_getindex3()
dotest_getindex4()
dotest_setindex1()
dotest_setindex2()
dotest_setindex3()
dotest_setindex4()
dotest_setindex5()
dotest_unaryminus()
dotest_bitnot()
dotest_flipbits()
dotest_divmod1()
dotest_divmod2()
nobig || dotest_divmod3()
dotest_andorxor()
dotest_pow1()
dotest_pow2()
nobig || dotest_pow3()
dotest_pow4()
dotest_lt1()
dotest_lt2()
nobig || dotest_lt3()
nobig || dotest_lt4()
nobig || dotest_lt5()
dotest_findnext()
dotest_findnextnot()
dotest_find()
dotest_all()
dotest_any()
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment