Optimizing the vector math

Discuss issues specific the Scala port of Box2D
Villane
Posts: 101
Joined: Mon Sep 01, 2008 6:32 am

Re: Optimizing the vector math

Postby Villane » Fri Jul 03, 2009 3:10 am

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.

Villane
Posts: 101
Joined: Mon Sep 01, 2008 6:32 am

Re: Optimizing the vector math

Postby Villane » Sat Jul 04, 2009 5:47 am

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: Select all

  // 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: Select all

--- 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
}

toucansam
Posts: 356
Joined: Mon Jun 08, 2009 12:21 pm
Contact:

Re: Optimizing the vector math

Postby toucansam » Sat Jul 04, 2009 11:33 am

This looks fantastic. I'm excited to see the performance gain!

Villane
Posts: 101
Joined: Mon Sep 01, 2008 6:32 am

Re: Optimizing the vector math

Postby Villane » Sun Jul 05, 2009 8:26 am

Some early performance comparison results (Optimizations applied to ContactSolver only!)
Both tests run with -server -XX:+DoEscapeAnalysis

Code: Select all

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.

Villane
Posts: 101
Joined: Mon Sep 01, 2008 6:32 am

Re: Optimizing the vector math

Postby Villane » Sun Jul 05, 2009 8:34 am

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

BorisTheBrave
Posts: 1911
Joined: Mon Jan 07, 2008 10:51 am
Contact:

Re: Optimizing the vector math

Postby BorisTheBrave » Sun Jul 05, 2009 8:39 am

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?

Villane
Posts: 101
Joined: Mon Sep 01, 2008 6:32 am

Re: Optimizing the vector math

Postby Villane » Mon Jul 06, 2009 6:06 am

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).

Villane
Posts: 101
Joined: Mon Sep 01, 2008 6:32 am

Re: Optimizing the vector math

Postby Villane » Mon Jul 06, 2009 3:08 pm

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 :)

Villane
Posts: 101
Joined: Mon Sep 01, 2008 6:32 am

Re: Optimizing the vector math

Postby Villane » Tue Jul 07, 2009 10:33 am

Hehe. Some bloopers:

Code: Select all

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.

BorisTheBrave
Posts: 1911
Joined: Mon Jan 07, 2008 10:51 am
Contact:

Re: Optimizing the vector math

Postby BorisTheBrave » Tue Jul 07, 2009 11:57 am

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.


Return to “Scala”



Who is online

Users browsing this forum: No registered users and 1 guest