11 May 2007

This is the way I roll

I wrote a piece of code that I'm fairly proud of. It was a bit of last minute effort before leaving my current job at MBARI, so it isn't polished, but I like the way it turned out. I used test first development for a lot of it and also some fluent interface stuff. It turned out being one of those code bases where I was able to come out of it with both decent functionality and a clean API, and that is an accomplishment in my mind.

You can see the project with full source code here. It's da bomb... (not) dot com. It's a timeline widget for displaying time based events along a single time axis.

12 March 2007

Rendering PNGs in Java

This post details an optimization problem that took me on a long and circuitous route. I'm writing it as documentation of my trail of tears. If anyone else is having problems with Java rendering 8bit png's slowly, or if the png's are taking up too much memory, I would endorse the approach described below. Without a tRNS chunk and color palette I consistently see poorer performance out of the Java render pipeline.

I have an application that works in the GIS mode of operation. There is a base map and on top of that base map are layers of geographically positioned images. For various reasons, all of these images are in the PNG format. Each image, except for the base layer, consists of two colors: black, which is set to fully transparent, and some other color, set to fully opaque. To control the navigation of the geographic context I use the terrific Piccolo API, an API designed for developing Zoomable User Interfaces. The application works very well; layers are easy to add, piccolo provides all the proper hooks to make user coordinate to geographic coordinate conversions, and the pan/zoom interactions are easy to use. There was but one problem: performance.

Especially on windows, the application performance is actually pretty good, particularly in light of the fact that all image rendering is happening on the main CPU rather than the graphics card. I tried to get the opengl pipeline in Java working through various tactics, but none of them worked reliably enough to make me feel confident that I could manage the install on other peoples computers, much less my own. Further, when I tried to use Java's default opengl pipeline the render performance on my zippy windows box slowed to a crawl. I didn't realize this until I tested on Linux, where the opengl pipeline is enabled by default (disabled by default in windows). If you see really slow rendering of PNGs with java, try passing the command line argument -Dsun.java2d.opengl=false, it makes a world of difference in my application.

So, I'm not complaining about the speed, it's "good enough". However, because I am rendering in memory on the main CPU my application was quite a resource hog. I'm using at least 3 images that are 4000x5000 pixels and a fourth that can be that big as well. While each of those images weighs in at a svelte 100k on disk, when you render, the full raster info needs to sit in an array. This means that at best, the smallest in-memory size for each of these images will be 2.5MB (20Mpx * 1bit / 8). But to make matters worse, because I hadn't adjusted the defaults on my image producing process, I was generating images with 64 bits per pixel. Using IrfanView I see that a 5000x4000, downconverted to 24 Bits per pixel, uses 60MB of memory. Additionally, IrfanView says this image takes 1.6 seconds to load, and that's using native code. No wonder my application wasn't performing as well as it could!

Okay, this is easy, I just need to convert to a lower Bit Per Pixel (BPP) level and I'm set. Not so easy, of course. From all of my testing, it looks to me like Java's png rendering is optimized for certain paths. For instance, when I converted my images to 1BPP (remember, my images only have two colors so I can do this), not only did the Java memory consumption not go down at all, I actually saw a significant slow down in the rendering speed in my application.

Through much trial and error, I found that a combination of 8bit pixels and a color palette was the friendliest format for Java to render. Now, I just tell ImageMagick that this is what I want and it's as easy as that, right? Wrong... of course. ImageMagick can generate 8bit images, but it only does it the GIF way, with binary transparency (i.e. some color is declared the transparent color and all instances of that color in the image are drawn transparent). Sadly, the png renderer in Java just flat out refused to honor this format (I didn't fiddle with this much). What Java really likes, as far as I can tell, is what png calls RGBA-Palette. This is a format that is unique to PNG, so I'm not surprised that ImageMagick does not support it. However, it is a cool format. What it does is allow for an additional block of metadata called tRNS. tRNS is an array of tranparency values from 0-255 that are applied to the color palette's array, so any color in the color palette can have a transparency value added to it. So here's what I did to get tRNS into my image.

  • Create my colored image with 8BPP using ImageMagic
    • C:\test_8bit>convert test.png -transparent black -fill red -opaque white -map nestscape: test2.png
      • Note, I use the nestcape color map to force 8bit color. When I don't use it I get a 4 color image back and for some reason the next step of inserting the tRNS chunk does not work with that image.
      • test.png is a grayscale image that consists of black and white pixels. The imagemagick command will convert black pixels to transparent and white to red.

  • Insert the tRNS chunk.

    • C:\test_8bit>pngcrush -trns_array 1 0 test2.png test3.png
      • Because the netscape color map starts with black, the trns_array needs to only contain one entry. The first number after -trns_array is the array length, which is then followed by array elements. 0 sets the first color in the color palette (black) to transparent.

And that's it. I now have transparent 8-bit images that render quickly, take up as little memory as possible and use less than a fifth of the disk space than they did originally. Woohoo!

