<div dir="ltr">This version is about 2x as fast as OP's on my system (look at h2.hs): <a href="https://gist.github.com/gregorycollins/9103248">https://gist.github.com/gregorycollins/9103248</a> <div class="gmail_extra">
<br></div><div class="gmail_extra"><div class="gmail_extra">$ time ./dist/build/h1/h1 50000000 +RTS -A4M > /dev/null</div><div class="gmail_extra">./dist/build/h1/h1 50000000 +RTS -A4M > /dev/null 23.88s user 0.06s system 99% cpu 24.003 total</div>
<div class="gmail_extra"><br></div><div class="gmail_extra">$ time ./dist/build/h2/h2 50000000 +RTS -A4M > /dev/null</div><div class="gmail_extra">./dist/build/h2/h2 50000000 +RTS -A4M > /dev/null 13.57s user 0.09s system 99% cpu 13.706 total</div>
<div class="gmail_extra"><br></div><div class="gmail_extra">$ time ./dist/build/h3/h3 50000000 +RTS -A4M > /dev/null</div><div class="gmail_extra">./dist/build/h3/h3 50000000 +RTS -A4M > /dev/null 24.24s user 0.18s system 99% cpu 24.490 total</div>
<div class="gmail_extra"><br></div></div><div class="gmail_extra">The "system" number here is especially telling: this program is spending almost all of its time in syscalls.</div><div class="gmail_extra"><br></div>
<div class="gmail_extra">G</div><div class="gmail_extra"><br><br><div class="gmail_quote">On Wed, Feb 19, 2014 at 12:47 PM, Charles-Pierre Astolfi <span dir="ltr"><<a href="mailto:cpa@crans.org" target="_blank">cpa@crans.org</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr">Thanks Erik!<div><br></div><div>I was kind of hoping for such a benchmark. On my system, the C version is consistently twice as fast as the Haskell version. (I tried -fllvm, but it doesn't change perf)</div>
<div><br></div><div>Then I added bang patterns for the argument of only012 and in the tuple (p,q) and it now has the same runtime as C.</div><div><br></div><div>Just for fun, I tried to void writing explicit recursion and used only combinators and this Haskell code is still as competitive as C, so the real bottleneck really was the laziness in the tuple/argument.</div>
<div><br></div><div><a href="http://lpaste.net/100153" target="_blank">http://lpaste.net/100153</a><br></div><div><br></div><div>In fact, this Haskell version takes 8 sec vs 10 sec for the C version on my laptop (input: 1000000000).</div>
<div><br></div><div>I tried using Data.List.Stream, I couldn't get any performance gain, probably because the code is very close to optimal.</div><div><br></div><div>So remember kids:</div><div>- Bang pattern the heck out of your code (not a silver bullet, but definitely worth trying).</div>
<div>- Don't rely on too much IO for benchmark.</div><div>- Don't be afraid of combinators even if you want performance.</div><div>- Ask on haskell-cafe, chaps here are very helpful :)</div><div><br></div></div><div class="gmail_extra">
<br clear="all"><div>-- <br>Cp</div>
<br><br><div class="gmail_quote">On Wed, Feb 19, 2014 at 8:39 PM, Erik Rantapaa <span dir="ltr"><<a href="mailto:erantapaa@gmail.com" target="_blank">erantapaa@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<div dir="ltr">I think a lot is being obscured by the IO subsystem.<div><br></div><div>If you print just a count of the only012 numbers I get very different results.</div><div><br></div><div>Here are the versions I compared:</div>
<div><br></div><div><a href="http://lpaste.net/100142" target="_blank">http://lpaste.net/100142</a></div><div><br></div><div>and on my system the C version is about 10x faster.</div><div><div class=""><div><br><br>On Wednesday, February 19, 2014 12:49:36 PM UTC-6, Charles-Pierre Astolfi wrote:</div>
</div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div class=""><div><div dir="ltr">Switching to quotRem gave no measurable improvements.<div>
After switching to ByteString, the code now runs in 9 seconds, which outperforms my C version. But honestly, I have no idea why.</div>
<div><br></div>
<div>New code:</div><div><a href="http://lpaste.net/100136" target="_blank">http://lpaste.net/100136</a><br></div><div><br></div><div><div>$ ghc --make -O3 303only012.hs && time ./303only012 50000000 > /dev/null</div>
<div>./303only012 50000000 > /dev/null 9.72s user 0.21s system 90% cpu 10.961 total</div>
</div><div><br></div><div>@Alois, I'm not sure how criterion can help compare my code with the C version, since in the C version I cannot measure the exec time of only012 only. What did you have in mind?</div><div><br>
</div><div>Thanks everyone!</div><div><br></div></div></div></div><div><br clear="all"><div>-- <br>Cp</div>
<br><br><div class="gmail_quote"><div class=""><div>On Wed, Feb 19, 2014 at 7:24 PM, Levent Erkok <span dir="ltr"><<a>erk...@gmail.com</a>></span> wrote:<br></div></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<div class="">
<div>
<div dir="ltr">Also, prefer quotRem over divMod as the former is faster. See here: <a href="http://stackoverflow.com/questions/339719/when-is-the-difference-between-quotrem-and-divmod-useful" target="_blank">http://stackoverflow.<u></u>com/questions/339719/when-is-<u></u>the-difference-between-<u></u>quotrem-and-divmod-useful</a></div>
</div></div><div><br><br><div class="gmail_quote">On Wed, Feb 19, 2014 at 10:19 AM, Gregory Collins <span dir="ltr"><<a>gr...@gregorycollins.net</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr"><div><div class=""><div><div><div><br><div class="gmail_quote">
On Wed, Feb 19, 2014 at 9:36 AM, Charles-Pierre Astolfi <span dir="ltr"><<a>c...@crans.org</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">So there's a difference, but I'm not sure if it's related to my algorithm or related to IO/RTS.</blockquote>
</div><br></div></div>Text.Printf is slower than the C version (and uses String). Use Data.ByteString.putStr instead.</div></div><span><font color="#888888"><br><br clear="all"><span class=""><font color="#888888"><span><font color="#888888"><span><font color="#888888"><div>
<br></div>
-- <br>Gregory Collins <<a>gr...@gregorycollins.net</a>>
</font></span></font></span></font></span></font></span></div></div><span class=""><font color="#888888"><span><font color="#888888"><div>
<br>______________________________<u></u>_________________<br>
Haskell-Cafe mailing list<br>
<a>Haskel...@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/<u></u>mailman/listinfo/haskell-cafe</a><br>
<br></div></font></span></font></span></blockquote></div><span class=""><font color="#888888"><span><font color="#888888"><br></font></span></font></span></div><span class=""><font color="#888888"><span><font color="#888888">
</font></span></font></span></blockquote></div><span class=""><font color="#888888"><span><font color="#888888"><br></font></span></font></span></div>
</blockquote></div></div></blockquote></div><br></div>
<br>_______________________________________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
<br></blockquote></div><br><br clear="all"><div><br></div>-- <br>Gregory Collins <<a href="mailto:greg@gregorycollins.net" target="_blank">greg@gregorycollins.net</a>>
</div></div>