[Haskell-cafe] Increasing parallelism in a frequency counter

[Claude Heiland-Allen]

Hi Andreas, all,

On 21/05/15 22:08, Andreas Pauley wrote:
> Hi everyone,
>
> I've started playing with some parallel programming in Haskell, mostly
> by applying the first few examples from Simon Marlow's book to my own
> toy problem:
> https://github.com/apauley/parallel-frequency

Nice.

> I'm quite pleased with the speedup I have so far, the fastest parallel
> implementation is just over twice as fast as its sequential
> counterpart.
>
> But looking at the threadscope images from the generated event logs I
> can see that there are still significant portions of my program that
> runs on only one core.
>
> Is anyone interested to see if we can increase the parallelism in this
> frequency counter?

If the problem is specified as taking the N most frequently occuring 
items in a list:

     f :: Ord a => Int -> [a] -> [(a, Int)]

then I cheated, I assume the input is pre-chunked into a sensible number 
of pieces:

     f' :: Ord a => Int -> [[a]] -> [(a, Int)]

with which it is much easier to get good parallel speedups.


Anyway, some general optimisation points, not all directly related to 
the parallel part of the problem:

0. profile to see what is taking time (and space, it increases GC time)
    you can use +RTS -h without having to recompile for profiling

1. lists are memory inefficient (eg: Map keys): replace String with Text

2. lists and Text are bad at random access (eg: splitting at an index)

3. use Data.Map.Strict to avoid building up (+) thunks

4. (take n . sort) is possibly taking a lot of sequential time (see 0)

5. perhaps try parallel reductions instead of linear folds:
    a * b * c * d * ... -> ((a * b) * (c * d)) * ...
    though the overhead didn't seem worth it in my tests

6. not optimisation related, but consider writing a defaultMain
    then each executable source can be reduce to
       import DefaultMain (defaultMain)
       import FrequencyImplementation (frequency)
       main :: IO ()
       main = defaultMain frequency
    you could even have all the implementations with the same module name
    but in different directories, and use hs-src-dirs: to select, then
    you would be able to use an identical Main module.


more on 2:

A bit of a low-level hack, this: I read the whole input file as a 
ByteString and split it into an appropriate number of chunks, taking 
care not to split UTF-8 sequences, also taking care not to split 
mid-word.  Each output chunk references the original input without 
copying the data.  Then I decodeUtf8 each ByteString chunk to a Text.

This reduced peak memory usage (as reported by +RTS -h graphed with 
hp2ps) from ~400MB of (:) to ~30MB of ARR_WORDS for the 11MB artamene.txt.


more on 4:

So you have a large Map k Int containing frequencies, and you want the 
largest n frequency counts.  There is an O(1) Map.splitRoot, which you 
can use to parallel divide and conquer - the largest n of the whole map 
are going to be among the (n * split count) combined largest n of each 
of the split maps.  This didn't give me much speed up at all, though.


I put my implementation at http://code.mathr.co.uk/word-histogram


Thanks,


Claude
-- 
http://mathr.co.uk