Box2D Forums

It is currently Sun May 19, 2013 11:26 am

All times are UTC - 8 hours [ DST ]




Post new topic Reply to topic  [ 30 posts ]  Go to page Previous  1, 2, 3  Next
Author Message
PostPosted: Fri Jul 03, 2009 3:10 am 
Offline

Joined: Mon Sep 01, 2008 6:32 am
Posts: 101
BorisTheBrave wrote:
That's AWESOME. Can it handle vectorizing expressions ( a*b+c) and matrices?


It can't handle all possible expressions yet, but I'm going to add matrices support pretty soon. Don't know how long this will take -- it seems like I may have to do a rewrite to make it more flexible.


Top
 Profile  
 
PostPosted: Sat Jul 04, 2009 5:47 am 
Offline

Joined: Mon Sep 01, 2008 6:32 am
Posts: 101
The refactoring is done. It should now be more robust and I can start adding matrix support.

Expressions like (v2 - v1) dot v3 are not fully supported yet. They may actually become worse ATM, but I'm planning to add support for creating anonymous vectors for expressions that are used multiple times. Here are some examples:
Code:
  // Original
  val v: org.villane.vecmath.Vector2 = v1.-(v2).×(-2.0);
  // Optimized
  val v$x: Float = v1.y.-(v2.y).*(-2.0);
  val v$y: Float = v1.x.-(v2.x).*(-2.0.unary_-); // -(-2) should be optimized later anyway before bytecode generation

  // Original
  var vd = Preamble.floatToFloatExtensions(v2.-(v1).dot(v3)).*(new Vector2(1.0, 3.0));
  var vx = Preamble.floatToFloatExtensions(v2.-(v1).cross(v3)).*(new Vector2(1.0, 3.0));
  vx.-(vd)
  // "Optimized" (actually at least v2 - v1 should be cached!!!)
  var vd$x: Float = v2.x.-(v1.x).*(v3.x).+(v2.y.-(v1.y).*(v3.y)).*(1.0);
  var vd$y: Float = v2.x.-(v1.x).*(v3.x).+(v2.y.-(v1.y).*(v3.y)).*(3.0);
  var vx$x: Float = v2.x.-(v1.x).*(v3.y).-(v2.y.-(v1.y).*(v3.x)).*(1.0);
  var vx$y: Float = v2.x.-(v1.x).*(v3.y).-(v2.y.-(v1.y).*(v3.x)).*(3.0);
  new org.villane.vecmath.Vector2(vx$x.-(vd$x), vx$y.-(vd$y))


The previous example had an error I missed (normalize call was not transformed), but now it works (even expanding the If-Then expression into a block as needed when a temporary variable is added):
Code:
--- ORIGINAL SOURCE ---
@org.villane.vecmath.optimizer.sr def testSegment(segment: org.villane.box2d.shapes.Segment, maxLambda: Float): org.villane.box2d.shapes.SegmentCollide = {
  val s: org.villane.vecmath.Vector2 = segment.p1;
  val r: org.villane.vecmath.Vector2 = segment.p2.-(s);
  val d: org.villane.vecmath.Vector2 = Segment.this.p2.-(Segment.this.p1);
  val n: org.villane.vecmath.Vector2 = d.cross(1.0);
  val slop: Float = 100.0.*(Settings.Epsilon);
  val denom: Float = r.dot(n).unary_-;
  if (denom.>(slop))
    {
      val b: org.villane.vecmath.Vector2 = s.-(Segment.this.p1);
      val a: Float = b.dot(n);
      if (0.0.<=(a).&&(a.<=(maxLambda.*(denom))))
        {
          val mu2: Float = b.cross(r);
          if (slop.unary_-.*(denom).<=(mu2).&&(mu2.<=(denom.*(1.0.+(slop)))))
            return SegmentCollide.hit(a./(denom), n.normalize)
        }
    };
  SegmentCollide.Miss
}
--- OPTIMIZED SOURCE ---
@org.villane.vecmath.optimizer.sr def testSegment(segment: org.villane.box2d.shapes.Segment, maxLambda: Float): org.villane.box2d.shapes.SegmentCollide = {
  val s$x: Float = segment.p1.x;
  val s$y: Float = segment.p1.y;
  val r$x: Float = segment.p2.x.-(s$x);
  val r$y: Float = segment.p2.y.-(s$y);
  val d$x: Float = Segment.this.p2.x.-(Segment.this.p1.x);
  val d$y: Float = Segment.this.p2.y.-(Segment.this.p1.y);
  val n$x: Float = d$y.*(1.0);
  val n$y: Float = d$x.*(1.0.unary_-);
  val slop: Float = 100.0.*(Settings.Epsilon);
  val denom: Float = r$x.*(n$x).+(r$y.*(n$y)).unary_-;
  if (denom.>(slop))
    {
      val b$x: Float = s$x.-(Segment.this.p1.x);
      val b$y: Float = s$y.-(Segment.this.p1.y);
      val a: Float = b$x.*(n$x).+(b$y.*(n$y));
      if (0.0.<=(a).&&(a.<=(maxLambda.*(denom))))
        {
          val mu2: Float = b$x.*(r$y).-(b$y.*(r$x));
          if (slop.unary_-.*(denom).<=(mu2).&&(mu2.<=(denom.*(1.0.+(slop)))))
            {
              val n$length: Float = Preamble.sqrt(n$x.*(n$x).+(n$y.*(n$y)));
              return SegmentCollide.hit(a./(denom), new org.villane.vecmath.Vector2(n$x./(n$length), n$y./(n$length)))
            }
        }
    };
  SegmentCollide.Miss
}


