About alternatives to Matlab

[Jon Harrop]

Filip Wasilewski wrote:
> Jon, both Python and Matlab implementations discussed here use the
> lifting scheme, while yours is a classic convolution based approach.

I've done both in OCaml. The results are basically the same.

> These are two *different* algorithms for computing wavelet transforms.
> Although they have similar names and give similar results, it does not
> mean you can use them interchangeably in one benchmark! It just does
> not make sense.

It makes sense because they solve the same problem. When you're comparing
non-trivial problems between disparate languages you are not likely to use
the same algorithms. Using built-in hash functions is an obvious example.

> What's more, taking only very big input 'n' gives only very limited
> information about true performance.

I've presented times for 2 different "n". I agree that it would be better to
present infinite different "n" but I only had finite time.

> If you want to draw objective
> conclusions about algorithm implementation you should measure timing
> and memory usage characteristic for different input lengths.

I did. The results are unsurprising: multi-pass (Matlab/Python) gets
comparatively slower for bigger n. Memory usage is roughly the same for
different languages.

> This will 
> also give you some idea about call overhead and possible memory
> bandwidth influence. For example, the 4-tap db2 lifting transform
> should be about 50% faster than the one using subband filtering. That's
> theory. In practice, due to specific memory usage, the speedup gained
> with reduction of number of arithmetic operations is easily wasted by
> huge cache miss overhead (C implementation, measured on x86
> architecture) for arrays which don't fit entirely in the CPU cache. See
> my point?

No. The effects you are talking about are swamped by the interpreted vs
compiled effect.

>> 1.88s C++ (816 non-whitespace bytes)
>> 2.00s OCaml (741 b)
>> 2.33s F# (741 b)
>> 9.83s Your Python (1,002 b)
>>
>> The original python was 789 bytes.
> 
> Is the byte count a standard measure you apply to describe code
> quality?

You can use bytes, lines, words, tokens or just look at the code. Whatever
you do, Python loses on this benchmark in terms of brevity, clarity and
performance.

> I don't think you would be much happier to see totally 
> obfuscated golf one-liners.

That doesn't even make sense. Squeezing code onto one line doesn't improve
byte count.

>> It is probably just as easy. Instead of dynamic typing you have
>> parametric polymorphism. If you want to make your function generic over
>> arithmetic type then you can pass in the arithmetic operators.
> 
> Probably? Using the interactive interpreter, how can I easily create
> two n-dimensional arrays of arbitrary data type, add them and multiply
> by 17?

In F#:

  open Math.Matrix.Generic
  let a = init n m (fun i j -> ...)
  let b = init n m (fun i j -> ...)
  17. $* (a + b)

In OCaml you'd either use an array of arrays and define your own functions
over them, or you'd use the built-in Bigarray.Array2 and define some
functions over that. Either way, you have to use different operator names
for different types. You'd end up with something like:

  open Array2
  let a = init n m (fun i j -> ...)
  let b = init n m (fun i j -> ...)
  17. $* (a +: b)

> I just prefer fair
> comparisons and clean use cases instead of marketing like that and I
> don't believe anyone will buy your story about OCaml superior brevity
> after seeing one fairly irrelevant loop with few arithmetic operations
> as a killer argument.

Sure. There are lots of other examples of OCaml's brevity out there:

  http://www.ffconsultancy.com/free/ocaml
  http://www.ffconsultancy.com/free/sudoku
  http://www.ffconsultancy.com/free/maze
  http://www.ffconsultancy.com/free/ray_tracer

and now F#:

  http://www.ffconsultancy.com/dotnet/fsharp/

>> Here's my complete OCaml:
> ...
>> and C++:
>> #include <vector>
> ...
> 
> You didn't mention your platform and compiler settings.

2.2GHz Athlon64 x2 with 2Gb RAM running Debian Linux.

g++ -O2
ocamlopt

> Using vector 
> at() method instead of plain C/C++ array indexing increases the timings
> by factor of ~1.5 to 10 or more (GCC, MSVC), depending on the
> optimizations set, so it doesn't seem to be the best possible solution.

Bounds checking is <1% slower with GCC and only 14% slower with MSVC.

> I was also unable to run your OCaml example for n >= 2^21 (win32, out
> of the box OCaml installation). Is there some 16MB memory limit imposed
> on Array?
> # let q = Array.make (1 lsl 21) 0.0;;
> Exception: Invalid_argument "Array.make".

On 32-bit, yes. You'd either have to use a different data structure
(Bigarrays), upgrade or switch to F#.

-- 
Dr Jon D Harrop, Flying Frog Consultancy
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists/index.html?usenet