Not in fact any relation to the famous large Greek meal of the same name.

Monday, 31 May 2010

Portability, Or Cut-And-Paste?

Suppose you’ve got some functionality with two completely different implementations on different platforms:

// Event.h v1
class Event // Win32 waitable event
{

  void *m_hEvent;
public:
  Event() : m_hEvent(::CreateEvent()) {}

  void Wake();
  ...
};
versus
// Event.h v2
class Event // Posix waitable event
{
  int m_fd[2];
public:
  Event() { ::pipe(m_fd); } // or maybe eventfd on Linux
  void Wake();
  ...
};

And, by the way, if you’ve got a class where only some of the implementation is different on different platforms, you’ve first got an opportunity for refactoring to extract that part of the implementation as a self-contained class. Portability and maintainability are aided if each of your classes is either wholly portable, or wholly platform-specific. But as it is, you’ve got a more immediate problem, which is that there’s two classes both called Event, and any translation unit that includes both headers isn’t going to compile. Here’s one solution:

// Event.h v3
#ifdef WIN32
class Event
{
  ...
};
#else
class Event
{
  ...
};
#endif
This, plus its close relative
// Event.h v4
#ifdef WIN32
#include "win32/Event.h"
#else
#include "posix/Event.h"
#endif
could well be the most commonly-encountered solutions to this problem in real-world code. But they’re not without problems. One problem is with code analysis tools, including such things as production of automated documentation with Doxygen. Really you want such tools to analyse your whole codebase, and if they do they’ll get hopelessly confused with the two classes both called Event. (You can set up preprocessor defines in Doxygen so that it only sees one Event class -- but that only means the other doesn’t get documented, or that you have two entire sets of Doxygen output for the two platforms, neither of which sounds desirable.)

To solve this problem, you’ve going to have to give the classes different names:

// Event.h v5
class Win32Event
{
  ...
};

class PosixEvent
{
  ...
};

No, no, no, this is C++, there’s a built-in language facility especially for namespaces, you don’t have to reinvent it in the class names themselves:

// Event.h v6
namespace win32 {
class Event
{
  ...
};
} // namespace win32

namespace posix {
class Event
{
  ...
};
} // namespace posix

(Why the comments on the “}” end-of-namespace lines? Because the error messages you get from C++ when you accidentally miss out an end-of-namespace brace are often insane and impenetrable, especially if you do it in a header file, and it’s convenient to be able to grep namespace *.h *.cpp and check whether braces appear in matching pairs in the grep output.)

Notice that both declarations are parsed on every compilation on either platform. This might require you to move some method definitions (those calling such unportable APIs as ::CreateEvent and ::pipe) into a cpp file. But even compiling the other platform’s declarations helps ensure that changes on one platform won’t break the other platform without somebody noticing. And a Doxygen run, or other automated code analysis, will at least get to see both sets of declarations even if not both sets of definitions.

While going down the route of helping platform developers avoid breaking other platforms, it’s been conspicuous so far that there’s nothing in Event.h making sure that the Win32 and Posix implementations keep the same API. Without such enforced consistency, there’s a risk of client code unwittingly using non-portable APIs. The way to enforce the consistency, of course, is to derive from an abstract base class containing the API:

// Event.h v7
class EventAPI {
public:
  virtual ~EventAPI() {}
  virtual void Wake() = 0;
  ...
};

namespace win32 {
class Event: public EventAPI
{
  ...
};
} // namespace win32

namespace posix {
class Event: public EventAPI
{
  ...
};
} // namespace posix

This is, after all, exactly the sort of thing you’d do if you had two different sorts of Event that were both used in the same build of the program. Really the fact that no one individual binary will contain instances of both classes, doesn’t mean that the quest for well-factored design should be thrown out of the window and replaced with cut-and-paste.

Now, though, all the method calls have become virtual function calls. For most of any given codebase, that won’t matter, but there’ll always be hot paths and/or embedded systems where it does, and indeed an event class might quite plausibly be on such a critical path. And after all, compiling the client code itself provides a, potentially large, body of checks that the API has remained consistent over time. It’s reasonable to adopt the position that using design techniques to discourage unthinkingly changing core APIs in a non-portable way isn’t actually necessary, so long as the compilation-failure results of such a change are always speedily available from all target platforms, such as from an automated-build or continuous-integration system.

