13

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?

Petr
  • 62,528
  • 13
  • 153
  • 317
  • It sounds like you want to use the INLINABLE pragma: http://www.haskell.org/ghc/docs/7.0.4/html/users_guide/pragmas.html#inlinable-pragma – John L Jan 15 '13 at 09:17
  • @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. – Petr Jan 15 '13 at 09:57
  • If performance is really critical, consider using vector or repa instead. – Don Stewart Jan 15 '13 at 13:00
  • 1
    @DonStewart Thanks Don, I didn't know vector already has a [sorting function](http://hackage.haskell.org/packages/archive/vector-algorithms/0.5.4.2/doc/html/Data-Vector-Algorithms-Intro.html#v:sort). According to my simple test, it is somewhat 5-10% faster than my _marray-sort_. And looking at [its source](http://hackage.haskell.org/packages/archive/vector-algorithms/0.5.4.2/doc/html/src/Data-Vector-Algorithms-Intro.html#sort) I see that it does what I do now - it just inlines the function. So it's probably the best thing to do. – Petr Jan 15 '13 at 14:22
  • 1
    See http://stackoverflow.com/a/11483226/83805 – Don Stewart Jan 15 '13 at 15:26

1 Answers1

3

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

Petr
  • 62,528
  • 13
  • 153
  • 317