Box2D Forums
It is currently Tue May 21, 2013 4:05 pm

View unanswered posts | View active topics


Board index » Box2D Ports » Scala

All times are UTC - 8 hours [ DST ]



Post new topic Reply to topic  Page 3 of 3
  [ 30 posts ]  Go to page Previous  1, 2, 3
  Print view Previous topic | Next topic 
Author Message
Villane
PostPosted: Wed Jul 08, 2009 1:14 pm 
Offline

Joined: Mon Sep 01, 2008 6:32 am
Posts: 101
BorisTheBrave wrote:
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.


I think you're right. If I'm making it more complex, it's going to be a real pain to add 3D later. I'm going to do some refactoring anyway though -- basically I ended up with the bulk of the code being one huge chain of nested pattern matches. I can't easily avoid that, but I'm moving some implementation to separate classes (separating them by Vector2, Matrix22 etc. where possible so Vector3 and so on can be added later)
Top
 Profile  
 
Villane
PostPosted: Thu Jul 09, 2009 2:17 pm 
Offline

Joined: Mon Sep 01, 2008 6:32 am
Posts: 101
Villane wrote:
huge chain of nested pattern matches


Turns out it is not that good an idea to do a lot of nested patterns. I've happened on at least one bug in Scala's pattern matcher. They will all hopefully be fixed in 2.8 though. There are workarounds, so I will use those for now.
Top
 Profile  
 
Villane
PostPosted: Fri Jul 10, 2009 3:25 pm 
Offline

