Monday, July 07, 2014

Arena Allocation in Go

Update: The optimization described here is accepted in the benchmarks game. Go is now at par with most other GC-ed languages in the binary-trees benchmark!

One of the weaknesses of Go's runtime today is the relatively naive GC implementation. This is evident from go performing consistently worse than most other languages in the binary trees benchmark. However, the language can make designing programs that reduce GC cost fairly straightforward.

On my laptop, the Go program runs in 32.32s and consumes 348.3 MB of resident memory. In comparison, the Haskell version (with "+RTS -N4 -K128M -H -RTS") runs in 16.06s and consumes 772.6MB!

The code used in the benchmark creates and discards several binary trees by allocating each node individually. A small change in the code to allocate several nodes whenever allocation is required, instead of just one, can significantly reduce the amount of work performed by GC. This technique is called arena allocation.

The NodeArena type's Get method returns a pointer to an element in the slice and allocates in chunks of 10,000 when the slice becomes empty.


The bottomUpTree function that creates the trees takes a pointer to NodeArena and uses it to create the nodes for the trees.


With arena allocation, the Go code runs in 15.73s and consumes 268.9 MB of memory. This fairly trivial change reduced the running time by 51% and memory consumption by 22.8%!

For the curious, if I give the Go GC as much memory as the Haskell version by setting GOGC=425, it runs in under 9s!

Note: All measurements are using go 1.3 and ghc 7.8.2, with the same build and runtime options as in the benchmarks game.

Friday, April 06, 2012

Go Does Delegates Beautifully!


When working with object-oriented languages, there are many instances when one would want to implement an interface re-using code from another implementation of the interface. While inheritance will work, it couples the new implementation to the specific other implementation. Composition with delegation will be a better way of doing this.

Let's consider an application which deals with doors of different shapes. You'd have a Door type and a Shape interface implemented by different concrete shapes. You'd also have a DrawingSurface which takes any implementation of Shape and invokes draw() and fill() on it passing a graphics context.

Here's the verbose and repetitive code you'd have in Java with neither delegates nor any form of duck-typing.


In a dynamic language with meta-programming like Ruby, this is less verbose but the delegates still need to be explicitly defined. The forwardable library defines the specified methods on Door to invoke corresponding methods on @shape at run-time. However, tools like IDEs can't recognize Door as an implementation of Shape unless they handle the specific library call as a special case.


Go gives you delegates with no extra work. You just say Door has a Shape and you get statically checked and compiled delegation.


This has all the compile-time safety checks of Java with the expressiveness of Ruby. This is one of the many cases where Go's simple design makes code less verbose!

Friday, January 22, 2010

How Git shines above Subversion at Merging

I've recently started getting my head around Git having been a Subversion (sadly even CVS) user all along. While I liked the fact that it was distributed and way faster than Subversion at most operations, I couldn't understand why many claimed it was better at merging than Subversion (1.5 and above). Even the "Branch Handling" section in Git's wiki talks only about better history tracking but not about how Git is better at merging the content themselves.

While correct history tracking is important, merging without breaking the code is an absolute must. So I wanted to see if there was a place where Subversion would silently break the code during a merge but Git would not. This might not be new to long time Git users but I hope this would help many Subversion users take another look at Git. Without further ado, lets see how Git manages merges better.

The Workflow

You initially start off with a file named Test.java in both SVN and Git repositories with initial content as below.


You then create a branch named "refactor" and within this branch rename the class to NicerName (and consequently rename the file too) and commit to the branch.


You switch back to the main branch (trunk/master) and fix a bug. In this case we change the message being printed to "Correct Message" and commit to the main branch.


Finally, we merge the changes from the refactor branch into the main branch.

The commands

SVN would do it with the following commands.


Git would do the same with these commands.


The Result

Neither SVN nor Git complain about conflicts which is fine. However, after the merge, SVN leaves two files in the main branch. NicerName.java has the new name but doesn't have the fix while Test.java has the fix but not the new name. Here is how it looks in SVN.



Essentially your code is broken silently by SVN during the merge. On the other hand Git handles this very cleanly. It leaves only NicerName.java back including the fix to the message and removes Test.java, exactly as you'd expect.


Over all the branching and merging commands looked cleaner with Git too. This kind of excellent support for branching, refactoring and merging back alone should make everyone give Git a serious consideration. Even if Git is used in a centralized workflow just like Subversion, it can still provide huge benefits over Subversion. If you utilize its distribution features too, it just gets better!

Sunday, December 13, 2009

Simple Layouts with JSP in Spring MVC

Every web application has elements common to all its pages which are good candidates for re-use. While Spring MVC provides integration with Tiles, it can be an overkill for simple applications and needs using Spring's client side JS library for AJAX (correct me if I'm wrong).

