Add some benchmarks functions to have an idea on the efficiency of the algorithm on different sizes of matrices.
… and change the call in main …
When benchmarking for a specific matrix size, test different matrices in order to avoid falling on special cases.
Try to port benchmarks to other systems than OS X. ATTENTION: This file commit not compile on system different than OS X.
Complete the port of benchmarking functions. It compiles on Ubuntu with gcc 4.6, still have to check on OS X
Fix the preprocessor variable name that was mistyped.
Turn gcc optimization on
Remove a useless test in the breakpoint binary search + fix a bug (the index has to be initialized to iMin instead of 0: if iMin = iMax, we never enter the loop and we haven't set i properly …)
Do not decrement an size_t (aka unsigned long) unless you know that it is > 0
Commit a useless assert, especially when it comes to benchmarking (huge loss of time).
Improve the function that finds the crossing breakpoint. It now tries to limit the spread of the binary search when searching for the breakpoint for a given position. For the multi size benchmark for sizes up to 300x300 (by steps of 20 and 50 sample matrices), it improves the performances of the function by 25%
Use the fastest implementation of queries on one column and a range of rows to improve the efficiency of the interval maxima building phase (it speeds up this phase by a factor almost 2).
Change the way we initialized the breakpoints vector: instead of creating an empty one and pushing some elements in it, compute the size of the new envelope, initialize an according vector an put the breakpoints at their right index.

This speeds up the mergeEnvelope function by 25% on the "standard" 300x300 benchmark.
Use assertions that are enable only in debug mode. It seems to be interesting from a performance point of view, especially when querying a value of a matrix.
Use inlining for some accessors.
Use the fastest implementation of the single position query.