Archive

Archive for the ‘software engineering’ Category

Java Concurrency Pitfalls (in Scala) Answers

May 10th, 2011 3 comments

Recently, Cay Horstmann posted a dozen Java concurrency pitfalls ported to Scala for extra pitfalliness. I had fun figuring them out. Here’s what I came up with.

I won’t copy all the code here, just provide my answers.

  1. The var stop isn’t synchronized in any way (synchronized, AtomicBoolean, etc) so there’s a chance that when it’s set to false, the change won’t be seen in the thread.
  2. Here, stop is an AtomicBoolean, fixing the issue in problem #1. That’s good. However, if doSomething() throws an exception done.put("DONE") will never execute and done.take() will wait forever.
  3. Here, Thread.run() is called rather than Thread.start(). The so-called “BackgroundTask” will actually run in the “foreground”
  4. ConcurrentHashMap.keySet().toArray will give a “weakly consistent” snapshot of the keyset at the time of the call. By the time it returns, the keys in the map may have changed completely.
  5. Oops. A string literal is used for the lock meaning that all instances of Stack will most likely share the same lock.
  6. Oops. A new “lock” is created every time push() is called, which is just as good as no lock.
  7. Here values is mercifully synchronized, but the var size isn’t. That is, if size is used in any other methods it may not be synchronized correctly.
  8. A do/while is used for the condition variable rather than just while. If cond is in a signaled state initially, the condition that size is zero may not be checked.
  9. If out.close() throws an exception, the myLock.unlock() will not be executed.
  10. Here, a string is being added to a blocking queue within a UI event handler. If the queue is full, queue.put() will block causing the UI to become unresponsive.
  11. I’m not totally sure with this one. I can think of a few things that could go wrong. First, if a listener is added or removed while fireListeners() is executing, you could get a ConcurrentModificationException. I think so anyway. I wasn’t able to find any indication of how ArrayBuffer iteration handles this. Second, since the listeners are notified with the lock held, you’ll almost certainly get a deadlock eventually, usually a lock inversion with some other thread that’s calling SwingUtilities.invokeAndWait().
  12. Ridiculously, SimpleDateFormat is NOT THREADSAFE! So using the same formatter from multiple threads is a recipe for sadness.

I wonder what I missed.

Cheers!

Say Something Nice About Every Language You’ve Used

December 8th, 2010 50 comments

In Michael Easter’s recent post, I was struck by his comment that Guy Steele like all languages. Seems like a pretty chill way to live a programming career. So I wondered, do I like all languages? Can I say something nice about every language I’ve used? As the saying goes, “If you can’t say something nice, don’t say nothin’ at all.”

Let me give it a try in rough chronological order of the first time I used each language in anger:

  • Pascal – Ouch. My memory is so fuzzy I can’t even think of something bad to say about it. So we’ll count “no comment” as nice and move along …
  • C++ – Another toughy, but this time because my memory is so sharp. Hmmm. Uh. C++ has a really nice personality. Next.
  • Matlab – Pretty cool array slicing notation. I don’t know if Python stole this from Matlab, but when I first learned Python I was like “Hey, this is Matlab!”
  • Common Lisp – Generic functions and multiple dispatch are cool.
  • Visual Basic 6 – Seemless integration with COM and built-in support for the observer pattern.
  • C – As Linus has pointed out, you need almost no context to understand a random chunk of C code. It is what it is and nothing more.
  • Java – It’s simple enough that really powerful, reliable tools can be built for it. If you change the signature of a method in Eclipse, you can feel confident that it actually worked. (unless you’re doing reflection…)
  • Tcl – The entire language is expressed in 11 simple rules and it’s homoiconic. Once you accept that everything is a string, you’ll enter a zen-like trance and every atom of your being will vibrate in harmony with Tcl’s interpreter. Or something. Finally, whenever you write a quick test script, you get to name it “test.tcl”
  • Python – Python taught me about list comprehensions and bound methods. It’s stupid, but I also always liked that you could multiply a string by a number to repeat it.
  • Soar – Fast, rete-based pattern matching is cool. Everything that’s really easy in a procedural language is hard in Soar, but some things that are hard are easy.
  • JavaScript – Taught me that objects are overrated and started my reptilian, OO brain down a brighter path.
  • Ruby – I think blocks are a neat bit of syntactic sugar. I like that everything, including nil, is an object.
  • Scala – Introduced me to implicit typing and opened my eyes to how much I actually have to type when I’m coding Java.
  • Clojure – It’s fun, has a nice cross-platform VM, persistent data structures, a good concurrency story, and is apparently saving Lisp from itself.

