Irony

I just received two magazines through my letterbox. This is the first one, addressed to a previous occupant of my home, is from the UK Ministry of Defense:

The second is my weekly subscription:

Awesome sentence fragment

Best phrase I've read in some time: an army of over-promoted, ideologically vetted homunculi

Jeff is Wrong and don't listen to him

I rarely (I hope) post specific corrections to misleading information out there on the web, not least because there's so much of it and it's usually a futile effort, but Jeff Atwood's latest post really rubbed me up the wrong way.

In his post, Jeff writes some unidiomatic C and bewails its ugliness and pain etc.:

b1 = (double *)malloc(m*sizeof(double));

By way of comparison, he then writes some C# (I expect that's what it's supposed to be) that doesn't actually use the GC, since it's not allocated on the heap:

Double b1;

(Of course, if it's not C#, and is in fact supposed to be e.g. Java, it's still not an example since it hasn't been initialized.)

Now Jeff's core message (at least at the start of the post) that GC is a Good Thing, I'm all in favour of. I strongly believe that manual memory allocation has good reasons to be used only in about 5% (or less) of programming tasks, usually restricted to things like operating systems and embedded devices. I consider well-defined, trivially provably correct zoned allocation to be a good 80% of the way to GC, so I would include good uses of that in the 95% case.

Jeff's final point, however, about "disposal anxiety" is where he casually reveals that he doesn't pay much attention to a very important issue: disposal of resources. He mocks a particular piece of code that has at least the core concept right:

sqlConnection.Close();
sqlConnection.Dispose();
sqlConnection = null;

Two-thirds of this code is redundant - the last line is always so unless sqlConnection is read later in the same routine, while either of the first two would do for resource disposal. This wouldn't be so bad but for Jeff saying:

Personally, I view explicit disposal as more of an optimization than anything else, but it can be a pretty important optimization on a heavily loaded webserver, or a performance intensive desktop application plowing through gigabytes of data.

Disposal of resources in a long-running application using GC is not a performance issue. It's a correctness issue.

Garbage collection knows about memory. With most collectors, GC is only invoked when the GC is asked for more memory than is immediately available, taking specific tuning parameters into account. In other words, the GC is only sensitive to memory pressure. It doesn't know about resources that it sees only as pointer-sized handles, it doesn't know how much they "cost", and indeed those resources might be on a different machine or even spread across many different machines.

More critically, garbage collection gets its performance surplus over and above manual garbage collection by not collecting until as late as reasonably possible, where "reasonable" is usually a function of how much free memory is available without swapping to disk. The long-run-average optimal collector for a program that has a machine all to itself won't collect at all until every last remaining byte of RAM has been allocated, which may of course take some time. (Added to clarify: this is a theoretical optimum, and not how most GCs act in practice. They collect much sooner e.g. the youngest generation may fit in L2 cache and so be very fast to collect.)

Precise tracing garbage collectors work somewhat paradoxically not by collecting garbage, but by collecting live objects. The "garbage" is everything left over after all the live objects have been collected. The more garbage as a fraction of live objects there is, the cheaper, proportionally, it has been to collect. (Added to clarify: this means that the collection of garbage is amortized; any amount of garbage costs the same to collect, providing the set of live objects is held constant.) This is how GCs outperform manual memory allocation on average and with sufficient free memory. Ideally, the GC never runs at all, and program termination cleans up.

With this insight under your belt, it should be clear that expecting the GC to clean up resources is to be ignoring one of the key benefits of GC. Not only that, but you shouldn't be expecting the GC to finalize your objects at all. If your resources must be disposed of - and almost all resources should, e.g. TCP sockets, file handles, etc. - then you need to take care of that yourself, and deterministically. Leaving e.g. file handles to be disposed of by the GC is opening up the program (and possibly the user) to odd non-deterministic failures when they find files on disk are still locked, even though the program should have closed them.

Implementing user-defined copy-on-write data structures in Delphi

There was some discussion about user-defined class operators in the Delphi non-technical forum. Some folks seem to be asking for operators for heap-allocated classes, but in the absence of either GC or reference counting, these are problematic.

I suggested that records combined with interfaces can get much of the benefit of both worlds: user-defined operators on the record, life-time management via interface reference counting, and arbitrary data sizing through the interface being a heap reference.

To demonstrate the idea through example, I have written up a quick copy-on-write array type that has a user-defined '+' operator that concatenates two lists. Let me build it up from the bottom. First, I've defined a generic dynamic array type to avoid the pitfalls of nominal typing that Delphi has inherited from Pascal (a common newbie mistake, particularly with the syntactic ambiguity with open arrays in parameter lists):

type
  TArray<T> = array of T;

Next up is the interface. Using an interface for communicating between the record and the heap value means that I get reference counting, and thus lifetime management, for free.

  ICowArrayData<T> = interface
    function GetLength: Integer;
    function MutableClone: ICowArrayData<T>;
    function GetItem(Index: Integer): T;
    procedure SetItem(Index: Integer; const Value: T);
    function ToArray: TArray<T>;
  end;

  TCowArrayData<T> = class(TInterfacedObject, ICowArrayData<T>)
  private
    FData: TArray<T>;
  public
    constructor Create(const Data: TArray<T>);
    function GetLength: Integer;
    function MutableClone: ICowArrayData<T>;
    function GetItem(Index: Integer): T;
    procedure SetItem(Index: Integer; const Value: T);
    function ToArray: TArray<T>;
  end;

The only "interesting" method really is MutableClone, which I'll be calling to verify that I have a unique instance before I perform any mutating operations. This is necessary to get copy-on-write behaviour. The implementation class doesn't add anything beyond a constructor, as all communication will be through the interface.

Here's the actual record, and the only type that the user of this bundle should concern themselves with:

  TCowArray<T> = record
  private
    FData: ICowArrayData<T>;
    function GetItems(Index: Integer): T;
    procedure SetItems(Index: Integer; const Value: T);
    function GetLength: Integer;
  public
    constructor Create(const Data: TArray<T>); overload;
    constructor Create(const Data: array of T); overload;
    property Items[Index: Integer]: T read GetItems write SetItems; default;
    property Length: Integer read GetLength;
    function ToArray: TArray<T>;

    class operator Add(const Left, Right: TCowArray<T>): TCowArray<T>;
  end;

It adds a nice default Items property so that values can be indexed like arrays, exposes a Length property much like .NET, and adds in the Add operator to prove the point.

The implementation of most the methods are pretty routine, but a few are important. First up, because interfaces are managed types, they get zero-initialized by default. Thus, we can't expect the record's FData field to be initialized. We can take a leaf out of Delphi's built-in array (and string) types, and let zero-length arrays be represented by a nil FData. That affects the implementation of the record methods, e.g.:

function TCowArray<T>.GetLength: Integer;
begin
  if FData = nil then
    Exit(0); // nil => zero-length
  Result := FData.GetLength;
end;

Another important method is the implementation of the copy-on-write itself. The only mutating method on this type is SetItems, and here it is:

procedure TCowArray<T>.SetItems(Index: Integer; const Value: T);
begin
  FData := FData.MutableClone;
  FData.SetItem(Index, Value);
end;

This isn't particularly efficient, but it does make sure that we have a unique reference when required. The implementation of MutableClone is simple enough too:

function TCowArrayData<T>.MutableClone: ICowArrayData<T>;
begin
  if RefCount = 1 then
    Exit(Self);
  Result := TCowArrayData<T>.Create(ToArray);
end;

Using the inherited RefCount from TInterfacedObject, we can determine safely if we are only referred to by our caller. In a race scenario, where RefCount might e.g. spuriously be 2, there won't be any correctness problem if we duplicate the array anyway.

The implementation of the '+' operator is pretty trivial too:

class operator TCowArray<T>.Add(const Left, Right: TCowArray<T>): TCowArray<T>;
var
  resultArr: TArray<T>;
  i: Integer;
begin
  SetLength(resultArr, Left.Length + Right.Length);
  for i := 0 to Left.Length - 1 do
    resultArr[i] := Left[i];
  for i := 0 to Right.Length - 1 do
    resultArr[Left.Length + i] := Right[i];
  Result := TCowArray<T>.Create(resultArr);
end;

Finally, let's look at the program body itself, testing these types:

procedure WriteArray(const Msg: string; Arr: TCowArray<Integer>);
var
  i: Integer;
begin
  Write(Msg, ':');
  for i := 0 to Arr.Length - 1 do
    Write(' ', Arr[i]);
  Writeln;
end;

var
  x, y: TCowArray<Integer>;
begin
  try
    x := TCowArray<Integer>.Create([1, 2, 3]);
    y := x;

    Writeln('Starting out, both x and y refer to same instance data');
    WriteArray('x', x);
    WriteArray('y', y);

    Writeln('Modifying x; note that y doesn''t change:');
    x[1] := 42;
    WriteArray('x', x);
    WriteArray('y', y);

    // Add operator as concatenation
    Writeln('Concatenation:');
    y := x + y;
    WriteArray('x', x);
    WriteArray('y', y);
    
  except
    on E: Exception do
      Writeln(E.ClassName, ': ', E.Message);
  end;
end.

The output does indeed show that the array is copied on writes, and that concatenation works as expected:

Starting out, both x and y refer to same instance data
x: 1 2 3
y: 1 2 3
Modifying x; note that y doesn't change:
x: 1 42 3
y: 1 2 3
Concatenation:
x: 1 42 3
y: 1 42 3 1 2 3

As an addendum, let me add the full source for reference. Note that due to some bugs in the current compiler's generics implementation for dynamic arrays, the code won't work if it's part of a unit - it needs to be in a single whole for now, unfortunately.

{$apptype console}
uses SysUtils;

type
  TArray<T> = array of T;
  
  ICowArrayData<T> = interface
    function GetLength: Integer;
    function MutableClone: ICowArrayData<T>;
    function GetItem(Index: Integer): T;
    procedure SetItem(Index: Integer; const Value: T);
    function ToArray: TArray<T>;
  end;
  
  TCowArrayData<T> = class(TInterfacedObject, ICowArrayData<T>)
  private
    FData: TArray<T>;
  public
    constructor Create(const Data: TArray<T>);
    function GetLength: Integer;
    function MutableClone: ICowArrayData<T>;
    function GetItem(Index: Integer): T;
    procedure SetItem(Index: Integer; const Value: T);
    function ToArray: TArray<T>;
  end;
  
  TCowArray<T> = record
  private
    FData: ICowArrayData<T>;
    function GetItems(Index: Integer): T;
    procedure SetItems(Index: Integer; const Value: T);
    function GetLength: Integer;
  public
    constructor Create(const Data: TArray<T>); overload;
    constructor Create(const Data: array of T); overload;
    property Items[Index: Integer]: T read GetItems write SetItems; default;
    property Length: Integer read GetLength;
    function ToArray: TArray<T>;

    class operator Add(const Left, Right: TCowArray<T>): TCowArray<T>;
  end;

{ TCowArray<T> }

class operator TCowArray<T>.Add(const Left, Right: TCowArray<T>): TCowArray<T>;
var
  resultArr: TArray<T>;
  i: Integer;
begin
  SetLength(resultArr, Left.Length + Right.Length);
  for i := 0 to Left.Length - 1 do
    resultArr[i] := Left[i];
  for i := 0 to Right.Length - 1 do
    resultArr[Left.Length + i] := Right[i];
  Result := TCowArray<T>.Create(resultArr);
end;

constructor TCowArray<T>.Create(const Data: TArray<T>);
begin
  if Data = nil then
    FData := nil
  else
    FData := TCowArrayData<T>.Create(Data);
end;

constructor TCowArray<T>.Create(const Data: array of T);
var
  arr: TArray<T>;
  i: Integer;
begin
  if System.Length(Data) = 0 then
    FData := nil
  else
  begin
    SetLength(arr, System.Length(Data));
    for i := 0 to System.Length(Data) - 1 do
      arr[i] := Data[i];
    FData := TCowArrayData<T>.Create(arr);
  end;
end;

function TCowArray<T>.GetItems(Index: Integer): T;
begin
  Result := FData.GetItem(Index);
end;

function TCowArray<T>.GetLength: Integer;
begin
  if FData = nil then
    Exit(0);
  Result := FData.GetLength;
end;

procedure TCowArray<T>.SetItems(Index: Integer; const Value: T);
begin
  FData := FData.MutableClone;
  FData.SetItem(Index, Value);
end;

function TCowArray<T>.ToArray: TArray<T>;
begin
  if FData = nil then
    Exit(nil);
  Result := FData.ToArray;
end;

{ TCowArrayData<T> }

constructor TCowArrayData<T>.Create(const Data: TArray<T>);
begin
  FData := Data;
end;

function TCowArrayData<T>.GetItem(Index: Integer): T;
begin
  Result := FData[Index];
end;

function TCowArrayData<T>.GetLength: Integer;
begin
  Result := Length(FData);
end;

function TCowArrayData<T>.MutableClone: ICowArrayData<T>;
begin
  if RefCount = 1 then
    Exit(Self);
  Result := TCowArrayData<T>.Create(ToArray);
end;

procedure TCowArrayData<T>.SetItem(Index: Integer; const Value: T);
begin
  FData[Index] := Value;
end;

function TCowArrayData<T>.ToArray: TArray<T>;
var
  i: Integer;
begin
  SetLength(Result, Length(FData));
  for i := 0 to Length(FData) - 1 do
    Result[i] := FData[i];
end;

procedure WriteArray(const Msg: string; Arr: TCowArray<Integer>);
var
  i: Integer;
begin
  Write(Msg, ':');
  for i := 0 to Arr.Length - 1 do
    Write(' ', Arr[i]);
  Writeln;
end;

var
  x, y: TCowArray<Integer>;
begin
  try
    x := TCowArray<Integer>.Create([1, 2, 3]);
    y := x;

    Writeln('Starting out, both x and y refer to same instance data');
    WriteArray('x', x);
    WriteArray('y', y);

    Writeln('Modifying x; note that y doesn''t change:');
    x[1] := 42;
    WriteArray('x', x);
    WriteArray('y', y);

    // Add operator as concatenation
    Writeln('Concatenation:');
    y := x + y;
    WriteArray('x', x);
    WriteArray('y', y);
    
  except
    on E: Exception do
      Writeln(E.ClassName, ': ', E.Message);
  end;
end.

Semantics, Formats and Markets

I was reading Dare's response to Bill's post on format proliferation and RDF. Bill hopes that more folks will understand RDF and seems to see it somewhat as a silver bullet for the problem, while Dare is more pessimistic.

The way I see it, there are distinctly two issues here. The first is the obvious one, solving the n*m problem, where n = format count and m = format producer and consumer count. The idea behind any common format or format mapping / shaping / semantic extraction is to reduce it to n*1 + 1*m, i.e. n+m.

That's all well and good, but it has problems: lowest common denominator, semantic loss in conversion, inhibition of innovation (gated on lowest common denominator), barriers to entry (new producers want only to be concerned with their specifics, not a huge standard, while new consumers don't want to have to implement the world before being useful).

