[Haskell-cafe] hstats median algorithm

[timothyhobbs at seznam.cz]

Thanks for the advice.  After taking most of it it is faster.  But it is 
still many times slower than it ought to be!  This algorithm should be much 
faster than simply sorting the list, and yet it is more than twice as slow!

One note, you said:
""""
> Increment length.
>
>> modifySTRef
>> lengthRef
>> (+1)

This will create a big thunk for the length, you should use

oldLength <- readSTRef lengthRef
writeSTRef lengthRef $! oldLength + 1

(I'm not sure if a strict modifySTRef exists somewhere...)""""




Actually, replacing modifySTRef with that code is just a hair slower...  Not
sure why.




I'm attaching the super optimized version. Along with the profiler output.  
I just can't understand what is slow here :(




Timothy




---------- Původní zpráva ----------
Od: Felipe Almeida Lessa <felipe.lessa at gmail.com>
Datum: 3. 9. 2012
Předmět: Re: [Haskell-cafe] hstats median algorithm
"On Mon, Sep 3, 2012 at 11:18 AM, Felipe Almeida Lessa
<felipe.lessa at gmail.com> wrote:
> Ditto for oldLen here. Also, you can simplify this lambda a lot:
>
> import Control.Applicative ((<$>))
>
> \(oldLen, oldVal) ->
> let newLen = oldLen + 1
> newVal = (number:) <$> oldVal
> in newLen `seq` newVal `seq` (newLen, newVal)

Or, using BangPatterns,

\(oldLen, oldVal) ->
let !newLen = oldLen + 1
!newVal = (number:) <$> oldVal
in (newLen, newVal)

Cheers,

-- 
Felipe."
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20120903/9535d546/attachment.htm>
-------------- next part --------------
	Mon Sep  3 20:54 2012 Time and Allocation Profiling Report  (Final)

	   medians +RTS -p -K400m -RTS

	total time  =        7.40 secs   (7397 ticks @ 1000 us, 1 processor)
	total alloc = 2,805,885,192 bytes  (excludes profiling overheads)

COST CENTRE      MODULE  %time %alloc

whichBucket      Main     46.8   49.5
buckets.\        Main     35.0   30.1
buckets          Main      7.7    4.6
buckets.\.bucket Main      5.8    5.7
someList.\       Main      2.7    5.7
someList         Main      1.7    4.0


                                                                      individual     inherited
COST CENTRE                 MODULE                  no.     entries  %time %alloc   %time %alloc

MAIN                        MAIN                     55           0    0.0    0.0   100.0  100.0
 CAF                        Main                    109           0    0.0    0.0   100.0  100.0
  someListMin               Main                    123           1    0.0    0.0     0.0    0.0
  someListMax               Main                    122           1    0.0    0.0     0.0    0.0
  someList                  Main                    121           1    1.7    4.0     4.4    9.7
   someList.\               Main                    124        1001    2.7    5.7     2.7    5.7
  someListNumBuckets        Main                    119           1    0.0    0.0     0.0    0.0
  someListGuessedMiddle     Main                    118           1    0.0    0.0     0.0    0.0
  someListMedian            Main                    111           1    0.0    0.0    95.6   90.3
   median                   Main                    112           1    0.3    0.4    95.6   90.3
    median.stubLen          Main                    134           1    0.0    0.0     0.0    0.0
    median.length           Main                    133           1    0.0    0.0     0.0    0.0
    median.halfLength       Main                    132           1    0.0    0.0     0.0    0.0
    median.(...)            Main                    116           1    0.0    0.0    95.3   89.9
     buckets                Main                    117           1    7.7    4.6    95.3   89.9
      buckets.\             Main                    129         100    0.0    0.0     0.0    0.0
      buckets.bottom        Main                    128           1    0.0    0.0     0.0    0.0
      buckets.\             Main                    125     2003001   35.0   30.1    87.6   85.3
       buckets.\.bucket     Main                    126     2003001    5.8    5.7    52.6   55.2
        whichBucket         Main                    127     2003001   46.8   49.5    46.8   49.5
      buckets.\             Main                    120         100    0.0    0.0     0.0    0.0
    median.myBuckets        Main                    115           1    0.0    0.0     0.0    0.0
    median.(...)            Main                    114           1    0.0    0.0     0.0    0.0
     median.(...).\         Main                    130         100    0.0    0.0     0.0    0.0
      median.(...).\.nextI  Main                    131          51    0.0    0.0     0.0    0.0
    median.medianBucketVals Main                    113           1    0.0    0.0     0.0    0.0
  main                      Main                    110           1    0.0    0.0     0.0    0.0
 CAF                        GHC.Conc.Signal          95           0    0.0    0.0     0.0    0.0
 CAF                        GHC.IO.Handle.FD         91           0    0.0    0.0     0.0    0.0
 CAF                        GHC.IO.Encoding          86           0    0.0    0.0     0.0    0.0
 CAF                        GHC.IO.Encoding.Iconv    72           0    0.0    0.0     0.0    0.0
-------------- next part --------------
A non-text attachment was scrubbed...
Name: medians.lhs
Type: text/x-literate-haskell
Size: 5254 bytes
Desc: not available
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20120903/9535d546/attachment.lhs>