Wow, I feel really great now.

Note that every one of these could have easily be extended with “even though”, “except for when” or “but sometimes”, but I resisted the urge, mostly.

Can you think of something nice to say?

Programming Etudes

December 6th, 2010 3 comments

Can you implement a stack off the top of your head? How about a simple hash table? A recursive descent parser? Can you do it without thinking about it?

These are a few programming “etudes“. Musicians have a tradition of etudes designed to teach fundamental lessons about playing their instrument. They practice them (usually as children) until they can play them perfectly from memory. Just like with the programming examples above, a musician doesn’t play these etudes in “the real world”. They’re technical exercises so that when they get on stage they can make an artistic statement rather than worrying about fingerings.

A pianist practicing an etude may focus on alternate fingerings, dynamics, tempo. What are equivalent variations you could try while doing a matrix multiplication “etude”? Elegance? Performance? Generality? Obfuscation?

Build your own set of programming etudes. Practice them. They’ll make you a better programmer. Now repeat in another language.

Can you minimize key strokes in your editor? Try it in a different editor?

Can you design a series of etudes that build on each other? Maybe it’s like programming a fugue? Linked-lists + a hash function becomes a hash table. What’s next?

Can you think of etudes in your favorite framework? The “fifteen minute blog” is one. See, it doesn’t have to be all about data structures and algorithms and clever interview questions. It’s about getting the tools of your trade under your skin.

What else?

Now go read Dave Thomas’ CodeKata.

Practice, practice, practice!!

Buffalo buffalo buffalo buffalo …

January 16th, 2009 No comments

Today I had a programming experience akin to the grammatically correct sentence “Buffalo buffalo Buffalo buffalo buffalo buffalo Buffalo buffalo.”

I’m working on a DSL that has values, which probably should have been called elements instead. I say this because I had to add a value keyword to the language which, of course, entailed a class named ValueValue. See where this is going? I knew things had gotten out of hand when I wrote this line of code:

    ValueValue valueValue = (ValueValue) value;

Yipes. Maybe this is why some think naming constructs is the hardest thing about programming.

Porting Soar to Java or: How I Learned to Stop Worrying and Love Spaghetti (Part 2)

December 26th, 2008 No comments

In the previous installment of this series, I wrote about some of the challenges of the initial port of the Soar cognitive architecture from C/C++ to Java. As I noted then, the approach I chose was bottom-up with minimal refactoring. With a couple months of work, I converted about 40k lines of C++ code to about 40k lines of Java code.

Actually, the overhead of stronger typing, lack of macros and unions made the Java implementation generally a bit larger in terms of lines of code. I think the ability to reliably browse the code in Eclipse more than made up for the bloat.

Moving Spaghetti Around The Plate

The original Soar code base is an amalgam of different programming styles reflective of its history as a university research system. There are hints of object orientation as well as functional aspects (it was originally implemented in Lisp, of course), but for the most part it’s good old procedural code. Open data structures with various free functions performing operations on them. The code base itself is broken up into compilation units along mostly functional lines. There’s decide.cpp, which deals mostly with the decision process: substates, impasses, the goal dependency set, etc. There’s symtab.cpp which deals for the most part with allocating and wrangling Soar symbol structures. And on and on…

Of course, you need an object to kind of tie all these pieces together. In the case of Soar, there is the agent struct, aka One Struct To Rule Them All. The agent struct lives in agent.h of all places and is 639 lines of deliciously public members. Here’s a taste:

typedef struct agent_struct {
  /* After v8.6.1, all conditional compilations were removed
   * from struct definitions, including the agent struct below
   */

  /* ----------------------- Rete stuff -------------------------- */
  /*
   * These are used for statistics in rete.cpp.  They were originally
   * global variables, but in the deglobalization effort, they were moved
   * to the (this) agent structure.
   */
  unsigned long actual[256], if_no_merging[256], if_no_sharing[256];

  unsigned long current_retesave_amindex;
  unsigned long reteload_num_ams;
  alpha_mem **reteload_am_table;

  // ... #### 615 lines omitted for sake of brevity #### ...
  // JRV: Added to support XML management inside Soar
  // These handles should not be used directly, see xml.h
  xml_handle xml_destination;		// The current destination for all XML generation, essentially either == to xml_trace or xml_commands
  xml_handle xml_trace;				// During a run, xml_destination will be set to this pointer.
  xml_handle xml_commands;			// During commands, xml_destination will be set to this pointer.

} agent;
/*************** end of agent struct *****/