If, conversely, your class is only used in situations where nobody’s really counting individual machine cycles, you could hide the implementations altogether, at the cost of ruling out stack objects and member variables of type Event and requiring a heap (new) allocation every time one is created:

// Event.h v8
class Event {
public:
  virtual ~Event() {}
  virtual void Wake() = 0;
  ...
};

std::auto_ptr<Event> CreateEvent();

// Event.cpp
std::auto_ptr<Event> CreateEvent()
{
  ... return whichever derived class of Event is appropriate ...
}

But for now let’s assume you can’t really conceal the two platform-specific declarations, and go back to Event.h version 6 or version 7. Let’s look at how client code gets to pick which of the two implementations it uses. For a start, not like this:

class NominallyPortableDomainAbstraction
{
#ifdef WIN32
  win32::Event m_event;
#else
  posix::Event m_event;
#endif
  ...
  m_event.Wake();
  ...
};

Flouting our design rule that each class is either wholly portable or wholly platform-specific, this sort of thing couples portability decisions into all client code, which is very undesirable. This is much better:

// Event.h v9
... as before in v6 or v7

#ifdef WIN32
typedef win32::Event Event;
#else
typedef posix::Event Event;
#endif

// Client code
class NominallyPortableDomainAbstraction
{
  Event m_event;
  ...
  m_event.Wake();
  ...
};

It’s still not great, though: if there are lots of classes involved, lots of code ends up inside the #ifdefs. How can we minimise the amount of #ifdef’d code? Well, here’s one way:

// Event.h v10
... as before in v6 or v7

#ifdef WIN32
using namespace win32:
#else
using namespace posix;
#endif

But this, of course, introduces everything from those namespaces into the surrounding namespace. Not only is that namespace pollution, it’s potentially misleading for client code, as there may be Win32-specific classes or functions -- ones with no Posix equivalent, for use in Win32 situations only -- which are now accessible in portable code without the telltale win32:: prefix. (And, of course, vice versa for Posix-specific ones.) Really we want to explicitly enumerate which classes and APIs are intended to be portable. So we can do this:

// Event.h v11
... as before in v6 or v7

#ifdef WIN32
namespace platform = win32;
#else
namespace platform = posix;
#endif

using platform::Event;
using platform::PollThread;
...

The intention is that the using declarations list precisely those facilities which are available on all platforms, but with differing implementations on each. Non-portable classes or functions can stay in namespace win32 (or namespace posix) so that any use of them in client code immediately flags that code up as itself non-portable.

There is one problem with this neat solution, though: it doesn’t actually compile. Or rather, once you do the same thing in several different header files, you’ll find that multiple namespace X = Y; statements for the same namespace X aren’t allowed, even if Y is the same each time. So, sadly, you have to come up with a different name for “platform” each time (or centralise the using in one header file, causing potentially-undesirable widespread dependency on that file):

// Event.h v12
... as before in v6 or v7

#ifdef WIN32
namespace eventimpl = win32;
#else
namespace eventimpl = posix;
#endif

using eventimpl::Event;
using eventimpl::PollThread;
...

There’s only one remaining wrinkle, which is that you can’t forward-declare a class-name if that name only exists due to using. So if there are header files that traffic in Event* or Event& and could otherwise be satisfied with a forward declaration class Event; and avoid including Event.h, then you can’t use Event.h version 12. (Version 9 is also out, as you can’t forward-declare typedefs either.) The best you can do is probably this:

// Event.h v13
... as before in v6 or v7

#ifdef WIN32
namespace eventimpl = win32;
#else
namespace eventimpl = posix;
#endif

class Event: public eventimpl::Event {};
class PollThread: public eventimpl::PollThread {};
...

although naturally that only works as-written if the eventimpl base classes don’t have constructors other than the default constructor; if they did, you’d have to write forwarding constructors in each derived class, making the code a lot less neat.

Wednesday, 26 May 2010

Think Same: Mapping An Apple Keyboard Like It’s A Normal One

The aluminium “laptop-style” Apple keyboards are really nice: quick and easy to type on. I’ve got one on my main Linux machine. But they’re mapped oddly (or at least the UK one is): backtick is next to Z, and backslash next to Enter. As I’m usually watching the screen and not the keyboard while typing, the fact that these think-different mappings are borne out by the printing on the keycaps doesn’t help.

