NATHANWIEGAND.COM

I had the great pleasure of attending the ICFP in 2009. I’m pretty new to the functional programming game, so it was really cool to meet the movers and shakers. I got to see Bryan O’Sullivan give this presentation on Criterion — a “robust, reliable performance measurement and analysis” package for analyzing Haskell programs. You can read Bryan’s description here.

When I first saw the Criterion presentation, I immediately thought about porting this to C. Unfortunately, I’ve been writing a dissertation and I haven’t gotten around to it yet. However, I did decide to do something that some might consider unholy. I’ve used Criterion to profile my C functions.

How to profile C with Criterion

For this example, I’m going to profile a Fibonacci heap that I’ve been working on.

We’re going to use Haskell’s Foreign Function Interface (FFI). So, let’s start with a simple header file for our test function:

/* FILE: test-fibheap.h */
#ifndef __TESTFIBHEAP__
#define __TESTFIBHEAP__
int test(int, int);
#endif

and now our test function:

/* FILE: test-fibheap.c */
#include "test-fibheap.h"
#include "fibheap.h"
#include < math.h>

int test(int n, int seed) {

  FibHeap *heap = FibHeapMakeHeap();

  int *arr = (int*) malloc(sizeof(int) * n);
  int i; 

  srand(seed);

  for(i = 0; i < n; i++) {
    arr[i] = i;
  }
  /* Insert the numbers [0, n) into the heap in a random order */
  for(i = 0; i < n-1; i++) {
    int r = rand() % (n - i) + i;
    int t = arr[i];
    arr[i] = arr[r];
    arr[r] = t;
    FibHeapInsert(heap, (double) i, 0);
  }
  /* remove all of them one at a time.  Same as sorting the array*/
  for(i = 0; i < n; i++) {
    FibHeapExtractMin(heap);
  }
  return 0;
}

This function takes two parameters, n which is how many elements to insert into the heap, and seed which is the seed to the random number generator. I don't want to use the current time as the seed because I want to be able to compare the efficiency on exactly the same structure.

Now, how to use the FFI:

{-# INCLUDE "test-fibheap.h" #-}
{-# LANGUAGE ForeignFunctionInterface #-}
module Main where
import Foreign.C -- get the C types

foreign import ccall unsafe "test" testFib ::
                  CInt -> CInt -> CInt

Of note are the first and last lines. The first line is just like #include. Then, the last line binds our C function int test(int,int) to the name testFib.

So, bringing it all together with Criterion:

{-# INCLUDE "test-fibheap.h" #-}
{-# LANGUAGE ForeignFunctionInterface #-}
module Main where
import Foreign.C -- get the C types
import Criterion.Main

-- "unsafe" means it's slightly faster but can't callback to haskell
foreign import ccall unsafe "test" testFib ::
               CInt -> CInt -> CInt

main = defaultMain [
          bgroup "fib" [bench title $ whnf (testFib n) seed]
          ]
  where
    n = 1000000
    seed = 7
    title = "testFibHeap " ++ (show n) ++ " " ++ (show seed)

Compile this with ghc -O --make profile.hs fibheap.o test-fibheap.o.
Then, run it ./profile -t png:500x175 -k png:500x175

I've run this twice. First with my fibheap code compiled without optimizations and then again with -O3

Results

Unoptimized

./profile -t png:500x175 -k png:500x175
warming up
estimating clock resolution...
mean is 9.843398 us (80001 iterations)
found 1259 outliers among 79999 samples (1.6%)
  1157 (1.4%) high severe
estimating cost of a clock call...
mean is 522.7480 ns (95 iterations)
found 3 outliers among 95 samples (3.2%)
  1 (1.1%) high mild
  2 (2.1%) high severe

benchmarking fib/testFibHeap 1000000 7
collecting 100 samples, 1 iterations each, in estimated 189.5377 s
bootstrapping with 100000 resamples
mean: 1.916353 s, lb 1.909884 s, ub 1.932393 s, ci 0.950
std dev: 48.79063 ms, lb 23.67417 ms, ub 99.28092 ms, ci 0.950
found 9 outliers among 100 samples (9.0%)
  4 (4.0%) high mild
  5 (5.0%) high severe
variance introduced by outliers: 0.998%
variance is unaffected by outliers

Optimized with -O3

./profile -t png:500x175 -k png:500x175
warming up
estimating clock resolution...
mean is 9.928848 us (80001 iterations)
found 1264 outliers among 79999 samples (1.6%)
  1150 (1.4%) high severe
estimating cost of a clock call...
mean is 522.4059 ns (95 iterations)
found 3 outliers among 95 samples (3.2%)
  1 (1.1%) high mild
  2 (2.1%) high severe

benchmarking fib/testFibHeapOptimized 1000000 7
collecting 100 samples, 1 iterations each, in estimated 67.12110 s
bootstrapping with 100000 resamples
mean: 670.1145 ms, lb 669.3443 ms, ub 671.1168 ms, ci 0.950
std dev: 4.445731 ms, lb 3.547659 ms, ub 5.887752 ms, ci 0.950
found 7 outliers among 100 samples (7.0%)
  4 (4.0%) high mild
  3 (3.0%) high severe
variance introduced by outliers: 0.990%
variance is unaffected by outliers

Post Mortem

Running the optimized test above yields:

real    0m0.722s
user    0m0.690s
sys     0m0.030s

which is comparable to the Criterion results. There's certainly an overhead involved because of the Haskell run-time, but for profiling relatively long running functions I don't think this will be that much of an issue.

I think it's worth adding to the arsenal, don't you?