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. Re: Optimising a combinatorial algorithm? (David McBride)
2. Re: foldl on Bool:s (Kostiantyn Rybnikov)
3. Re: Optimising a combinatorial algorithm? (Ozgur Akgun)
4. Re: Optimising a combinatorial algorithm? (Mario Lang)
----------------------------------------------------------------------
Message: 1
Date: Thu, 24 Sep 2015 14:07:15 -0400
From: David McBride <[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:
<can+tr40qjz-jpmai3b38adcmtapffawqyjivb3_kenq-wrm...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
I tried memoizing dur in some places, but it gets called with too many
different arguments to make it worthwhile.
I tried change StateT to Strict.StateT.
Last ditch effort, I tried making your data types strict, but that didn't
help.
The dur in your PartialVoice Duration instance gets called 3.5 million
times. I don't know if you are going to find a magic bullet that makes
this faster without tweaking your algorithm. I feel like their is a way to
speed it up, maybe even exploit laziness to eliminate things early, but I'm
just not familiar with this domain. Sorry
On Thu, Sep 24, 2015 at 10:11 AM, Mario Lang <[email protected]> wrote:
> 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,
> ?????
> _______________________________________________
> 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/0590ff27/attachment-0001.html>
------------------------------
Message: 2
Date: Thu, 24 Sep 2015 22:45:21 +0300
From: Kostiantyn Rybnikov <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] foldl on Bool:s
Message-ID:
<caabahfs9j4tookrfxeysl6beocu6k_dbwq46tbmsy7qd5jo...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
Hi.
Your function gets passed numbers one by one in the place of x, and its
previous result in the place of acc, and it returns a Bool. Initial value
in place of acc parameter ("previous result") is put as False (since you
begin with answer "no" to question "is it elem?").
Hope this helps.
24 ???. 2015 19:04 "goforgit ." <[email protected]> ????:
> 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!
>
> _______________________________________________
> 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/c259f0fe/attachment-0001.html>
------------------------------
Message: 3
Date: Thu, 24 Sep 2015 21:11:05 +0100
From: Ozgur Akgun <[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:
<calzazpdpx3zqcmexoye7zusaonljm+md-em+vbtyagipcyw...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
On 24 September 2015 at 15:11, Mario Lang <[email protected]> wrote:
> 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.
>
As a start, and to aid profiling, I suggest getting rid of the Duration
type class and giving explicit names to different dur functions. Which one
of the dur's is getting called most? How do they interact?
My hunch is that after you do this (something like) memoization to avoid
calculating the durations repeatedly will be needed.
Hope this helps,
Ozgur
PS: Cool problem! Do you have some input/output pairs available? If you can
share some, others can validate their attempts without too much domain
knowledge.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20150924/0d172ec9/attachment-0001.html>
------------------------------
Message: 4
Date: Thu, 24 Sep 2015 23:18:25 +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
David McBride <[email protected]> writes:
> I tried memoizing dur in some places, but it gets called with too many
> different arguments to make it worthwhile.
Likely with all possible combinations from the input :-)
> I tried change StateT to Strict.StateT.
> Last ditch effort, I tried making your data types strict, but that didn't
> help.
>
> The dur in your PartialVoice Duration instance gets called 3.5 million
> times. I don't know if you are going to find a magic bullet that makes
> this faster without tweaking your algorithm. I feel like their is a way to
> speed it up, maybe even exploit laziness to eliminate things early, but I'm
> just not familiar with this domain. Sorry
lazyness is a good topic. I am not sure how it actually affects this
algorithm. I wonder if my use of 'filter' is the actual culprit, and if
I instead should try to rewrite the uses of 'traverse' to actually
try and not generate invalid possibilities in the first place. Right
now, I am sort of hoping lazyness would work together with filter being
applied after all possibilities have been generated.
Thanks for your time and insights.
> On Thu, Sep 24, 2015 at 10:11 AM, Mario Lang <[email protected]> wrote:
>
>> 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,
>> ?????
>> _______________________________________________
>> Beginners mailing list
>> [email protected]
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
--
CYa,
????? | Debian Developer <URL:http://debian.org/>
.''`. | Get my public key via finger mlang/[email protected]
: :' : | 1024D/7FC1A0854909BCCDBE6C102DDFFC022A6B113E44
`. `'
`- <URL:http://delysid.org/> <URL:http://www.staff.tugraz.at/mlang/>
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
[email protected]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 87, Issue 16
*****************************************