Useful PNG Tools
Through all this fooling around, I came across a couple useful tools for working with PNGs. The two most useful for my purposes were PNGCRUSH and TweakPng. TweakPng is the tool that I used to examine PNG files that I knew worked in my system. Through that, i was able to manually manipulate the images I was getting back from ImageMagick and keep tweaking those images until they rendered as I wanted in Java. PNGCRUSH was then the followup to TweakPng that let me insert the tRNS programatically. Of course, if you really need to hack at PNGs there's always libpng as well...

Labels: , ,

26 October 2006

Ignoring tail call recursion...

I'm feeling bitchy right now, so if you don't want to here my venting on tail call recursion optimization, move along.

This bitch is specifically directed at the code in Bruce Tate's article on IBM's developerWorks site, Concurrent programming with Erlang, but the exact same code shows up all over the place.

The problem is, when folks are trying to explain functional programming they love to use the fibonacci and factorial algorithms to demonstrate how cleanly the mathematical definition translates into functional code. Invariably, you see something like this:

factorial(0) -> 1;
factorial(N) -> N * factorial(N-1).

And we all say, "wow, that's really cool how concisely you've written that function". But then we also say, "wait a minute, that recursive call is going to cause your stack to grow and grow, that ain't cool". And if you are thinking that, you're totally justified in doing so, because you're right. That really isn't cool. That's because the author, in an effort to introduce as few new concepts as possible, is leaving out the standard use of an accumulator to allow for tail call optimization.

Okay, if you don't already know what tail call optimization is, I'm sure you're dying to know now. It's really quite a simple concept, but is really important if you want to get the most out of your recursive functions. What tail call optimization does is it looks at the current stack frame where a function call is being made, and if that function call does not rely on anything outside of its own arguments, it releases the resources from that frame. This allows the garbage collector to come through and do its job, it also allows you to call a recursive function an infinite number of times without overflowing the stack. Let me show you what I mean with some code.

factorial(N) -> factorial(N, N-1).
factorial(Accum, 0) -> Accum;
factorial(Accum, N) -> factorial(Accum * N, N-1).