More germane to the RDF situtaion, a requirement to understand a meta-model as well as any given model itself is so large a barrier to non-specialists just trying to get their work done that it's highly unlikely to ever receive serious attention. More on that in a bit.

Official standards-body approaches are the other issue. Formats in an area of innovation act like a bubbling market; take-up of formats by consumers and producers determine the winner, until eventually network effects reduce the total number of formats to just a handful. The problem with trying to manage this market process via a committee is much like the problem of trying implement socialism: the total information embodied in various choices of one format over and above another, which a free market reveals naturally, is not available to committees. Committees tend to be dominated by large market players which have various strategic and political objectives that may be quite distinct, and indeed sometimes covertly opposed, to the average market desires for any given format.

The working programmer, at the end of the day, is either putting square pegs into square holes (in which case, no problem), or trying to put square pegs into round holes, and then having to create an adapter to convert square pegs into round pegs. An arbitrary selection of square or round as a "peg standard" doesn't necessarily help him for his specific needs; similarly, pointing at some generalized framework for describing the semantic meaning of square and round pegs respectively is far too abstract for him to get his job done efficiently - i.e. without investment whose cost exceeds the value of getting the original job done.

iPod Touch, iTunes, and unwanted processes

I recently got a second-generation iPod Touch. I don't make enough phone calls to make a phone contract worthwhile, much less an iPhone contract with O2 in the UK; and O2's PAYG (pay as you go) appears to charge GBP 7.50 per roaming MB, while I pay EUR 1 for first 50 MB with my Vodafone Ireland PAYG, whether I'm in the UK, anywhere else in Europe, or in the US. So, iPod Touch it is.