It’s a beast and it’s passed to just about every function in the system just in case that function may need access to just about anything.

In the interests of sanity, I took a fairly naive approach to the port. For each compilation unit (cpp file) I:

  • Created a Java class
  • Created a Java method for each function in the cpp file
  • Created Java member variables for each member of the old agent structure that seemed to be accessed more or less exclusively by that module

This approach gave me the warm and fuzzy feeling that I was breaking up that awful agent struct and make the system more modular. All my dreams of refactoring the spaghetti of the Soar kernel into a highly modular, easily extended and tested system were coming true…

Ok, maybe not. As I mentioned above, the kernel was only broken up across cpp files along functional lines. This meant that any member variable that I chose to move from the agent structure to the Java class corresponding to the cpp file still had to be public because it was likely that several other modules accessed it however they wanted.

I had taken a 10 Lbs wad of spaghetti and delicately teased it into 10 or so 1 Lbs wads. Each of these spaghetti-lets still maintained an array of strands connecting it to most of its siblings. I think a diagram is in order.

Here’s what I started with, 10 Lbs of spaghetti:

10 Lbs of Spaghetti

10 Lbs of Spaghetti

And here’s what I ended with, 10 little 1 Lbs spaghetti monster babies:

1 Lbs Spaghetti Babies, 10 of them

1 Lbs Spaghetti Babies, 10 of them

See what I mean? I’m really no closer to object orientation, encapsulation or anything. And, of course, the punchline is that I need a top-level object to stitch all these babies together. Can you guess what it’s called?

So, I have an Agent class. It contains a bunch of “module” objects which are all intertwined with each other and have to be public so that everyone can get at each other’s parts.  I’m pretty sure there’s a code smell here, but I can’t quite put my finger on it…

I have actually have two goals here. First, I want to build a public interface for jsoar that is clean and clear and suitable for integrating intelligent Soar agents into cool systems. Second, I want an agent that’s nicely modularized and encapsulated so that the rete can be used (and tested!) on its own, etc. Of course, I don’t want to over encapsulate either. Soar is first and foremost a research system which, in my opinion, means that encapsulation can often get in the way of getting things done.

For the first goal, a clean interface, I want the Agent class to be straightforward without a bunch of yucky public members or just as yucky public accessors.  I also want an interface that will allow me to refactor all these modules slowly over time without impacting external clients. Here I’ll describe my current approach to solving these two problems.

Using the Adapter Pattern to Hide Your Spaghetti

First, how to I give access to private members without cluttering up the interface with a bunch of getters?  For this problem, I chose to use the adapter pattern used liberally by the Eclipse framework. The basic idea is an interface like this:

public interface Adaptable
{
    Object getAdapter(Class<?> klass);
}

The getAdapter method takes a class as an argument and returns an instance of that class. Basically, you’re asking the adaptable object to turn itself into something else for you. In the case of the jsoar Agent, this is a great way to give access to internal modules without cluttering up the API. When one module needs access to another internal module, it can just ask for it by class name:

Decider decider = (Decider) agent.getAdapter(Decider.class);

Here Decider is an internal class. If you happen to know the password (Decider.class) you can get access to it. If you’re just a casual client building another demonstration of Missionaries and Cannibals, you’ll never be tempted by that public getDecider() method, because it’s not there. Yay!  This could also be implemented with a map and string keys, but I kind of like the adapter approach for its simplicity and type safety.

I realize I could also introduce an Agent interface where the private implementation has all the accessors and public members you could want. I will probably add such an interface as well, but I still like the approach of accessing this stuff only through the adapter. If also clearly illuminates the numerous dependencies between the internal modules in a way that I think getters would hide. It’s psychological :)

Hey, I was Eating That! Twiddling Your Secret Spaghetti

Now, there are a lot of places where an external client would like to twiddle the private parts of various internal modules. For example, to change the “wait on state-no-change” setting, client code really needs to be able to access Decider.waitsnc, which is a boolean member variable. Well, it seems like I just cut off that route in the previous section. Besides, I’m not really married to this whole Decider class thing anyway. It’s a monster and should probably be broken up into several smaller objects.  I could just add a getter/setter pair to the top-level Agent class.  There are dozens of these parameters though and I don’t want them cluttering up the interface.

