Hacktoberfest 2026: the issues maintainers tagged for October, open and beginner-friendly. Browse Hacktoberfest issues

Faster IntMap.size and IntSet.size

Open
  • Is something wrong?
#1,062 0 comments 2 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Assessment

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

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.

Description

IntMap IntSet performance

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.

Dominant language
Haskell
Stars
356
Forks
195
Avg merge
3d 42m
Merged PRs (30d)
5

Getting set up

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

More from haskell/containers

All issues in haskell/containers

Similar issues

More Haskell issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.