Better unordered folds?
Nobody has claimed this yet.
- Dominant language
- Haskell
- Stars
- 17
- Forks
- 12
- PR merge metrics
- No merged PRs in 30d
Description
I'm not a huge fan of the way we implement unordered folds. The compiler has no clue what they're up to, so optimization is garbage. I experimented with using an operation
```haskell
viewU :: BinomHeap a -> Maybe (a, BinomHeap a)
```
which extracts the root of the first binomial tree, to implement `foldlU'`.
Unfortunately, the performance was worse than what we do now. But I wonder if things might change if we work in bigger chunks. For starters, something like
```haskell
viewU2 :: BinomForest (Succ Zero) a -> Maybe (a, a, BinomForest (Succ Zero) a)
```
Working with two elements at once should reduce the churn in the low bits, and might give this technique some hope.
Contributor guide
No contributing guide indexed for this repository
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.
Research direction
Start with the existing unordered-fold implementation and the named foldlU', viewU, and viewU2 entry points. Compare the current approach with processing two elements at a time; done means determining whether the proposed technique improves performance and, if so, applying it to the unordered fold.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- haskell
- Domain
- performance
- Issue type
- Refactor
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 25/100