Simulation speed changes for unkown reason

[Marc]

I haven't experimented with x64 vs. x86 yet. One argumet I heard why x64 can be slower in some cases is the instruction length. Because of the backwards compatiblity, the 64 bit
instructions are longer. So the cpu has to wait longer to get the code from the memory, which doesn't get faster by switching to x64. But then again, code is rather small compared
to the usual amount of data a programm processes so the time needed to access the code from memory should be neglectable in most cases.

I checked msdn for /fp:fast and it says: "Because the calculation involves floating-point data types that are represented in memory by less than 80 bits, however, carrying the extra bits of precision (80 bits minus the number of bits in a smaller floating-point type) through a lengthy calculation can produce inconsistent results."
Sounds like that might create trouble with determinism again. Maybe you have to set the fpu rounding mode
to 32 bits as well in code with _controlfp or _control87 to make it work?

I pmed you about the "demo" - which is actually the current state of my project.

[Julio Jerez]

Sounds like that might create trouble with determinism again.

I do not think i will create any problem with determinism, Even if teh CPU state si changed, as long as it is chege consitent;y.
The made cause problems with collision rutine take longe or lower doe to flat desition made whet a comarison is for exampl on eth poistive side or teh negative side of a plane.

I could be for example that a point test maube by large than zero vbecause in registere a Plane test in iolf with 80 bit registerd, but if teh rsult is save to memory,
teh the tunation may set teh resutl to zero.

so something like may lead

Code: Select all

val = PlaneTest (point)
if val <= 0.0) {
  //do somethong
}

to different results because now Val is zero, due to truncation.
I will put the SDK out, and see what happens
If we have problem teh I will mak eteh collison system use teh strict float bu the solver use teh fast math.
The solve do not use float comparison to make desictikon is is just a long set of brute set of float operation,
the good news is that since the solve is more than 90% of the total time in a frame, the prospect si very good.

I will check the demo, tonight:
are you in the same LA time zone?

[Marc]

No, I'm from Germany. It's 02:00 am right now over here. I'm going to sleep soon I guess

Are you sure that task switches might not lead to rounding the 80bit down at random times? I never experienced that, but sometimes people tell me that - then again, I never changed /fp:precise to something else, so maybe that's true? I don't know.

If you put the new sdk out with /fp:fast I'll for sure test it for determinism

[Julio Jerez]

Are you sure that task switches might not lead to rounding the 80bit down at random times? I never experienced that, but sometimes people tell me that - then again, I never changed /fp:precise to something else, so maybe that's true? I don't know.

Yes this is the kind of stuff the self appointed expert on Gamedev.net always come up with.
This is all made up stuff to make it look like they know things, but it is all junk sceince than come from where the sun do not shine, if you know what I mean.
I say let us try and see what happens.

I am more concerned with some malfunction than I am with the lost of the ability to reproduce same runs.

Beside the idea that truncation to 32 bits is more correct than the fast precision that uses the 80 bits in totally misleading, the fast version not only is faster it is also more accurate.
The problem is that like everything that is controlled by committee and or consensus of soem autocrats, you get a misbag of good and bad ideas.
We are still suggested to a standard that was created in 1985 by a bunch of people that had no idea of how to design hardware.
Back then, floating point operations where executed in software with integer instructions, so the more important thing was minimizing the number of operations.
Since then we have gone over 20 generations of hardware but these morons are still suggestiong hardware manufacturer to the same 754 IEEE standard than is more than 30 years old.
So they force Compiler manufaters to make the worse posible setups, the default.

I can see this fail from one PC to another PC of a different Generation for example I once read the some AMD Athlons in their quest to beat Intel they actually masked the float register to 32 bits of they use a different algorithm for some transcendent function that lead to one bit lost in precision against the Intel but tah was corrected and they are but equal now.

I would not worry about that and see what the test show.

[Julio Jerez]

Wholly Smoking

Before downloading Intel compiller, I decided to use just the option -O2 with GCC to have as baseline

Code: Select all

gcc -c -Wall -Wno-strict-aliasing -D_LINUX_VER -fsingle-precision-constant -fPIC -m64 -O2 -Idg -Iphysics -o physics/dgWorldDynamicUpdate.o physics/dgWorldDynamicUpdate.cpp   


and I got something beyond my wildest expectation, The resulting code is amost three time faster, I did it twice to make sure it is not a fluck,

The same scne in the video is now 4 to 6 misecunds and it was around 22 milisecunds before. Now the Linux 64 version is the fastest of all,
almost 50% faster than the PC 64, I posted this just to make sure it is not a dream.

All those other flags all they do is to make the compiler generate code that run slower.
Those anyone know a tool to make video in Linux Unbuntu 64?

Oh Man I feel so embarrass now, after criticizing GCC so much and in eth end GCC come back with vengeance and strike such a blow making the linux build twice as fast as the PC.
Help what do I do now?

[hpesoj]

Wholly Smoking

Haha. I had a feeling that GCC couldn't be that much worse than Visual Studio.

For video capture you could try this: http://ubuntuforums.org/showthread.php?t=294605. I haven't ever used any video capture software for Linux, so it may not be suited for capturing real time graphics.

Oh Man I feel so embarrass now, after criticizing GCC so much and in eth end GCC come back with vengeance and strike such a blow making the linux build twice as fast as the PC.
Help what do I do now?

My first thoughts would be a) see how fast GCC code runs on Windows, and b) try to see if you can find any way to improve the speed of Visual Studio code.

I'm looking forward to seeing these speed increases .

[Marc]

That's odd. For me GCC always created slower code than vc as well. I always just used gcc -O2 vs. the project defaults of vc release. But the last time I tried was around 2005 ...

This thread drifting to code speed optimizations makes me wonder if we are actually thinking about the same kind of issue we are searching. My issue is not that sometimes the cpu usage gets high but instead, the simulation gets slow, like a NewtonUpdate(0.016) only seems like NewtonUpdate(0.001) - like Bullettime in Matrix. And not using NewtonBodySetFreezeState prevents this from happening. The "demo" and the instructions are oriented towards that. I just wanted to make that clear, not that you are using the demo and searching for another effect than I wanted to show.

[JernejL]

if gcc builds are so fast, you could try offering GCC dlls on win32 aswell?

[Julio Jerez]

Woohoo, found the bug, very subtle but
You remember when you could no reproced determinism, I found one of the reason was that the
Aligment of the scene in the Multigrid Broadphase needed to be flushed as well, so I added this code.

Code: Select all

void dgBroadPhaseCollision::InvalidateCache ()
{
   dgBodyMasterList& masterList (*m_me);
   for (dgBodyMasterList::dgListNode* node = masterList.GetFirst(); node; node = node->GetNext()) {
      dgBody* body;
      body = node->GetInfo().GetBody();
      Remove(body);
   }

   for (dgBodyMasterList::dgListNode* node = masterList.GetFirst(); node; node = node->GetNext()) {
      dgBody* body;
      body = node->GetInfo().GetBody();
      Add(body);
      body->SetMatrix(body->GetMatrix());
   }

That flushes all cashes, but it have one big problem,
When a body is added to the world for teh first time, the body does not have a valid AABB for the world,
However when I remove the body from the world the AABB is still Valid because teh body is no destroyed,
The second loop adds the body to the work again, but is adds the body to the root level of the Mutigrid,
then it calls SetMatrix, but now SetMatrix when is recalculates the new AABB, it finds that it is the same as the old AABB,
Therefore it says ohh this body has not changed position and it does not need to update its position in the Mutigrid world, as a result the body state in the top layer.

The usually is not a big problem for any normal scene, but your game is like a perfect storm, because you have 909 static bodies in your scene and they old state in the root level
Since static bodies do not get any update so they then never get promoted to their correct Cell on the Mutigrid world,

So the game run almost as naive SAP, so the slow down you see is when you add a new body you call Invalidate, so after that the world is sorted with a naive insertion sort.
The Solution is to invalidate the current AABB of the body when the body removed from the world.

Code: Select all

void dgBroadPhaseCollision::InvalidateCache ()
{
   dgBodyMasterList& masterList (*m_me);
   for (dgBodyMasterList::dgListNode* node = masterList.GetFirst(); node; node = node->GetNext()) {
      dgBody* body;
      body = node->GetInfo().GetBody();
      Remove(body);

      // invalidate AABB so next add can promote the body to the correct CELL.
      body->m_minAABB = dgVector ( 1.0e10f,  1.0e10f,  1.0e10f, 0.0f);
      body->m_maxAABB = dgVector (-1.0e10f, -1.0e10f, -1.0e10f, 0.0f);
   }

   for (dgBodyMasterList::dgListNode* node = masterList.GetFirst(); node; node = node->GetNext()) {
      dgBody* body;
      body = node->GetInfo().GetBody();
      Add(body);
      body->SetMatrix(body->GetMatrix());
   }

That solves that bug, but there is more,
I noticed that your world has a vertical direction alone the z axis, The world BradPhase is designed to work best when the axis is along y,
I made that changed when I optimize the BroadPhase, I notice the a 3d Multigrid uses a lot of memory, and that the gain in speed is maginally,
so I made the the Y axis is always zero.
that put all bodies at the center layer but since teh Grid is a hash map, there ares no cell on top and bottom of the center layer.
I will add a function to indidate what axis should be Masked and that will maximize the ditribution of bodies in the mutigrid world.
I will do tha and test this afternonn.

but wait there is more still, I believe your game can run about 2 to 3 time faster since it has some many static bodies,
If you use a Scene Collision shape and you put all the stastic bodies in that shape, then it will run a lot faster because now the world will see 1 body instead of 900 static ones,
The Scene collision is liek a compound collision bu for static bodies and it is optimized for queries of dynamics bodies agains static shape,
It never worries about checking static shape against static shapes.

I think we can try that after I post 2.08 with the fix.

[agi_shi]

if gcc builds are so fast, you could try offering GCC dlls on win32 aswell?

You can find recent MinGW builds with the latest GCC for windows here: http://www.tdragon.net/recentgcc/

[Julio Jerez]

if gcc builds are so fast, you could try offering GCC dlls on win32 aswell?

That's an idea, I am going to check this more, because it looks too good to be true, this is dowubling the PC build even if the PC is SSE and mutithreading it does not make sense.
But if it does I will see how to make a GCC buidl for the PC too. I guess I will just have to adapt the Make Linux make file.

[Julio Jerez]

Ok I made the fix and nwo teh Demo run 60 fps pedal to eth metal, before I was getting 45-46 and diiping to 34 whan I was ading bodies with the leter M
Now the slowest I see is 56
I beleive that whe I add the Vertical Axis to function to the BroadPhase this will be a perpetual 60, but I have to go to work now.
I assume you are limiting the FPS to 60, because teh Highest I see is 59.9 fps,

Also I think that if you use the Scene collision then the Physics will become a non issue for this game.

[Marc]

Ok, I'm looking forward to your new version then

I notice that you world has a verycal direction alone the z axis, The worl is desigen to work best whn the axis is along y,
I made tah change when I optimiz the BradPhase, I notice the a 3d Multigrid use lot of memory, and eh gain in speed in maginally, so I make the the Y axis is alwa zero, tah put all bodis at the cenet layer by since is is a Hash map the lares on top and bottom are never used.
I will add a funtion to indidate what axis soudl be Masked an dteh will maximise the ditibution of bodies in the mutigrid world.
I will do tha and test this afternonn.

Oh, I didn't know this. Yes I prefer z up. It's just my personal preference; I think it's handy that way since the ai code is basically 2d and I can just take the first 2 values of my 3d vectors instead of taking the first and the 3rd.
For the 3d multigrid using a lot of memory: I'm not entirely sure how this works but I assume you generate a large 2d grid and sort the bodies in there and maybe do a few layers like that. So you have a memory consumption of about O(x*z). If you do that with a 3d grid you get O(x*y*z) which is a lot more. But if that grid is sparse, you can save a lot of memory by using a hashtable for it that maps from (x,y,z) to a place in the hashtable. If it's sparse, like only about O(x*z) grid blocks are full, then the memory consumption of that should be similar to the memory consumption of a simple 2d grid - and at least in games like mine, this assumption is true. Or do you already do/tried that and it's still too consuming? I posted this suggestion on another engines forum and nobody commented on that.

but wait there is more, I believe you game can run about 2 to 3 time faster since it has some many static bodies,
If you use a Scwene Collision shape and you put all the ststic bodeis in the shape, then it will run a lot faster because now the world will see 1 body instead of 900 static ones,
The Scene collsion is optimized for queries of dynamics bodies agains statioc shape, and do not worries about shaking staic shape sgaisn static shape.

[/quote]
Oh interesting. So I'll try and put it all in one compound shape.

You are right, I have vsync on, so actually your monitor frequency limits it - which is most likely 60hz.

Thanks Julia, with the speed gain of /fp:fast and your suggestions, it sounds like my game could run twice as fast or even faster.

[Julio Jerez]

For the 3d multigrid using a lot of memory: I'm not entirely sure how this works but I assume you generate a large 2d grid and sort the bodies in there and maybe do a few layers like that. So you have a memory consumption of about O(x*z). If you do that with a 3d grid you get O(x*y*z) which is a lot more. But if that grid is sparse, you can save a lot of memory by using a hashtable for it that maps from (x,y,z) to a place in the hashtable. If it's sparse, like only about O(x*z) grid blocks are full, then the memory consumption of that should be similar to the memory consumption of a simple 2d grid - and at least in games like mine, this assumption is true. Or do you already do/tried that and it's still too consuming? I posted this suggestion on another engines forum and nobody commented on that.

That is the theory but the practice is very different.
Say you have a world with say 5 bodies, five bodies is small enough that the fastest test you can possible write is the brute force one body against the rest only for tes the all. It beat SAP, it Bit Grid,
Now let us say to add these bodies in to a MultiResulution grid, and you get to bodies in one cell and few bodies on other cell.
Now you end up with tow cells in the hashmap, and tow listen the you will need to check using some kind of merge sort.
If the Gird was 3D it is possible that bodies get distributed in 3, 4 or even 5 grid, and now you have more entry in eth Hard Map with cause a lot of Rehashing because of hah collisions.
Plus you end up with lot of very small list to compare.
The 2d Cell is good enough for medium side world because if provides list that are small enough the catch coherence is better and the Hasp map do no grow as much. In fact it is conceivable to remove the Hash map all together and use a 2d array of pointed. I have no done than by I will try some time.

The closest analogy is a quick sort, if you make a quick sort and you let the inner loop go until the runs are one or two key it is much slower than stop when
the runs are say 6 to 10 elements, because a brute force insertion source in faster.
Mutigrids have the same problem if you have each body in one grid it is slower than grids with few close bodies together.

Oh interesting. So I'll try and put it all in one compound shape.

It is not a compound collision, that will be bad, it is a new Collision shape for 2.0x called SceneCollision.
It was created precisely to deal with case like yours, plus It will be a big player in future versions of the engine.

[Julio Jerez]

Ha one more thing, he engine has performance counter that can tell you the time spent on any of the major systems.
if you can use them to display that information then it will be eassy to detect when something is going wrong and also insulate what system is reponsable,