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.