Linear time IntSet / IntMap construction from sorted input

[Scott Dillard]

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 at 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 at 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 :
-------------- next part --------------
A non-text attachment was scrubbed...
Name: fromAscList_BF.patch
Type: text/x-diff
Size: 71654 bytes
Desc: not available
Url : http://www.haskell.org/pipermail/libraries/attachments/20080521/b727db1a/fromAscList_BF-0001.bin