Threads: A Clarification.

Posted on by
Reply

In a previous post I wrote:

Frankly, not only is it not thread safe, but the solution doesn’t even make any sense in a multi-threaded environment!

What are you trying to do here? Well, when someone comes along and changes the value, you’d like to tell everyone who cares what that value changed to. Simple enough, right? But in a multi-threaded environment, what does it mean when thread 1 changes the value when thread 2 also wants to change the value? Are the objects who want to be notified thread safe? What does it mean when a central value is changed twice by two threads? What is the semantics here?

I think this is worth clarifying in order to illustrate a basic point.

In the single-threaded single-process environment we’re all used to, the primary question a programmer should ask himself is “what am I trying to accomplish.” That is, if the purpose of the program is to display status in a window, then what you’re trying to accomplish is to display status in a window. Immediately from the above statement of intent, you can see that you’ll need something that gets the status you’re trying to display (a ‘CGetStatus’ class, say), you need a window (a ‘CWnd’ derived class which overrides OnPaint, say), and the usual syntactic and semantic fluff which makes a program, well, a program–such as a ‘CApp’, the code to handle the menu bar and the like. At this point you can start throwing darts at the design model board if you like: observer makes a good pattern, or some sort of timer loop or whatever. At this point even a so-so GUI programmer can visualize the program in his head and start visually laying out the resources and the class relationships.

But in a multi-threaded environment, we’ve added a new dimension: threads. And now we no longer need to just ask ourselves “what am I trying to accomplish”–but (and this is the key part) who (or rather, which thread) is trying to accomplish it?

And that’s why the observer design pattern fundamentally makes no sense in a multi-threaded environment. The observer pattern answers the question “what are we trying to accomplish” (notify listeners when a value changed), but not “who is trying to accomplish it?” So, without knowing ‘who’ (which thread), we don’t know if it’s acceptable to simply run the notification loop re-entrantly (ignoring threads entirely), or if we need to shunt the notification to a Swing UI thread (as was done in my previous example) or create a background thread or threads which handle the notifications.

Until we ask “who is trying to accomplish it”, then shoring up a design pattern (such as the observer pattern) to be “multi-thread safe” is sort of like (well, it actually is) trying to write software without knowing what we’re trying to write.

Pruning Non-Determinacy verses Thinking Ahead.

Posted on by
Reply

Oh, look; now we have multiple cores inside of modern day computers. Today you can get a laptop with two processor cores in one chip for cheap, and soon Apple will be releasing a computer with 8 processor cores spread across two microprocessor chips. Noticing that the workaround being used today to allow Moore’s Law to get around physical reality is to stuff more processor cores onto a chip–which requires multithreading and multitasking to take full advantage of it–several articles have come across which attempt to illustrate the pitfalls of multithreaded programming.

Except, well, do they?

Exhibit A: The Problem with Threads, which attempts to illustrate the problem with threads by discussing the Observer Pattern:

Consider the observer pattern,5 a very simple and widely used design pattern. Figure 1 shows a Java implementation valid for a single thread. This shows two methods from a class where an invocation of the setValue() method triggers notification of the new value by calling the valueChanged() method of any objects that have been registered by a call to addListener().

The code in Figure 1 is not thread safe, however. That is, if multiple threads can call setValue() or addListener(), the listeners list could be modified while the iterator is iterating through the list, triggering an exception that will likely terminate the program.

To reiterate, because I don’t feel like copying his code across, the observer pattern example given is simple: someone calls “setValue”, and this sets the value for the object as well as tells everyone else about the value that was just set.

Then we go on for several paragraphs talking about why the code is not thread safe, to which all I can really add here is, well, no fucking shit, Sherlock, it isn’t thread safe.

Frankly, not only is it not thread safe, but the solution doesn’t even make any sense in a multi-threaded environment!

What are you trying to do here? Well, when someone comes along and changes the value, you’d like to tell everyone who cares what that value changed to. Simple enough, right? But in a multi-threaded environment, what does it mean when thread 1 changes the value when thread 2 also wants to change the value? Are the objects who want to be notified thread safe? What does it mean when a central value is changed twice by two threads? What is the semantics here?