My solution to this is a simple multi-layer property system. It provides type-safety as well as a affordances for high-performance parameters that are accessed frequently in inner loops. First we start off with a generic class that describes a single parameter/property, a PropertyKey. It’s basically like this:

class PropertyKey<T>
{
    public String getName();

    public T getDefaultValue();

    // ... etc ...
}

A PropertyKey is an immutable object. Instances are built with a convenient builder interface. They are meant to be instantiated as constants, i.e. static and final. A PropertyKey acts as a key into a map of property values managed by, of all things, a PropertyManager:

class PropertyManager
{
    public <T> T get(PropertyKey<T> key);
    public <T> T set(PropertyKey<T> key, T value);

    // ... etc ...
}

As you can see, this is all nice and typesafe. Now, what if we have a property that’s a flag, like “learning enabled” that’s checked frequently by internal code. In this case, for performance, we don’t want that inner loop constantly doing a map lookup, not to mention boxing and unboxing of the value. Enter the third interface, PropertyProvider:

public interface PropertyProvider<T>
{
    T get();
    T set(T value);
}

A property provider holds the actual value of the property rather than holding it directly in the property manager. Thus, in the Chunker module, our learning flag can be managed with a simple inner class:

public class Chunker
{
    // ...
    private boolean learningEnabled;
    private PropertyProvider<Boolean> learningEnabledProvider = new PropertyProvider<Boolean>() {
        public Boolean get() { return learningEnabled; }
        public void set(Boolean value)
        {
            learningEnabled = value;
        }
    };

Now, high-frequency code can access the learningEnabled member directly (through the getAdapter() back door), while low-frequency client code can access it through the PropertyManager interface. As a bonus, the property provider can do additional bounds checking on parameters and other fancy stuff. Best of all, our Agent interface isn’t faced with an ever growing set of arbitrary accessors. New properties can be added as needed without affecting other code. In fact, they can be added at run-time, if that’s ever necessary.

Oh, there’s more

So. Now I’m at a point where I have a pretty clean public interface for building jsoar-based systems. Beneath this clean API lurks a bunch of baby spaghetti monsters just dying to be refactored. I haven’t quite firgured that part out yet and so, I’ll have to leave that story for another day.

Categories: java, soar, software engineering Tags: , ,

My First Open Source Release

December 12th, 2008 No comments

This week, I released the first version of jsoar, my Java implementation of the Soar kernel.  Obviously, the Soar community is quite small, so the release is fairly low-key and low-stress.  Still, it’s the first time I’ve really done a release of an open source project of my own.  For promotion, I sent out an announcement to the mail Soar mailing list.  I also gave a brief introduction and demonstration during lunch at my job, a Soar shop.  Overall, I think it was well received. Everyone seemed engaged and maybe even excited to give it a try.  I even got an unexpected, but very nice, pat on the back.

Probably the most interesting thing to come out of the release though was my choice of version number.  This may have been foolish, but I released jsoar as version 0.0.1.  One of my problems is a fear of overstating or exaggerating something, so I think my reasoning for this decision has something to do with managing expectations.  I don’t want someone to download it and be disappointed because the version number made it seem like more than it was.

That said, I was immediately chastised by some colleagues for choosing such a low version number. In their opinion, 0.0.1 says “I’ve barely finished writing the first module and you’re lucky if the code even compiles”.  I guess they have a point. Now that I think about it, I would think the same thing if I came across an open source project with a single 0.0.1 release.  jsoar is actually fully functional and ready to be used in real Soar projects, at least projects tolerant of a little risk.  Because it’s a direct port, a lot of the code ain’t pretty, but by the same token, it benefits from 20 odd years of debugging and optimization.

As Steve Yegge has pointed out, marketing is actually a pretty important skill for developers. So, I’m learning that lesson again.  Maybe in a couple weeks I’ll put out a new version and call it Soar 10.0, or jsoar 2009. Ok, maybe not that, but I think 0.6.0 is probably a good compromise. I think that says “this system is functional, but don’t be surprised if I change a bunch of stuff on you before the next release”, which is really what I was going for in the first place.

A brief postscript: My release timing seems fortuitous. The next day, another message was posted to soar-group asking if anyone had successfully compiled Soar in 64-bit mode. Sadly, the answer is no owing to the C implementation’s frequent abuse of pointers and other architecture dependent features. jsoar, of course, has none of those problems and 64-bit support was one of my initial selling points of a Java implementation…

Convenient or Minimal API?

December 4th, 2008 1 comment

There is always a tension in API design between convenience and minimality. I’ve found this especially true when defining interfaces.

What’s Right

As Scott Meyers has written, pretty convincingly I think, it is preferable to keep an interface minimal and then provide a library of non-member helper functions that provide common operations. A classic example of this approach is Java’s Collections class. It provides a bunch of useful methods for working with the collections framework while not bloating up the collections interfaces.

The primary benefit of this approach is improved encapsulation. When you think of encapsulation as minimizing the amount of code affected by a change in the implementation of the class, this makes perfect sense. C++’s std::string (and Java’s for that matter) is the mother of violations of this rule of thumb. It has a ton of methods, many of which can be trivially implemented in terms of other methods. Thus, any change to the internal implementation could require modifications to much more code than necessary. More code changes means greater bug potential.

What’s Feels Good

On the other hand, you want to provide a convenient interface as well. I don’t think it’s unreasonable, especially in the presence of code completion tools, to expect to hit “dot” and get a list of the operations you can perform on that type. That is, without having to know about some other set of utility functions. This is how common functions get reinvented over and over.

It’s interesting that this hang up seems less prominent in the world of dynamic languages. In Ruby, coders have no issues with adding new methods to a class, even at run-time. For statically typed languages, I think that C# might have the right idea with Extension Methods. It’s basically syntactic sugar for static helper methods that makes them look like normal object methods. As usual, Lisp (CLOS, actually) seems to really have it right. ALL methods are “static helpers”, so called generic functions. Note that I realize there’s a major distinction here! Generic functions are polymorphic on the types of their parameters, while a normal static helper is not. But if you tip your head and squint, I think the there’s a resemblance.

Why I Worry

Anyway, I’m working in Java mostly, which has proven to be much less sprightly than C# lately. Way it goes. I have to make this decision. It’s particularly annoying to have to make this decision when the API is a Java interface. In this case, implementers have to implement the convenience function, which means a chance of getting it wrong if the interface is implemented frequently, or at least changing the semantics slightly.

The example that got me thinking of all of this is the InputOutput interface from jsoar. It looks something like this:

public interface InputOutput
{
    // ...

