# \`issubset(::BitSet,::BitSet)\` is slow and allocates unnecessarily

**URL:** <https://discourse.julialang.org/t/issubset-bitset-bitset-is-slow-and-allocates-unnecessarily/43828>\
**Category:** Performance\
**Created:** [July 28, 2020, 6:23pm UTC](https://discourse.julialang.org/t/issubset-bitset-bitset-is-slow-and-allocates-unnecessarily/43828 "2020-07-28T18:23:41Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![guyvdb](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/guyvdb/32/11596_2.png) [@guyvdb](https://discourse.julialang.org/u/guyvdb)\
**Post date:** [July 28, 2020, 6:23pm UTC](https://discourse.julialang.org/t/issubset-bitset-bitset-is-slow-and-allocates-unnecessarily/43828/1 "2020-07-28T18:23:41Z")

</div>

The implementation of `issubset` between two `BitSet`: [https://github.com/JuliaLang/julia/blob/3909294e78d223c740b7e7a4d00eb2d4771055a7/base/bitset.jl#L419](https://github.com/JuliaLang/julia/blob/3909294e78d223c740b7e7a4d00eb2d4771055a7/base/bitset.jl#L419)  
first intersects the sets. This unnecessarily allocates memory to compute an entirely new `BitSet` for the intersection. It ended up costing me 30% CPU time on my workload.

It seems that on ‘standard’ sizes of `BitSet`, the following implementation is often 6x faster and has 0 allocations.

```julia
function issubset_fast(s::BitSet,t::BitSet)
    s == t && return true
    s.offset < t.offset && return false
    length(s.bits) > length(t.bits) && return false
    length(s) > length(t) && return false
    return all(e -> e ∈ t, s)
end

s1 = BitSet([2i for i=1:100]);
s2 = BitSet([7i+70 for i=1:15]);
s3 = BitSet([20i+70 for i=1:6]);
s4 = BitSet([2i for i=1:99]);

@btime issubset($s1, $s1);
@btime issubset_fast($s1, $s1); 
@btime issubset($s2, $s1);
@btime issubset_fast($s2, $s1); 
@btime issubset($s3, $s1);
@btime issubset_fast($s3, $s1); 
@btime issubset($s4, $s1);
@btime issubset_fast($s4, $s1); 

```

Giving:

```julia
  85.817 ns (3 allocations: 160 bytes)
  8.865 ns (0 allocations: 0 bytes)
  86.080 ns (3 allocations: 160 bytes)
  14.888 ns (0 allocations: 0 bytes)
  86.146 ns (3 allocations: 160 bytes)
  19.714 ns (0 allocations: 0 bytes)
  88.973 ns (3 allocations: 160 bytes) 
  142.452 ns (0 allocations: 0 bytes)

```

On the last `issubset(s4, s1)` the implementation in `Base` is still faster, I suppose it has been optimized for this case.

Still, I’m hoping that someone who understands the internals of `BitSet` better than me can make a general-purpose non-allocating version that’s faster on all cases?

---

<div class="post-metadata">

**Author:** ![stev47](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stev47/32/14090_2.png) [@stev47](https://discourse.julialang.org/u/stev47)\
**Post date:** [August 2, 2020, 1:28pm UTC](https://discourse.julialang.org/t/issubset-bitset-bitset-is-slow-and-allocates-unnecessarily/43828/2 "2020-08-02T13:28:10Z")

</div>

maybe something like [this](https://github.com/JuliaLang/julia/pull/36882)?

```julia
using BenchmarkTools

function issubset_fast(a::BitSet, b::BitSet)
    n = length(a.bits)
    shift = b.offset - a.offset
    i, j = shift, shift + length(b.bits)

    f(a, b) = a == a & b
    return (
        all(@inbounds iszero(a.bits[i]) for i in 1:min(n, i)) &&
        all(@inbounds f(a.bits[i], b.bits[i - shift]) for i in max(1, i+1):min(n, j)) &&
        all(@inbounds iszero(a.bits[i]) for i in max(1, j+1):n))
end

s1 = BitSet([2i for i=1:100]);
s2 = BitSet([7i+70 for i=1:15]);
s3 = BitSet([20i+70 for i=1:6]);
s4 = BitSet([2i for i=1:99]);

@btime issubset($s1, $s1);
@btime issubset_fast($s1, $s1);
@btime issubset($s2, $s1);
@btime issubset_fast($s2, $s1);
@btime issubset($s3, $s1);
@btime issubset_fast($s3, $s1);
@btime issubset($s4, $s1);
@btime issubset_fast($s4, $s1);

```

On my machine:

```julia
  133.868 ns (3 allocations: 160 bytes)
  8.346 ns (0 allocations: 0 bytes)
  128.104 ns (3 allocations: 160 bytes)
  5.216 ns (0 allocations: 0 bytes)
  123.255 ns (3 allocations: 160 bytes)
  7.014 ns (0 allocations: 0 bytes)
  128.310 ns (3 allocations: 160 bytes)
  8.346 ns (0 allocations: 0 bytes)

```

Though the speedup observed here might be somewhat unrepresentative.