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 -- http://mail.python.org/mailman/listinfo/python-list
