search

haskell-unordered-containers / unordered-containers

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

`updateOrConcatWithKey` could be more efficient #403

Open sjakobi opened 2 years ago

sjakobi commented 2 years ago

https://github.com/haskell-unordered-containers/unordered-containers/blob/b6bde46eae679111c3f088964f192290cc08b6c8/Data/HashMap/Internal.hs#L2181-L2210

I think that we could avoid allocating the intermediary indices array. Instead over-allocate the output array and shrink (#362) it once we've determined the final size.

When matching the keys we could also use a similar optimization as suggested in https://github.com/haskell-unordered-containers/unordered-containers/issues/291.