Consider optimizing map update for the shape-preserving case
Open
Map
performance
- Dominant language
- Haskell
- Stars
- 355
- Forks
- 194
- Avg merge
- 3d 4h
- Merged PRs (30d)
- 4
Description
One of the major costs of `update` is rebalancing on the way up. Notably, this has to follow pointers to the _siblings_ of all nodes along the path. We can avoid this in cases where the update neither inserts nor deletes a key by returning a flag saying so. This will obviously hurt a bit in cases where the shape _does_ change, but I conjecture that it won't hurt much.
Contributor guide
Assessment
This issue has not been assessed yet.