JuliaLang/julia — pull request #6035 by carlobaldassi (2014-03-03 15:46:43+00:00)
Title: BitArray broadcasting

This fixes #5877 and touches related issues, in that it makes element-wise comparisons (`.==`, `.<`, etc.) broadcasting, and also completes broadcasting behaviour for all element-wise operations which involve BitArrays (`.*`, `./`, etc.), unless I missed something.

Besides that, there is some minor stuff in here, the most relevant being that it fixes `.+` and `.-` for Bools, which now return `Array{Int}`. There's also a specialization for `Bool^Int`.

This is a pull request even though to me it's ready for merging, mainly to highlight some issues I found. Here's a list of reasons why I didn't merge it directly:

1. Since broadcast is @toivoh's (and others) creature, review is in order
2. The code adds a specialization for `broadcast!(f::Function, B::BitArray, ...)`, but adds another function `bitbroadcast`, which is not exported: should it be exported?
3. Performance is good, unless broadcasting is actually needed (i.e. `broadcast_shape` yields something different from `promote_shape`) _and_ BitArrays are involved in the argument list.

3a. In the case `promote_shape` succeeds, I added fallbacks which make things efficient. One possibly questionable issue is my use of `try` blocks for that purpose.

3b. In case it fails, and BitArrays are involved (e.g. `trues(5) .+ falses(1,5)`), cartesian iteration kills performance, to the point that it is much faster to invoke `bitunpack` on the arguments first; however, that may clearly become very memory-expensive. I haven't been able to overcome this issue yet, so advice would be welcome on this. (One might imagine unpacking below a certain size, but that is not a very satisfactory solution.)

Example of timings for the last issue: here's a specialized version which doesn't truly broadcast:

```
julia> n1=110; n2=323; n3=681; a = randbool(n1,n2,n3); b = randbool(n1,n2,n3);

julia> @time a .* b; # not really broadcasting
elapsed time: 0.004324182 seconds (3024816 bytes allocated)
```

And here's one where it does:

```
julia> n1=110; n2=323; n3=681; a = randbool(n1,1,n3); b = randbool(1,n2,1);

julia> @time a .* b; # broadcasting
elapsed time: 1.087884438 seconds (3029848 bytes allocated)

julia> @time bitunpack(a) .* bitunpack(b); # broadcasting
elapsed time: 0.124664672 seconds (24273712 bytes allocated)
```

Similar timings are obtained for comparison operations like `.==`.

Part of the problem is that `@inbounds` is ineffective for BitArrays, but I don't think it's only that (even if it would be nice to have some way of making it work, cc @JeffBezanson ). Probably, with a sufficient effort, one could come up with some (contrived) way out from this by avoiding multidimensional indexing for BitArrays, but even in that case it is hard to think of a solution for general AbstractArrays (e.g. comparing a `BitArray` with an `Array`).