Repository : ssh://[email protected]/containers On branch : ghc-head Link : http://git.haskell.org/?p=packages/containers.git;a=commit;h=e4e9a97fb3883b3cd5b52e4e73adcd3b9952d97a
>--------------------------------------------------------------- commit e4e9a97fb3883b3cd5b52e4e73adcd3b9952d97a Author: Milan Straka <[email protected]> Date: Fri Aug 31 00:22:21 2012 +0200 Improve {Map,Set}.fromList. While the input is sorted, use implementation of fromDistinctAscList. When first unordered key is found, switch to the general fromList implementation, which inserts the rest of the keys to the already constructed tree. This gives a huge advantage for sorted inputs. The inplementation is 5% (for Map) and 0% (for Set) slower than fromDistinctAscList in that case. The larger overhead for Map is probably because of the the pair unpacking. For input list of size 2^12, the fromList is 10 times faster if the input is sorted. The fromList could be further improved by trying to handle semi-sorted inputs. But currently I have no idea how to do it efficiently. >--------------------------------------------------------------- e4e9a97fb3883b3cd5b52e4e73adcd3b9952d97a Data/Map/Base.hs | 44 +++++++++++++++++++++++++++++++++++++++++--- Data/Map/Strict.hs | 43 ++++++++++++++++++++++++++++++++++++++++--- Data/Set/Base.hs | 43 +++++++++++++++++++++++++++++++++++++++++-- 3 files changed, 122 insertions(+), 8 deletions(-) Diff suppressed because of size. To see it, use: git diff-tree --root --patch-with-stat --no-color --find-copies-harder --ignore-space-at-eol --cc e4e9a97fb3883b3cd5b52e4e73adcd3b9952d97a _______________________________________________ ghc-commits mailing list [email protected] http://www.haskell.org/mailman/listinfo/ghc-commits