In a multi-threaded environment, assuming the Observer Pattern should somehow be made to work overlooks a rather obvious question: what does it mean for two threads to change the same value? And the corollary: when we are notified do we just need to be told that something changed so we can refresh something–like a UI display widget–and so we just need to know the last time it changed? Or do we need to know every value transition in the order in which they occurred, because we’re driving a state machine?

In other words, by focusing upon the design model to proclaim that Threading is hard, we’ve avoided the question of what the hell it is we’re doing. And if we could answer the question “what are we trying to accomplish here,” perhaps we could then solve the problem by using an appropriate design pattern rather than trying to extend a design pattern where it doesn’t belong.

So, say instead the problem is you want to just be notified the last time something changed, so you can update a user interface element. We know that Swing runs everything within its own UI thread–so it means our setValue routine will need to use Swing method EventQueue.invokeLater() on a Runnable object which then sends out the notification to our listeners that the value has changed. Then, when the value has changed, we can determine if we’ve inserted an event into the Swing event queue and see if it has fired yet. If it hasn’t, we’re done. If it has, create and insert a new one.

The implementation is straight forward:

public class ValueHolder
{
    private List listeners = new LinkedList();
    private int value;
    private boolean fWaitToFire = false;
    
    public interface Listener 
    {
        public void valueChanged(int newValue);
    }
    
    private class FireListeners implements Runnable
    {
        private List copyOfListeners;

        FireListeners()
        {
            copyOfListeners = new LinkedList(listeners);
        }
        public void run()
        {
            fireListeners(copyOfListeners);
        }
    }
    
    public synchronized void addListener(Listener listener)
    {
        listeners.add(listener);
    }
    
    public synchronized void setValue(int newValue)
    {
        value = newValue;
        if (!fWaitToFire) {
            EventQueue.invokeLater(new FireListeners());
            fWaitToFire = true;
        }
    }
    
    private void fireListeners(List list)
    {
        int localValue;
        
        synchronized(this) {
            /* Grab value and reset wait to fire. If someone else changes me while */
            /* I'm iterating the values, that's okay; I'll just get fired again later */
            /* Since we're invoked from FireListeners internal class, we're already */
            /* in the main Swing thread, so there are no multi-threaded issues with */
            /* the list iterator here. */
            localValue = value;
            fWaitToFire = false;
        }
        
        Iterator it = list.iterator();
        while (it.hasNext()) {
            ((Listener)it.next()).valueChanged(localValue);
        }
    }
}

Notice the two principles I’ve used here: first, keep the amount of code in the synchronized block as short as possible. That way, the size of the non-syncronous section is kept to a minimum, and parallelism is maximized. Second, I’ve used a monitor flag, ‘fWaitToFire’, which is used to determine if we already have an object queued up in the Swing thread that hasn’t been fired yet. This permits me to minimize the number of times we carry out the expensive operation of creating a copy of my listener list. Since we’re only interested in knowing when the value changed, but not being notified every time the value changed, this may only notify us once if the value is changed twice, right in a row.

Suppose, however, that we need to be notified every time the value has changed, and in the order the value has changed to. Then we need to implement a thread queue: an object which doesn’t just store the current value, but a queue of all of the values that were held by this object. A thread then owned by that object runs in the background, peeling off entries in the queue and sending them out to the listener in order.

Because it’s late, I will leave the implementation of a thread queue to the reader.

There is one thing in this article I do agree with wholeheartedly:

I conjecture that most multithreaded general-purpose applications are so full of concurrency bugs that—as multicore architectures become commonplace—these bugs will begin to show up as system failures.

Absolutely.

And if the current thinking shown in the above linked article prevails–of applying inappropriate design models to a multi-threaded environment without giving a single thought as to what the original problem was–then we’re not going to find any good solutions anytime soon.

Because ultimately the goal seems to be tackling the wrong problem. The problem is not

…[adding] mechanisms [to] enrich the programmer’s toolkit for pruning nondeterminacy.

No, the goal should be to think about what the hell it is you’re trying to accomplish in the first place, and using the correct design model so as not to create non-determinacy in the first place.

