Archive of ‘Java’ category

Come work for me at Cartifact!

If you are in the Los Angeles area, have a couple of years (or a few decades!) of experience writing software in Java (or heck, if you’re fresh out of school and want to sink your teeth into developing for the real world), and want to help create a new development group here writing software for some of the biggest real estate developers in the world, send me your resumé!

We’re a small company but we’re doing work for some of the largest companies in the world. And the upside is damned near limitless, as we sit square at the intersection of technology, liberal arts, and customers with very deep pockets with very real needs.

You know where you can reach me… :-)

On Memory Leaks in Java and in Android.

Just because it’s a garbage collected language doesn’t mean you can’t leak memory or run out of it. Especially on Android where you get so little to begin with.

Now of course sometimes the answer is that you just need more memory. If your program is a Java command line program to load the entire road map of the United States to do some network algorithms, you probably need more than the default JVM configurations give you.

Sometimes it’s not even a full-on leak, but a large chunk of memory isn’t being released in time as a consequence of some holder object that isn’t being released in time.

There are some tools that can help. With Android, you can use DDMS to get an idea what’s going on, and you can even dump a snapshot of the heap by using the Dump HPROF File option. (You can also programmatically capture uncaught exceptions on startup of your application or activity and dump an hprof file within the exception handler like so:

public void onCreate(Bundle savedInstanceState)
{
...
    Thread.setDefaultUncaughtExceptionHandler(new Thread.UncaughtExceptionHandler()
    {
        @Override
        public void uncaughtException(Thread thread, Throwable ex)
        {
            try {
                File f = new File(Environment.getExternalStorageDirectory(),"error.hprof");
                String path = f.getAbsolutePath();
                Debug.dumpHprofData(path);
                Log.d("error", "HREF dumped to " + path);
            }
            catch (IOException e) {
                Log.d("error","Huh?",e);
            }
        }
    });
...
}

Of course once you have an .hprof file from Android you have to convert it to something that can be used by an application such as the Eclipse Memory Analyzer tool using the hprof-conv command line application included as part of the Android SDK; there is more information on how to do this and how to use the MAT tool here: Attacking memory problems on Android.

One place where I’ve been running into issues is with a clever little bit of code which loads images from a separate thread from a remote resource, and puts them into a custom view that replaces the ImageView class. This little bit of code creates a background thread which is used to talk to a remote server to download images; once the image is loaded, a callback causes the custom view to redraw itself with the correct contents. A snippet of that code is below:

/*  Cache.java
 *
 *  Created on May 15, 2011 by William Edward Woody
 */

package com.chaosinmotion.android.utils;

import java.io.File;
import java.io.FileOutputStream;
import java.io.InputStream;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map.Entry;

import org.apache.http.HttpEntity;
import org.apache.http.HttpResponse;
import org.apache.http.client.HttpClient;
import org.apache.http.client.methods.HttpGet;
import org.apache.http.impl.client.DefaultHttpClient;

import android.graphics.Bitmap;
import android.graphics.BitmapFactory;
import android.os.Handler;

public class Cache
{
    /**
     * Our callback interface
     */
    public interface Callback
    {
        void loaded(String url, Bitmap bitmap);
        void failure(String url, Throwable th);
    }
    
    /**
     * Item in the queue which is waiting to be processed by our network thread(s)
     */
    private static class QueueItem
    {
        String url;
        Callback callback;
        
        QueueItem(String u, Callback c)
        {
            url = u;
            callback = c;
        }
    }
    
    /// The handler to thread to the UI thread
    private Handler fHandler;
    /// The event queue
    private LinkedList<QueueItem> fQueue;
    /// The global cache object, which will be created by the class loader on load.
    /// Because this is normally called from our UI objects, this means our Handler
    /// will be created on our UI thread
    public static Cache gCache = new Cache();
    
    /**
     * Internal runnable for our background loader thread
     */
    private class NetworkThread implements Runnable
    {
        public void run()
        {
            // Start HTTP Client
            HttpClient httpClient = new DefaultHttpClient();
            
            for (;;) {
                /*
                 * Dequeue next request
                 */
                QueueItem q;

                synchronized(fQueue) {
                    while (fQueue.isEmpty()) {
                        try {
                            fQueue.wait();
                        }
                        catch (InterruptedException e) {
                        }
                        break;
                    }

                    /*
                     * Get the next item
                     */
                    q = fQueue.removeLast();
                }
                
                /*
                 * Read the network
                 */
                
                try {
                    /*
                     * Set up the request and get the response
                     */
                    HttpGet get = new HttpGet(q.url);
                    HttpResponse response = httpClient.execute(get);
                    HttpEntity entity = response.getEntity();
                    
                    /*
                     * Get the bitmap from the URL response
                     */
                    InputStream is = entity.getContent();
                    final Bitmap bmap = BitmapFactory.decodeStream(is);
                    is.close();

                    entity.consumeContent();
                    
                    /*
                     * Send notification indicating we loaded the image on the
                     * main UI thread
                     */
                    final QueueItem qq = q;
                    fHandler.post(new Runnable() {
                        public void run()
                        {
                            qq.callback.loaded(qq.url,bmap);
                        }
                    });
                }
                catch (final Throwable ex) {
                    final QueueItem qq = q;
                    fHandler.post(new Runnable() {
                        public void run()
                        {
                            qq.callback.failure(qq.url,ex);
                        }
                    });
                }
            }
            
//            httpClient.getConnectionManager().shutdown();
        }
    }
    
    /**
     * Start up this object
     */
    private Cache()
    {
        fHandler = new Handler();
        fQueue = new LinkedList();
        Thread th = new Thread(new NetworkThread());
        th.setDaemon(true);
        th.start();
    }
    
    /**
     * Get the singleton cache object
     */
    public static Cache get()
    {
        return gCache;
    }
    
    /**
     * Get the image from the remote service. This will call the callback once the
     * image has been loaded
     * @param url
     * @param callback
     */
    public void getImage(String url, Callback callback)
    {
        synchronized(fQueue) {
            fQueue.addFirst(new QueueItem(url,callback));
            fQueue.notify();
        }
    }
}

Now what this does is rather simple: we have a queue of items which are put into a linked list, and our background thread loads those items, one at a time. Once the item is loaded, we call our callback so the image can then be handled by whatever is using the service to load images from a network connection.

Of course we can make this far more sophisticated; we can save the loaded files to a cache, we can collapse multiple requests for the same image so we don’t try to load it repeatedly. We can also make the management of the threads more sophisticated by creating a thread group of multiple threads all handling network loading.

We can then use this with a custom view class to draw the image, drawing a temporary image showing the real image hasn’t been loaded yet:

/*  RemoteImageView.java
 *
 *  Created on May 15, 2011 by William Edward Woody
 */

package com.chaosinmotion.android.utils;

import android.content.Context;
import android.graphics.Bitmap;
import android.graphics.Canvas;
import android.graphics.Color;
import android.graphics.Paint;
import android.view.View;

public class RemoteImageView extends View
{
    private Paint fPaint;
    private Bitmap fBitmap;
    private String fURL;

    public RemoteImageView(Context context)
    {
        super(context);
        // TODO Auto-generated constructor stub
    }
    
    public void setImageURL(String url)
    {
        fBitmap = null;
        fURL = url;
        
        Cache.get().getImage(fURL, new Cache.Callback() {
            public void loaded(String url, Bitmap bitmap)
            {
                fBitmap = bitmap;
                invalidate();
            }

            public void failure(String url, Throwable th)
            {
                // Ignoring for now. Could display broken link image
            }
        });
    }

    @Override
    protected void onDraw(Canvas canvas)
    {
        if (fPaint == null) fPaint = new Paint();
        
        canvas.drawColor(Color.BLACK);
        if (fBitmap == null) return;        // could display "not loaded" image
        canvas.drawBitmap(fBitmap, 0, 0, fPaint);
    }
}

This is a very simple example of our using the Cache object to load images from a background thread. We can make this far more sophisticated; we can (for example) display a “loading” image and a “image link broken” image. We can also alter the reported size during onMeasure to return the size of the bitmap, or we can center the displayed bitmap or scale the bitmap to fit. But at it’s core, we have a simple mechanism for displaying the loaded image in our system.

Can you spot the leak?

I didn’t, at first.

Here’s a hint: Avoiding Memory Leaks

Here’s another: the RemoteImageView, being a child of the View class, holds a reference to it’s parent, and up the line until we get to the top level activity, which holds a reference to–well–just about everything.

No?

Okay, here goes.

So when we call:

        Cache.get().getImage(fURL, new Cache.Callback() { ... });

The anonymous inner class we create when we create our callback holds a reference to the RemoteImageView. And that inner class doesn’t go away until after the image is loaded. So if we have a few dozen of these and a very slow connection, the user switches from one activity to another–and we can’t let the activity go, because we’re still waiting for the images to load and be copied into the image view.

So while it’s not exactly a memory leak, the class can’t be let go of, nor can all the associated resources, until our connection completes or times out. In theory it’s not a leak, exactly, because eventually the memory will be released–but it won’t be released soon enough for our purposes. And so we crash.

So how do we fix this?

Well, we need to add two things. First, we need to somehow disassociate our view from the anonymous inner class so that, when our view no longer exists, the callback class no longer holds a reference to the view. That way, the activity can be reclaimed by the garbage collector even though our callback continues to exist. Second, we can remove the unprocessed callbacks so they don’t make a network call to load an image that is no longer needed.

To do the first, we change our anonymous inner class to a static class (that way it doesn’t hold a virtual reference to ‘this’), and explicitly pass a pointer to our outer class to it, one that can then be removed:

/*  RemoteImageView.java
 *
 *  Created on May 15, 2011 by William Edward Woody
 */

package com.chaosinmotion.android.utils;

import android.content.Context;
import android.graphics.Bitmap;
import android.graphics.Canvas;
import android.graphics.Color;
import android.graphics.Paint;
import android.view.View;

public class RemoteImageView extends View
{
    private Paint fPaint;
    private Bitmap fBitmap;
    private String fURL;
    private OurCallback fCallback;
    
    public RemoteImageView(Context context)
    {
        super(context);
        // TODO Auto-generated constructor stub
    }
    

    private static class OurCallback implements Cache.Callback
    {
        private RemoteImageView pThis;
        
        OurCallback(RemoteImageView r)
        {
            pThis = r;
        }
        
        public void loaded(String url, Bitmap bitmap)
        {
            if (pThis != null) {
                pThis.fBitmap = bitmap;
                pThis.invalidate();
                pThis.fCallback = null; // our callback ended; remove reference
            }
        }

        public void failure(String url, Throwable th)
        {
            // Ignoring for now. Could display broken link image
            if (pThis != null) {
                pThis.fCallback = null; // our callback ended; remove reference
            }
        }
    }

    public void setImageURL(String url)
    {
        fBitmap = null;
        fURL = url;
        
        fCallback = new OurCallback(this);
        Cache.get().getImage(fURL, fCallback);
    }

    @Override
    protected void onDraw(Canvas canvas)
    {
        if (fPaint == null) fPaint = new Paint();
        
        canvas.drawColor(Color.BLACK);
        if (fBitmap == null) return;        // could display "not loaded" image
        canvas.drawBitmap(fBitmap, 0, 0, fPaint);
    }

    @Override
    protected void onDetachedFromWindow()
    {
        // Detach us from our callback
        if (fCallback != null) fCallback.pThis = null;
        
        super.onDetachedFromWindow();
    }
}

The two biggest changes is to create a new static OurCallback class which holds a reference to the view being acted on. We then hold a reference to the callback that is zeroed out when the callback completes, either on failure or on success. Then on the onDetachedFromWindow callback, if we have a request outstanding (because fCallback is not null), we detach the view from the callback. Note that because all the calls in the callback are done on the UI thread we don’t need to synchronize access.

This will now detach the view from the callback when the view goes away, so the activity that contains the view can be reclaimed by the memory manager.

Our second change is to remove the request from the queue, so we don’t use unnecessary resources. While not strictly necessary for memory management purposes, it helps our network performance. The change here is to explicitly remove our callback from the queue.

First, we change our onDetachedFromWindow() call to remove us (by callback) from the cache:

    @Override
    protected void onDetachedFromWindow()
    {
        // Detach us from our callback
        if (fCallback != null) {
            fCallback.pThis = null;
            Cache.get().removeCallback(fCallback);
        }
        
        super.onDetachedFromWindow();
    }

Second, we add a method to the cache to look for all instances of requests with the same callback, and delete the request from the queue. If it isn’t in the queue, it’s probably because the request is now being acted upon by our networking thread. (If we were particularly clever we could signal our networking thread to stop the network request, but I’m not going to do that here.)

So our method added to the Cache is:

    /**
     * Remove from the queue all requests with the specified callback. Done when the
     * result is no longer needed because the view is going away.
     * @param callback
     */
    public void removeCallback(Callback callback)
    {
        synchronized(fQueue) {
            Iterator iter = fQueue.iterator();
            while (iter.hasNext()) {
                QueueItem i = iter.next();
                if (i.callback == callback) {
                    iter.remove();
                }
            }
        }
    }

This iterates through the queue, removing entries that match the callback.

I’ve noted this on my list of things not to forget because this (and variations of this) comes up, with holding references to Android View objects in a thread that can survive the destruction of an activity.

The basic model is when the view goes away (which we can detect with a callback to onDetachedFromWindow), to disassociate the callback from the view and (preferably) to kill the background thread so the view object (and the activity associated with that view) can be garbage collected in a timely fashion.

It’s not quite black magic…

Problem: I need to connect to an SSL socket while ignoring the trust certificate chain, so I can connect to a self-signed SSL connection. In particular I want to connect to an LDAP server using the Netscape LDAP library but I keep hitting the error:

“Caused by: sun.security.provider.certpath.SunCertPathBuilderException: unable to find valid certification path to requested target”

I managed to find a snippet of code with the correct solution here, and am basically repeating it here for my own edification.

First, to create a client socket you need to use a socket factory. But in order to connect to an SSL socket while bypassing the trust chain on the certificate, you must first set up the socket factory:

SocketFactory gSocketFactory;
...
SSLContext sc = SSLContext.getInstance("SSL");
TrustManager[] trustAll = new TrustManager[] {
        new X509TrustManager() {
            @Override
            public void checkClientTrusted(X509Certificate[] arg0,
                    String arg1) throws CertificateException
                    {
                    }

            @Override
            public void checkServerTrusted(X509Certificate[] arg0,
                    String arg1) throws CertificateException
                    {
                    }

            @Override
            public X509Certificate[] getAcceptedIssuers()
            {
                return null;
            }
        }
};

sc.init(null, trustAll, new SecureRandom());
gSocketFactory = sc.getSocketFactory();

Once the socket factory has been created, you can make an SSL connection:

Socket socket = gSocketFactory.createSocket();
socket.connect(new InetSocketAddress(host,port));
// Do stuff with the socket

The magic bit of code creates a new trust management chain and installs it into a new SSLContext object, used to build our socket factory. The trusted chain contains one X509TrustManager, which does–nothing. And thus, we can connect to all SSL sockets without worrying if we have the correct certificate installed or if the remote SSL connection is properly signed.

Usual caviats remain: don’t do this unless you must, it creates all sorts of security problems (such as increased susceptibility to man in the middle attacks), your mileage may vary, limited supplies are available, no shoes no shirt no service.

Simple things: volatile

I’ve been watching some posts go by discussing the volatile keyword.

Two observations.

(1) In C and Java, the volatile keyword means “make sure changes to this variable are read and written out from the actual variable.”

I’ve seen people suggest what this means is that if you don’t mark a variable volatile, then its value is only accessible to the thread writing that variable, or some such nonsense.

Not quote.

Volatile is essentially a hint to the optimizer, indicating that once the code point hits a statement to either read or write to the specified variable, the memory holding that variable should be accessed rather than optimizing out the read or write access.

For example, suppose I have the following bit of code:

public class A
{
    int x;
    
    public void test()
    {
        for (x = 0; x < 10; ++x) {
            System.out.println("Item " + x);
        }
    }
}

(Yes, this is a dumb, contrived example.)

A reasonable optimizer could write out the following (equivalent) instructions:

public class A
{
    int x;
    
    public void test()
    {
        for (int _tmp = 0; _tmp < 10; ++_tmp) {
            System.out.println("Item " + _tmp);
        }
        x = 10;
    }
}

In other words, rather than go through the hassle of generating a global access every time we look into ‘x’ (which is a relatively expensive operation), we could simply use a local stack variable (whose access is significantly faster), iterate through the loop, then slam the global variable x to 10 at the end of the routine.

What volatile says, however, is “don’t skip read/write access for this variable; it could change independently of the current instructions being executed in this thread.” In our example above, if we were to declare ‘x’ volatile:

public class A
{
    volatile int x;
    
    public void test()
    {
        for (int x = 0; x < 10; ++x) {
            System.out.println("Item " + x);
        }
    }
}

Then we’re telling the compiler on every access of the variable: when we set it to 0 at the start of the loop, when we increment it, and when we test to see if it is less then 10, and when we print it out–each time we should always go directly to the global variable. No fair using a local variable to speed things up. The optimization above, in other words, is illegal when x is marked volatile.

Of course this is a completely contrived example; in the real world you wouldn’t use a field for a for loop. But you may want to access a class variable and use it in a rather complex way while guaranteeing that within your method access to that variable isn’t optimized out for whatever reason–and volatile guarantees that for you.

(2) Java 5 and greater also adds an additional semantic to volatile: reads and writes to the variable are guaranteed to be atomic. What this means is simple: suppose you’re writing a long integer:

	long i = 5;

The underlying processor may be a 32-bit processor, which means that the underlying CPU must actually do something like:

	int i_0 = 0;		// the first 4 bytes
	int i_1 = 5;		// the last 4 bytes

In other words, the assignment ‘i = 5’ actually requires two processor memory write operations.

Now suppose we have a task swap take place between the first write and the second. Then what happens is that only half of our long integer has been updated, and the other half may contain garbage. So in the following contrived example:

	long i = -1;
	// some time later...
	i = 0;

A read from the variable i could, in theory, return more than just -1 and 0: it may also return 0xFFFFFFFF00000000 or it could return 0x00000000FFFFFFFF, depending on the order the 32-bit words are written.

If i is only allowed to be -1 or 0, well, you can see how you could have a problem.

By guaranteeing that the reads and writes are atomic, however, Java guarantees that both words are written before we attempt to read either. In other words, by declaring i volatile we do the equivalent of:

    synchronized(_semaphore) {
        int i_0 = high_word;
        int i_1 = low_word;
    }

(Though the semaphore Java uses is significantly faster.)

This means we’ll never see 0xFFFFFFFF00000000 or 0x00000000FFFFFFFF in our contrived example, if we only declare i as volatile, with Java 5 or later. (Java 1.4 or earlier, however, does not guarantee atomic read/write semantics, which means you must wrap the variable in a semaphore.)

It’s important to be aware of these issues and carefully craft your code with a full understanding of the ramifications of your code. Otherwise you may wind up with a multi-tasking application which, on a very rare (and damned hard to find occasion) just randomly fail for no good reason.

Little killers: channel abuse.

Channel abuse.

When you use a magic value in a particular field (such as a text field) in order to signify something else. For example, if you use a magic text pattern (like ‘XXX’) to signify the last record.

This can kill you because (a) what if the user types in “XXX” into that field? And (b) if you’re storing the record as an explicit marker, what happens if your magic record goes away?

Better off either creating some sort of conversion protocol to allow out-of-band information to reside within the text (like the & escape character in HTML), or to create a separate control channel to contain control data. And if you’re using the symbol as an end of array marker, you’re much better off using the built-in OS routines (end of file marker, end of database marker, etc) to determine you’re at the end of the list.

A surprising observation, or finding your own voice.

One thing that surprised me was the percentage of people who, on reading my code from my last post, took umbrage to the following line of code:

if (null != (ret = cache.get(n))) return ret;

(Okay, in all fairness, only two people out of 20 or so commenters made a comment–about one in 10, but on a trivially small data set.)

It fascinates me.

First, a disclaimer. I don’t mean to use my comments to disparage anyone. I don’t know the people who made their comments, and I’m sure if they’re here they’re clearly very intelligent people of the highest caliber whose code quality is undoubtedly impeccable. If it wasn’t, they wouldn’t be here, right?

My comments go to current development trends, however, which motivate people to be far more interested in form over function.

There is nothing new here, by the way, as I go into in my comments below. But I’m fascinated by the devotion of form over function that is being taught to our developers which sometimes makes people blind to the reasons why the form exist.

I started tinkering with computers in 1977 when I played with the BASIC interpreter on a TRS-80 in the 8th grade. I don’t observe this to suggest that my experience trumps other people’s experience or to present myself as some sort of code guru or expert that people should not argue with. I only note this to note that I’ve been around a while and have seen different trends ebb and flow over the past 34 years of hacking, and over the past 23 years or so of doing this professionally since getting my B.S. in Math from Caltech.

It’s context, nothing more.

But in that time, I’ve noticed a few shifting trends: things that at one time was considered “best practice” are is now considered poor practice or visa versa.

Take, for example, the statement above that started this whole article. One suggestion I saw was to rewrite the code:

MyClass ret = cache.get(n);
if (null != ret) return ret;

We could even go so far as to rewrite this statement with the allocator statement reserving the variable on a separate line:

MyClass ret;
ret = cache.get(n);
if (null != ret) return ret;

When I started writing software, we edited our code on an 80 x 24 character display. This means you could only see 24 lines of code at any one time. Back then, the two statements below would have consumed two or three of those 24 lines of code, and so would be considered inferior to the one line statement:

if (null != (ret = cache.get(n))) return ret;

Back then, the limit on the number of characters in a line also favored shorter variable names. Setting aside, of course, that earlier C compilers could only match variable names of 6 characters or less (so that, for example, ‘myVariable’ would match ‘myVari’ or ‘myVariFoo’), which was imposed partially for memory reasons, but partially because of a lack of need–variable names were kept short because:

if (null != (foundFactorialReturnValue = factorialReturnStorage.get(n))) return ret;

This could get pretty unwieldy.

It gets worse when discussing formulas, such as the distance between two points:

double dx = p1.x - p2.x;
double dy = p1.y - p2.y;
double dist = Math.sqrt(dx * dx + dy * dy);

is easier to follow than:

double deltaXCoordinate = point1.xCoordinate - point2.xCoordinate;
double deltaYCoordinate = point1.yCoordinate - point2.yCoordinate;
double distanceBetweenPoints = Math.sqrt(deltaXCoordinate * deltaXCoordinate + deltaYCoordinate * deltaYCoordinate);

Of course programming styles change over the years. We’re no longer constrained by the 80×24 character limits of a green ADM-2A terminal. My computer display at home is 30 inches in diagonal, and capable of displaying several hundred lines of code with documentation in a separate window. Even the smallest MacBook Air has a pixel resolution of 1366 x 768 pixels; at 12 pixels per line, this means you can easily display 55 lines of code with room left over for the window tile and decorators and the menu bar.

And of course in the desire to cram more and more code into an 80×24 character display, C programmers took some “liberties” that took the whole drive towards putting as much information within a single line of code waaaay to far, writing such abominations as:

for (ct=0,p=list;p;++ct,p=p->next) ;

which counts the number of items in a linked list. (The count is in ct, the list in list.)

(In fact, this drive for “clarity” through compactness was one of the inspirations that led to the creation of the International Obfuscated C Code Contest.)

Today, I believe the pendulum has swung too far in the other direction. We’re so hell bent on the proper form (out of concern that, by putting a compound statement in a single line of code it will make it ‘harder’ to understand) that we even have tools (such as Checkstyle) which will enforce syntactic styles–throwing an error during the build process if someone writes an early return or a compound statement.

And while I’m not arguing anarchy, I do believe going so far as to break the build because someone dared to write a compound statement with an early return rather than writing:

MyClass ret;
ret = cache.get(n);
if (null == ret) {
    // some additional logic with a single exit point 
    // at the end of the if statement, using no returns, 
    // breaks or continues or (God help us!) gotos
}
return ret;

is going too far. (Setting ‘ReturnCount’ = 1 in Checkstyle.)

Imagine a world with only declarative sentences. There are no conjunctions. All sentences follow a proper format. All sentences start with a noun. The noun is followed by a proper verb phrase. The verb phrase is followed by a well structured object. The object of the sentence is a proper noun phrase.

Imagine this world with well written sentences. Sentences that follow the format taught in the third grade.

“I want you to be an uncle to me,” said Mr. George Wright. He leaned forward towards the old sailor.

“Yes,” said Mr. Kemp. Mr. Kemp was mystified. Mr. Kemp paused with a mug of beer midway to his lips.

Or:

The question is ‘to be or not to be.’
Is it nobler to suffer outrageous fortune?
Or should we take arms against a sea of rising troubles, and end them?
To die? To sleep no more?

Sorry, but I don’t think Shakespeare or Hemingway are helped by our rules.

Ultimately writing code has two goals.

The first is to accomplish a task, to create a software package that can be deployed which accomplishes the specified task with as few bugs (or no bugs) as possible.

The second is to produce maintainable code: code that, years from now, you can figure out. And code that, more likely than not, will be handed off to a maintenance developer–possibly overseas in India or China–who will be asked to understand and maintain the software that you wrote.

Now both tasks can be helped by writing simple code: that was yesterday’s post.

But code legibility can also be helped by thinking about the code you write.

To me, writing code is like writing an essay. Like an essay, which is full of sentences and paragraphs and sections, code is full of statements, and code groupings (like paragraphs) and classes or modules.

And like sentences, which has rules that we were all taught in the third grade (but then we later ignore as we learn the rules of the road and find our own voice), code too has rules of legibility that we should be able to break judiciously as we gain experience.

Each statement of code is, in a way, a sentence: it has a noun (the object being operated on), a verb (the operator or function call), subjects (parameters), and so forth. While we’re taught that a sentence must have a subject, a verb and an object, we learn later on that perhaps to express ourselves we can bend the rules.

So, for example:

if (null != (ret = cache.get(n))) return ret;

This may be a perfectly acceptable statement under the right circumstances: the idea is clearly expressed (get the cached value and return it if it was found), the logic is easy to follow.

And by putting it on one line, our focus is carried away from the logic of checking the cache and can focus on the multiple lines of calculating the cached value. We can concentrate, in other words, on the meat of the algorithm (the computational code), and the code which bypasses the check can be made into a functional footnote.

Of course there are places where this can be the wrong thing to write as well: if the emphasis in the routine, for example, is on checking the cache–well, then perhaps this deserves a multi-line statement.

Or perhaps when we find a value in our cache we trip off some other logic, then the logic deserves a line of it’s own. Perhaps the checking is sufficiently important enough that it needs to be called out separately, like:

ret = cache.get(n);
if (null != ret) {
	return doThing(ret);
}

It’s all a matter of communicating, with your own voice, what is and is not important, so future generations of code maintainers can understand what is and is not important, what goes together and what is separate.

Ultimately it’s about striving for a balance: creating working code that can be understood, by using idioms of programming which convey the subtext of the meaning of that code.

Sure, when you’re inexperienced and you haven’t found your voice, it’s appropriate to follow a strict “noun/verb/object” structure. It’s appropriate, in other words, to use simple declarative statements while you gain experience writing code, and to observe other common “best practices” such as using descriptive variable names.

But at some point you need to find your own voice. When you do, it’s also appropriate to break the rules.

And if you concentrate too much on the rules rather than on what’s being said, then perhaps you’ll also make the mistake both commentors did when commenting on my code style, when they failed to note the code itself was actually broken, with a dangerous infinite loop triggered by certain parameter values.

How (not) to write Factorial in Java.

I will admit this post was inspired by How would you write factorial(n) in java? So excuse me while I rant in code: I have a point to make at the bottom of this article.

Now most people who write factorial in Java may start with something simple, like:

    public static int factorial(int n)
    {
        if (n == 0) return 1;
        return n * factorial(n-1);
    }

Wrapping this in a class (since we’re talking about Java, of course), they may write it inside a utility class. For example:

public class FactorialUtil
{
    public static int factorial(int n)
    {
        if (n == 0) return 1;
        return n * factorial(n-1);
    }
}

Simple, no?

There is a non-recursive solution as well:

public class FactorialUtil
{
    public static int factorial(int n)
    {
        int ret = 1;
        for (int i = 1; i <= n; ++i) ret *= i;
        return ret;
    }
}

Now the observent reader may note “gosh, it’s entirely possible the value will be longer than an integer”, so they’ll perhaps rewrite in terms of BigInteger or at least in terms of long, depending on the requirements of the program. Thus:

public class FactorialUtil
{
    public static BigInteger factorial(int n)
    {
        BigInteger ret = BigInteger.ONE;
        for (int i = 1; i <= n; ++i) ret = ret.multiply(BigInteger.valueOf(i));
        return ret;
    }
}

Notice that thus far, of course, I’ve made no use the fact that I’m constantly recalculating the intemediate values from 1 to n. If those values were cached, of course, I could save myself a lot of computations. One way to do this is to use recursion, but if we’ve already calculated the value, store it away for future use. Thus (using HashMap, because it’s there), we get:

public class FactorialUtil
{
    static HashMap<Integer,BigInteger> cache = new HashMap<Integer,BigInteger>();
    
    public static BigInteger factorial(int n)
    {
        BigInteger ret;
        
        if (n == 0) return BigInteger.ONE;
        if (null != (ret = cache.get(n))) return ret;
        ret = BigInteger.valueOf(n).multiply(factorial(n-1));
        cache.put(n, ret);
        return ret;
    }
}

Easy enough, right?

Now each of these different methods entail different tradeoffs, and given that we may wish to reuse this library in the future, perhaps what we want to use is a technique routinely used in other Java libraries: a pluggable mechanism that allows us at runtime to decide which technique (the slower but small memory footprint technique, or the more memory intensive, but faster technique). So first, we need to refactor our class as a singleton, because pluggable things require instantiated classes and a default singleton class to implement the default mechanism.

So we create a class whose job it is to maintain a singleton for our factory class, and a reference to the algorithm that actually implements our method. This class provides the old interface we have from above, but defers to a separate (and new and improved!) algorithm engine:

public class FactorialUtil
{
    private static FactorialUtil singleton;
    private FactorialAlgorithm algorithm;
    
    /**
     * Default (internal) constructor constructs our default algorithm.
     */
    private FactorialUtil()
    {
        algorithm = new CachedFactorialImplementation();
    }
    
    /**
     * New initializer which allows selection of the algorithm mechanism
     * @param algorithm
     */
    public FactorialUtil(FactorialAlgorithm a)
    {
        algorithm = a;
    }
    
    /**
     * Default public interface for handling our factorial algorithm. Uses
     * the old standard established earlier for calling into our utility class.
     * @param n
     * @return
     */
    public static BigInteger factorial(int n)
    {
        if (singleton == null) {
            // Use default constructor which uses default algorithm
            singleton = new FactorialUtil();
        }
        return singleton.doFactorial(n);
    }

    /**
     * New mechanism which allows us to instantiate individual factorial
     * utilitiy classes and invoke customized factorial algorithms directory.
     * @param n
     * @return
     */
    private BigInteger doFactorial(int n)
    {
        // Defer to our algorithm
        return algorithm.factorial(n);
    }
}

Notice the above class is now responsible for creating the singleton and deferring to the algorithm class. We even have a private initializer which initializes to any algorithm, and a way to create an instance which uses the algorithm we select.

This all depends on an algorithm interface:

public interface FactorialAlgorithm
{
    BigInteger factorial(int n);
}

And here is our cached factorial implementation referred to from above:

public class CachedFactorialImplementation implements FactorialAlgorithm
{
    static HashMap<Integer,BigInteger> cache = new HashMap<Integer,BigInteger>();
    
    @Override
    public BigInteger factorial(int n)
    {
        BigInteger ret;
        
        if (n == 0) return BigInteger.ONE;
        if (null != (ret = cache.get(n))) return ret;
        ret = BigInteger.valueOf(n).multiply(factorial(n-1));
        cache.put(n, ret);
        return ret;
    }
}

Look how beautiful this structure is! I mean, we can also add a non-caching non-recursive algorithm easily:

public class LoopedFactorialImplementation implements FactorialAlgorithm
{
    @Override
    public BigInteger factorial(int n)
    {
        BigInteger ret = BigInteger.ONE;
        for (int i = 1; i <= n; ++i) ret = ret.multiply(BigInteger.valueOf(i));
        return ret;
    }
}

The weakness of this design from a Java perspective should be obvious: it does not allow us to select the algorithm we wish to use at runtime, which was a major design feature we were striving for. (I mean, after all, if our new program has different constraints, we should be able to select the specific algorithm used, right?) So clearly we need to load a configuration property and select the algorithm we want. We can do this by having our utility class look in the System properties, for example, which has the nice property that we can then, higher up, wire up to an external interface as needed. Ideally our main method would look like:

    public static void main(String[] args)
    {
        System.getProperties().setProperty("com.chaosinmotion.factorialalgorithm", "cachedAlgorithm");
        System.out.println("5! = " + FactorialUtil.factorial(5));
    }

This implies that we need a hash map of algorithms that we pick from prior to creating our singleton inside the factorial method.

So we need a factory that can generate the algorithms. We store both a map of instantiated factory singletons by name in mapping, and we store the class references in classMapping, so we don’t create the algorithm class until we actually need it. (No point in running a bunch of constructors and allocating resources we don’t use.)

/**
 * Factory class manages the factorial algorithms in our system.
 * @author wwoody
 *
 */
public class FactorialAlgorithmFactory
{
    private static HashMap<String,FactorialAlgorithm> mapping = new HashMap<String,FactorialAlgorithm>();
    private static HashMap<String,Class<? extends FactorialAlgorithm>> classMapping = new HashMap<String,Class<? extends FactorialAlgorithm>>();
    private static FactorialAlgorithm defaultAlgorithm = new CachedFactorialImplementation();
    
    /** Static initializer registers some of my known classes */
    static {
        try {
            Class.forName("com.chaosinmotion.factorial.LoopedFactorialImplementation");
            Class.forName("com.chaosinmotion.factorial.CachedFactorialImplementation");
        }
        catch (ClassNotFoundException e) {
            // Should never happen.
        }
    }
    
    /** Get the default algorithm for computing factorials */
    public static FactorialAlgorithm getDefaultAlgorithm()
    {
        if (defaultAlgorithm == null) {
            // Warning: this will fail if for whatever reason CachedFactorialImplementation
            // is not in the class path.
            defaultAlgorithm = getAlgorithm("cachedAlgorithm");
        }
        return defaultAlgorithm;
    }
    
    /** Get the factorial algorithm specified by name */
    public static FactorialAlgorithm getAlgorithm(String name)
    {
        FactorialAlgorithm f = mapping.get(name);
        if (f == null) {
            // We haven't created an instance yet. Get it from the class mapping.
            Class<? extends FactorialAlgorithm> c = classMapping.get(name);
            if (c != null) {
                // Create a new instance of the factorial algorithm specified
                try {
                    f = c.newInstance();
                    mapping.put(name, f);
                    return f;
                }
                catch (Exception e) {
                    // Log the error
                    Logger.getLogger("com.chaosinmotion.factorial").
                    warning("Unable to instantiate algorithm " + 
                            c.getCanonicalName() + ", named " + name);
                }
            }
            return getDefaultAlgorithm(); // return something.
        }
        else return f;
    }
    
    /** Register the class so we can construct a new instance if not already initialized */
    public static void registerAlgorithm(String name, Class<? extends FactorialAlgorithm> f)
    {
        classMapping.put(name, f);
    }
}

Rewriting our FactorialUtil class to use our named algorithms instead, we get:

public class FactorialUtil
{
    private static FactorialUtil singleton;
    private FactorialAlgorithm algorithm;
    
    /**
     * Default (internal) constructor constructs our default algorithm.
     */
    private FactorialUtil()
    {
        String name = System.getProperty("com.chaosinmotion.factorialalgorithm", "cachedAlgorithm");
        if (name == null) {
            algorithm = FactorialAlgorithmFactory.getDefaultAlgorithm();
        } else {
            algorithm = FactorialAlgorithmFactory.getAlgorithm(name);
        }
    }
    
    /**
     * New initializer which allows selection of the algorithm mechanism
     * @param algorithm
     */
    public FactorialUtil(FactorialAlgorithm a)
    {
        algorithm = a;
    }
    
    /**
     * Utility to create by name. Calls into FactorialAlgorithmFactory to
     * actually get the algorithm.
     * @param name
     */
    public FactorialUtil(String name)
    {
        algorithm = FactorialAlgorithmFactory.getAlgorithm(name);
    }
    
    /**
     * Default public interface for handling our factorial algorithm. Uses
     * the old standard established earlier for calling into our utility class.
     * @param n
     * @return
     */
    public static BigInteger factorial(int n)
    {
        if (singleton == null) {
            // Use default constructor which uses default algorithm
            singleton = new FactorialUtil();
        }
        return singleton.doFactorial(n);
    }

    /**
     * New mechanism which allows us to instantiate individual factorial
     * utilitiy classes and invoke customized factorial algorithms directory.
     * @param n
     * @return
     */
    private BigInteger doFactorial(int n)
    {
        // Defer to our algorithm
        return algorithm.factorial(n);
    }
}

And we have to modify our CachedFactorialImplementation and LoopedFactorialImplementation to include static class initializers which register those classes with my factory:

public class CachedFactorialImplementation implements FactorialAlgorithm
{
    static HashMap<Integer,BigInteger> cache = new HashMap<Integer,BigInteger>();
    
    static {
        FactorialAlgorithmFactory.registerAlgorithm("cachedAlgorithm", CachedFactorialImplementation.class);
    }
    
    @Override
    public BigInteger factorial(int n)
    {
        BigInteger ret;
        
        if (null != (ret = cache.get(n))) return ret;
        ret = BigInteger.valueOf(n).multiply(factorial(n-1));
        cache.put(n, ret);
        return ret;
    }
}

and

public class LoopedFactorialImplementation implements FactorialAlgorithm
{
    static {
        FactorialAlgorithmFactory.registerAlgorithm("loopedAlgorithm", LoopedFactorialImplementation.class);
    }
    @Override
    public BigInteger factorial(int n)
    {
        BigInteger ret = BigInteger.ONE;
        for (int i = 1; i <= n; ++i) ret = ret.multiply(BigInteger.valueOf(i));
        return ret;
    }
}

The beauty of this architecture, of course, is that we can even add in our own custom algorithm and plug it into the singleton underlying FactorialUtil. We simply create our new FactorialAlgorithm implementation, registering our class with the FactorialAlgorithmFactory class during static class initialization:

public class RecursiveFactorialImplementation implements FactorialAlgorithm
{
    static {
        FactorialAlgorithmFactory.registerAlgorithm("recursiveAlgorithm", RecursiveFactorialImplementation.class);
    }

    @Override
    public BigInteger factorial(int n)
    {
        if (n == 0) return BigInteger.ONE;
        return BigInteger.valueOf(n).multiply(factorial(n-1));
    }
}

and in our main routine, we make sure our class is loaded, then we set the property to specify we use our new algorithm.

    public static void main(String[] args)
    {
        try {
            Class.forName("com.chaosinmotion.factorial.RecursiveFactorialImplementation");
        }
        catch (ClassNotFoundException e) {
            // if this fails, no matter; we'll still use the default implementation.
        }
        System.getProperties().setProperty("com.chaosinmotion.factorialalgorithm", "recursiveAlgorithm");
        System.out.println("5! = " + FactorialUtil.factorial(5));
    }

No problems! And the architecture even lends itself to our plugging in more ingenious solutions, such as the algorithms documented here.

separator.png

Now I’m sure at this point there are a number of Java programmers reading this who are nodding their heads at how cool all of this mechanism is. There are a few, of course, who are about to hit the comment button and say “gosh, instead you should wire up the properties this way, or that way…” For example, I could have put the initializer for the different class mappings into a properties file that is part of the package, or as an XML file. Or perhaps I could have set the property to accept the class name explicitly; that way I could have the FactorialAlgorithmFactory do the ‘forName’ call and instantiate the class directly without having to look it up in two hash maps.

And I’m sure there are a few programmers out there taking notes or even cutting and pasting the above blocks of code. (Yes, I tested it all; it works on my system, though I don’t claim to have done the cut and paste properly in all cases.)

But here’s my point.

It’s all crap.

Every last line of it.

Sure, there are circumstances where a pluggable architecture would be desirable or even necessary–but that comes up so rarely it’s not even funny. About 99% of the time I see code like this, it’s completely and utterly useless. It’s obscuring the purpose of the code–replacing a two or three line utility (max!) with dozens or even hundreds of lines of self-important masturbatory Java bullshit. Sure, it may make you feel good–but it makes an ugly mess of it that future developers will have to clean up, or more likely just avoid like the plague.

And, worse, in the entire discussion, did you notice something?

We never handled negative numbers.

separator.png

The smart Java developer would know when to stop. Life is too short to build castles in the clouds. He’d know that a simple looped solution is more than sufficient, and of course he handles negative numbers. (Note that in our recursive solutions, a negative number results in an endless loop.)

The really smart Java developer figures out the domain of the problem set, knowing (for example) that factorial is actually a special subset of the Gamma function. Perhaps the right answer isn’t any of the code above; perhaps the right answer is using Gergo Nemes’s approximation to Stirling’s approximation to the Gamma Function:

    static double Gamma(double z)
    {
        double tmp1 = Math.sqrt(2*Math.PI/z);
        double tmp2 = z + 1.0/(12 * z - 1.0/(10*z));
        tmp2 = Math.pow(z/Math.E, z); // ooops; thanks hj
        tmp2 = Math.pow(tmp2/Math.E, z);
        return tmp1 * tmp2;
    }

But it depends on the domain: a domain we only second-guessed in all of our factory creation/algorithm interface bullshit above.

separator.png

The biggest complaint I have with many Java developers is that they develop a whole bunch of really bad habits. Specifications are unclear, or they think someday the code may need to be extended into a different direction. So they write a whole bunch of overblown architectural nonsense, sight unseen, thinking that the additional crap someday will help out and make things easier. And Java as a language lends itself to doing this very quickly and easily, so that (as the theory goes) it’s easy for us to build architectures that will someday make it easier on us in the future.

But the future never gets easier, does it?

Because a year from now they wade through all this excess baggage written at a time when they thought they understood the domain of the problem (but clearly didn’t), instead of having simple code (like the very first example of factorial above) that they can revise as needed, they wind up with the most over-engineered pile of nonsense that no-one can possibly understand.

And rather than wade into the mess to untangle the knot, or at least understand the mechanism that was put into place, they just plaster over the problem in a classical example of the lava flow anti-pattern. Perhaps they don’t understand how to create a pluggable algorithm, so instead they override the FactoryUtil class, or they simply create a new FactoryUtil class instead–and add hundreds more lines of (ill-conceived) code to plaster over the lack of understanding of the hundreds of existing lines of (ill-conceived) code.

separator.png

So please, do us all a favor: if you have the urge to add complexity because “someday we’ll need it, I just know it!”, or because “it’s not sufficiently flexible enough” or “we need reusability in our code” or (God help us!) because it’s “cool”–just go home early. Watch some cartoons. Rent Inception on DVD.

And stop creating extra work for us in the future for no good reason.

two_cents++: Apple dropping Java.

Two observations about the whole Apple deprecating Java thing:

(1) One of the biggest problems with Java on the Macintosh is that the Java AWT/Swing stuff is just bloated like crazy. I like Java Swing and the Mac implementation a lot; I have written Macintosh applications in Java that look and feel like Macintosh applications.

But practically speaking it’s just crazy bloated–and I would have been just as happy with something significantly smaller. (Do you really need pluggable LAF libraries? Has anyone you known ever successfully extended the javax.swing.plaf abstract classes to build their own custom look and feel? And would you really want to in the first place?)

The engineering cost is just not worth it.

Had Sun made portability a substantial requirement: require, for example, that the OpenSDK can be ported to a new windowing environment with less than a few months of one engineer’s time, by simplifying the native dependencies, for example, we wouldn’t be here.

(2) Of all the companies in the world right now using Java, Google is the one company that is doing the most interesting things: they’ve created their own VM for Android, they’ve created a Java to Javascript cross-compiler in GWT. They seem to be the most devoted to creating a useable subset of Java that allows you to write once (in Eclipse) and run anywhere (on mobile devices, desktop, web browsers).

If people really want Java to survive, they’d petition Google to purchase the assets behind Java. And let Google maintain Java and extend it into a full-fledged open language.

And then Apple changes the Rules. Again.

So I uploaded J2OC, and had lost interest in it. After all, who needs a second “let’s recompile Java into Objective C” in order to build iPhone and Android applications, if Apple isn’t going to allow it?

Then Apple does this: Statement by Apple on App Store REview Guidelines

In particular, we are relaxing all restrictions on the development tools used to create iOS apps, as long as the resulting apps do not download any code. This should give developers the flexibility they want, while preserving the security we need.

What I would ideally want is a Java VM kernel that can be linked into an iPhone application, one capable of running a jar file. Because ideally I’d like to write model code in Java–so I can port that model code to Android. Yet I don’t want UI bindings into the Apple API–I’d rather just build the UI twice, while the (more complicated) model code remains the same.

Thank you Apple. Maybe I’ll document J2OC better and provide some sample programs. It really is a cool little bit of technology. :-)

