Permalink
Commits on May 11, 2012
  1. Merge pull request #11 from thomie/master

    foxik committed May 11, 2012
    Data.Graph: refer to a better version of the King and Launchbury article
Commits on May 3, 2012
  1. Merge changes release by GHC HQ as 0.7.4.1

    tibbe committed May 3, 2012
    Conflicts:
    	containers.cabal
Commits on Apr 30, 2012
  1. Add tests and benchmarks to sdist.

    foxik committed Apr 30, 2012
  2. Add comment to tests/Makefile.

    foxik committed Apr 30, 2012
    Add comment to tests/Makefile that users should use cabal to build and
    run tests.
Commits on Apr 28, 2012
  1. Remove type of local 'go' function in query methods of Set and Map.

    foxik committed Apr 28, 2012
    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.
  2. Define Map.{union,difference,intersection}WithKey using mergeWithKey.

    foxik committed Apr 28, 2012
    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.
  3. Add Map.mergeWithKey.

    foxik committed Apr 28, 2012
Commits on Apr 27, 2012
  1. Remove redundant parenthesis.

    foxik committed Apr 27, 2012
  2. Fix warnings, formatting.

    foxik committed Apr 27, 2012
  3. Improve {Map, Set}.union.

    foxik committed Apr 27, 2012
    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.
  4. Improve {Map, Set}.intersection.

    foxik committed Apr 27, 2012
    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.
  5. Once again revert argument capturing by local 'go' function.

    foxik committed Apr 27, 2012
    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).
  6. Improve heap-allocation in mergeWithKey'.

    foxik committed Apr 27, 2012
    Avoid allocating the closure for local function 'merge'.
Commits on Apr 25, 2012
  1. Add fromSet method.

    foxik committed Apr 25, 2012
    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.
  2. Fix warnings.

    foxik committed Apr 25, 2012
Commits on Apr 24, 2012
  1. Improve manual makefile for tests.

    foxik committed Apr 24, 2012
    Leave dependencies on GHC instead of make.
  2. Improve {Map, IntMap}.keysSet.

    foxik committed Apr 24, 2012
    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.
  3. Factor Data.IntSet into Data.IntSet.Base and Data.IntSet.

    foxik committed Apr 24, 2012
    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.
  4. Factor Data.Set into Data.Set.Base and Data.Set.

    foxik committed Apr 24, 2012
    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.
  5. Add lookupLT, lookupGT, lookupLE, lookupGE methods.

    foxik committed Apr 24, 2012
    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.
  6. On 32-bit architectures, improve highestBitMask.

    foxik committed Apr 24, 2012
    Even on 32-bit architectures, bit shift of size 32 was performed.
Commits on Apr 23, 2012
  1. Change ASCII character for underline from ^ to ~.

    foxik committed Apr 23, 2012
    We use the following:
      -- [Note: Some superimportant message]
      -- ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    Unfortunately, -- ^ is wrongly picked up by Haddock.
    Instead we now use
      -- [Note: Some superimportant message]
      -- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  2. Change INLINE to INLINABLE on methods using Ord.

    foxik committed Apr 23, 2012
    As mentioned previously, INLINE - INLINABLE method chain does not result
    in specialization, it has to be INLINABLE - INLINABLE.
  3. Add benchmark of lookupGE to choose best implementation.

    foxik committed Apr 23, 2012
    Most of the code is by Twan van Laarhoven, thanks.
  4. Fix warnings.

    foxik committed Apr 23, 2012
  5. Move SetOperations benchmark to its own subdirectory.

    foxik committed Apr 23, 2012
    Also improve the infrastructure to handle benchmarks in different
    subdirectories.
Commits on Apr 22, 2012
  1. Manually inline {Map,IntMap}.map.

    foxik committed Apr 22, 2012
  2. Inline {Map,Set}.fold* when 2 arguments are given.

    foxik committed Apr 22, 2012
    Inlining folds when 2 arguments are given is consistent
    with Prelude.foldr and {IntMap,IntSeT}.fold*.
  3. Remove obsolete comment about deleteWith.

    foxik committed Apr 22, 2012
    DeleteWith is no longer method of any collection.
  4. Improve heap-allocation by adding explicit type signatures.

    foxik committed Apr 22, 2012
    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.
Commits on Apr 21, 2012
  1. Improve Map indexing functions.

    foxik committed Apr 21, 2012
    * Manually inline findIndex and deleteAt to avoid allocation.
    
    * Give type to local 'go' function of findIndex and lookupIndex
      to avoid heap allocation.
  2. Improve query functions of Map and Set.

    foxik committed Apr 21, 2012
    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.