On that note I’ll leave you with two thoughts. First, we have the article Thread pools and work queues, of which my outline of an alternate mechanism above for sending out every value change as it happens really is just a work queue with a thread pool size of 1 thread.

And the second is not to fear thread deadlocks–just remember the following rule: if you always lock in order and unlock in reverse order, you’ll be fine. That is, if you have three locks, numbered 1 through 3, so long as you always write your code so that lock A locks before lock B if n(A) < n(B), then you will never deadlock. That’s because deadlocks occur if thread A locks 1,2 and thread B tries to lock 2,1: thread A is waiting for 1 to come free while thread B is waiting for 2 to become free. But if you always lock in order–then you will never have code that deadlocks because you will never have the code in thread B: it locks out of order.

Sometimes that can be damned hard: it can involve rethinking how some code is written, locking locks early, for example, or even adding what seems like unnecessary thread work queues or other stuff. But if you follow the rule above you will never deadlock.

And provably correct code wins over “pruning nondeterminacy” every day of the week and twice on Sundays.

With this in mind, you can imagine the constant mental anguish that was going on inside of my head as I read the following article, submitted into evidence as Exhibit B: Barrier. I mean–deliberately trying to create non-determinacy in order to demonstrate pruning techniques? Why not just give some thought as to appropriate multi-threaded design models and techniques for proper design?

New section in Wiki

Posted on by
Reply

I’ve added a new section to the Wiki to store articles I put together to track how to do something. This new section, called “technical notes” will contain notes about how to string a technology together to make it work.

The first article is an overview of the work I’ve done so far to understand Java’s Drag and Drop.

There was a time when I loved Apple’s documentation.

Posted on by
Reply

But since the NeXT folks showed up, Apple’s documentation has gotten remarkably worse–and in the past few years there have been no attempts to fix the problem.

Okay, here’s a question for anyone who knows Cocoa: what is the lifecycle of a NSWindow? I mean, sure, you can create a NIB representing the contents and it just “magically” appears–but who is the guy behind the curtain? How does the “magic” work? And how is it supposed to work?

There was a time when Apple’s documentation would give an introductory couple of pages about each logical unit of execution–each “toolbox manager”–which talked in some depth about how something would occur, and which routines would be called to make it happen. If there was a resource-driven initialization routine, the documentation would explain what non-resource driven routines were being invoked and how things were being wired up–so that, when we did use the resource-driven routines, there was a certain sort of “sense” to it all. We were not writing to a black box: we had a mental model of how things worked under the hood, even if some of that mental model was not completely accurate. After all, we may not have carburators anymore–but something mixes the air and vaporized fuel together to explode in the cylinder to make the engine turn over.

And my biggest obsticle to learning NeXTStep, er, ah, Cocoa, is that I don’t have the 10 years of history watching the system evolve to understand what it evolved from–as I do with the Win32 API. So I don’t have a mental model as to how it all hangs together–and Apple’s current sorry state of documentat sure the hell isn’t helping.

Some parts of the documentation do help. The Event Handling Overview sure helps. But figuring out how a Window goes from an idea to something I’m interacting with on screen–well, it’s not like the the NSWindow class overview is of any help. Two hundred plus methods, and the documentation sucks even worse than a JavaDoc dump–if that were even possible. Two hundred plus methods, and two fucking paragraphs of introductory material which state the obvious–and nothing else. Nothing on how Windows get built–nor even a mention if it is even possible to build an NSWindow without using a NIB.

*sigh*

Somehow Apple assumes from this I’m supposed to gain some sort of understanding. Yeah, right. An alphabetical dump of 200 methods with a rough grouping by “function” doesn’t exactly constitute transmitting a fundamental understanding.

Java Swing Stupidity, pt. 2

Posted on by
4

How the hell can Sun take something complicated and make it overengineered and overly complicated to boot?

Well, if the functionality is ‘drag and drop’, the answer is apparently easy.

