Ticket #4887: mapops-benchmark.dpatch

File mapops-benchmark.dpatch, 36.6 KB (added by tibbe, 3 years ago)

Changed benchmarks to use MapOps?

Line 
12 patches for repository /Users/tibell/src/containers/master:
2
3Fri Jan  7 18:12:08 CET 2011  Ross Paterson <ross@soi.city.ac.uk>
4  * add a Location interface for element-wise operations
5 
6  This is a variant of a suggestion by apfelmus:
7 
8  http://www.haskell.org/pipermail/libraries/2010-September/014510.html
9 
10  To avoid proliferation of variants of element-wise operations, the idea
11  is to split these operations into two phases mediated by a new Location
12  type, so that users can do whatever they like between these phases.
13
14Wed Jan 12 22:45:11 CET 2011  Johan Tibell <johan.tibell@gmail.com>
15  * Modified benchmark to use MapOps
16 
17  This allows us to test the performance of e.g. insertWith', when defined
18  in terms of 'search'.
19
20New patches:
21
22[add a Location interface for element-wise operations
23Ross Paterson <ross@soi.city.ac.uk>**20110107171208
24 Ignore-this: eae16f6e0219241daf0b1d6dbc9662a1
25 
26 This is a variant of a suggestion by apfelmus:
27 
28 http://www.haskell.org/pipermail/libraries/2010-September/014510.html
29 
30 To avoid proliferation of variants of element-wise operations, the idea
31 is to split these operations into two phases mediated by a new Location
32 type, so that users can do whatever they like between these phases.
33] {
34hunk ./Data/Map.hs 65
35             -- * Operators
36             , (!), (\\)
37 
38+            -- * Locations
39+            , Location
40+            -- ** Components
41+            , key
42+            , before
43+            , after
44+            -- ** Locations in maps
45+            , search
46+            , index
47+            , minLocation
48+            , maxLocation
49+            -- ** Building maps
50+            , assign
51+            , clear
52+
53             -- * Query
54             , null
55             , size
56hunk ./Data/Map.hs 305
57 
58 #endif
59 
60+{--------------------------------------------------------------------
61+  Map locations
62+--------------------------------------------------------------------}
63+
64+-- | A location represents a map with a \"hole\" at a particular key
65+-- position.
66+--
67+-- Locations are used for element-wise operations on maps (insertion,
68+-- deletion and update) in a two-stage process:
69+--
70+-- (1) A 'Location' (and the value at that position, if any) is obtained
71+--     from a 'Map' by searching or indexing.
72+--
73+-- (2) A new 'Map' is made from a 'Location' by either filling the hole
74+--     with a value ('assign') or erasing it ('clear').
75+
76+data Location k a
77+    = Empty !k !(Path k a)
78+    | Full {-# UNPACK #-} !Size !k !(Path k a) !(Map k a) !(Map k a)
79+
80+data Path k a
81+    = Root
82+    | LeftBin {-# UNPACK #-} !Size !k a !(Path k a) !(Map k a)
83+    | RightBin {-# UNPACK #-} !Size !k a !(Map k a) !(Path k a)
84+
85+-- | /O(log n)/. Search the map for the given key, returning the
86+-- corresponding value (if any) and an updatable location for that key.
87+--
88+-- Properties:
89+--
90+-- @
91+-- case 'search' k m of
92+--     (Nothing, loc) -> 'key' loc == k && 'clear' loc == m
93+--     (Just v,  loc) -> 'key' loc == k && 'assign' v loc == m
94+-- @
95+--
96+-- @'lookup' k m == 'fst' ('search' k m)@
97+
98+search :: Ord k => k -> Map k a -> (Maybe a, Location k a)
99+search k = k `seq` go Root
100+  where
101+    go path Tip = (Nothing, Empty k path)
102+    go path (Bin sx kx x l r) = case compare k kx of
103+       LT -> go (LeftBin sx kx x path r) l
104+       GT -> go (RightBin sx kx x l path) r
105+       EQ -> (Just x, Full sx kx path l r)
106+
107+-- | /O(log n)/. Return the value and an updatable location for the
108+-- /i/th key in the map.  Calls 'error' if /i/ is out of range.
109+--
110+-- Properties:
111+--
112+-- @
113+-- 0 \<= i && i \< 'size' m ==>
114+--     let (v, loc) = 'index' i m in
115+--         'size' ('before' loc) == i && 'assign' v loc == m
116+-- @
117+--
118+-- @'elemAt' i m == let (v, loc) = 'index' i m in ('key' loc, v)@
119+
120+index :: Int -> Map k a -> (a, Location k a)
121+index = go Root
122+  where
123+    STRICT_2_OF_3(go)
124+    go _path _i Tip = error "Map.index: out of range"
125+    go path i (Bin sx kx x l r) = case compare i size_l of
126+        LT -> go (LeftBin sx kx x path r) i l
127+        GT -> go (RightBin sx kx x l path) (i-size_l-1) r
128+        EQ -> (x, Full sx kx path l r)
129+      where size_l = size l
130+
131+-- | /O(log n)/. Return the value and an updatable location for the
132+-- least key in the map, which must be non-empty.
133+--
134+-- Properties:
135+--
136+-- @
137+-- 'size' m > 0 ==>
138+--     let (v, loc) = 'minLocation' i m in
139+--         'size' (`before` loc) == 0 && 'assign' v loc == m
140+-- @
141+--
142+-- @'findMin' m == let (v, loc) = 'minLocation' i m in ('key' loc, v)@
143+
144+minLocation :: Map k a -> (a, Location k a)
145+minLocation = go Root
146+  where
147+    go _path Tip = error "Map.least: empty map"
148+    go path (Bin sx kx x Tip r) = (x, Full sx kx path Tip r)
149+    go path (Bin sx kx x l r) = go (LeftBin sx kx x path r) l
150+
151+-- | /O(log n)/. Return the value and an updatable location for the
152+-- greatest key in the map, which must be non-empty.
153+--
154+-- Properties:
155+--
156+-- @
157+-- 'size' m > 0 ==>
158+--     let (v, loc) = 'maxLocation' i m in
159+--         'size' (`after` loc) == 0 && 'assign' v loc == m
160+-- @
161+--
162+-- @'findMax' m == let (v, loc) = 'maxLocation' i m in ('key' loc, v)@
163+
164+maxLocation :: Map k a -> (a, Location k a)
165+maxLocation = go Root
166+  where
167+    go _path Tip = error "Map.greatest: empty map"
168+    go path (Bin sx kx x l Tip) = (x, Full sx kx path l Tip)
169+    go path (Bin sx kx x l r) = go (RightBin sx kx x l path) r
170+
171+-- | /O(1)/. The key marking the position of the \"hole\" in the map.
172+key :: Location k a -> k
173+key (Empty k _path) = k
174+key (Full _sx kx _path _l _r) = kx
175+
176+-- | /O(log n)/. @'before' loc@ is the submap with keys less than @'key' loc@.
177+before :: Ord k => Location k a -> Map k a
178+before (Empty _k path) = buildBefore Tip path
179+before (Full _sx _kx path l _r) = buildBefore l path
180+
181+buildBefore :: Ord k => Map k a -> Path k a -> Map k a
182+buildBefore t Root = t
183+buildBefore t (LeftBin _sx _kx _x path _r) = buildBefore t path
184+buildBefore t (RightBin _sx kx x l path) = buildBefore (join kx x l t) path
185+
186+-- | /O(log n)/. @'after' loc@ is the submap with keys greater than @'key' loc@.
187+after :: Ord k => Location k a -> Map k a
188+after (Empty _k path) = buildAfter Tip path
189+after (Full _sx _kx path l _r) = buildAfter l path
190+
191+buildAfter :: Ord k => Map k a -> Path k a -> Map k a
192+buildAfter t Root = t
193+buildAfter t (LeftBin _sx kx x path r) = buildAfter (join kx x t r) path
194+buildAfter t (RightBin _sx _kx _x _l path) = buildAfter t path
195+
196+-- | /O(log n)/. Return a map obtained by placing the given value
197+-- at the location (replacing an existing value, if any).
198+--
199+-- @'assign' v loc == 'before' loc `union` 'singleton' ('key' loc) v `union` 'after' loc@
200+
201+assign :: a -> Location k a -> Map k a
202+assign x (Empty k path) = rebuildGT (singleton k x) path
203+assign x (Full sx kx path l r) = rebuildEQ (Bin sx kx x l r) path
204+
205+-- | /O(log n)/. Return a map obtained by erasing the location.
206+--
207+-- @'clear' loc == 'before' loc `union` 'after' loc@
208+
209+clear :: Location k a -> Map k a
210+clear (Empty _k path) = rebuildEQ Tip path
211+clear (Full _sx _kx path l r) = rebuildLT (glue l r) path
212+
213+-- Rebuild the tree the same size as it was, so no rebalancing is needed.
214+rebuildEQ :: Map k a -> Path k a -> Map k a
215+rebuildEQ t Root = t
216+rebuildEQ l (LeftBin sx kx x path r) = rebuildEQ (Bin sx kx x l r) path
217+rebuildEQ r (RightBin sx kx x l path) = rebuildEQ (Bin sx kx x l r) path
218+
219+-- Rebuild the tree one entry smaller than it was, rebalancing as we go.
220+rebuildLT :: Map k a -> Path k a -> Map k a
221+rebuildLT t Root = t
222+rebuildLT l (LeftBin _sx kx x path r) = rebuildLT (balanceR kx x l r) path
223+rebuildLT r (RightBin _sx kx x l path) = rebuildLT (balanceL kx x l r) path
224+
225+-- Rebuild the tree one entry larger than it was, rebalancing as we go.
226+rebuildGT :: Map k a -> Path k a -> Map k a
227+rebuildGT t Root = t
228+rebuildGT l (LeftBin _sx kx x path r) = rebuildGT (balanceL kx x l r) path
229+rebuildGT r (RightBin _sx kx x l path) = rebuildGT (balanceR kx x l r) path
230+
231 {--------------------------------------------------------------------
232   Query
233 --------------------------------------------------------------------}
234}
235[Modified benchmark to use MapOps
236Johan Tibell <johan.tibell@gmail.com>**20110112214511
237 Ignore-this: fdce9f67a45fd07e340fee299d3d1f6d
238 
239 This allows us to test the performance of e.g. insertWith', when defined
240 in terms of 'search'.
241] {
242hunk ./benchmarks/Map.hs 14
243 import Data.Maybe (fromMaybe)
244 import Prelude hiding (lookup)
245 
246+import qualified MapOps as MO
247+
248 instance (NFData k, NFData a) => NFData (M.Map k a) where
249     rnf M.Tip = ()
250     rnf (M.Bin _ k a l r) = rnf k `seq` rnf a `seq` rnf l `seq` rnf r
251hunk ./benchmarks/Map.hs 82
252 lookupIndex xs m = foldl' (\n k -> fromMaybe n (M.lookupIndex k m)) 0 xs
253 
254 ins :: [(Int, Int)] -> M.Map Int Int -> M.Map Int Int
255-ins xs m = foldl' (\m (k, v) -> M.insert k v m) m xs
256+ins xs m = foldl' (\m (k, v) -> MO.insert k v m) m xs
257 
258 insWith :: [(Int, Int)] -> M.Map Int Int -> M.Map Int Int
259hunk ./benchmarks/Map.hs 85
260-insWith xs m = foldl' (\m (k, v) -> M.insertWith (+) k v m) m xs
261+insWith xs m = foldl' (\m (k, v) -> MO.insertWith (+) k v m) m xs
262 
263 insWithKey :: [(Int, Int)] -> M.Map Int Int -> M.Map Int Int
264hunk ./benchmarks/Map.hs 88
265-insWithKey xs m = foldl' (\m (k, v) -> M.insertWithKey add3 k v m) m xs
266+insWithKey xs m = foldl' (\m (k, v) -> MO.insertWithKey add3 k v m) m xs
267 
268 insWith' :: [(Int, Int)] -> M.Map Int Int -> M.Map Int Int
269hunk ./benchmarks/Map.hs 91
270-insWith' xs m = foldl' (\m (k, v) -> M.insertWith' (+) k v m) m xs
271+insWith' xs m = foldl' (\m (k, v) -> MO.insertWith' (+) k v m) m xs
272 
273 insWithKey' :: [(Int, Int)] -> M.Map Int Int -> M.Map Int Int
274hunk ./benchmarks/Map.hs 94
275-insWithKey' xs m = foldl' (\m (k, v) -> M.insertWithKey' add3 k v m) m xs
276+insWithKey' xs m = foldl' (\m (k, v) -> MO.insertWithKey' add3 k v m) m xs
277 
278 data PairS a b = PS !a !b
279 
280hunk ./benchmarks/Map.hs 101
281 insLookupWithKey :: [(Int, Int)] -> M.Map Int Int -> (Int, M.Map Int Int)
282 insLookupWithKey xs m = let !(PS a b) = foldl' f (PS 0 m) xs in (a, b)
283   where
284-    f (PS n m) (k, v) = let !(n', m') = M.insertLookupWithKey add3 k v m
285+    f (PS n m) (k, v) = let !(n', m') = MO.insertLookupWithKey add3 k v m
286                         in PS (fromMaybe 0 n' + n) m'
287 
288 insLookupWithKey' :: [(Int, Int)] -> M.Map Int Int -> (Int, M.Map Int Int)
289hunk ./benchmarks/Map.hs 107
290 insLookupWithKey' xs m = let !(PS a b) = foldl' f (PS 0 m) xs in (a, b)
291   where
292-    f (PS n m) (k, v) = let !(n', m') = M.insertLookupWithKey' add3 k v m
293+    f (PS n m) (k, v) = let !(n', m') = MO.insertLookupWithKey' add3 k v m
294                         in PS (fromMaybe 0 n' + n) m'
295 
296 del :: [Int] -> M.Map Int Int -> M.Map Int Int
297hunk ./benchmarks/Map.hs 111
298-del xs m = foldl' (\m k -> M.delete k m) m xs
299+del xs m = foldl' (\m k -> MO.delete k m) m xs
300 
301 upd :: [Int] -> M.Map Int Int -> M.Map Int Int
302hunk ./benchmarks/Map.hs 114
303-upd xs m = foldl' (\m k -> M.update Just k m) m xs
304+upd xs m = foldl' (\m k -> MO.update Just k m) m xs
305 
306 upd' :: [Int] -> M.Map Int Int -> M.Map Int Int
307hunk ./benchmarks/Map.hs 117
308-upd' xs m = foldl' (\m k -> snd $ M.updateLookupWithKey (\_ a -> Just a) k m) m xs
309+upd' xs m = foldl' (\m k -> snd $ MO.updateLookupWithKey (\_ a -> Just a) k m) m xs
310 
311 alt :: [Int] -> M.Map Int Int -> M.Map Int Int
312hunk ./benchmarks/Map.hs 120
313-alt xs m = foldl' (\m k -> M.alter id k m) m xs
314+alt xs m = foldl' (\m k -> MO.alter id k m) m xs
315 
316 maybeDel :: Int -> Maybe Int
317 maybeDel n | n `mod` 3 == 0 = Nothing
318addfile ./benchmarks/MapOps.hs
319hunk ./benchmarks/MapOps.hs 1
320+-- Element-wise operations from Data.Map re-defined using Locations.
321+
322+module MapOps where
323+
324+import Data.Map (Map, empty, null,
325+        Location, key, before, after, assign, clear,
326+        search, index, minLocation, maxLocation)
327+
328+import Prelude hiding (null)
329+
330+-- ** Insertion
331+
332+insert :: Ord k => k -> a -> Map k a -> Map k a
333+insert k v m = assign v (snd (search k m))
334+
335+insertWith :: Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k a
336+insertWith f k v m = case search k m of
337+        (Nothing, loc) -> assign v loc
338+        (Just oldv, loc) -> assign (f v oldv) loc
339+
340+insertWith' :: Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k a
341+insertWith' f k v m = case search k m of
342+        (Nothing, loc) -> assign v loc
343+        (Just oldv, loc) -> flip assign loc $! f v oldv
344+
345+insertWithKey :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> Map k a
346+insertWithKey f k v m = case search k m of
347+        (Nothing, loc) -> assign v loc
348+        (Just oldv, loc) -> assign (f (key loc) v oldv) loc
349+
350+insertWithKey' :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> Map k a
351+insertWithKey' f k v m = case search k m of
352+        (Nothing, loc) -> assign v loc
353+        (Just oldv, loc) -> flip assign loc $! f (key loc) v oldv
354+
355+insertLookupWithKey :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> (Maybe a, Map k a)
356+insertLookupWithKey f k v m = case search k m of
357+        (Nothing, loc) -> (Nothing, assign v loc)
358+        (Just oldv, loc) -> (Just oldv, assign (f (key loc) v oldv) loc)
359+
360+insertLookupWithKey' :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> (Maybe a, Map k a)
361+insertLookupWithKey' f k v m = case search k m of
362+        (Nothing, loc) -> (Nothing, assign v loc)
363+        (Just oldv, loc) -> v' `seq` (Just oldv, assign v' loc)
364+          where v' = f (key loc) v oldv
365+
366+-- ** Delete/Update
367+
368+delete :: Ord k => k -> Map k a -> Map k a
369+delete k m = clear (snd (search k m))
370+
371+adjust :: Ord k => (a -> a) -> k -> Map k a -> Map k a
372+adjust f k m = case search k m of
373+        (Nothing, _) -> m
374+        (Just v, loc) -> assign (f v) loc
375+
376+adjustWithKey :: Ord k => (k -> a -> a) -> k -> Map k a -> Map k a
377+adjustWithKey f k m = case search k m of
378+        (Nothing, _) -> m
379+        (Just v, loc) -> assign (f (key loc) v) loc
380+
381+update :: Ord k => (a -> Maybe a) -> k -> Map k a -> Map k a
382+update f k m = case search k m of
383+        (Nothing, _) -> m
384+        (Just v, loc) -> maybeAssign (f v) loc
385+
386+updateWithKey :: Ord k => (k -> a -> Maybe a) -> k -> Map k a -> Map k a
387+updateWithKey f k m = case search k m of
388+        (Nothing, _) -> m
389+        (Just v, loc) -> maybeAssign (f (key loc) v) loc
390+
391+updateLookupWithKey :: Ord k => (k -> a -> Maybe a) -> k -> Map k a -> (Maybe a, Map k a)
392+updateLookupWithKey f k m = case search k m of
393+        (Nothing, _) -> (Nothing, m)
394+        (Just v, loc) -> (Just v, maybeAssign (f (key loc) v) loc)
395+
396+alter :: Ord k => (Maybe a -> Maybe a) -> k -> Map k a -> Map k a
397+alter f k m = case search k m of
398+        (v, loc) -> maybeAssign (f v) loc
399+
400+-- * Filter
401+
402+split :: Ord k => k -> Map k a -> (Map k a, Map k a)
403+split k m = case search k m of
404+        (_, loc) -> (before loc, after loc)
405+
406+splitLookup :: Ord k => k -> Map k a -> (Map k a, Maybe a, Map k a)
407+splitLookup k m = case search k m of
408+        (res, loc) -> (before loc, res, after loc)
409+
410+-- * Indexed
411+
412+updateAt :: (k -> a -> Maybe a) -> Int -> Map k a -> Map k a
413+updateAt f i m = case index i m of
414+        (v, loc) -> maybeAssign (f (key loc) v) loc
415+
416+deleteAt :: Int -> Map k a -> Map k a
417+deleteAt i m = clear (snd (index i m))
418+
419+-- * Min/Max
420+
421+deleteMin :: Map k a -> Map k a
422+deleteMin m
423+  | null m = empty
424+  | otherwise = clear (snd (minLocation m))
425+
426+deleteMax :: Map k a -> Map k a
427+deleteMax m
428+  | null m = empty
429+  | otherwise = clear (snd (maxLocation m))
430+
431+deleteFindMin :: Map k a -> ((k, a), Map k a)
432+deleteFindMin m
433+  | null m = (error "Map.deleteFindMin: empty map", m)
434+  | otherwise = case minLocation m of
435+        (x, loc) -> ((key loc, x), clear loc)
436+
437+deleteFindMax :: Map k a -> ((k, a), Map k a)
438+deleteFindMax m
439+  | null m = (error "Map.deleteFindMax: empty map", m)
440+  | otherwise = case maxLocation m of
441+        (x, loc) -> ((key loc, x), clear loc)
442+
443+updateMin :: (a -> Maybe a) -> Map k a -> Map k a
444+updateMin f m
445+  | null m = m
446+  | otherwise = case minLocation m of
447+        (x, loc) -> maybeAssign (f x) loc
448+
449+updateMax :: (a -> Maybe a) -> Map k a -> Map k a
450+updateMax f m
451+  | null m = m
452+  | otherwise = case maxLocation m of
453+        (x, loc) -> maybeAssign (f x) loc
454+
455+updateMinWithKey :: (k -> a -> Maybe a) -> Map k a -> Map k a
456+updateMinWithKey f m
457+  | null m = m
458+  | otherwise = case minLocation m of
459+        (x, loc) -> maybeAssign (f (key loc) x) loc
460+
461+updateMaxWithKey :: (k -> a -> Maybe a) -> Map k a -> Map k a
462+updateMaxWithKey f m
463+  | null m = m
464+  | otherwise = case maxLocation m of
465+        (x, loc) -> maybeAssign (f (key loc) x) loc
466+
467+minView :: Map k a -> Maybe (a, Map k a)
468+minView m
469+  | null m = Nothing
470+  | otherwise = case minLocation m of
471+        (x, loc) -> Just (x, clear loc)
472+
473+maxView :: Map k a -> Maybe (a, Map k a)
474+maxView m
475+  | null m = Nothing
476+  | otherwise = case maxLocation m of
477+        (x, loc) -> Just (x, clear loc)
478+
479+minViewWithKey :: Map k a -> Maybe ((k, a), Map k a)
480+minViewWithKey m
481+  | null m = Nothing
482+  | otherwise = case minLocation m of
483+        (x, loc) -> Just ((key loc, x), clear loc)
484+
485+maxViewWithKey :: Map k a -> Maybe ((k, a), Map k a)
486+maxViewWithKey m
487+  | null m = Nothing
488+  | otherwise = case maxLocation m of
489+        (x, loc) -> Just ((key loc, x), clear loc)
490+
491+-- utility
492+
493+maybeAssign :: Maybe a -> Location k a -> Map k a
494+maybeAssign = maybe clear assign
495}
496
497Context:
498
499[Fixed space leak in lookupIndex
500Johan Tibell <johan.tibell@gmail.com>**20110109113222
501 Ignore-this: 4fcd3af4b613a1cdfd306bb9708a5eaa
502]
503[Rollback "hoist constant parameter"
504Johan Tibell <johan.tibell@gmail.com>**20110109112457
505 Ignore-this: ecb77a93588ca5743273cf777ce73826
506 
507 SAT-ing the key causes an extra closure to be allocated.
508 
509 rolling back:
510 
511 Fri Jan  7 16:50:12 CET 2011  Ross Paterson <ross@soi.city.ac.uk>
512   * hoist constant parameter
513 
514     M ./Data/Map.hs -8 +7
515]
516[hoist constant parameter
517Ross Paterson <ross@soi.city.ac.uk>**20110107155012
518 Ignore-this: 1061fdf82eb91cad409ccea022610856
519]
520[fix typos in comments
521Ross Paterson <ross@soi.city.ac.uk>**20101215172553
522 Ignore-this: f66f871ce348a41bc1598bc2b5e40943
523]
524[whitespace changes and a little re-ordering to make the export lists match
525Ross Paterson <ross@soi.city.ac.uk>**20101215170649
526 Ignore-this: 3bf7b6d824ea1c25ed92bbe3ca826efe
527]
528[whitespace changes and a little re-ordering to make the export lists match
529Ross Paterson <ross@soi.city.ac.uk>**20101215162127
530 Ignore-this: 7f11aef6c6c8330bb93b6571589e18af
531]
532[change Int to Key (type synonym) in 3 places for consistency
533Ross Paterson <ross@soi.city.ac.uk>**20101215150459
534 Ignore-this: 6da6f8629bb0718e2394a85ce0944d7f
535]
536[use Applicative form in Arbitrary instances
537Ross Paterson <ross@soi.city.ac.uk>**20101213040129
538 Ignore-this: 335e6eac24563baef481fdc689f369dc
539 (these are ifdef'ed out by default)
540]
541[fix comment for unfoldl
542Ross Paterson <ross@soi.city.ac.uk>**20101213040022
543 Ignore-this: c4bac18538933b981ed2875595f98196
544]
545[make local binding monomorphic without using scoped type variables
546Ross Paterson <ross@soi.city.ac.uk>**20101213035831
547 Ignore-this: 52b7f5ed7cb7c6ef0eda6caa39e4713f
548]
549[Always inline foldrWithKey' and foldlWithKey' from Data.Map
550Johan Tibell <johan.tibell@gmail.com>**20101201110527
551 Ignore-this: a84198febd304659ff029c3424855be3
552 
553 Inlining makes it possible to replace an indirect call to an unknown
554 function with a call to a known function at the call site.
555]
556[Tweak insertWith' and insertWithKey' to better match the non-' versions
557Ian Lynagh <igloo@earth.li>**20101128175028
558 Ignore-this: 41b50b13b1a94ae56bad8d381c696d04
559 They now are not marked inlinable, force the key, and are exported.
560]
561[Explain INLINEs in IntMap and IntSet.
562Milan Straka <fox@ucw.cz>**20101104224507
563 Ignore-this: 322a22056e9aa5d4e5a9f2caa6542017
564]
565[Fix warnings.
566Milan Straka <fox@ucw.cz>**20101104223950
567 Ignore-this: 19460b7cab4554fef3b637ebb36addd1
568 
569 Just trivial renames of shadows variables.
570]
571[Explain the nomatch clause in IntSet.hs
572Milan Straka <fox@ucw.cz>**20101104221451
573 Ignore-this: 2f90d0037027e77cffff30cf21729845
574]
575[Rename STRICTxy to STRICT_x_OF_y.
576Milan Straka <fox@ucw.cz>**20101104220917
577 Ignore-this: fb12cee5518d1a8844ee44273330fa57
578 
579 Also explain why bang patterns are not used.
580]
581[Settle performance issues in Map and Set.
582Milan Straka <fox@ucw.cz>**20101031082146
583 Ignore-this: 9a4c70d5f9a5884c7ff8f714ae4ff1e4
584 
585 Explain the INLINE/INLINABLE in the Map and Set sources.
586 
587 Use 'go' only for functions that can be INLINE.
588]
589[Settle performance issues in IntMap and IntSet.
590Milan Straka <fox@ucw.cz>**20101029231653
591 Ignore-this: c1234a5113da14178a2394976e91b786
592 
593 The worker-wrapper transformation is removed from
594 all functions but lookup and member. This is the
595 only place where it causes benefits -- a 10% to
596 15% speedup. It increases memory allocation
597 slightly (0-5%), but the effect on GHC is really
598 minor.
599 
600 Also INLINE/INLINABLE hints are not really needed,
601 GHC figures it all by itself. The explicit INLINE
602 were left on internal functions that are crutial
603 to INLINE because of performance.
604]
605[Make foldlStrict semantics to match foldl'.
606Milan Straka <fox@ucw.cz>**20101022100939
607 Ignore-this: 3790a5a47e4ff7b55c005a8c95e5890f
608]
609[Remove INLINABLE in IntMap and IntSet.hs.
610Milan Straka <fox@ucw.cz>**20101022091744
611 Ignore-this: 4f532887bf54444989cc66d6546f1c89
612 
613 It makes no sense, as the calls are already specialized
614 for Int keys. Benchmarks actually show small slowdown.
615]
616[Do not pass f explicitely for fold.
617Milan Straka <fox@ucw.cz>**20101019202043
618 Ignore-this: bb0a5e758ebfebbdf8160be4317898e9
619 
620 Benchmarks shows this is a huge win (100% for (:) being
621 the function, 1000% for (+) being the function).
622]
623[Mark fold explicitely as INLINE.
624Milan Straka <fox@ucw.cz>**20101016222150
625 Ignore-this: b72855a0af39e57b1862908717fc14fc
626 
627 The INLINABLE does not work well in this case. Benchmarks
628 show memory savings (due to unboxing) and nearly no GHC binary
629 size increase.
630]
631[Changing INLINE pragmas.
632Milan Straka <fox@ucw.cz>**20101016215959
633 Ignore-this: 933327354749d18e4617280fde55cce0
634 
635 The internal functions that need to be inlined are marked INLINE
636 (bit fiddling in IntMap/IntSet, empty, singleton, bin).
637 
638 Aslo if INLINABLE is available, use it for all exported functions.
639 The functions like insert that were INLINE because of specialization
640 issues are now INLINE only in the case of INLINABLE absence.
641]
642[Whitespace changes only.
643Milan Straka <fox@ucw.cz>**20101016202831
644 Ignore-this: 8850e09fb49937b54da6585d01aade9a
645]
646[Correct a typo in macro name.
647Milan Straka <fox@ucw.cz>**20101016202641
648 Ignore-this: 356621b0ca954f73d543fc33d43383b2
649]
650[Change the worker/wrapper to explicitly pass arguments.
651Milan Straka <fox@ucw.cz>**20101016195757
652 Ignore-this: 7f4a2180a263ee15cbb73c60b2d8cc46
653 
654 As the benchmarking showed, it is not a good idea to create
655 closures in the worker/wrapper transformation, as the captured
656 arguments of the enclosing function have to be allocated on the
657 heap. It is better to explicitly pass the arguments on the stack.
658 This saves memory and add no time penalty if the arguments are
659 the first arguments of recursive function (GHC refrains from
660 needless copying).
661 
662 The worker is often strict in some arguments. I did not want
663 to use BangPatterns, so I used macros to indicate strictness.
664 If majority thinks BangPatters are fine, I will gladly change it.
665]
666[Add foldlWithKey' and foldrWithKey' to Data.Map
667Johan Tibell <johan.tibell@gmail.com>**20101103132836
668 Ignore-this: d2ac0f0a50842ec5a007b9ad11ce63d0
669]
670[Add strict versions of insertWith and insertWithKey to IntMap
671Johan Tibell <johan.tibell@gmail.com>**20101030135122
672 Ignore-this: 5472c9be565e75672140d243ef0211f2
673]
674[Fix warnings in Data.Map and Data.Set.
675Milan Straka <fox@ucw.cz>**20100924154946
676 Ignore-this: cb2c0a8ecf0a57acc5941ba841aa7c40
677 
678 Only trivial changes.
679]
680[Finish the started worker/wrapper transformation.
681Milan Straka <fox@ucw.cz>**20100924153353
682 Ignore-this: baeb24573242beb56c3bbe7ca67f5ff7
683 
684 Some methods (insert, lookup) were not modified as the rest
685 (like insertWith, delete, ...). Also the `seq` were missing
686 sometimes.
687]
688[Merge all the OPTIONS and LANGUAGE module pragmas.
689Milan Straka <fox@ucw.cz>**20100924152642
690 Ignore-this: 86067abf13f0501f29c13ec7c877533c
691]
692[Remove most INLINE from Map, Set, IntMap and IntSet.
693Milan Straka <fox@ucw.cz>**20100924152008
694 Ignore-this: c88c4ede21c06bfda20af131c232a720
695 
696 Because of a code bloat the INLINEs cause, remove most of
697 them. The only INLINEs left are the following:
698 - only in Set and Map, because in IntMap and IntSet the specialization
699   does not help
700 - only on functions which need Ord
701 - only on 'small' functions, namely member, notMember, lookup*,
702   insert*, delete*, adjust*, alter*, update*
703 
704 All other functions of Map, Set, IntMap and IntSet are marked INLINABLE,
705 even if they are recursive.
706 
707 The INLINEs left are only a short-term solution. In the long run the
708 auto-specialization of INLINABLE methods seems a good way (maybe
709 SPECIALIZABLE).
710]
711[Comment tests and benchmarks on foldlWithKey' which
712Milan Straka <fox@ucw.cz>**20100924110705
713 Ignore-this: 71b988389e6ae9a78ea3b0e20156ca2f
714 was commented recently by Ian Lynagh.
715]
716[Worker/wrapper transformation for Data.IntSet.
717Milan Straka <fox@ucw.cz>**20100923125604
718 Ignore-this: b0228582818f7bfb690d0853022a7809
719]
720[Compile only the benchmark source, not the Data/*.hs.
721Milan Straka <fox@ucw.cz>**20100921115821
722 Ignore-this: f94d9e3ffe126cd057d23490c973a4e9
723]
724[Add criterion-based benchmark for IntSet.hs.
725Milan Straka <fox@ucw.cz>**20100921103225
726 Ignore-this: 3d31a820830c7382748626bc9a1ba54
727 
728 The benchmark is nearly identical copy of Set.hs benchmark.
729]
730[Add a testsuite for Data.IntSet.
731Milan Straka <fox@ucw.cz>**20100921102802
732 Ignore-this: e55484ee185e71915452bdf2a7b2a2b3
733]
734[Further improve Data.Set balance function.
735Milan Straka <fox@ucw.cz>**20100921091828
736 Ignore-this: f23be37859224e9bbe919a3c0a71fdc6
737 
738 As suggested by Kazu Yamamoto, we split balance to balanceL and
739 balanceR, which handle only one-sided inbalance, but need fewer
740 tests than balance.
741 
742 As nearly all functions modifying the structure use balance, this
743 results in speedup of many functions. On my 32-bit GHC 6.12.1,
744 11% speedup for insert, 12% speedup for delete.
745]
746[Further improve Data.Map balance function.
747Milan Straka <fox@ucw.cz>**20100921091547
748 Ignore-this: 8abfd027142a5183b2b5282e96ccb414
749 
750 As suggested by Kazu Yamamoto, we split balance to balanceL and
751 balanceR, which handle only one-sided inbalance, but need fewer
752 tests than balance.
753 
754 As nearly all functions modifying the structure use balance, this
755 results in speedup of many functions. On my 32-bit GHC 6.12.1,
756 20% speedup for insert, 7% speedup for delete, 5% speedup for update.
757]
758[Changing delta to 3 in Data.Set.
759Milan Straka <fox@ucw.cz>**20100921090507
760 Ignore-this: a47d0c542ed9cee99ad6b17c52c977a1
761 
762 Only possible values are 3 and 4. The value 3 has much faster inserts,
763 value 4 slightly faster deletes, so choosing 3.
764 
765 Also changed the inequalities to rebalance only when one subtree
766 is _strictly_ larger than delta * the other one, to mimic the behaviour
767 from the proof (both from the Adams' and from the one to come).
768]
769[Changing delta to 3 in Data.Map.
770Milan Straka <fox@ucw.cz>**20100921090358
771 Ignore-this: 85f733f836b65b2b1038383ddb92e8e1
772 
773 Only possible values are 3 and 4. The value 3 has much faster inserts,
774 value 4 slightly faster deletes, so choosing 3.
775 
776 Also changed the inequalities to rebalance only when one subtree
777 is _strictly_ larger than delta * the other one, to mimic the behaviour
778 from the proof (both from the Adams' and from the one to come).
779]
780[Correct Data.Set Arbitrary instance never to return unbalanced trees.
781Milan Straka <fox@ucw.cz>**20100914150442
782 Ignore-this: b5c70fa98a56f225b8eb5faf420677b0
783 
784 The previous instance sometimes returned unbalanced trees,
785 which broke the tests.
786 
787 Also the new instance mimics Data.Map instance more closely in the shape
788 of the generated trees.
789]
790[Correct Data.Map Arbitrary instance never to return unbalanced trees.
791Milan Straka <fox@ucw.cz>**20100914145841
792 Ignore-this: 114bbcc63acdb16b77140ea56aeb0a95
793 
794 The previous instance sometimes returned unbalanced trees,
795 which broke the tests.
796]
797[Improve Data.Set benchmark.
798Milan Straka <fox@ucw.cz>**20100914142010
799 Ignore-this: 9b878ae3aa5a43ef083abfd7f9b22513
800 
801 Add union, difference and intersection to Data.Set benchmark.
802]
803[Improve benchmark infrastructure and Data.Map benchmark.
804Milan Straka <fox@ucw.cz>**20100914141707
805 Ignore-this: 67e8dafcb4abcb9c726b9b29c7c320fd
806 
807 Renamed Benchmarks.hs to Map.hs, as it only benchmarks Data.Map.
808 Improve the Makefile to work with multiple benchmarks.
809 Add union, difference and intersection to Data.Map benchmark.
810]
811[Improve the performance of Data.Set balance function.
812Milan Straka <fox@ucw.cz>**20100914140417
813 Ignore-this: 577c511c219695b8d483af546c7387e8
814 
815 The balance function is now one monolithic function, which allows
816 to perform all pattern-matches only once.
817 
818 Nearly all functions modifying Data.Map use balance.
819 The improvements are 12% for insert, 14% for delete (GHC 6.12.1).
820]
821[Improve the performance of Data.Map balance function.
822Milan Straka <fox@ucw.cz>**20100914140217
823 Ignore-this: 951181e035fcac90674dff3300350a1
824 
825 The balance function is now one monolithic function, which allows
826 to perform all pattern-matches only once.
827 
828 Nearly all functions modifying Data.Map use balance.
829 The improvements are 7-11% for various insert*, delete*, alter,
830 update or intersection functions (GHC 6.12.1).
831]
832[Improve performance of Data.Set union and difference operations.
833Milan Straka <fox@ucw.cz>**20100914135725
834 Ignore-this: 6dc4a186ea060b9cdb9e783db71ca280
835 
836 Use datatype storing evaluated bound instead of high-order functions.
837 The improvements are over 25% for both union and difference (GHC 6.12.1).
838]
839[Improve performance of Data.Map union* and difference* operations.
840Milan Straka <fox@ucw.cz>**20100914134614
841 Ignore-this: 35b23a40ef33e9fa14eb81fdee4b152d
842 
843 Use datatype storing evaluated bound instead of high-order functions.
844 The improvements are 22% for union and 20% for difference (GHC 6.12.1).
845]
846[Make the Set store the elements evaluated (bang added).
847Milan Straka <fox@ucw.cz>**20100913165132
848 Ignore-this: b3f230db5bf30d93d3fddf2c81c5f3b4
849]
850[Improved performance of Data.Set
851Johan Tibell <johan.tibell@gmail.com>**20100831124352
852 Ignore-this: 38a304a0408d29a2956aa9a1fc0ce755
853 
854 Performance improvements are due to manually applying the
855 worker/wrapper transformation and strictifying the keys.
856 
857 Average speed-up is 32% on a 2GHz Core 2 Duo on OS X 10.5.8
858]
859[Added benchmarks for Data.Set
860Johan Tibell <johan.tibell@gmail.com>**20100831124225
861 Ignore-this: fcacf88761034b8c534d936f0b336cc0
862]
863[Added a test suite for Data.Set
864Johan Tibell <johan.tibell@gmail.com>**20100831124030
865 Ignore-this: f430dc302c0fcb8b5d62db2272a1d6f7
866 
867 Expression coverage: 74%
868]
869[Remove use of lambdas with irrefutable patterns
870simonpj@microsoft.com**20100923120838
871 Ignore-this: c36e90a0258c0d5262684c585c321419
872]
873[Revert the recent contentious changes
874Ian Lynagh <igloo@earth.li>**20100915135103
875 Ignore-this: fe4f71ff1ade51c11421dc9974aa0fda
876 These will probably be tidied up and reinstated later, but this gets
877 the package back to a releasable state.
878]
879[fix warnings
880Simon Marlow <marlowsd@gmail.com>**20100831114555
881 Ignore-this: 53df71bc054a779b8ad2dad89c09e02d
882]
883[Missing MagicHash for IntSet
884Don Stewart <dons@galois.com>**20100831093446
885 Ignore-this: d075f760adb9a2aa0ee04676e38a07cc
886]
887[Performance improvements for Data.IntMap (worker/wrapper and inlining)
888Don Stewart <dons@galois.com>**20100831093316
889 Ignore-this: 206036448558d270f0eb85ef4cd55368
890]
891[Add criterion-based benchmarking for IntMap
892Don Stewart <dons@galois.com>**20100831093240
893 Ignore-this: d7d85b9afb513532cc30f5b51a3f825e
894]
895[Add comprehensive testsuite for IntMap
896Don Stewart <dons@galois.com>**20100831093202
897 Ignore-this: d455fedbc615e5b63ac488e605550557
898]
899[-O2 -fregs-graph is a uniform 10% improvements for IntMap
900Don Stewart <dons@galois.com>**20100831092956
901 Ignore-this: 2372cf4be945fe7939d0af94e32c567f
902]
903[Missed base case for updateAt worker. Spotted by Jan-Willem Maessen
904Don Stewart <dons@galois.com>**20100829163329
905 Ignore-this: b8daf1c55c163c16f50c3b54cca2dba1
906]
907[Major bump (new functions, clarified strictness properties, vastly better performance)
908Don Stewart <dons@galois.com>**20100829122628
909 Ignore-this: 9bfbc58ecaa24a86be37b8c4cb043457
910]
911[Add two new functions: foldlWithKey' and insertLookupWithKey'
912Don Stewart <dons@galois.com>**20100829122147
913 Ignore-this: a2f112653ba38737fe1b38609e06c314
914 
915 These two functions use strict accumulators, compared to their existing
916 counterparts (which are lazy left folds, that appear not to be useful).
917 Performance is significantly better.
918 
919]
920[Performance improvements to Data.Map
921Don Stewart <dons@galois.com>**20100829120245
922 Ignore-this: b4830cddfa6d62e4883f4e0f58ac4e57
923 
924 Applied several standard transformations to improve the performance of
925 code:
926 
927     * Worker/wrapper of all recursive functions with constant arguments
928     * Inlining of all (non-recursive) wrappers
929     * Consistent use of strict keys
930 
931 Average performance improvements across common API (with GHC 6.12.3):
932 
933     * Linux / x86_64 / 2.6Ghz i7        : 48%
934     * Mac OSX 10.5 / x86 / 2 Ghz Xeon   : 36%
935 
936 Graphs and raw data: http://is.gd/eJHIE
937 
938 This patch is (mostly) orthogonal to the algorithmic changes suggested
939 by Milan Straka in his HW 2010 paper:
940 
941     http://research.microsoft.com/~simonpj/papers/containers/containers.pdf
942 
943 Those changes could be added separately, for some additional improvments.
944 
945 Work carried out over 28/29th August, 2010 in Utrecht, NL, by Johan Tibell
946 and Don Stewart.
947 
948]
949[Add a criterion-based benchmark suite for Data.Map
950Don Stewart <dons@galois.com>**20100829114611
951 Ignore-this: ec61668f5bcb78bd15b72e2728c01c19
952 
953 This adds a criterion-based micro-benchmarking suite for Data.Map. It
954 can be used to measure performance improvements for individual top-level
955 functions.
956 
957 Examples here: http://is.gd/eJHIE
958 
959]
960[Add a comprehensive testsuite for Data.Map
961Don Stewart <dons@galois.com>**20100829113545
962 Ignore-this: 891e7fe6bac3523868714ac1ff51c0a3
963 
964 This patch adds a joint quickcheck2 / hunit testsuite, with coverage of
965 91% of top level functions (remaining features are mostly in instances).
966 
967 The coverage data is here:
968     
969     http://code.haskell.org/~dons/tests/containers/hpc_index.html
970 
971 No bugs were found. It includes unit tests for known past bugs
972 (balancing).
973 
974]
975[Oops, get the #ifdef symbol correct.
976Malcolm.Wallace@me.com**20100902081938]
977[Protect a gratuitous GHC-ism with #ifdefs.
978Malcolm.Wallace@me.com**20100902081217]
979[Set Data.Map's delta to 4; fixes #4242
980Ian Lynagh <igloo@earth.li>**20100815131954]
981[Add a test for #4242
982Ian Lynagh <igloo@earth.li>**20100815131856]
983[Add a local type signature
984simonpj@microsoft.com**20100730124447
985 Ignore-this: b581d3f2c80a7a860456d589960f12f2
986]
987[Add type signature in local where clause
988simonpj@microsoft.com**20100727151709
989 Ignore-this: 5929c4156500b25b280eb414b508c508
990]
991[Fix Data.Sequence's breakr, and add a test for it; fixes trac #4157
992Ian Lynagh <igloo@earth.li>**20100704140627]
993[Fix proposal #4109: Make Data.Map.insertWith's strictness consistent
994Ian Lynagh <igloo@earth.li>**20100615133055]
995[Tweak layout to work with the alternative layout rule
996Ian Lynagh <igloo@earth.li>**20091129154519]
997[Disable building Data.Sequence (and dependents) for nhc98.
998Malcolm.Wallace@cs.york.ac.uk**20091124025653
999 There is some subtlety of polymorphically recursive datatypes and
1000 type-class defaulting that nhc98's type system barfs over.
1001]
1002[Fix another instance of non-ghc breakage.
1003Malcolm.Wallace@cs.york.ac.uk**20091123092637]
1004[Add #ifdef around ghc-only (<$) as member of Functor class.
1005Malcolm.Wallace@cs.york.ac.uk**20091123085155]
1006[Fix broken code in non-GHC branch of an ifdef.
1007Malcolm.Wallace@cs.york.ac.uk**20091123084824]
1008[doc bugfix: correct description of index argument
1009Ross Paterson <ross@soi.city.ac.uk>**20091028105532
1010 Ignore-this: 9790e7bf422c4cb528722c03cfa4fed9
1011 
1012 As noted by iaefai on the libraries list.
1013 
1014 Please merge to STABLE.
1015]
1016[Bump version to 0.3.0.0
1017Ian Lynagh <igloo@earth.li>**20090920141847]
1018[update base dependency
1019Ross Paterson <ross@soi.city.ac.uk>**20090916073125
1020 Ignore-this: ad382ffc6c6a18c15364e6c072f19edb
1021 
1022 The package uses mkNoRepType and Data.Functor, which were not in the
1023 stable branch of base-4.
1024]
1025[add fast version of <$ for Seq
1026Ross Paterson <ross@soi.city.ac.uk>**20090916072812
1027 Ignore-this: 5a39a7d31d39760ed589790b1118d240
1028]
1029[new methods for Data.Sequence (proposal #3271)
1030Ross Paterson <ross@soi.city.ac.uk>**20090915173324
1031 Ignore-this: cf17bedd709a6ab3448fd718dcdf62e7
1032 
1033 Adds a lot of new methods to Data.Sequence, mostly paralleling those
1034 in Data.List.  Several of these are significantly faster than versions
1035 implemented with the previous public interface.  In particular, replicate
1036 takes O(log n) time and space instead of O(n).
1037 (by Louis Wasserman)
1038]
1039[Fix "Cabal check" warnings
1040Ian Lynagh <igloo@earth.li>**20090811215900]
1041[TAG 2009-06-25
1042Ian Lynagh <igloo@earth.li>**20090625160202]
1043Patch bundle hash:
1044ffad03dd8b00f2031ce09dcbb2dfd71d97cad94f