Mikio Braun has written a good summary on calling Java code from JRuby. A lot of this material is covered on the JRuby Wiki, but Mikio adds some much needed exposition. Thanks Mikio!
I have recently just finished up a port of the Soar kernel from C/C++ to Java. The existing implementation is about 40,000 lines of C and C++ code accumulated over more than 15 years of development, mostly by grad students at the University of Michigan. For such a long span of time, that’s not really that much code, but unlike a lot of “modern” object-oriented systems, every line does something important. There’s very little getter/setter boilerplate.
I won’t get into why I wanted to port it to Java here. That’s another story. Instead focus on the software process.
From the start, I had some basic principles to follow. First, this was to be a port, not a reimplementation from scratch. Although there is a manual, wiki, and forthcoming book on the Soar architecture, there is nothing that I would call a specification for the language or run-time. That is to say, as is so often the case, the code is the spec. And there’s enough code of a sufficiently intricate nature that there’s minimal hope of generating a spec for Soar in any reasonable amount of time. It’s intractable. Besides, I wanted to use jsoar in the near future and with two children under two, I’m not spending my spare time writing a spec.
Second, because there is already a community of researchers working on the kernel, I wanted the port to be as lossless as possible. If the entire structure of the kernel changes out from under them, the chances of adoption are low.
Third, I wanted to actually test the Soar kernel. Historically, testing on the kernel has been minimal aside from manually running a few test cases to make sure nothing crashes. Since no one wants to write unit tests for a big legacy system, I might as well write some while I’m porting.
Finally, I wanted to be fairly conservative with refactoring during the port. In taking a bottom up approach to the port, I never knew when a refactoring choice would come back to haunt me. Furthermore, one argument for Java is that it’s easy (or easier) to refactor, so I might as well refactor at the end when I have a full view of the system. I’ll post more on how this has turned out later.
So, from these principles, I started out from Rivendell for Mordor. The upshot of the first tenet is kind of the funniest. My approach to the port came down to the following procedure:
That last step was a doozy. The first few days were essentially building up data structures in Java and required the most actual though. The Soar kernel makes heavy use of the old tagged union pattern. This generally maps pretty nicely to a type hierarchy with polymorphism, but there were a few stumbling blocks… In particular, there are a few Soar data structures that are “transmogrified” at run-time, i.e. their type is changed. Nice. In these cases, I settled for an “expanded union” where all of the unused data fields were null. This is the closest I could get in Java without some major refactoring of the code… and since I was taking a mostly bottom up approach to the port, I was never sure when a refactoring decision would bite me at some later point.
Here’s an example of such a beast. You can see my assertions desperately trying to ensure that the “union” was indeed behaving like a union.
The rete algorithm implementation in Soar makes heavy use of tables of function pointers. Since Java lacks function pointers, I took the fairly tedious route of defining an interface and implementing it once for each function pointer. Basically, I ended up with a bunch of inner classes, one for each function pointer. This worked fine.
The interesting part came when the port was finished and I started performance testing. It turns out that method calls from a nested class to a containing class are actually pretty slow when called in an inner loop due to an additional level of method calls generated by the compiler. So, in the end, for many function pointer tables, I ended up reverting to simple switch statements which gave me something like a 20% speedup on some tests.
Enumerations are one area where I really did some refactoring. I kept the names the same, but I almost always converted enum or #define constant lists to Java enumerations. The ordinal() method provides access to the original integer value, if needed, but I found that with EnumSet and EnumMap, this was rarely necessary. The improved typesafety and overall debuggability didn’t hurt either.
Another obvious area of difficulty is what to do with macros, especially “clever” macros. For example, here’s the insert_at_head_of_dll() macro from the C Soar kernel:
/* This macro cannot be easily converted to an inline function.
Some additional changes are required.
*/
#define insert_at_head_of_dll(header,item,next_field_name,prev_field_name) { \
((item)->next_field_name) = (header) ; \
((item)->prev_field_name) = NIL ; \
if (header) ((header)->prev_field_name) = (item) ; \
(header) = (item) ; }
That’s fun, isn’t it? I kept the comment (ca. 2003) for extra effect. This is a “generic” procedure for inserting an item at the head of a linked list. You’ve got the list header, the item and then two special parameters. What do they do? They name the next and previous fields in the item structure used for the linked list. Why not fix the names so you can just define a C++ template? Or pass in the address of the next and previous links? There are probably a few reasons. One would be performance. When this code was written (early 90s) they were squeezing every bit of performance they could out of the code. More interesting though is why the names aren’t fixed. That’s easily answered with a look at the working memory element (WME) structure from the kernel:
typedef struct wme_struct {
/* WARNING: The next three fields (id,attr,value) MUST be consecutive--
the rete code relies on this! */
Symbol *id;
Symbol *attr;
Symbol *value;
Bool acceptable;
unsigned long timetag;
unsigned long reference_count;
struct wme_struct *rete_next, *rete_prev; /* used for dll of wmes in rete */
struct right_mem_struct *right_mems; /* used for dll of rm's it's in */
struct token_struct *tokens; /* dll of tokens in rete */
struct wme_struct *next, *prev; /* (see above) */
struct preference_struct *preference; /* pref. supporting it, or NIL */
struct output_link_struct *output_link; /* for top-state output commands */
tc_number grounds_tc; /* for chunker use only */
tc_number potentials_tc, locals_tc;
struct preference_struct *chunker_bt_pref;
/* REW: begin 09.15.96 */
struct gds_struct *gds;
struct wme_struct *gds_next, *gds_prev; /* used for dll of wmes in gds */
/* REW: end 09.15.96 */
} wme;
Just this one datastructure is potentially part of 1, 2, 3 linked lists (see the X_next and X_prev fields?) and holds the head for 1, 2, 3, 4 linked lists. So, how can this be improved? If I can’t improve it in C, I doubt I can implement it in Java. Well, the next and previous pointers can at least be pushed down into a structure:
template <typename T> struct list_member
{
T next;
T prev;
};
which will allow us to do something like this:
typedef struct wme_struct {
// ... snip ...
list_member<struct wme_struct*> rete_next_prev; /* used for dll of wmes in rete */
struct right_mem_struct *right_mems; /* used for dll of rm's it's in */
struct token_struct *tokens; /* dll of tokens in rete */
list_member<struct wme_struct> next_prev; /* (see above) */
// ... snip ...
struct wme_struct *gds_next, *gds_prev; /* used for dll of wmes in gds */
} wme;
Now we have actual object we can work with and write a single insert_at_head_of_dll() function, not macro. And it will be typesafe… but, we’re porting to Java here, and my number one goal is to port this thing, and my number two goal is to avoid manually expanding that linked list management code over and over again in Java.
My solution is encapsulated in two generic classes, ListHead and AsListItem. The former represents the head of a list, the latter an entry in the linked list equivalent to list_member<T> above. AsListItem came about when I was starting to play around with Ruby and it’s approach to mixin classes (like “acts_as_taggable”). It seemed clever at the time, but now it just seems stupid.
Anyway, these classes allowed objects to be a part of multiple lists at a time while eliminating the need for duplicate code, but there was one more issue…
As it turns out, the objects that use these classes the most also happen to be the most frequently created, short-lived objects in Soar, in particular rete WMEs and tokens. ListHead and AsListMember object were being created like crazy, reducing performance. So over the course of a few days, I slowly reverted the most performance-critical lists to raw linked list manipulation code, just duplicating the list maintenance. D’oh. It improved performance by around 40% though, so I can’t complain too much.
This seems like enough for now. In a later installment, I’ll talk about testing, getting Java to run as fast as C, and why refactoring the Soar kernel still seems hard even after its been moved to Java.
Here are some random links about porting C/C++ to Java:
One aspect of the jsoar implementation that I wasn’t sure about in the beginning was the management of symbols. In the Soar kernel, a symbol represents an id, attribute or value in a working memory element. They boil down to either identifiers, or wrappers around atomic data types like string, double, or int. The kernel caches symbols so that they can be compared quickly using pointer identity rather than the usual equals() and hashCode() approach. These comparisons are the “inner loop” of the rete algorithm. The cache also helps with memory consumption where it’s not uncommon for a symbol, like input-link to appear in many rules.
In the C implementation of the Soar kernel, symbols are tediously reference counted. When the reference count goes to zero, the symbol is no longer in use and can be removed from the cache. In jsoar, I obviously didn’t want to do reference counting. We’re trying to make things easier here. But, if the symbols are cached, they’ll always be referenced and thus, never removed from the cache and garbage collected.
Before I go further, the symbol cache is basically a map from atomic value (like a string) to symbol, something like Map<String, StringSymbol> strings .
So, I started hunting around and quickly discovered Java’s support for weak references (I cheated a bit because I already knew they existed, just hadn’t used them before). A weak reference is a reference that does not stop the garbage collector from reclaiming an object. Nice. Even better, Java includes WeakHashMap which sounds kind of like what I want, i.e. a map that will remove entries when a value is garbage collected. Unfortunately, WeakHashMap puts a weak reference on keys rather than values which is the opposite of what I want.
Next, I started looking into using a ReferenceQueue to implement what I wanted. This didn’t look that fun, but thankfully I stumbled upon the Google Collections API. It includes a Map implementation for all combinations of key/value reference types. Better yet, it even works. Here’s what one of the map declarations looks like:
private static <K, V> Map<K, V> newReferenceMap()
{
return new ReferenceMap<K, V>(ReferenceType.STRONG, ReferenceType.WEAK);
}
private Map<String, StringSymbolImpl> symConstants = newReferenceMap();
I used a static helper method to make the instantiation a little cleaner since I had to do it once for each type of symbol.
I mentioned that it even works. Here’s my unit test that I used to convince myself:
@Test
public void testGarbageCollectedSymbolsAreRemovedFromCache()
{
for(int i = 0; i < 1000; ++i)
{
assertNotNull(syms.createInteger(i));
assertNotNull(syms.createString(Integer.toString(i)));
}
// Why do I believe this test works? Because it fails if I remove the
// call to the garbage collector here :)
System.gc();
for(int i = 0; i < 1000; ++i)
{
assertNull(syms.findInteger(i));
assertNull(syms.findString(Integer.toString(i)));
}
}
Anyway, that was a bunch of time saved. As a bonus, Google Collections includes a number of other useful functions and classes. All of the stuff you wish was in Java’s Collections class, but isn’t. Especially handy was the composite iterator implementation. You give it a list of iterators and it returns an iterator that will iterate over each in turn. This was great for creating a natural interface for some of Soar’s weirder iterable data structures, like working memory.
In a recent meeting I was asked whether Java’s concurrency support was an advantage for jsoar over the existing C++ implementation. I kind of said yes, but was mostly incoherent because I’m always trying to avoid saying things that aren’t true. This is probably a weakness. Anyway, I wrote the followup email below and I kind of liked it so I figured I’d post it … just for context, “kernel” here refers to the Soar kernel …
Regarding Java concurrency support vs. C/C++… In any discussion like this, you can argue than anything is possible in just about any language which is why I was a little hesitant to make a firm statement. In this case, C++ (or at least its runtime libraries) provide the same basic concurrency primitives as Java, i.e. locks, condition variables, etc. However, Java has two advantages here. First is cross-platform support. The Java concurrency and memory model are specifications that are implemented the same on every platform. So
while it’s possible to write a wrapper library that puts a common interface around say pthreads and the Win32 threading APIs, guaranteeing consistent semantics across both is notoriously difficult (e.g. http://www.cs.wustl.edu/~schmidt/win32-cv-1.html).
Boost and other libraries will cover many things, but you’re still left having to include the boost library and hoping that it plays nicely with whatever threading model any other library your using decides to use.
Furthermore, on top of the basic synchronization primitives, Java provides a really nice library of higher-level concurrency tools (http://java.sun.com/j2se/1.5.0/docs/api/java/util/concurrent/package-summary.html) like concurrent collections, thread-safe queues, thread pools, etc. All of these can be implemented with pthreads, but it’s nice to have a standard set of tools that are used more or less uniformly throughout the community. The situation is similar to the mid-90s C++ where everybody and their grandma had their own implementation of a string class because a standard hadn’t yet been established.
More generally, since I’ve been thinking about this quite a bit lately for some reason, the advantages of Java over C/C++ boil down to the following:
The more I’ve thought about this, the cute stuff like scripting language support, running in Java application servers, and even concurrency falls away. They’re all nice, but also possible with the Soar’s SML Java (or C#, Python, etc) bindings (maybe with some tweaking). So you’re left with the fact that development and testing on the kernel itself (and surrounding modules) is where Java really wins out. If you want to do research on the kernel itself, it helps to not spend half of your time waiting for builds to finish, hunting through headers, or creating cross-platform wrappers for basic services.
Also, this isn’t really about Java. If jsoar was a completely personal project for me (i.e. I didn’t work at SoarTech), I’d probably try it in C#, which seems to be both mainstream (as opposed to other advanced
languages like F#, Scala, etc) and ahead of Java in cool language features. It’s more about productivity in C++ versus almost any other language out there.
c++, concurrency, java, soar
Once again, I stumble onto some feature of the Java platform that I had no idea existed. Today, while researching various ways to store version and build information in jar files, I found this article on Java Product Versioning.
The main idea is that there are now interfaces for accessing special tags in your manifest file. Obviously, the ability to read manifests has been around for a while, but all of the methods I’ve seen were a little hacky. They all involved figuring out the path to your jar, often by parsing the class path and then extracting the manifest from it. This is necessary because, depending on class path order, just asking for ‘/manifest.mf’ with the resource interfaces won’t necessarily get you your manifest.
This article describes the Package class which knows which manifests go with which classes. It also provides methods for accessing the following manifest properties:
Specification-Title: “Java Utility Classes”
Specification-Version: “1.2”
Specification-Vendor: “Sun Microsystems Inc.”
Package-Title: “java.util”
Package-Version: “build57”
Package-Vendor: “Sun Microsystems. Inc.”
etc…
Clearly, this has been around for a while. Why does it always take so long for me to find out about these things? Is this not as useful as it seems?
I recently started experimenting with the BIRT reporting engine for Java. It seems pretty powerful, well-designed, and has a nice report design tool implemented in Eclipse. Since the project I’m working on doesn’t have a database, I decided to use BIRT’s scripting data sources. These allow you to create a (hopefully) small JavaScript glue layer between the reporting engine and your plain old Java objects. The purpose of this post is to cover some of the gotchas I’ve encountered so far.
The basic idea is that you implement a few JavaScript callback methods that feed row-like back to the reporting engine. BIRT uses Mozilla’s Rhino JavaScript engine. Since the typical use case for BIRT is a database backend, the documentation for the scripting interface seems harder to come by. The FAQ helped, but didn’t answer all of my questions.
First, all of the examples retrieve their “model” from a static factory method called from JavaScript. This isn’t that realistic. How do I pass my model in to the JavaScript? Or at least a parameter like a filename? I think part of the reason all the examples take this approach is so that it’s possible to run the report at design time with the preview window. I did some digging and eventually found the right calls:
MyModel model = ...;
IRunAndRenderTask task = engine.createRunAndRenderTask(design);
Map parameters = new HashMap();
parameters.put("model", model);
task.setParameterValues(parameters);
Cool. Now my model’s being passed to the engine. But wait. How does BIRT find my classes? I know it’s built on top of Eclipse which means the classpath is not as simple as you’d like. In some examples I found, you have to manually copy your compiled class files to a directory in one of the BIRT plugins. Uggh. This is a pain, but acceptable for deployment. But during development? I might as well go back to C++ if I want to waste that much time.
Some more searching dug up this FAQ question. It lists too yucky solutions and then has a tacked on snippet of code that looks promising.
config = new EngineConfig(); HashMap hm = config.getAppContext(); hm.put(EngineConstants.APPCONTEXT_CLASSLOADER_KEY,MyClass.class.getClassLoader()); config.setAppContext(hm);
However, I guess I think this is for the version of BIRT I’m not using because it doesn’t work. Some more digging and I come up with this:
IRunAndRenderTask task = engine.createRunAndRenderTask(design);
HashMap contextMap = new HashMap();
contextMap.put(EngineConstants.APPCONTEXT_CLASSLOADER_KEY,
MyModel.class.getClassLoader());
task.setAppContext(contextMap);
I guess the app context stuff moved from the task to the engine at some point. Anyway, now we can finally try it out. I set up my open callback in Java and… wait, how do I actually get to my model in the JavaScript code? This wasn’t too tricky to figure out. The parameters passed to the engine above are passed to the JavaScript code in a global (?) parameter aptly named params:
model = params["model"];
Nice. Now I write some more code to call some methods on the model and run it and… NullPointerException. This is where I was stuck for a little while. I thought that I had screwed up the class loader stuff or something so I fiddled with that stuff for a while. Eventually, when I was about to give up, I stumbled upon this bug report which, although it doesn’t mention a NullPointerException, does mention a “display name” which I had noticed references to while poking around in the debugger after my crash.
The trick is that the params variable in JavaScript doesn’t hold just my model, but an extra wrapper object with a display name and value is stuck in there. I revise my code to look like this:
model = params["model"].value
and voila, I run it again and my report is generated as expected.
Hope this is helpful to someone else out there.
One aspect of implementing a text editor in Eclipse that I’ve found to be tricky is the reconciler. In this post, I’ll detail some of the lessons I’ve learned. I’m assuming you’ve gotten as far as creating a basic editor. The reconciler is a background process in your editor responsible for updating your model when the user takes a break from typing. The kinds of things it should update are:
Some editor programmers don’t seem to know that the reconciler even exists. They usually take one of two approaches: update the entire model on every keystroke or update the model only when the user saves. Neither of these is very satisfying, especially for users familiar with editing Java in Eclipse. The former approach leads to poor performance on large files. The latter requires the user to save constantly to find out whether errors exist or get an up to date outline.
So, how does the reconciler work? The reconciler runs as a background thread in Eclipse. It sets a timer which will trigger a reconcile whenever it expires. Each time the user types a keystroke, the timer is reset. In this way, the user can type a great deal of text without being interrupted by the reconciling process. Once the user pauses, as all humans must, the reconciler’s timer expires and the model is updated.
Creating a Reconciler
Eclipse uses the strategy pattern to separate the timer/keystroke logic from the details of updating your model. The MonoReconciler is the simplest implementation of the timer/keystroke logic. It is configured with an instance of IReconcilingStrategy which is responsible for updating your model, i.e. you implement this interface.
The basic procedure for setting up your reconciler and reconciling strategy are:
That’s it. Now when your editor is created, your reconciler will be initialized and the reconcile() method will be called whenever the user modifies the document. I usually store a reference to the editor itself in the strategy object.
The Reconciler Runs in Its Own Thread!
It’s important to always remember that the reconciler runs in its own thread, as with most stuff in Eclipse. It’s safe to access the document, but there are few other things you need to keep in mind:
If your model is simple enough, one simple solution to this problem is to have the reconciler construct an entirely new model each time it runs and then pass it on to the editor with Display.asyncExec(). This way there are no shared objects between the threads and thus, no syncrhonization problems.
What if the user doesn’t start typing right away?
After you’ve implemented your reconciler, everything will seem great. Great until you (or a user) decides to just view a file without editing it. They’ll find that their outline view is not updated. Same with folding ranges, etc. The problem is that your reconciling strategy is not run until the document is actually modified. Go figure. If only there was a way to tell the reconciler, “Hey, how about an initial reconcile pass on the document right when it’s opened?”.
Fortunately, a friendly Eclipse programmer also thought of this question. Rather than implementing IReconcilingStrategy, try IReconcilingStrategyExtension. This adds an initialReconcile() method where you can do an … well, you get the idea.
What about the incremental reconciler?
If you poke around in the reconciler interfaces a bit you’ll notice there are actually two modes of operation. The non-incremental mode simply tells you that the document has been modified with little additional information. The incremental mode tells you about what’s changed in the document each time that reconcile() is called. It tells you when text has been added or removed and from where in the document. That sounds pretty useful!
On my last Eclipse editor project, I wanted to take advantage of this. If I knew which part of the document has changed, I could just reparse that section and update the affected model elements. I actually foolishly went through all the trouble of implementing this logic and then gave it a try. Things did not work as I expected. There is a fatal flaw in the incremental mode: By the time the reconciler is called, the document may have been modified further so all the modification information is provides is basically useless!
I believe this is caused by two factors. First, because it is multi-threaded, it’s hard to lock the document and still maintain the “update in the background” semantics of the reconciler. Second, the incremental reconcile() method only provides information about a single modification, i.e. an insert or delete in the document. So if the user does the classic “insert character + down arrow” editing technique to say comment out a bunch of lines, the reconciler will get called for each individual change, but the document will already contain all the modifications when the first reconcile call is made. D’oh.
When I realized it works like this, I did a bunch of searches on Eclipse newsgroups, google code, etc. I came to the conclusion that either no one has ever actually used the incremental reconciler, or they have and then silently slunk back to the non-incremental version when the found this fatal flaw.
If I’m wrong about this, I’d love to hear why!