Now, in the ideal world, drag and drop would be handled as follows: your custom drag component would call a magic “is drag initiated” when a MouseListener.mousePressed() method is called, which would take control of the mouse click and automagically determine if drag and drop was initiated. If it is initiated, the magic routine would return true, giving you the opportunity to build your drag operation and call some magic ‘startDrag’ routine. If the magic routine returned false, then you know you should handle the mousePressed routine as usual.

Drop would be similarly easy: you would register and implement a ‘DropTargetListener’ interface, which would give you the opportunity to say “yes, I’ll accept that drop” and handle mouse events and the drop target.

A third class would implement the ‘Transferable’ interface which would represent the thing you’re dragging.

Is Java Swing’s drag and drop this easy? That is, do they do the hard work so that, as someone who wants to implement a custom JComponent which accepts drag and drop, it’s fairly easy?

Uh, no.

No, instead we wind up with this whole dazzling array of stupidity on the part of Sun which, after spending a few hours deciphering some excellent articles, eventually leads you to something that resembles drag and drop nerdvana. (*sigh*)

What’s wrong with Drag and Drop?

Okay, to start off with, apparently Java didn’t decide to create an insulating drag & drop layer for Swing above AWT. So we need to use AWT, which scatters drag and drop functionality across two packages: java.awt.dnd (not Dungeons and Dragons), and java.awt.datatransfer. And our first step in creating a drag and drop tool is handling dragging.

With dragging, we need to do the following: (a) determine if our mouse event is a drag event, then, if true, (b) create an object we transfer, and (c) start dragging. So in my search I came across this thing called DragGestureRecognizer, and its subclass, MouseDragGestureRecognizer.

And immediately we encounter a violation of the first rule of making an application framework–a violation which is very common with intermediate-level developers: they engineered it more complicated than it needed to be. Why the fuck have an abstract drag gesture recognizer engine which is then enstantiated with a concrete class? Does Sun think that at some time in the future drag recognition is going to be triggered by a network event? Do they anticipate a TCP/IP packet which starts a drag event?

Drag and drop is not a general-purpose user interface thingy; it is specifically an action that is triggered by a mouse gesture (or the equivalent of a mouse gesture). Conceptually if you press at a given location with your mouse (finger/tablet pen) and hold for a moment, you pick something up, and then you drag it somewhere else and you drop it. You don’t trigger this sequence through keyboard actions (unless your keyboard is emulating a mouse), nor do you trigger this sequence through a TCP/IP network connection or by manipulating the knobs on the front of the computer.

So the first rule of frameworks is violated: don’t make it overly generalized unless it needs to be.

So, now that we know that we somehow need this gesture recognizer to, well, recognize a gesture, how do we plug this in?

Not into mousePressed, we don’t. Instead, when we construct our JComponent, we have to initialize the DragGestureRecognizer for our component and pass a reference to our component to this DragGestureRecognizer, which listens to mouse events in the background. Well, that’s convenient: instead of adding like three likes of code to our mousePressed routine, we add three lines of code to our constructor and like magic, our mouse presses are automatically translated into drag events.

Except now we have a problem. Because this effectively happens asynchronously to our mouse down/mouse move events (because we keep receiving these events as the drag gesture recognizer is figuring out if this is a drag event), we have the odd problem that we continue receiving mouse events unaware or uncertain if this will be handled as a drag event. So we go along, implementing a ‘rectangle select’ operation–then, all of a sudden, our rectangle select event turns into a drag event.

The reason why it is preferable to handle triggering drags on mouse down is that we know right away if the event is a drag and drop event or not. Generally the rule for drag and drop is if the mouse stays within a small (5 pixel) rectangle for more than 1/4th of a second, the user is probably ‘grabbing’ the object to drag–so it’s not like that quarter second delay is going to be all that noticeable. Further, we can decide prior to asking if it is a drag event if the location where we are clicked is eligable for dragging in the first place.

But now we have this asynchronous operation taking place behind our back–a monster we have to feed. And while the solution is simple: on our click event decide if we are eligable for a drag event, and if we are, bail and allow the background drag code then handle things–this has two problems. First, it scatters the logic for handling drag and drop across multiple locations rather than keeping them in one spot–which makes maintanance a royal pain in the ass. Second, it means that if we select an object eligable for drag and drop, we have no way to implement secondary behavior if the user clicks and drags in a way which doesn’t fit in our drag and drop sematics.