    Wme addInputWme(Identifier id, Symbol attr, Symbol value);
    Wme removeInputWme(Wme wme);
    Wme updateInputWme(Wme wme, Symbol newValue);

    // ...
}

The tricky part is that updateInputWme method. A Soar WME is immutable, i.e. it can’t be changed after it’s been created. Thus, to update the value of WME (say to change the x coordinate of a simulation object), you have to remove the WME and replace it with a new one with the value changed. That’s what updateInputWme does, and thus it’s implemented completely in terms of the public interface:

public Wme updateInputWme(Wme wme, Symbol newValue)
{
    removeInputWme(wme);
    return addInputWme(wme.getId(), wme.getAttribute(), newValue);
}

This is such a basic operation that people expect, I decided not to make it a helper… but I had to think about it for a minute, which is pretty annoying.

When Right Is Wrong

There’s (at least) one case I can think of where you can’t use static helper methods. This is when dealing with concurrency using the private lock idiom. If the helper performs several operations and it would violate the helper’s contract for other code to see the object in the intermediate states created by those operations, the helper must be implemented as a normal method, holding the private lock as necessary.

An example of such a method is ConcurrentHashMap.putIfAbsent() from the Java concurrency library. If it was implemented naively with get() and put(), it’s thread-safety guarantees would be violated.

In cases like this, you have to just suck it up and pile the methods into the interface and worry about Scott Meyers later.

Categories: software engineering Tags:

Beware of Case-Sensitive Environment Variables in ANT

December 2nd, 2008 No comments

Today I was bitten by a kind of annoying feature of ANT. Sadly, a project I’m working relies on a Swig-generated wrapper for a C++ library, in particular the SML client libraries for Soar. So, it’s important to have all the DLLs in the right spot to avoid link exceptions. The usual, and I think most straightforward, solution is to ensure that the DLLs are on the system path. To this end, I can make a simple bat scripts (or shell script) that sets up the environment and then invokes Java.

However, I try to be good and write unit tests for this stuff too which means that the environment has to be set up correctly for JUnit too, even when invoked from ANT. So, in ANT, how do I extend the system path for the JUnit task while not clobbering the path that’s already there? I did a little hunting around and found the nice <env> tag which is documented in the exec task. Lo and behold, the second example is exactly what I want to do. Here is what I did, translated for junit:

<property environment="env"/>
<junit fork="true" ... >
  <env key="PATH" path="${env.PATH}:${basedir}/vendor/soar-8.6.3/bin"/>
</exec>

Pretty straightforward, right. But, of course it didn’t work right away. After a little more hunting, I figure out the problem is with that <property environment … > tag. It turns out there are a few things going on here:

