Matlab - How to compare two algorithms in MATLAB

Author

How to compare two algorithms in MATLAB

hollowspook

2007-03-30, 10:09 pm

Hi, all

In lower version of MATLAB, we can compare two algoritm by flops
function. But now, this function is no longer practical because of
optimized BLAS.

Another way is by CPU time. However MATLAB is a interpreted language,
it seems not exact to use CPU time to compare them.

Then is there any other way to compare two algorithms in MATLAB?

Thanks

Sam

Konstantinos Konstantinidis

2007-03-31, 8:10 am

I think the fellow means if you can do it automatically in Matlab. I
actually had the same problem since R12 so i had to do everything by hand.
Is there actually some way to count operations in Matlab? I found a program
that counts flops but that is outside matlab and surely conciders some
background programs and windows as well, so it is not objective.
Flops was really nice...

"Nasser Abbasi" <nma@12000.org> wrote in message
news:bQlPh.104584$115.87373@newsfe10.phx...
>
> "hollowspook" <hollowspook@gmail.com> wrote in message
> news:1175305394.228186.17320@y80g2000hsf.googlegroups.com...
>
> One way to measure algorithm performance is to do arithmetic operations
> count.
>
> Normally only long operations are counted. These are division and
> multiplication. So you will get a big O measure of your algorithm in
> terms of the problem dimensions. Do this for both algorithms and you can
> see which is faster.
>
> hth
> Nasser
>
>

John D'Errico

2007-03-31, 8:10 am

Konstantinos Konstantinidis wrote:
>
>
> I think the fellow means if you can do it automatically in Matlab.
> I
> actually had the same problem since R12 so i had to do everything
> by hand.
> Is there actually some way to count operations in Matlab? I found a
> program
> that counts flops but that is outside matlab and surely conciders
> some
> background programs and windows as well, so it is not objective.
> Flops was really nice...

All would be good if flops actually
was correct. It is no longer applicable.
Its not just that they capriciously
decided to make your life miserable.

For example, do you KNOW how many
flops are involved in a single
matrix multiply? Do you KNOW it?
Are you sure? Try out the following
code. While it is executing, do NOT
even touch your mouse. If you have a
fast computer, allow N to go a little
larger.

figure
N = (5:250)';
t = zeros(length(N),2);
M = 20;
for i = 1:length(N)
A = rand(N(i));
B = rand(N(i));
for L = 1:2
tic;
for j = 1:M
C = A*B;
end
t(i,L) = toc;
end
end
loglog(N,t,'-o')
grid on

Note that the plot produced should
be linear. There should not be any
repeatable dips, bumps, jiggles. Yet
there will be exactly that.

These intriguing artifacts will be
repeatable. Note that there are two
curves plotted. If you run it again,
the same bumps appear. There are even
dips, where increasing the size of the
matrices causes a significant decrease
in the time required.

Worse, this behavior will vary depending
on what cpu you have, how much ram you
have, how large are the various caches
your cpu has, etc. I can't even imagine
what effect a multi-threaded blas call
does to this mess.

This behavior cannot be predicted by
the simple O(N^3) theoretical number
for the flops count.

THERE IS A REASON WHY THEY DROPPED
FLOPS.

John

hollowspook

2007-03-31, 7:09 pm

yep, I know why flops function is obsolete. However If I really want
to compare two algorithms, can I use the following process?

1=2E Program them in a Compiled Language like Fortran, C++,....
2=2E Run the program on same machine
3=2E Compare the CPU time they take and the memory they need .

Or is there better practical method?

Sam

On 3=D4=C231=C8=D5, =CF=C2=CE=E76=CA=B154=B7=D6, "John D'Errico" <woodch...=
@rochester.rr.com> wrote:
> Konstantinos Konstantinidis wrote:
>
>
> All would be good if flops actually
> was correct. It is no longer applicable.
> Its not just that they capriciously
> decided to make your life miserable.
>
> For example, do you KNOW how many
> flops are involved in a single
> matrix multiply? Do you KNOW it?
> Are you sure? Try out the following
> code. While it is executing, do NOT
> even touch your mouse. If you have a
> fast computer, allow N to go a little
> larger.
>
> figure
> N =3D (5:250)';
> t =3D zeros(length(N),2);
> M =3D 20;
> for i =3D 1:length(N)
> A =3D rand(N(i));
> B =3D rand(N(i));
> for L =3D 1:2
> tic;
> for j =3D 1:M
> C =3D A*B;
> end
> t(i,L) =3D toc;
> end
> end
> loglog(N,t,'-o')
> grid on
>
> Note that the plot produced should
> be linear. There should not be any
> repeatable dips, bumps, jiggles. Yet
> there will be exactly that.
>
> These intriguing artifacts will be
> repeatable. Note that there are two
> curves plotted. If you run it again,
> the same bumps appear. There are even
> dips, where increasing the size of the
> matrices causes a significant decrease
> in the time required.
>
> Worse, this behavior will vary depending
> on what cpu you have, how much ram you
> have, how large are the various caches
> your cpu has, etc. I can't even imagine
> what effect a multi-threaded blas call
> does to this mess.
>
> This behavior cannot be predicted by
> the simple O(N^3) theoretical number
> for the flops count.
>
> THERE IS A REASON WHY THEY DROPPED
> FLOPS.
>
> John

John D'Errico

2007-03-31, 7:09 pm

hollowspook wrote:
>
>
> yep, I know why flops function is obsolete. However If I really
> want
> to compare two algorithms, can I use the following process?
>
> 1. Program them in a Compiled Language like Fortran, C++,....
> 2. Run the program on same machine
> 3. Compare the CPU time they take and the memory they need .
>
> Or is there better practical method?

Of course you can try to compare a
basic algorithm that way.

Just don't expect your results to be
either exact or always comparable to
the same algorithm of a different cpu,
or even across different releases of
matlab. Also, if you program the
algorithm in a compiled languiage,
DON'T expect the results to be
equivalent to that in matlab, as
there will be algorithmic differences
in the underlying calls between your
compiled code and what Matlab does.
Also, use of a compiled code separate
from Matlab may be VERY different from
the same algorithm in Matlab, since
Matlab will have additional overhead
that the compiled code will not. Thus
if you need to grab a large contiguous
block of ram, it may be harder to do
if you have Matlab in memory already.
So Matlab might need to go out to
virtual memory at different times.

Don't forget that they are always
looking for improvements to the JIT
acceleration, as well as now in
multi-threaded blas calls, so the
Matlab release is quite important in
the speed you will see.

John

hollowspook

2007-03-31, 7:09 pm

On 3=D4=C231=C8=D5, =CF=C2=CE=E79=CA=B151=B7=D6, "John D'Errico" <woodch...=
@rochester.rr.com> wrote:
> hollowspook wrote:
>
>
>
>
> Of course you can try to compare a
> basic algorithm that way.
>
> Just don't expect your results to be
> either exact or always comparable to
> the same algorithm of a different cpu,
> or even across different releases of
> matlab. Also, if you program the
> algorithm in a compiled languiage,
> DON'T expect the results to be
> equivalent to that in matlab, as
> there will be algorithmic differences
> in the underlying calls between your
> compiled code and what Matlab does.
> Also, use of a compiled code separate
> from Matlab may be VERY different from
> the same algorithm in Matlab, since
> Matlab will have additional overhead
> that the compiled code will not. Thus
> if you need to grab a large contiguous
> block of ram, it may be harder to do
> if you have Matlab in memory already.
> So Matlab might need to go out to
> virtual memory at different times.
>
> Don't forget that they are always
> looking for improvements to the JIT
> acceleration, as well as now in
> multi-threaded blas calls, so the
> Matlab release is quite important in
> the speed you will see.
>
> John

That's right. With different CPU(AMD Athlon 64 processor 3200+ and
Intel Core 2 Duo T5600), I once get opposite results. Maybe the
results by more advanced cpus and larger memory are more
acceptable.

Anyway all seem that comparison between algorithms is a very
complicated work. Many factors have to be considered.

Sam

John D'Errico

2007-03-31, 7:09 pm

hollowspook wrote:
> That's right. With different CPU(AMD Athlon 64 processor 3200+ and
> Intel Core 2 Duo T5600), I once get opposite results. Maybe the
> results by more advanced cpus and larger memory are more
> acceptable.
>
> Anyway all seem that comparison between algorithms is a very
> complicated work. Many factors have to be considered.

Artifacts and differences between more
advanced cpus will be larger, not smaller.

This is because each cpu will have its
own pathways for the operations. If one
cpu has pipelined processing and the
other does not, this will make a huge
difference. The number of cores and how
they interact with each other and memory
will be crucial.

John

Nasser Abbasi

2007-03-31, 7:09 pm

"hollowspook" <hollowspook@gmail.com> wrote in message
news:1175353087.377434.145440@y66g2000hsf.googlegroups.com...

"Anyway all seem that comparison between algorithms is a very
complicated work. Many factors have to be considered."

this is useful, lecture on
Analysis of Algorithms

http://www.cs.cmu.edu/~pattis/15-1X...s/aa/index.html

Sponsored Links