haskell / containers

Assorted concrete container types
https://hackage.haskell.org/package/containers
315 stars 178 forks source link

Add Data.IntSet.fromRange #965

Closed meooow25 closed 1 year ago

meooow25 commented 1 year ago

For #632

Benchmark on GHC 9.2.5:

  fromRange:       OK (0.20s)
    376  ns ±  22 ns, 4.0 KB allocated,   2 B  copied, 7.0 MB peak memory
  fromRange:small: OK (0.18s)
    10.0 ns ± 872 ps, 119 B  allocated,   0 B  copied, 7.0 MB peak memory

Comparing fromDistinctAscList [1..2^12] from #951 against fromRange (1,2^12), currently it takes 24.3 μs (~62x the time) and with fusion it would still take 4.49 μs (~11x the time).

meooow25 commented 1 year ago

Note: I've made some changes to the algorithm. If you didn't see the previous version you can ignore this comment. I made the change because I realized that we could be forced to do $O(W)$ work even when $n$ is very small, making the complexity $O(n/W + W)$. I changed goL and goR to avoid this, so it's correctly $O(n/W)$ now. This can be observed on fromRange (-1,0) which changed from ~70ns to 10ns. Also fixed a bug where I used bitmapOfSuffix instead of bitmapOf, the tests ran fine because on x86 the shift value is masked to 5/6 bits anyway.

treeowl commented 1 year ago

Cool!