I received a few interesting comments on my previous entry regarding the new multithreaded topological sort I implemented in TestNG and there is one in particular from Rafael Naufal that I wanted to address:

The @Priority annotation couldn’t be adapted to say which free methods get scheduled first? BTW, the responsibility of knowing which nodes are free couldn’t be moved to the graph of test methods?

This is pushing my current algorithm even further in the sense that we not only want to schedule free nodes as they become available, we also want to schedule them in order of importance.
What makes a node more important than another? Its level of dependencies. The more a node is depended upon, the more beneficial it is to schedule it as soon as possible since this will end up freeing more nodes. Admittedly, you are still bounded by the size of your thread pool, but this is exactly what we want: increasing the pool size should lead to more parallelism and therefore better performance, but the current scheduling algorithm being fair (or random) means that we are not guaranteed to see this performance increase.
My first reaction was to modify my Executor but as it turns out, you can actually do this with the existing implementation. The constructor of all the Executors takes a
BlockingQueue in parameter, which is the queue that the Executor will use to process the workers. Unsurprisingly, there already is a priority queue called PriorityBlockingQueue.
All you need to do is to use that queue instead of the default one when you create your Executor and then make sure that the workers you pass it have a natural ordering. In this case, the weight of a worker is how many other workers depend on it, which is very easy to calculate.
On a related topic, I wanted to get a closer look at how the algorithm I described in my previous blog post actually works. I described the theory and I have tests that show that it seems to work as expected, but it occurred to me that I could actually “view it from the inside” with little effort.
First, I added a method called toDot which generates a Graphviz file representing the current graph. This turned out to be trivial:

/**
* @return a .dot file (GraphViz) version of this graph.
*/
public String toDot() {
  String FREE = "[style=filled color=yellow]";
  String RUNNING = "[style=filled color=green]";
  String FINISHED = "[style=filled color=grey]";
  StringBuilder result = new StringBuilder("digraph g {\n");
  Set<T> freeNodes = getFreeNodes();
  String color;
  for (T n : m_nodesReady) {
    color = freeNodes.contains(n) ? FREE : "";
    result.append("  " + getName(n) + color + "\n");
  }
  for (T n : m_nodesRunning) {
    color = freeNodes.contains(n) ? FREE : RUNNING;
    result.append("  " + getName(n) + color + "\n");
  }
  for (T n : m_nodesFinished) {
    result.append("  " + getName(n) + FINISHED+ "\n");
  }
  result.append("\n");
  for (T k : m_dependingOn.getKeys()) {
    List<T> nodes = m_dependingOn.get(k);
    for (T n : nodes) {
      String dotted = m_nodesFinished.contains(k) ? "style=dotted" : "";
      result.append("  " + getName(k) + " -> " + getName(n) + " [dir=back " + dotted + "]\n");
    }
  }
  result.append("}\n");
  return result.toString();
}

Then I modified the executor to dump the graph every time a worker terminates, and finally, I wrote a shell script to convert these dot files into images and to create an HTML file. I ran a simple test case, processed the files with the shell script and here is the final result.
A yellow node is “free”, green means that the node is “ready” (to be run in the thread pool), grey is “finished” and white nodes haven’t been processed yet. Dotted arrows represent dependencies that have been satisfied.

As you can see, the execution matches very closely what you would expect based on my description of the algorithm and I confirmed that changing the size of the thread pool creates different executions.

Tags: testng

A TestNG user recently requested an interesting feature: method priorities.

The idea is to be able to assign a priority to a test method (or an entire class) to guarantee that it will be run before other methods with a higher priority. Note that this is slightly different from dependent methods, since it’s just about ordering: if a method with a priority 2 fails, methods with higher priorities will still be run.

As it turns out, this is very easy to implement with one of TestNG 5.8 newest features: method interceptors.

TestNG lets you declare a class implementing the interface IMethodInterceptor, whose signature is:

public interface IMethodInterceptor extends ITestNGListener {
  List<IMethodInstance> intercept(List<IMethodInstance> methods, ITestContext context);
}

