Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Optimising a combinatorial algorithm? (Mario Lang)
2. Re: Optimising a combinatorial algorithm? (Daniel Trstenjak)
3. Re: applicative style (David Moberg)
4. Re: applicative style (Mario Lang)
5. foldl on Bool:s (goforgit .)
6. Re: Optimising a combinatorial algorithm? (Mario Lang)
7. Re: Optimising a combinatorial algorithm? (Chas Leichner)
----------------------------------------------------------------------
Message: 1
Date: Thu, 24 Sep 2015 16:11:29 +0200
From: Mario Lang <[email protected]>
To: [email protected]
Subject: [Haskell-beginners] Optimising a combinatorial algorithm?
Message-ID: <[email protected]>
Content-Type: text/plain; charset=utf-8
Hi!
TL;DR: My implementation looks elegant (to me), but is rather slow
compared to a well optimized C++ impl. of the same algorithm. Runtime
differences are currently huge. Looking for input on what I could
change to match C++ performance, without loosing too much expressiveness
of the code.
I am writing software to deal with Braille music code.
As an exercise for me, and as an attempt to boil the algorithm down
to a more readable form, I am in the process of translating my C++
program[1] to Haskell. So far, so good. Given that I only came back to
Haskell (after 10 years of a break) roughly 2 weeks ago, I think I
have made quite nice progress. However, now that I reached a stage
where I can actually do a performance comparison, the dreaded thing has
happened: The performance of my Haskell implementation is rather
horrible to what my C++ implementation can deliver. While the code size
has gone down roughly by a factor of 10, runtime has gone up roughly by
the same factor...
For the impatient, here is the code I am talking about:
https://github.com/mlang/hbmc/blob/master/Data/Braille/Music.hs
The first half of the code is concerend with parsing braille.
Performance is not critical here, so I opted to use Parsec, mostly
because I am interested in good quality error messages.
The fun starts with the definition of 'pvs'.
The problem:
Braille music values are inherently ambiguous. The sign for a whole
note can also mean a 16th note, a sign for a half note can also
mean a 32th note, the sign for a quarter note can also mean a 64th, and
a 8th note could also mean a 128th note. This is histoical, and there
is no way around this. The time signature (meter) is used to actually
tell which note is which. This is relatively easy to do for an
experienced human, but quite complicated for a computer.
A measure (bar) of braille music can contain parallel *and* sequential
parts. The data structure is basically:
data Sign = ...
type PartialVoice = [Sign]
type PartialMeasure = [PartialVoice]
type Voice = [PartialMeasure]
type Measure = [Voice]
As a constraint, all PartialVoices in a PartialMeasure need to have the
exact same duration. Similarily, all Voices inside a Measure also need to
have the exact same duration.
So 'pvs', 'pms', 'vs' and 'ms' in my Data.Braille.Music module are concerned
with calculating all possible interpretations of the input.
All in all, the current Haskell implementation is doing what it should.
However, profiling tells me I am allocating roughly 2GB of memory
to disambiguate a single measure of music in 3/2 time.
This takes roughly 1.2s on my rather fast CPU.
The amount of allocation and the runtime are unacceptable.
If I leave it at that, I might as well ditch the code and terminate the
experiment.
As a comparison, my C++ impl. takes roughly 1s to disambiguate 32 measures of
the same piece, while Haskell already takes 1.2s to disambiguate just
one of these measures.
Profiling tells me I am spending 90% of all the time in 'dur', which is my
small helper method to calculate the duration of a PartialVoice,
PartialMeasure or Voice.
The project is setup to support profiling:
git clone https://github.com/mlang/hbmc
cd hbmc
cabal run profiling
Do you see a way to significantly speed this algorithm up, without
loosing a lot of expressiveness/elegancy?
Since I am back to Haskell since only 2 weeks, I am basically happy abut
every sort of hint/tip you can give me. Stylistic, as well as
performance-related.
For now, this is really just a toy project. However, if I can manage to
improve the performance significantly without destroying the readability
of the code too much, I might be interested to finish translating my
current C++ work into a more-or-less complete Haskell library.
After all, BMC is more or less a compiler.
And Haskell is supposed to be very good at this stuff :-)
Here is a link to the original C++ project:
[1] https://github.com/malng/bmc
--
CYa,
?????
------------------------------
Message: 2
Date: Thu, 24 Sep 2015 16:41:52 +0200
From: Daniel Trstenjak <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Optimising a combinatorial algorithm?
Message-ID: <20150924144152.GA9234@machine>
Content-Type: text/plain; charset=us-ascii
Hi Mario,
I just took a quick look on the implementation of 'dur'
and as a first thing I would replace foldl with
the strict version foldl'.
This already might explain the memory usage.
Greetings,
Daniel
------------------------------
Message: 3
Date: Thu, 24 Sep 2015 16:51:11 +0200
From: David Moberg <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] applicative style
Message-ID:
<CAL2+Mis0pq_hNzgU7VDvricyESjBtDSHv8oLJ=hvmyx6ww8...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
This mail got stuck in my spam filter because of auth reason.
Bumping in case someone else who missed it wants to answer.
2015-08-28 19:12 GMT+02:00 Williams, Wes(AWF) <[email protected]>:
> Hi haskellers,
>
> I am trying to understand why I get the following error in learning
> applicative style.
>
> Prelude> let estimates = [5,5,8,8,2,1,5,2]
>
> Prelude> (/) <$> Just $ foldl (+) 0 estimates <*> Just . fromIntegral $
> length estimates
>
>
> <interactive>:54:1:
>
> Non type-variable argument in the constraint: Fractional (Maybe r)
>
> (Use FlexibleContexts to permit this)
>
> When checking that ?it? has the inferred type
>
> it :: forall a r.
>
> (Fractional (Maybe r), Num a, Num (Int -> Maybe a -> r)) =>
>
> Maybe r -> Maybe r
>
> All the parts work individually. If use let and assign the parts to x and
> y it also works.
>
> E.g. This works
> let x = Just $ foldl (+) estimates
> Let y = Just . fromIntegral $ length estimates
> (/) <$> x <*> y
>
> I clearly do not understand exactly how these work. :-)
>
> Thanks for any help,
> -wes
>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20150924/b8a84b7d/attachment-0001.html>
------------------------------
Message: 4
Date: Thu, 24 Sep 2015 17:41:05 +0200
From: Mario Lang <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] applicative style
Message-ID: <[email protected]>
Content-Type: text/plain; charset=utf-8
David Moberg <[email protected]> writes:
> This mail got stuck in my spam filter because of auth reason.
> Bumping in case someone else who missed it wants to answer.
>
> 2015-08-28 19:12 GMT+02:00 Williams, Wes(AWF) <[email protected]>:
>
>> Hi haskellers,
>>
>> I am trying to understand why I get the following error in learning
>> applicative style.
>>
>> Prelude> let estimates = [5,5,8,8,2,1,5,2]
>>
>> Prelude> (/) <$> Just $ foldl (+) 0 estimates <*> Just . fromIntegral $
>> length estimates
I think $ is the culprit. You can not combine $ and <*> and
get what you expect, because $ works on *the whole* expression:
Prelude> (/) <$> Just (foldl (+) 0 estimates) <*> Just (fromIntegral (length
estimates))
Just 4.5
Another problem was (.), you actually don't need any function
composition here.
--
CYa,
?????
------------------------------
Message: 5
Date: Thu, 24 Sep 2015 18:04:18 +0200
From: "goforgit ." <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: [Haskell-beginners] foldl on Bool:s
Message-ID:
<CAHzzbMAuKR7b2ZU+65DNDpEbfFG0hiism=a7vfzhdpgqusg...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
Reading http://learnyouahaskell.com/higher-order-functions
I understand that with the function
sum' :: (Num a) => [a] -> a
sum' = foldl (+) 0
the call
ghci>>> sum' [1,2,3]
will be evaluated as
0 + 1 + 2 + 3 = 6
But what about the function
elem' :: (Eq a) => a -> [a] -> Bool
elem' y ys = foldl (\acc x -> if x == y then True else acc) False ys
and calling it with
ghci>>> elem' 3 [1,2,3]
How is that evaluated to True by foldl in elem'?
Thanks in advance for any explanation to this!
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20150924/8ddc1d38/attachment-0001.html>
------------------------------
Message: 6
Date: Thu, 24 Sep 2015 18:42:32 +0200
From: Mario Lang <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Optimising a combinatorial algorithm?
Message-ID: <[email protected]>
Content-Type: text/plain; charset=utf-8
Daniel Trstenjak <[email protected]> writes:
> Hi Mario,
>
> I just took a quick look on the implementation of 'dur'
> and as a first thing I would replace foldl with
> the strict version foldl'.
>
> This already might explain the memory usage.
foldl' helps a bit, but is not the main contributor to the overhead.
Before:
1,954,532,728 bytes allocated in the heap
After:
1,741,200,280 bytes allocated in the heap
And runtime is more or less unaffected.
--
CYa,
?????
------------------------------
Message: 7
Date: Thu, 24 Sep 2015 09:42:45 -0700
From: Chas Leichner <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Optimising a combinatorial algorithm?
Message-ID:
<calppnrwz2oxy_2grnkzwdfwncnjuwbd3mvb_pttt04099mu...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
I haven't had a chance to test anything, but list operations are frequently
problematic because they make it easy to accidentally write O(n^2)
algorithms. Have you tried using Sequences or Vectors? I would expect one
of them to give you better performance for your access patterns.
On Thursday, September 24, 2015, Daniel Trstenjak <
[email protected]> wrote:
>
> Hi Mario,
>
> I just took a quick look on the implementation of 'dur'
> and as a first thing I would replace foldl with
> the strict version foldl'.
>
> This already might explain the memory usage.
>
> Greetings,
> Daniel
> _______________________________________________
> Beginners mailing list
> [email protected] <javascript:;>
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20150924/43ea8aa2/attachment.html>
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
[email protected]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 87, Issue 15
*****************************************