The function that clients would call is still the single argument version of factorial, but now we've introduced a new two argument (btw, in Erlang, the number of arguments a function takes is called its "arity") function. Looking at the two versions of the function, you'll see that instead of the recursive call "N * fact(N-1)" we take that N that's hanging out outside of the function and put it within the functions arguments. This one small change now allows the compiler/virtual machine/whoever to look at the last function called and see that there's nothing left in the current stack frame that will be used in the future, so that frame can be forgotten (gc'd). When we had that hanging reference to N in the first version of the function the stack frame could not be eliminated because down the line, when the recursive function returned, it would then need to use that value of N. You can test this out by executing the two versions of factorial, on my machine trying to evaluate factorial(100000) crashed the non-optimized version while the optimized version ran just fine (Erlang also handles numbers of arbitrary size, so factorial(100000) spits out a crazy big integer value).

Once you have tail call optimization you can start to see how functional languages can get away with not having for loops (a pure functional language can't have for loops because that would require incrementing a variable and variables can only be assigned once in FP). So, instead of saying:

for(int i = 0; i < 50; i++){ do_something(i); }

we would say:

for_loop(i, max) when (i < max) -> do_something(i), for_loop(i + 1, max);
for_loop(i, max) -> .//end

Here, for_loop is just a function that uses an accumulator and a max value. Since that last call to for_loop does not require any other information besides what's in its arguments, it the current stack frame will be removed. Without tail call optimization the iterative version of the for loop is clearly superior to the recursive version, but with optimization the two are basically equivalent.

11 October 2006

What I saw from Alvin

Well, this post has been a long time coming. Mainly because it's a daunting task to describe what diving in Alvin was like, so I kept putting it off. I've decided that a sub-par description is better than none at all, so here goes.

For three weeks in August I went to sea on the research vessel Atlantis with a team of fellow MBARI engineers as well as scientists from Dr. Ken Smith's lab. My team was there to test the autonomous vehicle we've been building, hopefully I'll talk more about that some other time. The special thing about Atlantis is that it is home to the deep sea research submarine Alvin, one of the few deep sea manned submersibles in the world. Because Ken Smith, the chief scientist of the cruise, is such a great guy, he tried his best to get as many people down in Alvin as the schedule permitted. Luckily, I was one of those lucky people.

Diving in Alvin was amazing. On my dive we went to 4100 meters deep and I seem to remember the rate of decent being around 25 meters a minute. So, that means for the first two hours and forty minutes we were descending. Not a minute of that time was boring though. There was a ton of stuff to see out of the small window next to where I was sitting, what I was struck by throughout the dive was how much biomass there actually is in the ocean. From about 250 meters deep until about 2000 meters there was a ton of bioluminesence. As the sub descended, it created turbulence in the water and this caused creatures affected by that turbulence to bioluminesce, a really amazing sight. When we eventually got to the bottom we quickly navigated to where our rover was parked and waited for it's mission script to begin. The evening before the dive I had been making code changes to the Rover, trying to work around a hardware bug that had only been uncovered after implementing some new behaviours. So, I was really interested (ahem, nervous) in how the Rover would perform. Luckily, the Rover did a pretty good job. It moved in the right direction, and at the right speeds (we were testing different speeds) right up until it got to the new moves we wanted it to make (turning to various compass points), then it made what right turn and quit. Great, nothing like seeing your bugs manifest themselves at 4100 meters. Luckily I was more worried about the 9000 pounds per square inch of water pressure we were under then what my colleagues would say about the bug, so I kept enjoying myself ;-)

So, with the Rover finished with it's mission we had other science objectives to complete. I'm not going to get into those, because this has already gone on longer than I'd planned. But the whole reason I wanted to make this post was to show the following video. We saw this little Isopod swimming by near the Rover and we were so intrigued by it that we followed it for several minutes. This kind of crazy creature is right at home in the deep ocean, where everything was a bit crazy.

Update: This isopod is from the family munnopsid and is a bathyopsurine, possibly a Bathopsurus or Paropsurus (see the comments section for how I found this out).



I felt like I was inside one of Salvador Dali's surreal landscapes...

18 April 2006

Aspected Oriented Programming with Rails Engines

I was talking to my co-worker the other day about ruby on rails and some of the benefits of the database wrapper approach versus the database to object mapping approach (which I think is well summarized in this developer works article ) and as a side note, he mentioned that he'd like a framework that did a good job handling cross-cutting concerns (and I think he said JBoss does do this to some degree, but I don't remember how well). Today, after installing rails engines I was looking at the readme and came across this:


Rails Engines are a way of dropping in whole chunks of functionality into your existing application without affecting *any* of your existing code. They could also be described as mini-applications, or vertical application slices - top-to-bottom units which provide full MVC coverage for a certain, specific application function.

This, to me, is finally an example of aspect oriented programming outside the box of logging, security et. al and into an arena of much more diverse problems. And the funny thing is, they never once say the word "aspect" in describing engines (at least in the readme). Woopee! (man, i gotta get a life ;-)

Let me justify my claim with a little more detail. First, a general explanation of AOP with regards to Ruby. Aspect oriented programming works through changing the behavior of your code in some manner that addresses a cross-cutting concern, such as logging, in one form or another. There's code generation, which in the Java world we all know through the heavy use of xdoclet. There's also code weaving, which takes the form of byte code manipulation in Java, a fairly sophisticated task, but doable. With ruby on rails both these forms of AOP are used heavily, but with significantly less struggle. Many of the RoR components use code generation to provide skeleton frameworks and sensible default behaviors, this can be seen right off the bat when you start up your first Rails project and an entire application structure is generated on startup (test framework, make file, properties file, database configuration file, etc). The code weaving is similarly engrained in the framework. For instance, when extending the main email class (ActionMailer) you can simply define methods such as "lateFeeReminder" and then call a method that is generated at runtime "myEmailClass.deliver_lateFeeReminder" and the base class will catch that undeclared method and create a method on the fly (or something to that effect) that allows you to deliver the email that is described in lateFeeReminder. It's the equivalent to byte code weaving in Java, but far easier due to various design aspects of Ruby (interpreted, clean OO).

So back to my point about engines. It'll be a while before I get a feel for how I like working with them, but at least on paper the rails engines are a great way to address concerns such as a login subsystem in a modular, easily overridable way. I'm really hoping to taste some proof in this pudding.

p.s. I know I've left out a lot of references to previous work (smalltalk comes immediately to mind), but I'm trying to be as to the point as possible without glossing over too many details.

28 March 2006

On Method Chaining

In Eric Evans tutorial at SDWest the question of method chaining came up in response to some of Eric's Time and Money code.

The code which brought up the question was something like this:


CalendarDate workdate = CalendarDate.date(2006, 2, 15);
CalendarDate billdate = workdate.plusMonths(1).lastOfMonth();
int day = workdate.plusMonths(1).lastOfMonth().dayOfWeek(); //(contrived) method chaining
if(day == Calendar.SATURDAY || day == Calendar.SUNDAY){
billdate = billdate.plusDays(2);
}


The objection raised concerns the third line, where four methods are chained together (I purposely avoided re-using billdate to create this contrived example). So why is this okay? One simple reason, the method chain is completey stateless. That, to me, is the thing to look for when deciding whether it's "okay" to chain methods, if they can be explained entirely in terms of their inputs and outputs (that is, no side effects).

The second half of my rule for method chaining is just the opposite of the above, state changing methods should not be chained. That means I'd preclude the Smalltalk idiom of returning an object reference from setter methods with this rule. None of this:

myObject.setAttr(foo).bar();

At one point I had a good reason for precluding this second case, but it eludes me for now. However, at the very least, I would say the above is bad because it hides a state transformation occuring in "myObject". It is preferable to avoid chaining in these cases so that these state transformations are made explicit in the flow of the code... I think.

20 March 2006

Hello, world



/*A blog, just like a billion others, but this one is mine */
public class AndrewsBlog extends LemmingBlog{
Collection currentResearch;
Collection workActivities;
Collection lifeActivities;

public AndrewsBlog(){
currentResearch = new PriorityQueue();
workActivities = new RoleList();
lifeActivities = new WeakHashMap();
}
}