Help with a Shootout program

[Bayley, Alistair]

> From: Simon Marlow [mailto:simonmar at microsoft.com] 
> 
> PackedStrings are still slow in 6.x.  I know there are various other
> PackedString implementations out there, we just need to 
> incorporate one.

They certainly seem to be. Below are the profiles (compiled with -O2; ran
them twice; took the second run) of Simon's old PackedString version, and
Alson's Hash version. Simon's uses way more memory, too. I might try some
more profiling later to narrow down the slow bits.


> From: Alson Kemp [mailto:Alson.Kemp at sloan.mit.edu] 
> 
> 	I tried Simon's version, but it throws a "Fail: 
> Ix{Int}.index: Index
> (5) out of range ((0,4))" error.  Haven't tracked down the cause yet.


Here's the fix (subtract one from (lengthPS ps)):

-- Looks bad, but GHC does a great job of optimising it:
hashPS :: PackedString -> Int
hashPS ps = foldr f 0 (map (ord.indexPS ps) [0..((lengthPS ps) - 1)])
  where f n m = n + m * 128 `mod` 1048583



------------------------------- Alson's:

       spellcheck +RTS -p -hr -H10m -K20m -RTS

    total time  =        1.84 secs   (92 ticks @ 20 ms)
    total alloc =  69,112,588 bytes  (excludes profiling overheads)

COST CENTRE                    MODULE               %time %alloc

main                           Main                  58.7   21.2
spellcheck                     Main                  23.9   34.2
buildHash                      Main                  17.4   44.6


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

MAIN           MAIN                  1           0   0.0    0.0   100.0
100.0
 main          Main                146           1  58.7   21.2   100.0
100.0
  spellcheck   Main                149           0  23.9   34.2    23.9
34.2
  buildHash    Main                148           1  17.4   44.6    17.4
44.6
 CAF           Main                140           1   0.0    0.0     0.0
0.0
  main         Main                147           0   0.0    0.0     0.0
0.0
 CAF       GHC.Handle              103           6   0.0    0.0     0.0
0.0
 CAF       System.Posix.Internals   81           4   0.0    0.0     0.0
0.0



------------------------------- Simon's:

       spellcheck +RTS -p -hr -H10m -K20m -RTS

    total time  =        6.90 secs   (345 ticks @ 20 ms)
    total alloc = 351,514,332 bytes  (excludes profiling overheads)

COST CENTRE                    MODULE               %time %alloc

main                           Main                  93.0   93.6
hashPS                         Main                   3.2    2.4
elemHashTable                  Main                   2.0    0.1
addToHashTable                 Main                   1.7    0.2
CAF                            Data.PackedString      0.0    3.6


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

MAIN             MAIN                1           0   0.0    0.0   100.0
100.0
 main            Main              166           1  93.0   93.6   100.0
96.4
  elemHashTable  Main              171       38618   2.0    0.1     2.9
1.3
   hashPS        Main              172       38618   0.9    1.2     0.9
1.2
  addToHashTable Main              168       38617   1.7    0.2     4.1
1.4
   hashPS        Main              169       38617   2.3    1.2     2.3
1.2
 CAF             Main              160           4   0.0    0.0     0.0
0.0
  hashPS         Main              170           0   0.0    0.0     0.0
0.0
  main           Main              167           0   0.0    0.0     0.0
0.0
 CAF             GHC.Handle        123           5   0.0    0.0     0.0
0.0
 CAF      System.Posix.Internals   101           4   0.0    0.0     0.0
0.0
 CAF      Data.PackedString         86           1   0.0    3.6     0.0
3.6


-----------------------------------------
*****************************************************************
Confidentiality Note: The information contained in this   message, and any
attachments, may contain confidential   and/or privileged material. It is
intended solely for the   person(s) or entity to which it is addressed. Any
review,   retransmission, dissemination, or taking of any action in
reliance upon this information by persons or entities other   than the
intended recipient(s) is prohibited. If you received  this in error, please
contact the sender and delete the   material from any computer.
*****************************************************************