Joined: Mon Sep 01, 2008 6:32 am
Posts: 101
I've completed most of the refactoring now and actually adding support for more complex cases is easier now. As well as adding support for new types such as Vector3 and Matrix33. I'm not sure if the current version will be the final design (I don't really know much about compilers actually and maybe I will learn something better :)), but for now I'm happy with it.

I'm pretty sure it can now correctly optimize some complex expressions, and where it suspects the expression may contain mutable things, it will not reuse the cache variables.

This is a pretty contrived example, just to show off some things (length of mutable v is re-computed as required, v1-(2.0,2.0) is cached, for v1.unit, only the length of v1 is cached)
Code:
--- ORIGINAL SOURCE ---
def selectNormalize(v1: org.villane.vecmath.Vector2): org.villane.vecmath.Vector2 = {
  var v: org.villane.vecmath.Vector2 = v1;
  val b: org.villane.vecmath.Vector2 = v.unit;
  val c: org.villane.vecmath.Vector2 = v.unit;
  v = v1.-(new org.villane.vecmath.Vector2(2.0, 2.0)).unit;
  v = v1.unit;
  val d: org.villane.vecmath.Vector2 = v.unit;
  d
}
--- OPTIMIZED SOURCE ---
def selectNormalize(v1: org.villane.vecmath.Vector2): org.villane.vecmath.Vector2 = {
  var v: org.villane.vecmath.Vector2 = v1;
  <synthetic> var v$length: Float = Preamble.sqrt(v.x.*(v.x).+(v.y.*(v.y)));
  final <synthetic> val b$x: Float = v.x./(v$length);
  final <synthetic> val b$y: Float = v.y./(v$length);
  final <synthetic> val c$x: Float = v.x./(v$length);
  final <synthetic> val c$y: Float = v.y./(v$length);
  final <synthetic> val $anon$v0$x: Float = v1.x.-(2.0);
  final <synthetic> val $anon$v0$y: Float = v1.y.-(2.0);
  final <synthetic> val $anon$v0$length: Float = Preamble.sqrt($anon$v0$x.*($anon$v0$x).+($anon$v0$y.*($anon$v0$y)));
  v = new org.villane.vecmath.Vector2($anon$v0$x./($anon$v0$length), $anon$v0$y./($anon$v0$length));
  val $anon$length1: Float = Preamble.sqrt(v1.x.*(v1.x).+(v1.y.*(v1.y)));
  v = new org.villane.vecmath.Vector2(v1.x./($anon$length1), v1.y./($anon$length1));
  v$length = Preamble.sqrt(v.x.*(v.x).+(v.y.*(v.y)));
  final <synthetic> val d$x: Float = v.x./(v$length);
  final <synthetic> val d$y: Float = v.y./(v$length);
  new org.villane.vecmath.Vector2(d$x, d$y)
}


And here it correctly does not reuse a cached expression:
Code:
def mutableExprLength(v1: org.villane.vecmath.Vector2, h: test.Test2.MutHolder): Float = {
  val n: Float = v1.-(h.v).length;
  h.v_=(new org.villane.vecmath.Vector2(7.0, 7.0));
  val m: Float = v1.-(h.v).length;
  n.-(m)
}
--- OPTIMIZED SOURCE ---
def mutableExprLength(v1: org.villane.vecmath.Vector2, h: test.Test2.MutHolder): Float = {
  final <synthetic> val $anon$v0$x: Float = v1.x.-(h.v.x);
  final <synthetic> val $anon$v0$y: Float = v1.y.-(h.v.y);
  final <synthetic> val $anon$v0$length: Float = Preamble.sqrt($anon$v0$x.*($anon$v0$x).+($anon$v0$y.*($anon$v0$y)));
  val n: Float = $anon$v0$length;
  h.v_=(new org.villane.vecmath.Vector2(7.0, 7.0));
  final <synthetic> val $anon$v1$x: Float = v1.x.-(h.v.x);
  final <synthetic> val $anon$v1$y: Float = v1.y.-(h.v.y);
  final <synthetic> val $anon$v1$length: Float = Preamble.sqrt($anon$v1$x.*($anon$v1$x).+($anon$v1$y.*($anon$v1$y)));
  val m: Float = $anon$v1$length;
  n.-(m)
}

And later I might add some immutability analysis (although probably not unless Scala itself will support it) so if h.v would be immutable, the temporary variables can be reused.

Now I will finish the refactoring ( a few small things still to do ) and then try to apply this to a larger part of Box2D
Top
 Profile  
 
Villane
PostPosted: Sat Jul 18, 2009 6:03 am 
Offline

Joined: Mon Sep 01, 2008 6:32 am
Posts: 101
Hmm... ran into a strange issue. Maybe there's something really plain I'm not seeing here. Here are non-scalarized & scalarized versions of two expressions. For some reason, the second causes a test to be much slower and have lots of more vector creations. I can't really see how more vectors could get created here, though... Can anyone see something I might be missing?

Code:
// xf2 is a Transform, vertices2 is an array of vectors

// non-scalarized
xf2 * vertices2(i1)
xf2 * vertices2(i2)

// scalarized
new Vector2(
  xf2.pos.x + xf2.rot.a11 * vertices2(i1).x + xf2.rot.a12 * vertices2(i1).y,
  xf2.pos.y + xf2.rot.a21 * vertices2(i1).x + xf2.rot.a22 * vertices2(i1).y
)
new Vector2(
  xf2.pos.x + xf2.rot.a11 * vertices2(i2).x + xf2.rot.a12 * vertices2(i2).y,
  xf2.pos.y + xf2.rot.a21 * vertices2(i2).x + xf2.rot.a22 * vertices2(i2).y
)

Note that I'm working on skipping scalarization for expressions like this: I think there is no improvement here, as they create a new vector in any case and normal inlining at compile time or by JIT should have the same result.

Oh, and these expressions in context:
Code:
// original (last statement of PolygonCollider.findIncidentEdge)
  scala.List.apply[org.villane.box2d.collision.PolygonCollider.ClipVertex](new org.villane.box2d.collision.PolygonCollider.ClipVertex(xf2.*(vertices2.apply(i1)), new org.villane.box2d.collision.ContactID(edge1, i1, 0, false)), new org.villane.box2d.collision.PolygonCollider.ClipVertex(xf2.*(vertices2.apply(i2)), new org.villane.box2d.collision.ContactID(edge1, i2, 1, false)))

// scalarized
  scala.List.apply[org.villane.box2d.collision.PolygonCollider.ClipVertex](new org.villane.box2d.collision.PolygonCollider.ClipVertex(new org.villane.vecmath.Vector2(xf2.pos.x.+(xf2.rot.a11.*(vertices2.apply(i1).x).+(xf2.rot.a12.*(vertices2.apply(i1).y))), xf2.pos.y.+(xf2.rot.a21.*(vertices2.apply(i1).x).+(xf2.rot.a22.*(vertices2.apply(i1).y)))), new org.villane.box2d.collision.ContactID(edge1, i1, 0, false)), new org.villane.box2d.collision.PolygonCollider.ClipVertex(new org.villane.vecmath.Vector2(xf2.pos.x.+(xf2.rot.a11.*(vertices2.apply(i2).x).+(xf2.rot.a12.*(vertices2.apply(i2).y))), xf2.pos.y.+(xf2.rot.a21.*(vertices2.apply(i2).x).+(xf2.rot.a22.*(vertices2.apply(i2).y)))), new org.villane.box2d.collision.ContactID(edge1, i2, 1, false)))


[edit] This also happens if I'll do this replacement manually and don't compile with the optimizer.
Top
 Profile  
 
Villane
PostPosted: Tue Jul 28, 2009 12:33 pm 
Offline

Joined: Mon Sep 01, 2008 6:32 am
Posts: 101
Just letting you know I'm still working on it. Had some busy time at work and my brain was too fried for working on this at home.

I'm getting pretty close to being able to run this on all of ScalaBox2D, but I'm getting some errors that happen in later compile phases, especially where anonymous functions are involved. I think I lack some fundamental understanding on how a Scala transformer should work so I've made errors that show up only in some cases which I hadn't tested earlier.

I may ask for some help on the scala-tools list, but the people who know much about the compiler are probably super busy.

Happened on some nice surprises among the errors too:
Code:
--- ORIGINAL SOURCE ---
def testTupleOp(): org.villane.vecmath.Vector2 = {
  val v: org.villane.vecmath.Vector2 = org.villane.vecmath.Preamble.tuple2fToVector2(new (Float, Float)(1.0, 2.0)).+(org.villane.vecmath.Preamble.tuple2fToVector2(new (Float, Float)(3.0, 4.0)));
  v
}
--- OPTIMIZED SOURCE ---
def testTupleOp(): org.villane.vecmath.Vector2 = {
  final <synthetic> val v$x: Float = 4.0;
  final <synthetic> val v$y: Float = 6.0;
  new org.villane.vecmath.Vector2(v$x, v$y)
}
--- END ---

I thought I was only eliminating the Tuple To Vector conversion but after that the compiler even decided to eliminate the + operation on two literals.
Top
 Profile  
 
wjordan
PostPosted: Wed Aug 12, 2009 12:33 pm 
Offline

Joined: Wed Aug 12, 2009 11:55 am
Posts: 3
Just wanted to drop in and say that it sounds like you're up to some really awesome experimental automated low-level optimization techniques here. I probably couldn't offer any real help without digging deep into the details of it all, so for now all you get is encouragement and my hopes that it all comes together and pays off nicely in the end :D
Top
 Profile  
 
Villane
PostPosted: Sun Dec 13, 2009 3:47 pm 
Offline

Joined: Mon Sep 01, 2008 6:32 am
Posts: 101
Hi. I haven't worked on ScalaBox2D for a while, but I want to return to it in the beginning of the new year.

However, I think I'm going to put this particular optimization work aside for a while, for two reasons. The first is that updating the vector library is going to become difficult if I also have to update the optimizer (it's not general enough to adapt automatically). And I don't know what changes Scala 2.8 would require me to make. The second is that the optimizer code is still quite brittle, even after a few refactorings. I could simplify it at the cost of additional requirements for user code, but then the user code would become brittle, which is even worse.

