Saturday, April 19, 2008

Threadsafe Lazy Instantiation Without Synchronized

The Problem to Solve

When I first read about the Threadsafe Lazy Singleton pattern, I was impressed by its elegance and wished there was something equally elegant for threadsafe lazy-loading of instance fields without the Java synchronized keyword. In most cases, declaring my fields as final and initializing them in the Constructor, even if they are never used in a given run of an application, has been satisfactory because Object allocation is generally cheap. Recently, however, I have encountered a situation where eagerly-loading a field is prohibitively expensive. The field must also be accessed in a threadsafe way. Because the accessor method will be called frequently after the first time it is called, I would prefer not to wrap the accessor implementation with a synchronized block (even though the performance hit can be small). This situtation has provided the right opportunity for me to investigate how the Java 5 concurrency utilities might help.

Start with a Test

Personally, I find it good practice to start the implementation of any new feature with a test. Here we want to verify that, if multiple threads call an accessor that lazily creates an Object, then the same Object instance is always returned from the accessor.
Since we are writing a test of thread-safety, it makes sense that the test case should use multiple threads. All threads should start at the same time and the results from each thread's execution should be evaluated only after all the threads have finished. This appears to be an opportunity to use a CountDownLatch, or rather two CountDownLatches: the first signals all threads to start; the second signals when all threads have finished.

So the structure of our test case can be mapped out as follows:

  • Setup some threads that will call the lazy-accessor method.
  • Run the threads to completion.
  • Collect the results from the lazy-accessor calls in each thread.
  • Verify that the same Object has been returned for every call.

The code below provides a starting point for what we need.


public class TestLazyCreation {
private static final int NUMBER_OF_THREADS = 10;
private CountDownLatch startSignal;
private CountDownLatch doneSignal;

@Before
public void setUp() {
startSignal = new CountDownLatch(1);
doneSignal = new CountDownLatch(NUMBER_OF_THREADS);
}

@Test
public void threadsafeLazyCreationReturnsExactlyOneInstance()
throws Exception {
final List<Future<Object>> futures =
submitCallables(/*A class instance with an accessor*/);
allowTheThreadsToRunToCompletion();
assertThatExactlyOneNonNullObjectWasReturned(futures);
}

private List<Future<Object>> submitCallables(/*A class with an accessor*/) {
final ExecutorService executorService = Executors
.newFixedThreadPool(NUMBER_OF_THREADS);
final List<Future<Object>> futures = new ArrayList<Future<Object>>();
for (int i = 0; i < NUMBER_OF_THREADS; i++) {
futures.add(
executorService.submit(/*The accessor class wrapped with a Callable*/));
}
return futures;
}

private void allowTheThreadsToRunToCompletion() throws InterruptedException {
Thread.sleep(250);
startSignal.countDown();
doneSignal.await();
}

private static void assertThatExactlyOneNonNullObjectWasReturned(
final List<Future<Object>> futures) throws InterruptedException,
ExecutionException {
final Set<Object> lazilyCreatedObjects = new HashSet<Object>();
for (final Future<Object> future : futures) {
lazilyCreatedObjects.add(future.get());
}
assertEquals(1, lazilyCreatedObjects.size());
assertNotNull(lazilyCreatedObjects.iterator().next());
}
}

Typical Lazy Instantiation

We still need to fill in the code above in two spots:
  • We need a class with an accessor.
  • We need a Callable that wraps that accessor class.
This code should suffice for the accessor class:

abstract class LazyGetter {
protected Object performLongRunningInitialization() {
try {
Thread.sleep(1);
} catch (final InterruptedException e) {
}
return new Object();
}
abstract Object get();
}

class TypicalLazyGetter extends LazyGetter {
private Object lazilyCreatedObject;
@Override
Object get() {
if (lazilyCreatedObject == null) {
lazilyCreatedObject = performLongRunningInitialization();
}
return lazilyCreatedObject;
}
}

This inner class inside TestLazyCreation will work as a Callable wrapper that uses the startSignal and doneSignal setup by the test class:

private final class CallableLazyGetter implements Callable<Object> {
private final LazyGetter lazyGetter;

CallableLazyGetter(final LazyGetter lazyGetter) {
this.lazyGetter = lazyGetter;
}

public Object call() throws Exception {
try {
startSignal.await();
return lazyGetter.get();
} finally {
doneSignal.countDown();
}
}
}

Now we can change the TestLazyCreation class to use the lazy accesor and the Callable wrapper just defined:

