# Fastest way to negate some booleans in an array
**URL:** https://discourse.julialang.org/t/fastest-way-to-negate-some-booleans-in-an-array/89261
**Category:** Performance
**Tags:** boolean
**Created:** [October 25, 2022, 9:10pm UTC](https://discourse.julialang.org/t/fastest-way-to-negate-some-booleans-in-an-array/89261 "2022-10-25T21:10:00Z")
**Posts on this page:** 11
**Page:** 1
### Author:  [@HMegh](https://discourse.julialang.org/u/HMegh)
#### Post date: [October 25, 2022, 9:10pm UTC](https://discourse.julialang.org/t/fastest-way-to-negate-some-booleans-in-an-array/89261/1 "2022-10-25T21:10:00Z")
Hi, I am trying to optimize a code for a number theory side project. Currently, I have a large vector of booleans, say
```julia
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
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
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.
---
### Author:  [@Henrique\_Becker](https://discourse.julialang.org/u/Henrique_Becker)
#### Post date: [October 25, 2022, 9:21pm UTC](https://discourse.julialang.org/t/fastest-way-to-negate-some-booleans-in-an-array/89261/2 "2022-10-25T21:21:59Z")
If you have no problem in writing some extra lines:
```julia
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)
```
---
### Author:  [@mikmoore](https://discourse.julialang.org/u/mikmoore)
#### Post date: [October 25, 2022, 9:31pm UTC](https://discourse.julialang.org/t/fastest-way-to-negate-some-booleans-in-an-array/89261/3 "2022-10-25T21:31:00Z")
Don’t be afraid to write a loop! There’s nothing magic about `map` or other constructs.
```julia
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.,
```julia
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
```julia
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.
---
### Author:  [@aplavin](https://discourse.julialang.org/u/aplavin)
#### Post date: [October 25, 2022, 9:58pm UTC](https://discourse.julialang.org/t/fastest-way-to-negate-some-booleans-in-an-array/89261/4 "2022-10-25T21:58:49Z")
> [@HMegh](#):
>
> `map!(!,A[2:2:end],A[2:2:end])`
Just use views and this becomes much more efficient:
```julia
@views map!(!,A[2:2:end],A[2:2:end])
```
Or use broadcasting, even faster:
```julia
A[2:2:end] .= .!(@view A[2:2:end])
```
---
### Author:  [@DNF](https://discourse.julialang.org/u/DNF)
#### Post date: [October 25, 2022, 10:00pm UTC](https://discourse.julialang.org/t/fastest-way-to-negate-some-booleans-in-an-array/89261/5 "2022-10-25T22:00:33Z")
Loops are great. You could also do
```julia
@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…
---
### Author:  [@stillyslalom](https://discourse.julialang.org/u/stillyslalom)
#### Post date: [October 25, 2022, 10:06pm UTC](https://discourse.julialang.org/t/fastest-way-to-negate-some-booleans-in-an-array/89261/6 "2022-10-25T22:06:42Z")
If you’re willing to get your hands dirty with `BitVector` internals, you could do something like
```julia
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
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
```
---
### Author:  [@Dan](https://discourse.julialang.org/u/Dan)
#### Post date: [October 25, 2022, 10:36pm UTC](https://discourse.julialang.org/t/fastest-way-to-negate-some-booleans-in-an-array/89261/7 "2022-10-25T22:36:21Z")
Another option I think is attractive (generalizes well for other `p`):
```julia
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:
```julia
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.
---
### Author:  [@jling](https://discourse.julialang.org/u/jling)
#### Post date: [October 25, 2022, 11:59pm UTC](https://discourse.julialang.org/t/fastest-way-to-negate-some-booleans-in-an-array/89261/8 "2022-10-25T23:59:02Z")
are you all missing something?
```julia
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)
```
---
### Author:  [@Dan](https://discourse.julialang.org/u/Dan)
#### Post date: [October 26, 2022, 12:10am UTC](https://discourse.julialang.org/t/fastest-way-to-negate-some-booleans-in-an-array/89261/9 "2022-10-26T00:10:02Z")
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
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 😉
---
### Author:  [@jling](https://discourse.julialang.org/u/jling)
#### Post date: [October 26, 2022, 12:11am UTC](https://discourse.julialang.org/t/fastest-way-to-negate-some-booleans-in-an-array/89261/10 "2022-10-26T00:11:02Z")
mapped array is fast in creation (O(1)) but subsequent access is much slower
---
### Author:  [@Dan](https://discourse.julialang.org/u/Dan)
#### Post date: [October 26, 2022, 12:28am UTC](https://discourse.julialang.org/t/fastest-way-to-negate-some-booleans-in-an-array/89261/11 "2022-10-26T00:28:31Z")
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
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.