Typed data for performance boost

After reading John McCutchan’s recent post on numeric computation in Dart, and a conversation with Srdjan Mitrovic from the Dart VM team, I made some changes to the Dart port of Box2D in the hope of improving performance. The specific commits that make up this change are here and here, and this change has been released to pub as version 0.1.6.

Originally, I had attempted to port the internal math library to John’s vector_math library. For one, this would mean that I no longer need to maintain a chunk of code, and for another it means any work he does to introduce SIMD into the library will automatically be available to me. However, this integration introduced some major instabilities into one of the collision solvers so I abandoned it.

Instead, I made two key changes to the code: Converted all num types to double, and converted the vector and matrix types to use typed data instead of double stored in fields. First, the results. All benchmark code can be found here and were run under SDK version 0.5.11.1_r23200. In all the below charts, the y-axis is the number of steps simulated per second, hence bigger is better.

Results

ball_drop

This simple benchmark shows little difference in performance across the board.

ball_cage

This simple benchmark shows a performance regression for higher step counts. This may be a sign that some parts of the code haven’t been updated to use doubles so the VM is having to do extra work.

circle_stress

The first of the complex benchmarks with many collisions per frame shows a huge improvement across the board. The performance was always fairly consistent, but now it is consistently better.

domino_platform

The most complex benchmark (the one that exhibits the collision instabilities under vector_math) also shows huge improvement in performance.

Rationale

It is clear from the above results that these changes have made a significant positive difference to performance, but why? We’ll tackle each part of the change in turn.

doubles

The VM can work with doubles in an unboxed form which makes computations very efficient. This does, however, break down when passing doubles to functions or returning them from methods as this causes a box/unbox operation pair. Similarly, storing a non-smi number in a field, as the old math library was doing, causes a box operation as fields can only hold smi values or object pointers. And that’s where typed lists come in.

Typed lists

Typed lists in Dart can only hold numbers, not regular objects. Further, unlike when working with integers, the double value does not need to be tagged. This means that the storing and retrieving doubles from a typed list is very fast, and also very memory efficient.

JavaScript

This is all well and good for the VM, but what happens when this code is converted to JavaScript, which is going to be the majority use-case at this point? JavaScript stores all numbers as double precision floating point numbers anyway, so there’s no conversion necessary there. Also, the typed lists map trivially to the native typed arrays in JavaScript which also means no further overhead.

Conclusion

If you’re doing any kind of numeric computation in Dart, read John’s article again and follow his advice. The tips he gives are not theoretical; they have a significant practical performance impact.

Getting started with DartBox2d part 2

This is an update to this post as dartbox2d has undergone some drastic changes since that was written over a year ago.

Getting the code

The first of the main differences is that dartbox2d is now a package hosted on pub. Getting the code is a matter of having a pubspec.yaml file in the root of your project that looks something like:

name: dartbox2d-tutorial
version: 0.0.1
author: Dominic Hamon <dominic@google.com>
homepage: http://dmadev.com
dependencies:
    box2d: ">=0.1.1"
    browser: any"

The dependencies section is the important bit. This lets pub know that this application depends on any version of box2d with a version number greater than 0.1.1. That version uses the vector_math package instead of a hand-rolled math library and runs against the latest (as of this writing) dart sdk r19447. It also depends on browser which we’ll need to pull in the script to allow the code to run both as dart and javascript.

Then, just call $DART_SDK/bin/pub install and the box2d package will be installed. If any errors about conflicting dependencies are printed, please let me know.

The HTML page

<html>
  <body>
    <script type="application/dart" src="tutorial.dart"></script>
    <script src="packages/browser/dart.js"></script>
  </body>
</html>

The Dart code

At the top of the dart file, you would now import the libraries you need:

library dartbox2d_tutorial;
import 'dart:html';
import 'package:box2d/box2d.dart';

