I got an off-list response from Bertram Felgenhauer, and he made some improvements to my code. I've attached a new patch -- disregard the old one. Here are the timings on my 2Ghz Core Duo, for the program main = print . IS.fold (+) 0 . IS.fromList $ [i-n|i<-[1..2*n]] where n = 5000000 original: 2,820,354,288 bytes allocated in the heap 647,827,824 bytes copied during GC (scavenged) 250,183,416 bytes copied during GC (not scavenged) 158,851,072 bytes maximum residency (9 sample(s)) 5325 collections in generation 0 ( 1.53s) 9 collections in generation 1 ( 1.14s) 315 Mb total memory in use INIT time 0.00s ( 0.00s elapsed) MUT time 2.52s ( 2.50s elapsed) GC time 2.67s ( 2.97s elapsed) EXIT time 0.00s ( 0.00s elapsed) Total time 5.19s ( 5.47s elapsed) %GC time 51.4% (54.3% elapsed) Alloc rate 1,117,350,788 bytes per MUT second Productivity 48.6% of total user, 46.1% of total elapsed new function: 1,168,348,000 bytes allocated in the heap 682,569,432 bytes copied during GC (scavenged) 264,208,568 bytes copied during GC (not scavenged) 184,315,904 bytes maximum residency (9 sample(s)) 2174 collections in generation 0 ( 1.57s) 9 collections in generation 1 ( 1.05s) 355 Mb total memory in use INIT time 0.00s ( 0.00s elapsed) MUT time 1.01s ( 1.02s elapsed) GC time 2.62s ( 2.91s elapsed) EXIT time 0.00s ( 0.00s elapsed) Total time 3.63s ( 3.93s elapsed) %GC time 72.1% (73.9% elapsed) Alloc rate 1,154,423,345 bytes per MUT second Productivity 27.9% of total user, 25.7% of total elapsed How many times can I reply to myself before I'm banned from the list? :) On Tue, May 20, 2008 at 5:24 PM, Scott Dillard <sedillard@ucdavis.edu> wrote:
I've gone ahead and made a patch, which is attached. I don't have access to the full test suite, but it passes the QuickCheck test for just the prop_Ordered property, which is no longer a tautology. Who wrote that test anyway? :)
Scott
On Mon, May 19, 2008 at 5:43 PM, Scott Dillard <sedillard@ucdavis.edu> wrote:
Hi,
It's always bugged me that IntSet.fromAscList is an alias for fromList, which is basically (foldr insert), even though a sorted list is (almost) already in tree order. Is there a reason for this? Or was it just that fromList is good enough? (which it is.)
Assuming the latter, and somewhat bored, I wrote a function to build an IntSet from sorted input in linear time. This goes in Data.IntSet.hs :