For most applications, standard JSPs can serve as good layout engine. This post shows how Spring's handler interceptor can be used to specify a normal JSP file as the layout for a Spring MVC web application.

This interceptor allows you to specify a JSP file containing the layout for the application into which the actual views get plugged. The interceptor takes the actual model and view and replaces the actual view with the layout view's name and puts the actual view name into the model map to be used by the layout file. If you do not want to include the layout for certain requests (AJAX requests) you can prefix the view name with "noLayout:".

The Interceptor
public class LayoutInterceptor extends HandlerInterceptorAdapter {
private static final String NO_LAYOUT = "noLayout:";

private String layoutView;

@Override
public void postHandle(HttpServletRequest request, HttpServletResponse response, Object handler, ModelAndView modelAndView) throws Exception {
super.postHandle(request, response, handler, modelAndView);

String originalView = modelAndView.getViewName();

if (originalView != null && !originalView.startsWith("redirect:")) {
includeLayout(modelAndView, originalView);
}
}

private void includeLayout(ModelAndView modelAndView, String originalView) {
boolean noLayout = originalView.startsWith(NO_LAYOUT);

String realViewName = (noLayout) ? originalView.substring(NO_LAYOUT.length()) : originalView;

if (noLayout) {
modelAndView.setViewName(realViewName);
} else {
modelAndView.addObject("view", realViewName);
modelAndView.setViewName(layoutView);
}
}

public void setLayoutView(String layoutView) {
this.layoutView = layoutView;
}
}

Sample Usage
<bean class="org.springframework.web.servlet.mvc.annotation.DefaultAnnotationHandlerMapping">
<property name="interceptors">
<list>
<bean id="layoutInterceptor" class="LayoutInterceptor">
<property name="layoutView" value="layout"></property>
</bean>
</list>
</property>
</bean>

<bean id="viewResolver" class="org.springframework.web.servlet.view.InternalResourceViewResolver">
<property name="viewClass" value="org.springframework.web.servlet.view.JstlView"></property>
<property name="prefix" value="/WEB-INF/jsp/"></property>
<property name="suffix" value=".jsp"></property>
</bean>
With that all the views returned by controllers can be included within the layout JSP by including the following line in WEB-INF/jsp/layout.jsp.
<jsp:include page="/WEB-INF/jsp/${view}.jsp"></jsp:include>

Sunday, November 01, 2009

Mocking Math.random() using PowerMock

Let's consider the below Game class in a guessing game where a random target is chosen by the system and the user guesses the target. The system returns an appropriate message based on whether the guess was higher, lower or equal to the random target.

package org.game;

public class Game {
private int target = (int) (Math.random() * 100);

public int guess(int guess) {
return target - guess;
}
}

No magic there. Now let's look at the unit test for this class.

package org.game;

// imports hidden;

public class GameTest {
private Game game;

@Before
public void setUp() {
game = new Game();
}

@Test
public void testHigherGuess() {
int result = game.guess(55);
Assert.assertTrue(result < 0);
}

@Test
public void testLowerGuess() {
int result = game.guess(35);
Assert.assertTrue(result > 0);
}

@Test
public void testCorrectGuess() {
int result = game.guess(50);
Assert.assertTrue(result == 0);
}
}

As you might have guessed by now this wouldn't work as the target is randomly generated. Now we have three options to handle this.
  1. Add a constructor taking the target value as argument and set the target using that. This would make passing a non-random value for testing simple. However, this would change the interface of the class unnecessarily.
  2. Access "target" using reflection and set its value after object creation. However, this would make the unit test fragile as it knows too much about the internals of the class under test.
  3. We can make Math.random() to return a constant value within our test case. This is the approach demonstrated in this post.
PowerMock is a mocking framework which extends several popular frameworks to allow mocking of static methods and more. In this post we'll use PowerMocks' extension for EasyMock. The general technique to mock static methods using PowerMock is outlined here.

This wouldn't work for system classes like Math. To workaround this, we can prepare the class using the static method for test rather than the class containing the static method. Which means we'd be using @PrepareForTest(Game.class) instead of @PrepareForTest(Math.class) in our case. The completed unit test would look like this.

package org.game;

// imports hidden

@RunWith(PowerMockRunner.class)
@PrepareForTest(Game.class) // Preparing class under test.
public class GameTest {
private Game game;

@Before
public void setUp() {
// Mocking Math.random()
PowerMock.mockStatic(Math.class);
EasyMock.expect(Math.random()).andReturn(0.50).anyTimes();
PowerMock.replay(Math.class);

game = new Game();
}

@Test
public void testHigherGuess() {
int result = game.guess(55);
Assert.assertTrue(result < 0);
}

@Test
public void testLowerGuess() {
int result = game.guess(35);
Assert.assertTrue(result > 0);
}

@Test
public void testCorrectGuess() {
int result = game.guess(50);
Assert.assertTrue(result == 0);
}
}

