# Optimization: How to make sure XOR is performed in chunks

**URL:** <https://discourse.julialang.org/t/optimization-how-to-make-sure-xor-is-performed-in-chunks/33947>\
**Category:** New to Julia\
**Created:** [January 29, 2020, 8:19pm UTC](https://discourse.julialang.org/t/optimization-how-to-make-sure-xor-is-performed-in-chunks/33947 "2020-01-29T20:19:17Z")\
**Posts on this page:** 14\
**Page:** 2

<div class="post-metadata">

**Author:** ![kristoffer.carlsson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kristoffer.carlsson/32/22_2.png) [@kristoffer.carlsson](https://discourse.julialang.org/u/kristoffer.carlsson)\
**Post date:** [January 30, 2020, 6:48pm UTC](https://discourse.julialang.org/t/optimization-how-to-make-sure-xor-is-performed-in-chunks/33947/22 "2020-01-30T18:48:49Z")

</div>

> [@jebej](#):
>
> it didn’t help, in fact, it

Maybe differs on the CPU if the AVX is worth it. Was quite a lot faster for me.

---

<div class="post-metadata">

**Author:** ![lesshaste](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lesshaste/32/12302_2.png) [@lesshaste](https://discourse.julialang.org/u/lesshaste)\
**Post date:** [January 30, 2020, 6:49pm UTC](https://discourse.julialang.org/t/optimization-how-to-make-sure-xor-is-performed-in-chunks/33947/23 "2020-01-30T18:49:18Z")

</div>

Yes you would need to iterate if you have more than 128 bits. Luckily there is also UIint128 for n \< 129.

---

<div class="post-metadata">

**Author:** ![non-Jedi](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/non-jedi/32/3645_2.png) [@non-Jedi](https://discourse.julialang.org/u/non-Jedi)\
**Post date:** [January 30, 2020, 8:29pm UTC](https://discourse.julialang.org/t/optimization-how-to-make-sure-xor-is-performed-in-chunks/33947/24 "2020-01-30T20:29:57Z")

</div>

> [@DNF](#):
>
> I don’t understand why bitvectors don’t do the same thing. They too are just wrapped arrays of `UInt64` . Iteration is needed if you have an array of `UInt64` s, surely.

It is (basically) the same as long as you use broadcast `=` as well. But doing a single `xor` on a pair of `UInt64` is faster still (I’m assuming something to do with arrays being allocated on the heap instead of the stack?). Some timings:

```julia
julia> x = bitrand(64);

julia> y = bitrand(64);

julia> z = similar(x);

julia> @btime $z .= $x .⊻ $y;
  9.309 ns (0 allocations: 0 bytes)

julia> x = rand(UInt64, 1);

julia> y = rand(UInt64, 1);

julia> z = similar(x);

julia> @btime $z .= $x .⊻ $y;
  9.021 ns (0 allocations: 0 bytes)

julia> x = rand(UInt64);

julia> y = rand(UInt64);

julia> @btime $x ⊻ $y;
  0.019 ns (0 allocations: 0 bytes)

julia> x = rand(UInt128);

julia> y = rand(UInt128);

julia> @btime $x ⊻ $y
  0.019 ns (0 allocations: 0 bytes)

```

EDIT: for the record, `@inbounds` made the timings worse for the `BitVector` and `Vector{UInt64}` cases on my computer as well.

EDIT2: The real question I have is why using `broadcast!(xor, z, x, y)` is slower than `z .= xor.(x, y)`:

```julia
julia> x = bitrand(64);

julia> y = bitrand(64);

julia> z = similar(x);

julia> @btime broadcast!(⊻, $z, $x, $y);
  18.687 ns (0 allocations: 0 bytes)

julia> x = rand(UInt64, 1);

julia> y = rand(UInt64, 1);

julia> z = similar(x);

julia> @btime broadcast!($⊻, $z, $x, $y);
  16.280 ns (0 allocations: 0 bytes)

```

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [January 30, 2020, 8:58pm UTC](https://discourse.julialang.org/t/optimization-how-to-make-sure-xor-is-performed-in-chunks/33947/25 "2020-01-30T20:58:14Z")

</div>

> [@non-Jedi](#):
>
> But doing a single `xor` on a pair of `UInt64` is faster still

Okay, but generally you have more, or rather, an unknown number of samples, I would think.

As for the sub-nanosecond timings, those are not real, when that happens, it’s the compiler eliding the entire computation.

---

<div class="post-metadata">

**Author:** ![non-Jedi](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/non-jedi/32/3645_2.png) [@non-Jedi](https://discourse.julialang.org/u/non-Jedi)\
**Post date:** [January 30, 2020, 9:43pm UTC](https://discourse.julialang.org/t/optimization-how-to-make-sure-xor-is-performed-in-chunks/33947/26 "2020-01-30T21:43:39Z")

</div>

> [@DNF](#):
>
> As for the sub-nanosecond timings, those are not real, when that happens, it’s the compiler eliding the entire computation.

Right of course:

```julia
julia> x = Ref(rand(UInt64));

julia> y = Ref(rand(UInt64));

julia> @btime $x[] ⊻ $y[];
  1.750 ns (0 allocations: 0 bytes)

julia> x = Ref(rand(UInt128));

julia> y = Ref(rand(UInt128));

julia> @btime x[] ⊻ $y[];
  31.367 ns (2 allocations: 64 bytes)

```

@lesshaste the important bit here for you is that using `UInt128` is slower than `BitVector`.

---

<div class="post-metadata">

**Author:** ![jebej](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jebej/32/1784_2.png) [@jebej](https://discourse.julialang.org/u/jebej)\
**Post date:** [January 30, 2020, 10:11pm UTC](https://discourse.julialang.org/t/optimization-how-to-make-sure-xor-is-performed-in-chunks/33947/27 "2020-01-30T22:11:19Z")

</div>

An other trick to see the real timings is to use the `setup` feature of BenchmarkTools:

```julia
julia> @benchmark a ⊻ b setup=((a,b)=rand(UInt,2))
BenchmarkTools.Trial:
  memory estimate: 0 bytes
  allocs estimate: 0
  --------------
  minimum time: 1.699 ns (0.00% GC)
  median time: 1.800 ns (0.00% GC)
  mean time: 1.769 ns (0.00% GC)
  maximum time: 11.200 ns (0.00% GC)
  --------------
  samples: 10000
  evals/sample: 1000

```

---

<div class="post-metadata">

**Author:** ![StefanKarpinski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stefankarpinski/32/24_2.png) [@StefanKarpinski](https://discourse.julialang.org/u/StefanKarpinski)\
**Post date:** [January 30, 2020, 10:34pm UTC](https://discourse.julialang.org/t/optimization-how-to-make-sure-xor-is-performed-in-chunks/33947/28 "2020-01-30T22:34:12Z")

</div>

If you don’t plan on having more than 64 bits, then it’s certainly faster to work with UInt64 values directly. You can easily make a BitVector64 type that acts like a 64-element boolean vector but is represented as a single UInt64 value. It may or may not be worth it to have something that behaves in a vectorlike fashion. BitVectors have more overhead since they are arbitrary length.

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [January 31, 2020, 8:45am UTC](https://discourse.julialang.org/t/optimization-how-to-make-sure-xor-is-performed-in-chunks/33947/29 "2020-01-31T08:45:42Z")

</div>

> [@non-Jedi](#):
>
> ```julia
> julia> @btime x[] ⊻ $y[];
> 31.367 ns (2 allocations: 64 bytes)
> 
> ```
> 
> @lesshaste the important bit here for you is that using `UInt128` is slower than `BitVector` .

You forgot a crucial part:

```julia
julia> @btime x[] ⊻ $y[];
  55.262 ns (3 allocations: 96 bytes)

julia> @btime $x[] ⊻ $y[];
  1.792 ns (0 allocations: 0 bytes)

```

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [January 31, 2020, 9:48am UTC](https://discourse.julialang.org/t/optimization-how-to-make-sure-xor-is-performed-in-chunks/33947/30 "2020-01-31T09:48:00Z")

</div>

> [@StefanKarpinski](#):
>
> You can easily make a BitVector64 type that acts like a 64-element boolean vector but is represented as a single UInt64 value.

Perhaps a `StaticBitVector` type that contains a tuple of `Int64` would be the best of both worlds. If someone has the time and is working on this anyway, implementing

> <https://github.com/JuliaArrays/StaticArrays.jl/issues/412>
>
> Since this hasn't really been brought up before, I would like to suggest the pos…sibility of Static BitArrays. In particular, since the performance of static arrays relative to regular arrays are so closely tied to their size, the space optimization afforded by BitArrays may allow much larger arrays to reap performance gains. 
> 
> For example, a bitboard for Chess would require only 64 bits, so it could fit in a single register, discounting overhead.

would be a great addition.

---

<div class="post-metadata">

**Author:** ![rfourquet](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rfourquet/32/3610_2.png) [@rfourquet](https://discourse.julialang.org/u/rfourquet)\
**Post date:** [January 31, 2020, 10:07am UTC](https://discourse.julialang.org/t/optimization-how-to-make-sure-xor-is-performed-in-chunks/33947/31 "2020-01-31T10:07:38Z")

</div>

> [@Tamas\_Papp](#):
>
> Perhaps a `StaticBitVector` type that contains a tuple of `Int64` would be the best of both worlds.

An alternative implementation idea is to use the `Bits` package, which arleady has a `BitVector1` type, which wraps a single integer and is supposed to have a similar interface to `BitVector`. It’s on my radar to develop this type a bit and make it more useful. Then this can be used with integer types of any bit-size to emulate a kind of “static bit-vector”.

---

<div class="post-metadata">

**Author:** ![lungben](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lungben/32/12314_2.png) [@lungben](https://discourse.julialang.org/u/lungben)\
**Post date:** [November 30, 2020, 5:10pm UTC](https://discourse.julialang.org/t/optimization-how-to-make-sure-xor-is-performed-in-chunks/33947/32 "2020-11-30T17:10:05Z")

</div>

A bit late to the party, but I just had a similar use case today.  
The fastest method I could find was working on UInt8 instead of BitArrays, `count_ones` and LoopVectorization:

```julia
function hamming_distance(h1, h2)
    s = 0
    @avx for i = 1:length(h1)
        s += count_ones(xor(h1[i], h2[i]))
    end
    s
end

h1 = Vector{UInt8}(randstring(hash_length))
h2 = Vector{UInt8}(randstring(hash_length))

julia> @btime hamming_distance($h1, $h2)
  11.813 ns (0 allocations: 0 bytes)

```

The method above (based on the same BitVectors) is slower for me:

```julia
function make_bitvector(v::Vector{UInt8})
           siz = sizeof(v)
           bv = falses(siz<<3)
           unsafe_copyto!(reinterpret(Ptr{UInt8}, pointer(bv.chunks)), pointer(v), siz)
           bv
end

h1b = make_bitvector(h1)
h2b = make_bitvector(h2)
buf = similar(h1b)

julia> @btime hamming($h1b, $h2b, $buf)
  16.933 ns (0 allocations: 0 bytes)

```

Is bitwise Hamming Distance on GPU an option to get even more speed? With my very limited GPU knowledge I could not find a way to make it faster (or even the same speed) as on CPU.

Edit: btw. I was able to beat the performance of a ~150 LOC Cython implementation with less than 30 lines of Julia code 😉

---

<div class="post-metadata">

**Author:** ![JeffreySarnoff](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jeffreysarnoff/32/1980_2.png) [@JeffreySarnoff](https://discourse.julialang.org/u/JeffreySarnoff)\
**Post date:** [December 2, 2020, 4:44pm UTC](https://discourse.julialang.org/t/optimization-how-to-make-sure-xor-is-performed-in-chunks/33947/33 "2020-12-02T16:44:48Z")

</div>

Your approach looks good to me.

---

<div class="post-metadata">

**Author:** ![Lilith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lilith/32/27492_2.png) [@Lilith](https://discourse.julialang.org/u/Lilith)\
**Post date:** [July 6, 2022, 6:41pm UTC](https://discourse.julialang.org/t/optimization-how-to-make-sure-xor-is-performed-in-chunks/33947/34 "2022-07-06T18:41:08Z")

</div>

Quite late to the party, but I find that @lungben’s approach is 2x faster with

```julia
h1_64 = reinterpret(Int, h1)
h2_64 = reinterpret(Int, h2)
@btime hamming_distance($h1_64, $h2_64)

```

For a total of 20x speedup in the OP by replacing the @lesshaste’s `hamming` function with

```julia
using LoopVectorization
function hamming(bits1, bits2)
    h1, h2 = bits1.chunks, bits2.chunks
    s = 0
    @avx for i = eachindex(h1, h2)
        s += count_ones(xor(h1[i], h2[i]))
    end
    s
end

```

---

<div class="post-metadata">

**Author:** ![JeffreySarnoff](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jeffreysarnoff/32/1980_2.png) [@JeffreySarnoff](https://discourse.julialang.org/u/JeffreySarnoff)\
**Post date:** [July 6, 2022, 7:18pm UTC](https://discourse.julialang.org/t/optimization-how-to-make-sure-xor-is-performed-in-chunks/33947/35 "2022-07-06T19:18:06Z")

</div>

I get crossover with bits1, bits2 each ~1792 bits (64 \* (1024+512+256))  
when using @tturbo performs better than @turbo (@avx).  
This is likely a cache line effect: div(2\*1792, 512) == 7

[Previous page](https://discourse.julialang.org/t/optimization-how-to-make-sure-xor-is-performed-in-chunks/33947.md?page=1)