Ticket #5034: improve-performance-of-data_graph-_ticket-_5034__.dpatch

File improve-performance-of-data_graph-_ticket-_5034__.dpatch, 22.6 KB (added by michalt, 3 years ago)

Revised patch for Data.Graph.

Line 
11 patch for repository http://darcs.haskell.org/packages/containers:
2
3Mon Mar 21 20:08:57 CET 2011  Michal Terepeta <michal.terepeta@gmail.com>
4  * Improve performance of Data.Graph (ticket #5034).
5
6New patches:
7
8[Improve performance of Data.Graph (ticket #5034).
9Michal Terepeta <michal.terepeta@gmail.com>**20110321190857
10 Ignore-this: f6f046dd6c17496ddba28b3bbb3a271
11] {
12hunk ./Data/Graph.hs 319
13 -- Algorithm 1: depth first search numbering
14 ------------------------------------------------------------
15 
16-preorder            :: Tree a -> [a]
17-preorder (Node a ts) = a : preorderF ts
18+preorder' :: Tree a -> [a] -> [a]
19+preorder' (Node a ts) = (a :) . preorderF' ts
20 
21hunk ./Data/Graph.hs 322
22-preorderF           :: Forest a -> [a]
23-preorderF ts         = concat (map preorder ts)
24+preorderF' :: Forest a -> [a] -> [a]
25+preorderF' ts = foldr (.) id $ map preorder' ts
26+
27+preorderF :: Forest a -> [a]
28+preorderF ts = preorderF' ts []
29 
30 tabulate        :: Bounds -> [Vertex] -> Table Int
31 tabulate bnds vs = array bnds (zipWith (,) vs [1..])
32hunk ./Data/Graph.hs 338
33 -- Algorithm 2: topological sorting
34 ------------------------------------------------------------
35 
36-postorder :: Tree a -> [a]
37-postorder (Node a ts) = postorderF ts ++ [a]
38+postorder :: Tree a -> [a] -> [a]
39+postorder (Node a ts) = postorderF ts . (a :)
40 
41hunk ./Data/Graph.hs 341
42-postorderF   :: Forest a -> [a]
43-postorderF ts = concat (map postorder ts)
44+postorderF   :: Forest a -> [a] -> [a]
45+postorderF ts = foldr (.) id $ map postorder ts
46 
47hunk ./Data/Graph.hs 344
48-postOrd      :: Graph -> [Vertex]
49-postOrd       = postorderF . dff
50+postOrd :: Graph -> [Vertex]
51+postOrd g = postorderF (dff g) []
52 
53 -- | A topological sort of the graph.
54 -- The order is partially specified by the condition that a vertex /i/
55}
56
57Context:
58
59[spell out fmap definitions instead of using fmapDefault
60Ross Paterson <ross@soi.city.ac.uk>**20110224011407
61 Ignore-this: 1b01d4e4bc397c5c6a1198fab2111573
62]
63[add split/append benchmark for Data.Sequence
64Ross Paterson <ross@soi.city.ac.uk>**20110202011606
65 Ignore-this: 59ceb723663e2021c99bbed46c90db58
66]
67[add -rtsopts (needed to use +RTS with GHC-7.0)
68Ross Paterson <ross@soi.city.ac.uk>**20110202011346
69 Ignore-this: ebbbf7639a3b80a954366ca1b9507568
70]
71[remove __HADDOCK__ ifdefs
72Ross Paterson <ross@soi.city.ac.uk>**20110115121344
73 Ignore-this: 9f638c4f603629645e987188d63585d0
74]
75[tweak indentation (whitespace only)
76Ross Paterson <ross@soi.city.ac.uk>**20110115120510
77 Ignore-this: 439b3001e762c6adad07070897a58d01
78]
79[QuickCheck properties for Data.Sequence
80Ross Paterson <ross@soi.city.ac.uk>**20110115011403
81 Ignore-this: 621e327003e9777fcb874e18598c9903
82]
83[tweak indentation (whitespace only)
84Ross Paterson <ross@soi.city.ac.uk>**20110115010705
85 Ignore-this: 2bf00adf8960a983fa782102680de4b8
86]
87[more fine-grained tests
88Ross Paterson <ross@soi.city.ac.uk>**20110114100642
89 Ignore-this: 23a04888564cdf415e681bdcdb4e1b51
90 
91 Distinguish between whether the key searched for is present or not,
92 and the different uses of update and alter.
93]
94[Fixed space leak in lookupIndex
95Johan Tibell <johan.tibell@gmail.com>**20110109113222
96 Ignore-this: 4fcd3af4b613a1cdfd306bb9708a5eaa
97]
98[Rollback "hoist constant parameter"
99Johan Tibell <johan.tibell@gmail.com>**20110109112457
100 Ignore-this: ecb77a93588ca5743273cf777ce73826
101 
102 SAT-ing the key causes an extra closure to be allocated.
103 
104 rolling back:
105 
106 Fri Jan  7 16:50:12 CET 2011  Ross Paterson <ross@soi.city.ac.uk>
107   * hoist constant parameter
108 
109     M ./Data/Map.hs -8 +7
110]
111[hoist constant parameter
112Ross Paterson <ross@soi.city.ac.uk>**20110107155012
113 Ignore-this: 1061fdf82eb91cad409ccea022610856
114]
115[fix typos in comments
116Ross Paterson <ross@soi.city.ac.uk>**20101215172553
117 Ignore-this: f66f871ce348a41bc1598bc2b5e40943
118]
119[whitespace changes and a little re-ordering to make the export lists match
120Ross Paterson <ross@soi.city.ac.uk>**20101215170649
121 Ignore-this: 3bf7b6d824ea1c25ed92bbe3ca826efe
122]
123[whitespace changes and a little re-ordering to make the export lists match
124Ross Paterson <ross@soi.city.ac.uk>**20101215162127
125 Ignore-this: 7f11aef6c6c8330bb93b6571589e18af
126]
127[change Int to Key (type synonym) in 3 places for consistency
128Ross Paterson <ross@soi.city.ac.uk>**20101215150459
129 Ignore-this: 6da6f8629bb0718e2394a85ce0944d7f
130]
131[use Applicative form in Arbitrary instances
132Ross Paterson <ross@soi.city.ac.uk>**20101213040129
133 Ignore-this: 335e6eac24563baef481fdc689f369dc
134 (these are ifdef'ed out by default)
135]
136[fix comment for unfoldl
137Ross Paterson <ross@soi.city.ac.uk>**20101213040022
138 Ignore-this: c4bac18538933b981ed2875595f98196
139]
140[make local binding monomorphic without using scoped type variables
141Ross Paterson <ross@soi.city.ac.uk>**20101213035831
142 Ignore-this: 52b7f5ed7cb7c6ef0eda6caa39e4713f
143]
144[Always inline foldrWithKey' and foldlWithKey' from Data.Map
145Johan Tibell <johan.tibell@gmail.com>**20101201110527
146 Ignore-this: a84198febd304659ff029c3424855be3
147 
148 Inlining makes it possible to replace an indirect call to an unknown
149 function with a call to a known function at the call site.
150]
151[Tweak insertWith' and insertWithKey' to better match the non-' versions
152Ian Lynagh <igloo@earth.li>**20101128175028
153 Ignore-this: 41b50b13b1a94ae56bad8d381c696d04
154 They now are not marked inlinable, force the key, and are exported.
155]
156[Add foldlWithKey' and foldrWithKey' to Data.Map
157Johan Tibell <johan.tibell@gmail.com>**20101103132836
158 Ignore-this: d2ac0f0a50842ec5a007b9ad11ce63d0
159]
160[Add strict versions of insertWith and insertWithKey to IntMap
161Johan Tibell <johan.tibell@gmail.com>**20101030135122
162 Ignore-this: 5472c9be565e75672140d243ef0211f2
163]
164[Explain INLINEs in IntMap and IntSet.
165Milan Straka <fox@ucw.cz>**20101104224507
166 Ignore-this: 322a22056e9aa5d4e5a9f2caa6542017
167]
168[Fix warnings.
169Milan Straka <fox@ucw.cz>**20101104223950
170 Ignore-this: 19460b7cab4554fef3b637ebb36addd1
171 
172 Just trivial renames of shadows variables.
173]
174[Explain the nomatch clause in IntSet.hs
175Milan Straka <fox@ucw.cz>**20101104221451
176 Ignore-this: 2f90d0037027e77cffff30cf21729845
177]
178[Rename STRICTxy to STRICT_x_OF_y.
179Milan Straka <fox@ucw.cz>**20101104220917
180 Ignore-this: fb12cee5518d1a8844ee44273330fa57
181 
182 Also explain why bang patterns are not used.
183]
184[Settle performance issues in Map and Set.
185Milan Straka <fox@ucw.cz>**20101031082146
186 Ignore-this: 9a4c70d5f9a5884c7ff8f714ae4ff1e4
187 
188 Explain the INLINE/INLINABLE in the Map and Set sources.
189 
190 Use 'go' only for functions that can be INLINE.
191]
192[Settle performance issues in IntMap and IntSet.
193Milan Straka <fox@ucw.cz>**20101029231653
194 Ignore-this: c1234a5113da14178a2394976e91b786
195 
196 The worker-wrapper transformation is removed from
197 all functions but lookup and member. This is the
198 only place where it causes benefits -- a 10% to
199 15% speedup. It increases memory allocation
200 slightly (0-5%), but the effect on GHC is really
201 minor.
202 
203 Also INLINE/INLINABLE hints are not really needed,
204 GHC figures it all by itself. The explicit INLINE
205 were left on internal functions that are crutial
206 to INLINE because of performance.
207]
208[Make foldlStrict semantics to match foldl'.
209Milan Straka <fox@ucw.cz>**20101022100939
210 Ignore-this: 3790a5a47e4ff7b55c005a8c95e5890f
211]
212[Remove INLINABLE in IntMap and IntSet.hs.
213Milan Straka <fox@ucw.cz>**20101022091744
214 Ignore-this: 4f532887bf54444989cc66d6546f1c89
215 
216 It makes no sense, as the calls are already specialized
217 for Int keys. Benchmarks actually show small slowdown.
218]
219[Do not pass f explicitely for fold.
220Milan Straka <fox@ucw.cz>**20101019202043
221 Ignore-this: bb0a5e758ebfebbdf8160be4317898e9
222 
223 Benchmarks shows this is a huge win (100% for (:) being
224 the function, 1000% for (+) being the function).
225]
226[Mark fold explicitely as INLINE.
227Milan Straka <fox@ucw.cz>**20101016222150
228 Ignore-this: b72855a0af39e57b1862908717fc14fc
229 
230 The INLINABLE does not work well in this case. Benchmarks
231 show memory savings (due to unboxing) and nearly no GHC binary
232 size increase.
233]
234[Changing INLINE pragmas.
235Milan Straka <fox@ucw.cz>**20101016215959
236 Ignore-this: 933327354749d18e4617280fde55cce0
237 
238 The internal functions that need to be inlined are marked INLINE
239 (bit fiddling in IntMap/IntSet, empty, singleton, bin).
240 
241 Aslo if INLINABLE is available, use it for all exported functions.
242 The functions like insert that were INLINE because of specialization
243 issues are now INLINE only in the case of INLINABLE absence.
244]
245[Whitespace changes only.
246Milan Straka <fox@ucw.cz>**20101016202831
247 Ignore-this: 8850e09fb49937b54da6585d01aade9a
248]
249[Correct a typo in macro name.
250Milan Straka <fox@ucw.cz>**20101016202641
251 Ignore-this: 356621b0ca954f73d543fc33d43383b2
252]
253[Change the worker/wrapper to explicitly pass arguments.
254Milan Straka <fox@ucw.cz>**20101016195757
255 Ignore-this: 7f4a2180a263ee15cbb73c60b2d8cc46
256 
257 As the benchmarking showed, it is not a good idea to create
258 closures in the worker/wrapper transformation, as the captured
259 arguments of the enclosing function have to be allocated on the
260 heap. It is better to explicitly pass the arguments on the stack.
261 This saves memory and add no time penalty if the arguments are
262 the first arguments of recursive function (GHC refrains from
263 needless copying).
264 
265 The worker is often strict in some arguments. I did not want
266 to use BangPatterns, so I used macros to indicate strictness.
267 If majority thinks BangPatters are fine, I will gladly change it.
268]
269[Fix warnings in Data.Map and Data.Set.
270Milan Straka <fox@ucw.cz>**20100924154946
271 Ignore-this: cb2c0a8ecf0a57acc5941ba841aa7c40
272 
273 Only trivial changes.
274]
275[Finish the started worker/wrapper transformation.
276Milan Straka <fox@ucw.cz>**20100924153353
277 Ignore-this: baeb24573242beb56c3bbe7ca67f5ff7
278 
279 Some methods (insert, lookup) were not modified as the rest
280 (like insertWith, delete, ...). Also the `seq` were missing
281 sometimes.
282]
283[Merge all the OPTIONS and LANGUAGE module pragmas.
284Milan Straka <fox@ucw.cz>**20100924152642
285 Ignore-this: 86067abf13f0501f29c13ec7c877533c
286]
287[Remove most INLINE from Map, Set, IntMap and IntSet.
288Milan Straka <fox@ucw.cz>**20100924152008
289 Ignore-this: c88c4ede21c06bfda20af131c232a720
290 
291 Because of a code bloat the INLINEs cause, remove most of
292 them. The only INLINEs left are the following:
293 - only in Set and Map, because in IntMap and IntSet the specialization
294   does not help
295 - only on functions which need Ord
296 - only on 'small' functions, namely member, notMember, lookup*,
297   insert*, delete*, adjust*, alter*, update*
298 
299 All other functions of Map, Set, IntMap and IntSet are marked INLINABLE,
300 even if they are recursive.
301 
302 The INLINEs left are only a short-term solution. In the long run the
303 auto-specialization of INLINABLE methods seems a good way (maybe
304 SPECIALIZABLE).
305]
306[Comment tests and benchmarks on foldlWithKey' which
307Milan Straka <fox@ucw.cz>**20100924110705
308 Ignore-this: 71b988389e6ae9a78ea3b0e20156ca2f
309 was commented recently by Ian Lynagh.
310]
311[Worker/wrapper transformation for Data.IntSet.
312Milan Straka <fox@ucw.cz>**20100923125604
313 Ignore-this: b0228582818f7bfb690d0853022a7809
314]
315[Compile only the benchmark source, not the Data/*.hs.
316Milan Straka <fox@ucw.cz>**20100921115821
317 Ignore-this: f94d9e3ffe126cd057d23490c973a4e9
318]
319[Add criterion-based benchmark for IntSet.hs.
320Milan Straka <fox@ucw.cz>**20100921103225
321 Ignore-this: 3d31a820830c7382748626bc9a1ba54
322 
323 The benchmark is nearly identical copy of Set.hs benchmark.
324]
325[Add a testsuite for Data.IntSet.
326Milan Straka <fox@ucw.cz>**20100921102802
327 Ignore-this: e55484ee185e71915452bdf2a7b2a2b3
328]
329[Further improve Data.Set balance function.
330Milan Straka <fox@ucw.cz>**20100921091828
331 Ignore-this: f23be37859224e9bbe919a3c0a71fdc6
332 
333 As suggested by Kazu Yamamoto, we split balance to balanceL and
334 balanceR, which handle only one-sided inbalance, but need fewer
335 tests than balance.
336 
337 As nearly all functions modifying the structure use balance, this
338 results in speedup of many functions. On my 32-bit GHC 6.12.1,
339 11% speedup for insert, 12% speedup for delete.
340]
341[Further improve Data.Map balance function.
342Milan Straka <fox@ucw.cz>**20100921091547
343 Ignore-this: 8abfd027142a5183b2b5282e96ccb414
344 
345 As suggested by Kazu Yamamoto, we split balance to balanceL and
346 balanceR, which handle only one-sided inbalance, but need fewer
347 tests than balance.
348 
349 As nearly all functions modifying the structure use balance, this
350 results in speedup of many functions. On my 32-bit GHC 6.12.1,
351 20% speedup for insert, 7% speedup for delete, 5% speedup for update.
352]
353[Changing delta to 3 in Data.Set.
354Milan Straka <fox@ucw.cz>**20100921090507
355 Ignore-this: a47d0c542ed9cee99ad6b17c52c977a1
356 
357 Only possible values are 3 and 4. The value 3 has much faster inserts,
358 value 4 slightly faster deletes, so choosing 3.
359 
360 Also changed the inequalities to rebalance only when one subtree
361 is _strictly_ larger than delta * the other one, to mimic the behaviour
362 from the proof (both from the Adams' and from the one to come).
363]
364[Changing delta to 3 in Data.Map.
365Milan Straka <fox@ucw.cz>**20100921090358
366 Ignore-this: 85f733f836b65b2b1038383ddb92e8e1
367 
368 Only possible values are 3 and 4. The value 3 has much faster inserts,
369 value 4 slightly faster deletes, so choosing 3.
370 
371 Also changed the inequalities to rebalance only when one subtree
372 is _strictly_ larger than delta * the other one, to mimic the behaviour
373 from the proof (both from the Adams' and from the one to come).
374]
375[Correct Data.Set Arbitrary instance never to return unbalanced trees.
376Milan Straka <fox@ucw.cz>**20100914150442
377 Ignore-this: b5c70fa98a56f225b8eb5faf420677b0
378 
379 The previous instance sometimes returned unbalanced trees,
380 which broke the tests.
381 
382 Also the new instance mimics Data.Map instance more closely in the shape
383 of the generated trees.
384]
385[Correct Data.Map Arbitrary instance never to return unbalanced trees.
386Milan Straka <fox@ucw.cz>**20100914145841
387 Ignore-this: 114bbcc63acdb16b77140ea56aeb0a95
388 
389 The previous instance sometimes returned unbalanced trees,
390 which broke the tests.
391]
392[Improve Data.Set benchmark.
393Milan Straka <fox@ucw.cz>**20100914142010
394 Ignore-this: 9b878ae3aa5a43ef083abfd7f9b22513
395 
396 Add union, difference and intersection to Data.Set benchmark.
397]
398[Improve benchmark infrastructure and Data.Map benchmark.
399Milan Straka <fox@ucw.cz>**20100914141707
400 Ignore-this: 67e8dafcb4abcb9c726b9b29c7c320fd
401 
402 Renamed Benchmarks.hs to Map.hs, as it only benchmarks Data.Map.
403 Improve the Makefile to work with multiple benchmarks.
404 Add union, difference and intersection to Data.Map benchmark.
405]
406[Improve the performance of Data.Set balance function.
407Milan Straka <fox@ucw.cz>**20100914140417
408 Ignore-this: 577c511c219695b8d483af546c7387e8
409 
410 The balance function is now one monolithic function, which allows
411 to perform all pattern-matches only once.
412 
413 Nearly all functions modifying Data.Map use balance.
414 The improvements are 12% for insert, 14% for delete (GHC 6.12.1).
415]
416[Improve the performance of Data.Map balance function.
417Milan Straka <fox@ucw.cz>**20100914140217
418 Ignore-this: 951181e035fcac90674dff3300350a1
419 
420 The balance function is now one monolithic function, which allows
421 to perform all pattern-matches only once.
422 
423 Nearly all functions modifying Data.Map use balance.
424 The improvements are 7-11% for various insert*, delete*, alter,
425 update or intersection functions (GHC 6.12.1).
426]
427[Improve performance of Data.Set union and difference operations.
428Milan Straka <fox@ucw.cz>**20100914135725
429 Ignore-this: 6dc4a186ea060b9cdb9e783db71ca280
430 
431 Use datatype storing evaluated bound instead of high-order functions.
432 The improvements are over 25% for both union and difference (GHC 6.12.1).
433]
434[Improve performance of Data.Map union* and difference* operations.
435Milan Straka <fox@ucw.cz>**20100914134614
436 Ignore-this: 35b23a40ef33e9fa14eb81fdee4b152d
437 
438 Use datatype storing evaluated bound instead of high-order functions.
439 The improvements are 22% for union and 20% for difference (GHC 6.12.1).
440]
441[Make the Set store the elements evaluated (bang added).
442Milan Straka <fox@ucw.cz>**20100913165132
443 Ignore-this: b3f230db5bf30d93d3fddf2c81c5f3b4
444]
445[Improved performance of Data.Set
446Johan Tibell <johan.tibell@gmail.com>**20100831124352
447 Ignore-this: 38a304a0408d29a2956aa9a1fc0ce755
448 
449 Performance improvements are due to manually applying the
450 worker/wrapper transformation and strictifying the keys.
451 
452 Average speed-up is 32% on a 2GHz Core 2 Duo on OS X 10.5.8
453]
454[Added benchmarks for Data.Set
455Johan Tibell <johan.tibell@gmail.com>**20100831124225
456 Ignore-this: fcacf88761034b8c534d936f0b336cc0
457]
458[Added a test suite for Data.Set
459Johan Tibell <johan.tibell@gmail.com>**20100831124030
460 Ignore-this: f430dc302c0fcb8b5d62db2272a1d6f7
461 
462 Expression coverage: 74%
463]
464[Remove use of lambdas with irrefutable patterns
465simonpj@microsoft.com**20100923120838
466 Ignore-this: c36e90a0258c0d5262684c585c321419
467]
468[Revert the recent contentious changes
469Ian Lynagh <igloo@earth.li>**20100915135103
470 Ignore-this: fe4f71ff1ade51c11421dc9974aa0fda
471 These will probably be tidied up and reinstated later, but this gets
472 the package back to a releasable state.
473]
474[fix warnings
475Simon Marlow <marlowsd@gmail.com>**20100831114555
476 Ignore-this: 53df71bc054a779b8ad2dad89c09e02d
477]
478[Missing MagicHash for IntSet
479Don Stewart <dons@galois.com>**20100831093446
480 Ignore-this: d075f760adb9a2aa0ee04676e38a07cc
481]
482[Performance improvements for Data.IntMap (worker/wrapper and inlining)
483Don Stewart <dons@galois.com>**20100831093316
484 Ignore-this: 206036448558d270f0eb85ef4cd55368
485]
486[Add criterion-based benchmarking for IntMap
487Don Stewart <dons@galois.com>**20100831093240
488 Ignore-this: d7d85b9afb513532cc30f5b51a3f825e
489]
490[Add comprehensive testsuite for IntMap
491Don Stewart <dons@galois.com>**20100831093202
492 Ignore-this: d455fedbc615e5b63ac488e605550557
493]
494[-O2 -fregs-graph is a uniform 10% improvements for IntMap
495Don Stewart <dons@galois.com>**20100831092956
496 Ignore-this: 2372cf4be945fe7939d0af94e32c567f
497]
498[Missed base case for updateAt worker. Spotted by Jan-Willem Maessen
499Don Stewart <dons@galois.com>**20100829163329
500 Ignore-this: b8daf1c55c163c16f50c3b54cca2dba1
501]
502[Major bump (new functions, clarified strictness properties, vastly better performance)
503Don Stewart <dons@galois.com>**20100829122628
504 Ignore-this: 9bfbc58ecaa24a86be37b8c4cb043457
505]
506[Add two new functions: foldlWithKey' and insertLookupWithKey'
507Don Stewart <dons@galois.com>**20100829122147
508 Ignore-this: a2f112653ba38737fe1b38609e06c314
509 
510 These two functions use strict accumulators, compared to their existing
511 counterparts (which are lazy left folds, that appear not to be useful).
512 Performance is significantly better.
513 
514]
515[Performance improvements to Data.Map
516Don Stewart <dons@galois.com>**20100829120245
517 Ignore-this: b4830cddfa6d62e4883f4e0f58ac4e57
518 
519 Applied several standard transformations to improve the performance of
520 code:
521 
522     * Worker/wrapper of all recursive functions with constant arguments
523     * Inlining of all (non-recursive) wrappers
524     * Consistent use of strict keys
525 
526 Average performance improvements across common API (with GHC 6.12.3):
527 
528     * Linux / x86_64 / 2.6Ghz i7        : 48%
529     * Mac OSX 10.5 / x86 / 2 Ghz Xeon   : 36%
530 
531 Graphs and raw data: http://is.gd/eJHIE
532 
533 This patch is (mostly) orthogonal to the algorithmic changes suggested
534 by Milan Straka in his HW 2010 paper:
535 
536     http://research.microsoft.com/~simonpj/papers/containers/containers.pdf
537 
538 Those changes could be added separately, for some additional improvments.
539 
540 Work carried out over 28/29th August, 2010 in Utrecht, NL, by Johan Tibell
541 and Don Stewart.
542 
543]
544[Add a criterion-based benchmark suite for Data.Map
545Don Stewart <dons@galois.com>**20100829114611
546 Ignore-this: ec61668f5bcb78bd15b72e2728c01c19
547 
548 This adds a criterion-based micro-benchmarking suite for Data.Map. It
549 can be used to measure performance improvements for individual top-level
550 functions.
551 
552 Examples here: http://is.gd/eJHIE
553 
554]
555[Add a comprehensive testsuite for Data.Map
556Don Stewart <dons@galois.com>**20100829113545
557 Ignore-this: 891e7fe6bac3523868714ac1ff51c0a3
558 
559 This patch adds a joint quickcheck2 / hunit testsuite, with coverage of
560 91% of top level functions (remaining features are mostly in instances).
561 
562 The coverage data is here:
563     
564     http://code.haskell.org/~dons/tests/containers/hpc_index.html
565 
566 No bugs were found. It includes unit tests for known past bugs
567 (balancing).
568 
569]
570[Oops, get the #ifdef symbol correct.
571Malcolm.Wallace@me.com**20100902081938]
572[Protect a gratuitous GHC-ism with #ifdefs.
573Malcolm.Wallace@me.com**20100902081217]
574[Set Data.Map's delta to 4; fixes #4242
575Ian Lynagh <igloo@earth.li>**20100815131954]
576[Add a test for #4242
577Ian Lynagh <igloo@earth.li>**20100815131856]
578[Add a local type signature
579simonpj@microsoft.com**20100730124447
580 Ignore-this: b581d3f2c80a7a860456d589960f12f2
581]
582[Add type signature in local where clause
583simonpj@microsoft.com**20100727151709
584 Ignore-this: 5929c4156500b25b280eb414b508c508
585]
586[Fix Data.Sequence's breakr, and add a test for it; fixes trac #4157
587Ian Lynagh <igloo@earth.li>**20100704140627]
588[Fix proposal #4109: Make Data.Map.insertWith's strictness consistent
589Ian Lynagh <igloo@earth.li>**20100615133055]
590[Tweak layout to work with the alternative layout rule
591Ian Lynagh <igloo@earth.li>**20091129154519]
592[Disable building Data.Sequence (and dependents) for nhc98.
593Malcolm.Wallace@cs.york.ac.uk**20091124025653
594 There is some subtlety of polymorphically recursive datatypes and
595 type-class defaulting that nhc98's type system barfs over.
596]
597[Fix another instance of non-ghc breakage.
598Malcolm.Wallace@cs.york.ac.uk**20091123092637]
599[Add #ifdef around ghc-only (<$) as member of Functor class.
600Malcolm.Wallace@cs.york.ac.uk**20091123085155]
601[Fix broken code in non-GHC branch of an ifdef.
602Malcolm.Wallace@cs.york.ac.uk**20091123084824]
603[doc bugfix: correct description of index argument
604Ross Paterson <ross@soi.city.ac.uk>**20091028105532
605 Ignore-this: 9790e7bf422c4cb528722c03cfa4fed9
606 
607 As noted by iaefai on the libraries list.
608 
609 Please merge to STABLE.
610]
611[Bump version to 0.3.0.0
612Ian Lynagh <igloo@earth.li>**20090920141847]
613[update base dependency
614Ross Paterson <ross@soi.city.ac.uk>**20090916073125
615 Ignore-this: ad382ffc6c6a18c15364e6c072f19edb
616 
617 The package uses mkNoRepType and Data.Functor, which were not in the
618 stable branch of base-4.
619]
620[add fast version of <$ for Seq
621Ross Paterson <ross@soi.city.ac.uk>**20090916072812
622 Ignore-this: 5a39a7d31d39760ed589790b1118d240
623]
624[new methods for Data.Sequence (proposal #3271)
625Ross Paterson <ross@soi.city.ac.uk>**20090915173324
626 Ignore-this: cf17bedd709a6ab3448fd718dcdf62e7
627 
628 Adds a lot of new methods to Data.Sequence, mostly paralleling those
629 in Data.List.  Several of these are significantly faster than versions
630 implemented with the previous public interface.  In particular, replicate
631 takes O(log n) time and space instead of O(n).
632 (by Louis Wasserman)
633]
634[Fix "Cabal check" warnings
635Ian Lynagh <igloo@earth.li>**20090811215900]
636[TAG 2009-06-25
637Ian Lynagh <igloo@earth.li>**20090625160202]
638Patch bundle hash:
6391451b786c264ebaff80fb0610594b7714f4fca88