Bah.

No problem, I suppose: I still have to decide if the click is eligable for drag and drop, and if it is, set a variable with a reference to the current mouse event we’re doing drag and drop with–because we need that event to set up drag and drop. By placing the drag and drop operation as an asynchronous operation, however, we suddenly find drag and drop going from “call this function and see if it’s drag and drop, then set up the drag object and run drag and drop” to implementing three separate interfaces and creating two classes.

I suppose two of those interfaces make a certain sort of sense, at least in the context where we have this background class “helping us”: if we’ve got this “helper class” helping us, we need an interface to tell the “helper” what it should do. And that’s the role of DragGestureListener: to listen for a drag gesture triggered event, and decide if it’s a valid drag operation, and trigger the drag if it is one. And the second interface, the Transferable, is something we’d need anyway: it’s the data being transfered.

The interface DragSupport, however, doesn’t seem to serve any purpose I can think of–except it does allow us to work around a bug in MacOS X’s implementation of Drag and Drop which doesn’t reset the mouse cursor when drag and drop ends. (*sigh*)

So, instead of overriding mousePressed, (a) determine if this is a drag event by calling some routine, (b) setting up drag, and (c) calling a routine to handle dragging, instead we (a) get an instance to the DragSource object, (b) create a new DragGestureRecognizer with our (c) interior class implementing the DragGestureListener interface and the DragSourceListener interface, which (of course) (d) fixes the MacOS X Java bug by setting the cursor in dragExit. Then we override mousePressed, (e) calculating if this is a drag event (which we’d have to do anyway), and (f) if so, setting some variable which our DragGestureListener can look at to see if it should then actually drag. In our DragGestureListener, we then (g) set up the drag and (h) call a routine to handle dragging.

Because 9 steps is easier than 3, natch.

Dropping

Now dropping should be an equally easy operation, and for the most part it is: you have a DropTargetListener which actually listens for drop events. And of course you still need to tell some global mechanism that your control accepts drop events: this appears to be the role of the DropTarget class. So we create a new DropTarget class, give it a reference to our component, and a reference to our inner class which implements the DropTargetListener class–and away we go.

So dropping isn’t as painful as dragging, I suppose.

Now if someone could tell me why Java took something that should have been two calls and turned it into two interfaces and two classes too many, I’d be greatful.

Web Sites are like an Iceburg

Posted on by
Reply

Any web site–including e-commerce web sites–are like an iceburg: the user interface the customer interacts with it is the 10% that is above water. But 90% of the site is below water, in the form of maintanance utilities and interfaces which allow products to be uploaded, described and managed, to allow orders to be downloaded and processed and to otherwise manage the web site.

Why is it that 90% is done all on the web site as well?

I wonder why we don’t build such web sites by creating a simplified XML-RPC interface for obtaining back-end information, then creating stand-alone applications in something like Java which can process the back-end information? Yes, it adds complexity: now you need programmers proficient in XML-RPC (or whatever home-grown XML processing language you use), as well as programmers proficient in desktop development as well as in web site development.

But the upside comes from testing: once you have broken your web application into a front-end UI that is on a series of web servers and separate (and potentially multiple) back-end applications which interact with the web site database, you can test each of these separate stand-alone management programs and deploy them independent of the main web site. You can also develop them and test them separately from each other, which makes the risk of uploading updates to the production server smaller.

Further, the upside is in reducing the amount of server space you need for your web site. Since the logic of your management programs are running on the desktop and not on your servers, the overall footprint of your server has been lowered.

Of course this all assumes that you provide excellent access control via your XML-RPC interface. But you had to do that anyway, right?

And if your company does its job correctly, the hard part of developing the interface and access control tools are developed by someone smart, and specialists in Java Swing can toss the UI together in Eclipse or NetBeans. And if your XML/RPC interface is written in a simplified fashion, you can even deploy a dev server whose sole purpose is to validate requests to help developers debug things.

The Shaking Of The Voodoo Stick.

