[Haskell-cafe] ST Vector / STRef -- Performances and allocation

[Carter Schonwald]

StRef is a boxed heap value.

If you use a single element Unboxed Mutable vector you may find there's
less boxing :)

On Saturday, June 18, 2016, Guillaume Bouchard <
guillaum.bouchard+haskell at 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 at haskell.org <javascript:;>
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20160618/c008db56/attachment.html>