search

haskell-unordered-containers / unordered-containers

Efficient hashing-based container types
BSD 3-Clause "New" or "Revised" License
221 stars 97 forks source link

Investigate performance of `update` #405

Open sjakobi opened 2 years ago

sjakobi commented 2 years ago

In the context of #404 I've had a brief look at update. My impression was that it might benefit from inlining alter. It would be good to take a closer look once #404 is done.

treeowl commented 2 years ago

A little bit, probably. Have you played with applying manual worker-wrapper to the function argument of alter?

alter# :: _ => ((# (##) | v #) -> (# (##)  | v #)) -> k -> HashMap k v -> HashMap k v

alter f = alter# f where
  f' (# _ | #) = twiddle (f Nothing)
  f' (# | v #) = twiddle (f (Just v))
  twiddle Nothing = (# (##) | #)
  twiddle (Just v) = (# | v #)

The hope is that f inlines into the wrapper and the Maybes are never realized. Whether this is faster... I'm not so sure. I've had pretty mediocre results from my limited experiments with unboxed sums, but that was a few years ago.