public class TestLazyCreation {
....
@Test
public void threadsafeLazyCreationReturnsExactlyOneInstance()
throws Exception {
final List<Future<Object>> futures = submitCallables(new TypicalLazyGetter());
....
}

private List<Future<Object>> submitCallables(final LazyGetter lazyGetter) {
....
futures.add(executorService.submit(new CallableLazyGetter(lazyGetter)));
....
}
....
private final class CallableLazyGetter implements Callable<Object> {
....
}
}

Looking at the code above, what do you think will happen when we run this test case?
Try running it a few times. What do you see?

My typical JUnit results show a failure similar to this:

JUnit test case failure because the accessor is not threadsafe.

The TypicalLazyGetter could be called NotThreadsafeLazyGetter. So how can we make this type of lazy instantiation threadsafe?
Java provides three keywords that are often associated with a class' synchronization policy: synchronized, final and volatile.
We can declare lazilyCreatedObject final and instantiate it in the constructor for TypicalLazyGetter, but then the Object would not be created lazily, so that solution is not what we want.
We can change the accessor declaration to synchronized Object get(), but we are trying to avoid the synchronized keyword.
We can change the declaration of lazilyCreatedObject to private volatile Object lazilyCreatedObject, but this does not solve our problem because the test-then-set critical section of the accessor method is not atomic. Run the test case again using the volatile declaration if you do not believe me.

Threadsafe Lazy Instantiation

The solution is fairly simple and boilerplate, if not as compact as the typical non-threadsafe lazy instantiation method. The key is to use an AtomicReference, and in particular, the method compareAndSet(V expect, V update). The code below will satisfy what we need:

class ThreadsafeLazyGetter extends LazyGetter {
private final AtomicReference<Object> lazilyCreatedObject =
new AtomicReference<Object>();

@Override
Object get() {
final Object existingValue = lazilyCreatedObject.get();
if (existingValue != null) {
return existingValue;
}
final Object newValue = performLongRunningInitialization();
if (lazilyCreatedObject.compareAndSet(null, newValue)) {
return newValue;
}
return lazilyCreatedObject.get();
}
}

What is the worst that could happen?
Multiple threads might enter the accessor, see that the lazilyCreatedObject referent has not been set and call performLongRunningInitialization(). As long as performLongRunningInitialization() can be called multiple times (i.e., it does not have side-effects or requirements that it be called at most once), then we should be safe. The accessor will return the same instance of the lazilyCreatedObject each time it is called.
Now we can modify our test class as follows:

@Test
public void threadsafeLazyCreationReturnsExactlyOneInstance()
throws Exception {
final List<Future<Object>> futures = submitCallables(new ThreadsafeLazyGetter());
allowTheThreadsToRunToCompletion();
assertThatExactlyOneNonNullObjectWasReturned(futures);
}

@Test(expected = AssertionError.class)
public void nonThreadsafeLazyCreationCanReturnMultipleInstances()
throws Exception {
final List<Future<Object>> futures = submitCallables(new NotThreadsafeLazyGetter());
allowTheThreadsToRunToCompletion();
assertThatExactlyOneNonNullObjectWasReturned(futures);
}

The second test case is silly but emphasizes that we expect the typical NotThreadsafeLazyGetter to fail in a mutli-threaded environment.

Lazy Instantiation in Eclipse

As previously mentioned, Object allocation is cheap with the latest releases of Java, so lazy-instantiation is often not necessary. Because I have spent the last 1 1/2 years programming Eclipse plug-ins, an example from Eclipse might provide a demonstration of a good use of lazy-instantiation.
First, we can define a class that lazily instantiates an Object from an Eclipse plug-in that does not typically get started when Eclipse is started. For this example, I chose to use something from org.eclipse.xsd:

class ClassThatLazilyCreatesAnObjectInAnotherPlugin {
private final AtomicReference<XSDSimpleTypeDefinition> lazilyCreatedObject =
new AtomicReference<XSDSimpleTypeDefinition>();

XSDSimpleTypeDefinition get() {
final XSDSimpleTypeDefinition existingValue = lazilyCreatedObject.get();
if (existingValue != null) {
return existingValue;
}
final XSDSimpleTypeDefinition newValue = XSDFactory.eINSTANCE
.createXSDSimpleTypeDefinition();
if (lazilyCreatedObject.compareAndSet(null, newValue)) {
return newValue;
}
return lazilyCreatedObject.get();
}
}

Next, we create a "Hello World" Command Contribution using the standard Eclipse Extension Wizard. We can insert the following code into the generated Hello World AbstractHandler:

private boolean firstTimeIn = true;

