Proposal: Make size (from 'unordered-containers') run in constant time

[Alexandre Rodrigues]

Greetings;

This email's purpose is to request comments from this mailing list regarding a PR to ‘unordered-containers’ (here: https://github.com/tibbe/unordered-containers/pull/170).

This PR modifies the existing code so that ‘size’ can calculate the size of a ‘Hash{Map, Set}’ in constant time instead of linear, which is its current performance.

To avoid making this message too large, the benchmarking results are not included here, but you may find them in the PR’s discussion. In short, a penalty of about 10% to functions in the library may be expected, and both ‘filterWithKey’ and ‘fromListWith’ are much slower, which is an issue I’d like to solve.

If this PR is mediocre, if you have any suggestions to make it better, or any other comment, please reply to this email.

I'd like to thank David Feuer and Niklas Hambüchen for the many improvements suggested to this PR, and Johan Tibell for writing an excellent library.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/libraries/attachments/20180217/26e15857/attachment-0001.html>