I may continue with this someday, but I'm not sure when. Maybe when Scala 2.8 is stable... or maybe JVM optimizations will render this whole work unnecessary (I hope :))
Top
 Profile  
 
toucansam
PostPosted: Sat Jan 09, 2010 11:38 pm 
Offline

Joined: Mon Jun 08, 2009 12:21 pm
Posts: 353
Villane wrote:
...or maybe JVM optimizations will render this whole work unnecessary (I hope :))


sigh....
Top
 Profile  
 
fictiveLaark
PostPosted: Sat Jul 03, 2010 4:33 am 
Offline

Joined: Mon Apr 26, 2010 4:18 am
Posts: 14
I likely know less than anyone else here about this subject but I had a suggestion, as a compromise between immutability and clean math perhaps you could cache your vectors. The obvious problem with that is that this cache will eat up a lot of memory, but Java does provide a SoftReference class that wraps a reference and only allows the garbage collector to trash your reference if a OutOfMemoryException is about to be thrown. I had in mind a class that maps long values( key = x-corrdinate << 32 & y-coordinate) to Vector wrapping SoftReference instances.
Top
 Profile  
 
toucansam
PostPosted: Mon Jul 05, 2010 7:18 pm 
Offline

Joined: Mon Jun 08, 2009 12:21 pm
Posts: 353
Pooling (caching) objects is definitely the way to go for java ports, that's what I've been working on for a while.
Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  Page 3 of 3
  [ 30 posts ]  Go to page Previous  1, 2, 3

Board index » Box2D Ports » Scala

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