Note that the box2d package actually contains two libraries; box2d.dart for use with the VM and box2d_browser.dart for use in the browser. The only difference is that the latter enables debug drawing functions using dart:html. If you’re planning on running through DartEditor, you probably want box2d_browser.

The rest of the tutorial works almost as is, though the new math library means that initializeWorld should look like:

void initializeWorld() {
    // Create a world with gravity and allow it to sleep.
    world = new World(new vec2(0, -10), true, new DefaultWorldPool());

    // Create the ground.
    PolygonShape sd = new PolygonShape();
    sd.setAsBox(50.0, 0.4);

    BodyDef bd = new BodyDef();
    bd.position.setCoords(0.0, 0.0);
    Body ground = world.createBody(bd);
    ground.createFixtureFromShape(sd);

    // Create a bouncing ball.
    final bouncingBall = new CircleShape();
    bouncingBall.radius = BALL_RADIUS;

    final ballFixtureDef = new FixtureDef();
    ballFixtureDef.restitution = 0.7;
    ballFixtureDef.density = 0.05;
    ballFixtureDef.shape = bouncingBall;

    final ballBodyDef = new BodyDef();
    ballBodyDef.linearVelocity = new vec2(-2, -20);
    ballBodyDef.position = new vec2(15, 15);
    ballBodyDef.type = BodyType.DYNAMIC;
    ballBodyDef.bullet = true;

    final ballBody = world.createBody(ballBodyDef);
    ballBody.createFixture(ballFixtureDef);
}

And the switch to dart:html leaves initializeCanvas looking like:

CanvasElement canvas;
CanvasRenderingContext2D ctx;
ViewportTransform viewport;
DebugDraw debugDraw

void initializeCanvas() {
    // Create a canvas and get the 2d context.
    canvas = new CanvasElement(width:CANVAS_WIDTH, height:CANVAS_HEIGHT);
    document.body.append(canvas);
    ctx = canvas.getContext("2d");

    // Create the viewport transform with the center at extents.
    final extents = new Vector(CANVAS_WIDTH / 2, CANVAS_HEIGHT / 2);
    viewport = new CanvasViewportTransform(extents, extents);
    viewport.scale = VIEWPORT_SCALE;

    // Create our canvas drawing tool to give to the world.
    debugDraw = new CanvasDraw(viewport, ctx);

    // Have the world draw itself for debugging purposes.
    world.debugDraw = debugDraw;
}

and run as:

void run() {
    window.animationFrame.then((time) => step());
}

void step() {
    world.step(1/60, 10, 10);
    ctx.clearRect(0, 0, CANVAS_WIDTH, CANVAS_HEIGHT);
    world.drawDebugData();
    run();
}

Also, though the frog and dartc compilers have been replaced by dart2js so this is compiled to javascript using:

$ $DART_SDK/bin/dart2js tutorial.dart -otutorial.dart.js

There are a host of examples in the demos folder of the DartBox2d source here.

Getting started with DartBox2d

This post is deprecated. Please see this post for the latest version.

The latest Dart library to be released is one that might see a fair bit of use, if the Java and JavaScript versions are anything to go by. DartBox2d is the latest port of the immensely popular 2d physics engine seen in games across the web. It has a very similar interface to the Java version, so getting started shouldn’t be too hard for anyone familiar with that version.

That being said, here’s how to put together a simple application.

Getting the library

Go here and follow the instructions to get a local copy of the code.

The HTML page

Next, you need an HTML page to host the application. A simple boilerplate would look something like:

<html>
  <body>
    <script type="text/javascript" src="tutorial.dart.js"></script>
  </body>
</html>

The Dart code

At the top of the dart file, you need to name your application and import any libraries you want to use:

#library('tutorial');
#import('dart:dom');
#import('[path_to_dartbox2d]/lib/box2d.dart');

Now create a class for your application and a simple main method:

class Tutorial {
  ...
}

void main() {
  Tutorial.main();
}

This simple main method is what will be called when your application starts. It is calling a static method on your class that should now look something like:

class Tutorial {
  static void main() {
    final app = new Tutorial();
    app.run();
  }

