About alternatives to Matlab

[Filip Wasilewski]

Jon Harrop wrote:
> Filip Wasilewski wrote:
> > Besides of that this code is irrelevant to the original one and your
> > further conclusions may not be perfectly correct. Please learn first
> > about the topic of your benchmark and different variants of wavelet
> > transform, namely difference between lifting scheme and dwt, and try
> > posting some relevant examples or use other topic for your benchmarks.
>
> Your lifting implementation is slightly longer and slower than the
> non-lifting one but its characteristics are identical. For n=2^25 I get:

Jon, both Python and Matlab implementations discussed here use the
lifting scheme, while yours is a classic convolution based approach.
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.

What's more, taking only very big input 'n' gives only very limited
information about true performance. How do you think who is faster, a
sprinter or a long distance runner? If you want to draw objective
conclusions about algorithm implementation you should measure timing
and memory usage characteristic for different input lengths. 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?

> 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? I don't think you would be much happier to see totally
obfuscated golf one-liners.

> > Neglecting this issues, I wonder if it is equally easy to juggle
> > arbitrary multidimensional arrays in a statically typed language and do
> > operations on selected axis directly from the interactive interpreter
> > like in the NumPy example from my other post -
> > http://groups.google.com/group/comp.lang.python/msg/a71a5bf00a88ad57 ?
> > I don't know much OCaml so it would be great if you could elaborate on
> > this.
>
> 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 this specific context (discrete wavelet transform benchmark), I'd have
> >> said that speed was the most important thing after correctness.
> >
> > Not necessarily, if you are doing research with different kinds of
> > wavelets and need a general, flexible and easily adaptable tool or just
> > the computation speed is not considered a bottleneck.
>
> Brevity is probably next.

Memory usage, development time, cost, portability, scalability,
readability, level of abstraction, usage experience and many many
others, not necessarily in this order. I do not intend getting into
advocacy of any specific language or feature here. 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.

> > Please don't make this discussion heading towards `what is the fastest
> > way of doing d4 transform and why OCaml rules` instead of `what is the
> > optimal way of doing things under given circumstances and still have a
> > free afternoon ;-)`.
>
> Comments like that seem to be based on the fundamental misconception that
> writing C++ like this is hard.

Not harder than writing a loop in bazillion of other languages. When
developing software do you only count time spent on typing because you
are idle during build process?

> Here's my complete OCaml:
...
> and C++:
> #include <vector>
...

You didn't mention your platform and compiler settings. 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.

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".

cheers,
fw