Fastest way to negate some booleans in an array

General Usage Performance
1

Hi, I am trying to optimize a code for a number theory side project. Currently, I have a large vector of booleans, say

A=rand(Bool,10^8)

I want to negate all the even-index terms. One possible way that I have found is using map, here’s what btime returns

julia> @btime A[2:2:end]=map(!,A[2:2:end]);
  103.509 ms (9 allocations: 95.37 MiB)

I am wondering if there is anything that could be done to speed up this process more. I have tried the following as well

julia> @btime map!(!,A[2:2:end],A[2:2:end]);
  129.196 ms (8 allocations: 95.37 MiB)

which runs slightly slower than the first one.

Problem background: I am working on a fast method to calculate some multiplicative functions and one operation that I use all the time is A[p:p:end]= map(!,A[p:p:end]), this seems to be my most expensive operation.

2

If you have no problem in writing some extra lines:

julia> function negateAllEvenIndexes(A)
           for i in 2:2:length(A)
               A[i] = !A[i]
           end
           A
       end
julia> @btime negateAllEvenIndexes($A)
  31.877 ms (0 allocations: 0 bytes)
1 Like
3

Don’t be afraid to write a loop! There’s nothing magic about map or other constructs.

function negateeven1!(A)
    for i in firstindex(A)+isodd(firstindex(A)) : 2 : lastindex(A) # even-valued indices
        @inbounds A[i] = !A[i] # faster with @inbounds, but don't mess up the indexing!
    end
    return A
end

Your map! version will not update A because of array slicing. You need to use views, e.g.,

function negateeven2!(A)
    inds = firstindex(A)+isodd(firstindex(A)) : 2 : lastindex(A) # even-valued indices
    @views map!(!,A[inds],A[inds])
    return A
end

although I think the loop is more clear.

But the best I could do is

function negateeven3!(A)
    for i in eachindex(A)
        A[i] = xor(A[i],iseven(i))
    end
    return A
end

Having not looked, this probably uses vectorized instructions and that’s where the extra speed comes from.

1 Like
4

Just use views and this becomes much more efficient:

@views map!(!,A[2:2:end],A[2:2:end])

Or use broadcasting, even faster:

A[2:2:end] .= .!(@view A[2:2:end])
3 Likes
5

Loops are great. You could also do

@views A[2:2:end] .= .!A[2:2:end]

Or 0:2:end if you’re into zero-based things…

Edit: typing too slow on phone…

6

If you’re willing to get your hands dirty with BitVector internals, you could do something like

julia> function neg_bitvector_evens(v)
           evens = 0xaaaaaaaaaaaaaaaa
           for i in eachindex(v.chunks)
               v.chunks[i] = xor(v.chunks[i], evens)
           end
           v
       end

julia> @btime neg_bv_evens(v) setup=(v = falses(10^8))
  277.700 μs (3 allocations: 4.28 KiB)
100000000-element BitVector:
 0
 1
 0
 1
 ⋮
 0
 1
4 Likes
7

Another option I think is attractive (generalizes well for other p):

julia> @btime foreach(2:2:length($A)) do i
       $A[i] = !$A[i]
       end
  21.342 ms (0 allocations: 0 bytes)

Remember to add $ to variables when doing @btime. Also, the last option suggested in original post doesn’t actually flip the bits because slicing without views creates a new vector:

map!(!,A[2:2:end],A[2:2:end]);

Also note, above method (and others) work with BitVectors as well. Because memory access is probably the constraining factor on the speed of operation, and the recent word of bits already in cache, the extra indexing operation for each negation will not cost much (for p=2 the low-level bit method is still much faster). If p is larger than word size then BitVector vs. Bool vector makes less difference.

8

are you all missing something?

julia> @btime foreach(2:2:length(A)) do i
              A[i] = !A[i]
              end setup=(A=rand(Bool,10^8))
  29.752 ms (0 allocations: 0 bytes)

julia> @btime let
              @view(A[2:2:end]) .⊻= true
              end setup=(A=rand(Bool,10^8));
  23.367 ms (0 allocations: 0 bytes)
9

You are right. I’ve used xor when testing as well.
In any case, taking optimization to extreme, and in a slightly humoristic suggestion:

julia> using MappedArrays

julia> @btime mappedarray((i,val)->ifelse(iseven(i),val,!val),1:10^8,$v) setup=(v=fill(true,10^8))
  4.009 ns (0 allocations: 0 bytes)
100000000-element mappedarray(var"#17#18"(), ::UnitRange{Int64}, ::BitVector) with eltype Bool:
 1
 0
 1
 0

also works :wink:

10

mapped array is fast in creation (O(1)) but subsequent access is much slower

11

Yep, access is slow. But we don’t know the usage pattern OP intends. It seems the goal is to flip prime sequences of entries.
Perhaps, the following ‘hybrid’ method will be optimized (and also sparkingly demonstrates Julia composability):

julia> using CircularArrays
julia> using MappedArrays
julia> using Primes

julia> P = primes(10);
julia> Pprod = prod(P)
210

julia> m = CircularArray(falses(Pprod))
210-element CircularVector(::BitVector):
 0
 0
 0

julia> v = falses(10^8);

julia> V = mappedarray((v1, v2)->v1⊻v2, view(m, 1:length(v)), v);

julia> V[1:10]
10-element Vector{Bool}:
 0
 0
 0
 0
 0
 0
 0
 0
 0
 0

julia> m[2:2:Pprod] .⊻= true;

julia> V[1:10]
10-element Vector{Bool}:
 0
 1
 0
 1
 0
 1
 0
 1
 0
 1

So essentially, for low primes, flipping the auxiliary vector m will flip all the virtual big vector V, and for higher primes, the big vector v should be flipped. Access time is longer but constant.