Skip to content
Advertisement

Haskell extremely slow simple recurrence

I’m experimenting with Haskell profiling with a simple recursive max algorithm:

JavaScript

When I compare it to a python imperative equivalent, I get a 10x speed factor in favor of python:

JavaScript
  • It seems there is an inherent limitation of using tail recursion in the Haskell case, am I right?
  • Any other way to make the Haskell code faster?
  • The input file contains 1M unsigned, unbounded integers (on average 32 digits)

For completeness, here is the complete Haskell file (not sure it is needed):

JavaScript

EDIT: refactor suggested by @Willem Van Onsem, works ! (28 sec -> 12 sec)

JavaScript

Any ideas on further improvements? I must be faster than python !

Advertisement

Answer

Using this to benchmark your function should make it go much faster (also be sure to use text version 2.0 or later):

JavaScript

You can also speed up your max_tag function itself by making it tail recursive and thus avoiding a bunch of memory allocations:

JavaScript

You can make it even slightly faster by using foldr so that you get foldr/build fusion with map readInt:

JavaScript
User contributions licensed under: CC BY-SA
6 People found this is helpful
Advertisement