It's a nice device, both style-wise and as a hand-held web-browsing experience. The browser is good enough to create a paradox; limitations that only surface because of the increased expectations start to get a little annoying. For example, up to eight separate pages can be browsed simultaneously, but as soon as one of the pages gets big enough, information about the other open pages is forgotten beyond the URL / request parameters. This means that e.g. you don't want to leave a purchase page open while browsing in a parallel window, or you'll break navigation flow / possibly pay twice.

The browser also crashes a lot. I've had the device for about two days, and suffered many (8+) unprompted "back to main menu" transitions, with nary a hint from the device that the browser had crashed. It does make me wonder; how much of the reputation Apple has for good firmware is due to pretending that errors don't happen? The subsequent OS-level cleanup / resource management doesn't seem too solid either, since searches on the topic suggest that a clean reboot is what's necessary to restore this BSD-based Unix kernel to good running. This doesn't inspire confidence.

As a device for playing music, it's too large and heavy for my taste; I'm still using my second-generation Nano, even though I also have a third-generation Nano - the wheel is too small on it.

The draconian limitations that are de rigeur with Apple firmware chafe quite a lot. Even my humble K800 phone can create folders in the file system, browse it, start applications from arbitrary locations, open videos, music and pictures from arbitrary locations, etc., all using the same tree that you see when browsing the CF card from a PC. The iPod Touch doesn't have any of this: it's Apple's way or screw you, to be blunt. iTunes synchronization is a useless to me; I'm a file system guy - give me scripting, cron and hard & symbolic links and I'll create the structure I prefer myself. I suspect I won't be happy until the device is jailbroken.