  Tutorial() {
    initializeWorld();
    initializeCanvas();
  }
}

All we have left to do is to define the two initialization methods and the run method. First, let’s initialize the world:

class Tutorial {
  ...

  static final int BALL_RADIUS = 1;

  World world;

  void initializeWorld() {
    // Create a world with gravity and allow it to sleep.
    world = new World(new Vector(0, -10), true, new DefaultWorldPool());

    // Create the ground.
    PolygonShape sd = new PolygonShape();
    sd.setAsBox(50.0, 0.4);
      
    BodyDef bd = new BodyDef();
    bd.position.setCoords(0.0, 0.0);
    Body ground = world.createBody(bd);
    ground.createFixtureFromShape(sd);

    // Create a bouncing ball.
    final bouncingBall = new CircleShape();
    bouncingBall.radius = BALL_RADIUS;

    final ballFixtureDef = new FixtureDef();
    ballFixtureDef.restitution = 0.7;
    ballFixtureDef.density = 0.05;
    ballFixtureDef.shape = bouncingBall;

    final ballBodyDef = new BodyDef();
    ballBodyDef.linearVelocity = new Vector(-2, -20);
    ballBodyDef.position = new Vector(15, 15);
    ballBodyDef.type = BodyType.DYNAMIC;
    ballBodyDef.bullet = true;

    final ballBody = world.createBody(ballBodyDef);
    ballBody.createFixture(ballFixtureDef);
  }
}

And now we’re ready to initialize the canvas:

class Tutorial {
  ...
  static final int CANVAS_WIDTH = 900;
  static final int CANVAS_HEIGHT = 600;
  static final int VIEWPORT_SCALE = 10;

  HTMLCanvasElement canvas;
  CanvasRenderingContext2D ctx;
  IViewportTransform viewport;
  DebugDraw debugDraw;

  void initializeCanvas() {
    // Create a canvas and get the 2d context.
    canvas = document.createElement('canvas');
    canvas.width = CANVAS_WIDTH;
    canvas.height = CANVAS_HEIGHT;
    document.body.appendChild(canvas);
    ctx = canvas.getContext("2d");

    // Create the viewport transform with the center at extents.
    final extents = new Vector(CANVAS_WIDTH / 2, CANVAS_HEIGHT / 2);
    viewport = new CanvasViewportTransform(extents, extents);
    viewport.scale = VIEWPORT_SCALE;

    // Create our canvas drawing tool to give to the world.
    debugDraw = new CanvasDraw(viewport, ctx);

    // Have the world draw itself for debugging purposes.
    world.debugDraw = debugDraw;
  }
}

Now, all that’s left is to start the world running:

class Tutorial {
  ...
  static final num TIME_STEP = 1/60;
  static final int VELOCITY_ITERATIONS = 10;
  static final int POSITION_ITERATIONS = 10;

  void run() {
    window.webkitRequestAnimationFrame((num time) {
      step(time);
    }, canvas);
  }

  void step(num time) {
    // Advance the world.
    world.step(TIME_STEP, VELOCITY_ITERATIONS, POSITION_ITERATIONS);

    // Clear the canvas and draw the frame.
    ctx.clearRect(0, 0, CANVAS_WIDTH, CANVAS_HEIGHT);
    world.drawDebugData();

    // Request another animation frame.
    window.webkitRequestAnimationFrame((num t) {
      step(t);
    }, canvas);
  }
}

Once you’ve put all this together, you’re ready to compile it to JavaScript.

I prefer the command-line frog compiler, but DartBox2d also compiles cleanly with dartc with warnings as errors and fatal type errors enabled, so feel free to use either. You can also use the Dart Editor to build your application, and that’s almost certainly the best route to take. Refer to the Dart language site for more details.

Once you’ve compiled to JavaScript, make sure that your html file is referencing the generated file correctly and load it up in a browser. If all went well, you should see a green box with a peach ball bouncing on it.