How to properly optimize MArray functions for speed?

Question

I'm working on a sorting library for MArrays. Speed is important, so I want to optimize it as much as possible.

Currently, I simply INLINE the sorting functions. This speeds up the code more than 10 times, compared to the non-optimized code. However this can easily explode code size if the functions are used in several places, and slows down compilation.

The only other alternative seems to SPECIALIZE the functions for all existing instances of MArray. This also enlarges the resulting code, but only by a constant factor, which doesn't depend on how many times the functions are used. The question is, is it possible that new instances of MArray appear? Or is MArray so special and bound to Haskell's internals so that I can be sure that no new instances can be defined by some other module?

Ahmedahmedabad

It sounds like you want to use the INLINABLE pragma: haskell.org/ghc/docs/7.0.4/html/users_guide/… – Supernova

@JohnL I thought about that, but I'm afraid it'd only work with additional SPECIALIZE pragmas, as the sorting functions are probably too big to be inlined by GHC's decision. But this combination could be a reasonable solution - specializing for all current instances and notifying users to specialize for any new MArray instances they declare. – Ahmedahmedabad

If performance is really critical, consider using vector or repa instead. – Brockington

@DonStewart Thanks Don, I didn't know vector already has a sorting function. According to my simple test, it is somewhat 5-10% faster than my marray-sort. And looking at its source I see that it does what I do now - it just inlines the function. So it's probably the best thing to do. – Ahmedahmedabad

See https://mcmap.net/q/529765/-using-vectors-for-performance-improvement-in-haskell – Brockington

Answer 1

Seems like that the best way is to use the INLINE pragma. sort from vector-algorithms uses it too.

Ahmedahmedabad