Emma Code Coverage Tool Fixed 64 Bit Support (2.1.5320)

Posted by & filed under java, programming, Technology.

So I’ve been spending my time trying to come up with a fix for 64bit JVM support in EMMA for some tools I’ve been building.  Unforunately active development on EMMA has died, and although there have been talks about forking the project nothing has really happened with this project since 2005.  EMMA 2.1 is really neat because it comes with some tools that allow you to do instrumentation on the fly, while applications remain running.

This can allow you to do coverage of your apps against live automation tests instead of just JUnit test cases.  If you’ve ever tried to run EMMA in a 64bit JVM you’ll know that you get a wonderful ArrayIndexOutOfBounds Exception the second you try to instrument the code.  This issue is known and there is a bug filled in the bug tracker for EMMA but since no one is actively maintaining it nothing has really been done to fix it.

If you checkout the bug tracker (here) a nice fellow by the name of Lukas has generated a patch to fix this issue, and even provided a patched version of emma.jar on his blog.  Unfortunately this patch and the patched emma.jar are for 2.0.5312 which does not have support for the CTL tool.  This is the tool that allows you to do instrumentation on the fly without relying on a JVM shutdown to write coverage information.

With all this information in hand I decided that I would patch the latest 2.1.5320 codeline in order to bring 64bit support to the Emma 2.1 branch.  This was a little more difficult then I originally thought, but luckily I wound up getting everything working in the end.

I am providing here a copy of the patched emma.jar (version 2.1.5320 fixed) in hopes that it may help some people out and perhaps spur some people to fork EMMA and get development started again on this project.  I’d definitely be more than willing to help get something like that started.

Please see the EMMA license for distribution. Please note I do not plan to release newer versions of Emma.

Fixed version of Emma 2.1.5320: http://www.kungfuice.com/wp-content/uploads/2009/07/emma.jar

Reversing a String in Scala

Posted by & filed under programming, Scala, Technology.

So I’ve been reading “Programming in Scala” by Martin Odersky, Lex Spoon and Bill Venners and I’ve been coming up with ways to get myself thinking and programming more in Scala.  Since I spent a better part of my week interviewing people I thought I’d take some time to write the famous “Reverse a String” interview question.  This is a pretty straight forward thing to do and thought it would be fun to experiment with some of Scala’s other cool features to get my feet wet.

On my first attempt I wound up with my usual tail-recursive implementation that makes use of an accumulator.

/**
 * Wrapper function.
 */
def reverse(str: String) : String = {
      if ((str == null) || (str.length() <= 1))
          str
      reverse(str, "")
  }

 /**
   * tail call recursive with accumulator
   */
  def reverse(str: String, acc: String) : String = {
      if (str.length() == 0)
        acc
      else
        reverse(str.substring(1), str.charAt(0) + acc);
  }

This seemed pretty standard to me.  It doesn’t differ much from the Java implementation I’ve written a hundred times, nor is it really all that interesting.  I decided to jump ahead a few chapters in the book to see what I could accomplish using a left fold.  For those unfamiliar with what a fold left operation is I point you to the Wikipedia entry on it here.  The basic idea as stated in the book ”Programming in Scala“ is this: “A fold left operation (z /: xs) (op) involves three objects: a start value z, a list xs, and a binary operation op.  The result of the fold is op applied between successive elements of the list prefixed by z.”

Ok that seems like it applies very well to what we are trying to accomplish.  Rewritting the above methods into one clean line of Scala code yielded the following

/**
   * This will fold the list left, and should run in constant time allocation
   */
  def reverseLeft[T](xs: List[T]) = (List[T]() /: xs) {(ys, y) => y :: ys}

Pretty beautiful isn’t it?  It’s amazingly simple and achieves the same thing as the tail-recursive implementation.  I can’t express how excited I am to get through this book and really start doing real programming with Scala.

So I guess the next time you go for an interview try and remember this for the answer and see how the interviewers faces light up, either with glee or rage that you didn’t solve it using the standard recursive implementation :)

Until next time …

Really Funny XKCD Comic

Posted by & filed under Technology.

A co-worker sent this to me yesterday and I definitely had a good laugh since for many years I’ve joked about calling my kid “URL”, pronounced EAARRLLL.  I definitely think this name is a better though and could definitely lead to some very comical situations.

XKCD A Webcomic SQL

XKCD A Webcomic

I hope you all enjoy this, now back to work!

Ext-JS Tasks & Progressbars a match made in heaven

Posted by & filed under Javascript, programming.

I’ve been working on some stuff that requires me to execute some long running tasks on a server from a web based client.  I really wanted to a way to let the user know what was going on, and I figured a progress bar would be the best way to let them know what was going on and how much longer it was going to be before the task was complete.

Using Ext-JS this task was actually a lot easier then I had originally thought. Ext has these two great classes called TaskRunner and TaskManager.  These classes basically allow you to create a task for execution in a multithreaded manner (we all know that JavaScript is only single threaded so this definitely will never be executed in parallel but we can all dream).  Here’s an example from the Ext API on how to setup a task to run a simple clock that updates every second.