Anyhow, the other reason I wanted to write this post, other than to praise and complain about the device, is the little setup I created to cope with iTunes 7, which I was reluctantly forced to upgrade to. The iPod Touch doesn't work without iTunes 7, and it also doesn't work without a bunch of other background services running, most importantly, the 'Apple Mobile Device' service.

Rather than have half a dozen Apple-related processes running, even though I'm not running iTunes and don't have a device connected to my machine, I wrote a little script to start up the necessary services upon iTunes startup, and kill off the unwanted processes after iTunes shutdown. They rely on Cygwin and some little utilities I wrote myself.

First up is 'hide.exe'. This simple executable, written in Delphi, runs a given process with a list of command-line arguments, but in a hidden window, by passing SW_HIDE as the nShow parameter. This basically lets a console hang around running my script while iTunes is running, waiting for it to exit, so that the script can clean things up later. The hide.exe executable itself is a GUI subsystem app, though it doesn't have a message pump or anything.

The second is a very simple killall script for Cygwin:

#!/bin/bash

if test -z "$1"; then
    echo "usage: $(basename $0) ..."
    echo "Kills all specified processes."
    exit
fi

while [ -n "$1" ]; do
    ps -W | grep -i "$1" | cut -b -10 | print0 | xargs -0 kill -f
    shift
