F# FSharpMap vs Dictionary performance

Question

I was wondering how does the F# immutable Map perform against the standard Dictionary.

I am writing a count function (for each line lookup increment set) to use on large files with millions of lines and thousands of elements.

What about the memory usage?

Thanks

Answer 1

I was wondering how does the F# immutable Map perform against the standard Dictionary.

See Visual F# 2010 for Technical Computing pages 241-242 "Optimization: Use mutable data structures". Shows a Dictionary running 5-40× faster than a Map in the very similar setting of counting the frequencies on ints as a function of the number of unique keys.

In general, purely functional data structures like Map are not only extremely slow in the serial case but they destroy scalability of entire parallel programs. I gave a lecture on this recently.

BTW, don't forget there is a Seq.countBy function!