search

haskell-unordered-containers / unordered-containers

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

Run alter in one pass #471

Open oberblastmeister opened 2 years ago

oberblastmeister commented 2 years ago

Resolves #404

oberblastmeister commented 2 years ago

I bet we could implement delete in terms of alter with some inlining.

sjakobi commented 2 years ago

I bet we could implement delete in terms of alter with some inlining.

Probably. My inclination is not to rely on GHC optimizations more than necessary though.

Also, wouldn't this increase the size of the unfolding and thereby make it less likely that delete is inlined in user code?!

oberblastmeister commented 2 years ago

My inclination is not to rely on GHC optimizations more than necessary though.

I think these are very simple optimizations, beta reduction and case simplification, which are performed by the ghc simplifier, and I am pretty sure these are very likely to fire. We also rely on these sorts of optimizations throughout the library anyways. It doesn't matter that much though, but would reduce a lot of code duplication, as alter is pretty much a direct copy of delete.

Why would this increase the size of the unfolding?

sjakobi commented 2 years ago

Sorry for the late response!

My inclination is not to rely on GHC optimizations more than necessary though.

I think these are very simple optimizations, beta reduction and case simplification, which are performed by the ghc simplifier, and I am pretty sure these are very likely to fire. We also rely on these sorts of optimizations throughout the library anyways. It doesn't matter that much though, but would reduce a lot of code duplication, as alter is pretty much a direct copy of delete.

I think this means that GHC will need to spend more cycles on optimizing usage of delete in user code. So the effect will be an increase in compile time and possibly a failure to perform other optimization once GHC runs out of simplifier iterations.

Feel free to give it a try in a follow-up PR though. I'm curious what effects this will have on the Core for delete.

Why would this increase the size of the unfolding?

My bad. Briefly, I had thought that the unfolding for delete would contain the unoptimized unfolding of alter.

oberblastmeister commented 2 years ago

I can't really tell if the benchmarks get faster or not, which is a bit weird.

oberblastmeister commented 2 years ago

I wonder if the old alter inlines, thus removing the closure and simplifying the cases. I am pretty sure the new alter will never inline.