public Object execute(final ExecutionEvent event) throws ExecutionException {
final IWorkbenchWindow window = HandlerUtil
.getActiveWorkbenchWindowChecked(event);
if (firstTimeIn) {
new ClassThatLazilyCreatesAnObjectInAnotherPlugin();
MessageDialog.openInformation(window.getShell(),
"Threadsafe Lazy Initialization Plug-in",
"The Sample Object has been created.");
firstTimeIn = false;
} else {
new ClassThatLazilyCreatesAnObjectInAnotherPlugin().get();
MessageDialog.openInformation(window.getShell(),
"Threadsafe Lazy Initialization Plug-in",
"The Internal Object from another plug-in has been created.");
}
return null;
}

The implementation is a toy example, so do not read much into it. The first time the command is executed, the ClassThatLazilyCreatesAnObjectInAnotherPlugin is instantiated. During each subsequent command execution, the ClassThatLazilyCreatesAnObjectInAnotherPlugin is instantiated and its accessor is called.

Now on the Manifest.MF Overview, we can run an Eclipse application that uses our Command contribution. In the launch configuration, on the Arguments tab, make sure to pass the Program argument -console to start the OSGi console so we can view plug-in state when we execute our command.

Use the launch configuration to start the osgi console.

After the Eclipse workbench comes up, we will see a new Coolbar button for our Command contribution. We will also see in your console view the osgi> prompt (For a good introduction to using the osgi console for more than viewing plug-in state, see Explore Eclipse's OSGi console).
In the console, type ss to see the state of all the plug-ins in the running Eclipse application, and look for the org.eclipse.xsd plug-in. You will see something like this:

836 <<LAZY>> org.eclipse.xsd_2.4.0.v200801152000

Now press our Command contribution button once so the dialog pops up. Again, type ss in the osgi console. The org.eclipse.xsd plug-in state has not changed:

836 <<LAZY>> org.eclipse.xsd_2.4.0.v200801152000

Press our command contribution button once more so the dialog pops up again. Type ss in the osgi console and what do you see?   The org.eclipse.xsd plug-in has been activated!  If you are as fortunate as I am to be running on low-powered hardware, you might even notice the slight lag before the dialog pops up as the plug-in is being activated:

836 ACTIVE org.eclipse.xsd_2.4.0.v200801152000

There you have it: in Eclipse, it does make sense in some cases to use lazy-instantiation. In this case, if the XSDSimpleTypeDefinition were created in the class' constructor, then the xsd plug-in would be activated even if the Command were never executed more than once in a given run of the Eclipse application. It is a contrived example, but the situation does apply not infrequently.   For plug-ins that are expensive to start, the usefulness is obvious.


Thursday, April 10, 2008

ODA Ecore Getting Started Guide

Overview


Now that the ODA Ecore enablement plug-ins are in the Data Tools Project incubator at Eclipse, a quick-start guide seems in order.
The Oda Ecore enablement plug-in provides a JDBC-like interface for querying object models defined with EMF. These queries are written with OCL and use the EMF Model Query OCL bridge.
The Oda Ecore UI plug-in contributes two Wizards for configuring BIRT reports: the first allows specification of a Data Source; the second provides a graphical interface for constructing queries.

Dependencies


In order to use the Oda Ecore enablement plug-in, you will need to install the following dependencies:

Datatools Connectivity
EMF Query
EMF Model Query OCL Integration
The Data Tools Platform Enablement for JDBC

In addition, to run the example, you will need to install the following plug-ins:
BIRT (for reporting query results)
EMF Examples (for the extlibrary sample)

This example has been tested so far with Ganymede M5 and M6.

Enablement Plug-ins In CVS


First, we will need to download the Oda Ecore enablement plug-ins from CVS.
File -> Import -> Projects from CVS
The Host is dev.eclipse.org
The Repository path is /cvsroot/datatools
Unless you are a committer, the User is anonymous.
Checkout from CVS at dev.eclipse.org

Browse to org.eclipse.datatools.incubator/plugins, select
org.eclipse.datatools.enablement.oda.ecore
org.eclipse.datatools.enablement.oda.ecore.ui
and check them out to your workspace.
Find the ODA Ecore enablement plug-ins in the datatools incubator.

Model File


You will also need a model file. You can create one yourself using New -> Other -> Example EMF Model Creation Wizards -> EXTLibrary Model or you can use the sample model below, which sets up two libraries with an assortment of books, some of which are in one library or both libraries, and authors, some of whom are also in one or both libraries:

my.extlibrary


<?xml version="1.0" encoding="UTF-8"?>
<xmi:XMI xmi:version="2.0" xmlns:xmi="http://www.omg.org/XMI" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:extlib="http:///org/eclipse/emf/examples/library/extlibrary.ecore/1.0.0">
<extlib:Library address="1000 4th Ave, Seattle, WA 98104" name="Seattle Public Library">
<stock xsi:type="extlib:Book" title="David Copperfield" category="Biography" author="/0/@writers.1"/>
<stock xsi:type="extlib:Book" title="Nicholas Nickleby" category="Biography" author="/0/@writers.1"/>
<stock xsi:type="extlib:Book" title="The Deerslayer" category="Biography" author="/1/@writers.0"/>
<stock xsi:type="extlib:Book" title="The Last of the Mohicans" category="Biography"/>
<writers firstName="James" lastName="Fenimore Cooper"/>
<writers firstName="Charles" lastName="Dickens" books="/0/@stock.1 /1/@stock.3 /0/@stock.0"/>
</extlib:Library>
<extlib:Library address="308 Kirkland Ave, Kirkland, WA 98033" name="Kirkland Public Library">
<stock xsi:type="extlib:Book" title="The Last of the Mohicans" category="Biography" author="/1/@writers.0"/>
<stock xsi:type="extlib:Book" title="The Pioneers"/>
<stock xsi:type="extlib:Book" title="Around The World In 80 Days" category="ScienceFiction" author="/1/@writers.2"/>
<stock xsi:type="extlib:Book" title="The Pickwick Papers" author="/0/@writers.1"/>
<writers firstName="James Fenimore" lastName="Cooper" books="/0/@stock.2 /1/@stock.0"/>
<writers firstName="Charles" lastName="Dickens"/>
<writers address="" firstName="Jules" lastName="Verne" books="/1/@stock.2"/>
</extlib:Library>
</xmi:XMI>



my.extlibrary example file
Feel free to modify the model file with the extlibrary example editor.

Launch Eclipse


There is nothing special to do here. Just open the Run Configurations Dialog, create a new Eclipse Application runtime configuration, if you do not already have one, and hit Run.
An example Eclipse runtime configuration.

BIRT Report


In this new Eclipse runtime, create a new General project. Here we can call it hello.world.oda.ecore. Drop your .extlibrary sample file into the new project. Now create a new Blank BIRT Report and switch to the Reporting perspective. Here we use the Wizard's default name for the report. It should be automatically opened in an editor.
A new BIRT report in your worspace.

Data Source


In the Data Explorer View, specify a new Data Source. From the Wizard, select Ecore ODA Data Source on the first page.
Select a new Ecore Data Source.

On the second page, select the sample .extlibrary file in your workspace and "Ping" it to make sure that it can be loaded.
Select and test the sample file.

Data Set


Again in the Data Explorer View, specify a new Data Set. The Data Source that we just created should be automatically selected on the first page of the Wizard, and the Wizard should know that the Data Set Type is Ecore ODA Data Set.
Select the Ecore Data Source we just created.

On the next two pages, we will choose the Model Object that we are querying from, the columns that we are selecting to use for the query result, and we will fill in the OCL Condition that will restrict the query results.
A very simple query would be to find the names of all writers in all libraries. For this, we will
select Writer -> name,
from the invariant Writer,
where self.oclIsKindOf(Writer)

Add the OCL Conditional Query and select an Invariant.
If you do not select an invariant from the combo, then all EAttributes and EReferences in the Model will be available for selection. Try it out!

Select the Columns for the Report.
The EAttributes and EReferences displayed are based on the invariant selection on the previous Wizard page. Here, a Writer is also an Addressable Person, so the EStructuralFeatures for those model elements are also available.


After we are finished with the Wizard, we can Edit the Data Set properties, preview the results of the query, and modify our query conditional, selected columns and invariant.
Edit the Invariant and Query condition.
Edit the Invariant and the conditional query.

Edit the Columns for reporting.
Edit the columns that will appear in the report.

Preview the Query Results.
Preview the query results. You can switch among the pages, so preview different conditional queries, different invariants and different column selections if you feel adventurous!

Run a Report


Now that we have a Data Set, we can drag it into our report to add all the column data (in this case, there is just one column name). From the Preview subtab, we can then preview the report and see our query results!
Drag the Data Set into the report to set up the result set table.

Backport


A backport of these plug-ins for Eclipse 3.2, JDK 1.4 and EMF 2.2 is also available, but future support is not guaranteed. A description of these plug-ins and a comparison between the latest version and the backport is available here.

Part Two


Continue to part 2 of this guide for more advanced features ->