TestNG passes the list of methods it’s about to run so you get a chance to reorder them. Implementing method priorities with this interface is very simple.

Let’s start with what we want this feature to look like. In the following example, I declare three kinds of priorities:

• Priorities at the method level.
• A priority at the class level.
• No priority. When no priority is defined on a method, we want to look for a priority on the class first, and if none can be found, the priority will receive a default value of 0.

Here is our test:

@Priority(10)
public class PriorityTest {
  @Test
  public void b1() { System.out.println("Default priority");}
  @Priority(-3)
  @Test
  public void a1()  { System.out.println("Priority -3");}
  @Priority(-3)
  @Test
  public void a2()  { System.out.println("Priority -3");}
  @Priority(3)
  @Test
  public void c1()  { System.out.println("Priority 3");}
  @Priority(3)
  @Test
  public void c2()  { System.out.println("Priority 3");}
  @Priority(4)
  @Test
  public void d1()  { System.out.println("Priority 4");}
}

Next, we implement the @Priority annotation:

@Retention(java.lang.annotation.RetentionPolicy.RUNTIME)
@Target({ElementType.METHOD, ElementType.TYPE})
public @interface Priority {
  int value() default 0;
}

Fairly straightforward: we make the annotation valid on methods and types only, and we use the shortcut value() annotation so we can specify @Priority(1).

Now comes the implementation of the IMethodInterceptor:

public class PriorityInterceptor implements IMethodInterceptor {
  public List<IMethodInstance> intercept(List<IMethodInstance> methods, ITestContext context) {
    Comparator<IMethodInstance> comparator = new Comparator<IMethodInstance>() {
      private int getPriority(IMethodInstance mi) {
      int result = 0;
      Method method = mi.getMethod().getMethod();
      Priority a1 = method.getAnnotation(Priority.class);
      if (a1 != null) {
        result = a1.value();
      } else {
        Class cls = method.getDeclaringClass();
        Priority classPriority = cls.getAnnotation(Priority.class);
        if (classPriority != null) {
          result = classPriority.value();
        }
      }
      return result;
    }
    public int compare(IMethodInstance m1, IMethodInstance m2) {
      return getPriority(m1) - getPriority(m2);
    }
  };
  IMethodInstance[] array = methods.toArray(new IMethodInstance[methods.size()]);
  Arrays.sort(array, comparator);
  return Arrays.asList(array);
}

The heart of this implementation is our Comparator, which tries to find a @Priority annotation the method it receives in parameter. If it can’t find any, it looks on the declaring class, and failing to find one there as well, assigns it a default value. The intercept() method simply sorts the methods with this comparator and returns it.

Now, let’s run our test without using that interceptor:

<suite name="Example">
  <test name="Method interceptor example" >
    <classes>
      <class name="priority.PriorityTest" />
    </classes>
  </test>
</suite>

As expected, the output is fairly random:

Priority 3
Default priority
Priority 3
Priority -3
Priority -3
Priority 4

Now we declare our interceptor in the testng.xml file:

<suite name="Example">
  <listeners>
    <listener class-name="priority.PriorityInterceptor" />
  </listeners>
  <test name="Method interceptor example" >
    <classes>
      <class name="priority.PriorityTest" />
    </classes>
  </test>
</suite>

And we get the expected outcome, with our method without any @Priority receiving the class priority (10) since it didn’t define any itself:

Priority -3
Priority -3
Priority 3
Priority 3
Priority 4
Default priority

To verify that our class priority implementation works, we can remove the @Priority class annotation. In this case, our method without any @Priority should receive a priority of 0:

Priority -3
Priority -3
Default priority
Priority 3
Priority 3
Priority 4

As you can see, Method Interceptors allow you to replace TestNG’s ordering of test methods with your own. It’s particularly powerful if used in conjunction with annotations, as shown in this example, but it’s also possible to imagine other external configuration factors to customize TestNG’s running engine to your liking.

Tags: testng