  • On Windows, environment variable names are case insensitive
  • Properties in ANT are case sensitive
  • The case of the PATH environment variable in Windows appears to be totally random

These factors conspired against me. In my case, my path environment variable was spelled “Path” with a capital Pee. Changing the ANT file to use this spelling fixed everything. And yes, this limitation is documented in the documentation for the property task.

The really sad thing is that I got bit by this less than an hour later when I set up the project on Hudson (really cool by the way). In this case, it appears that Hudson (or something else) changes the PATH environment variable to all lower case when invoking ANT. So, now I have a build script that runs great on my machine, but fails on the build machine. I’m sure there’s a better solution, but for expediency, I went with this monstrosity:

<property environment="env"/>
<junit fork="true" ... >
  <env key="PATH" path="${env.path}:${env.Path}:${basedir}/vendor/soar-8.6.3/bin"/>
</exec>

I wonder if this will ever come back to haunt me… Yet another reason for me to eliminate this C++ dependency.

Categories: java, software engineering Tags: , ,

Steve Yegge and (Guitar) Gearheads

November 30th, 2008 No comments

A recent StackOverflow podcast featured Steve Yegge. It’s great stuff. A perfect mix of technical wisdom and insider gossip. In one portion of the discussion, Steve and Joel are discussing script kiddies and Steve starts to make a analogy to young guitarists. Unfortunately, he’s either interrupted or diverted. So, I’m going to try to make his point for him which I’m sure he’ll appreciate.

So, in the guitar world, young players (and many older ones) tend to fixate on gear to the detriment of musical fundamentals.  They always know about the latest pedals, picks, strings, amps, and, of course, guitars. They buy this stuff and fiddle around with it, all the while ignoring the fact that they have terrible technique, terrible ears, or just bad taste.

I know this because not only have I seen it, I’ve done it myself. I spent a lot of time in high school messing with distortion pedals, buying books of tablature, switching picks and strings, and believing that I’d be better if I had a better guitar.  (In guitar circles this is commonly known as Gear Acquisition Syndrome, or GAS). What I really needed was to sit down with a guitar, a metronome, and blank staff paper for transcription. Way it goes. I eventually learned my lesson, but it’s much harder to learn in your twenties than your teens.

The analogy to programming is the tendency of programmers to flit from one bleeding edge technology (c++, java, agile, rails, dependency injection, ajax, …) to the next looking for a silver bullet rather than honing their basic programming skills. I’m all for applying libraries to make life easier, but frequently it just boils down to basic design skills which you can’t get from the getting started page of some new widget.

I do this in my programming life too … maybe that last system turned into spaghetti because I didn’t use JAX-B … or maybe such and such book will suddenly make writing concurrency a snap. It usually doesn’t work out that way. Only when I actually sit down and do a really honest post-mortem, focusing on design, algorithm selection, usability, testing do I actually end up a little further ahead on the next project.

So what’s my current guitar rig? I have a guitar (Gibson ES-137) plugged straight into an amp (Roland Cube 30). No pick and heavy flat-wound strings. That’s been my basic, happy configuration for several years now. No fuss, no muss. The best part is that I now know what a truly terrible guitaris I am … d’oh.

Categories: software engineering Tags:

Porting Soar to Java or: How I Learned to Stop Worrying and Love Spaghetti (Part 1)

November 25th, 2008 No comments

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:

  1. Open a cpp file, say rete.cpp
  2. Gasp at the majesty of a 9000 line cpp file
  3. Create class Rete in Java
  4. One by one, paste functions from C++ into Java, changing pointer arrows to dots, ec, etc

Union Busting

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.

Function Pointers

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

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.

Macros

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.

Links

Here are some random links about porting C/C++ to Java:

  • Jazillian – this guy’s put some serious thought into the issue. Plus, he occasionally stirs the pot on the ANTLR mailing list which is always fun.
  • Point Legacy C++ code Java: Tales from a Trading Desk – the answer is here. The point about functional tests is important. Lucky for me, some functional tests already existed for Soar and I had help from a Soar “guru”
Categories: c++, java, soar, software engineering Tags: , , ,