Re: Efficent lens operation for Data.Map et al.

* roconnor@theorem.ca [2012-01-18 19:26:02-0500]

On Wed, 18 Jan 2012, Johan Tibell wrote:

...

On Wed, Jan 18, 2012 at 1:51 PM, Roman Cheplyaka wrote:

...

* roconnor@theorem.ca [2012-01-18 16:35:52-0500]

...

On Wed, 18 Jan 2012, Johan Tibell wrote:

...

IIRC you just replace the current functions with yours and run make in the benchmarks/ directory to compile the benchmark binaries (which use Criterion). Then simply run them.

I got an error trying to build the benchmarks:

Worked for me with GHC 7.0.4.

The results are attached.

In short, your version is indeed typically slower, up to a factor of 5 (for lookup).

That's even slower than I expected. Doesn't mean that we cannot add the operation though (although we should think about exactly which operation(s) we need.)

Ya, all I really want is one function:

lens :: Key -> IntMap a -> (Maybe a -> IntMap a, Maybe a)

for every container type.

Considering the benchmark results, it seems that implementing lens in terms of lookup and update actually is the fastest option we've seen? The difference between one and two traversals could become significant as the tree depth increases, but: * for Data.{Map,Set} it's logarithmic in the container size, so it won't be large for something that fits into memory * for Data.Int{Map,Set} it's bounded by the size of Int -- Roman I. Cheplyaka :: http://ro-che.info/