Now PowerMock ensures that any call to Math.random() would always return a constant value within the Game class when used for testing. Hence we can test the guess() method just as how any client code using the Game class would.

Friday, August 28, 2009

ScriptEngineBuilder for Java

Java 6 allows you to execute and communicate with scripts written in any scripting language, using the Scripting API. However, the code needed to create a ScriptEngine and evaluate a set of script files within it, is quite verbose and throws several checked exceptions.

I decided to create a simple fluent Builder which can be used to create a ScriptEngine and execute a set of script files inside it. It also allows you to add Java Objects into the engine before executing the script files.

ScriptEngineBuilder
import java.io.InputStreamReader;
import java.net.URL;

import javax.script.ScriptEngine;
import javax.script.ScriptEngineManager;

public class ScriptEngineBuilder {
private ScriptEngine engine;

public ScriptEngineBuilder(String shortName) {
this.engine = new ScriptEngineManager().getEngineByName(shortName);
}

public ScriptEngineBuilder add(String scriptResource) {
try {
URL scriptURL = getClass().getResource(scriptResource);
InputStreamReader scriptReader = new InputStreamReader(scriptURL.openStream());
engine.eval(scriptReader);

return this;
} catch (Exception e) {
throw new RuntimeException(e);
}
}

public ScriptEngineBuilder put(String key, Object value) {
engine.put(key, value);
return this;
}

public ScriptEngine build() {
return engine;
}
}


Applications can create an instance of ScriptEngineBuilder by passing the shortName of the engine to the constructor. Then they can invoke add() method for the script files to be evaluated (as classpath resource name). They can finally invoke build() to get the ScriptEngine instance.

Sample Invocation
ScriptEngine engine = new ScriptEngineBuilder("js").add("/script1.js").put("myObj", obj).add("/script2.js").build();

Monday, October 06, 2008

Shortcuts in JSF web applications using AJAX4JSF

AJAX4JSF is library of JSF components which can be used to easily add AJAX capabilities to JSF web applications. AJAX4JSF is available as part of the Richfaces component library.

Goal

For this example, let us consider a simple goal of listing a set of products or services based on the category chosen by the user. A combo box is presented to the user, where he can choose between "Products" and "Services". Based on his choice a list of products or services is retrieved from the server and displayed.

The user can also hit "Ctrl + 1" to list all products and "Ctrl + 2" to list all services, instead of choosing from the combo box.

Compromises

While in real world scenarios, the list of products/services will have to retrieved from a DB, to keep the example simple, we just swap between 2 predefined lists of Strings.

How does it work?

<a4j:support> tag is used to send an AJAX request to the server whenever the combo box selection changes.

<a4j:support event="onchange" action="#{dataLoader.updateCurrentData}"
rerender="currentItemsTable">
</a4j:support>

Providing shortcut keys involves two steps.

  1. Using <a4j:jsFunction> tag to define a Javascript function which takes the category as parameter.

  2. Writing Javascript code to check for keystrokes and invoke the JS function define in step-1 with appropriate parameters.


The <a4j:jsFunction> tag
This tag simplifies the client side process of initiating AJAX request from Javascript. The value specified for its name attribute is used as the name of the Javascript function generated. It also takes the JSF action to be invoked and the region of page to be re-rendered after the AJAX request as attributes.

<a4j:actionparam> tag can be used to define the parameters to be accepted by the generated JS frunction and the managed bean property to which they are to be assigned. In our case the key pressed is passed as parameter to the generated JS function, "updateData()".


<a4j:jsFunction name="updateData"
action="#{dataLoader.updateCurrentData}"
reRender="currentItemsTable">
<a4j:actionparam name="choice"
assignTo="#{dataLoader.currentChoice}" />
</a4j:jsFunction>

The Javascript code

This fragment of Javascript is used to check for keystrokes and invoke the generated JS function with appropriate parameter.


var ctrlPressed;

document.onkeydown = function(e) {
var keyCode;

if (window.event)
keyCode = window.event.keyCode;
else if (e.which)
keyCode = e.which;

if (keyCode == 17)
ctrlPressed = true;

if (ctrlPressed) {
switch (keyCode) {
case 49:
updateData(1);
break;
case 50:
updateData(2);
break;
}
}

}

document.onkeyup = function(e) {
var keyCode;

if (window.event)
keyCode = window.event.keyCode;
else if (e.which)
keyCode = e.which;

if (keyCode == 17)
ctrlPressed = false;
}

For further details of implementation, look into the complete source code archive provided below. This archive does not include the JSF and Richfaces libraries. You'll have to download them separately before being able to successfully execute this code.