How can I bitwise or truncate along the axis of a boolean array in Julia?

There are various standard optimization tricks and hints that can be applied, but the critical point to make here is that Julia organizes the array in a column-to-column rather than a row-large order. For small-sized arrays, it is not easy to see, but as the arrays grow, it says. There is a method to reduce , provided it is optimized to execute a function on the collection (in this case, OR ), but this comes with a cost. If the number of step combinations is relatively small, it is best to simply loop. In all cases, minimizing the amount of memory access is better. Below are various optimization attempts with these two things in mind.

Various attempts and observations

Initial function

Here's a function that takes your example and summarizes it.

function boolReduce1(x)
   out = copy(x[:,:,1])
   for i = 1:size(x,1)
       for j = 1:size(x,2)
           for k = 2:size(x,3)
               out[i,j] |= x[i,j,k]
           end
       end
   end
   out
end

      

        
        
        
      

    

By creating a fairly large array, we can execute it for a while

julia> @time boolReduce1(b); 
elapsed time: 42.372058096 seconds (1056704 bytes allocated)

      

        
        
        
      

    

Applying optimizations

Here's another similar version, but with standard types, uses @inbounds and inverts loops.

function boolReduce2(b::BitArray{3})
   a = BitArray{2}(size(b)[1:2]...)
   for j = 1:size(b,2)
      for i = 1:size(b,1)
         @inbounds a[i,j] = b[i,j,1]
         for k = 2:size(b,3)
            @inbounds a[i,j] |= b[i,j,k]
         end
      end
   end
   a
end

      

        
        
        
      

    

And take the time

julia> @time boolReduce2(b);
elapsed time: 12.892392891 seconds (500520 bytes allocated)

      

        
        
        
      

    

Insight

The second function is much faster and also less memory allocated because the temporary array was not created. But what if we just take the first function and invert the array indexing?

function boolReduce3(x)
   out = copy(x[:,:,1])
   for j = 1:size(x,2)
       for i = 1:size(x,1)
           for k = 2:size(x,3)
               out[i,j] |= x[i,j,k]
           end
       end
   end
   out
end

      

        
        
        
      

    

and take the time

julia> @time boolReduce3(b);
elapsed time: 12.451501749 seconds (1056704 bytes allocated)

      

        
        
        
      

    

It is as fast as the second function.

Using abbreviation

There is a reduce function that we can use to eliminate the 3rd cycle. Its function is to reapply an operation to all elements with the result of the previous operation. This is exactly what we want.

function boolReduce4(b)
   a = BitArray{2}(size(b)[1:2]...)
   for j = 1:size(b,2)
      for i = 1:size(b,1)
         @inbounds a[i,j] = reduce(|,b[i,j,:])
     end
   end
   a
end

      

        
        
        
      

    

Now take your time

julia> @time boolReduce4(b);
elapsed time: 15.828273008 seconds (1503092520 bytes allocated, 4.07% gc time)

      

        
        
        
      

    

This is fine, but not as fast as the simple optimized original. The reason is to look at all the extra memory that has been allocated. This is because data has to be copied from all over in order to create input data to shrink.

Combining things

But what if we are as exhaustive as possible. Instead of decreasing the last index, the first one is?

function boolReduceX(b)
   a = BitArray{2}(size(b)[2:3]...)
   for j = 1:size(b,3)
      for i = 1:size(b,2)
         @inbounds a[i,j] = reduce(|,b[:,i,j])
      end
   end
   a
end

      

        
        
        
      

    

And now create a similar array and time it.

julia> c = randbool(200,2000,2000);

julia> @time boolReduceX(c);
elapsed time: 1.877547669 seconds (927092520 bytes allocated, 21.66% gc time)

      

        
        
        
      

    

The result is 20 times faster than the original version for large arrays. Pretty good.

But what if the average size?

If the size is very large then the above function looks best, but if the size of the dataset is smaller the use of the reduction is not paid back enough and the next is faster. Including a temporary variable makes things faster since version 2. Another version of boolReduceX, using a loop instead of a shortcut (not shown here), was even faster.

function boolReduce5(b)
   a = BitArray{2}(size(b)[1:2]...)
   for j = 1:size(b,2)
      for i = 1:size(b,1)
         @inbounds t = b[i,j,1]
         for k = 2:size(b,3)
            @inbounds t |= b[i,j,k]
         end
         @inbounds a[i,j] = t
      end
   end
   a
end

julia> b = randbool(2000,2000,20);
julia> c = randbool(20,2000,2000);

julia> @time  boolReduceX(c);
elapsed time: 1.535334322 seconds (799092520 bytes allocated, 23.79% gc time)

julia> @time  boolReduce5(b);
elapsed time: 0.491410981 seconds (500520 bytes allocated)