New patches in /srv/darcs/git-mirrors/containers
commit 207010cabd5d697c9e6688460afe01241e3687e1
Author: Milan Straka <[email protected]>
Date: Mon Apr 30 14:29:46 2012 +0200
Add tests and benchmarks to sdist.
commit cfde03ba1e69dea36fb85288681ee9e236966beb
Author: Milan Straka <[email protected]>
Date: Mon Apr 30 14:28:30 2012 +0200
Add comment to tests/Makefile.
Add comment to tests/Makefile that users should use cabal to build and
run tests.
commit 556b80c6f7b457393428f42700405d04071491de
Author: Milan Straka <[email protected]>
Date: Sat Apr 28 16:51:13 2012 +0200
Remove type of local 'go' function in query methods of Set and Map.
The resulting implementations are a bit faster, and there seems to be no
increased heap-allocation. I will confirm this by examining GHC memory
allocation.
commit 5810f064f1270688ebdcc7055545f3140f3aa5b2
Author: Milan Straka <[email protected]>
Date: Sat Apr 28 16:36:31 2012 +0200
Define Map.{union,difference,intersection}WithKey using mergeWithKey.
The resulting implementations are approximately 40-50% faster, although
for some input data the performance is worse. This happens
* in unionWithKey, if the data are disjunct: 15% slowdown
* in differenceWithKey, as now we recurse over the first tree and not
the second. The slowdown happens also only for disjunct data: 30%.
See the SetOperations benchmark for yourself if you are interested.
commit bb7213c7d2f53c60d79e6b6bf5cac3d35234dc61
Author: Milan Straka <[email protected]>
Date: Sat Apr 28 16:35:51 2012 +0200
Add Map.mergeWithKey.
commit c82a6386772774fe55475d375ceea0345acbb109
Author: Milan Straka <[email protected]>
Date: Fri Apr 27 13:34:48 2012 +0200
Remove redundant parenthesis.
commit cd5acad324e64436428fdf24a4a8e4a2291e4f11
Author: Milan Straka <[email protected]>
Date: Fri Apr 27 11:58:55 2012 +0200
Fix warnings, formatting.
commit cd96a9045df8d2f8d98d9ec6e13c4a2492f0836b
Author: Milan Straka <[email protected]>
Date: Fri Apr 27 11:51:48 2012 +0200
Improve {Map, Set}.union.
Instead of having a special case set `union` set_of_size_1 in union,
move it to hedgeUnion, so it can be used recursively. Benchmark shows up
to 30% speedup.
commit b19776e51d99f9264c9449952950f5f6071a0aa3
Author: Milan Straka <[email protected]>
Date: Fri Apr 27 11:30:13 2012 +0200
Improve {Map, Set}.intersection.
Use the hedge-intersection algorithm, similar to hedge-union and
hedge-difference.
Depending on inputs, this causes up to 80% speedup.
Also remove Set.splitLookup, which was used only to define intersection.
commit cf2cdd50743f540c0781a6f1455cebec9a6042d1
Author: Milan Straka <[email protected]>
Date: Fri Apr 27 11:12:07 2012 +0200
Once again revert argument capturing by local 'go' function.
At last I found an example, where capturing the argument in local 'go'
function in 'member' causes increased heap-allocation. It is caused by
'go' function floating out of 'member' and allocating a dictionary and
the key argument.
This happens only with Map and Set methods. Therefore in IntMap and IntSet,
'go' function still captures the argument (and GHC shows no increased
heap-allocation as a result of that).
commit 6f8344ef7e22ba7dee1e97a86f976bbec29dcc50
Author: Milan Straka <[email protected]>
Date: Fri Apr 27 10:36:28 2012 +0200
Improve heap-allocation in mergeWithKey'.
Avoid allocating the closure for local function 'merge'.
commit 044579a42383a1de214717e66823b1f5c7869c0b
Author: Milan Straka <[email protected]>
Date: Wed Apr 25 18:54:04 2012 +0200
Add fromSet method.
Following a proposal on libraries@..., we add fromSet method to Map and
IntMap:
Map.fromSet :: (k -> a) -> Set k -> Map k a
IntMap.fromSet :: (Key -> a) -> IntSet -> IntMap a
It is implemented using exported Set and IntSet constructors.
Map.fromSet is trivial, as Map and Set have the same structure.
The IntMap.fromSet implementation is more complicated, as IntSet uses
dense representation of several last leves of the trie.
commit a9b07a6e0eff8103564de45785cdc69e6fb0c8f5
Author: Milan Straka <[email protected]>
Date: Wed Apr 25 18:45:59 2012 +0200
Fix warnings.
commit cdc2c695b879ff18c0c830ff8d79e689c9ed8f6c
Author: Milan Straka <[email protected]>
Date: Tue Apr 24 18:05:40 2012 +0200
Improve manual makefile for tests.
Leave dependencies on GHC instead of make.
commit ab8460f8017c1defb649df8413407153d6750d1c
Author: Milan Straka <[email protected]>
Date: Tue Apr 24 17:32:04 2012 +0200
Improve {Map, IntMap}.keysSet.
The keysSet method is now implemented using the exported constructors of
Data.{Set, IntSet}.Base.
The implementation of Map.keysSet is trivial, as Set and Map use same
tree structure.
The implementation of IntMap.keysSet is slightly complicated, because of
the dense representation of IntSet, where several last levels of the
tree are flatten into a bitmap.
commit 57042dc65cdedfc64d5f63e144b87c98443438f9
Author: Milan Straka <[email protected]>
Date: Tue Apr 24 16:58:05 2012 +0200
Factor Data.IntSet into Data.IntSet.Base and Data.IntSet.
Similarly to Map and IntMap, the whole functionality is in
Data.IntSet.Base. The Data.IntSet module just reexports methods from
Data.IntSet.
The only difference between Data.IntSet.Base and Data.IntSet is that
Data.IntSet.Base exports the constructors of IntSet data type. This will
be used in IntMap to define efficient versions of keysSet and fromSet.
commit ea8688fb6065da1f967168eab46029ef7be84407
Author: Milan Straka <[email protected]>
Date: Tue Apr 24 16:45:45 2012 +0200
Factor Data.Set into Data.Set.Base and Data.Set.
Similarly to Map and IntMap, the whole functionality is in
Data.Set.Base. The Data.Set module just reexports methods from Data.Set.
The only difference between Data.Set.Base and Data.Set is that
Data.Set.Base exports the constructors of Set data type. This will be
used in Map to define efficient versions of keysSet and fromSet.
commit 083451fb0bcd3edcdfa9cc43bf688af408986011
Author: Milan Straka <[email protected]>
Date: Tue Apr 24 16:23:13 2012 +0200
Add lookupLT, lookupGT, lookupLE, lookupGE methods.
Following the proposal on libraries@..., we add lookupLT, lookupGT,
lookupLE, lookupGE methods to Set, Map, IntSet and IntMap.
The implementations were chosen using the LookupLE benchmark.
Current implementations do not heap-allocate apart from the result.
Corresponding tests are added. The test suites for Set and IntSet
now use HUnit too.
commit dbc5fb6be82398e391f40f31bbea81b859ceda9a
Author: Milan Straka <[email protected]>
Date: Tue Apr 24 16:20:29 2012 +0200
On 32-bit architectures, improve highestBitMask.
Even on 32-bit architectures, bit shift of size 32 was performed.
commit ef6112461bdbb5574d57da2bebcea75f3cfc5fe6
Author: Milan Straka <[email protected]>
Date: Mon Apr 23 18:29:50 2012 +0200
Improve one of the benchmarked methods: lookupGE4.
commit 0e6152727e6ef60b7ac12951a4c88c27952f210e
Author: Milan Straka <[email protected]>
Date: Mon Apr 23 16:44:01 2012 +0200
Change ASCII character for underline from ^ to ~.
We use the following:
-- [Note: Some superimportant message]
-- ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Unfortunately, -- ^ is wrongly picked up by Haddock.
Instead we now use
-- [Note: Some superimportant message]
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commit 857ae5b7da3b730f579c546939e3d3776c237bff
Author: Milan Straka <[email protected]>
Date: Mon Apr 23 15:54:13 2012 +0200
Change INLINE to INLINABLE on methods using Ord.
As mentioned previously, INLINE - INLINABLE method chain does not result
in specialization, it has to be INLINABLE - INLINABLE.
commit 586df039376b0d1884d3c130be1b65b8f8b622e3
Author: Milan Straka <[email protected]>
Date: Mon Apr 23 10:57:45 2012 +0200
Add benchmark of lookupGE to choose best implementation.
Most of the code is by Twan van Laarhoven, thanks.
commit 349e88e2219d3ec3cdf40dbe0b3cd8e4ee00f7c3
Author: Milan Straka <[email protected]>
Date: Mon Apr 23 10:53:49 2012 +0200
Fix warnings.
commit b77a60ad0f95df9556f8304095f6c8ea70e67882
Author: Milan Straka <[email protected]>
Date: Mon Apr 23 10:02:12 2012 +0200
Move SetOperations benchmark to its own subdirectory.
Also improve the infrastructure to handle benchmarks in different
subdirectories.
commit af732b9bc06273684d821e75f93f424ae2141d6e
Author: Milan Straka <[email protected]>
Date: Sun Apr 22 18:06:21 2012 +0200
Manually inline {Map,IntMap}.map.
commit 6c430a5d7cb0bba29857b193729193217bcf048c
Author: Milan Straka <[email protected]>
Date: Sun Apr 22 18:00:43 2012 +0200
Inline {Map,Set}.fold* when 2 arguments are given.
Inlining folds when 2 arguments are given is consistent
with Prelude.foldr and {IntMap,IntSeT}.fold*.
commit 4cdb33f48129a01bc1eec3f1cfd02c94181d01f7
Author: Milan Straka <[email protected]>
Date: Sun Apr 22 17:54:00 2012 +0200
Remove obsolete comment about deleteWith.
DeleteWith is no longer method of any collection.
commit 32d84ba5eb82f34dbb8a8fabf07077d848cdb408
Author: Milan Straka <[email protected]>
Date: Sun Apr 22 17:48:29 2012 +0200
Improve heap-allocation by adding explicit type signatures.
When a local 'go' function is using methods from Ord dictionary,
this dictionary is heap-allocated at the entry to the outer function.
If it is given explicit type mentioning the Ord class, the dictionary is
passed on the stack, decreasing heap allocation.
commit 299ba9054c1f9ac97fe66e6c422b1b32730855ec
Author: Milan Straka <[email protected]>
Date: Sat Apr 21 22:14:42 2012 +0200
Improve Map indexing functions.
* Manually inline findIndex and deleteAt to avoid allocation.
* Give type to local 'go' function of findIndex and lookupIndex
to avoid heap allocation.
commit 78c1e523a6dacb092da6fa2deef04d498fd588a3
Author: Milan Straka <[email protected]>
Date: Sat Apr 21 21:41:22 2012 +0200
Improve query functions of Map and Set.
As documented in the Note: Local 'go' functions and capturing,
it is safe to use captured key argument in query functions.
Also, in order to decrease allocation, the query functions in Map
are manually inlined, so 'member' does not have to call 'lookup'
and heap-allocate 'Just a'.
Tests of query functions are much improved too.
commit 0928ff026a70b759be060f6ea46a48c58957049c
Author: Milan Straka <[email protected]>
Date: Sat Apr 21 21:37:14 2012 +0200
Insert missing space in an error message.
commit 1ae51a2993b5518b8f1e39963a509c42a98dbaec
Author: Milan Straka <[email protected]>
Date: Sat Apr 21 20:25:00 2012 +0200
Prevent multiple warnings.
Prevent multiple warnings caused by unsuccessful SpecConstr pass.
We do so by not inlining helper testing function.
commit 8142b0304511b7a687e508a6c8bf5e28680a3154
Author: Milan Straka <[email protected]>
Date: Fri Apr 20 20:26:47 2012 +0200
Add empty line between Notes.
commit c712fe4d92c3bfae59323eb74ba2259cb3e45a77
Author: Milan Straka <[email protected]>
Date: Fri Apr 20 18:32:18 2012 +0200
Inline Int{Map,Set}.{null, empty, singleton}.
These are probably inlined anyway, but we explicitly INLINE
them in Map and Set, so we do also in IntMap and IntSet for consistency.
commit 9be5ec295996794259189db969efa39bc7378b54
Author: Milan Straka <[email protected]>
Date: Fri Apr 20 18:18:55 2012 +0200
Improve query functions of IntMap and IntSet.
As documented in the Note: Local 'go' functions and capturing,
it is safe to use captured key argument in query functions.
Also, in order to decrease allocation, the query functions in IntMap
are manually inlined, so 'member' does not have to call 'lookup'
and heap-allocate 'Just a'.
Tests of query functions are much improved too.
commit 03a0620f8eaf0ad5af4d1f314d5e34842c3b23c3
Author: Milan Straka <[email protected]>
Date: Fri Apr 20 18:04:54 2012 +0200
Reorder the data constructors of Map and Set.
The order of constructors has clearly no effect on corectness.
Inspired by the change in order of constructors of IntMap and IntSet,
the benchmark shows slight improvement when changing the data
constructors from Tip | Bin to Bin | Tip.
Also, we now consistently use the same order of constructors in all
these structures: Map, Set, IntMap, IntSet.
commit bdae0d4fce159d3f4d43e7a67930627419fe52de
Author: Milan Straka <[email protected]>
Date: Fri Apr 20 17:57:35 2012 +0200
Improve programming documentation.
Move important programming comments to the beginning of the source file,
give them names and refer to the from the source code where necessarry.
commit 1a682593892f44d4727a53a51685d29d47042d33
Author: Milan Straka <[email protected]>
Date: Fri Apr 20 17:43:14 2012 +0200
Add forgotten GHC >= 7.0 condition in (!).
The INLINABLE pragma works only for GHC >= 7.0 and generates
warning for older compilers.
commit 6ab2ba0aada982256cb204c6e28846d846e97a6b
Merge: 7332813... 9d72ff1...
Author: Milan Straka <[email protected]>
Date: Sat Apr 14 19:04:41 2012 +0200
Merge branch 'master' of github.com:haskell/containers
commit 73328131d9573d0b1d2cd2d18abad7399368e816
Author: Milan Straka <[email protected]>
Date: Sat Apr 14 18:44:37 2012 +0200
Improve IntSet.{union, difference, intersection}.
Incorporate improvements achieved in IntMap implementation by using
mergeWithKey' -- i.e., reorder and modify pattern matches of combining
functions, to play nicely with pattern match compiler. Also improve
the ``Tip vs Bin'' case handling.
commit 0b3612276f50afeb89dbdf76d27c3a7c48508e48
Author: Milan Straka <[email protected]>
Date: Sat Apr 14 18:44:02 2012 +0200
Benchmark of set operations -- union, difference, intersection.
commit 12d03ebd2755f6acb78516d8f7ca5954b1e76cb0
Author: Milan Straka <[email protected]>
Date: Sat Apr 14 18:40:31 2012 +0200
Scripts for comparing csv results of benchmarks.
commit 1e3c78cf788a5b09fd121546cb2e7cacadc19617
Author: Milan Straka <[email protected]>
Date: Sat Apr 14 16:55:46 2012 +0200
Add IntMap.mergeWithKey.
The slightly more general internal function mergeWithKey' is used to
define both mergeWithKey and other combining functions union*,
difference*, intersection*.
The resulting implementations of union*, difference* and intersection*
are no slower than before, and up to 30% faster in case of two large
interleaved maps. Measured by benchmarks/SetOperations-IntMap.hs.
commit 9d72ff15f739e6ab2633e71fdb366e44c5af8e8a
Merge: d95988c... 76a2b9d...
Author: Milan Straka <[email protected]>
Date: Fri Mar 30 10:08:45 2012 -0700
Merge pull request #10 from batterseapower/master
Add traverseWithKey to Map and IntMap API
commit 76a2b9d97429497fe4f88cc47eb4945ba7eda163
Author: Max Bolingbroke <[email protected]>
Date: Fri Mar 30 14:20:15 2012 +0100
Add traverseWithKey to Map and IntMap API
Proposal reviewed and approved by the libraries list.
Particular thanks goes to Thomas Schilling for his suggestions
regarding how the function should be documented.
commit e0dfe5274aa4d70646e93b66234100c89d9d2b8a
Author: Milan Straka <[email protected]>
Date: Mon Mar 26 16:37:48 2012 +0200
Add Makefile for manually building tests.
commit cb1f087a0c37d586496689db9041182d81615234
Author: Milan Straka <[email protected]>
Date: Mon Mar 26 16:39:07 2012 +0200
Small benchmark changes.
* Uncomment all working benchmarks.
* Use whnf instead of nf, as all containers are spine and key strict.
* Overhaul Makefile.
commit d95988c2fc7f920b3d6ec2f28166f06ec56be255
Author: Milan Straka <[email protected]>
Date: Wed Mar 14 18:30:43 2012 +0100
Mark Data.Map.(!) as INLINABLE instead of INLINE.
This should have been done in commit 3f798e33. As mentioned in the
commit log, the chain
m ! k = find k m
{-# INLINE (!) #-}
find k m = ...
{-# INLINABLE find #-}
results in find not being specialized at the call site of (!).
commit d4e8b5bd70f87af4463410df3aade72d42d675e0
Author: Paolo Capriotti <[email protected]>
Date: Tue Mar 6 10:57:33 2012 +0000
Update .gitignore.
commit 67b4a057d1e6cfb3cd8f9b1d0f02b71b9302ce31
Author: Milan Straka <[email protected]>
Date: Sun Mar 4 19:22:47 2012 +0100
Improve {Map,IntMap}.fold* tests.
commit 68cc2e86ecc6d57943906a96d99ce2be3958d60f
Author: Milan Straka <[email protected]>
Date: Sun Mar 4 18:54:28 2012 +0100
Fix Data.Sequence warnings.
As GHC HEAD found out, methods deep, node2, node3 were both
INLINE and SPECIALIZE. Make them INLINE only.
Also the -Wwarn option can be removed.
commit 0c5e71cd7d0a76d09dcd6ba3d95c468d70d6d6a9
Author: Milan Straka <[email protected]>
Date: Sun Mar 4 16:29:42 2012 +0100
Improve list fusion.
* Allow fusable methods to be converted back to the original call when
no fusion happens. For that, foldlFB and foldrFB are used, inspired by
mapFB from Prelude.
* Remove RULES for aliases like toList, assocs, elems, just INLINE them.
commit a7d02d55385798a872daf6340fc29c762550d9ac
Author: Milan Straka <[email protected]>
Date: Sun Mar 4 16:26:38 2012 +0100
Improve Int{Set,Map}.fold*.
In the fold definitions, do not call go if the Bin constructor was
matched during the test for negative numbers. Instead, manually inline
that branch of go.
Otherwise GHC optimizer does this for us -- it creates local definition
of that branch of go and calls it. On my machine, it causes >200B growth
of object file, for every fold.
commit c0e28dc571cc0a4bcfab6fd81458758e6061703b
Author: Milan Straka <[email protected]>
Date: Sun Mar 4 16:24:52 2012 +0100
Improve Int{Map,Set}.fold*.
Improve Int{Map,Set}.fold* defitions to be inlinable with
two arguments only.
Otherwise GHC inlined toAscList, toDescList _and after that_ inlined
the fold, resulting in useless code growth.
commit 5d742ef1e4a26ae1c8c9bfa5b2c76031108dc9fb
Author: Milan Straka <[email protected]>
Date: Sun Mar 4 16:23:11 2012 +0100
Improve IntMap.fold*.
Improve IntMap.fold* not to do two checks for negative numbers
-- both prefix and mask were tested. Mask tests are enough.
commit 0aaac529f4c37b88180e6f0e6b8fbc160d09ebc2
Author: Milan Straka <[email protected]>
Date: Sat Mar 3 11:28:18 2012 +0100
Improve {Map,IntMap}.intersection* and its tests.
* Add tests for intersectionWith*.
* Add specific Map.intersection implementation instead of using
Map.intersectionWithKey.
* Refactor Map.intersectionWithKey implementatioin.
commit 69ae2392c426412f58067e91c949d3faed69a619
Author: Milan Straka <[email protected]>
Date: Mon Dec 12 13:08:36 2011 +0100
Add toDescList.
Add toDescList to IntMap, Set and IntSet. Also add
corresponding fusion RULES and tests.
The function is added as community was opposed to removing
toDescList from Map.
commit 079c641cd2a250f77aeed9978b39e4996caddadf
Author: Milan Straka <[email protected]>
Date: Mon Dec 12 12:12:42 2011 +0100
Improve formatting of oneliners.
commit eaa4d342b0510591a2a473aaa54aa8b73dfd744d
Author: Milan Straka <[email protected]>
Date: Wed Dec 7 20:47:48 2011 +0100
Improve tests.
* Test IntMap.mapKeys, mapKeysWith, mapKeysMonotonic, which were just
added.
* Unify map-properties and intmap-properties as possible, by renaming
methods and changing comments, so that they are the same in both.
commit 4ee54fe619c5aba38f4ca3a38a4fc793ce1c759a
Author: Milan Straka <[email protected]>
Date: Wed Dec 7 20:42:10 2011 +0100
Add IntMap.mapKeys* methods.
Add IntMap.mapKeys, mapKeysWith, mapKeysMonotonic.
These functions are present in the Map module and we want IntMap
to be a replacement of Map Int.
The IntMap.mapKeysMonotonic is not as efficient as Map.mapKeysMonotonic
because of the IntMap representation -- the trie structure changes
wildly when the keys changes, even if the ordering of keys is not
altered.
Also, some time complexities were corrected.
commit 7afa9c0b606770927d81a9283885c637fed9c581
Author: Milan Straka <[email protected]>
Date: Wed Dec 7 20:38:57 2011 +0100
Improve performance of Map.mapKeys[With].
We can manually fuse
List.map fFirst . toList
where fFirst (a, b) = (f a, b)
using the right fold as
foldrWithKey (\k x xs -> (f k, x) : xs) []
commit b53359b62f0a182ff4ee33d1173190ac8e3c9c9e
Author: Milan Straka <[email protected]>
Date: Wed Dec 7 20:05:36 2011 +0100
Remove unnecessary methods from Data.Map.Strict.
Remove implementations of mapKeys and mapKeysMonotonic
from Data.Map.Strict module. These methods modify keys only
and even Data.Map.Lazy are strict in keys.
commit 4c0a00252dea5a3eecfddda6cf0bd8d93f2d9561
Author: Milan Straka <[email protected]>
Date: Wed Dec 7 19:54:43 2011 +0100
Generalize IntMap.update{Min,Max}[WithKey].
Previously these methods were given an argument of type
[Key ->] a -> a
Now they are given an argument of type
[Key ->] a -> Maybe a
That makes them compatible with Map counterparts.
commit 0bead5148215b68993952d9173983cdc83135e1a
Author: Milan Straka <[email protected]>
Date: Mon Dec 5 22:33:18 2011 +0100
Unify IntMap.deleteFind{Min,Max} with the Map ...
... counterparts.
The type signature has changed from
IntMap.deleteFind{Min,Max} :: IntMap a -> (a, IntMap a)
to
IntMap.deleteFind{Min,Max} :: IntMap a -> ((Key, a), IntMap a)
.
commit f461aea96e8294a93264fcd09152f2ebef1cd531
Author: Milan Straka <[email protected]>
Date: Mon Dec 5 22:14:46 2011 +0100
Int{Set.Map}.delete{Min,Max} doesn't fail on empty.
Make Int{Map,Set}.delete{Min,Max} behave like {Map,Set}.delete{Min,Max}.
* Old behaviour: Int{Set,Map}.delete{Min,Max} empty ==> error
* New behaviour: Int{Set,Map}.delete{Min,Max} empty == empty
commit 189b16ea02ce82a39f7a572da08b883f5f3c1aad
Author: Milan Straka <[email protected]>
Date: Fri Mar 2 17:48:44 2012 +0100
Disable ropt_plain_output.
The ropt_plain_output was used to disables ansi sequences in the test
log. But it works only for test-framework < 0.5.
In test-framework >= 0.5, ropt_plain_output no longer exists. The line
"ropt_color_mode = Just ColorNever" can be used, but test-framework >= 0.5
detects it is not writing to the terminal and disables ansi sequences by
itself.
It is difficult to compile ropt_plain_output conditionally for
test-framework < 0.5 only (MIN_VERSION_* macros are not defined for
dependencies of tests, conditions in cabal tests do not work for
ghc-7.0). We therefore do not set ropt_plain_output and live with ansi
sequences in test logs produces by test-framework < 0.5.
_______________________________________________
Cvs-ghc mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/cvs-ghc