Something Funny Happened To Me On The Way To Release.

So I started playing with parsing Java class files, creating a cross compiler capable of converting Java class files into Objective C files. I even had a sufficient amount of Apache Harmony running so I could use a good part of the java.lang and java.util classes; roughly in parity with the GWT cross compiler that can compile Java class files into Javascript.

Then Apple dropped the “no cross compiling” bombshell.

Now, keep in mind that I’m just me, tinkering on my spare time during weekends. I don’t have the desire or the time to go up against Apple. I’d rather allow the XMLVM project (which has a well established ecosystem, or so it seems) to decide to go (or not go) against Apple’s wishes.

Then time went by, and I sort of lost interest in this thing.

So I’ve taken the liberty to post the source code here: the Java to Objective C Compiler sources, and the J2OC RTL, which contains a subset of the Apache Harmony project, and implementing the java.lang and java.util classes.

It’s been an interesting project, and hopefully in the next few weeks I’ll document how this all works–including the wierdnesses and pitfalls I came across with the Java VM to get Apache Harmony to work. (Nothing like working through a very large collection of class files to find all the fringe cases.) The output code was intended to be human readable–but it really isn’t for some expressions.

But I’ll describe that in the next few weeks.

And at some point I’ll post an example iPhone application which includes Java code.

Note that my approach was different than the XMLVM project. Instead of providing Java bindings of the iOS libraries, my intent was to only allow the compilation of a computational kernel, then have the user provide the UI elements separately for Android, the iPhone, the iPad, and whatever other target the code was to compile for.

