Performance Invariants (Part II)

A few days ago I wrote a post about performance invariants. The basic idea behind them, is that there should be an easy way to declare performance constraints at the source code level, and that you should be able to check them every time you run your unit tests. To make a long story short, I have been a busy little bee for the last few days and managed to build a reasonable proof-of-concept.

Let's start with simple example:

import performance.annotation.Expect;
...
class Test {
    @Expect("InputStream.read == 0")
    static void process(List<String> list) {
        //...
    }
}

What we're asserting here is that we want to make sure that the number of calls to methods called read defined in classes named InputStream should be exactly zero.

If we want to exclude basically all IO, we can change the expectation to:

import performance.annotation.Expect;
...
class Test {
    @Expect("InputStream.read == 0 && OutputStream.write == 0")
    static void process(List<String> list) {
        //...
    }
}

Note that these are checked even for code that is called indirectly by the method process.

If we add an innocent looking println:

    @Expect("InputStream.read == 0 && OutputStream.write == 0")
    static void process(List<String> list) {
        System.out.println("Hi!");
        //...
    }

And run it with the agent enabled by using:

~>java -javaagent:./performance-1.0-SNAPSHOT-jar-with-dependencies.jar \
       -Xbootclasspath/a:./performance-1.0-SNAPSHOT-jar-with-dependencies.jar Test

You should get something like the following output:

