Difference in performance for Coin Change between Haskell and C++

Question

I was trying to implement the Coin Change problem in Haskell. The problem is as follows:

Given a set of coins and an infinite supply of those coins, find the minimum number of coins that it will require to make a certain value, say n.

I wrote the following program in haskell:

import Data.Vector ((!), generate)
import Control.Applicative
import Control.Monad

coins = [1, 5, 10, 25, 100] :: [Int]

coinchangev :: Int -> [Int] -> Int
coinchangev n cs = v ! n
 where v = generate (n+1) f
       f 0 = 0
       f n = 1 + minimum [v ! x | x <- map (n-) cs, x >= 0]

main :: IO ()
main = do n <- read <$> getLine :: IO Int
           putStrLn . show $ coinchangev n coins

I wrote the following program in c++:

#include <iostream>
#include <vector>

using namespace std;
typedef vector<int> row;

const row coins {1, 5, 10, 25, 100};
#define INT_MAX 9999999;

int coinchange(const int n, const row& coins) {
    row v(n+1, 0);

    for (int i=1; i<n+1; i++) {
        int min = INT_MAX;

        for (int j=0; j<coins.size(); j++) {
            int x = i - coins[j];
            if (x >= 0 && v[x] < min) {
                min = v[x];
            }
        }

        v[i] = 1 + min;
    }

    return v.back();
}

int main() {
    int n; cin >> n;
    cout << coinchange(n, coins) << endl;

    return 0;
}

I compiled the haskell version with ghc -O3 (version 7.8.4) and the c++ version with g++ --std=c++1y -O3 (version 4.8.4).

For the input 10000000 my haskell program takes much longer than my c++ version to complete. Here are the timings that were measured using time:

Haskell: 6.40user 0.85system 0:07.26elapsed 99%CPU (0avgtext+0avgdata 2664316maxresident)k 152inputs+0outputs (1major+647822minor)pagefaults 0swaps

C++: 0.08user 0.00system 0:00.08elapsed 97%CPU (0avgtext+0avgdata 39964maxresident)k 0inputs+0outputs (0major+936minor)pagefaults 0swaps

My question is why I'm seeing such a large difference and what steps I can take (if any) to improve the performance of the Haskell code. I had expected performance to be basically equivalent (at least within the same order). My objective was to keep the solution simple (and hopefully idiomatic) in both languages.

Answer 1

Unboxed vectors might help here:

import Data.Vector.Unboxed as U ((!), constructN, length)

coinchangev :: Int -> [Int] -> Int
coinchangev n cs = v ! n
 where v = constructN (n+1) f
       f w = case U.length w of
             0 -> 0
             m -> 1 + minimum [w ! x | x <- map (m-) cs, x >= 0]

Original code:

$ time ./CoinChange 
100000

real    0m12.543s
user    0m11.742s
sys 0m0.800s

Unboxed variant:

$ time ./CoinChange2
100000

real    0m1.598s
user    0m1.588s
sys 0m0.012s

Original C++:

$ time ./CoinChange_cpp 
100000

real    0m0.084s
user    0m0.072s
sys 0m0.012s