[MLton-user] Destructive update

[Joe Hurd]

On 2/9/06, Stephen Weeks <sweeks@sweeks.com> wrote:
>
> If you do benchmarks comparing HashSet to some immutable data
> structure(s), please send the results to the list, as I'm sure there
> would be interest.

I'm afraid I didn't do these benchmarks, but I'd like to report my
results anyway because they may be of interest to other people
optimizing ML programs.

Using MLton's wonderful source level profiling I was able to quickly
narrow down my performance bottleneck to one algorithm, implemented in
250 lines of ML and using purely functional data structures.

[Digression: the algorithm in question is loopy belief propagation,
which performs many iterations of visiting all vertices of an
undirected graph, and updating two probability distributions stored on
every edge.]

I rewrote the entire algorithm to 300 lines of ML operating on a
single array of real numbers, with some index preprocessing so that
the computation would have access to relevant indices without any
work.

Anyway, the computation time for my dataset fell from 576 minutes to
30 minutes, which made me rather cheerful. Realistically I'd have to
say that creativity was required to achieve such dramatic savings
(choosing the Array data structure, introducing a preprocessing step),
but I still believe that targeting single threaded data structures for
optimization in MLton would be worthwhile.

Thanks again for all your help,

Joe