# Difference between Set{Int}() and BitSet()

**URL:** <https://discourse.julialang.org/t/difference-between-set-int-and-bitset/27737>\
**Category:** Performance\
**Tags:** question, performance\
**Created:** [August 20, 2019, 5:04am UTC](https://discourse.julialang.org/t/difference-between-set-int-and-bitset/27737 "2019-08-20T05:04:20Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![biona001](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/biona001/32/16497_2.png) [@biona001](https://discourse.julialang.org/u/biona001)\
**Post date:** [August 20, 2019, 5:04am UTC](https://discourse.julialang.org/t/difference-between-set-int-and-bitset/27737/1 "2019-08-20T05:04:20Z")

</div>

I want to compute the intersection of a matrix of sets. I came across `BitSet` in addition to `Set{Int}`, and the following benchmarks (which initialize a matrix of Set or BitSet) baffles me in terms of memory usage:

```julia
julia> @benchmark [Set{Int}() for i in 1:1000, j in 1:1000]
BenchmarkTools.Trial:
  memory estimate: 480.65 MiB
  allocs estimate: 5000002
  --------------
  minimum time: 362.486 ms (63.15% GC)
  median time: 722.896 ms (79.61% GC)
  mean time: 746.622 ms (81.50% GC)
  maximum time: 1.108 s (86.71% GC)
  --------------
  samples: 8
  evals/sample: 1

```

```julia
julia> @benchmark [BitSet() for i in 1:1000, j in 1:1000]
BenchmarkTools.Trial:
  memory estimate: 160.22 MiB
  allocs estimate: 3000002
  --------------
  minimum time: 62.636 ms (0.00% GC)
  median time: 367.854 ms (80.83% GC)
  mean time: 392.743 ms (82.20% GC)
  maximum time: 542.071 ms (87.16% GC)
  --------------
  samples: 13
  evals/sample: 1

```

And indeed using `BitSet` reduced my code’s memory usage by more than 10 times. My question is:

1. Why does a matrix of sets (BitSet) require so much memory to initialize? In comparison, a 1000x1000 Matrix{Float64} is around 8MB.
2. Is `BitSet()` concretely typed? I want the compiler to know I will only ever push `Int` into my sets.
3. When is it more appropriate to use `BitSet` as opposed to `Set`? I read the [documentation](https://docs.julialang.org/en/v1/base/collections/index.html#Set-Like-Collections-1) but I don’t quite get it.

Thank you for your time.

---

<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:** [August 20, 2019, 5:32am UTC](https://discourse.julialang.org/t/difference-between-set-int-and-bitset/27737/2 "2019-08-20T05:32:06Z")

</div>

I am not sure those benchmarks are very informative, unless all your sets are empty.

As the docs explain, `BitSet` is basically a bitstring of flags. Use it when your sets are dense.

`BitSet` happens to be concretely typed, but generally you should use `@code_warntype` and similar to investigate these things. See [Performance Tips · The Julia Language](https://docs.julialang.org/en/v1/manual/performance-tips/#man-performance-tips-1)

---

<div class="post-metadata">

**Author:** ![foobar\_lv2](https://avatars.discourse-cdn.com/v4/letter/f/ee59a6/32.png) [@foobar\_lv2](https://discourse.julialang.org/u/foobar_lv2)\
**Post date:** [August 20, 2019, 8:33am UTC](https://discourse.julialang.org/t/difference-between-set-int-and-bitset/27737/3 "2019-08-20T08:33:26Z")

</div>

Also consider using [static-sized bitsets](https://github.com/JuliaArrays/StaticArrays.jl/pull/647) if you want to represent densish subsets of `1:64*N` with known `N`. It doesn’t look like that PR will land in static arrays, but you can just take the source and run with it.