haskell / haskell/containers

Faster IntMap.size and IntSet.size

Open
#1,062 0 comments 2 reactions 0 assignees View on GitHub
IntMap IntSet performance
Dominant language
Haskell
Stars
355
Forks
194
Avg merge
3d 4h
Merged PRs (30d)
4

Description

I've been playing around with a few alternative implementations for `IntMap.size` to see if it can be made faster, and interestingly it seems it can.

Here are the implementations: https://gist.github.com/meooow25/0864ec79ad7885b470bf3d927b4deffa

And results on my machine with GHC 9.10.1:

```
asc
size: OK
2.08 μs ± 179 ns
sizeNoNil: OK
1.66 μs ± 105 ns, 0.80x
sizeUnroll: OK
1.54 μs ± 124 ns, 0.74x
size2: OK
1.33 μs ± 22 ns, 0.64x
size3: OK
1.14 μs ± 102 ns, 0.55x
size4: OK
1.16 μs ± 51 ns, 0.56x
sizeStack2: OK
1.49 μs ± 61 ns, 0.71x
rand
size: OK
2.17 μs ± 149 ns
sizeNoNil: OK
2.02 μs ± 179 ns, 0.93x
sizeUnroll: OK
2.53 μs ± 188 ns, 1.17x
size2: OK
1.52 μs ± 115 ns, 0.70x
size3: OK
1.36 μs ± 108 ns, 0.63x
size4: OK
1.56 μs ± 119 ns, 0.72x
sizeStack2: OK
1.43 μs ± 94 ns, 0.66x
```

Of course, these are still O(n) (#763), but being faster doesn't hurt.

`size3` seems to be doing the best so we could switch to it, unless someone offers a faster implementation.

Contributor guide

Open the contributing guide

Research direction

Start by comparing the existing IntMap.size and IntSet.size implementations with the alternatives in the linked gist. Run the reported benchmarks with GHC 9.10.1, check that the candidate preserves the existing size behavior, and confirm whether the faster implementation improves both ascending and random inputs before deciding whether to adopt it.

Written by the indexing model from the issue text.

Assessment

Tech stack
haskell
Domain
data
Issue type
Refactor
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.