Ticket #5034: improve-performance-of-data_graph_.dpatch

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