BitArray is much slower than Array{Bool}

[cstjean]

Old issue: #2360

On Julia 0.4, OSX:

function true_arr()
    out = Array{Bool, 2}(300,200)
    for i in eachindex(out) out[i] = true end
end
function true_bitarr()
    out = BitArray{2}(300, 200)
    for i in eachindex(out) out[i] = true end
end

function foo(n)
    for _ in 1:n true_arr() end
end

function foo2(n)
    for _ in 1:n true_bitarr() end
end

@time(foo(10000))
> 0.387643 seconds (23.33 k allocations: 573.136 MB, 15.92% gc time)

@time(foo2(10000))
> 2.764923 seconds (33.85 k allocations: 73.283 MB, 0.35% gc time)

I ran into this because my code has a line:

# Comparing an image with a color returns a BitArray
img .!= green

and this calls bitneq_cache. Writing the loop explicitly yields comparable performance if I use BitArray{2}, but it's 5X faster if I use Array{Bool, 2}. That's probably because with BitArray, the set_index! call does not get inlined.

[carlobaldassi]

It's true that a lot of the performance penalty comes from not inlining set_index! (#13946).
Apart from that, cycling explicitly through a BitArray and calling set_index! will often be slower than using an Array{Bool}. However, there are usually faster ways than cycling explicitly, depending on the case. For example, you'd use fill! to fill the array with trues. Or, you'd use copy! to fill and array with a copy from another one. Or you could use map! to fill a BitArray with the result of a binary operation. All these operations provide major speedups. Do you have a code sample?

[cstjean]

UPDATE It seems that I can't tell the difference between milli- and micro-seconds. Equality is clearly faster than the map! versions. Sorry for the noise.

---

Hi Carlo, thank you for looking into this. map! turned into a pretty big speed-up, making BitArray comparable to Array{Bool} (slightly faster in fact). But I found that for an array of float, arr .== 0.1 is 5X slower than the map! version

function test_bitarr(val, arr)
    out = BitArray{2}(size(arr)...)
    f = @anon (x)->x==val
    map!(f, out, arr)
    out
end
function test_bool(val, arr)
    out = Array{Bool, 2}(size(arr)...)
    f = @anon (x)->x==val
    map!(f, out, arr)
    out
end
function test_eql(val, arr)
    arr .== val
end

float_arr = rand((200,200));
@benchmark test_eql(0.1, float_arr)
     Time per evaluation: 74.32 μs [72.35 μs, 76.28 μs]
@benchmark test_bitarr(0.1, float_arr)
     Time per evaluation: 13.60 ms [7.86 ms, 19.33 ms]
@benchmark test_bool(0.1, float_arr)
     Time per evaluation: 18.32 ms [13.71 ms, 22.93 ms]

[carlobaldassi]

@cstjean I don't understand your last comments, I suspect you're being misled by the time units (μs vs ms). Is that so?
Also, I apologize, I have now realized that the problem was the .!= operation itself, which I had thought was already optimized. The good news is it could in fact be optimized further, see #13946. That should basically close this issue.

[cstjean]

@carlobaldassi You're right, I was misled by the time units, please ignore that post. Sorry for the confusion, I will be more careful in my benchmarks. Thank you for #13946, that should fix the issue!