Use BitSet for Tracer input set

[adrhill]

@gdalle, you were sceptical on this topic, but it looks like BitSets improve the performance even further, cutting runtime in half:

julia> include("test/benchmark.jl")
[ Info: Benchmarking Brusselator of size 6 with tracer...
BenchmarkTools.Trial: 10000 samples with 1 evaluation.
 Range (min … max):  27.000 μs …  2.795 ms  ┊ GC (min … max):  0.00% … 98.14%
 Time  (median):     28.917 μs              ┊ GC (median):     0.00%
 Time  (mean ± σ):   33.634 μs ± 96.856 μs  ┊ GC (mean ± σ):  12.10% ±  4.15%

     ▂▆██▅▁    ▁▂▁                                             
  ▁▂▅███████▆▆▇███▇▆▅▃▃▂▂▂▁▁▁▁▁▂▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁ ▃
  27 μs           Histogram: frequency by time        39.4 μs <

 Memory estimate: 108.19 KiB, allocs estimate: 1252.
 
[ Info: Benchmarking Brusselator of size 6 with symbolics...
BenchmarkTools.Trial: 2253 samples with 1 evaluation.
 Range (min … max):  2.048 ms …   4.927 ms  ┊ GC (min … max): 0.00% … 55.67%
 Time  (median):     2.085 ms               ┊ GC (median):    0.00%
 Time  (mean ± σ):   2.218 ms ± 574.703 μs  ┊ GC (mean ± σ):  5.77% ± 11.90%

  █▇▁                                                       ▂  
  ███▃▄▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▃██ █
  2.05 ms      Histogram: log(frequency) by time      4.77 ms <

 Memory estimate: 2.86 MiB, allocs estimate: 41727.

Down from 76.298 μs ± 174.080 μs in #4.

---

[ Info: Benchmarking Brusselator of size 24 with tracer...
BenchmarkTools.Trial: 7975 samples with 1 evaluation.
 Range (min … max):  507.959 μs …   3.436 ms  ┊ GC (min … max):  0.00% … 79.82%
 Time  (median):     545.792 μs               ┊ GC (median):     0.00%
 Time  (mean ± σ):   626.101 μs ± 416.698 μs  ┊ GC (mean ± σ):  12.28% ± 14.41%

  ██▂                                                        ▁  ▁
  ███▅▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▄▁▃▅▆▇████ █
  508 μs        Histogram: log(frequency) by time       2.88 ms <

 Memory estimate: 2.15 MiB, allocs estimate: 23416.
 
[ Info: Benchmarking Brusselator of size 24 with symbolics...
BenchmarkTools.Trial: 131 samples with 1 evaluation.
 Range (min … max):  34.386 ms … 43.780 ms  ┊ GC (min … max):  0.00% … 12.79%
 Time  (median):     38.694 ms              ┊ GC (median):    10.20%
 Time  (mean ± σ):   38.394 ms ±  2.239 ms  ┊ GC (mean ± σ):   8.32% ±  4.78%

   ▇                       ▂ ▄ █   ▂                           
  ▅█▇▅▁▅▁▃▃▃▃▇▁▁▁▃▃▇█▆▆▇▅▃██▃█▅█▆█▆█▃▃▆▆▃▅▃▃▆▃▁▅▅▁▁▇▁▁▃▁▁▁▁▁▅ ▃
  34.4 ms         Histogram: frequency by time        43.7 ms <

 Memory estimate: 45.80 MiB, allocs estimate: 672702.

Down from 1.315 ms ± 688.047 μs in #4.

---

[ Info: Benchmarking NNlib.conv with tracer...
BenchmarkTools.Trial: 46 samples with 1 evaluation.
 Range (min … max):   95.325 ms … 218.397 ms  ┊ GC (min … max): 11.79% … 58.32%
 Time  (median):     105.045 ms               ┊ GC (median):    17.90%
 Time  (mean ± σ):   108.741 ms ±  20.552 ms  ┊ GC (mean ± σ):  20.71% ±  8.62%

  ▃█▃  ▁▃ ▄                                                      
  ███▆▇██▇█▇▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▄▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▄ ▁
  95.3 ms          Histogram: frequency by time          218 ms <

 Memory estimate: 505.94 MiB, allocs estimate: 3345683.

Symbolics fails on NNlib.conv.

[codecov-commenter]

Codecov Report

All modified and coverable lines are covered by tests ✅

Project coverage is 70.40%. Comparing base (121fef8) to head (36cd987).

Additional details and impacted files

@@            Coverage Diff             @@
##             main      #11      +/-   ##
==========================================
- Coverage   71.00%   70.40%   -0.60%     
==========================================
  Files           6        6              
  Lines         100       98       -2     
==========================================
- Hits           71       69       -2     
  Misses         29       29              

☔ View full report in Codecov by Sentry.
📢 Have feedback on the report? Share it here.

[gdalle]

I never was skeptical about BitSets, just about BitVectors 😉 so now we're at a casual 100x speed up or what ^^?

[Vaibhavdixit02]

Looks more like 70x, not that that isn't great 😅