Library proposal: add a Location interface for element-wise operations on Data.Map (#4887)

[Johan Tibell]

On Fri, Jan 7, 2011 at 6:37 PM, Ross Paterson <ross at soi.city.ac.uk> wrote:
> This is a variant of a suggestion by apfelmus:
>
>  http://www.haskell.org/pipermail/libraries/2010-September/014510.html
>
> To avoid proliferation of variants of element-wise operations, the idea
> is to split these operations into two phases mediated by a new Location
> type, so that users can do whatever they like between these phases.
> Documentation is here:
>
>  http://code.haskell.org/~ross/containers_doc/Data-Map.html#3
>
> This adds a type and 9 functions to the interface, but makes possible
> monadic updates and much more.  As an illustration, the file MapOps.hs
> attached to the ticket gives definitions of 30 of the public functions of
> Data.Map in terms of the new interface.  At least in the case of insert,
> this definition is slightly faster than the current one.

I ran the current benchmark suite and my results differ from yours.
Here's the baseline for the current API:

insert,"317.7258 us"
"insertWith empty","326.9462 us"
"insertWith update","306.1100 us"
"insertWith' empty","330.3835 us"
"insertWith' update","295.4943 us"
"insertWithKey empty","329.2176 us"
"insertWithKey update","306.1306 us"
"insertWithKey' empty","330.5804 us"
"insertWithKey' update","295.7395 us"
"insertLookupWithKey empty","800.2740 us"
"insertLookupWithKey update","747.5337 us"
"insertLookupWithKey' empty","793.6592 us"
"insertLookupWithKey' update","683.3591 us"
delete,"156.7483 us"
update,"426.2789 us"
updateLookupWithKey,"492.0369 us"
alter,"302.2354 us"

And here's the current API, implemented in terms of Location (i.e.
using MapOps.hs).

insert,"532.1855 us"
"insertWith empty","532.5082 us"
"insertWith update","472.3454 us"
"insertWith' empty","530.2606 us"
"insertWith' update","457.9754 us"
"insertWithKey empty","526.2428 us"
"insertWithKey update","689.5042 us"
"insertWithKey' empty","528.4261 us"
"insertWithKey' update","456.7405 us"
"insertLookupWithKey empty","532.3916 us"
"insertLookupWithKey update","683.7498 us"
"insertLookupWithKey' empty","526.8173 us"
"insertLookupWithKey' update","459.0202 us"
delete,"298.9599 us"
update,"441.9685 us"
updateLookupWithKey,"441.2167 us"
alter,"444.8947 us"

It's interest to compare the Location-based API to simply using
'lookup' and 'insert', which is another way to get rid of
proliferation of element-wise operations. Here's the results for
implementing insertWith' in terms of those two functions:

"insertWith' empty","606.2098 us"
"insertWith' update","492.5084 us"

So the baseline insertWith' is 35% faster than the Location-based
insertWith' which is 7% faster than composing lookup and insert, on
the "insertWith' update" benchmark.

Can we get the Location-based implementation to perform closer to the
current implementation?

Johan