Set/Map fromList using sorting
Nobody has claimed this yet.
Assessment
- Difficulty
- 5/5
- Estimated time
- Over a week
- Newbie friendliness
- 35/100
Research direction
Start by locating the Set fromList implementation and the existing STUArray-based DFS code mentioned in the issue. Explore whether sorting a mutable array and building a Set preserves the expected behavior and performance, including already sorted input and GHC-specific CPP maintenance. Done means demonstrating the approach’s allocation and speed tradeoffs and accounting for the portability costs.
Written by the indexing model from the issue text.
Description
I've had this thought for a while so I might as well document it and try it out at some point.
The idea is to dump the list contents into a mutable array, sort it in-place, then build a Set out of it. Mergesort (as opposed to other algorithms) would to preserve the "O(n) if already sorted" property. What I expect:
The good
- Allocations go way down, and things get faster in most cases.
The bad
- Might be slower on already sorted input.
- This is GHC-only, so there will some icky bits to maintain with CPP. A bit like how we use STUArray for dfs, but more involved.
- Dominant language
- Haskell
- Stars
- 356
- Forks
- 195
- Avg merge
- 3d 42m
- Merged PRs (30d)
- 5
Getting set up
- No Dockerfile or Docker Compose file
- No pull request template
- Read the contributing guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
More from haskell/containers
-
major-release strictness Tree
Difficulty 2/5 1-3 hours Newbie friendliness 72/100
haskell/containers#1260 ·
-
low-hanging-fruit performance Seq
Difficulty 4/5 3-5 days Newbie friendliness 43/100
haskell/containers#1262 · 2 comments ·
-
Difficulty 5/5 Over a week Newbie friendliness 35/100
haskell/containers#1261 · 11 comments ·
-
IntSet low-hanging-fruit performance
Difficulty 3/5 1-2 days Newbie friendliness 58/100
haskell/containers#1251 ·
-
maintainability major-release
Difficulty 3/5 1-2 days Newbie friendliness 70/100
haskell/containers#1250 ·
All issues in haskell/containers
Similar issues
-
Difficulty 2/5 1-3 hours Newbie friendliness 72/100
Maintainers usually reply within 2 days
-
A failed JNA download is reported as a corrupt zip, because `curl` in `Makefile` lacks `--fail`Open
Difficulty 1/5 Under an hour Newbie friendliness 88/100
objectionary/phino#1884 · 1 comment ·
Maintainers usually reply within 1 day
-
component: hls-eval-plugin status: needs triage type: bug
Difficulty 2/5 1-3 hours Newbie friendliness 65/100
haskell/haskell-language-server#5144 · 2 comments ·
Maintainers usually reply within 1 day
-
[BUG]: -std selection does not work with COBOL -> GnuCOBOL 1.1Possibly taken A pull request linked to this issue is open or already merged. Openbug
Difficulty 2/5 1-3 hours Newbie friendliness 62/100
compiler-explorer/compiler-explorer#9272 ·
Maintainers usually reply within 1 day
-
enhancement
Difficulty 1/5 Under an hour Newbie friendliness 82/100
alunduil/siren-json.hs#247 ·
Maintainers usually reply within 1 day