Solver model speeds

[hpesoj]

I'm having some trouble getting the expected results from the different solvers models in Newton 2.04. I have a demo set up in which there are 100 stacks of boxes, each 10 (EDIT: not 20!) boxes high. I have switched auto sleep off, and these are the resultant frame rates for the various solver models.

Physics off: 550
Exact: 42
Adaptive: 23
Linear (2): 20
Linear (16): 8

I am not sure what is going on . I do the same test in Newton 1.53 with the exact same setup, and the results are more reasonable, though there isn't no noticable difference between the first three settings.

Physics off: 550
Exact: 60
Adaptive: 60
Linear (2): 60
Linear (16): 40

If there something I am missing? My setup is very basic.

[Julio Jerez]

so you found 1.53 is faster than 2.00?
That is not posible, and even if it was, 1.53 is history there is not coming back.

2.0x is the official SDK

[hpesoj]

So I guess that you have no idea why this could be happening? The fact that 1.53 is faster in my test is secondary to the fact that the speeds of the solver models are the reverse of what they should be! Something is clearly wrong, but I have no clue what. If I cannot find a solution I will release a demo for others to try.

[hpesoj]

Ok, those previous results were with platform architecture 0 (default). I set platform architecture to 1 or 2 and these are the results:

Exact: 66
Adaptive: 38
Linear (2): 36
Linear (16): 16

Has anyone else encountered behaviour like this?

[JernejL]

Can you post the code to your benchmark app? the results are impossible.

[hpesoj]

Delfi - Indeed I can, I just created one .

Ok, I've created a small example program for Visual C++. Basically, it creates a floor with 10x10x10 stacks of boxes. I then count how many 1/60th of a second calls to NewtonUpdate can be performed per second. You have to change the solver model in-code and run again to test the different cases. These are how my figures level out (approximately):

Exact: 124 per second
Adaptive: 62 per second
Linear (2): 60 per second
Linear (4): 60 per second
Linear (8): 54 per second
Linear (16): 45 per second

http://dbpnewton.origo.ethz.ch/system/files/newton_benchmark.zip

Copy Newton.h, newton.dll and newton.lib into the project folder.

Basically, I want to know a) whether I am doing anything stupid, and b) what other people are getting, and whether this is normal. I really appreciate it if anyone takes the time to try this out.

[Julio Jerez]

you are the first person I know tha found everything backward.

The is not way that the exact mode in 1.53 is fasters of a mode, include linear in 2.04 it is simple imposible.

[hpesoj]

you are the first person I know tha found everything backward.

The is not way that the exact mode in 1.53 is fasters of a mode, include linear in 2.04 it is simple imposible.

This is why I would like someone to try out the benchmark I uploaded. If at least someone can confirm that they get the expected results, I can go about determining why my results are anomylous.

[hpesoj]

I will note also that, although this is the case with static stacks of boxes, the adaptive solver is very fast compared to the exact solver if you start the stacks toppling; the exact solver can almost completely come to a halt with lots of bodies in motion, while the adaptive solver will chug along nicely at around 10 fps.

However, in both scenarios, the linear solver is slower than the adaptive solver.

[Julio Jerez]

you just have to let 1.53 go. It is in the pass the future is 2.0x
There are many many reason for that.
for example 1.53 solver can not be ported to High performance computing.
The same solver that is in 1.53 is also in 2.0x

[Stucuk]

It looks like he is right. I recreated his test in Delphi and 2.06 and 2.03 are slower with a 10x10x10 box stack. Note that when Autosleep is turned on 1.53 is still faster.

You can download the source + "Interactive" (As in you can set the PlatformArchitecture, SolverModel and AutoSleep at runtime) Applications for 1.53, 2.03 and 2.06 below. Included is all DLL's, etc.

- Download ~1.65MB

P.S I Still don't believe the results... Tho ill definatly still stick to 2.0 range.

[hpesoj]

@Stucuk - I'm starting to think I just misunderstand how the solver models work (see below). Also, I'm pretty sure NewtonSetSolverModel in 1.53 does absolutely nothing (though everyone except me probably already knew this).

[EDIT]Quite a nice program Stucuk. Apparently there is some difference for solver model 2.[/EDIT]


@Julio - I shouldn't have mentioned 1.53, my problem isn't that 2.0x doesn't behave like 1.53. I have tried various setups of stacks using both 2.0x and 1.53, and and the 1.53 exact solver behaves far more erratically, and crashes with high numbers of bodies (you must have changed something for 2.0!). Thus, as you say, it is pointless to waste time comparing 1.53 to 2.0x. Forget I ever mentioned 1.53 .

My actual problems/questions were/are as follows:

1) I have found that in scenes with perfect upright stacks of boxes which aren't toppling, the exact solver is faster than the adaptive and linear solvers. Once the stacks are set toppling/moving, the exact solver becomes very slow, and with imperfect stacks (small random offset added to each box) exact and adaptive perform about the same. Now that I think about it, this probably makes sense: I'd imagine that an exact solver will be able to solve "perfect" systems like this very easily, more easily than the adaptive and linear solvers. This is just speculation, so I would very much like to hear what you have to say Julio.
2) The linear solver, even when performing only 2 iterations, is never faster than the adaptive solver. Perhaps the linear solver doesn't provide much of a performance increase with rigid body collisions and stacking? Is the linear solver only designed to speed up joint operation? (I haven't tried stress tests with joints yet)

I would really like to have answers to these questions so I can perhaps stop worrying that something is wrong, and go and do something more productive with my time .

Thanks.

[Julio Jerez]

It looks like he is right. I recreated his test in Delphi and 2.06 and 2.03 are slower with a 10x10x10 box stack. Note that when Autosleep is turned on 1.53 is still faster.
You can download the source + "Interactive" (As in you can set the PlatformArchitecture, SolverModel and AutoSleep at runtime) Applications for 1.53, 2.03 and 2.06 below. Included is all DLL's, etc.

I run the test and yes you are right 1.53 is about twice as fact.
These totally correct, 1.53 have and exact solver, and mean a real complementary solver it is not a joke.
If you have simple stacked of bodies that are just resting, there the solve will be fasters than anything
This Is explained by the time complexity of the solver which goes from linear to quadratic.
So in a small stack when the bodies have zero velocity, and they are in perfect equilibrium after the first pass the solver only do one pass, to calculate the forces since the force of the previous frame do not change.
However of the bodies in the stack are moving then the solver can take unto n x n passed to find the solution.
In 2.0x the solver is a linear time complexity by it is not an exact solver, so since the number of passes if fix even if the stack is at rest.

@Stucuk - I'm starting to think I just misunderstand how the solver models work (see below). Also, I'm pretty sure NewtonSetSolverModel in 1.53 does absolutely nothing (though everyone except me probably already knew this).

This is no true solver model are different in 1.53 you do no notic ethe diffrence becaus eyou are testion a scen that is mostly static.
Basically you are measuring teh idle peroformance ef the engiene. which in 1.53 is amost zero.
2.04 is desegned for working with multicores, therefore some algothsmm clevermeness have to be given up for teh sake of data parallelism.

@Julio - I shouldn't have mentioned 1.53, my problem isn't that 2.0x doesn't behave like 1.53. I have tried various setups of stacks using both 2.0x and 1.53, and and the 1.53 exact solver behaves far more erratically, and crashes with high numbers of bodies (you must have changed something for 2.0!). Thus, as you say, it is pointless to waste time comparing 1.53 to 2.0x. Forget I ever mentioned 1.53 .

This is right 1.53 will crash of you stack more than 512 bodies in one pile. The spedd will be so slow the it poinless to use it. Remember 1.53 was release in 2003 at a time the stack of 100 bodie was unthinkable until some people came up with pseudo Laws of physics to make commercial engines that do not really work.

I have found that in scenes with perfect upright stacks of boxes which aren't toppling, the exact solver is faster than the adaptive and linear solvers. Once the stacks are set toppling/moving, the exact solver becomes very slow, and with imperfect stacks (small random offset added to each box) exact and adaptive perform about the same. Now that I think about it, this probably makes sense: I'd imagine that an exact solver will be able to solve "perfect" systems like this very easily, more easily than the adaptive and linear solvers. This is just speculation, so I would very much like to hear what you have to say Julio.

As you noticed this is quite correct.
And it it explained by the time complexity of the solver algorithm.
To make an analogy say the you have a let up compare insertion sort to radix sort.
If you have need to sort and array constantly I will chose insertion sort because if the change are not too many insertion source work in linear time, and force a perfect sorted array is work in one pass.
However insertion sort have a quadric time complexity for random permuted arrays.
Radix sort on the other hand have a linear time complexity by it is high fix cost, since you will have to make a minimum of 5 passes for and 32 bit key array plus it requires extra space.
So Insertion sort for array that are almost organized will smoke Radix sort, but it will lose big time for random arrays.
It is the same with a complementary solver if the solution of eth previous frame is exact, and the state of each body doe no change form frame to frame the 1.53 will find a solution in one pass.
However if the state of eth bodies are changing then 1.53 will spend upto N passes to find the exact solution, by that solution will no help on the ned frame solution.

The linear solver, even when performing only 2 iterations, is never faster than the adaptive solver. Perhaps the linear solver doesn't provide much of a performance increase with rigid body collisions and stacking? Is the linear solver only designed to speed up joint operation? (I haven't tried stress tests with joints yet)

There is no such thing as adaptive solver in 2.0x
There are not difference between joint and collision in Newton, you can see in the interface than the pointer to a joint is the same as the pointer to a contact.
The only different is that contact joint are managed by the collision system internally.
In 1.53 the there is a big difference between adaptive and exact solver, they both have quadratic time complexity, but the algorithm for calculation friction forces in the exact solver is part of the solver, and it make take a like more steps. Exact solver is a one pass solver that calculate friction and normal forces at once.
In the adaptive solver is a two pass solver, is used the solution form previous frame to calculate the normal forces, then using the new forces and the friction from the previous frame is execute another pass for calculation all the forces.
This reduces the number of passes especially on stack that are unstable, but it can be slower tah the exact solver if the body motion is too fast.
The linear solve limited the number of passes of eth exact solver to a fix value and return with and approximation of the solution.
In 2.0x the linear solver is a complete iterative algorithm, some setting solve mode to one execute one pass, setting to 2 do tow passes and so on.
The exact solver is the same as it was in 1.53 with some bug fixed.
All in all 2.0x is by far superior than 1.53 saying that 1.53 is faster is the equivalent to saying the Bubble sort is faster than Quick sort when this is only they for a very special case.

[hpesoj]

Thanks for the reply Julio, that has cleared up a lot of things.

I didn't realise at all that the adaptive solver didn't exist in 2.0x, the Wiki page led me to believe it did. So in Newton 2.0x, solver model 0 is exact, any any other number N will perform N iterations of the iterative solver. I'll update the wiki to reflect that.

EDIT

While I'm at it, does NewtonSetFrictionModel act the same as in 1.53?

[Julio Jerez]

While I'm at it, does NewtonSetFrictionModel act the same as in 1.53?

only for the exact solver.
firction values are always calculated in each frame now.