done

Obviously, when using this script you don't want to be too ambiguous about your process search string. The 'print0' in the pipe is another little utility I wrote to bridge the gap between line-oriented programs, word-oriented programs and programs that can accept null-terminated strings. It simply reads each line one at a time, and prints out the same line with a null terminator instead of a newline. Without it, any programs with spaces in their names would be parsed by xargs as multiple separate arguments, since xargs, by default, breaks arguments on any whitespace, not just newlines.

With that aside, my iTunes wrapper script (I call it start-itunes) is fairly simple:

#!/bin/bash

itunes="${itunes:-/c/other/itunes/itunes.exe}"

net start 'Apple Mobile Device' > /dev/null
"$itunes" || messagebox "Failed to start \"$itunes\""
net stop 'Apple Mobile Device' > /dev/null || messagebox 'Failed to stop "Apple Mobile Device"'
net stop 'iPod Service' > /dev/null
killall SyncServer.exe distnoted.exe

It simply starts the required service, lets iTunes run to completion, and then stops the redundant services and blows away the crap left behind by iTunes. I don't use iTunes to "sync" anything, so I'm assuming that blowing them away doesn't hurt. I haven't had any problems, anyhow.

This script uses 'messagebox', yet another little utility I wrote, to display errors using the Win32 MessageBox function. This is necessary, otherwise the errors wouldn't be visible - the script is run from a hidden window.

The final step is the shortcut itself. Cygwin has a utility, mkshortcut, to create shortcuts, though I don't like its command-line syntax and wrote a wrapper script to make it look more like ln and friends. However, a Cygwin mkshortcut command-line for creating an appropriate shortcut for my script above might look a bit like this (watch the backslash, added for nicer PRE formatting):

mkshortcut -a "$(cygpath -w $(which bash.exe)) $(which start-itunes)" \
    -n start-itunes.lnk -i /c/other/itunes/iTunes.exe $(which hide.exe)

Since start-itunes and hide.exe are useful in themselves, they're on my path, so 'which' is able to find them.