So I needed to swap them back again. And, X being the stovepipe it is, I needed to do it twice, once for inside X (including Gnome and KDE) and once for the console.

X was actually easier: I added this to ~/.xinitrc:

# Apple silver keyboard has these keycodes swapped
xmodmap -e "keycode 94 = grave notsign grave notsign bar bar"
xmodmap -e "keycode 49 = backslash bar backslash bar bar brokenbar"

For console use there doesn’t seem to be a similar way of modifying just certain keycodes, so you end up needing to make a whole new keymap:

dumpkeys > keymap.txt
(edit keymap.txt)
loadkeys < keymap.txt

Here’s the diff I had to apply to the standard UK map to get the Apple keyboard working the way my fingers expect:

--- std_keymap  2010-03-12 13:49:34.000000000 +0000
+++ silverapple.keymap  2010-03-12 13:50:39.000000000 +0000
@@ -93,9 +93,9 @@
        shift   control keycode  40 = nul             
        alt     keycode  40 = Meta_apostrophe 
        shift   alt     keycode  40 = Meta_at         
-keycode  41 = grave            notsign          bar              nul             
-       alt     keycode  41 = Meta_grave      
-       control alt     keycode  41 = Meta_nul        
+keycode  86 = grave            notsign          bar              nul             
+       alt     keycode  86 = Meta_grave      
+       control alt     keycode  86 = Meta_nul        
 keycode  42 = Shift           
 keycode  43 = numbersign       asciitilde      
        control keycode  43 = Control_backslash
@@ -201,10 +201,10 @@
        control alt     keycode  83 = Boot            
 keycode  84 = Last_Console    
 keycode  85 =
-keycode  86 = backslash        bar              bar              Control_backslash
-       alt     keycode  86 = Meta_backslash  
-       shift   alt     keycode  86 = Meta_bar        
-       control alt     keycode  86 = Meta_Control_backslash
+keycode  41 = backslash        bar              bar              Control_backslash
+       alt     keycode  41 = Meta_backslash  
+       shift   alt     keycode  41 = Meta_bar        
+       control alt     keycode  41 = Meta_Control_backslash
 keycode  87 = F11              F23              Console_23       F35             
        alt     keycode  87 = Console_11      
        control alt     keycode  87 = Console_11

And to get this loaded on every boot, I stuck it in /etc/rc.local:

# Apple keyboards start up in "F-keys are magic" mode; this puts them in
# "F-keys are F-keys" mode
echo 2 > /sys/module/hid_apple/parameters/fnmode

# Also they have the backslash and backtick keys swapped
loadkeys < /etc/silverapple.keymap

Oh, right, yes, the function keys: they think different too, or at least they default to think-different mode on power-up. To get them thinking same, you need to have the Linux hid_apple module loaded, and to set its “fnmode” parameter as above. (Other systems may use other ways of setting module parameters.)

If you’ve found this and want to check that your fingers are mapped the same way mine are, this is the list of keys that, with the setup above, do not generate the symbol printed on the keycap:

labelledgenerates
§` (backtick)
± (shift-§)¬ (notsign)
@ (shift-2)"
" (shift-')@
\#
| (shift-\)~
` (backtick)\
~ (shift-`)|

Overall you lose the ability to type “§” and “±”, and gain “¬” (meh) and, rather surprisingly, the hash character “#”, which isn’t marked anywhere on the Apple keyboard.

Sunday, 31 January 2010

How Facebook Wasted An Hour And A Half Of My Life

Now it should be admitted up-front that in fact, taken as a whole, Facebook has in fact wasted far more than an hour and a half of my life. But all the other hours and halves, I at least felt it was my choice to waste them. This time, however, it was definitely Facebook’s choice instead — or Apple’s.

The problem started when Facebook for Iphone refused to do anything, showing only the message “This version of the Facebook application is no longer supported. Please upgrade to version 3.0.”

Despite having always thought that the whole point of web applications, or websites in general, is that you design them carefully-enough to start with that you can support old URLs or clients in the field indefinitely — you can’t, after all, reach out and rewrite everyone in the world’s bookmark files if you want to change a URL — I consoled myself that at least updates to Facebook for Iphone are free, so went off to the Iphone App Store to download the newer version. But that failed too: apparently version 3.0 of Facebook for Iphone required at least Iphone OS 3.0, and mine was still on 2.2.

Upgrading the OS on a jailbroken Iphone can be stressful, but I thought that, as Facebook was pretty much the only Iphone application I actually used, even the worse-case scenario of bricking the phone and going back to the Nokia 8890 wouldn’t lose me that much. It turns out that the procedure for upgrading a jailbroken Iphone to OS 3.1.2 is as follows:

  • Find out how. I’m not even including the finding in the hour and a half.
  • Reboot, because it only works from MacOS.
  • Download Pwnagetool, BL-3.9, and the IPSW. (I always think that the file icon for IPSW files ought to be a blue scarf, but it isn’t.)
  • Try and download BL-4.6, but the link doesn’t work.
  • Go and fetch BL-4.6 on a USB stick from the Windows laptop you last did an Iphone upgrade from. (This is actually an improvement over the previous process, which only lets you know you’ll need the BL files halfway through the upgrade itself.)
  • Run Pwnagetool, which immediately stops because you need at least Itunes 8 for the “restore from specific IPSW” feature, and you only have Itunes 7.
  • In Itunes, run “Check for updates”, which runs the system Software Updater program, which offers loads of nonsense. Untick everything except Itunes, and download and install it.
  • Run Pwnagetool again, which now does everything it needs to and creates the custom IPSW.
  • Put the Iphone into recovery mode.
  • Run Itunes, which refuses to start because it needs Quicktime 7.5.5 or later.
  • Go and find Software Updater (it’s in System Preferences) and run it again. Untick everything except Quicktime, and download and install it.
  • Reboot, because the Quicktime installer demands it.
  • Put the Iphone into recovery mode again because it’s fallen out of it during the reboot.
  • Re-run Itunes, and have it tell you “Itunes could not contact the Iphone software update server because you are not connected to the internet.”
  • Click on “More information” about this “no internet” error, and watch it open a web page in Firefox to tell you about it.
  • Start to wonder whether Apple are just deliberately messing with your head in order to scold you for jailbreaking their phone.
  • Unplug the network cable from the Mac and plug it directly into the router, bypassing the HTTP proxy.
  • Reconfigure both MacOS and Firefox not to use the proxy.
  • Quit and re-run Itunes, because there’s no obvious way of telling it to rescan for devices.
  • Actually install the upgrade, which takes ages to “prepare”, much of which time you spend eyeing the old Nokia 8890 which never caused you any of these problems.
  • Once the Iphone restarts, observe with relief the little magnifying-glass icon that 2.2 didn’t have, thus providing evidence that the upgrade actually did something. Also notice that it’s rearranged all your icons; arrange them back the way you like.
  • Install the Facebook application from the Iphone App Store.
  • Open “Contacts” and realise that in fact the upgrade has wiped all your user data.
  • Notice with relief that Itunes is now asking you whether to restore the Iphone from a backup.
  • Notice with alarm that the backup in question is from 2008.
  • Restore from the backup anyway because it’s got to be better than nothing.
  • Rearrange all your icons back the way you like them again.
  • Reinstall the Facebook application from the Iphone App Store, because the restore restored the old version.
  • Unplug the network cable again and plug the Mac in back behind the firewall where it belongs.
  • Reboot back into Linux.
  • Start wondering what important phone numbers you’ve obtained since 2008.

Monday, 16 November 2009

This Code Is Completely Bogus

Here’s some rubbish code I wrote:

class Connection: public util::Stream
{
    ...

public:
    class Observer
    {
    public:
 virtual ~Observer() {}

 virtual unsigned OnHttpHeader(const std::string& key,
          const std::string& value) = 0;
 virtual unsigned OnHttpData() = 0;
 virtual void OnHttpDone(unsigned int error_code) = 0;
    };

private:
    explicit Connection(Observer*);
    friend class Client;

public:
    ~Connection();

    unsigned int OnActivity();

    // Being a Stream
    unsigned Read(void *buffer, size_t len, size_t *pread);
    unsigned Write(const void *, size_t, size_t*) { return EINVAL; }
};

typedef boost::intrusive_ptr<Connection> ConnectionPtr;

class Client
{
public:
    Client();

    /** Passing a NULL verb means POST (if !body.empty()) or GET (otherwise).
     */
    ConnectionPtr Connect(util::PollerInterface *poller,
     Connection::Observer *obs,
     const std::string& url,
     const std::string& extra_headers = std::string(),
     const std::string& body = std::string(),
     const char *verb = NULL);
};

It’s meant to be an HTTP client implementation, where the Connect() call returns a smart pointer to a connection object that manages its own lifetime. The Connect() call sets it all off, and attaches it to the PollerInterface object, which calls back into the Connection object (the OnActivity method) whenever the socket becomes writable (or readable, depending on where we are in the http transaction).

I mean, just look at it: it’s obviously completely bogus. [Short pause whilst you just look at it.]

Actually, no. It wasn’t at all obvious to me just from looking at it, that it was completely bogus. The only point, in fact, at which it became obvious that it was completely bogus, was when it started causing bugs.

And the bugs it caused were quite awkward ones: crashes (and Valgrind violations), obviously timing-related, to do somehow with Connection pointers still being used after the object had gone away — which should really have been disallowed by the smart-pointer class.

It turned out that the problem was if the transaction completed too quickly. At the time the code was written, the PollerInterface object didn’t own (smart pointers to) the pollable items hung off it. So, in order to stop the Connection object disappearing, due to the final reference going away, during a call to OnActivity, OnActivity itself creates and holds an additional reference to the Connection object during its execution. But if the transaction got started quickly enough, the first call to OnActivity would happen before the constructor returned — in other words, before the pointer had been assigned to the smart-pointer that’s the result of Connect(). So the “additional” reference held inside OnActivity would be the only reference — and when it went away at the end of the function, there’d be no outstanding references and the object would be deleted.

The effect was as if the constructor had included “delete this” — resulting in the new call in “p = new Connection” returning a pointer that was already dead and dangling before even being assigned to p.

Completely bogus. And worse, a completely bogus design; given the constraints, there was nothing that could possibly be done in the methods of the classes Client and Connection that would correctly implement that interface. The interface itself needed to change. Fortunately, I decided it didn’t need to change much:

class Connection
{
    ...
public:

    /** Start the HTTP transaction.
     *
     * Immediate errors (failure to parse host, failure of connect()
     * call) are returned here; errors happening any later come back
     * through Observer::OnHttpDone. In fact, OnHttpDone may be called
     * before Init() returns, i.e. you need to be ready for OnHttpDone
     * calls before you call Init(). If Init() returns a failure,
     * OnHttpDone has not been called, and is guaranteed not to be
     * called afterwards. Otherwise, it's guaranteed it WILL be
     * called.
     */
    unsigned int Init();
    ...
};

So you get a completely inert ConnectionPtr back from Client::Connect, and only then — once you’ve safely squirreled-away the smart-pointer — do you light the blue touch-paper by calling Connection::Init().

But although this version at least makes it possible to use the functionality correctly, it doesn’t really make it easy — and that should be the real goal of any act of API design. There’s that uneasy division of labour between Connect() and Init() — methods on two different classes — and there’s a whole paragraph of complex object-lifetime issues to read and understand (or, as they’re otherwise known, bugs waiting to happen) for users of Init().

This, and particularly the lifetime of the Connection::Observer object, which usually ends up having to call “delete this” in its OnHttpDone() method, left me with one of those code itches that tells me that I (and, the largely theoretical, other users of this API) am writing more complex and icky client code than I should be.

Neatening this up required making the object-lifetime issues more sane, which in turn involved greater use of smart pointers. (Not quite Wheeler’s Law, because there was already a use of indirection, and the change involved only a strengthening from reference to ownership.) In the next release of Chorale, the PollerInterface has been replaced by a Scheduler, which keeps smart pointers to its pollable items, allowing the HTTP client API to be simplified to this:

class Connection: public util::Stream
{
public:
    virtual ~Connection() {}

    /** Called with data from the returned HTTP body (if transaction
     * succeeds).
     */
    virtual unsigned Write(const void *buffer, size_t len, size_t *pwrote);

    /** Called with each incoming HTTP header (if connection succeeds).
     */
    virtual void OnHeader(const std::string& /*key*/, 
     const std::string& /*value*/) {}

    /** Called with the overall result of the connection/transaction attempt.
     */
    virtual void OnDone(unsigned int error_code) = 0;
};

typedef util::CountedPointer<Connection> ConnectionPtr;

class Client
{
    class Task;

public:
    Client();

    /** Passing a NULL verb means POST (if body != NULL) or GET (otherwise).
     */
    unsigned int Connect(util::Scheduler *poller,
    ConnectionPtr target,
    const std::string& url,
    const std::string& extra_headers = std::string(),
    const std::string& body = std::string(),
    const char *verb = NULL);
};

So the Scheduler owns the (unseen to the library user) connection Task objects, and the connection Task objects own the Connection stream target objects. Connect() can return immediate errors from the socket ::connect call or from URL parsing, while deferring any other errors to come back through a later OnDone callback — all without there being any ambiguity of the lifetime of the streams or their observers.

(There would be a problem if the Connection object also had a smart pointer to the Task object, as then neither would ever be deleted and both would become memory leaks. But, because the data is pushed from the Task to the Connection, the Connection never needs to see the Task object — and indeed can’t, because Tasks live and die entirely inside library code, and users of the library can’t even obtain pointers to them.)

Simplicity does not precede complexity, but follows it
attributed to Alan Perlis

So here’s the thing. The third design is clearly better than the second. Well, it’s clearly better than the first, too, but mainly because the first doesn’t work, which is a boring and trivial way for one design to be better than another. The interesting thing is that it’s better than the second.

And better it certainly is — making this change halved the size of the code that uses the library, as well as making it more intentional and less fragile and stylised.

So why, having got to the second design, was I not satisfied? Why did I carry on thinking about it, waiting for the inspiration of the third design to strike? And why, having come up with the third design, was there a feeling of happiness that wasn’t present when writing the the second one, even when it passed all the unit tests the first one failed?

The only answer I can come up with is to theorise the existence of an almost aesthetic sense of code quality — which is worrying in a couple of ways. Firstly, because what is instinctive is rarely communicable, and what is not communicable is soon lost: a software engineer’s fate is that of the wheelwright in the old story of Duke Huan.

But worse than that: if code quality is in fact an aesthetic, and thus extrarational, experience, then it raises the prospect that others, even other good software engineers, could have a different sense of aesthetics, ultimately resulting in a point where you and they are pulling the same code in opposite directions. (I heard recently of a software organisation, believers in the currently-fashionable “agile”, “refactor-mercilessly” style of development, in which two otherwise talented engineers spent all their time rewriting each others’ code rather than pushing things forward — as their aesthetic senses, and frankly their assumptions about who was “in charge” in the deliberately un-micro-managed environment, butted heads.)

No aesthete could get away with “correcting” the second design above into the first: the failing unit tests would prevent that. But are there those who would correct the third design into the second, in the opposite direction to me? If so, why? And, even more importantly, if not, why not?

Wednesday, 14 October 2009

Productivity Gains With KDE4

Honesty’s a good thing, usually. In particular, it’s usually a good thing in software engineering, in which most of what we do is digital and repeatable, is either one thing or the other; this fosters a culture of honesty in the same way that it does (or should do) in science, as Feynman points out in Cargo Cult Science. Unlike in a courtroom, or even in a courtroom drama, software engineering rarely comes down to one person’s word against another. (Well, unless your co-workers are sociopaths.)

But there are situations where more honesty isn’t a Good Thing. One example, in fact, is a courtroom drama: if you’re writing such a thing, the principle of pure honesty would have you title it something like “Not Guilty of Murder” — whereas, in fact, letting people know the verdict before they’ve seen the piece robs it of its whole point.

Now KDE3 came with a desktop toy called KPat, a patience game which (among others) includes an implementation of the same “Klondike” patience found in Windows Solitaire. The KDE3 (3.5.10) version of KPat had a feature where, if it detected you’d got into a situation where it was impossible to complete the hand, it would stop the game and tell you so. Naturally, such a feature has to be extremely conservative: it must stop the game only when it can be proved that forward progress is impossible. And in fact the algorithm in KDE3 KPat was very conservative indeed: it kicked-in so rarely that seeing the message always came as a surprise, even on games you already knew you’d lost.

Occasionally I’d idly wonder whether the lost-game detection could be improved — but then I realised that actually, if you improved it enough, you’d eventually get to a situation where the game detects, and tells you, the moment you’ve made a move that leads only to dead-ends. “OK, you’re an idiot, bye, next.” There’d be no point playing the game at all.

And yet, in the KDE4 (4.3.2) version of KPat, that’s exactly what’s been implemented. In the status bar, the whole time, is one of two messages — either “Solver: This game is winnable” or “Solver: This game is not winnable in its current state”. Any time you make a move that makes the first message change to the second, you soon reconsider!

And so, alongside the huge amount of work on the graphics (the original neat bitmaps have become huge and flouncy SVG images; the codebase diff is huge even ignoring the Solver; the whole thing has unexpectedly acquired an Ancient Egyptian feel) the developers have completely ruined the actual game. All the time you’re playing, it’s as if a stern examiner is watching over your shoulder, always ready to lean forwards and intone “Now I don’t believe you wanted to do that”. Worse, unlike the KDE3 algorithm, which just summarised information you could already see, the examiner can see the cards that you can’t, making it an eerily omniscient guide, not to mention a shocking cheat.

Solving patience is a great technical achievement. And it’s certainly scrupulously honest to tell the player exactly what the prospects of success are. But it’s a technical achievement that shouldn’t have been achieved (or shouldn’t be present in the game itself, even though it can be turned off), and a case where honesty is definitely not the best policy. And one of the best little time-wasters in KDE has, effectively, been eliminated.

Saturday, 12 September 2009

Recursive Make Is A Time-Waster

Now you’ve arranged to divide your project into libraries, how do you go about compiling them?

Clearly you want to be able to do the whole thing in one go: to do otherwise would be to fail the Joel test. And you want all the dependencies to be checked every time: there’s no bug harder to find than one that no longer actually exists in the source you’re looking at. (And stale objects, not updated following a header change, can lead to ODR violations: in other words, to random spookiness and borkage that the compiler and linker aren’t required to warn you about, and in many cases can’t even theoretically do so.)

GNU Automake is one answer to the problem, and makefiles in the same spirit as the ones it generates are popular even in projects that don’t use Automake. Such makefiles express inter-module dependencies, such as that of an application on a library, by recursively invoking make in the library directory before invoking it again in the application directory.

For a variety of reasons, documented once and for all in the famous paper Recursive make Considered Harmful, this is a bad idea. The paper suggests that for some systems, it’s even a bad idea for correctness reasons — that incorrect builds with inadequately-followed dependencies can result. But the example given is that of a system whose module dependencies can’t be serialised; this naturally means Automake’s sequential run over the sub-Makefiles can’t do the Right Thing. However, if the module dependencies can’t be serialised, that means there’s a cycle and they don’t form a true hierarchy; that’s a bad situation for more reasons than just Automake’s — bad for reusability, bad for unit-testability, and bad because it reveals that the system designers haven’t really thought through what the rôles of the modules are.

So if that doesn’t apply to you, if your modules are properly factored into a neat hierarchy, does that mean there’s less incentive to ditch a recursive-make scheme and take the time to write a non-recursive one? Less, perhaps, but decidedly not none — because there are substantial performance benefits from whole-project makefiles on modern systems.

This effect is, to be fair, mentioned in Recursive make Considered Harmful (7.1), but the author didn’t draw it out on pretty graphs, nor quantify the improvements, so there is scope for it to be better-documented.

Suppose your project has ten components (nine libraries and the application, say), each with between four and twenty source files. These source files won’t, naturally, all take exactly the same length of time to compile — in fact, typically there’ll be quite a wide range of compilation times, especially if only certain files include certain rather profligate library headers. And further suppose that the machine you’re compiling on has eight CPU cores or threads (such machines are desktop-class these days), so you use make -j8.

If your makefiles are like Automake’s, what happens is that make will make the first library using up to eight CPUs, then, once that’s done, make the second library using up to eight CPUs, and so on until it’s done all of them in the serialised order you used in the top-level Makefile. Which is correct, but it’s not efficient, because make needlessly serialises the entire of each library build against the entire of the next one, when typically a library’s components will each depend on only some of the previous one’s targets.

In graphical form, your CPU utilisation would look like the following diagram, where time runs from left to right, each horizontal row represents a different CPU, and blocks of the same colour belong to the same library; the top half of the diagram shows CPU utilisation during a recursive-make-driven recompilation, and the bottom half the same recompilation done with a whole-project Makefile.


click for full-size

Using one Makefile has allowed make -j8 to keep all eight CPUs busy the whole time — as, whenever a CPU comes free, any pending work from anywhere else in the project can be scheduled on it. By contrast, the top half of the diagram has lots of whitespace, where all the CPUs must wait each time until the last one in that library has finished.

In this example, the build takes scarcely 70% of the time a recursive build would do. If you have more cores, perhaps in a multi-machine build farm, the benefit goes up: building on four cores sees a reeduction only to 88%, but 12 cores sees the whole-project build take just 59% as long as the recursive version, and on 16 cores the time is better than halved. If, in the limit, you work for Dr. Evil, your entire company is basically one big compute surface and you can use “make -j one-meelion”, then the improvement factor is essentially the same as the number of libraries — in this case, 10x, though in practice if you went down that route you’d find communication overheads starting to bite into your scalability.

Four Quarters Of The Codebase

As a software project grows, eventually it becomes unwieldy to keep the entire source in one single gigantic folder: you’ll need to split it up. Canonically, and indeed quite correctly, the first idea most architects then have is to split the source into a main program plus one or more libraries that provide ancillary services.

Once that’s done, everyone on the project who sits down to write some new code, will have to think at least for a moment about where to put the source file. The answer, of course, is that the new code should go in the main program if it’s fairly specific to the current project (or if it depends on code that’s already in there), and into the library otherwise. The “force of gravity” — developers’ sense of where code should go unless there’s good reason otherwise — should be in the direction of pulling functionality over into the generic code.

Sometimes this decision seems harder than it should be: if that’s the case, what’s often going on is that the functionality in question should really be split up — with a generic part in the library, and the specific use this project makes of it in the main program. In this way, source code organisation can act as a forcing function for good design.

If that’s so useful, can we get extra design-forcing out of how we organise the source? One issue that often throws a spanner in the works of software designs whose creators didn’t originally bear it in mind, is portability between software platforms. It would be decidedly helpful if the source code organisation, and/or the system architecture it (one hopes) reflects, could help prevent platform specialists from unthinkingly tying code to a particular platform when in fact it’ll be needed more widely in future.

So instead of just application versus library, it’s helpful to organise the codebase so that a developer sitting down to write new code, will have to choose between four different places to put it:


Application-specific,
platform-specific
Library code,
platform-specific
Application-specific,
platform-agnostic
Library code,
platform-agnostic

This means that, if you’re writing an application that you’re targetting at, say, both Iphone and Windows, or both desktop and embedded, then the actual application logic needs to go in the south-west corner, where implementations on any platform can use it; user-interface code mostly goes in the north-east, where other applications wanting similar UI components can use it; and only the minimum of code necessary to wire the two together goes in the north-west.

The force of gravity in this diagram acts towards the south and the east: if you can turn code from a Win32 application into generic Win32 components, or into a portable implementation of the logic, that’s a design improvement. If you can split the code up, even split a single class up, along those lines, that’s an improvement too. And by forcing developers to make the four-way choice before they write a source file, you’re helping everyone in the team to think about these issues and to factor the code in the best way as it’s first written. Fostering a feeling of “design guilt”, in yourself or others, when placing functionality further north or west than it belongs, gives everyone an easily-grasped metric for well-factored designs.

Really this just another way of thinking about the model-view-controller pattern; the mapping is straightforward, except that MVC doesn’t have a word for the fourth quarter, libraries which are assumed to be at a lower level than the components MVC deals with:

Controllers Views
Models (Libraries)

but, even so, embodying MVC in the source layout itself means that its issues get thought about earlier in the software process.

Now naturally, any real codebase above a certain size won’t consist of just “the” application and “the” library. There’ll be a whole collection of libraries, and perhaps of applications too, arranged in a dependency graph — hopefully, for reasons Lakos expounds, a graph which forms a non-cyclic hierarchy. But it should be possible to partition this graph into (up to) four parts, matching the four quarters of the codebase, and with all dependency arrows pointing southwards, eastwards, or south-eastwards. No view or model should depend on a controller; no platform-agnostic library should depend on any view, model or controller. Again, these are truisms of MVC design, but thinking about them in their four quarters gives an easy visual way of thinking about and discussing the issues.

Incidentally, my own Chorale codebase currently (as of v0.15) fails this test, or at least gets a technical pass only: it doesn’t have any platform-specific library code or directories, as all that code is rather bogusly stuffed in the application-specific, platform-specific directories. (Some classes are, in fact, platform-specific library classes, but the split isn’t enforced in the source organisation, either by libraries or by directories.)

About Me

Cambridge, United Kingdom
Waits for audience applause ... not a sossinge.
CC0 To the extent possible under law, the author of this work has waived all copyright and related or neighboring rights to this work.