// Start a simple clock task that updates a div once per second
var task = {
    run: function(){
        Ext.fly('clock').update(new Date().format('g:i:s A'));
    },
    interval: 1000; //1 second
}
var runner = new Ext.util.TaskRunner();
runner.start(task);

In my case I wanted to setup a task that would execute every 10 seconds and ask the server what the progress of my longrunning task was.  I then used the information returned from the server to update the progress bar on page.

//Create the success handler for the Ajax request
function successHandler (response, options) {
    if(response) {
        try {
           var json = Ext.util.JSON.decode(response.responseText);
        } catch (err) { return; }
        if (!json.done) {
           //update the progressBar by parsing the percentage updated
           //by the server and returned in the json response.
           percentage =json.results[0].strPercent;
           progressBar.updateProgress(json.results[0].percentage,
                                     'Task ' + percentage + ' Complete';
        }
        else { progressBar.updateProgress(1, 'Done'); }
}

var task = {
	run: function() {
		Ext.Ajax.request({
			url: 'mystatus'
			success: successHandler,
			params: { processId: processId }
		});
	},
	interval 10000; //10 seconds
}

var runner = new Ext.util.TaskRunner();
runner.start(task);

Now I’ve let some code out here for handling the failure case of the Ajax request and a couple of other functions for handling what I’m actually doing on the server but you can start to see that with the combination of the TaskRunner and the ProgressBar adding “background” worker threads to your interface becomes a lot easier.

Unfortunately this solution is not necesarilly optimal since the client will constantly be polling the server asking what’s going on.  A much better solution to this would be to implement a comet based service that allowed the server to merely report to the user its status and when it was complete.

Currently Ext does not have any comet handling functionality, but if you watch for my next post I’ll show how you can implement a comet based Servlet in Tomcat 6 and create a client that will listen for updates from the server.

Tail Recursive Algorithms In Scala

Posted by & filed under Computers, java, programming.

< ![endif]–>After the NFJS conference this weekend I have been spending more and more time working in Scala and trying to learn the ins-and-outs of the language.  One of the neat things I came across was tail recursive algorithm optimization within the language itself.

When writing in a functional language like Scala you rely heavily on recursive algorithms to do your work, instead of iterative algorithms more present in OO languages like Java. This leads to an interesting problem with running functional languages within the JVM.

The Java Virtual Machine does not have support for tail-recursive algorithm optimizations.  What does that mean? Basically the JVM cannot spot when to optimize calls stacks for recursive algorithms. Well who cares right? If you’re writing in Java this issue doesn’t usually come up since most of us simply write our loops and are happy with the performance the JVM offers us.

However, when you are writing a lot of recursive algorithms you quickly start to see how tail-recursive algorithms help makes your code more efficient.

For those of you who don’t remember what a tail-recursive algorithm is, here is a short little explanation:

A Tail-recursive function is a function that ends in a recursive call to itself (effectively not building up any deferred operations). Tail recursive functions have the ability to re-use the same stack frame over and over and therefore are not bound by the number of available stack frames.  Many people have written the simple factorial function recursively, but many have noticed that if you pass it a value of N that is large enough you will see a dreaded Out of Memory exception.

The reason for this is due to the factorial functions deferred operation statement that comes at the end of the method. Let’s look at the simple factorial algorithm

//INPUT: n is an Integer such that n >= 1
int fact(int n) {
   if (n == 1)
      return 1;
   else
      return n* fact(n-1);
}

H You can see that at then end of the algorithm we have a deferred operation of multiplying n with the next value computed from factorial, this goes on and on until we finally hit a factorial function that returns one, at which point the stack is popped and everything returns nicely. However we are now bound by the available stack frames in terms of computing n (Also by the max size of an int, but that’s beside the point).

In a tail-recursive algorithm you do not see this deferred execution, and therefore the same stack frame can be reused over and over again. Here is the same algorithm rewritten using a tail-recursive algorithm.

//INPUT: n is an Integer such that n >= 1
int fact(int n) {
    return fact_support(n, 1);
}

int fact_support(int n, int acc) {
    if (n == 0) return acc;
    else return fact_support(n-1,acc*n);
}

As you can see there are no deferred operations in this example we have effectively gotten rid of having to use n number of stack frames. Each call to fact_support brings with it the current accumulated sum, and thus does not need to wait to “pop” the stack and rely on the stack pop to accumulate the sum of the factorials.

As you can see tail-recursive optimizations are very important to languages where recursion is relied on heavily. Without this type of optimization many of the recursive algorithms are now bound by the number of available stack frames.

So that can’t be so hard right? Why not just write all your algorithms to use tail-recursion? Well for one it’s not always possible to do this, but also it puts a lot of work in the hands of the developer. We have this beautiful thing called the JVM that should be able to spot cases where optimization can occur.

Unfortunately the JVM doesn’t know how to spot this optimization, therefore the Scala compiler must look at ways of optimizing your code. Even more unfortunate the Scala documentation explicitly states that you should not rely on the Scala compiler making this optimization.

It may optimize your code, but it may not as well, so really the only way to be sure is to write your algorithms guaranteeing that tail-recursion is being utilized from the get-go.

It would be really nice to see the JVM improved to allow for this type of optimization to be done in the Hotspot, and there has been talk about improving the JVM to support functional languages, but I guess time will only tell.