StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Dr Jon Harrop, whom I contacted over e-mail, explained what is going on:</p> <blockquote> <p>The problem is simply that the program has been optimized for Python. This is common when the programmer is more familiar with one language than the other, of course. You just have to learn a different set of rules that dictate how F# programs should be optimized... Several things jumped out at me such as the use of a "for i in 1..n do" loop rather than a "for i=1 to n do" loop (which is faster in general but not significant here), repeatedly doing List.mapi on a list to mimic an array index (which allocated intermediate lists unnecessarily) and your use of the F# TryGetValue for Dictionary which allocates unnecessarily (the .NET TryGetValue that accepts a ref is faster in general but not so much here)</p> <p>... but the real killer problem turned out to be your use of a hash table to implement a dense 2D matrix. Using a hash table is ideal in Python because its hash table implementation has been extremely well optimized (as evidenced by the fact that your Python code is running as fast as F# compiled to native code!) but arrays are a much better way to represent dense matrices, particularly when you want a default value of zero.</p> </blockquote> <p>The funny part is that when I first coded this algorithm, I <em>DID</em> use a table -- I changed the implementation to a dictionary for reasons of clarity (avoiding the array boundary checks made the code simpler - and much easier to reason about).</p> <p>Jon transformed my code (back :-)) into its <a href="https://gist.github.com/950728">array version</a>, and it runs at 100x speed.</p> <p>Moral of the story: </p> <ul> <li>F# Dictionary needs work... when using tuples as keys, compiled F# is slower than interpreted Python's hash tables!</li> <li>Obvious, but no harm in repeating: Cleaner code sometimes means... much slower code.</li> </ul> <p>Thank you, Jon -- much appreciated.</p> <p><strong>EDIT</strong>: the fact that replacing Dictionary with Array makes F# finally run at the speeds a compiled language is expected to run, doesn't negate the need for a fix in Dictionary's speed (I hope F# people from MS are reading this). Other algorithms depend on dictionaries/hashes, and can't be easily switched to using arrays; making programs suffer "interpreter-speeds" whenever one uses a Dictionary, is arguably, a bug. If, as some have said in the comments, the problem is not with F# but with .NET Dictionary, then I'd argue that this... is a bug in .NET!</p> <p><strong>EDIT2</strong>: The clearest solution, that doesn't require the algorithm to switch to arrays (some algorithms simply won't be amenable to that) is to change this:</p> <pre><code>let optimalResults = new Dictionary<_,_>() </code></pre> <p>into this:</p> <pre><code>let optimalResults = new Dictionary<_,_>(HashIdentity.Structural) </code></pre> <p>This change makes the F# code run 2.7x times faster, thus finally beating Python (1.6x faster). The weird thing is that tuples <em>by default</em> use structural comparison, so in principle, the comparisons done by the Dictionary on the keys are the same (with or without Structural). Dr Harrop theorizes that the speed difference may be attributed to virtual dispatch: <em>"AFAIK, .NET does little to optimize virtual dispatch away and the cost of virtual dispatch is extremely high on modern hardware because it is a "computed goto" that jumps the program counter to an unpredictable location and, consequently, undermines branch prediction logic and will almost certainly cause the entire CPU pipeline to be flushed and reloaded"</em>.</p> <p>In plain words, and as suggested by Don Syme (<a href="http://cs.hubfs.net/forums/thread/654.aspx">look at the bottom 3 answers</a>), "be explicit about the use of structural hashing when using reference-typed keys in conjunction with the .NET collections". (Dr. Harrop in the comments below also says that we should <em>always</em> use Structural comparisons when using .NET collections).</p> <p>Dear F# team in MS, if there is a way to automatically fix this, please do.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload