On May 11 2007, 2:28 am, Greg <edven
...@gmail.com> wrote:
> I'm trying to understand the difference between the processFrameOT and
> processFramePP functions. I thought that the OT version would be
> faster, but I'm seeing about 2-3x the speed if I use the PP version.
> I've checked with particle counts from 1000-20000.
> Am I misunderstanding the two algorithms?
Hi Gred, Gerald,
I made a similar observation. My PC : 3Ghz Athlon XP, Windows 2000,
GF5200 graphics card.
In theorie, when increasing the number of particles,
Computing time of processFramePP goes up fast (N^2),
while the computing time of processFrameOT is rising slower.
But the point is, for me the "Break Even" between these two methods is
at (roughly) 12000 particles!
I think we can expalin this. The PP method need to loop over all
particle combinations, while the OT method first groups the particles
into a tree, then computes only forces betwenn the relevant
combination.
The PP method is basicially brute-force number-crunshing (even without
needing a SQRT function !).
Gerald's OT involves recursion, dynamic memory allocating/freeing and
several square roots (diameter of a tree node, etc...). This overhead
seems very expensive, and should be a good target for optimization
efforts. OT will always be better for high numbers of particles.
Maybe it's like breaking a wall : For smaller(thinner) walls, banging
your head agains it very fastly can be more effective than solving the
problem by beeing smart. Especially if you have a hard hat ;-).
best wishes, and keep on hacking ;-)
Frank.
|