So you won’t find a turn-key solution for recompiling Android code and have it run on the iPhone. You should really check out the XMLVM project instead.

All this code, by the way, is being published under a BSD style license: go ahead and use the code, but leave me out of it and don’t blame me if it goes haywire.

separator.png

While I don’t intend to get into the functioning of the compiler, I will give a taste of how the code works. The bulk of the .class file parser, which reads and loads the .class file data into memory, is contained in the class ClassFile in com.chaosinmotion.j2oc.vm. This class takes in its constructor an input stream opened to the first byte of a .class file, and loads the entire class file into memory.

Once read, the entire class file can be accessed using the getters associated with that class. The bulk of the code contained inside the .vm (and subpackages within .vm) are used to represent the contents of the class file. The .vm.data classes contain the various data types used to store the meta data within a class file (such as the method names, the attributes fields, and the like), and the .vm.code classes contain a code parser to convert the code within the .class files into an array of processed instructions.

Once the instructions are parsed (by the vm.code.Code class), the code in a method is represented as an array of code segments; a run of instructions that starts with an instruction first jumped into by another instruction, and terminates with either the end of the method or with a jump instruction. In other words, a CodeSeg (Code.CodeSeg class) is a section of instructions that always enters at the first instruction and executes sequentially to the last instruction in the segment. Additional information, such as the list of variables that are used when the segment is entered are noted; this is the current state of the Java operator stack as this segment is entered.

Ultimately the code parser and class file reader represents the code in a .class file in memory in an intermediate state that can then be used to write Objective C with the WriteOCMethod class (com.chaosinmotion.j2oc.oc). A class, CodeOptimize (.oc package) provides utilities that determine if code preambles must be written for memory management or for exception handling: memory management preamble does not need to be written if I never invoke another method. (This is the case for simple functions which return a field or does simple math.)

The theory is that in practice, it should be possible to replace the code writer method with a writer method capable of writing a different language, such as C++ or C.

separator.png

In the future, when I have more time, I’ll write more about the J2OC project. But for now, if there are any segments or parts you want to use or play with, be my guest.

1 2 3 6