Top
 Profile  
 
PostPosted: Sat Jul 04, 2009 11:33 am 
Offline

Joined: Mon Jun 08, 2009 12:21 pm
Posts: 353
This looks fantastic. I'm excited to see the performance gain!


Top
 Profile  
 
PostPosted: Sun Jul 05, 2009 8:26 am 
Offline

Joined: Mon Sep 01, 2008 6:32 am
Posts: 101
Some early performance comparison results (Optimizations applied to ContactSolver only!)
Both tests run with -server -XX:+DoEscapeAnalysis
Code:
2046 ms (old version, with manual optimizations)
 first 100: 375 ms
 last  900: 1671 ms
vectors created:22868550

2703 ms (compiled normally)
 first 100: 344 ms
 last  900: 2359 ms
vectors created:140496823

2297 ms (compiled with optimizer)
 first 100: 312 ms
 last  900: 1985 ms
vectors created:20375221


7x less vectors created!

The automatically optimized result is slower than what I was getting earlier with manual inlining. But that may because I removed almost all manual inlining and due to the optimizer plug-in not caching sub-expressions inside complex expressions.


Top
 Profile  
 
PostPosted: Sun Jul 05, 2009 8:34 am 
Offline

Joined: Mon Sep 01, 2008 6:32 am
Posts: 101
Hey, this actually removed a bug I must have made in manual optimizing!! :D

I had spent hours tracking it down but didn't find it


Top
 Profile  
 
PostPosted: Sun Jul 05, 2009 8:39 am 
Offline

Joined: Mon Jan 07, 2008 10:51 am
Posts: 1911
Sounds like you are best of doing sub-expression elimination manually. Next you should try it on all of Box2D, to see how much difference it can make in total - it's not more effort for the manual process right?


Top
 Profile  
 
PostPosted: Mon Jul 06, 2009 6:06 am 
Offline

Joined: Mon Sep 01, 2008 6:32 am
Posts: 101
BorisTheBrave wrote:
Sounds like you are best of doing sub-expression elimination manually.

Maybe, although I think there are some cases where it may make sense to always cache: Vec2 Dot Vec2, Vec2 Cross Vec2. In both cases, if they are used as a sub-expression in a context where a vector is being scalarized, I know they will be computed twice (for X and Y). There may be some other cases, like (V2-V1).unit. I'll think about somehow generalizing this.
But yeah, I think some manual optimization of complex expressions will be required anyway in the end. It would be nice to give the user an idea of how things will be optimized, but I'm not sure how to do that. Maybe I could emit compile warnings for cases that are likely to be sub-optimal...

BorisTheBrave wrote:
Next you should try it on all of Box2D, to see how much difference it can make in total - it's not more effort for the manual process right?

Yep. It may take time though -- I've surely created some bugs that haven't come out yet and Matrices are not fully supported yet (only Mat22 * Vec2 and Mat22 transpose* Vec2).


Top
 Profile  
 
PostPosted: Mon Jul 06, 2009 3:08 pm 
Offline

Joined: Mon Sep 01, 2008 6:32 am
Posts: 101
Did some more comparing between the manual inlined version and automatically inlined and it seems that some things which may seem like a good idea may end up worse:

in the solvePositionConstraints and solveVelocityConstraints, a local variable normal is declared:
val normal = c.normal
Even if I manually replace this with:
val normalx = c.normal.x
val normaly = c.normal.y
It actually gets a little slower! Maybe too many local variables is not a good thing? Anyway, I think I can make an exception for these cases. Hmm... maybe I could even automatically eliminate the local variable :)


Top
 Profile  
 
PostPosted: Tue Jul 07, 2009 10:33 am 
Offline

Joined: Mon Sep 01, 2008 6:32 am
Posts: 101
Hehe. Some bloopers:
Code:
val dot = new Vector2(normals1.apply(i).x, normals1.apply(i).y).x.*(dlx).+(new Vector2(normals1.apply(i).x, normals1.apply(i).y).y.*(dly))


Aargh... the optimizer is growing in complexity, I will have to find some ways to generalize things more so I think I'll have to do another refactoring at some point.


Top
 Profile  
 
PostPosted: Tue Jul 07, 2009 11:57 am 
Offline

Joined: Mon Jan 07, 2008 10:51 am
Posts: 1911
I'm telling you, move some of the burden onto the programmer. Require immutable vectors and matrices, and single static assignment, and it should be a doddle compared with what you are attempting.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 30 posts ]  Go to page Previous  1, 2, 3  Next

All times are UTC - 8 hours [ DST ]


Who is online

Users browsing this forum: No registered users and 0 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Powered by phpBB® Forum Software © phpBB Group