<div dir="ltr"><div><div><div></div>I tried memoizing dur in some places, but it gets called with too many different arguments to make it worthwhile.<br></div><div></div></div><div>I tried change StateT to Strict.StateT.<br>Last ditch effort, I tried making your data types strict, but that didn't help.<br></div><div><br></div>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<br></div><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Sep 24, 2015 at 10:11 AM, Mario Lang <span dir="ltr"><<a href="mailto:mlang@delysid.org" target="_blank">mlang@delysid.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi!<br>
<br>
TL;DR: My implementation looks elegant (to me), but is rather slow<br>
compared to a well optimized C++ impl. of the same algorithm.  Runtime<br>
differences are currently huge.  Looking for input on what I could<br>
change to match C++ performance, without loosing too much expressiveness<br>
of the code.<br>
<br>
I am writing software to deal with Braille music code.<br>
As an exercise for me, and as an attempt to boil the algorithm down<br>
to a more readable form, I am in the process of translating my C++<br>
program[1] to Haskell.  So far, so good.  Given that I only came back to<br>
Haskell (after 10 years of a break) roughly 2 weeks ago, I think I<br>
have made quite nice progress.  However, now that I reached a stage<br>
where I can actually do a performance comparison, the dreaded thing has<br>
happened: The performance of my Haskell implementation is rather<br>
horrible to what my C++ implementation can deliver.  While the code size<br>
has gone down roughly by a factor of 10, runtime has gone up roughly by<br>
the same factor...<br>
<br>
For the impatient, here is the code I am talking about:<br>
<a href="https://github.com/mlang/hbmc/blob/master/Data/Braille/Music.hs" rel="noreferrer" target="_blank">https://github.com/mlang/hbmc/blob/master/Data/Braille/Music.hs</a><br>
<br>
The first half of the code is concerend with parsing braille.<br>
Performance is not critical here, so I opted to use Parsec, mostly<br>
because I am interested in good quality error messages.<br>
<br>
The fun starts with the definition of 'pvs'.<br>
<br>
The problem:<br>
Braille music values are inherently ambiguous.  The sign for a whole<br>
note can also mean a 16th note, a sign for a half note can also<br>
mean a 32th note, the sign for a quarter note can also mean a 64th, and<br>
a 8th note could also mean a 128th note.  This is histoical, and there<br>
is no way around this.  The time signature (meter) is used to actually<br>
tell which note is which.  This is relatively easy to do for an<br>
experienced human, but quite complicated for a computer.<br>
A measure (bar) of braille music can contain parallel *and* sequential<br>
parts.  The data structure is basically:<br>
<br>
data Sign = ...<br>
type PartialVoice = [Sign]<br>
type PartialMeasure = [PartialVoice]<br>
type Voice = [PartialMeasure]<br>
type Measure = [Voice]<br>
<br>
As a constraint, all PartialVoices in a PartialMeasure need to have the<br>
exact same duration.  Similarily, all Voices inside a Measure also need to<br>
have the exact same duration.<br>
<br>
So 'pvs', 'pms', 'vs' and 'ms' in my Data.Braille.Music module are concerned<br>
with calculating all possible interpretations of the input.<br>
<br>
All in all, the current Haskell implementation is doing what it should.<br>
However, profiling tells me I am allocating roughly 2GB of memory<br>
to disambiguate a single measure of music in 3/2 time.<br>
This takes roughly 1.2s on my rather fast CPU.<br>
<br>
The amount of allocation and the runtime are unacceptable.<br>
If I leave it at that, I might as well ditch the code and terminate the<br>
experiment.<br>
As a comparison, my C++ impl. takes roughly 1s to disambiguate 32 measures of<br>
the same piece, while Haskell already takes 1.2s to disambiguate just<br>
one of these measures.<br>
<br>
Profiling tells me I am spending 90% of all the time in 'dur', which is my<br>
small helper method to calculate the duration of a PartialVoice,<br>
PartialMeasure or Voice.<br>
<br>
The project is setup to support profiling:<br>
<br>
git clone <a href="https://github.com/mlang/hbmc" rel="noreferrer" target="_blank">https://github.com/mlang/hbmc</a><br>
cd hbmc<br>
cabal run profiling<br>
<br>
Do you see a way to significantly speed this algorithm up, without<br>
loosing a lot of expressiveness/elegancy?<br>
<br>
Since I am back to Haskell since only 2 weeks, I am basically happy abut<br>
every sort of hint/tip you can give me.  Stylistic, as well as<br>
performance-related.<br>
<br>
For now, this is really just a toy project.  However, if I can manage to<br>
improve the performance significantly without destroying the readability<br>
of the code too much, I might be interested to finish translating my<br>
current C++ work into a more-or-less complete Haskell library.<br>
After all, BMC is more or less a compiler.<br>
And Haskell is supposed to be very good at this stuff :-)<br>
<br>
Here is a link to the original C++ project:<br>
[1] <a href="https://github.com/malng/bmc" rel="noreferrer" target="_blank">https://github.com/malng/bmc</a><br>
<span class="HOEnZb"><font color="#888888"><br>
--<br>
CYa,<br>
  ⡍⠁⠗⠊⠕<br>
_______________________________________________<br>
Beginners mailing list<br>
<a href="mailto:Beginners@haskell.org">Beginners@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners</a><br>
</font></span></blockquote></div><br></div>