Posted on by
Reply

*sigh*

Why is it so much coding resembles more the shaking of a voodoo stick (that is, the random trial and error by someone who appears not to have a freakin’ clue as to what’s going on) than it does the studied fix of someone who sees a problem, studies it to find out what is going on, then fixes the problem?

Perhaps it has something to do with the fact that most developers don’t know what they’re doing, especially when it comes to someone else’s code.

Many years ago I obtained a copy of “Inside Macintosh”, the document which outlines the Macintosh development API. Except back then, it was called a “toolbox”–the term “API” hadn’t been invented yet. (Yes, I’m dating myself.) One of the most remarkable things about the original documentation–something which most modern documentation fails to emulate (and which, in my opinion is a major contributor to ‘voodoo stick shaking’)–is the design and layout of each chapter.

Each chapter of Inside Macintosh documented one “manager”, a conseptual unit of code. For example, there would be a separate chapter for the “font manager”, another for the “event manager” and so forth. While the details of the specific managers nowadays would be different–we’ve learned so much since this document was published in June of 1983–it is the idea that we can decompose a program into conseptual units and what those units are: single conseptual units we initialize, manipulate, interact with, and shut down, which is the important part.

But what was most remarkable was how each chapter was organized.

The first part of the chapter was an “About”: “About the Event Manager”, “About the Font Manager”. This would be a two to 20 page summary of why the manager was there–what it did, and why, from a high-level point of view. The chapter on QuickDraw (the Macintosh Carbon API for drawing information on the screen) was quite extensive as it gave a detailed outline of how drawing occured, and what you could draw. This summary would then be followed by a number of sections outlining some of the key concepts, such as a section on event masks or a section on font kerning.

The second part of the chapter consisted of a “Using” chapter: “Using the Event Manager”, “Using the Font Manager”, “Using Quickdraw”, which itself would be organized into “Initializing”, “Using” (with appropriate sections) and “Terminating”. Some chapters would simply describe how to do something, some would contain sample code. But in all cases they indicated the name of the function that would need to be called. So, for example, from the “Event Manager” chapter:

Before using the Event Manager, you should call the Window Manager procedure InitWindows: arts of the Event Manager rely upon the Window Manager’s data structures and will not work properly unless those structures have been properly initialized. It’s also usually a good idea to call FlushEvents(everyEvent,0), to empty the event queue of any stray events left over from before your program was started up (such as keystrokes typed to the Finder.)

As noted earlier, most application prorams are event-driven. Such programs typically have a main loop that repeatedly calls GetNextEvent to retrieve the next available event, then use a CASE statement to decide what type of event it is and take whatever action is appropriate.

And so forth.

Aside from the sheer primitivism of the actual API being discussed, what is most striking is that the discussion tells you what API functions to use and why. This clearness means that you don’t have to shake the voodoo stick: you know that in your startup code you need to call FlushEvents–and more importantly, why you should.

The third section of each chapter would then consist of the usual listing of APIs that we see in things like JavaDoc output: a list of functions grouped by the type of stuff they do–so, for example, posting and removing events are grouped together and reading the mouse routines are grouped together.

Granted, today APIs have gotten expoentially more complex: after all, its far easier to shovel code than it is to think about and write good software. But even so, there is no reason why today’s APIs couldn’t be documented using the same formula: (1) What is it? (2) How do I use it? (3) The details.

All too often documentation (especially internal documentation) fails to provide the (1) and the (2)–ephemeral properties that only live inside the mind of the developer who figured out how to do it, and often never communicated to the guy stuck using it or debugging it, and instead go for (3)–and worse, go for (3) in the context of something like JavaDoc, which is a very nicely organized list of routines with no frakking explanation as to why I should care.

And so, lost in a maze of very poor documentation–documentation which could be quite good if only we’d add a page on what it is, and five pages on how to use it–programmers today have no choice than to either reconstruct the “what” and “how” themselves through wasting countless hours digging through the code, or (if the time pressure is on) shaking the voodoo stick, slaughtering a pig, and praying to the Gods of Code that what they stuck in causes the bug to go away.