Hi!
Exception in thread "main" java.lang.AssertionError: Method 'Test.process' did not fulfil: InputStream.read == 0 && OutputStream.write == 0
         Matched: [#OutputStream.write=7, #InputStream.read=0]
         Dynamic: []
        at performance.runtime.PerformanceExpectation.validate(PerformanceExpectation.java:69)
        at performance.runtime.ThreadHelper.endExpectation(ThreadHelper.java:52)
        at performance.runtime.Helper.endExpectation(Helper.java:61)
        at Test.process(Test.java:17)
        at Test.main(Test.java:39)

This is witchraft, I say! ... well kind of.

Let's stop a moment and consider what's going on here. Notice the first line of the output. It contains the text "Hi!" that we printed. This happens because the check is performed after the method process finishes. In the fourth line, you can see how many times each method matched during the execution of the process method. Ignore the "Dynamic" list for just a second.

Let's try something a bit more interesting:

    class Customer { /*... */}
    //...
    @Expect("Statement.executeUpdate < ${customers.size}")
    void storeCustomers(List<Customer> customers) {
        //...
    }

Note the ${customers.size} in the expression, what this intuitively mean is that we want to take the size of the list as an upper bound. It's like the poor programmer's big-O notation. If we were to run this, but assuming that we execute two updates for each customer (instead of one as asserted), we would get:

Exception in thread "main" java.lang.AssertionError: Method 'Test.storeCustomers' did not fulfil: Statement.executeUpdate < ${customers.size}
         Matched: [#Statement.executeUpdate=50]
         Dynamic: [customers.size=25.0]
        at performance.runtime.PerformanceExpectation.validate(PerformanceExpectation.java:69)
        at performance.runtime.ThreadHelper.endExpectation(ThreadHelper.java:52)
        at performance.runtime.Helper.endExpectation(Helper.java:61)
        at Test.storeCustomers(Test.java:19)
        at Test.main(Test.java:42)

Check the third line, this time, the "Dynamic" list contains the length of the list. In general, expressions of the form ${a.b.c.d} are called dynamic values. They refer to arguments, instance variables or static variables. For example:

• ${static.CONSTANT} refers to a variable named CONSTANT in the current class.
• ${this.instance} refers to a variable named 'instance' in the current object (only valid for instance methods).
• ${n} refers to an argument named 'n' (this only works if the class has debug information)
• ${3} refers to the fourth argument from the left (zero based indexing)

All dynamic values MUST yield a numeric value, otherwise a failure will be reported at runtime. Currently the library will complain if any dynamic value is null.

Although this is an early implementation, it is enough to start implementing performance invariants that can be checked every time you run your unit tests.
Enough for today, in a followup post I'll go into the internals of the agent. If you want to browse the source code or try it out, go and grab a copy from github.

Performance Invariants

UPDATE A newer post on this subject can be found here

Let's start with a problem: How do you make unit tests that test for performance?

It might seem simple, but consider that:

• Test must be stable across hardware/software configurations
• Machine workload should not affect results (at least on normal situations)

A friend of mine (Fernando Rodriguez-Olivera if you must know) thought of the following (among many other things):
For each test run, record interesting metrics, such as:

• specific method calls
• number of queries executed
• number of I/O operations
• etc.

And after the test run, assert that these values are under a certain threshold. If they're not, fail the test.
He even implemented a proof-of-concept using BeanShell to record these stats to a file during the test run, and it would check the constraints after the fact.

Yesterday I was going over these ideas while preparing a presentation on code quality and something just clicked: annotate methods with performance invariants.
The concept is similar to pre/post conditions. Each annotation is basically a post condition on the method call that states which performance "promises" the method makes.

For example you should be able to do something like:

@Ensure("queryCount <= 1")
public CustomerInfo loadCustomerInfo() {...}

Or maybe something like this:

@Ensure("count(java.lang.Comparable.compareTo) < ceil(log(this.customers.size()))")
public CustomerInfo findById(String id) {...}

These promises are enabled only during testing since checking for them might be a bit expensive for a production system.

As this is quite recent I don't have anything working (yet), but I think it's worth exploring.
If I manage to find some time to try and build it, I'll post some updates here.

gluUnProject for iPhone/iOS

I had a hard time finding a suitable implementation of gluUnProject for an iPhone project I was working on, so I decided to port the original implementation by SGI.

This is the header file (I called it "project.h"):

#ifndef __GLU_PROJECT_IOS
#define __GLU_PROJECT_IOS

#include <OpenGLES/ES1/gl.h>
#include <OpenGLES/ES1/glext.h>

void
gluPerspective(GLfloat fovy, GLfloat aspect, GLfloat zNear, GLfloat zFar);

void
gluLookAt(GLfloat eyex, GLfloat eyey, GLfloat eyez, GLfloat centerx,
    GLfloat centery, GLfloat centerz, GLfloat upx, GLfloat upy,
    GLfloat upz);

GLint
gluProject(GLfloat objx, GLfloat objy, GLfloat objz, 
     const GLfloat modelMatrix[16], 
     const GLfloat projMatrix[16],
     const GLint viewport[4],
     GLfloat *winx, GLfloat *winy, GLfloat *winz);

GLint
gluUnProject(GLfloat winx, GLfloat winy, GLfloat winz,
    const GLfloat modelMatrix[16], 
    const GLfloat projMatrix[16],
    const GLint viewport[4],
    GLfloat *objx, GLfloat *objy, GLfloat *objz);


GLint
gluUnProject4(GLfloat winx, GLfloat winy, GLfloat winz, GLfloat clipw,
     const GLfloat modelMatrix[16], 
     const GLfloat projMatrix[16],
     const GLint viewport[4],
     GLclampf nearVal, GLclampf farVal,      
     GLfloat *objx, GLfloat *objy, GLfloat *objz,
     GLfloat *objw);

void
gluPickMatrix(GLfloat x, GLfloat y, GLfloat deltax, GLfloat deltay,
     GLint viewport[4]);

#endif

And the source code:

#include "project.h"
#include <math.h>


/*
** Make m an identity matrix
*/
static void __gluMakeIdentityf(GLfloat m[16])
{
    m[0+4*0] = 1; m[0+4*1] = 0; m[0+4*2] = 0; m[0+4*3] = 0;
    m[1+4*0] = 0; m[1+4*1] = 1; m[1+4*2] = 0; m[1+4*3] = 0;
    m[2+4*0] = 0; m[2+4*1] = 0; m[2+4*2] = 1; m[2+4*3] = 0;
    m[3+4*0] = 0; m[3+4*1] = 0; m[3+4*2] = 0; m[3+4*3] = 1;
}

#define __glPi 3.14159265358979323846

void
gluPerspective(GLfloat fovy, GLfloat aspect, GLfloat zNear, GLfloat zFar)
{
    GLfloat m[4][4];
    float sine, cotangent, deltaZ;
    float radians = fovy / 2 * __glPi / 180;

    deltaZ = zFar - zNear;
    sine = sin(radians);
    if ((deltaZ == 0) || (sine == 0) || (aspect == 0)) {
 return;
    }
    cotangent = cos(radians) / sine;

    __gluMakeIdentityf(&m[0][0]);
    m[0][0] = cotangent / aspect;
    m[1][1] = cotangent;
    m[2][2] = -(zFar + zNear) / deltaZ;
    m[2][3] = -1;
    m[3][2] = -2 * zNear * zFar / deltaZ;
    m[3][3] = 0;
    glMultMatrixf(&m[0][0]);
}

static void normalize(float v[3])
{
    float r;

    r = sqrt( v[0]*v[0] + v[1]*v[1] + v[2]*v[2] );
    if (r == 0.0) return;

    v[0] /= r;
    v[1] /= r;
    v[2] /= r;
}

static void cross(float v1[3], float v2[3], float result[3])
{
    result[0] = v1[1]*v2[2] - v1[2]*v2[1];
    result[1] = v1[2]*v2[0] - v1[0]*v2[2];
    result[2] = v1[0]*v2[1] - v1[1]*v2[0];
}

void
gluLookAt(GLfloat eyex, GLfloat eyey, GLfloat eyez, GLfloat centerx,
   GLfloat centery, GLfloat centerz, GLfloat upx, GLfloat upy,
   GLfloat upz)
{
    float forward[3], side[3], up[3];
    GLfloat m[4][4];

    forward[0] = centerx - eyex;
    forward[1] = centery - eyey;
    forward[2] = centerz - eyez;

    up[0] = upx;
    up[1] = upy;
    up[2] = upz;

    normalize(forward);

    /* Side = forward x up */
    cross(forward, up, side);
    normalize(side);

    /* Recompute up as: up = side x forward */
    cross(side, forward, up);

    __gluMakeIdentityf(&m[0][0]);
    m[0][0] = side[0];
    m[1][0] = side[1];
    m[2][0] = side[2];

    m[0][1] = up[0];
    m[1][1] = up[1];
    m[2][1] = up[2];

    m[0][2] = -forward[0];
    m[1][2] = -forward[1];
    m[2][2] = -forward[2];

    glMultMatrixf(&m[0][0]);
    glTranslatef(-eyex, -eyey, -eyez);
}

static void __gluMultMatrixVecf(const GLfloat matrix[16], const GLfloat in[4],
        GLfloat out[4])
{
    int i;

    for (i=0; i<4; i++) {
 out[i] = 
     in[0] * matrix[0*4+i] +
     in[1] * matrix[1*4+i] +
     in[2] * matrix[2*4+i] +
     in[3] * matrix[3*4+i];
    }
}

/*
** Invert 4x4 matrix.
** Contributed by David Moore (See Mesa bug #6748)
*/
static int __gluInvertMatrixf(const GLfloat m[16], GLfloat invOut[16])
{
    float inv[16], det;
    int i;

    inv[0] =   m[5]*m[10]*m[15] - m[5]*m[11]*m[14] - m[9]*m[6]*m[15]
             + m[9]*m[7]*m[14] + m[13]*m[6]*m[11] - m[13]*m[7]*m[10];
    inv[4] =  -m[4]*m[10]*m[15] + m[4]*m[11]*m[14] + m[8]*m[6]*m[15]
             - m[8]*m[7]*m[14] - m[12]*m[6]*m[11] + m[12]*m[7]*m[10];
    inv[8] =   m[4]*m[9]*m[15] - m[4]*m[11]*m[13] - m[8]*m[5]*m[15]
             + m[8]*m[7]*m[13] + m[12]*m[5]*m[11] - m[12]*m[7]*m[9];
    inv[12] = -m[4]*m[9]*m[14] + m[4]*m[10]*m[13] + m[8]*m[5]*m[14]
             - m[8]*m[6]*m[13] - m[12]*m[5]*m[10] + m[12]*m[6]*m[9];
    inv[1] =  -m[1]*m[10]*m[15] + m[1]*m[11]*m[14] + m[9]*m[2]*m[15]
             - m[9]*m[3]*m[14] - m[13]*m[2]*m[11] + m[13]*m[3]*m[10];
    inv[5] =   m[0]*m[10]*m[15] - m[0]*m[11]*m[14] - m[8]*m[2]*m[15]
             + m[8]*m[3]*m[14] + m[12]*m[2]*m[11] - m[12]*m[3]*m[10];
    inv[9] =  -m[0]*m[9]*m[15] + m[0]*m[11]*m[13] + m[8]*m[1]*m[15]
             - m[8]*m[3]*m[13] - m[12]*m[1]*m[11] + m[12]*m[3]*m[9];
    inv[13] =  m[0]*m[9]*m[14] - m[0]*m[10]*m[13] - m[8]*m[1]*m[14]
             + m[8]*m[2]*m[13] + m[12]*m[1]*m[10] - m[12]*m[2]*m[9];
    inv[2] =   m[1]*m[6]*m[15] - m[1]*m[7]*m[14] - m[5]*m[2]*m[15]
             + m[5]*m[3]*m[14] + m[13]*m[2]*m[7] - m[13]*m[3]*m[6];
    inv[6] =  -m[0]*m[6]*m[15] + m[0]*m[7]*m[14] + m[4]*m[2]*m[15]
             - m[4]*m[3]*m[14] - m[12]*m[2]*m[7] + m[12]*m[3]*m[6];
    inv[10] =  m[0]*m[5]*m[15] - m[0]*m[7]*m[13] - m[4]*m[1]*m[15]
             + m[4]*m[3]*m[13] + m[12]*m[1]*m[7] - m[12]*m[3]*m[5];
    inv[14] = -m[0]*m[5]*m[14] + m[0]*m[6]*m[13] + m[4]*m[1]*m[14]
             - m[4]*m[2]*m[13] - m[12]*m[1]*m[6] + m[12]*m[2]*m[5];
    inv[3] =  -m[1]*m[6]*m[11] + m[1]*m[7]*m[10] + m[5]*m[2]*m[11]
             - m[5]*m[3]*m[10] - m[9]*m[2]*m[7] + m[9]*m[3]*m[6];
    inv[7] =   m[0]*m[6]*m[11] - m[0]*m[7]*m[10] - m[4]*m[2]*m[11]
             + m[4]*m[3]*m[10] + m[8]*m[2]*m[7] - m[8]*m[3]*m[6];
    inv[11] = -m[0]*m[5]*m[11] + m[0]*m[7]*m[9] + m[4]*m[1]*m[11]
             - m[4]*m[3]*m[9] - m[8]*m[1]*m[7] + m[8]*m[3]*m[5];
    inv[15] =  m[0]*m[5]*m[10] - m[0]*m[6]*m[9] - m[4]*m[1]*m[10]
             + m[4]*m[2]*m[9] + m[8]*m[1]*m[6] - m[8]*m[2]*m[5];

    det = m[0]*inv[0] + m[1]*inv[4] + m[2]*inv[8] + m[3]*inv[12];
    if (det == 0)
        return GL_FALSE;

    det = 1.0 / det;

    for (i = 0; i < 16; i++)
        invOut[i] = inv[i] * det;

    return GL_TRUE;
}

static void __gluMultMatricesf(const GLfloat a[16], const GLfloat b[16],
    GLfloat r[16])
{
    int i, j;

    for (i = 0; i < 4; i++) {
 for (j = 0; j < 4; j++) {
     r[i*4+j] = 
  a[i*4+0]*b[0*4+j] +
  a[i*4+1]*b[1*4+j] +
  a[i*4+2]*b[2*4+j] +
  a[i*4+3]*b[3*4+j];
 }
    }
}

GLint
gluProject(GLfloat objx, GLfloat objy, GLfloat objz, 
       const GLfloat modelMatrix[16], 
       const GLfloat projMatrix[16],
              const GLint viewport[4],
       GLfloat *winx, GLfloat *winy, GLfloat *winz)
{
    float in[4];
    float out[4];

    in[0]=objx;
    in[1]=objy;
    in[2]=objz;
    in[3]=1.0;
    __gluMultMatrixVecf(modelMatrix, in, out);
    __gluMultMatrixVecf(projMatrix, out, in);
    if (in[3] == 0.0) return(GL_FALSE);
    in[0] /= in[3];
    in[1] /= in[3];
    in[2] /= in[3];
    /* Map x, y and z to range 0-1 */
    in[0] = in[0] * 0.5 + 0.5;
    in[1] = in[1] * 0.5 + 0.5;
    in[2] = in[2] * 0.5 + 0.5;

    /* Map x,y to viewport */
    in[0] = in[0] * viewport[2] + viewport[0];
    in[1] = in[1] * viewport[3] + viewport[1];

    *winx=in[0];
    *winy=in[1];
    *winz=in[2];
    return(GL_TRUE);
}

GLint
gluUnProject(GLfloat winx, GLfloat winy, GLfloat winz,
  const GLfloat modelMatrix[16], 
  const GLfloat projMatrix[16],
                const GLint viewport[4],
         GLfloat *objx, GLfloat *objy, GLfloat *objz)
{
    float finalMatrix[16];
    float in[4];
    float out[4];

    __gluMultMatricesf(modelMatrix, projMatrix, finalMatrix);
    if (!__gluInvertMatrixf(finalMatrix, finalMatrix)) return(GL_FALSE);

    in[0]=winx;
    in[1]=winy;
    in[2]=winz;
    in[3]=1.0;

    /* Map x and y from window coordinates */
    in[0] = (in[0] - viewport[0]) / viewport[2];
    in[1] = (in[1] - viewport[1]) / viewport[3];

    /* Map to range -1 to 1 */
    in[0] = in[0] * 2 - 1;
    in[1] = in[1] * 2 - 1;
    in[2] = in[2] * 2 - 1;

    __gluMultMatrixVecf(finalMatrix, in, out);
    if (out[3] == 0.0) return(GL_FALSE);
    out[0] /= out[3];
    out[1] /= out[3];
    out[2] /= out[3];
    *objx = out[0];
    *objy = out[1];
    *objz = out[2];
    return(GL_TRUE);
}

GLint
gluUnProject4(GLfloat winx, GLfloat winy, GLfloat winz, GLfloat clipw,
       const GLfloat modelMatrix[16], 
       const GLfloat projMatrix[16],
       const GLint viewport[4],
       GLclampf nearVal, GLclampf farVal,      
       GLfloat *objx, GLfloat *objy, GLfloat *objz,
       GLfloat *objw)
{
    float finalMatrix[16];
    float in[4];
    float out[4];

    __gluMultMatricesf(modelMatrix, projMatrix, finalMatrix);
    if (!__gluInvertMatrixf(finalMatrix, finalMatrix)) return(GL_FALSE);

    in[0]=winx;
    in[1]=winy;
    in[2]=winz;
    in[3]=clipw;

    /* Map x and y from window coordinates */
    in[0] = (in[0] - viewport[0]) / viewport[2];
    in[1] = (in[1] - viewport[1]) / viewport[3];
    in[2] = (in[2] - nearVal) / (farVal - nearVal);

    /* Map to range -1 to 1 */
    in[0] = in[0] * 2 - 1;
    in[1] = in[1] * 2 - 1;
    in[2] = in[2] * 2 - 1;

    __gluMultMatrixVecf(finalMatrix, in, out);
    if (out[3] == 0.0) return(GL_FALSE);
    *objx = out[0];
    *objy = out[1];
    *objz = out[2];
    *objw = out[3];
    return(GL_TRUE);
}

void
gluPickMatrix(GLfloat x, GLfloat y, GLfloat deltax, GLfloat deltay,
    GLint viewport[4])
{
    if (deltax <= 0 || deltay <= 0) { 
 return;
    }

    /* Translate and scale the picked region to the entire window */
    glTranslatef((viewport[2] - 2 * (x - viewport[0])) / deltax,
     (viewport[3] - 2 * (y - viewport[1])) / deltay, 0);
    glScalef(viewport[2] / deltax, viewport[3] / deltay, 1.0);
}

I'm thinking on porting the entire GLUT library to the iPhone and sharing it on github. Anyone interested?