Hi, You might want to add inline pragmas to "inc" and so on. STRef is boxed, so it will allocate. The 'URef' type here might be useful: http://hackage.haskell.org/package/mutable-containers-0.3.2.1/docs/Data-Muta... It is just a wrapper around unboxed mutable vector, as Carter suggests. The sad story is that in my experience, if you really want decent performance you will have to dump the Core and inspect it by hand. You'd then add inline and bang patterns based on the Core. I do not recommend it as a relaxing weekend exercise. I usually use an invocation something like:
ghc -ddump-prep -dppr-case-as-let -dsuppress-all -fforce-recomp inversions.hs > inversions.hscore
On Sun, 19 Jun 2016 at 06:38 Guillaume Bouchard < guillaum.bouchard+haskell@gmail.com> wrote:
Hello.
I read a reddit post [0] which ends in a debate about haskell performances. Someone gives a C implementation which runs in 15ms on some dataset. I wanted to learn about mutable vector and ST and got something in haskell which runs in 50ms. Code is here [1].
[0] https://www.reddit.com/r/haskell/comments/4ojsn0/counting_inversions_haskell... [1] https://github.com/guibou/inversionsCount/blob/syntax/inversions.hs
When I'm profiling the code, I'm surprised to see more than 50% of the %alloc in function which, from my point of view, must not allocate.
For example, this function :
inc :: forall s. STRef s Int -> ST s () inc v = modifySTRef' v (+1)
Is responsible for 10% of the allocation in this program. I was hoping that the "unboxing magic" of GHC may have replaced my Int somewhere by an unboxed one, but I guess the allocation means that the STRef is somehow pointing to a heap allocated Int.
Do you know a way to remove theses allocations?
As a second question, if you see any other way to improve this implementation, I'll be happy to learn something new ;)
Finally, if you read my code, you'll see that I implemented a small DSL around ST / STRef / MVector to make my main function more readable. How do people write readable code in real life ?
Especially, I was annoyed when I tried to convert this piece of C code :
if (x1 < mid && (x2 == sz || tmp[x1] <= p[x2])) { a; } else { b; }
In my haskell code, x1, x2 are STRef, and tmp and p are MVector. This was highly painful to write in haskell and I had to write something such as:
x1 <- readSTRef x1' x2 <- readSTRef x2'
cond <- if x1 < mid then if x2 == sz then return True else do tmp_x1 <- Vector.read tmp x1 p_x2 <_ Vector.read p x2 return (tmp_x1 <= p_x2) else return False if cond then a else b
This is painful, complex and error prone, so is there another solution ?
Thank you. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe