Bad Performance

Posts that don't fit into other categories.
x33
Posts: 3
Joined: Sat Nov 04, 2017 3:19 pm

Bad Performance

Postby x33 » Sat Nov 04, 2017 3:58 pm

Hi,

I was porting my project with my simple rudementary physics solution to this engine. My app just moves a bunch of rectangles around in a box with zero gravity. When they are hitting an edge they get accelerated into another direction. Before I used a brute force solution comparing every object with one another, which obviously takes a lot of time (n^n).
At 5000 moving objects on an i5 4x3.2Ghz and 200 moving objects on an Exynos Octa 7580@8x1.6Ghz this solution started to stutter visibly.

Now with dyn4j I get 1/5 of that performance?*
I set the BroadphaseDetector to return false by default to disable collisions, or it gets even worse!. Running the profiler shows dyn4j is enormously often checking for body.isStatic() (10-30 % of total computation time ???) and another 50 % goes just into the broadphase.detect and aabb.update methods.
Especially on Android this is a little bit annoying with less then 30 moving objects allowed before it breaks visibly.
I did all the performance tips on this site except using SapIncremental instead of DynamicAABB, which seems to be not included anymore. Using just "Sap" results in completly awful performance.

Normally I would have expected an AABB Tree to ease performance constraints when it comes to collision detection, not the other way around :(
I do not expect an easy solution or anything, I just wanted to give a headsup on my results. My examination: If you plan to use dyn4j on Android: do not. Sadly I cant tell you anything about other 2D simulations. Native Box2D/LiquidFun is pretty annoying to use in Java.


(*) It should be noted that dyn4j is running in its own thread. It is really just dyn4j.

William
Site Admin
Posts: 373
Joined: Sat Feb 06, 2010 10:23 pm

Re: Bad Performance

Postby William » Sun Nov 05, 2017 7:07 am

Thank you for the feedback. Can you please post a runnable reproduction case so that we can validate this? Saying don't use dyn4j without supplying anything for us to confirm, and potentially resolve, your claim is a bit unfair.

5000 is a lot, and I don't think any physics library would recommend having that many bodies in a simulation at one time, but dyn4j should be better than brute force in any scenario.

I've run simulations with 200 moving bodies with performance well above 1000 fps, on a 4 year old pc. I have seen a noticeable difference between AMD and Intel when running any performance related Java application, with AMD far worse. I've also noticed that Java rendering time can skew performance figures drastically. For example, running dyn4j just as a console application, it has no noticeable impact on performance with a 1000 bodies.

William

zoom
Posts: 144
Joined: Sun Mar 17, 2013 3:57 pm
Location: Stockholm, Sweden
Contact:

Re: Bad Performance

Postby zoom » Sun Nov 05, 2017 7:47 am

I too would like to reproduce this and find the bottleneck, it would be really helpful if you could provide a test to illustrate this. Maybe it is a use-case that can be optimized in many ways but it is impossible to tell.

x33
Posts: 3
Joined: Sat Nov 04, 2017 3:19 pm

Re: Bad Performance

Postby x33 » Sun Nov 05, 2017 4:25 pm

William wrote:Saying don't use dyn4j without supplying anything for us to confirm, and potentially resolve, your claim is a bit unfair.

5000 is a lot, and I don't think any physics library would recommend having that many bodies in a simulation at one time, but dyn4j should be better than brute force in any scenario.

I am sorry, you are right. Sadly, I can't yet provide a simple demo (yet) as the program runs on a licensed multithreading environment that ensures that dyn4j is completly decapsulated from OpenGL and any other calculations in its own thread. I am mostly concentrating on Android right now.

Some results I made: (100 moving 10x10 rectangles in a 100x100 zero gravity box)
- I could squeeze out additional 17-20 % performance (from 300-310 ms to 240-250 ms per cycle) on Android 6 due to reduction of object allocation/deallocation in dyn4j by simply reusing AABBs and Vector2 objects in the DynamicAABBTree.insert() method like this:

Code: Select all

// union the new node's aabb and the current aabb
         AABB union = aabb.getUnion(itemAABB);
         
         // get the union's perimeter
         double unionPerimeter = union.getPerimeter();

Code: Select all

// union the new node's aabb and the current aabb
         AABB union = aabb.getUnion(aabbPrivateBuffer, itemAABB);
         
         // get the union's perimeter
         double unionPerimeter = union.getPerimeter();

Above is the old code, below the new one. aabbPrivateBuffer is instantiated once as final. Instead of creating a new AABB object in AABB.getUnion, it stores the result in the buffer. DynamicAABBTree.insert() gets called very often and AABB and Vector2 objects are instantiated a lot in it, so these are some easy fixes with an relative big impact.
Theoretically and according to Google, with Android 8 and the improvments to its ART VM this effect should mitigate by 80 %.

Sadly this is not very well written Java code and something like that should be rather the task of the JVM to solve. Yet, this is how it works on Android as of now - worse maintainable but faster.

The same goes for other often used methods by modifying the methods to take a storage object instead of creating a new instance.

Code: Select all

void class foo( double x, double y ) {
   return new Vector2( x, y );
}

Code: Select all

void class foo( double x, double y, Vector2 storageBufferOrWhatever ) {
   if( storageBufferOrWhatever == null )
      storageBufferOrWhatever = new Vector2();
   storageBufferOrWhatever.set( x, y );
}


I am still diving into the code base to find out which objects can be easily reused (are not further stored and reused outside the stack).
I am playing around with an additional object pool for DynamicTreeNodes as they are one of the major allocated objects and they cause multiple AABB and Vector2 allocations as well. However object pools also have an overhead not necessarily better against simple plain allocation and garbage collection.

There doesn't seem to be that much left for easy improvements beyond this point, though.

Besides that I am trying to find out why this

Code: Select all

type == MassType.INFINITE

is so expensive (30 % of computation time in 5 s) according to the Android profiler. Either this part gets called an immensly lot of times (this should cause nearly no overhead at all) or this is just a device and/or Android 6 specific thing. I am going to try this out on another device with another Android version.
Also I wonder if the result of body.isStatic can be stored without destabilizing the engine.

I am going to keep you updated with my progress.

zoom
Posts: 144
Joined: Sun Mar 17, 2013 3:57 pm
Location: Stockholm, Sweden
Contact:

Re: Bad Performance

Postby zoom » Mon Nov 06, 2017 4:51 am

Allocation free methods are great and I think users of Dyn4J would benefit from them. One thing I learned form looking at other libraries that work hard to avoid allocations (like JOML, jMonkeyEngine et.c) is that on the one hand you want immutable value holders and on the other hand you want to avoid allocating new objects. So you end up with a lot of methods, something like:

Code: Select all

class Vector2d {
   // Immutable version
   Vector2d multiply(Vector2d other) { return new Vector2d(....); }
   // Immutable version with primitives
   Vector2d multiply(double x, double y) { return new Vector2d(....); }
   
   // Mutable version to avoid allocating new object
   Vector2d multiplyLocal(Vector2d other) { return this.x=... return this; }
   // Mutable version with primitives to avoid allocating new object
   Vector2d multiplyLocal(double x, double y) { return this.x=... return this; }
 
   // version with 'out' arg
   void multiply(Vector2d other, Vector2d result) { result.set(....); }
   // version with 'out' arg and primitives
   void multiply(double x, double y) { result.set }
}


And repeat for div/cross/dot et.c

A consistent scheme for naming and return values is really important. Like should a method that takes an 'out' parameter also return it to be able to chain calls?

Code: Select all

   Vector2d multiply(Vector2d other, Vector2d result) { return result.set(....); }


or as in your example if the provided 'out' parameter is null should it allocate a return value instead or throw an error? I think whatever strategy is fine as long as it is consistently implemented.

William
Site Admin
Posts: 373
Joined: Sat Feb 06, 2010 10:23 pm

Re: Bad Performance

Postby William » Mon Nov 06, 2017 9:10 pm

Thank you for the additional details. I'm very interested in how different the performance is on Android 8 as you mentioned (dyn4j relies heavily on small object allocation). If you would be so kind to keep us updated that would be appreciated!

We could introduce some object pooling, but my fear here is that this pattern was considered an anti-pattern a long time ago. It sounds like Android is behind on this though due to the garbage collector. That's why I'm interested in the performance on Android 8. We could also do some optimization like you describe, but as you say, it increases maintenance and decreases readability.

All that said, we may be able to address some object allocation issues without too many downsides. For example, your issue with the AABB allocations in the DynamicAABBTree. I have made a few changes so that much less AABBs should be generated. Can you try with the attached jar to see if performance is better than 3.2.4? The changes just involved using a method local and/or reusing an existing instance of the AABB were possible - so no additional maintenance cost, but maybe a slight readability loss.

I'd be happy to take a look at any other spots where the profiler says it's spending it's time.

Thanks,
William
Attachments
dyn4j-v3.2.5_rc1.jar
dyn4j 3.2.5 rc1
(370.45 KiB) Downloaded 23 times

x33
Posts: 3
Joined: Sat Nov 04, 2017 3:19 pm

Re: Bad Performance

Postby x33 » Wed Nov 08, 2017 7:30 pm

Thanks William, I am going to test your jar and write more detailled in the next days.

johnson
Posts: 14
Joined: Sat Apr 07, 2012 10:50 am
Contact:

Re: Bad Performance

Postby johnson » Fri Nov 17, 2017 6:36 am

I'd hate to see a nice codebase like dyn4j be polluted with object pooling. Doing that is extremely inadvisable on modern JVMs.

I'd actually advise going the other way: Use very short-lived immutable data structures as much as possible. Modern JVMs eliminate many short-lived objects when those objects are only passed to monomorphic or bimorphic call sites, and those that aren't eliminated entirely end up being deleted immediately (essentially for free) when the Eden space is collected (as long as they're actually short lived). Also, as bits of the OpenJDK Valhalla value type implementation trickle into JDK releases, codebases that are already using immutable objects throughout will find it a lot easier to transition to real value types (because value types are immutable).

TMNCorp
Posts: 6
Joined: Thu Aug 04, 2016 1:31 pm

Re: Bad Performance

Postby TMNCorp » Tue Nov 21, 2017 9:21 pm

johnson wrote:I'd hate to see a nice codebase like dyn4j be polluted with object pooling. Doing that is extremely inadvisable on modern JVMs.

I'd actually advise going the other way: Use very short-lived immutable data structures as much as possible.

While I am agreeing on that, this consensus of this topic was obviously reached, already.
However, the memory churn capability on a usual Android device is significantly lower then on PC. Allocation and deallocation is only (nearly) free as long as you stay below this rate.
Dyn4j is pretty demanding.
https://www.dynatrace.com/resources/ebo ... ry-issues/
https://developer.android.com/topic/per ... html#churn

The solution mentioned above seems to have a high impact with a small codechange, only.

William
Site Admin
Posts: 373
Joined: Sat Feb 06, 2010 10:23 pm

Re: Bad Performance

Postby William » Wed Nov 22, 2017 10:24 pm

OP - have you had chance to test these changes or to test with Android 8?

Thanks,
William


Return to “General Discussion”

Who is online

Users browsing this forum: No registered users and 2 guests