Entropy Overload

Delphi XE2 compiler performance

2011-10-04T12:22:00.002+01:00

Delphi XE2 introduced namespaces across the runtime library. This stressed unit name lookup inside the compiler, and led to some severe performance regressions in certain cases. So during the runup to the XE2 release, I fired up a profiler and started investigating. It turns out there were numerous situations where lookups were being performed repeatedly with the same arguments, and logically the results should have been consistent across these repeated calls. A relatively cheap and easy fix seemed to be memoization. So I added a caching infrastructure to the compiler and used the profiler to guide me where to inject it.

For the most part - particularly for full builds - the cache works really well. But I've had some reports of bugs that I suspected were caused by the cache hanging on to function results slightly too long, and upon investigation, this turned out to be true. The problem with caches is usually in invalidation; if you don't invalidate the cache soon enough and in all required situations, you end up serving stale results. So there are a few bugs lurking in the Delphi compiler here, which I'm seeking out and squashing.

Some good news, however; I had anticipated that this might be the case, so I added a super secret switch that enables diagnosing a probable cache failure: caches can be selectively disabled, and if a problem goes away with the cache disabled, it's probably because of stale results.

Caches can be disabled by setting an environment variable:

DCC_CACHE_DISABLE='SearchUnitNameInNS,FileSystem,UnitFindByAlias,GetUnitOf'

The above environment variable setting disables all the compiler's caches. By including fewer than the four separate cache names, the problem can iteratively be narrowed down to a specific cache.

I've just been fixing one bug caused by the cache that brought home how needed it is. The project is large; almost 2 million lines. An initial build with the cache enabled takes about a minute on my machine; the bug exhibits itself in later incremental compiles when modifying the source code and pressing F9, producing spurious errors. However, once I disabled the cache (or rather, I recompiled the compiler with cache sanity checking enabled, which still filled out the cache, but also invoked the underlying logic, and simply compared the results to verify the cache), the build time took nearly 3 hours!

Note: invalidation is most likely to be a problem on incremental compiles, rather than full rebuilds, especially from within the IDE. The reason is that the compiler may have lots of stale data for one half of an incremental compile that it later decides is out of date (e.g. a dependency changed); this can leave a bunch of stale entries in the cache for all the memoized function calls that occurred in the first half of the compile. The cache is strictly per-compile; it keeps no data across multiple compilations, even partial compilations.

An ugly alternative to interface to object casting

2011-03-01T15:13:00.005Z

I was answering a question on Stack Overflow, but the user didn't have the latest version of Delphi. My answer included converting an interface to an object instance, which is made possible with the as cast on interfaces in recent Delphi versions. But there is another way of doing it, exploiting the regularity Delphi interface vtable implementations:

{$apptype console}

function Intf2Obj(x: IInterface): TObject;
type
  TStub = array[0..3] of Byte;
const
  // ADD [ESP+$04], imm8; [ESP+$04] in stdcall is Self argument, after return address
  add_esp_04_imm8: TStub = ($83, $44, $24, $04);
  // ADD [ESP+$04], imm32
  add_esp_04_imm32: TStub = ($81, $44, $24, $04);
  
  function Match(L, R: PByte): Boolean;
  var
    i: Integer;
  begin
    for i := 0 to SizeOf(TStub) - 1 do
      if L[i] <> R[i] then
        Exit(False);
    Result := True;
  end;
  
var
  p: PByte;
begin
  p := PPointer(x)^; // get to vtable
  p := PPointer(p)^; // load stub address from vtable
  
  if Match(p, @add_esp_04_imm8) then 
  begin
    Inc(p, SizeOf(TStub));
    Result := TObject(PByte(Pointer(x)) + PShortint(p)^);
  end
  else if Match(p, @add_esp_04_imm32) then
  begin
    Inc(p, SizeOf(TStub));
    Result := TObject(PByte(Pointer(x)) + PLongint(p)^);
  end
  else
    raise Exception.Create('Not a Delphi interface implementation?');
end;

type
  ITest = interface
    procedure P;
  end;
  TTest = class(TInterfacedObject, ITest)
    F: array[0..200] of Byte;
    procedure P;
  end;

procedure TTest.P;
begin
  Writeln('Hello');
end;
  
procedure Go;
var
  orig: TTest;
  i: ITest;
  o: TObject;
begin
  orig := TTest.Create;
  i := orig;
  i.P;
  o := Intf2Obj(i);
  Writeln(o = orig);
end;

begin
  Go;
end.

This approach is predicated on the idea that the stub code that Delphi produces for turning the implicit interface argument into an instance argument is predictable. It generally only has two forms, depending on how much of an adjustment it needs to make (which itself depends on how much instance data there is). It ought to work for almost all 32-bit Delphi interfaces that have been implemented by instances, where the vtable was created by the compiler. If not, other stub variations can be analyzed (in the IDE CPU view) and handled too. It ought to be pretty safe, as only this specific code is permitted. It could be made even safer by ensuring that the stub ends with a JMP and that the instance returned has a ClassType descending from TClass.

Update: After a Google search I note that Hallvard also wrote about this some time ago. His code is a little tighter than mine (using Integer constants rather than byte-by-byte comparison); in my defense, I only spent a few minutes on this...

Scrolling: Chrome vs Firefox

2010-12-20T18:03:00.007Z

I was using the Chrome browser on my laptop the other day (some browser compat problem). I don't normally use it; Firefox is my preferred browser. I couldn't help but notice how peculiarly laggy it felt to use. It came down to vertical scrolling: this highly common task - for any long article you'll be doing a lot of it - felt jerky and unpleasant. So I did a quick ad-hoc experiment: open up the same web page in both browsers with viewports of the same size, grab the vertical scroll bar, and wiggle it up and and down continuously so the browser is constantly redrawing text.

This is a crop from Process monitor on my desktop machine, which has 8 logical cores, i.e. 4 physical cores with hyperthreading. That means that 100% CPU usage on one core shows up as 12.5% CPU usage. The big wide bump on the left is the CPU usage while I was fiddling with Chrome; the one on the right is Firefox. (The bump in the middle is sqlservr.exe, which wakes up and does meaningless busywork every 60 seconds.) You can see that Chrome uses perhaps 50% more CPU usage on this task than Firefox, with more time spent in the user process and (proportionately) less in the kernel (presumably shifting bits around). Eyeballing an average of CPU usage, Firefox ranged from 6% to 7.5%, while Chrome pegged at 12.5%. Chrome is simply less CPU-efficient redrawing while scrolling, and it's very obvious to my eyes. (I did the same experiment with IE, and it was in the middle, with about 9% CPU.)

I might hazard a guess that Firefox spends more memory on caching bitmaps of the web page, or some similar trick trading off space for time. In any case, it's one of the reasons Firefox is still my primary browser, and also why I'm completely unconcerned about its memory usage. I have yet to encounter significant paging because of Firefox, not least because it's a 32-bit process, limiting its maximum usage, and I have alternately 12G and 4G of memory in my primary desktop and laptop respectively.

Mind you, when I add up the private working set for all 8 chrome.exe processes apparently needed to display this web page, they add up to 86M, only 1M less than my recently restarted firefox.exe session at 87M. (Comparing other memory usage numbers is awkward, as non-working-set memory isn't relevant, while non-private memory would be double-counted with Chrome.)

CrashPlan manual installation approach on Nexenta

2010-11-15T06:14:00.008Z

I wrote an earlier post about installing CrashPlan on Nexenta. However, it seems that CrashPlan have changed their Linux installer's modus operandi, and it tries to install a (Linux) JRE of its own. Of course, that won't work; it needs the Nexenta JRE (but I get the whole JDK, as you never know when you'll need to brew up some Java):

$ sudo apt-get install sun-java6-jdk

Anyhow, I received some comments and emails about setting all this up, and figured I'd break it down a little more for people who still want to get it all working. It's a process of hacking things together, though, not a blind recipe; that's why I'm proceeding almost as if it's a debugging session.

Anyhow, once we have a JRE installed (from apt-get above), we can try and extract out the guts of the Linux installer, so rather than running its install.sh, we can set it up manually.

I went to the CrashPlan Linux download web page, and started downloading the installer in a scratch folder (this was the URL at the time of writing):

$ wget http://download.crashplan.com/installs/linux/install/CrashPlan/CrashPlan_2010-03-08_Linux.tgz

That's a gzipped tar archive, so I extracted it:

$ tar xzf CrashPlan_2010-03-08_Linux.tgz
$ cd CrashPlan-install # the dir it extracted
$ ls
CrashPlan_2010-03-08.cpi  EULA.txt  INSTALL  README  install.sh  scripts  uninstall.sh

I didn't know what the big CrashPlan*.cpi file was, so I checked:

$ file CrashPlan_2010-03-08.cpi
CrashPlan_2010-03-08.cpi: gzip compressed data, was "CrashPlan_2010-03-08.cpi", from Unix, max compression

So it's a gzipped file! I decompressed it, and tested the result:

$ gunzip < CrashPlan_2010-03-08.cpi > test
$ file test
test: ASCII cpio archive (pre-SVR4 or odc)

A cpio archive! I extracted that too, but in a separate directory:

$ mkdir t; cd t; cpio -i ../test
$ ls
bin  conf  doc  jniwrap.lic  lang  lib  libjniwrap.so  libjniwrap64.so  libjtux.so  libjtux64.so  log  skin  upgrade

Now this looks very close to the root listing of my actual current CrashPlan install on Nexenta, and by and large it is. Here's a rough difference between the two (listing.curr is my actual install, listing is extracted from the installer):

--- listing.curr        2010-11-15 06:32:12.548701734 +0000
+++ listing     2010-11-15 06:31:40.726884007 +0000
-CrashPlanEngine.pid
-bin/CrashPlanDesktop
-bin/CrashPlanEngine
-bin/CrashPlanEngine.lsb
-bin/run.conf
-bin/vars.sh
-conf/my.service.xml
-conf/service.login
-conf/service.model
-install.vars
-libjtux.so.lsb
-libjtux.so.sol

Let's go through those. This install tree is almost complete; it can be put in /usr/local/crashplan (that's where I have mine) or wherever you like, so long as the configuration bits are also hooked up appropriately.

CrashPlanEngine.pid is just the pidfile, a text file containing the process id of the currently running instance. I'm not sure why it's in the crashplan directory rather than somewhere like /var/run, but it is. I believe the crashplan service will create it.

CrashPlan* are all shell wrappers for Java applications; *.lsb (LSB for Linux Standard Base) are the original versions (I think I renamed them to this). I don't have an X server or libraries on my Nexenta install, so I'm uninterested in CrashPlanDesktop. CrashPlanEngine however is important; it's the main daemon file. Here's mine, which seems to work; I think I may have edited it to work with some GNU utils rather than Solaris utils, as I believe this came from the Solaris installer (or vice versa; actually that's probably more likely):

#!/bin/bash

TARGETDIR="`dirname ${0}`/.."

. ${TARGETDIR}/install.vars
. ${TARGETDIR}/bin/run.conf

cd ${TARGETDIR}

case $1 in
        start)
                PID=`/usr/bin/ps -Af -o pid,ppid,args | grep 'app=CrashPlanService' | grep -v grep | cut -f2 -d' '`
                if [ -n "$PID" ]; then
                  echo CrashPlan is already running with pid $PID
                  exit 1;
                fi
                echo "Starting CrashPlan Engine ... "
                nice -n 19 ${JAVACOMMON} ${SRV_JAVA_OPTS} -classpath "./lib/com.backup42.desktop.jar:./lang" com.backup42.service.CPService > ${TARGETDIR}/log/engine_output.log 2> ${TARGETDIR}/log/engine_error.log & 
                if [ $! -gt 0 ]; then
                        echo $! > ${TARGETDIR}/CrashPlanEngine.pid
                        echo "OK"
                else
                        echo "FAIL" 
                        exit 1
                fi
                ;;
        stop)
                echo "Stopping CrashPlan Engine ... "
                if [ -f ${TARGETDIR}/CrashPlanEngine.pid ] ; then
                  kill `cat ${TARGETDIR}/CrashPlanEngine.pid`
                  sleep 5
                fi
                PID=`/usr/bin/ps -Af -o pid,ppid,args | grep 'app=CrashPlanService' | grep -v grep | cut -f2 -d' '`
                if [ -n "$PID" ]; then
                  echo Still running, killing PID=$PID
                  kill -9 $PID
                fi
                rm -f ${TARGETDIR}/CrashPlanEngine.pid
                echo "OK"
                ;;
        *)      
                echo "$0 "
                exit 1
                ;;
esac

As you can see, that script sources (includes) a couple of other guys, bin/run.conf and install.vars. bin/run.conf looks like this:

SRV_JAVA_OPTS="-Dfile.encoding=UTF-8 -Dapp=CrashPlanService -DappBaseName=CrashPlan -Xms20m -Xmx512m -Dsun.net.inetaddr.ttl=300 -Dnetworkaddress.cache.ttl=300 -Dsun.net.inetaddr.negative.ttl=0 -Dnetworkaddress.cache.negative.ttl=0"
GUI_JAVA_OPTS="-Dfile.encoding=UTF-8 -Dapp=CrashPlanDesktop -DappBaseName=CrashPlan -Xms20m -Xmx512m -Dsun.net.inetaddr.ttl=300 -Dnetworkaddress.cache.ttl=300 -Dsun.net.inetaddr.negative.ttl=0 -Dnetworkaddress.cache.negative.ttl=0"

install.vars looks like this (for my current install):

TARGETDIR=/usr/local/crashplan
BINSDIR=/usr/local/bin
MANIFESTDIR=/tank/share/backup/crashplan
INITDIR=/etc/init.d
RUNLVLDIR=/etc/rc3.d
INSTALLDATE=20100310
APP_BASENAME=CrashPlan
DIR_BASENAME=crashplan
DOWNLOAD_HOST=download.crashplan.com
JAVACOMMON=/usr/bin/java

The MANIFESTDIR variable points to a directory I expect I provided when I ran the original install.sh, but there's nothing currently in it. The other paths are as you'd expect.

As far as I can make out, the conf/* files are created by CrashPlan itself in coordination with the configuration utility, which, as I linked in my previous post, can be run remotely from a Windows (or other OS) install of CrashPlan. There's a default.service.xml as a prototypical my.service.xml, while service.{login,model} appear to be login and encryption keys.

That leaves libjtux.so.*. These are renamed versions of the file libjtux.so which differs between Linux and Solaris. Primarily they differ in which C library they link against (note: running ldd on untrusted binaries is unsafe, but I trust these binaries):

$ ldd libjtux.so.*
warning: ldd: libjtux.so.lsb: is not executable
libjtux.so.lsb:
        librt.so.1 =>    /lib/librt.so.1
        libnsl.so.1 =>   /lib/libnsl.so.1
        libc.so.6 =>     (file not found)
        libmp.so.2 =>    /lib/libmp.so.2
        libmd.so.1 =>    /lib/libmd.so.1
        libscf.so.1 =>   /lib/libscf.so.1
        libc.so.1 =>     /lib/libc.so.1
        libuutil.so.1 =>         /lib/libuutil.so.1
        libgen.so.1 =>   /lib/libgen.so.1
        libm.so.2 =>     /lib/libm.so.2
warning: ldd: libjtux.so.sol: is not executable
libjtux.so.sol:
        librt.so.1 =>    /lib/librt.so.1
        libsocket.so.1 =>        /lib/libsocket.so.1
        libnsl.so.1 =>   /lib/libnsl.so.1
        libc.so.1 =>     /lib/libc.so.1
        libmp.so.2 =>    /lib/libmp.so.2
        libmd.so.1 =>    /lib/libmd.so.1
        libscf.so.1 =>   /lib/libscf.so.1
        libuutil.so.1 =>         /lib/libuutil.so.1
        libgen.so.1 =>   /lib/libgen.so.1
        libm.so.2 =>     /lib/libm.so.2

Anyhow, we need to get the right version of libjtux.so. It seems to be an open-source project and getting a version wouldn't be difficult, but the one in the CrashPlan Solaris installer works fine; let's get that one:

# current version when I ran this
$ wget http://download.crashplan.com/installs/solaris/install/CrashPlan/CrashPlan_2010-03-08_Solaris.tar.gz
$ tar xzf CrashPlan_2010-03-08_Solaris.tar.gz
$ cd CrashPlan/root/opt/sfw/crashplan
$ ls
bin  client-build.properties  conf  doc  installer  jniwrap.lic  lang  lib  libjtux.so  skin  upgrade

So here we have the entrails of a CrashPlan for Solaris install, and we can pick and choose which organs we need to transplant; and the thing that's particularly needed is libjtux.so; it needs to replace the Linux version.

All that should be left is getting CrashPlan to start at boot-up, which is easiest manually done in Nexenta with the init.d system. Here's the executable crashplan script I have in /etc/init.d:

#!/bin/bash
SCRIPTNAME=/usr/local/crashplan/bin/CrashPlanEngine

case "$1" in
start)
        $SCRIPTNAME start       
        ;;
stop)
        $SCRIPTNAME stop
        ;;
restart)
        $SCRIPTNAME restart
        ;;
force-reload)
        $SCRIPTNAME force-reload
        ;;
status)
        $SCRIPTNAME status
        ;;
*)      
        echo "Usage: $0 " >&2
        exit 3
        ;;
esac
exit 0

And the symlink in rc3.d:

$ ls -l /etc/rc3.d/S99crashplan 
lrwxrwxrwx 1 root root 21 Mar 10  2010 rc3.d/S99crashplan -> ../init.d/crashplan

That's it!

Non-Delphi: Postmodernism, Transformers: ROTF and Baudrillard

2010-09-15T09:51:00.008+01:00

The simulacrum is never that which conceals the truth--it is the truth which conceals that there is none. The simulacrum is true. (Baudrillard, Simulacra and Simulation)

I've just watched Transformers: Revenge of the Fallen, and it got me thinking. It's perhaps the most post-modern movie I've seen to date.

T:ROTF isn't so much a movie as a string of soundbites, stereotypes and cliches arranged into a 2.5 hour trailer for a movie you'll never get to see, because it was never made. You turn up for the product the advertisement is selling, but it turns out the whole product was ad. There's no "there" there. I've never seen a better embodiment of Baudrillard's conception of simulacrum than this.

The meaningless symbols are so densely packed in this movie I need a convention. Everything in the movie is a stereotype or cliche: a stand-in, an intellectually lazy shorthand reference. I'll be lazy too, and mark stereotypes in my commentary with [brackets].

The beginning is indistinguishable from a trailer. A brief [dawn of man] scene, you know the kind, [stone age people silhouetted against a dawn sky somewhere in Africa], doing [caveman things with the spears and the facepaint], with a [rumbling voiceover] helpfully telling you that it's ["Earth, birthplace of the human race"]. If it were storytelling, it would be rushed, heavy-handed, and contemptuous of the viewer - both showing and telling. But I don't think it is storytelling. It's arranging some symbols (humans, decepticons) into a particular aspect required for later symbolic purposes. The decepticons portrayed in this ancient time are [evil] (with [King Kong-like grabbing] of a feeble human, albeit male), but there is no motive, no narrative. Why would such powerful machines pay any more attention to stone age humans than they would apes, or insects, which they can swat away with similar ease?

Next up: Shanghai, [disaster scene], with [disaster radio news chatter]. Cue [Pentagon command centre], explaining that some black hawks are moving in, while showing some black hawks moving in: Americans aircraft and troops entering Chinese territory, in complete suspension of geopolitical disbelief, no explanation considered necessary. Expository trailer voiceover says "new autobots", while expository camera shot shows new autobots, including [hot girl on bike], [fast car], and [military transport]. "Together, we form an alliance", explains voiceover, while showing human troops in [military transport] (which subsequently transforms). No attempt to explain why squishy soldiers with small arms are going up against fast-moving heavy machinery. What do they hope to achieve with their flying pieces of lead? Would they go up against even a human-engineered tank with such miserable munitions? Nor an explanation for the gunships flying with mere tens of feet clearance from the ground and the surrounding buildings that tower over them, completely negating the tactical advantages of a mobile, hovering cannon and missile platform.

But all is soon revealed. The squishy humans aren't going in to fight, they are going in to be squished, to symbolize human weakness against the machines. After a decepticon slams its fists into some concrete pipe sections, somehow creating a fiery explosion, gunships capable of engaging the enemy with missiles and canons from considerable distance approach low and close enough to be clobbered with a mere wave of mechanical arms. As an alleged depiction of a military engagement, it's beyond ludicrous, laughable on its face. Suspension of disbelief isn't possible: this isn't a battle; it isn't even a simulation of a battle. It's a simulation of battle simulation, an arrangement of symbols of battles. Here are our valiant heroes going into battle; here's our shockingly powerful foe, see how he easily puts our heroes on the back foot; but wait (!) here come our heroes again with reinforcements, to win the day with a bunch of soundbites: ["damn, I'm good!"], ["punk-ass decepticon"], ["any last words?"], "the fallen shall rise again", ["that doesn't sound good"], ["not today!", reload-click, bullet to the head].

That's just the first 8 minutes or so; it goes on for hours (!), with no variation in pacing that you wouldn't also expect in a 30-second movie trailer. Some other commentary roughly concurs with mine, though I didn't enjoy the spectacle or visual feast aspects, primarily because those spectacles are filmed too close to the action, and the subjects, transformed machines, have so many bits and bobs hanging out of them it's hard to tell where one begins and another ends, much like how camouflage breaks up outlines. Trying to figure out what's actually going on within the pace of the editing cuts would give me a headache. Besides, marvelling at the sheer density of signifiers and its generally jaw-dropping empty awfulness is more fun, in a perverse way.

Virtual method interception

2010-09-01T12:00:00.004+01:00

Delphi XE has a new type in Rtti.pas called TVirtualMethodInterceptor. It was originally designed for use in DataSnap authentication scenarios (though I don't think it's currently being used there), but of course, making it only work for that would have been quite a limitation.

What does it do? Essentially, it creates a derived metaclass dynamically at runtime that overrides every virtual method in the ancestor, by creating a new virtual method table and populating it with stubs that intercepts calls and arguments. When the metaclass reference for any instance of the "ancestor" is replaced with this new metaclass, the user can then intercept virtual function calls, change arguments on the fly, change the return value, intercept and suppress exceptions or raise new exceptions, or entirely replace calling the underlying method. In concept, it's somewhat similar to dynamic proxies from .NET and Java. It's like being able to derive from a class at runtime, override methods (but not add new instance fields), and then change the runtime type of an instance to this new derived class.

Why would you want to do this? Two obvious purposes spring to mind: testing and remoting. Mock objects have been in vogue in the testing space in other languages for some time. By intercepting method calls, one may more easily verify that a particular subsystem is calling all the right methods, with the correct arguments, in the expected order; similarly, the subsystem can proceed with the return values from these method calls, without necessarily having to hit the database, the network, etc. for what should be a unit test. Remoting on the basis of method calls is somewhat less useful, especially when an unreliable and latency-prone network gets into the stack, but that's not the only usage point. The virtual method interceptor logic was originally implemented to be used as part of DataSnap authentication, so that a call that comes in from the network can still be checked as its code flow spreads throughout the graph of objects.

Anyhow, here's a simple example to get started:

uses SysUtils, Rtti;
{$apptype console}
type
  TFoo = class
    // Frob doubles x and returns the new x + 10
    function Frob(var x: Integer): Integer; virtual;
  end;

function TFoo.Frob(var x: Integer): Integer;
begin
  x := x * 2;
  Result := x + 10;
end;

procedure WorkWithFoo(Foo: TFoo);
var
  a, b: Integer;
begin
  a := 10;
  Writeln('  before: a = ', a);
  try
    b := Foo.Frob(a);
    Writeln('  Result = ', b);
    Writeln('  after:  a = ', a);
  except
    on e: Exception do
      Writeln('  Exception: ', e.ClassName);
  end;
end;

procedure P;
var
  foo: TFoo;
  vmi: TVirtualMethodInterceptor;
begin
  vmi := nil;
  foo := TFoo.Create;
  try
    Writeln('Before hackery:');
    WorkWithFoo(foo);
    
    vmi := TVirtualMethodInterceptor.Create(foo.ClassType);
    
    vmi.OnBefore := procedure(Instance: TObject; Method: TRttiMethod;
      const Args: TArray<TValue>; out DoInvoke: Boolean; out Result: TValue)
    var
      i: Integer;
    begin
      Write('[before] Calling ', Method.Name, ' with args: ');
      for i := 0 to Length(Args) - 1 do
        Write(Args[i].ToString, ' ');
      Writeln;
    end;
    
    // Change foo's metaclass pointer to our new dynamically derived
    // and intercepted descendant
    vmi.Proxify(foo);
    
    Writeln('After interception:');
    WorkWithFoo(foo);
  finally
    foo.Free;
    vmi.Free;
  end;
end;

begin
  P;
end.

Here's what it outputs:

Before hackery:
  before: a = 10
  Result = 30
  after:  a = 20
After interception:
  before: a = 10
[before] Calling Frob with args: 10 
  Result = 30
  after:  a = 20
[before] Calling BeforeDestruction with args: 
[before] Calling FreeInstance with args:

You'll notice that it intercepts all the virtual methods, including those called during destruction, not just the one I declared. (The destructor itself is not included.)

We can get more ambitious with what it does. I can change the implementation entirely, and skip calling the underlying (i.e. inherited) method body:

procedure P;
var
  foo: TFoo;
  vmi: TVirtualMethodInterceptor;
  ctx: TRttiContext;
  m: TRttiMethod;
begin
  vmi := nil;
  foo := TFoo.Create;
  try
    Writeln('Before hackery:');
    WorkWithFoo(foo);
    
    vmi := TVirtualMethodInterceptor.Create(foo.ClassType);
    
    m := ctx.GetType(TFoo).GetMethod('Frob');
    vmi.OnBefore := procedure(Instance: TObject; Method: TRttiMethod;
      const Args: TArray; out DoInvoke: Boolean; out Result: TValue)
    begin
      if Method = m then
      begin
        DoInvoke := False;
        Result := 42;
        Args[0] := -Args[0].AsInteger;
      end;
    end;

Here, I inhibit the invocation and hard-code the result to 42, while negating the first argument. The proof is in the output:

Before hackery:
  before: a = 10
  Result = 30
  after:  a = 20
After interception:
  before: a = 10
  Result = 42
  after:  a = -10

I could have inhibited the call by raising an exception instead:

    vmi.OnBefore := procedure(Instance: TObject; Method: TRttiMethod;
      const Args: TArray; out DoInvoke: Boolean; out Result: TValue)
    begin
      if Method = m then
        raise Exception.Create('Aborting');
    end;

And output:

Before hackery:
  before: a = 10
  Result = 30
  after:  a = 20
After interception:
  before: a = 10
  Exception: Exception

It's not limited to interception before the logically inherited call, but also interception after the call, again with the opportunity to fiddle with arguments and return value:

    m := ctx.GetType(TFoo).GetMethod('Frob');
    vmi.OnAfter := procedure(Instance: TObject; Method: TRttiMethod;
      const Args: TArray; var Result: TValue)
    begin
      if Method = m then
        Result := Result.AsInteger + 1000000;
    end;

And output:

Before hackery:
  before: a = 10
  Result = 30
  after:  a = 20
After interception:
  before: a = 10
  Result = 1000030
  after:  a = 20

And if the inherited implementation raises an exception, that can even be squashed:

function TFoo.Frob(var x: Integer): Integer;
begin
  raise Exception.Create('Abort');
end;

// ...
    m := ctx.GetType(TFoo).GetMethod('Frob');
    vmi.OnException := procedure(Instance: TObject; Method: TRttiMethod;
      const Args: TArray; out RaiseException: Boolean;
      TheException: Exception; out Result: TValue)
    begin
      if Method = m then
      begin
        RaiseException := False;
        Args[0] := Args[0].AsInteger * 2;
        Result := Args[0].AsInteger + 10;
      end;
    end;

Output:

Before hackery:
  before: a = 10
  Exception: Exception
After interception:
  before: a = 10
  Result = 30
  after:  a = 20

One thing the TVirtualMethodInterceptor class doesn't have, however, is a way to unhook (unproxify) the object. If the object is never unhooked, it's important that the object doesn't outlive the interceptor, because the interceptor needs to allocate executable memory in order to create the little stubs with which it redirects method calls to the events. Fortunately, it's pretty trivial to do:

    PPointer(foo)^ := vmi.OriginalClass;

Another point: the class inheritance chain is changed by the hooking process. This can be shown easily:

//...
    Writeln('After interception:');
    WorkWithFoo(foo);
    
    Writeln('Inheritance chain while intercepted:');
    cls := foo.ClassType;
    while cls <> nil do
    begin
      Writeln(Format('  %s (%p)', [cls.ClassName, Pointer(cls)]));
      cls := cls.ClassParent;
    end;
    
    PPointer(foo)^ := vmi.OriginalClass;
    
    Writeln('After unhooking:');
    WorkWithFoo(foo);
    
    Writeln('Inheritance chain after unhooking:');
    cls := foo.ClassType;
    while cls <> nil do
    begin
      Writeln(Format('  %s (%p)', [cls.ClassName, Pointer(cls)]));
      cls := cls.ClassParent;
    end;
// ...

And output:

Before hackery:
  before: a = 10
  Exception: Exception
After interception:
  before: a = 10
  Result = 30
  after:  a = 20
Inheritance chain while intercepted:
  TFoo (01F34DA8)
  TFoo (0048BD84)
  TObject (004014F0)
After unhooking:
  before: a = 10
  Exception: Exception
Inheritance chain after unhooking:
  TFoo (0048BD84)
  TObject (004014F0)

The feature is primarily an infrastructure piece for advanced libraries, but hopefully you can see that it's not too difficult to get into.

Memory leaks, log analysis and Unix command-line tools

2010-08-30T03:53:00.005+01:00

I had cause recently to tackle a fairly tricky memory leak bug in the Delphi compiler as hosted by the IDE. The test case for the bug was complicated: compiling and running a large portion of the IDE itself. After a compile, subsequent debug runs of the IDE kept on increasing the debugging IDE's memory usage.

The memory profiler in Automated QA's AQtime tool provided a very rough indication of the call stack that allocated the memory. The reason it was very rough, and frankly, not particularly useful, was because the Delphi compiler uses a memory suballocator for performance and complexity reasons. Dcc - the Delphi compiler - has roughly 3 different classes of memory allocation: memory associated with a unit, memory associated with a depth in the call stack, and temporary memory that will be done away with periodically, in particular, memory associated with parsing the syntax tree for any one procedure and generating code for it. What the stack from AQtime did tell me was that the memory was (at least initially) associated with unit allocations. Since the compiler reuses memory as units get freed, the initial allocation isn't necessarily the one that gets leaked

To get better insight into what happened around the allocator, I instrumented it. The Delphi compiler in its debug build has a simple logging system. Every logging point has a string associated with it, and by specifying a list of globs in an environment variable, the compiler will output more or less logging info, according to how those globs match the strings associated with each logging point. For example, a log point inside the memory allocator might look like "dcc.memory.alloc", and another like "dcc.memory.free". A glob like "dcc.memory.*" would then match both of these; alternatively, "*.free;*.alloc" would match both of them, but also other logical allocations and frees that use the same naming convention. Whether or not any logging point is matched by the log glob is usually cached in static variables at each logging point, so there's surprisingly little performance loss even from very aggressive logging.

I ended up with a log file which output every new unit allocation, along with all the unit frees, and some supplementary logging relating to how the compiler managed the state of units - information it used to decide whether or not to free the unit, or keep it around for reuse later. It ended up being about 2.4G in size. That's a little big to try and eyeball, so I used some tools to whittle down the interesting bits.

There's a general pattern I use; probably not the most efficient, but it works well for me because it uses the Unix-standard (Cygwin in my case) command-line tools I use most often, rather than other tools that might be more suited but I'm less familiar with. It generally goes like this:

egrep -o 'interesting regex' log | sed -r 's|.*boring (interesting).*|\1|'

That is, it extracts just the interesting lines out, then only the interesting bits of those lines, using extended regex with egrep, and extended regex with a capture in sed. The sed s command is a substitution; I substitute the entire line with the captured interesting bit.

Using this technique, I extracted every allocation address into one temporary output file and every deallocation address into another. I could then do set operations on them to discover allocations that aren't matched by deallocations:

sort allocs deallocs deallocs | uniq -u > leaks

Sort will bring all the allocations and deallocations together. Uniq, without any arguments, reduces consecutive duplicate lines down to a single line; but with -u, it removes all lines that are part of consecutive duplicates, and leaves the unique lines. By specifying deallocs twice, I guarantee that no deallocations with an unmatched allocation will appear in the output; only allocations with an unmatched deallocation.

Often this is sufficient. But in this case, the enormous amount of churn, thousands of units, meant that duplicate memory locations were showing up, associated with different units. How did I know this? I did this:

fgrep -f leaks log | egrep -o 'interesting etc.' ...

Fgrep searches for fixed strings rather than regexes, which is much faster. The -f argument tells fgrep to load the list of fixed strings from the subsequent file argument, one string per line. This is a quick way of whittling down a log file to only those lines containing one of possibly thousands of strings.

When slightly more processing is needed, a different approach can work, using bash:

for item in $(<leaks); do fgrep "$item" log | ...; done > output

That works well if you don't expect $item to contain spaces; bash breaks it up on each whitespace boundary, rather than each line. For lines, I prefer this:

cat leaks | while read -r line; do ...; done > output

I use the redundant cat at the start for readability and ease of use; bash would otherwise need the input redirector (<) at the end of the command. The bash command "read" loads a line from standard input into the specified variable. The -r argument prevents it from messing with the string, doing funny things with backslashes, which, in my experience, is almost always undesirable.

Anyhow, to get around the duplicate problem, I changed tack. I modified my filtering so that I had a simple text file consisting of lines like "alloc <address>" and "free <address>" in chronological order of the event, and then wrote a simple program which kept track of each address in a hash table, so that it wouldn't be fooled by reuse of addresses. This got me an unambiguous list of leaked allocations.

Once I had a reliable means of extracting the addresses of the leaks, I scripted the process (not much more than a list of command-lines in a bash script) so that I could easily experiment with deeper and more focused logging. This was the real meat of the process of fixing the bug, and involved a lot of scanning the log file with the "less" pager's search forward (/) and backward (?) commands, tracing the lifetime of various units. But the fact that I knew what to search for, and could whittle down the log file as necessary, was down to what had come earlier from the command-line tools.

I don't know how other programmers tackle these kinds of problems, but these are some of the tools in my toolbox, and they come in surprisingly useful every day. In many ways, debugging is the least talked-about discipline in software engineering, and I think it would be of great benefit to us all to share more of our experiences and techniques.

Android: Momentum and Apps

2010-05-25T10:05:00.003+01:00

I'm liking the current momentum behind Android. I'm sure Apple will come out with their new phone soon, and the pendulum will swing a bit, but it's definitely a two horse race, and Apple isn't out of sight, not by a long shot.

I got my Nexus One from http://www.google.com/phone a few months ago, to replace my aging K800i (which still takes better photos than the Nexus One, or the iPhone, or indeed most phones). Since I got my phone directly from Google, it was easy to update to the latest Froyo, which got rid of some of my bigger annoyances on the device. Most tedious in previous versions was the need to individually select and authorize every application when an update showed up. Most days I see between two and five updated applications, and updating any given application takes around 30 seconds, so it was turning into a chore. Froyo is also much smoother in its transitions; it's the way Eclair should have been.

The Android app store (Marketplace) has gotten some criticism, but I don't know how truly meaningful those criticism are, as I've gotten applications primarily based on recommendations, or searching the store with intent, rather than browsing the store. I recently had occasion to count the number of apps I have installed, and if you judge by Android's app management screen, it's now up to 70 (I have 93 icons in my app icon scroller view). I thought I'd list a few of the best ones, as a way of aggregating my own perspective from the different recommended lists I've seen. Some of these applications are not free, but as a developer I don't baulk at paying the small amounts charged, especially since returning for a refund is built into the marketplace if you don't like the app.

ES File Explorer is probably the single application that's most responsible for me preferring Android to iPhone. It's a file browser, but more than that: it can browse Windows (SMB) network shares, as well as FTP and Bluetooth. That means I can copy music, movies etc. on and off my device to and from my NAS. I find iTunes to be a tedious waste of memory and processes, not to mention it wants to update with huge downloads practically every second week, incorporating media players and web browsers I don't want. Crapware. Being able to take control of the media upload and download experience is wonderful, and makes me feel like my phone is more than a locked-down toy.

I complement it with Astro File Manager, which has better support for photo management and a built-in image viewer (which supports image view intents, so it can actually be used by ES File Explorer to view photos). I'm not a big fan of Nexus One's stock Gallery app (by CoolIris) - lots of gloss, but slow to index photos if you've taken a bunch. Astro can also act as a file selection agent for other applications that browse for an image, such as image editors.

Another photo viewer is B&B Gallery. It was one of the first to support multi-touch, manually implemented before the OS got support. An advantage it has over the built-in Gallery is that it doesn't downsample loaded photos, so you can zoom in and check the details, rather than quickly getting lost in blur. As a gallery app, however, it's not particularly pretty. I find file management superior, especially as you don't have to wait as thumbnails from all over the place get loaded, but can classify into directories, etc.

Act 1 Video Player is an excellent replacement for the stock video player. It doesn't add any more decoding capabilities, but it has better affordances in its UI, especially with its touch-based seeking support. Best feature: swiping left and right in the center of the screen seeks back and forth through the video.

NewsRob is an offline RSS reader that synchronizes with Google Reader. It has configurable caching, so you can have it download images which are linked from the RSS (a problem with Google Reader's own offline version using Gears, ironically), up to caching the full web page associated with that RSS item. Excellent for public transport.

A major annoyance with the iPod Touch (and also the iPhone) for me was the auto-rotation. I almost never want to rotate the view, and it always ends up rotating when I'm lying down, or otherwise not in front of a computer. I was only able to solve this problem on the iPod Touch by jailbreaking it. Android has a setting for this, but for easier access to it I use the AutoRotate widget. This lets you put a 1x1 widget anywhere which toggles the auto-rotate setting on a tap.

Some games are useful for passing idle moments. Robo Defense is quite addictive tower defense with RPG-like elements; you earn what are essentially XP points, and can spend them on incremental upgrades, so there's a campaign-like aspect to the gameplay. Replica Island is a classic-style platformer which is particularly ergonomic on the Nexus One, using the scroll ball for directional control. As an aside, controls are one of the weakest elements of most iPhone games - it badly needs more physical buttons. And Nesoid, an NES emulator, is nice in principle, but a better control system is needed.

Artistic diversions: DoodleDroid is a finger-painting app with configurable brush dynamics, so with care, you can get some interesting impressionistic images out of it. Simpler, more like coloured markers than paint, is Draw!.

Of course, there are the bar code apps, like ShopSavvy, probably the most integrated when you have buying intent, though its local shop search isn't very localized, even when in London; ZXing Barcode Scanner, which runs more general web searches based on barcodes; Google Shopper and Google Goggles also do barcodes, but I feel they're weaker, and Goggles is mostly a gimmick (IMO).

Google Sky Map is pretty neat - the way it uses the accelerometer to overlay constellations etc. is probably the neatest augmented reality-style implementation I've seen, even though it doesn't overlay on a video image from the camera. Layar is the probably the canonical implementation, but I find it to be too gimmicky in practice, having to walk around like an idiot with a phone held out in front of you. At least with stars, you're normally standing still and looking into the sky.

Google Translate is another essential app. It's tantalizingly close to real-time speech to speech translation; as it is, you can speak into it and at a button press do text to speech on the translation, providing the speech recognition was good. My girlfriend tells me it can be overly literal for German, however.

Wifi Analyzer helped me get better channel placement on my home wifi access points. Really neat live view of signal strength for all the different APs in your area, even ones too faint to actually connect to.

Arity is a simple expression-based calculator which can graph simple non-parametric functions in two and three dimensions. By non-parametric, I mean you give it an expression using x, or x and y, and it plots the result of the expression as y, or z, in a 2D plane or 3D volume. You can't plot circles with it, for example.

ConnectBot is a SSH client, useful for remote administration when you're really stuck for connectivity. Doing anything serious on the command line without access to a keyboard is insanity, of course. When the job you're trying to do is simpler - a single command over SSH - ServerAssistant is a better approach.

If you're interested in programming your life, Locale can trigger events based on conditions. Conditions are one or more of location, time, orientation, calls by contacts and battery state. Settings include wallpaper, ringtone, screen brightness, wifi enabled or not, volume, bluetooth, but also actions published by third-party applications. For example, NewsRob can synchronize based on a Locale trigger. And if you've installed ASE, the Android Scripting Environment, you can run arbitrary scripts - bash, python, ruby, etc. - on a trigger. The sample scripts available for ASE include invoking text to speech to say the time and the current weather, toggling airplane mode, showing notifications, etc. Locale is a lot less useful if you have a more flexible schedule, but if you're tied in to a timetable, it makes a lot of sense.

Finally, a battery widget: Battery Left. I don't use task managers or killers; I've found that it's better to let Android do its thing and kill what it needs to kill, when it chooses to do it. I get about 46 hours on average battery, but I tend to recharge before 36 hours have gone past. You can drop this widget as a 1x1 (or 2x1) visual indicator of battery left, with configurable detailed textual data: estimated time before battery dead, estimated time of day of dead battery, estimated battery %, etc. It monitors battery performance, so it should straighten the curve that batteries self-report - I've often seen batteries say they have three-quarters battery for ages, and then run out the remainder quite suddenly, etc.

Obviously, I have many more applications installed than I've mentioned here, but they tend to be single-purpose location-based ones that have less general applicability, or ones I don't use as often and can't in good conscience recommend. But I can say that all of the above work pretty well for me, and it's notable that many of them would contravene Apple's developer policy, so for me at least, app availability for the iPhone isn't the killer advantage it's made out to be.

Locations vs Values: using RTTI to work with value types

2010-05-11T18:21:00.003+01:00

Delphi's Rtti unit is designed in substantial part around TValue, a kind of hold-all record that should be capable of containing almost any Delphi value, along with type information for that value. However, this means that when you're working with value types, such as static arrays and records, modifying the values when stored in a TValue is modifying that copy, stored inside the TValue. If you want to manipulate a field (F1) of a record which is itself a field (F2) of another type, you need to first copy the F2 field's value out into a TValue, then modify F1 in the TValue, and then copy it back in to the original F2 field.

As an aside: TValue.MakeWithoutCopy does not relate to this copying behaviour, but is rather for managing reference counts with strings and interfaces and other managed types. This is particularly important when marshalling parameters to and from stack frames, where logical copies sometimes should be made, and sometimes not.

However, working with values in TValue all the time is not necessarily the most efficient technique. By adding another layer of indirection, we can improve things: instead of working with values, we can work with locations.

This can be encapsulated fairly trivially using the current RTTI support. I hacked up a TLocation type which represents a typed location analogously to how TValue represents a value:

type
  TLocation = record
  private
    FLocation: Pointer;
    FType: TRttiType;
  public
    class function FromValue(C: TRttiContext; const AValue: TValue): TLocation; static;
    class function FromAddress(ALocation: Pointer; AType: TRttiType): TLocation; static;
    function GetValue: TValue;
    procedure SetValue(const AValue: TValue);
    function Follow(const APath: string): TLocation;
    function Dereference: TLocation;
    function Index(n: Integer): TLocation;
    function FieldRef(const name: string): TLocation;
  end;

For ease of use, it uses TRttiType. If it were to be fully as flexible as TValue, it would use PTypeInfo instead, like TValue does. However, using the RTTI wrapper objects makes life a lot easier.

Here it is in use:

type
  TPoint = record
    X, Y: Integer;
  end;
  TArr = array[0..9] of TPoint;

  TFoo = class
  private
    FArr: TArr;
    constructor Create;
    function ToString: string; override;
  end;

{ TFoo }

constructor TFoo.Create;
var
  i: Integer;
begin
  for i := Low(FArr) to High(FArr) do
  begin
    FArr[i].X := i;
    FArr[i].Y := -i;
  end;
end;

function TFoo.ToString: string;
var
  i: Integer;
begin
  Result := '';
  for i := Low(FArr) to High(FArr) do
    Result := Result + Format('(%d, %d) ', [FArr[i].X, FArr[i].Y]);
end;

procedure P;
var
  obj: TFoo;
  loc: TLocation;
  ctx: TRttiContext;
begin
  obj := TFoo.Create;
  Writeln(obj.ToString);
  
  ctx := TRttiContext.Create;
  
  loc := TLocation.FromValue(ctx, obj);
  Writeln(loc.Follow('.FArr[2].X').GetValue.ToString);
  Writeln(obj.FArr[2].X);
  
  loc.Follow('.FArr[2].X').SetValue(42);
  Writeln(obj.FArr[2].X); // observe value changed
  
  // alternate syntax, not using path parser
  loc.FieldRef('FArr').Index(2).FieldRef('X').SetValue(24);
  Writeln(obj.FArr[2].X); // observe value changed again
  
  Writeln(obj.ToString);
end;

Here's most of the implementation:

{ TLocation }

type
  PPByte = ^PByte;

function TLocation.Dereference: TLocation;
begin
  if not (FType is TRttiPointerType) then
    raise Exception.CreateFmt('Non-pointer type %s can''t be dereferenced', [FType.Name]);
  Result.FLocation := PPointer(FLocation)^;
  Result.FType := TRttiPointerType(FType).ReferredType;
end;

function TLocation.FieldRef(const name: string): TLocation;
var
  f: TRttiField;
begin
  if FType is TRttiRecordType then
  begin
    f := FType.GetField(name);
    Result.FLocation := PByte(FLocation) + f.Offset;
    Result.FType := f.FieldType;
  end
  else if FType is TRttiInstanceType then
  begin
    f := FType.GetField(name);
    Result.FLocation := PPByte(FLocation)^ + f.Offset;
    Result.FType := f.FieldType;
  end
  else
    raise Exception.CreateFmt('Field reference applied to type %s, which is not a record or class',
      [FType.Name]);
end;

function TLocation.Follow(const APath: string): TLocation;
begin
  Result := GetPathLocation(APath, Self);
end;

class function TLocation.FromAddress(ALocation: Pointer;
  AType: TRttiType): TLocation;
begin
  Result.FLocation := ALocation;
  Result.FType := AType;
end;

class function TLocation.FromValue(C: TRttiContext; const AValue: TValue): TLocation;
begin
  Result.FType := C.GetType(AValue.TypeInfo);
  Result.FLocation := AValue.GetReferenceToRawData;
end;

function TLocation.GetValue: TValue;
begin
  TValue.Make(FLocation, FType.Handle, Result);
end;

function TLocation.Index(n: Integer): TLocation;
var
  sa: TRttiArrayType;
  da: TRttiDynamicArrayType;
begin
  if FType is TRttiArrayType then
  begin
    // extending this to work with multi-dimensional arrays and non-zero
    // based arrays is left as an exercise for the reader ... :)
    sa := TRttiArrayType(FType);
    Result.FLocation := PByte(FLocation) + sa.ElementType.TypeSize * n;
    Result.FType := sa.ElementType;
  end
  else if FType is TRttiDynamicArrayType then
  begin
    da := TRttiDynamicArrayType(FType);
    Result.FLocation := PPByte(FLocation)^ + da.ElementType.TypeSize * n;
    Result.FType := da.ElementType;
  end
  else
    raise Exception.CreateFmt('Index applied to non-array type %s', [FType.Name]);
end;

procedure TLocation.SetValue(const AValue: TValue);
begin
  AValue.Cast(FType.Handle).ExtractRawData(FLocation);
end;

To make it slightly easier to use, and slightly more fun for me to write, I also wrote a parser - the Follow method, which is implemented in terms of GetPathLocation:

function GetPathLocation(const APath: string; ARoot: TLocation): TLocation;

  { Lexer }
  
  function SkipWhite(p: PChar): PChar;
  begin
    while IsWhiteSpace(p^) do
      Inc(p);
    Result := p;
  end;

  function ScanName(p: PChar; out s: string): PChar;
  begin
    Result := p;
    while IsLetterOrDigit(Result^) do
      Inc(Result);
    SetString(s, p, Result - p);
  end;

  function ScanNumber(p: PChar; out n: Integer): PChar;
  var
    v: Integer;
  begin
    v := 0;
    while (p >= '0') and (p <= '9') do
    begin
      v := v * 10 + Ord(p^) - Ord('0');
      Inc(p);
    end;
    n := v;
    Result := p;
  end;

const
  tkEof = #0;
  tkNumber = #1;
  tkName = #2;
  tkDot = '.';
  tkLBracket = '[';
  tkRBracket = ']';
  
var
  cp: PChar;
  currToken: Char;
  nameToken: string;
  numToken: Integer;
  
  function NextToken: Char;
    function SetToken(p: PChar): PChar;
    begin
      currToken := p^;
      Result := p + 1;
    end;
  var
    p: PChar;
  begin
    p := cp;
    p := SkipWhite(p);
    if p^ = #0 then
    begin
      cp := p;
      currToken := tkEof;
      Exit(currToken);
    end;
    
    case p^ of
      '0'..'9':
      begin
        cp := ScanNumber(p, numToken);
        currToken := tkNumber;
      end;
      
      '^', '[', ']', '.': cp := SetToken(p);
      
    else
      cp := ScanName(p, nameToken);
      if nameToken = '' then
        raise Exception.Create('Invalid path - expected a name');
      currToken := tkName;
    end;
    
    Result := currToken;
  end;
  
  function Describe(tok: Char): string;
  begin
    case tok of
      tkEof: Result := 'end of string';
      tkNumber: Result := 'number';
      tkName: Result := 'name';
    else
      Result := '''' + tok + '''';
    end;
  end;
  
  procedure Expect(tok: Char);
  begin
    if tok <> currToken then
      raise Exception.CreateFmt('Expected %s but got %s', 
        [Describe(tok), Describe(currToken)]);
  end;

  { Semantic actions are methods on TLocation }
var
  loc: TLocation;
  
  { Driver and parser }
  
begin
  cp := PChar(APath);
  NextToken;
  
  loc := ARoot;
  
  // Syntax:
  // path ::= ( '.' <name> | '[' <num> ']' | '^' )+ ;;
  
  // Semantics:
  
  // '<name>' are field names, '[]' is array indexing, '^' is pointer
  // indirection.
  
  // Parser continuously calculates the address of the value in question, 
  // starting from the root.
  
  // When we see a name, we look that up as a field on the current type,
  // then add its offset to our current location if the current location is 
  // a value type, or indirect (PPointer(x)^) the current location before 
  // adding the offset if the current location is a reference type. If not
  // a record or class type, then it's an error.
  
  // When we see an indexing, we expect the current location to be an array
  // and we update the location to the address of the element inside the array.
  // All dimensions are flattened (multiplied out) and zero-based.
  
  // When we see indirection, we expect the current location to be a pointer,
  // and dereference it.
  
  while True do
  begin
    case currToken of
      tkEof: Break;
      
      '.':
      begin
        NextToken;
        Expect(tkName);
        loc := loc.FieldRef(nameToken);
        NextToken;
      end;
      
      '[':
      begin
        NextToken;
        Expect(tkNumber);
        loc := loc.Index(numToken);
        NextToken;
        Expect(']');
        NextToken;
      end;
      
      '^':
      begin
        loc := loc.Dereference;
        NextToken;
      end;
      
    else
      raise Exception.Create('Invalid path syntax: expected ".", "[" or "^"');
    end;
  end;
  
  Result := loc;
end;

The principle can be extended to other types and Delphi expression syntax, or TLocation may be changed to understand non-flat array indexing, etc.

This post was inspired by this question on Stack Overflow, and some similar questions to it that popped up over the past few weeks.

Programming font for VS2010

2010-04-19T11:19:00.008+01:00

So, Visual Studio 2010 shipped. Now I have a problem: what font to use? My old standby, Dina, is a bitmap font so it doesn't work with the WPF text editor in VS2010.

Some things I look for in a programming font:

High information density - vertical height in particular. For example, I use Dina at 8pt.
Crisp, even lines
Strong distinction between bold and regular (for lexical highlighting)
Clearly unambiguous letters: l,1,0,O, and the like.
Balanced operators - good placement for <, >, {, }, etc.

Here's Dina 8pt in VS2008:

Here's Consolas at 8pt in VS2010:

(At least, I think that's 8pt. I have zoomed the editor in and out a little with Ctrl+Mouse Wheel, but there doesn't seem to be a zoom reset...

Here's Consolas 9pt in VS2010:

Consolas is quite constrained on the horizontal. It looks horrible at 8pt, and is still slightly taller than Dina 8pt. Even at 9pt though, to my eyes, it suffers quite badly with comparison to Dina. The bold of the comment and digits is almost unnoticeable. 'M' and 'm' are very weak, probably because of the narrowness. The vertical on the 'F' of 'Func' is weak, as is the vertical on 'r'. These are in part properties of ClearType subpixel rendering, which looks slightly different from monitor to monitor and depending on configuration, but even with the configuration selected for its heaviest rendering, it looks poor on my system. Overall, the effect is washed out and slightly blurry.

Proggy Fonts are another contender. These have TTF hinted versions of what amount to bitmap fonts, so they try and sneak older rendering in through the back door. Here's Proggy Clean Slashed Zero with Bold Punctuation (Visual Studio can bold operators (and I do - and make them white, to stand out even more), but it doesn't include [], {}, () as operators, unfortunately):

This is probably the most palatable option for me, but it's still not quite as good as Dina. It's the same height, probably because Dina was based on Proggy; but the things I don't like about it most are things that Dina fixed, in particular the oddly elongated < and >, the lazy looking 's', and the "gappy" look of the bold - contrast the comment in Proggy vs Dina. Other differences incude the leg on the 'R' and the general way the capitals are slightly overly broad. Another oddity is however ClearType has interacted with its hinting, the font has ended up tinted with green.

Proggy Clean SZBP is the font I'll stick with for the moment, until I see a better option, or a better translation of Dina to TTF than this one, which is tuned for 10pt Dina, not the size I use.

JEDI newsgroup change

2010-03-23T22:10:00.002Z

I got word that the JEDI newsgroup changed after the old forums.talkto.net server died. The new server is at:

news.delphi-jedi.org

That's nntp on standard port 119. Please update your favorite news reader to this new server.

CrashPlan for Backup on Nexenta

2010-03-13T17:35:00.004Z

For some time, I've been using cron jobs with rdiff-backup on Cygwin for backups. The cron job runs on a Windows server I have on my home network and iteratively mounts remote Windows shares (if they're present) and runs rdiff-backup over them, with the destination also being local. Then the job runs rsync to mirror this backup to my Nexenta NAS running ZFS raidz.

This solution gives me a fair amount of local redundancy: two separate machines, with two copies of the backup data, plus the RAID-5-like redundancy and checksumming integrity that ZFS provides. Rdiff-backup is quite reassuring with respect to restores too: it stores files in the filesystem directly, along with differences (the rdiff bit) so you can go back in time. That means that restoring is as simple as copying the files straight out of the backup and deleting the rdiffs.

Of course, a backup strategy isn't solid without a remote copy. Today, I finished configuring CrashPlan, a really neat backup solution built using Java. You can read about the features etc. of CrashPlan on the website - I heard about it from the Java Posse podcast, episode 298. Initially, I opened an Amazon S3 account, and was considering mirroring my backups to S3 with s3sync, but after I evaluated CrashPlan, it looked like it made more sense than further pursuing my homegrown approach. Not only is it cheaper than S3 for my data (I guess they depend on overselling like ISPs), but CrashPlan has features that make it work well in my case.

The fact that it's primarily Java meant I could install it on my Nexenta box. CrashPlan don't have an installer for Nexenta, but they do have ones for Linux (LSB) and Solaris, and Nexenta is like a hybrid. I'm documenting the steps here in case I need to set it all up again, though hopefully not for a restore.

I'm running NexentaCore NCP 2, which doesn't come with Java. Installing a JDK (overkill, but I wanted to test the Java environment with a simple hello-world):

$ sudo apt-get install sun-java6-jdk

I was running a release candidate of Nexenta and I had to do an apt-get update and upgrade to resolve all necessary dependencies, but it was fairly stress free because Nexenta's apt-clone checkpointed the root file system with a ZFS snapshot. I did lose my almost half-year of uptime though - my Nexenta machine has been the most dependable of all my machines, in both hardware and software.

Installing CrashPlan itself needs bits from both the Linux and Solaris installers. I downloaded both, and unpacked both. In the Linux install, I ran the provided install.sh and followed the steps, putting it in /usr/local, with daemon init script in /etc/init.d and runlevel symlink in /etc/rc3.d. But the Linux install isn't enough. In particular, the init script assumes GNU ps, but Nexenta uses Solaris ps. So I swapped in CrashPlanEngine (the target of the init script symlink) from the Solaris installer in the place of the installed CrashPlanEngine that was here:

/usr/local/crashplan/bin/CrashPlanEngine

But that wasn't enough. CrashPlan loads a library called libjtux via JNI, a kind of POSIX API for Java programmers who want direct access to the OS. The libjtux.so from the Linux install was linking against libc.so.6, assuming GNU C library versioning. Replacing libjtux.so with the version from Solaris, linking against plain libc.so, solved this problem - here:

/usr/local/crashplan/libjtux.so

Finally, I had to configure CrashPlan. My Nexenta install is headless - all my interaction with it is either over Samba shares, HTTP for wiki servers etc., and of course ssh for everything else. Here's one of the really neat features of CrashPlan: the user interface for configuration is a client that depends on a single TCP connection with the local backup server. All I had to do is get the client to connect to a different local port, and tunnel that port to Nexenta using SSH, after enabling TCP forwarding in Nexenta in /etc/ssh/sshd_config. This bit is described on CrashPlan's site describing how to configure a headless client.

I'm running CrashPlan+, a for-pay version of the engine, on two machines - my main desktop and my Nexenta box - to get all the encryption, compression, deduplication etc. goodness. And considering that CrashPlan supports peer to peer backup, I may simply replace my existing ad-hoc rdiff-backup approach with local CrashPlan backups, as CrashPlan supports multiple destinations for backups, as well as receiving backups from other machines.

A key limitation of CrashPlan, and one that I found particularly annoying, is that the Windows client doesn't support network shares at all, in any shape or form - whether they're mapped to drive letters or not. The backup engine runs under the SYSTEM account, so it doesn't have network credentials, and also means it may not be able to access all the files you're trying to back up - especially EFS encrypted files. (CrashPlan doesn't seem to use Windows' EFS backup capability, e.g. ReadEncryptedFileRaw.) I changed the CrashPlan engine's service account to my own account to try and close this hole, but still no go on accessing network shares. This meant that I had to get CrashPlan running on my Nexenta box in order to store local backups on ZFS, should I so choose.

But apart from that, I've been impressed with CrashPlan's feature set and usability.

Multidimensional Separation of Concerns, or Matrix Inheritance

2010-02-03T19:35:00.003Z

I just spotted a paper that I didn't know existed before. Abstract:

Done well, separation of concerns can provide many software engineering benefits, including reduced complexity, improved reusability, and simpler evolution. The choice of boundaries for separate concerns depends on both requirements on the system and on the kind(s) of decomposition and composition a given formalism supports. The predominant methodologies and formalisms available, however, support only orthogonal separations of concerns, along single dimensions of composition and decomposition. These characteristics lead to a number of well-known and difficult problems.

This paper describes a new paradigm for modeling and implementing software artifacts, one that permits separation of overlapping concerns along multiple dimensions of composition and decomposition. This approach addresses numerous problems throughout the software lifecycle in achieving well-engineered, evolvable, flexible software artifacts and traceability across artifacts.

I came up with a remarkably similar concept I called matrix inheritance in a previous job. Here's one description I've written up out there on the web:

[This is a description of a symptom of the problem.] Nested if-then-else can introduce non-essential complexity merely by having dead nested cases which are actually obviated by outer cases; looking at a complex version of this code, it can become quite difficult to see where exactly the code is supposed to flow under what circumstances, as there can seem to be conflicting assumptions in different areas.

Once upon a time I invented a scheme to solve this problem in the best way I thought possible, and called it "matrix inheritance". The problem with inheritance and subclassing is that it only handles a single dimension of customization. Suppose you have two dimensions, genre and type, such as [comedy, drama] and [movie, series]. If you were to try and classify any given thing under a classical type breakdown, you could subclass by one axes or the other, but you would need to duplicate subclassing for the remaining axes. So, you could end up with Programme, Comedy <: Programme, Drama <: Programme, but then you'd need ComedyMovie, ComedySeries, DramaMovie, DramaSeries, duplicating the kind axis in the two different branches.

The matrix inheritance concept basically takes the cartesian product of all option axes, essentially modelling it as an n-dimensional space, and then applies behaviour to sub-spaces of this space. So, you could apply conditions to [drama,*] and [*, series], with these two representing slices of the example 2-dimensional space described above. The advantage of modelling things this way is that it is declarative: you can analyse overlaps and identify un-covered space.

Here's the original post I made on comp.compilers when looking for related work. Here's a brief excerpt:

Object-oriented techniques have been rejected because they constrain me to using a fixed order of dimensions for reuse and overriding. A possible solution presents itself:

1. Creating a notional Cartesian-product of all dimensions of customization.

2. Overriding based on the application of rules whose scope is defined by sets described by a simple language: by example, '{a,b}' represents the set containing a and b, while '*' represents the set containing all the values for that dimension.

One-liner RAII in Delphi

2010-01-29T19:18:00.006Z

Some C++ aficionados point at the ability, in C++, to create an object such that the creation allocates some kind of resource, and the destruction frees the resource, with much glee. The idiom is RAII: Resource Acquisition Is Initialization. The technique can be a useful, albeit somewhat opaque, way of acquiring a resource for the duration of a block of code and relinquishing the resource upon exiting the block. It's C++'s equivalent of Delphi / Java / C# / SEH's try / finally blocks (though of course C#'s "using" statement is an even closer analogue).

Delphi has a similar mechanism in the form of deterministic reference counting for interfaces. This can be (ab)used to functionally implement almost exactly the same technique as C++. The degree to which it is useful, however, is moderated by readability issues; RAII doesn't necessarily employ a visible nesting, and rather depends on the implied nesting of the scope in which it's used.

Anyway, here's a way of implementing RAII in Delphi, for people to whom the technique may not have occurred yet. It relies on defining a general-purpose class which implements an interface, and whose death will be triggered by scope exit:

type
  TScopeExitNotifier = class(TInterfacedObject)
  private
    FProc: TProc;
  public
    constructor Create(const AProc: TProc);
    destructor Destroy; override;
  end;

constructor TScopeExitNotifier.Create(const AProc: TProc);
begin
  FProc := AProc;
end;

destructor TScopeExitNotifier.Destroy;
begin
  if Assigned(FProc) then
    FProc;
  inherited;
end;

function MakeScopeExitNotifier(const AProc: TProc): IInterface;
begin
  Result := TScopeExitNotifier.Create(AProc);
end;

I would generally recommend hiding the actual class in the implementation-section of a unit - the functional interface of MakeScopeExitNotifier ought to be sufficient. Using this function, we can now implement a one-liner RAII equivalent of the following code:

  Writeln('Disable controls on ', {ASurface});
  try
    // (user code)
  finally
    Writeln('Enable controls on ', {ASurface});
  end;

Of course, I'm using strings etc. for simplicity, so that the demo translation is compilable. Here is the definition of the function which will be called to form the one-liner:

function DisableEnableControls(const ASurface: string): IInterface;
begin
  Writeln('Disable controls on ', ASurface);
  Result := MakeScopeExitNotifier(procedure
  begin
    Writeln('Enable controls on ', ASurface);
  end);
end;

And here it is in action:

procedure P;
begin
  DisableEnableControls('Foo');
  DisableEnableControls('Bar');
  Writeln('Controls on Foo and Bar are disabled now');
end;

Because of the way Delphi's deterministic reference counting and destruction works, Foo and Bar will be released in reverse order of construction, as expected for RAII. Functions that return an interface value in Delphi are implemented behind the scenes as procedures that take an out Result parameter; these are in effect hidden variables that keep the return values alive until the scope is exited.

The output of the program is as follows:

Disable controls on Foo
Disable controls on Bar
Controls on Foo and Bar are disabled now
Enable controls on Bar
Enable controls on Foo

Of course, it's not necessarily clear what DisableEnableControls(string) would do, and how it protects the scope. That's why I wouldn't necessarily recommend using this technique, except to counter C++-ite arguments. Using anonymous methods directly would seem to be a more readable approach in general, something along these lines:

procedure DisableEnableControls(const ASurface: string; const ACB: TProc);
begin
  Writeln('Disable controls on ', ASurface);
  try
    if Assigned(ACB) then
      ACB;
  finally
    Writeln('Enable controls on ', ASurface);
  end;
end;

procedure P;
begin
  DisableEnableControls('Foo', procedure
  begin
    DisableEnableControls('Bar', procedure
    begin
      Writeln('Controls are disabled now.');
    end);
  end);
end;

Output is the same as earlier. The extra complexity / verbosity of this abstraction over and above a literal try/finally would of course be more justified if the logic in the place of Enable and Disable sections were more involved, such as possibly setting up and rolling back transactions, etc.

However, the functionality of MakeScopeExitNotifier() routine is actually useful in the context of anonymous methods, because by capturing a variable containing the return value, you can get informed as to when the scope that created your anonymous method dies. This can be useful to e.g. free any objects that were allocated when the anonymous method was created:

function FreeOnExit(const Args: array of TObject): IInterface;
var
  toFree: TArray<TObject>;
begin
  // copy open array to toFree because open arrays can't be captured
  SetLength(toFree, Length(Args));
  Move(Args[0], toFree[0], Length(Args) * SizeOf(Args[0]));
  
  Result := MakeScopeExitNotifier(procedure
  var
    i: Integer;
  begin
    Writeln('FreeOnExit is freeing objects');
    for i := 0 to High(toFree) do
      toFree[i].Free;
  end);
end;

procedure Use(const x: IInterface);
begin
end;

function Q: TProc;
var
  onDie: IInterface;
  obj: TObject;
begin
  obj := nil;
  onDie := FreeOnExit([obj]);
  Writeln('Allocating an object');
  obj := TObject.Create;
  Result := procedure
  begin
    Use(onDie); // cause onDie to be captured
    Writeln(Format(
      'Inside callback, obj still alive: %p: %s',
      [Pointer(obj), obj.ToString]));
  end;
end;

procedure P;
var
  r: TProc;
begin
  Writeln('Before Q');
  r := Q();
  Writeln('Invoking result of Q');
  r;
  Writeln('Clearing result of Q');
  r := nil;
  Writeln('Result is cleared');
end;

The output is something like:

Before Q
Allocating an object
Invoking result of Q
Inside callback, obj still alive: 00970D20: TObject
Clearing result of Q
FreeOnExit is freeing objects
Result is cleared

This technique, capturing a variable of an interface or other deterministically lifetime-managed type, is essential for flexibility in cleaning up any resources that an anonymous method needs to for its lifetime. Note, however, that there can be a gotcha: the following alternative, using MakeScopeExitNotifier directly, will not work:

// <BROKEN CODE DO NOT USE>
function Q: TProc;
var
  onDie: IInterface;
begin
  onDie := MakeScopeExitNotifier(procedure
  begin
    Writeln('died!');
  end);
  Result := procedure
  begin
    Use(onDie);
  end;
end;
// </BROKEN CODE DO NOT USE>

The reason it's broken is that the anonymous method that's handed off to MakeScopeExitNotifier will itself keep the scope alive. So in order to make use of MakeScopeExitNotifier for this particular purpose, the anonymous method passed to it needs to be in a different scope.

Using anonymous methods in method pointers

2010-01-20T18:12:00.002Z

Anonymous methods may have associated state. In particular, all variables that an anonymous method captures need to be kept alive so long as the anonymous method is callable. For this reason, anonymous methods are implemented with a lifetime management approach: anonymous methods are actually methods on an object which implements COM-style reference counted interfaces. Method references are interface references with a single method called Invoke.

If one badly wants to store an anonymous method in a method pointer, this information can be used to shoehorn it in. Here's how it can be done:

procedure MethRefToMethPtr(const MethRef; var MethPtr);
type
  TVtable = array[0..3] of Pointer;
  PVtable = ^TVtable;
  PPVtable = ^PVtable;
begin
  // 3 is offset of Invoke, after QI, AddRef, Release
  TMethod(MethPtr).Code := PPVtable(MethRef)^^[3];
  TMethod(MethPtr).Data := Pointer(MethRef);
end;

This procedure will take a method reference as the first argument, and then extract the two crucial pieces of data needed to put into a method pointer: the value to be passed as the first argument (the method, or interface, reference), and the code address to be called (the value of the Invoke entry in the interface's vtable).

The procedure can be used as follows. Note that the method reference still needs to be kept alive somewhere as long as the method pointer is callable to avoid premature disposal of the heap-allocated object:

type
  TMeth = procedure(x: Integer) of object;
  TMethRef = reference to procedure(x: Integer);
  
function MakeMethRef: TMethRef;
var
  y: Integer;
begin
  y := 30;
  Result := procedure(x: Integer)
  begin
    Writeln('x = ', x, ' and y = ', y);
  end;
end;

procedure P;
var
  x: TMethRef;
  m: TMeth;
begin
  x := MakeMethRef();
  MethRefToMethPtr(x, m);
  Writeln('Using x:');
  x(10);
  Writeln('Using m:');
  m(10);
end;

On the other hand, if the anonymous method's body never captures any variables, then it's not necessary to keep the method reference around. This loses much of the benefits of anonymous methods, but it does prove the point:

uses SysUtils, Forms, StdCtrls, Dialogs, classes;

procedure MethRefToMethPtr(const MethRef; var MethPtr);
type
  TVtable = array[0..3] of Pointer;
  PVtable = ^TVtable;
  PPVtable = ^PVtable;
begin
  // 3 is offset of Invoke, after QI, AddRef, Release
  TMethod(MethPtr).Code := PPVtable(MethRef)^^[3];
  TMethod(MethPtr).Data := Pointer(MethRef);
end;

type
  TNotifyRef = reference to procedure(Sender: TObject);

function MakeNotify(const ANotifyRef: TNotifyRef): TNotifyEvent;
begin
  MethRefToMethPtr(ANotifyRef, Result);
end;

procedure P;
var
  f: TForm;
  btn: TButton;
begin
  f := TForm.Create(nil);
  try
    btn := TButton.Create(f);
    btn.Parent := f;
    btn.Caption := 'Click Me!';
    btn.OnClick := MakeNotify(procedure(Sender: TObject)
      begin
        ShowMessage('Hello There!');
      end);
    f.ShowModal;
  finally
    f.Free;
  end;
end;

begin
  try
    P;
  except
    on e: Exception do
      ShowMessage(e.Message);
  end;
end.

Delphi 2010 RTTI Contexts: how they work, and a usage note

2010-01-07T19:34:00.002Z

Delphi 2010 includes extended support for RTTI, also known as run-time type info or reflection. Many design approaches that have previously only been possible with managed languages like C# and Java because of the code annotation and introspection they required should now be possible in the Delphi world.

Something somewhat interesting about how the RTTI works is its approach to object pools. Delphi isn't a garbage collected language, so users need to be careful to free objects when they're no longer needed, either explicitly, or by designing or using some kind of ownership scheme, such as that used by TComponent, where the Owner takes care of destruction.

Type information usage scenarios don't mesh particularly well with a TComponent-style of ownership. Typically, when working with RTTI, you want to do some kind of search for interesting objects, do something with them, and then go on your way. That means that many objects may get allocated for inspection, but not actually be used. Managing those objects' lifetimes independently would be tedious, so a different approach is used: there is a single global RTTI object pool. While there is at least one RTTI context active in the application, this object pool keeps all its objects alive. When the last context goes out of scope, the objects get freed up.

The pool management works by using a Delphi record that contains an interface reference. The first time any given RTTI context is used, it fills in this interface reference. It can't fill it in any later than first use, because Delphi records don't support default constructors, which besides have their own problems. For example, how do you handle exceptions in default constructors, in all the places they can occur? Allocating arrays, thread-local variables, global variables, global variables in packages, temporary objects created in expressions, etc. It can get ugly, and in C++ it sometimes does.

So, this first use allocates an interface, called a pool token. It acts as a reference-counted handle to the global object pool. For so long as this interface is alive, the the global object pool should stay alive. Even if the RTTI context is copied around, Delphi's built-in interface handling logic, designed along COM principles, will ensure that the interface doesn't gets disposed of prematurely or get its reference count muddled up. And when an RTTI context goes out of scope, either by being a local variable in a function that is exited, or a field in an object that is freed, the reference count is reduced. When it hits zero, the pool is emptied.

The biggest upside of this approach is that RTTI usage should feel reasonably cheap, conceptually speaking. Code need only declare a variable of the appropriate type, and start using it:

procedure Foo;
var
  ctx: TRttiContext;
  t: TRttiType;
begin
  t := ctx.GetType(TypeInfo(Integer));
  Writeln(t.Name);
end;

A downside, however, is that lazy initialization can create a gotcha. Imagine this scenario:

Library A declares an RTTI context A.C
User code B declares an RTTI context B.C
B pulls some RTTI objects O out of B.C, in order to hand them to library A
B.C goes out of scope
Library A now tries to work with O, but discovers much to its surprise, that the objects have been prematurely disposed, even though A already has an RTTI context, A.C

The problem is that A never used A.C, so it never allocated a pool token. When B.C used its context, the pool came into being, and objects O were assigned to it; but after B.C went out of scope, the objects got freed.

The solution to this problem is for Library A, knowing that it has a long-lived RTTI context and it expects to communicate with third-party code which allocates objects from its own RTTI context and hands them back, it should ensure that the long-lived context's pool token is allocated. A trivial way to do this is like this:

type
  TFooManager = class
    FCtx: TRttiContext;
    // ...
    constructor Create;
    // ...
  end;

constructor TFooManager.Create;
begin
  FCtx.GetType(TypeInfo(Integer));
  // ...
end;

This will allocate only a bare minimum of RTTI objects, those needed to represent the type System.Integer, but more importantly, will ensure that FCtx has a pool token and will keep the global RTTI pool alive.

In future releases of Delphi, the static method TRttiContext.Create will make sure that its return value has a pool token allocated; currently, it does not. TRttiContext.Create was originally defined to make the TRttiContext record feel more like a class for people unfamiliar with the idiom of using interfaces for automated deterministic lifetime management. The corresponding TRttiContext.Free method disposes of the internal pool token, and should remain the same.

Playing DVDs in Windows 7

2009-12-29T03:48:00.002Z

Oh, how I pine for the blissful days of Windows XP, when menus were still in fashion, the start menu didn't contain a tree view, applications didn't require a half-dozen clicks to launch (to expand the tree view, you see), and the user's colour theme choices were respected. Better days, when the customer was still king.

Lately I've been having difficulty playing back DVDs on my Windows 7 PC. My preferred media player, mplayerc aka Media Player Classic - and its close cousin, the more recently maintained Media Player Classic Home Cinema, failed with the error message "DVD: copy-protection failed". (I quote the message and versions in detail to increase the chances a search will find this page.) Windows Media Player has similar issues, though since they've hidden the menus and generally "simplified" the WMP UI, I can no longer figure out how to use it.

From my research and experimentation, it appears that ever since Windows Vista, RPC1 (aka region-free) DVD drives are no longer welcome. Windows will detect the drive as being region-free, and prevent DVD video playback. The only commonly-found player that still works is VLC, if you can stand its broken UI. I cannot: for example, try full-screen playback (F11) with hidden controls (Ctrl+H) in VLC; you'll find that hiding the controls breaks the full-screen toggle, F11! I've had to flash my DVD drive with a region-locked firmware just to play DVDs. Workarounds exist, such as using auto-reset firmwares if they exist for the drive, or what I'm probably going to do, use a separate DVD drive for each region, since DVD drives are exceedingly cheap - less than 20 GBP - and I only need two regions, Europe (2) and North America (1). (I note with slight puzzlement that DVD drives seem to be slightly cheaper in the UK than in the US; not normally the case.)

One thing does really puzzle me, though. All the error messages say that copy protection failed, when as far as I know region locking has nothing whatsoever to do with copy protection, but is rather about inhibiting global trade. With some irony, one of the workarounds I used to watch DVDs was to rip them and play from the file server across the network.

Commonly Confused Tidbits re .NET Garbage Collector

2009-12-14T16:01:00.005Z

I recently read a less than informed blog post purporting to describe the .NET garbage collector, but when pressed to point to a better one, I couldn't find a single concise article that covered everything I thought should have been covered.

Type and Memory Safety

We all know what the gist of GC is about: you allocate new objects, but don't have to worry about freeing them. Combined with type safety in the language, this can give you another kind of guarantee, memory safety: that it's impossible to create a dangling pointer (a pointer to freed memory). Type safety's "safety" is compromised in the absence of memory safety. For example, in a type-safe yet non-GC language, if you allocate an object, make a copy of the reference, then free the object, you're left with a dangling pointer. If you then reallocate another object with a similar size, depending on the memory allocator's implementation, you may have actually created a type hole - the dangling pointer may now point to the newly allocated object but with the wrong type. This extra safety is one of the reasons why GC programs often have less bugs than ones using manual allocation.

Precise compacting GC

.NET has a precise compacting GC. It's precise because .NET deals with type-safe and memory-safe references into the managed heap, it can know the precise layout of every allocated object. The opposite is conservative GC; conservative GC doesn't necessarily know the types of variables stored on the stack or in registers, or the layouts of those types, so if a random number on the stack or in a register or the middle of an object happens to coincide with a valid object address, it can't collect that object. It's compacting because during a collection, it moves live (non-garbage) objects closer together, squeezing out the gaps left by dead, old objects which no longer have any references to them. This eliminates the problem of memory fragmentation, at least as far as the managed heap is concerned.

However, thinking of a precise compacting GC as "collecting garbage" is not always the best way. When looking at the asymptotic performance of GC, it's helpful to turn things around, and consider that the GC collects live objects and brings them together. Garbage is just the stuff that got overwritten during moving, or the stuff left at the end after everything has been compacted together. Why is this important? Because the cost of a precise compacting garbage collection is proportional to the number of live objects it has to trace through and move, rather than the amount of garbage it needs to collect. When compared with manual allocation, where the cost of freeing memory is usually proportional to the number of objects freed (i.e. the amount of garbage), something should become clear: the longer you can delay GC - i.e. the more garbage you can build up - the faster and cheaper, in per-garbage terms, GC is than manual allocation.

An example. Imagine a single linked list with 1000 elements, with a single variable in the program referring to the head of the list. Consider the problem of truncating the list, and leaving only the head behind. With manual memory allocation, all 999 trailing items will need to be disposed of, with bookkeeping for each one. With garbage collection, only the first element need be moved to the start of the heap, and the free pointer (where new allocations begin) set to begin directly after it. The 999 other elements got "collected" for free.

This is why the performance of precise compacting GC is proportional to the amount of garbage it is allowed to build up between collections, and hence proportional to the amount of memory it's allowed to consume. It's also the reason why GC programs tend to use more memory than manual allocation ones. It's also the reason why small single-use objects, such as for function return values, are very cheap and shouldn't be unduly avoided in GC languages. Congruent with this, code in a programming language with GC is often more naturally written, easier to read and easier to write because of the freedom with which one can return freshly allocated objects without concern for who is going to collect them, or the performance ramifications. Understanding this point is key to understanding why GC is so productivity-enhancing.

Resources

The garbage collector is for memory, not resources. I've written about this at length in the past, so I shall quote myself:

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

In .NET, the deterministic disposal mechanism is via the IDisposable interface, and in languages like C#, the using keyword.

Finalizer vs IDisposable

Finalizers in .NET are overrides of the method System.Object::Finalize(void). In C#, the syntax looks like a C++ destructor, but other .NET languages have other syntaxes. If this method is overridden, the .NET GC treats the object specially. After it has become garbage, rather than just overwriting it during compaction phase of GC, it will delay collection until the Finalize method of the instance has been executed by the finalizer thread. The GC makes a best effort to call the method; if the finalizer thread is blocked (e.g. some other finalizer hung), then the finalizer might not get called. This is another reason why deterministic disposal is preferred to relying on finalizers.

Finalizers should only be used with objects that directly encapsulate a non-managed resource, such as a file handle, a window handle, a socket, etc. A file stream, or a window object, or a network stream, should not normally implement a finalizer. IDisposable is a different matter. IDisposable should be implemented by every class with a finalizer, and every class that logically owns (transitively) any other object that implements IDisposable. Calling IDisposable on the root of the ownership tree should ripple through and call IDisposable on everything beneath it; ownership trees and other deterministic lifetime approaches still exist with GC precisely because GC is just for memory, not resources. Most objects neither own nor encapsulate resources, however, so much of the burden is still lifted.

Generations

I've read many posts that describe how generational GC works: very loosely, you have three generations, gen0 through gen2; allocations come from gen0; gen0 is collected if it's full; gen1 is collected if gen0 collection didn't free enough space; gen2 is collected if gen1 didn't free enough; more memory is allocated if gen2 didn't free enough; if not enough memory, then out of memory exception.

They also describe the hypothesis behind generational collections: that young objects are more likely to die (become garbage) sooner rather than later, while old objects are likely to survive longer.

But this, however, doesn't capture the intuition behind why there are 3 generations, rather than 4, or 5, or some other number. Let me explain.

Most applications have a roughly constant, steady state of total allocated memory. It's made up of two kinds of objects: objects associated with currently executing code (let's call them ephemeral objects), and objects linked into a global object graph which is shared across multiple instances and iterations of executing code (let's call them persistent objects). We want to avoid tracing through the persistent objects as much as possible, as it's unlikely that any objects which have survived for a long time have become garbage. Actually, making old objects garbage is a pathology to be avoided in .NET programs, and has been described as the mid-life crisis problem.

The ephemeral objects, on the other hand, are likely to have a high proportion of garbage. But we have a problem: when we perform a garbage collection on the ephemeral objects, there'll be some live objects left over, currently being used by executing code - but we still don't want them in with the persistent objects. To solve this problem, there needs to be a generation in the middle, a half-way house, before resorting to increasing the persistent object set.

This combination of three generations is almost ideally suited to server applications which have relatively little variance in total per-request allocation and tend towards an average per-request allocation which is less than the size of gen0+gen1 per thread. If one could time per-thread collections of gen0 and gen1 correctly, in between requests, then in theory GC would be almost completely free, as there would be almost no live objects. There are complications in practice (we can't manually invoke a GC for just a single thread, for one thing), but when designing applications and servers, it's very much worth keeping the generational design of the GC in mind and working with its assumptions, rather than against them.

For example, this can mean that caching objects can turn out to be a pessimization rather than an optimization, because keeping them around moves them into gen2, where it is more expensive to collect them when they get evicted from the cache than it was to create them in the first place. Depending on how expensive the objects are to create vs cache, they may need to be cached permanently and updated as needed, or referred to through a WeakReference which won't keep them alive, or at worst managed manually one way or another, such as via unmanaged memory, or slots or ranges in an array, etc.

On the Difficulty of setting the Windows 7 Desktop Wallpaper

2009-11-10T16:59:00.007Z

You need to be a software engineer to precisely and correctly set the Windows background in Windows 7.

I have a multi-monitor setup, and I use a very particular method for laying out windows on my secondary screen: I have them cascaded, from the top-left corner of the screen towards the bottom right, such that a little of the bottom-left corner of every window is visible on-screen at all times, like this:

The corners form a mechanism for switching between windows based on spatial layout. Certain windows, such as terminals, browsers, email apps, etc. have "natural" dimensions. Browsers generally like to be page-shaped; terminal windows are quite squat; documentation browsers are somewhere in between, with a treeview on the left and a content pane on the right. These natural shapes guide their spatial positioning. So, all my terminal windows end up cascaded one after the other on at the top left of the screen, followed by Firefox's downloads window, then my bug tracker client, then Thunderbird, then MSDN documentation, with Firefox at the bottom-right, filling the full height of the screen.

Switching between applications based on their spatial layout turns out to usually be more efficient than almost any other scheme, particularly when one's hands aren't on the keyboard. Even alt-tab doesn't distinguish very clearly between different instances of e.g. a terminal app, when in fact each one may be logged in via ssh to different machines and thus it matters very much which one I select.

This scheme works well enough, but the bottom-left corners can get a little ragged. To make aligning the corners easier, I have a special wallpaper which consists of a line carefully placed so that it shows up on the bottom-left corner of my second monitor. When the wallpaper mode is set to "tile", a wallpaper which is big enough to cover the entire desktop area will show up at the expected offset, and everything works out OK.

This wallpaper, a 16-colour bitmap, is so small when compressed that I can embed it here uuencoded directly:

begin 644 wallpaper2.bmp.bz2
M0EIH.3%!629365%3W2<`1PST[.0U0`!`0!`"`0!``!``0`!$``,(L`#9`0JC
M4#1HR::%&C(&C3(T"E4TAM30`&=?M"6=)(E^T$2WA+9$L*JDF-E$NG?'AI55
M0/>6^L(CB*T(550`Q-.DJ".(B"O,*JH`8F(WU0$<@^P((\>[801S_$;<:YG'
:LR**SC<GG'.8JJ@!M,13_%W)%.%"045/=)P`
`
end

If you save that to a file with a '.uue' extension, many common archivers, such as WinZip or WinRar, will be able to open it up. Here's what the meat of it looks like, anyway:

However, it turns out, if you try to set this background using the "Personalization" Control Panel applet in Windows 7, it does some helpful "conversions" on it: it appears to round-trip the damn bitmap through JPG, resulting in artefacts. I've enhanced a zoom of the line after Windows has butchered it:

The line looks unclean, and in particular, it ends up with wave of intensity throughout its length, which is quite distracting and not the desired effect.

Things can get worse though; if you try to use Windows Photo Viewer to set the background using the original bitmap, it will actually resize the thing down to fit the dimensions of your primary monitor (!!!), all but zooming the line out of existence. This drove me up the wall for about 20 minutes, as I tried to figure out where my line had gone when I first transitioned from XP to Windows 7.

The easiest way I currently know to correctly set the Windows 7 desktop wallpaper is to write a program that uses the SystemParametersInfo function directly, to ensure the bits get through unmolested.

I have a lot more Windows 7 annoyances where this came from, but this one cost me quite a bit of time, so it sticks out. My verdict on Windows 7 is pretty mixed. Many applications, particularly games, are incompatible, and overall I dislike the shell compared to XP, especially Windows Explorer and the Vista-esque Start Menu. About the best things I can say in favour of the move is having less concern about future compatibility, and having a 64-bit mode that mostly works, despite all the horrific hacks going on beneath the covers to make it happen. Oh, and I'm running with UAC disabled. I can only take so many access denied errors as I poke around the system before I crack - and command-line apps generally just give you the error, rather than popping up an elevation prompt.

Bad week

2009-10-24T23:27:00.002+01:00

It's been a bad week. My main hard drive crashed last Monday or so, while today my scooter is gone, presumed stolen. On the bright side, the final component of my new PC arrived and I was able to get Windows 7 up and running.

The new machine has an i7 920, so things like %NUMBER_OF_PROCESSORS% returns 8 - it's a quad core with 2x hyperthreading. Having so many logical cores has some downsides: maxed-out single-threaded processes only take up 12.5% CPU, so it can look like the machine is not particularly busy even though a process is working as hard as it can. Other specs include 12GB RAM, AMD 5870 graphics, 80GB Intel SSD and 1TB Samsung F3.

Maximizing the value of the small boot drive has been interesting. Windows 7 all by itself takes up a good 18G of space, what with the side-by-side (SxS) feature keeping lots of versions of the same APIs, and a big hiberfil.sys in the root - I moved the page file to the big drive. Because of the acute space constraints, I've been strongly motivated to keep almost all the junk that apps usually dump into the file system off the boot drive. By and large, I achieve that by creating directories on the 1TB drive and pointing to them with junctions on the boot drive. That way, apps think they are installing onto the C drive but they don't steal too much space. My prior drive - the one that died - was a 10K WD Raptor, so I've had some experience with this, and I wrote a script to automate the process:

#!/bin/bash

. _die

function usage
{
    echo "usage: $(basename $0) <directory>..."
    echo "Replace directories with junctions pointing to /bulk, after moving contents."
    exit 1
}

test -n "$1" || usage

for f in "$@"; do
    
    test -d "$f" || die "'$f' isn't a directory"
    
    dest="$(abs-path "$f")"
    dest=/bulk/mathom/"${dest//\//_}"
    
    test -d "$dest" && die "'$dest' already exists"
    
    # Try to copy stuff over; if an error, delete target and give up.
    cp -r "$f" "$dest" || {
        rm -rf "$dest"
        die "couldn't copy '$f' to '$dest'"
    }
    
    # Rename source, in case something can't be deleted.
    aside="$(move-aside "$f")" || die "failed in move-aside"
    
    # Create junction.
    junction "$dest" "$f" || die "failed to create junction"
    
    # Remove the aside.
    rm -rf "$aside" || {
        echo "warning: couldn't delete '$aside'"
    }
done

This script uses a number of little wrapper utilities I wrote - at this point I really ought to be thinking of putting them in an online repository. Here's a summary so you can follow along:

abs-path: Canonicalizes and makes an absolute path by using cygpath twice, once to Windows format and once again back to Unix format, and prepending $PWD if necessary.
_die: Defines a die function which prints out appropriate error and exits.
move-aside: Renames a file or directory so that a failed attempt at creating a junction can be rolled back. Also helps with locked files - generally these can be copied and renamed, but not deleted. The new name is printed out on standard output.
junction: This wraps SysInternals junction to create a junction in the TARGET LINK_NAME argument order familiar from ln, and permits using Cygwin paths.

With this script, and the big drive mounted at /bulk with a directory called mathom in its root, any given directory tree can be moved across readily enough. However, things in Windows 7 x64 are slightly more complicated.

Some of the directories I moved over to /bulk/mathom included Program Files, Program Files (x86), and ProgramData. Windows 7 itself has some junctions set up (the rats nest here is a proper horrorshow, I should document it at some point just for my own use, if nothing else). For example, "ProgramData\Application Data" points at ProgramData itself, and a simple cmd /c dir will fall into the infinite recursion and print out errors when the file path gets too long. So, in moving these directories across, I had to examine them for existing junctions and replace these as necessary. The Cygwin tools of Unix heritage are more robust against cycles in the file system hierarchy - for example, find keeps track of inodes to avoid infinite recursion.

All this checking of existing junctions wasn't sufficient to get everything working nicely, though. The permissions generally also need tweaking, particularly for folders that get modified by installers. These generally perform operations using either the NT SERVICE\TrustedInstaller or NT AUTHORITY\SYSTEM accounts - and sometimes both, in a dance of setup.exe and msiexec.exe. So, by process of checking, trial and error, using SysInternals Process Monitor to track installation failures, I put together a new script to ensure Program Files, ProgramData and folders of their ilk have the right set of permissions:

#!/bin/bash

function usage
{
    echo "usage: $(basename $0) <file/directory>..."
    echo "Resets files and directories to Windows 7 general install permissions."
    echo "Essentialy this is: SYSTEM/TrustedInstaller/Admin: full; AuthUsers: Modify; Users: Read"
    exit 1
}

test -e "$1" || usage

for arg; do
    
    # First, take ownership so we can definitely set all ACLs.
    # /F <file>; /R - recurse; /D <Y/N> - take ownership if no directory listing
    takeown /F "$(cygpath -w "$arg")" /R /D Y > /dev/null
    
    # Reset ACLs recursively to inherit from parent
    icacls "$(cygpath -w "$arg")" /reset /t /c /q > /dev/null
    
    # Set appropriate ACL on root, to progate recursively
    icacls "$(cygpath -w "$arg")" \
        /grant "Administrators:(OI)(CI)F" \
        /grant "SYSTEM:(OI)(CI)F" \
        /grant 'NT SERVICE\TrustedInstaller:(OI)(CI)F' \
        /grant 'Authenticated Users:(OI)(CI)M' \
        /grant 'Users:(OI)(CI)RX' \
        /inheritance:r /c /q > /dev/null
    
done

The logic is applied in three phases:

Take ownership, with takeown
Reset permissions recursively so that they inherit from parent
Set ACL on the root, so children will inherit from it, but make sure the root itself doesn't inherit permissions.

I tried for a while to get it all into one icacls invocation, but I couldn't get the two effects working together: enabling inheritance in the children, but disabling it in the root. This is something you can do in one "Apply" step using the Security tab in Explorer, though it's quite tedious picking out all the users and setting the appropriate checkboxes.

As an aside, the Security tab is quite confused by junctions; when permissions have been inherited from a directory on a different drive, because the current file / directory is in a subtree pointed to by a junction, the Security tab will search in vain through the parents looking for what provided the given inherited permission. Sometimes it gets lucky, and finds a random parent that coincidentally has the same permission; otherwise, it bails out with "Parent Object" as the indicated "Inherited From" column. But my proper list of Windows 7 issues will have to wait until I really feel the need to rant, which will no doubt happen sooner or later.

I should add that all the drastic file system surgery I write about here was performed with UAC effectively out of the picture, and all Cygwin tools running with the administrative privilege bits set. It's been my experience that command-line apps don't pop up the required UAC prompt; instead, they fail with an access denied message, which is rather vexing when you're trying to automate things.

Public interest rule of thumb

2009-07-15T13:15:00.002+01:00

TechCrunch is having a crisis of conscience over what they'll do with internal Twitter documents they've received.

My rule of thumb is pretty simple. The documents are stolen. Unless the documents reveal wrongdoing greater than stealing, such that the public interest served in publishing is greater than the private harm, then it's unethical to publish. Idle musings about "they are going to be published somewhere on the Internet" is specious; the morality of one's actions don't depend on whether someone else is "doing it", much less everyone.

If TechCrunch goes ahead and publishes these documents, it'll only further cement my already pretty low opinion of Arrington. (I'm not a habitual reader of TechCrunch, or otherwise I'd waste away over all the food I'd be vomiting up.)

StackOverflow and religious language in programming

2009-07-14T19:45:00.002+01:00

I was reading Why I Don’t Listen to the StackOverflow Podcast any More, and in reading the comments, I found it interesting to see the amount of religious language.

#21 (sbohlen) I’d have to agree that they do indeed appear successful, but success / failure isn’t a boolean [...] The world is full of people who succeed due to all kinds of factors including dumb-luck, [...]

This reminds me intensely of "the race is not always to the swift" etc. Eccl 9:11.

I changed adopters to believers to accentuate the effect:

"#16: [...] I have also experienced that the non-[believers] aren’t (gnerally) non-[believers] out of choice but are instead non-[believers] largely out of ignorance and inexperience — they just don’t know what they don’t know [...]"

#16: "the [types] who aren’t interested in self-improvement; there’s not a damned thing I can suggest to help these people — I cannot MAKE someone want to better themselves, that’s gotta come from within"

#16: "I [...] think that Jeff and Joel are indeed preaching [...] they are (IMO) abdicating the unofficial professional responsibility that comes with having a pulpit from which to preach."

#14: "I am a strong believer"

#13: "@sbohlen. I fully agree with the sentiment that “up and running” is not a valid metric"

I'm not going to go on with this, though I could - the about page for the blog is particularly ripe for further examples of religious language - but I do want to make a further point.

Could it be that latent religious feelings are responsible for a good portion of the minor angst on display in these comments? Could it be that people are unconsciously annoyed, not with StackOverflow's success, but rather its success even in the face of quite mild contempt at the unit-testing / SOLID religion?

My own position: I'm a "believer" in evolution and the market. Neither evolution nor the market have any moral content (they can't say what "ought" to be), and both only measure success by effects rather than processes. In a phrase, "up and running" is not just a valid metric - it's the only metric, until it stops running. If SO continues to thrive, and doesn't die under the weight of its lack of unit testing (which seems to be the logical end result of the beliefs of the believers in the comments), where then is the truth in the proclamations of doom from the prophets of the true religion?

I don't think unit-testing is the only way to avoid long-term bit-rot. I think it's a good way, but not the only way; moreover, I don't think unit testing is especially useful in the very early stages of a project, where the design changes often and rewriting unit tests becomes a disincentive to larger refactoring and redesign. I think every one of the concepts embodied in S.O.L.I.D. is debatable in certain scenarios (except perhaps LSP).

In my experience, premature abstraction has been responsible for a similar number of ills to premature optimization: abstractions chosen at the wrong boundaries, for the wrong reasons, because designers thought they could foretell the future and anticipate where changes would come. Thus I am wary of merchants of abstractions and patterns, principles and practices. I'll use them when appropriate, but never with religious zeal.

WPF / VS2010 Font rendering: blurryville

2009-05-22T13:03:00.008+01:00

I downloaded and installed VS2010 Beta 1 to see how it's looking. It's not pleasant though - it makes me feel like I'm looking at the screen through a layer of coke-bottle plastic:

Compared to the old rendering, where my preferred fixed-width code / terminal font, Dina, is correctly chosen, as opposed to falling back to what looks like Courier New:

The new rendering hurts my eyes (they keep trying to focus more, but it doesn't help!) and makes VS2010 Beta unusable, as far as I'm concerned.

The "recommended solution" for text clarity issues in WPF is "use the largest font size possible". That's a bit of a cop-out for the working programmer, where displaying as much code on-screen as is comfortably legible is usually the best option.

FWIW, I registered a feedback item on this.

Sharing a printer, the hard way: writing your own spooler

2009-04-28T13:47:00.006+01:00

I have an ultra-cheap HP Color Laserjet 1600 printer, the kind that costs less than a full set of replacement toner cartridges, and the ones that are shipped in the box are only 20% full. From the driver publisher info it appears the I/O protocol logic of the printer was provided by a company called Zenographics, which appears to now be either a part of or owned by Marvell. It works well enough when you have it directly connected to a machine via the USB cable, but sharing it is a nightmare.

In particular, the drivers are very unstable when targeting shared printers. Especially problematic is printing from Vista to XP, or XP to XP, or XP to Vista. With some combinations, the print spooler crashes; with others, it simply hangs, and the spooler service needs to be restarted to get the document printing at all. The folks on the HP forums seem to imply (a) that this is by design, and (b) sharing the printer effectively is impossible. I find this hard to swallow; since the printer works when directly connected, there is no valid reason why printing across the network should not also work, since the physical printer doesn't come into the equation. Bits are bits; if the driver can't consistently send some bits across the network, either there's some atrocious QA going on inside Zenographics, or worse, malice.

I had despaired of ever getting it working nicely as a small workgroup printer, but I saw a faint glimmer of hope when setting up my home NAS, based on Solaris. CUPS is available for Solaris, and there's a Foomatic printer driver available for this specific model as well.

It turns out that I couldn't get CUPS configured with this printer and driver setup. CUPS uses a web page interface for configuration, but it was desperately slow, and every time I tried to print a test page, it informed me that the printer had just gone offline. I could see all the background processes it had started up to print, and the printer device at /dev/printers/0 was indeed opened for writing, but it never got anywhere.

But that didn't matter. The foo2hp driver provided the only real tools I needed: a PostScript to ZjStream (the printer protocol) filter, which simply reads the raw PostScript and outputs the raw print data. Windows ships with a generic PostScript driver; I use the PScript5-based "HP Color Laserjet PS". A simple shell pipeline from source to printer device would do.

To share the printer, I needed some kind of queue for buffering. I decided on a simple filesystem-based approach, which seems to me to be in the Unix tradition. I created a share on my Solaris box specifically for files to be printed. Windows clients can use the aforementioned generic printer driver with a FILE: target, and place the output in this shared directory. The spooler script I wrote polls this directory periodically, and attempts to print whatever it finds.

The printing logic is pretty simple, at its core:

foo2hp2600-wrapper -p 9 input.ps > /dev/printers/0

The actual code is a mite more sophisticated, of course; it does logging, moves documents to be printed into a directory categorized by date and time, etc. And in future it can be extended to other document types than PS, e.g. printing PDFs or photos simply by copying them to a directory.

Another advantage of this approach is that I can shell out to ps2pdf to create an archival version of the printed document. The PDF is usually far smaller than the PS and is viewable from Windows without installing a PostScript viewer. This archival version is useful if I ever need to print it again. Consider online flight checkins, for example - some websites (such as EasyJet) prevent printing the boarding pass more than three times, which is a little inconvenient if you're having printer trouble.

On the downside, printer options that can't be expressed directly in the PostScript with the generic driver can't be configured. For example, the way I have things configured I'm limited to printing monochrome on A4 by default. In practice this isn't really a problem, since the vast majority of print jobs fit this template; I could create other spooler directories for different defaults.

I expect that with enough research, I'll be able to get CUPS configured correctly, or to get Samba to look like a PostScript printer that dumps the raw network data into my spooler directory. However, I'm pretty happy with my hack for now...

ZFS/Solaris as a NAS

2009-03-22T03:24:00.004Z

I've finally got a semblance of a Solaris system up and running with a nice fat ZFS storage pool. It was neither trivial nor pleasant, however.

Here's the executive summary of what I learned:

Don't use OpenSolaris 2008.11; use at least NexentaCore 2 instead; others may work.
Don't use an Intel or Realtek network adapter; if you must, use Realtek with an older version of the gani driver.
Don't use Solaris's built-in CIFS implementation, smb/server, aka hereafter "cifs" (to contrast with "samba").
Don't let ZFS to default to 128KB max block size unless all your files are big (greater than about 2MB) or tiny (less than about 64KB).

OpenSolaris 2008.11, the version I tried, is not production ready unless you have extremely specific hardware and quite narrow requirements. I finally ended up using NexentaCore Unstable v2.0 Beta 2.

The prime requirements for a working NAS are:

Lots of attachment points for disks
Good physical network connectivity
Good network protocol implementation
Good filesystem implementation

There is no one of these that I didn't have issues with.

The first one, attachment points, was a nice-to-know gotcha that it took me a while to figure out. My motherboard (an old Abit AW9D-MAX) has 7 internal SATA attachment points, as well as 1 PATA channel for two extra PATA devices. This being insufficient, I procured an extra PCIe two-port SATA adapter. I was up and running fine with 5 disks attached (1 boot drive and 4 drives in a raidz ZFS pool - effectively RAID 5 without the need for NVRAM), and in preparation for creating my second raidz vdev (virtual device in ZFS lingo), I started attaching more drives, one by one so that I could label them (and thereby know which one failed when it fails - which it will, eventually). When I had 7 drives attached, the OS occasionally failed to boot, but would reliably hang upon execution of the 'format' command (the handiest way of figuring out the drive device name under Solaris).

The gotcha, however, is that the BIOS defaults to IDE emulation mode, which, for this particular BIOS, supports a maximum of 6 devices. It packs the first 2 hard drives into pretend-PATA (complete with "master" and "slave") even if they aren't actually PATA, and then labels the next 4 drives as SATA 1 through 4. I had to change the BIOS's mode to AHCI to get it to support more drives. Luckily, my boot drive is an old PATA one, so it didn't need compatibility to stay in the same place (master on the first PATA channel).

Physical network connectivity was a far, far harder task, and one that still isn't quite complete. My motherboard has two physical 1Gb Ethernet adapters built in. Unfortunately, OpenSolaris defaults to a driver it calls rge for the chipset (RTL8111/8168B PCIe), but this driver has big issues, that I suspect are related somehow to duplex operations. Big transfers using big buffers using cifs (the Windows-compatible protocol Solaris ships with) will work with reasonable performance (30MB/sec or so), but streaming video (small reads that expect low latency) performs abysmally. Even worse, at non-deterministically random times (as far as I could ascertain), the rge driver would fall into a mode where transfers were extremely slow, as in less than 1MB/sec slow. I took to keeping a ssh session open to the Solaris machine and simply echoing '.' back and forth (echo '.' loop piped to ssh cat -), and mysteriously enough, so long as there was small back and forth traffic, transfer performance rocketed back up again.

This being unsatisfactory, I tried to use the gani driver. I never could get gani-2.6.3 to work with my chipset, however. I didn't know if it was a problem with the driver, a conflict with my chipset, or my poor configuration skills with Solaris. All I know is that I tried every technique I could find, up to and including patching driver_aliases and running sys-unconfig to start things off from a fresh basis.

So, I bought an Intel 1000/PRO Gigabit ethernet adapter. Folks online, in response to reports of rge not working correctly, seemed to say that the Intel adapter "just worked", but I should have dug deeper... The driver Solaris uses for this is called e1000g. The version of this driver shipping in OpenSolaris 2008.11 doesn't work. It drops packets. Simply pinging the Solaris machine from the outside shows packet loss exceeding 5%. With a ssh session open to Solaris, simply holding down '.' on the keyboard and watching the character getting echoed in the terminal is sufficient to demonstrate the hiccups: the pauses are visible and disturbing. It actually affects typing in ssh, almost as if one was at the end of a dodgy Internet connection, perhaps some half-baked cafe wifi link in Marrakesh. A recursive diff of about 100MB of data across about 1000 files using cifs took a whole 45 minutes. A trivial test using dd to copy a 640KB blob of data using a 64KB buffer size took about 15 seconds and dd reported transfer rate of 45KB/sec.

It was this network connectivity that prompted me to start trying out other distributions. NexentaCore 2 was first in line. It defaults to the gani driver for the Realtek adapter, but an earlier version, 2.6.2. This works, but only at 100Mbps; try as I might, I can't convince it to go higher. (Windows running on the same hardware, same patch cable and same switch, never, ever dropped down to 100Mbps - something I can't say about the other Windows machines I have here.) Alos with significant importance, NexentaCore doesn't ship with a GUI (so no need to disable it), and does ship with apt-get and a reasonable selection of packages, including my preferred Linux/Unix editor, joe (very similar to old Borland DOS IDE text editors). I detest vi - I've never used a program that gleefully punished more heavily every transgression of the user.

Anyhow, that's how I got one reasonably-working 100Mbps connection out of three 1Gbps adapters, four driver versions and two operating system installs.

Next, the network protocol. Solaris defaults to using something that is colloquially called cifs, although the usual identifiers used when e.g. enabling and disabling with svcadm are smb/server and smb/client. I can't say much about smb/client - I'm sure it works well enough, but I don't have much use for it - but smb/server barely works at all. It's implemented as a kernel module, which unfortunately means it has odd and painful limitations compared to how user-level programs view the file system. In particular, only one ZFS filesystem can be navigated from a cifs share, significantly harming the usefulness of creating lots of ZFS filesystems. A ZFS file system mounted inside an existing filesystem, where the mountpoint is visible from a cifs share, will show up as an empty directory to clients, whereas it appears correctly mounted locally on the Solaris box.

Another limitation is symbolic links. By apparent design, cifs prohibits what Samba calls "wide links": symbolic links that resolve to locations that are outside the share's hard-linked subtree. Such symbolic links look much like dead links from Windows, i.e. the text little files they are implemented as. Samba defaults to "wide links" on for performance reasons if nothing else.

A final limitation is hard links created from Windows using CreateHardLink. Cygwin 'ln' ultimately uses this API. For whatever reason (and I didn't dig too deeply, like investigating Wireshark traces), Cygwin determines that 'ln' isn't supported on cifs shares and falls back to copying instead. Cygwin 'ln' works correctly on Windows shares, however, and it also works correctly over Samba.

The verdict: cifs isn't worth it. Needs more time to bake. Use Samba instead.

Finally, ZFS itself. ZFS is the big draw, and the reason I chose to use Solaris. Userspace implementations are available in Linux via FUSE, and also in FreeBSD, but I had bad performance experiences of NTFS-3G/FUSE in Linux, and FreeBSD's implementation sounded dangerously non-production ready. ZFS largely works as advertised. The primary limitation is the inflexibility in removing drives from pools. Raidz vdevs can't have drives removed at all. A word of warning, though: ZFS has what I can only consider a bad bug for files in the 128KB..2MB range. If you have a file of about 129KB, depending on how it was created, it ought to be using up about 100% more space than it should be. In some largeish directories of files I was seeing wastage of about 35% (as measured by 'du' versus 'du --apparent-size'), whereas NTFS on Windows had wastage in the region of 5%. Paring back the ZFS default block size (dynamically settable on ZFS - yay! - but only affects subsequent file operations) to 8KB or 16KB improves things immensely, but still not quite as space-efficient as NTFS.

In conclusion, ZFS/Solaris as a NAS can work well with very carefully chosen hardware and select software configuration. If you get it working better than I describe herein, be very careful what you touch, and whatever you do, don't upgrade your zpools until you're sure that whatever step forward you take is better than what you had previously.

OpenSolaris, ZFS, Dvorak and VI

2009-03-06T06:14:00.002Z

Been experimenting with OpenSolaris to try out ZFS. OpenSolaris is not a pleasant experience even after using an average Linux.

Its termcap and terminfo databases don't include complete information for xterm as implemented by the very gnome-terminal it defaults to, much less gnome-terminal itself; nor does it include any entries for rxvt derivatives (so I have to export TERM=xterm upon ssh in from Cygwin). Thus, there is much fun with Del, Home, End, PgUp, PgDn etc. brokenness: Ctrl+A/E instead of Home/End, Ctrl+D instead of Del, f/b in less rather than PgUp/PgDn, etc. The terminfo DB is spartan even by comparison with Cygwin, and termcap rather, eh, antique:

solaris$ find /usr/share/lib/terminfo/ | wc
    1716    1716   58553
cygwin$ find /usr/share/terminfo/ | wc
   2544    2544   79257

solaris$ grep 1982 /usr/share/lib/termcap
# From research!ikeya!rob Tue Aug 31 23:41 EDT 1982
# From jwb Wed Mar 31 13:25:09 1982 remote from ihuxp
# Extensive changes to c108 by arpavax:eric Feb 1982

Also, there is apparently no text-mode Dvorak layout shipped with OpenSolaris. I managed to patch something rudimentary together reverse engineering the contents of /usr/share/lib/keytables and applying with loadkeys. Within X, xmodmap can load an appropriate translation, but getting that working before gdm comes up for the login and password screen is tedious. Getting a vnc server session running gdm is easier.

Finally, I have to resort to using vi to edit basic files. Vi is a line editor masquerading as a text editor. Now I feel like I'm living in the 80s. The early 80s.

SecuROM and SysInternals tools

2009-02-04T18:34:00.004Z

If you're like me, you like visibility into the workings of your OS, which processes are running, what modules are loaded and from where and whether they are signed or not, what files are open, what files are being touched and what registry entries are being frobbed.

I use the SysInternals tools for getting increased visibility into these things. In particular, I use Process Explorer (procexp) alongside Task Manager (the two aren't complete overlaps for functionality), with File Monitor (filemon) and Registry Monitor (regmon) on XP and Process Monitor (procmon) on Vista. Filemon and regmon are more focused to their specific tasks and have easier to configure filters than procmon, so I usually prefer them, but they are not compatible with Vista.

Any time I see an unexpected filesystem locking error, such as a failure in Windows Explorer to delete a folder, I can search for the culprit in procexp's handle view. Often the culprit is Windows Explorer itself - perhaps caused by a shell extension like Winzip or Winrar - and I can force closed the handle right there from the procexp interface itself.

I have a set of "verification columns" configured procexp that makes visible the Company, Description and Verified Signer columns for processes and modules (DLLs). With Options | Verify Image Signatures turned on, this makes for easy checking for suspicious DLLs and kernel drivers (modules loaded into the System process) loaded in the system.

Procmon supports a whole lot more analysis than the easier to use tools like filemon and regmon, but the most important distinct feature is probably the stack trace on every file and registry operation. Double-clicking an event in the procmon view pops up a dialog that has a Stack tab, wherein the stack trace is displayed. When Windows symbols are correctly configured, procmon will call out to windbg.dll and show symbolic information such as function name and offset for each code address in the stack trace, up to and including downloading the symbols PDB if necessary.

Since I don't think I've done it already on this blog, I'll outline the sequence of steps required to get symbols correctly configured.

Download and install WinDbg. WinDbg is a useful tool in its own right for low-level Windows debugging, and particularly for .NET debugging when using the SOS command extension DLL.
Choose a location - i.e. an empty directory - for the symbol cache on your system. Once chosen, create an environment variable called _NT_SYMBOL_PATH with the value "SRV*[symbol-cache-dir]*http://msdl.microsoft.com/download/symbols" (without quotes), but replace [symbol-cache-dir] with the path to your selected directory.
Now, the SysInternals tools can be configured with these settings. Procmon and Procexp both have Configure Symbols dialogs in their Options menus. Set the DbgHelp.dll path to the DbgHelp.dll from the installation location of WinDbg, and set the "Symbol paths" textbox to the value of the _NT_SYMBOL_PATH environment variable created earlier.

However, the reason I wrote this post is not merely to laud the SysInternals tools and the work of Mark Russinovich. The fact is that SecuROM, a DRM solution used in many games these days, has panic attacks when it sees evidence of SysInternals tools being used. I don't really understand what SecuROM's justification for its conniptions could be, since monitoring the process with the tools could only help in an initial cracking attempt, yet game cracks appear to come out no slower than they ever did. All it seems to do is annoy honest users - and in this case, developers. Not only does SecuROM want you to exit the applications in question, but it also wants you to reboot the entire system, ignoring the fact that you might have concurrent long-lived tasks that don't merit interruption by a mere game

Well, I couldn't let that stand. I created a tool to enable me to simply exit the SysInternals utilities in question, rather than having to reboot the machine. The key to SecuROM's detection of the tools is in the communication mechanism between the SysInternals tools and their kernel driver counterparts, in particular the named devices in the Windows Object Manager namespace, visible using the WinObj tool. It turns out that merely by changing the ACL (access control list) on the device object to a single deny-all ACE (access control entry) is sufficient to fool SecuROM from thinking the device is no longer loaded - though SecuROM also looks for top-level windows with particular window classes, so the utilities do have to be exited as well.

So, I wrote a simple Delphi console application, called cacls_driver, to modify the ACL of a driver device. A key set of libraries that made this easy was the JEDI Win32 API library, in particular the units JwaWinType, JwaWinBase, JwaWinNT, JwaNative and JwaSddl. I've appended the tool's source code to this entry.

Using the tool is simple enough. The most important thing to know is the name of the driver one is changing the permissions of. For the versions of filemon and regmon I have installed, the correct driver names are filemon701 and regmon701 respectively. I figured this out by running the aforementioned WinObj and looking in the 'GLOBAL??' folder for devices with names starting with filemon and regmon. For the original Crysis, SecuROM even complained about Process Explorer, so I had to include procexp110 (IIRC) as well. SecuROM support, on the other hand, recommended that I upgrade Process Explorer, which of course used an incrementally different device name (procexp111) and thereby avoided the SecuROM sanction.

Here's an example of the tool in use hiding the regmon and filemon driver links ($ is my command-line prompt, and # are comments):

# This simply shows the current ACL
$ cacls_driver -s filemon701 regmon701
filemon701 :: D:(A;;CCRC;;;WD)(A;;CCSDRCWDWO;;;SY)(A;;CCSDRCWDWO;;;BA)(A;;CCRC;;;RC)
regmon701 :: D:(A;;CCRC;;;WD)(A;;CCSDRCWDWO;;;SY)(A;;CCSDRCWDWO;;;BA)(A;;CCRC;;;RC)

# This disables the ACL. There's no output from this command.
$ cacls_driver -d filemon701 regmon701

# Verifying that the ACL has been set.
$ cacls_driver -s filemon701 regmon701
filemon701 :: D:
regmon701 :: D:

These ACLs having been applied - and ensuring the tools in question aren't still running - I'm free to run my games without the odious requirement for a reboot.

Source code follows...

program cacls_driver;

{$APPTYPE CONSOLE}

uses
  SysUtils, JwaWinType, JwaWinBase, JwaWinNT, JwaNative, JwaSddl, Generics.Collections;

type
  TOperation = (opNone, opApply, opShow);

  TOptions = class
  private
    FOperation: TOperation;
    FDrivers: TList<string>;
    FDacl: string;
  public
    constructor Create;
    destructor Destroy; override;
    property Operation: TOperation read FOperation write FOperation;
    property Drivers: TList<string> read FDrivers;
    property Dacl: string read FDacl write FDacl;
  end;

function ParseOptions: TOptions;
const
  // http://msdn.microsoft.com/en-us/library/cc230374.aspx
  // These were the defaults on my system (WinXP SP3)
  // SID tokens (last two letters in ACEs):
  // SY = local system; BA = builtin administrators; WD = everyone; 
  // RC = restricted code
  // Permissions:
  // CC = create child; RC = read control; SD = delete; WD = write DAC;
  // WO = write owner
  DefaultDacl = 'D:(A;;CCRC;;;WD)(A;;CCSDRCWDWO;;;SY)(A;;CCSDRCWDWO;;;BA)(A;;CCRC;;;RC)';
  NullDacl = 'D:';
var
  i: Integer;
  opt: string;

  procedure Usage;
  begin
    Writeln(Format('usage: %s <command> <driver...>', [ParamStr(0)]));
    Writeln('Modify discretionary ACL for the given global namespace driver symlinks.');
    Writeln('  -d       Disable access (deny-all ACL)');
    Writeln('  -e       Enable access (apply default ACL: ', DefaultDacl, ')');
    Writeln('  -s       Show ACL for the given drivers');
    Writeln('  -a <acl> Apply an explicit ACL');
  end;
  
  procedure SetOpOnly(Op: TOperation);
  begin
    if Result.Operation <> opNone then
      raise Exception.Create('only one of -s, -d or -e allowed');
    Result.Operation := Op;
  end;

  procedure SetOp(Op: TOperation; const ADacl: string);
  begin
    SetOpOnly(Op);
    Result.Dacl := ADacl;
  end;
  
  procedure SetOpArg(Op: TOperation);
  begin
    Inc(i);
    if i > ParamCount then
      raise Exception.Create('missing argument to option ' + ParamStr(i - 1));
    SetOp(Op, ParamStr(i));
  end;
  
begin
  Result := TOptions.Create;
  try
    i := 1;
    if ParamCount = 0 then
    begin
      Usage;
      Exit;
    end;
    
    while i <= ParamCount do
    begin
      opt := ParamStr(i);
      case opt[1] of
        '/', '-':
        begin
          if Length(opt) > 2 then
            raise Exception.Create('invalid option');
          case opt[2] of
            's': SetOpOnly(opShow);
            'd': SetOp(opApply, NullDacl);
            'e': SetOp(opApply, DefaultDacl);
            'a': SetOpArg(opApply);
            '?', 'h': Usage;
          else
            raise Exception.Create('invalid option');
          end;
        end;
      else
        Result.Drivers.Add(opt);
      end;
      Inc(i);
    end;
  except
    Result.Free;
    raise;
  end;
end;

{ TOptions }

constructor TOptions.Create;
begin
  FDrivers := TList<string>.Create;
end;

destructor TOptions.Destroy;
begin
  FDrivers.Free;
  inherited;
end;

procedure EnablePrivilege(Process: THandle; const Name: string);
var
  privs: TTokenPrivileges;
begin
  FillChar(privs, SizeOf(privs), 0);
  privs.PrivilegeCount := 1;
  privs.Privileges[0].Attributes := SE_PRIVILEGE_ENABLED;
  Win32Check(LookupPrivilegeValue(nil, PChar(Name),
    privs.Privileges[0].Luid));
  Win32Check(
    AdjustTokenPrivileges(Process, False, @privs, SizeOf(privs), nil, nil));
end;

procedure ElevatePrivileges;
var
  process: THandle;
begin
  Win32Check(OpenProcessToken(GetCurrentProcess(), TOKEN_ALL_ACCESS, process));
  try
    EnablePrivilege(process, SE_SECURITY_NAME);
    EnablePrivilege(process, SE_DEBUG_NAME);
  finally
    CloseHandle(process);
  end;
end;

function NtErrorMessage(Status: TNTStatus): string;
var
  buf: PChar;
  h: THandle;
begin
  h := LoadLibrary('ntdll.dll');
  try
    FormatMessage(
      FORMAT_MESSAGE_ALLOCATE_BUFFER or FORMAT_MESSAGE_FROM_SYSTEM or
        FORMAT_MESSAGE_FROM_HMODULE,
      Pointer(h),
      Status,
      0,
      PChar(@buf),
      0,
      nil);
    try
      Result := TrimRight(buf);
    finally
      LocalFree(Cardinal(buf));
    end;
  finally
    CloseHandle(h);
  end;
end;

procedure NtCheck(Status: TNTStatus);
begin
  if Status <> 0 then
    raise EOSError.Create(NtErrorMessage(Status));
end;

procedure WithDriver(const Name: string; Mask: TAccessMask; const Proc: TProc<THandle>);
var
  path: string;
  driverName: TUnicodeString;
  driverAttr: TObjectAttributes;
  handle: THandle;
begin
  path := '\GLOBAL??\' + Name;
  RtlInitUnicodeString(@driverName, PChar(path));
  try
    FillChar(driverAttr, SizeOf(driverAttr), 0);
    driverAttr.Length := SizeOf(driverAttr);
    driverAttr.ObjectName := @driverName;
    
    NtCheck(NtOpenSymbolicLinkObject(@handle, Mask, @driverAttr));
  finally
    RtlFreeUnicodeString(@driverName);
  end;
  try
    Proc(handle);
  finally
    NtClose(handle);
  end;
end;

function GetKernelObjectDacl(Handle: THandle): string;
var
  len: Cardinal;
  desc: PSecurityDescriptor;
  buf: PChar;
begin
  GetKernelObjectSecurity(handle, DACL_SECURITY_INFORMATION, nil, 0, len);
  desc := AllocMem(len);
  try
    Win32Check(
      GetKernelObjectSecurity(handle, DACL_SECURITY_INFORMATION, desc, len, len));

    Win32Check(ConvertSecurityDescriptorToStringSecurityDescriptor(desc,
      SDDL_REVISION_1, DACL_SECURITY_INFORMATION, buf, nil));
    try
      Result := buf;
    finally
      LocalFree(Cardinal(buf));
    end;
  finally
    FreeMem(desc);
  end;
end;

procedure SetKernelObjectDacl(Handle: THandle; const Dacl: string);
var
  secDesc: PSecurityDescriptor;
begin
  Win32Check(ConvertStringSecurityDescriptorToSecurityDescriptor(PChar(Dacl), 
    SDDL_REVISION_1, secDesc, nil));
  try
    Win32Check(SetKernelObjectSecurity(Handle, DACL_SECURITY_INFORMATION, secDesc));
  finally
    LocalFree(Cardinal(secDesc));
  end;
end;

procedure ApplyToDriverHandle(Drivers: TList<string>; const Proc: TProc<string,THandle>);
var
  driver: string;
begin
  ElevatePrivileges;
  
  for driver in Drivers do
    WithDriver(driver, MAXIMUM_ALLOWED,
      procedure(Handle: THandle)
      begin
        try
          Proc(driver, Handle);
        except
          on e: Exception do
            Writeln(Format('failed on "%s": %s', [driver, e.Message]));
        end;
      end);
end;

procedure DoShow(Drivers: TList<string>);
begin
  ApplyToDriverHandle(Drivers,
    procedure(Driver: string; Handle: THandle)
    begin
      Writeln(Format('%s :: %s', [driver, GetKernelObjectDacl(Handle)]));
    end);
end;

procedure DoApply(Drivers: TList<string>; const Dacl: string);
begin
  ApplyToDriverHandle(Drivers,
    procedure(Driver: string; Handle: THandle)
    begin
      SetKernelObjectDacl(Handle, Dacl);
    end);
end;

begin
  try
    with ParseOptions do
      try
        case Operation of
          opShow: DoShow(Drivers);
          opApply: DoApply(Drivers, Dacl);
        end;
      finally
        Free;
      end;
  except
    on E: EOSError do
      Writeln('error: ', e.Message);
    on E: Exception do
      Writeln(e.Message);
  end;
end.

Irony

2009-01-30T15:22:00.003Z

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

2009-01-22T12:15:00.002Z

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

2009-01-15T17:18:00.005Z

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

2009-01-13T18:02:00.003Z

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

2009-01-12T16:05:00.003Z

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

2009-01-03T00:42:00.003Z

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.

Somewhat more efficient smart pointers

2008-11-02T23:44:00.003Z

There was a little to and fro in the comments on yesterday's post on more fluent smart pointers.

It wasn't my intention to create the ultimate in performance for the smart pointer, so I didn't pay much attention to it; I focused mainly on getting an effect from composing a number of simple reusable primitives and ideas.

However, I'd like to point out that since method references are just interfaces, a more efficient implementation can simply implement the interface directly. A yet more efficient implementation might choose to construct a vtable directly, and use a simple 64-bit value on the heap (32-bits for the reference count, 32-bits for the instance pointer), but I'll leave that as an exercise for the reader.

Anyhow, here it is: construction is now sufficient to assign to a location of type TFunc<T>, rather than needing an extra Wrap method:

unit ObjHandle2;

interface

uses SysUtils;

type
  TObjectHandle<T: class> = class(TInterfacedObject, TFunc<T>)
  private
    FValue: T;
  public
    constructor Create(AValue: T);
    destructor Destroy; override;
    function Invoke: T;
  end;
  
implementation

constructor TObjectHandle<T>.Create(AValue: T);
begin
  FValue := AValue;
end;

destructor TObjectHandle<T>.Destroy;
begin
  FValue.Free;
end;

function TObjectHandle<T>.Invoke: T;
begin
  Result := FValue;
end;

end.

Reference-counted pointers, revisited

2008-11-01T19:05:00.002Z

Some time ago, I blogged about writing smart pointers (i.e. reference-counted auto-destruction) in Delphi. While having dinner with some of the speakers at the EKON 12 conference I attended last week, a more fluent interface for using smart pointers in Delphi occurred to me.

I'm using the same TSmartPointer<T> class that I started out with in the previous article, though I've renamed it TObjectHandle<T>. The main tricks I'm pointing out here are (1) to use method references to avoid having to use the Value property all the time, and (2) to use aliases at the point of class definition to make construction slightly more palatable.

So, here's my new TObjectHandle<T> class; the main change, apart from the name, is a new method called Wrap:

type
  TObjectHandle<T: class> = record
  private
    FValue: T;
    FLifetimeWatcher: IInterface;
  public
    constructor Create(const AValue: T);
    property Value: T read FValue;
    class operator Implicit(const AValue: T): TObjectHandle<T>;
    class function Wrap(const AValue: T): TFunc<T>; static;
  end;

The implementation of the new method is pretty simple too:

class function TObjectHandle<T>.Wrap(const AValue: T): TFunc<T>;
var
  h: TObjectHandle<T>;
begin
  h := AValue;
  Result := function: T
  begin
    Result := h.Value;
  end;
end;

The capture of the h local variable will mean that the handle will be kept alive as long as the method reference constructed from the anonymous method is kept alive.

Here it is in use, as two versions, so that the usage difference can be seen. This is also where the additional lubrication of declaring aliases comes in. I start out with a little TCanary class which can keep track of destruction, and has a Name property to demo the fluency of the technique:

type
  TCanary = class
  private
    FName: string;
  public
    destructor Destroy; override;
    property Name: string read FName write FName;
  end;
  
  OHCanary = TObjectHandle<TCanary>;
  HCanary = TFunc<TCanary>;

The destructor prints out the name of the canary when it is destroyed. The two aliases represent an Object Handle for TCanary and a Handle for TCanary respectively. The fluent technique relies on both; the second is used for smart pointer locations and the first for smart pointer construction. There is a tradeoff involved in the technique, between construction fluency and usage fluency:

procedure Test1;
var
  canary: OHCanary;
begin
  // easy construction (implicit operator)
  canary := TCanary.Create;
  // but cumbersome access - always need Value accessor
  canary.Value.Name := 'Test1 canary';
end;

The new style has slightly worse construction, but better actual use:

procedure Test2;
var
  canary: HCanary;
begin
  // cumbersome constructor
  canary := OHCanary.Wrap(TCanary.Create);
  // but much nicer access
  canary.Name := 'Test2 canary';
end;

Without having to access everything by prefixing every access with .Value, a lot of fluency is gained, IMHO.

To summarize, here's the entire ObjHandle.pas unit:

unit ObjHandle;

interface

uses SysUtils;

type
  TObjectHandle<T: class> = record
  private
    FValue: T;
    FLifetimeWatcher: IInterface;
  public
    constructor Create(const AValue: T);
    property Value: T read FValue;
    class operator Implicit(const AValue: T): TObjectHandle<T>;
    class function Wrap(const AValue: T): TFunc<T>; static;
  end;
  
  TObjectHandleArray<T: class> = array of TObjectHandle<T>;

procedure MakeDestroyer(Obj: TObject; out Result: IInterface);

implementation

{ TLifetimeWatcher }

type
  TLifetimeWatcher = class(TInterfacedObject)
  private
    FProc: TProc;
  public
    constructor Create(const AProc: TProc);
    destructor Destroy; override;
  end;

constructor TLifetimeWatcher.Create(const AProc: TProc);
begin
  FProc := AProc;
end;

destructor TLifetimeWatcher.Destroy;
begin
  if Assigned(FProc) then
    FProc;
  inherited;
end;

procedure MakeLifetimeWatcher(out Result: IInterface; const AProc: TProc);
begin
  Result := TLifetimeWatcher.Create(AProc);
end;
  
procedure MakeDestroyer(Obj: TObject; out Result: IInterface);
begin
  Result := TLifetimeWatcher.Create(procedure
    begin
      Obj.Free;
    end);
end;

{ TObjectHandle<T> }

constructor TObjectHandle<T>.Create(const AValue: T);
begin
  FValue := AValue;
  MakeDestroyer(FValue, FLifetimeWatcher);
end;

class operator TObjectHandle<T>.Implicit(const AValue: T): TObjectHandle<T>;
begin
  Result := TObjectHandle<T>.Create(AValue);
end;

class function TObjectHandle<T>.Wrap(const AValue: T): TFunc<T>;
var
  h: TObjectHandle<T>;
begin
  h := AValue;
  Result := function: T
  begin
    Result := h.Value;
  end;
end;

end.

And here's the entire demo program:

{$apptype console}

uses SysUtils, ObjHandle;

type
  TCanary = class
  private
    FName: string;
  public
    destructor Destroy; override;
    property Name: string read FName write FName;
  end;
  
  OHCanary = TObjectHandle<TCanary>;
  HCanary = TFunc<TCanary>;

destructor TCanary.Destroy;
begin
  Writeln(FName, ' died.');
end;

procedure Test1;
var
  canary: OHCanary;
begin
  // easy construction (implicit operator)
  canary := TCanary.Create;
  // but cumbersome access - always need Value accessor
  canary.Value.Name := 'Test1 canary';
end;

procedure Test2;
var
  canary: HCanary;
begin
  // cumbersome constructor
  canary := OHCanary.Wrap(TCanary.Create);
  // but much nicer access
  canary.Name := 'Test2 canary';
end;

begin
  Test1;
  Test2;
end.

Types: Values versus Locations

2008-10-20T11:28:00.003+01:00

Minor thought I had this morning: I was doing some prep work for the conference I'm speaking at next week, and I noticed I was being perhaps overly pedantic about the terminology of types in a way that only matters for imperative languages.

I habitually make explicit the distinction between values and locations of a particular type. I might say, the storing of values of multiple types in a location of a single type is an instance of polymorphism. In describing a class, I might say, this is "an iterator over a stream of values of type T", instead of just saying "an iterator over a stream of T" (no, not a teapot!).

The distinction is important in languages that have mutable state. Locations can have their address taken, they are subject to polymorphism, and the location itself has an identity independent of its value. Values, on the other hand, cannot have their address taken - at most, the value is or contains an address. Values always have a fixed type, but locations may contain values of different types if the type of the location is polymorphic. Locations may be lvalues or rvalues, but values are always rvalues (unless you dereference, index or field-access them). Especially important is the fact that implementations of closures in imperative languages like C#, Delphi, Ruby, etc. have almost always opted to capture locations, not values.

However, consider a pure language, like Haskell. If the language doesn't have mutable state, there's no such thing as a location (at the conceptual level). If you have an iterator in such a language (perhaps modeled using a tail-call continuation design), it's redundant to say "iterator over a stream of values of T" - it's always OK to say "iterator over a stream of T" instead. And the closures might capture values or locations, as performance demands, since the semantics don't change.

Painfully Amateur Philosophy addendum: locations are a pretty physical concept - you know the data is in there in memory somewhere - but values are more of a platonic concept, existing in some pure universe, and we can only refer to them by metaphor and convention by using specific bit patterns interpreted in precise ways. I specifically use the word metaphor in the conceptual metaphor sense: in no way are the electron levels inside the machine representing the ASCII characters of "cat" anything like the furry mammal. Rather, the bit pattern is like a pointer only the human mind can dereference, once it has been transformed into what humans have agreed to be a semantically equivalent representation on screen (which is just a different part of memory) or on paper (which is just bits streamed out over the wire).

Perhaps most people find this obvious and boring, but what interests me is the way the representational power of the bits is entirely unmagical, yet it permits meaning to be stored inside the machine. I say meaning, by which I mean that we humans, the only judges of what is meaningful, find to be meaningful, but no more: I do not think meaning is something inherent in objects, just in judges. What if brains had no more magic in their neurons than the circuits in the machine? (It seems entirely plausible to me, and to many programmers I imagine. And this would constrain those judges to be mere boolean functions over matter patterns.)

In such a scenario, qualia would be beyond our power to deconstruct using physical means, since the brain/machine could be evaluated "on paper", and such an evaluated brain would report the same qualia as you or I, and we would have no way to argue otherwise in a one on one dialogue (this is how I think of the Turing test - as a philosophical concept, not an actual benchmark, which I think is silly and pointless). Under this assumption, there isn't any argument that could prove that the machine isn't conscious which doesn't itself rely on arbitrarily chosen boolean functions which explicitly return false for non-mysterious matter patterns (e.g. capable of "understanding"). Closely related is the problem of other minds, about which I'm on Turing's side - if we can't tell the difference, then there isn't any.

Perhaps consciousness and the experience of qualia is just what matter feels like when it's part of a causal chain? (The technical term, I understand from my Googling, is "type physicalism", though epiphenominalism is related.)

Philosophy over. I need to get back to work :)

WASD's little known alternative, QWAS

2008-10-18T23:26:00.006+01:00

I was reading a review of a new Microsoft gaming keyboard today and I noticed that it has extra highlighting for the traditional WASD keyboard layout most commonly used by first-person shooters (FPSs).

This interests me because I don't use WASD; I use a variant that I have almost never seen anyone else describe, namely, QWAS, with W for forward, Q/S for strafe left/right, and A for reverse.

It was a long time in gestation. I started out playing Doom with just the keyboard, like most other people at the time, but then I read - I forget where and can't find the reference - about using the mouse for looking and the keyboard, specifically the Z and X keys, for strafing, with Space, Ctrl and mouse buttons used in some combination for Use, Fire, Forward, Run, etc. I didn't find this combination especially easy to use, though, so it wasn't long before I stumbled onto the QWAS hold I use today. I do, however, find it puzzling that so few other people use it.

The reason I don't use WASD is because I think the layout is awkward for the wrist when the keyboard is centrally positioned, ready for touch-typing:

Moreover, since, like most men, my ring finger is much longer than my index finger, WASD means my ring finger on the A key is in an uncomfortable cramp-prone position:

When this is compared with the QWAS layout, the advantage in comfort and ergonomics - for my hand shape and keyboard positioning, at least - is clear:

The Search for Differentiation and Build vs Buy/Adopt/Coopt

2008-10-18T19:22:00.003+01:00

There's been some chatter in the development blogosphere recently about that old chestnut, the build vs buy decision; but in these days of open source development, there are more alternatives to build: adoption and cooption (private forking / customized modules etc.).

Jeff Atwood wrote an article about not being ashamed to write your own software (i.e. build) when the functionality in question is core to your business. Much of the reaction to Jeff's fairly strongly stated article has been pulling in the opposite direction. I'd like to argue back in Jeff's direction, though.

The basic trouble I have is that the vast majority of open source is crap. Once you tread outside the critical path of high-user-base server-side software, like (to take three examples completely at random) Linux, Hibernate and MySQL, you very quickly get stuck in the mire; even then, much of the "good" open-source software is only good in parts.

For example, if you're looking for a mature, well-designed and stable interface for writing drivers for Linux - exactly what is needed to make supplying binary drivers viable for hardware vendors - tough luck, buddy. Economically speaking, incentives in open source are almost always not aligned with consumers' interests, but rather with the companies which hire the developers: and those guys are usually consultant / service shops, i.e. aligned with corporate customers, not consumers. Firefox is an exception because of Google advertising revenue, which is correlated with consumer adoption, thus their incentives are aligned.

Rails has a solid concept and has a reasonably good API, but its execution is, IMHO, not great. I have little patience for server-side technologies that aren't thread-safe, as request/response cycles are trivially parallel; though, from an historical viewpoint I can understand it, as relatively few scripting languages implement threading. All the same, though, the kind of coding that would make a server-side library thread-unsafe, I wouldn't tolerate even if the platform was single-threaded: it implies poorly-factored mutable global state. I wouldn't touch PHP with a barge pole - I have zero technical respect for the language.

To compete, you need differentiation: you need to do something, for some subset of the market, in a way that is head and shoulders better than every other choice. Open source (or, indeed, buying) can only give you what everyone else has; you need to add in the magic yourself that makes you stand out. Private forks of open-source software are one way of doing that, but is vulnerable to all the usual problems that forking has (staying current, merging bugfixes, divergent evolution, etc.). Creating your differentiating software yourself means your codebase will be smaller and more perfectly adapted to your problem domain, and thus easier to maintain and keep up to date than a private fork of an ongoing public open-source project.

The only real question is which software in your organization is, in the language of strategic management, going to help give you a sustainable competitive advantage. Open source software and third-party libraries can never give you that (unless you own the founding team & brand), because they are equally available to your competitors. Choosing the balance of build vs buy means trading off risk and cost versus lack of differentiation. You have to measure and compare the resources available to you and the risk of non-completion of differentiated software, taking into account opportunity cost, with the lack of differentiation that would come from the buy / ad/coopt decision.

Where the balance lies thus depends on both sides: how much [human+monetary] capital you have, versus the competitive landscape on the other. Whether a third-party library exists or not, in and of itself, is not a sufficient reason to always use it. Making users happy isn't sufficient; you must make them happier than the competition, and that's not going to happen if you don't do something the competition isn't already doing. The only thing that holds you back is risk & capital versus the reward in differentiation.

Anonymous methods as an alternative to 'out' parameters

2008-09-25T19:05:00.003+01:00

Out parameters are a useful language feature for multiple results, particularly when the language in question doesn't have tuples as a first-class feature. Even though Java omitted pass-by-reference (meaning both var and out in Delphi parlance), C# did not follow its lead and includes both parameter-passing semantics. And so it follows that the .NET method System.Int32.TryParse(String,Int32&) is possible in C#, but not in Java.

The API works well enough when you want to put the extra return value(s) into local variables or visible fields. What about times when you want to put the return value into a property, though? Since you can't (generally) take a reference to a property, you have to manually create a local variable, pass the local variable by reference, and then, in a separate statement, assign the variable to the property.

Anonymous methods can provide an "out" here, if you'll pardon the pun. By passing a setter instead of a mutable reference, you can escape from this constraint. Here's are two overloaded ReadLine functions, one using the out mechanism, the other using the setter pattern:

function ReadLine(const Prompt: string; out Dest: string): Boolean; overload;
var
  line: string;
begin
  Write(Prompt, '> ');
  Flush(Output);
  Readln(line);
  Result := line <> '';
  if Result then
    Dest := line;
end;

function ReadLine(const Prompt: string; const Setter: TProc<string>): Boolean; overload;
var
  line: string;
begin
  Write(Prompt, '> ');
  Flush(Output);
  Readln(line);
  Result := line <> '';
  if Result then
    Setter(line);
end;

As can be seen, the code that uses setters versus out parameters is little different. (It would be more different in a language that requires definite assignment, like C#, as otherwise we would have to set Dest to some value in the case of no entry.)

The real difference is in the usage point of this idiom. (And don't forget, this is an idiom; it might look odd the first time you see it, but when you understand anonymous methods, or even just the idiom, it's a trivial pattern and easy to understand.) Here's the definition of a class with a couple of properties, and a couple of functions. The first uses the out idiom, and the second uses the setter idiom:

type
  TFrob = class
  private
    FFoo: string;
    FBar: string;
  public
    property Foo: string read FFoo write FFoo;
    property Bar: string read FBar write FBar;
  end;

// Using 'out' idiom - requires separate assignment statement
function WorkWithFrob: Boolean;
var
  frob: TFrob;
  temp: string;
begin
  frob := TFrob.Create;
  try
    if not ReadLine('Give me Foo', temp) then
      Exit(False);
    frob.Foo := temp;
    if not ReadLine('Give me Bar', temp) then
      Exit(False);
    frob.Bar := temp;
    Writeln(Format('Your foo is %s and bar is %s', [frob.Foo, frob.Bar]));
    Result := True;
  finally
    frob.Free;
  end;
end;

// Using 'setter' idiom - can be done inline
function WorkWithFrob2: Boolean;
var
  frob: TFrob;
begin
  frob := TFrob.Create;
  try
    if not ReadLine('Give me Foo', procedure(x: string) begin frob.Foo := x; end)
        or not ReadLine('Give me Bar', procedure(x: string) begin frob.Bar := x; end) then
      Exit(False);
    Writeln(Format('Your foo is %s and bar is %s', [frob.Foo, frob.Bar]));
    Result := True;
  finally
    frob.Free;
  end;
end;

This idiom isn't useful very often, but when the right situation comes up, it's really quite nice to have, especially when you need persistent references to properties - e.g. when you need to store the reference in some structure somewhere, and update it with different values over time.

Viewed more generally, anonymous methods / method references can act as kinds of pipes that join up producers and consumers of data, with getters (TFunc<TResult>) for consumer-pull and setters (TProc<TArg>) for producer-push.

Google Developer Day 2008, London

2008-09-17T17:40:00.003+01:00

I was at Google Developer Day here in London yesterday. Most of it was pretty light on technical details, but there was some good info on V8, Google's new JavaScript engine which is used in Google Chrome.

The specific sessions I went to were Intro to Android, Intro to Android SDK, Google Data API mashups, and V8 - "the Chrome Engine" (sic). The heavy tilt towards Android was chiefly driven by curiosity after Mike Jennings took out a pre-production OHA phone and demoed it in the keynote. It looks reasonably neat, borrowing some nifty effects from Apple's iPhone; no pinch-zooming though.

Intro to Android was a mix of business / very lightweight technical details about the phone. Apparently, Google has twisted some arms in back-rooms to get buy-in from operators & OEMs, so anything with the OHA / Android branding etc. should have some minimum level of openness etc. Should be a welcome relief from the vice-grips of Apple. There wasn't much description of the Dalvik VM running behind the scenes, other than that you take your .class files from javac and run them through a processor to get running on the device, and apparently the guy Mike talks to about the VM is "very bright". That was mentioned a number of times, so it must be important.

The Android SDK intro was given by a guy (Carl-Gusaf Harroch) from a local startup, not an actual Google guy. He very roughly described content providers, and also briefly outlined some entries in the application manifests, which are the mechanism by which the Android OS figures out what events your application is interested in (phone call arrived, moved certain distance according to GPS, that kind of thing). There was a laboured comparison of content providers with REST, in that there are methods that correspond to CRUD operations, but apparently there are other concerns such as observability etc. which make them not as simple as REST (and thus an invalid comparison, in my view). Apparently content stored on the phone and exposed to other applications is heavily skewed towards assuming that the content is living in an SQLite DB.

The GData mashup session wasn't interesting to anyone who has interacted with Google REST / AtomPub APIs even trivially. Once upon a time I wrote a blogger post app, so I didn't learn much.

Oh, and if you are writing a client to GData etc., I recommend that you don't start by trying to grok any of the Google API libraries unless you need deep integration. I didn't like the look of them last time (Java-itis, factories etc. everywhere), and I'm fairly sure they haven't improved.

Finally, I went to the V8 talk by Kevin Millikin. This was the best and most technical by a long, long way; to be honest, if it hadn't been for this talk, the day would have been a waste, on net. He described some V8 implementation details.

Roughly speaking, the main approach V8 takes is to try and shoe-horn classes into the JavaScript dynamic type system so that other, more classical dynamic object-oriented optimizations can be applied in the future. The way it works is with hidden classes. Every freshly new'd up object obj gets the same class, call it class_0. The first time you add a property, call it 'x', to obj, a new class class_1 is created which has a single property called 'x'. Additionally, a class transition edge is added to class_0 pointing at class_1, and this edge is labeled 'x'. This means that all objects which are freshly new'd up and have a single property called 'x' added to them will all share the same class. So, in theory, every object in the system which has the same properties in the same order will share the same class. The class transitions described above form a tree (I asked), and can't close over to make a dag, because if that happened, enumeration order would change. (I believe this is an implementation detail of ECMA, so people shouldn't be relying on it; however, it's something the V8 folks discovered that they could not change from extant practice.) This in turn means that if you do have conditional branches in your JavaScript constructors, you should assign to all properties in the same order, if that is feasible.

Anyhow, the use of classes as indicated above means that object use sites can now be optimized based on the runtime class of the object. Here's a specific example: whenever you access a property in JS running on V8, the access site will be a little stub function using one of 4 templates: uninitialized, pre-monomorphic, fast-monomorphic, and megamorphic. The first time the access site is invoked, the runtime class is inspected and noted, and the stub moves to the pre-monomorphic state. The second time it's accessed, the runtime class is checked against the previous class and if it's the same, the stub moves to the fast-monomorphic state, and is written so that it is very simple: compare object type, if it's as expected then dereference to object storage, then load property at the specific offset (stored in the property in the class but inlined as machine code in the access site). If the class wasn't as expected, then the stub is changed to the megamorphic state. Finally, the megamorphic state is the slow path that falls back to hash-based lookup, just like most other JS implementations.

Since arrays in JS are just tightly-packed hash buckets with particular key patterns, the same approach could be taken but it wouldn't necessarily be fast. Apparently the V8 folks discovered that a lot of artificial JS benchmarks were based around array manipulations, so they put a little work in this, but they're not finished in this area (as far as I could make out). In any case, array access strategy is governed by a heuristic; for small packed arrays accessed with integers, a direct lookup can be made. For larger, sparse arrays, the property access mechanism is used.

Variable capture in closures (a topic dear to my heart at this point) also works along similar lines as property creation, from what Kevin described. There is a caveat: if you are using the "with" statement in JavaScript, or there is eval( between the variable definition and the access site in your closure, then the access can't be optimized; these constructs fall back to the hash-based lookup, because they effectively need to use dynamic scope. So, don't create closures in that way unless you're prepared for the speed bump.

The majority of the JS standard library, things like array.join etc., are implemented in JavaScript itself in V8. They're using a special %AddProperty function to make them non-enumerable. V8 also uses a freeze-dried heap mechanism to reduce the cost of initializing the standard library. It can essentially save and restore the heap, with appropriate relocations etc. as required, so that it doesn't have to reparse everything on startup.

The garbage collector for V8 looks less interesting as a source of performance. It's almost certainly an improvement on what other JS implementations are using for GC, but I think it's some way from the last word on the topic. It has only 2 generations, so intermediate live objects that get promoted when collecting new-space will eventually force a costly old-space collection. Kevin didn't say that they were using write barriers to reduce need to scan old-space looking for pointers to new-space, but grepping the V8 sources turns up some write barrier hits, so maybe they are. V8's GC is definitely better than reference counting as implemented in IE of older days, of course.

Since the main approach taken thus far was just to give values a class, and use that to optimize property access, there is still a lot of scope for optimization in V8. I wouldn't be surprised to see significant (2-5x) performance improvements in the not too distant future in V8, as more techniques are integrated. They're currently going straight from the JS AST to machine code, no inlining of aforementioned property access sites (AFAICT - there was a 'ret' at the end of the demo access site). The main thing is (a) they have objects pinned down to types now, and (b) hopefully as JS developers learn how to make code run fast under this paradigm, objects will look even more type-ful and thus increase scope for other optimizations.

Exogenous Exceptions (oh and another Vista rant :)

2008-09-11T04:01:00.003+01:00

Eric Lippert has just posted an entry about "vexing exceptions", talking about the various buckets he classifies exceptions into and different approaches for handling them:

Vexing exceptions are the result of unfortunate design decisions. Vexing exceptions are thrown in a completely non-exceptional circumstance, and therefore must be caught and handled all the time.

[...]

The classic example of a vexing exception is Int32.Parse, which throws if you give it a string that cannot be parsed as an integer. But the 99% use case for this method is transforming strings input by the user, which could be any old thing, and therefore it is in no way exceptional for the parse to fail.

[...]

And finally, exogenous exceptions appear to be somewhat like vexing exceptions except that they are not the result of unfortunate design choices. Rather, they are the result of untidy external realities impinging upon your beautiful, crisp program logic. [Example of file-not-found follows, and points out that File.Exists check would only be a race.]

However, I strongly disagree on his suggestion that you try to catch exogenous exceptions, and somewhat disagree on the "vexing" exceptions (here, it's probably just the specific example he chose that I don't really agree with).

In my opinion, exceptions should, in general, be propagated all the way to a user-visible dialog box / notification message, if the exception represents an error by the user. So, for example, if a user enters a floating-point value or a string value in a box that should semantically be an integer, it is fine for an exception in Int32.Parse to bubble its way back into the user's view - so long as the message in the exception is meaningful to the user, and is written in the correct language / jargon etc. If not, then certainly the exception should be wrapped in another exception and re-propagated, but the exception itself shouldn't be just caught.

Of course, if there is valid logic for a failure case that doesn't simply mean telling the user about a problem in their input / what they're trying to do, then that's a situation where TryParse etc. makes sense.

On the exogenous question, catching these is extremely problematic, because when the user eventually sees the message, they'll need to figure out what went wrong. So, if you have a file access problem, the very first exception raised - the exogenous one when the CreateFile call at the heart of things failed - should have a message associated with it indicating that such-and-such file couldn't be accessed. This is the same message that should eventually be propagated to the user, either in an event log, a dialog box, or other notification mechanism, particularly if the high-level attempted action was user-initiated.

To do otherwise leaves the user stranded with a generic, non-specific (and thus meaningless) "I couldn't do something" message. I've seen far too much MS software that gives non-specific and non-actionable error messages in failure situations that this kind of advice really annoys me unless it is very carefully qualified and described.

If anything, exceptions should be wrapped rather than caught, with higher-level semantic information wrapping the underlying reason. So, if you're trying to e.g. modify a record in a data entry application, the chain of failure might be "couldn't modify record because" -> "couldn't contact database for locking because" -> "couldn't connect to database server because" -> "remote server name FooBar could not be found". This kind of message has information about every level of the stack, and should a user have to e.g. contact IT, the full message (the technical details can be hidden in a pop-out dialog etc.) is 100% actionable, and even regular users, let alone power users, may find it actionable.

Software does not have AI-level capabilities, and is very far from it. Describing what went wrong is 100x more useful than presenting something vaguely actionable. Unless the error case is very common, and thus you are very certain what the fix is, you should not try to present "actionable" advice over describing what went wrong, simply because to give good actionable advice in general, you need to embed an expert system; without populating the expert system with data, it needs to include IT-support-level AI, which like I said, isn't happening any time soon.

Here's a specific example that really burned me just the other day. Vista Ultimate has a full PC backup capability. I found out that my main HD is failing (SMART alert). I wanted to restore that backup onto a different disk of the same make and size (actually, right down to consecutive serial numbers). However, my machine is rather complex - there are 7 SATA disk devices in the machine. The Vista OS DVD failed to restore the backup to my perfectly-matched disk, but I have no idea why. All I do know is that the error message was "vaguely actionable":

Error details: There are too few disks on this computer or one or more of the disks is too small. Add or change disks so they match the disks in the backup and try the restore again. (0x80042401)

This message is completely and utterly useless, because it does not describe what went wrong, only "how" to fix it - but because the software isn't AI-level and doesn't include an expert system, it itself can't produce a specific set of instructions.

In this machine, I had 4x1TB disks, 1x400GB disk, and 1x200GB disk; the backup was on the 400GB disk and the target of the restore was the 200GB disk. 2 of the 1TB disks were blank and formatted. Thus, there was no lack of disks or space. Similarly, the target of the restore was at Disk 0, achieved through careful selection of the SATA connection on the motherboard. Still didn't work though, and I can't fix it because the error message is following the wrong philosophy for our current knowledge of AI.

FWIW, here's another user's experience with this problem. Notice the procedure to actually show the user the actual error, rather than the useless message:

Boot from the Vista DVD
Go to Repair Computer -> Command Prompt
Go into Regedit
Under HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows NT\CurrentVersion\
Create the key: Asr
Under Asr create the key LogFileSetting
Under LogFileSetting create the dword EnableLogging with the value 1
Under LogFileSetting create the string LogPathName (string) with a value such as D:\Asr.log
- you should specify a physical drive (e.g. I used the drive you are going to restore from) not the ramdrive (X:) so that the log is saved after reboot.
Exit Regedit
From the Repair menu launch Complete PC Restore
Attempt the Complete PC Restore
When you get the error, check the logging path to be sure the Asr.log file exists. I did that by going back to the Command Prompt and getting a directly listing before rebooting.

This is disgraceful, and frankly, unforgivable. Don't do this with your exogenous exceptions.

Vista LanmanServer falling apart on you?

2008-09-09T11:05:00.004+01:00

I've been having a lot of trouble over the past day or so with my Vista machine. Since I can't tolerate it long as a main desktop, it's primarily acting as a file and print server.

Over the past day, however, the Vista network sharing service, LanmanServer, has been falling over on me. All attempts to connect to Vista shares fail with error 1130, aka ERROR_NOT_ENOUGH_SERVER_MEMORY, and the event log on Vista is filled with 2017 (primarily) and 2021 Event IDs:

2017: The server was unable to allocate from the system nonpaged pool because the server reached the configured limit for nonpaged pool allocations.

2021: The server was unable to allocate a work item %d times in the last 60 seconds.

Fixing it required stopping Computer Browser (net stop browser) and Server (net stop server) and restarting them (net start etc.) on the Vista machine.

Other people have been having this problem too; here's a relevant thread where you can read up about these frustrations:

[...] Vista Ultimate file/print server that is accessed by various Vista and XP client workstations. Recently - and increasingly - the XP machines have been spontaneously losing their connections to the Vista file server. This started out as a minor annoyance about a month ago, but has escalated to the point where the XP clients cannot stay connected for more than 5-30 minutes[...]

Anyhow, I've found a solution that appears to work, linked to at the end of the previous thread (which makes me suspect it fixed the problem for those folks too).

Smart pointers in Delphi

2008-09-04T22:47:00.003+01:00

Strongly-typed smart pointers are now possible in Delphi, leveraging the work on generics. Here's a simple smart pointer type:

  TSmartPointer<T: class> = record
  strict private
    FValue: T;
    FLifetime: IInterface;
  public
    constructor Create(const AValue: T); overload;
    class operator Implicit(const AValue: T): TSmartPointer<T>;
    property Value: T read FValue;
  end;

Here it is in action, where TLifetimeWatcher is a little class that executes some code when it dies:

procedure UseIt;
var
  x: TSmartPointer<TLifetimeWatcher>;
begin
  x := TLifetimeWatcher.Create(procedure
  begin
    Writeln('I died.');
  end);
end;

Here's the full project code that defines TSmartPointer<>, TLifetimeWatcher, and the above test routine:

{$APPTYPE CONSOLE}

uses
  SysUtils;

type
  TLifetimeWatcher = class(TInterfacedObject)
  private
    FWhenDone: TProc;
  public
    constructor Create(const AWhenDone: TProc);
    destructor Destroy; override;
  end;

{ TLifetimeWatcher }

constructor TLifetimeWatcher.Create(const AWhenDone: TProc);
begin
  FWhenDone := AWhenDone;
end;

destructor TLifetimeWatcher.Destroy;
begin
  if Assigned(FWhenDone) then
    FWhenDone;
  inherited;
end;

type
  TSmartPointer<T: class> = record
  strict private
    FValue: T;
    FLifetime: IInterface;
  public
    constructor Create(const AValue: T); overload;
    class operator Implicit(const AValue: T): TSmartPointer<T>;
    property Value: T read FValue;
  end;

{ TSmartPointer<T> }

constructor TSmartPointer<T>.Create(const AValue: T);
begin
  FValue := AValue;
  FLifetime := TLifetimeWatcher.Create(procedure
  begin
    AValue.Free;
  end);
end;

class operator TSmartPointer<T>.Implicit(const AValue: T): TSmartPointer<T>;
begin
  Result := TSmartPointer<T>.Create(AValue);
end;

procedure UseIt;
var
  x: TSmartPointer<TLifetimeWatcher>;
begin
  x := TLifetimeWatcher.Create(procedure
  begin
    Writeln('I died.');
  end);
end;

begin
  try
    UseIt;
    Readln;
  except
    on E:Exception do
      Writeln(E.Classname, ': ', E.Message);
  end;
end.

Update: Fixed capture - was capturing a location in the structure, which of course will be freely copied etc.

Anonymous methods in testing / profiling - Pt. 2

2008-08-31T18:24:00.003+01:00

In the last post, I only went into profiling. Here's a simple testing usage scenario. Suppose you want to make sure that a certain body of code throws an exception of a particular type. That means you have to wrap it up in a try / except block, and test the type of the exception. The logic to do this would be quite repetitive if it had to be expanded out long-hand. Fortunately, that's not the case:

procedure ExpectException(ExClass: ExceptClass; const Code: TProc);
var
  noThrow: Boolean;
begin
  noThrow := False;
  try
    Code;
    noThrow := True;
  except
    on e: Exception do
      if not e.ClassType.InheritsFrom(ExClass) then
        raise Exception.CreateFmt('Failed - %s expected, %s actually raised',
          [ExClass.ClassName, e.ClassName]);
  end;
  if noThrow then
    raise Exception.CreateFmt('Failed - %s not raised', 
      [ExClass.ClassName]);
end;

Here it is in use:

var
  list: TList;
begin
  list := TList.Create;
  try
    
    ExpectException(EListError, procedure
    begin
      list[42] := nil;
    end);
    
  finally
    list.Free;
  end;
end;

Anonymous methods in testing / profiling situations

2008-08-31T16:58:00.003+01:00

One situation in which anonymous methods are particularly useful is for ad-hoc profiling and testing scenarios. For both profiling and testing, it is code itself that one wants to work with. I.e. the question you are trying to answer is "test this code", or "time this code". Using code as a parameter is a natural fit for this problem.

I'll start with a very simple profile harness. It does little more than run a code block a number of times and report on how long it took. Here's the definition of the class:

  TBenchmarker = class
  private
    const
      DefaultIterations = 3;
      DefaultWarmups = 1;
    var
      FReportSink: TProc<string,Double>;
      FWarmups: Integer;
      FIterations: Integer;
      FOverhead: Double;
    class var
      FFreq: Int64;
    class procedure InitFreq;
  public
    constructor Create(const AReportSink: TProc<string,Double>);

    class function Benchmark(const Code: TProc; 
      Iterations: Integer = DefaultIterations; 
      Warmups: Integer = DefaultWarmups): Double; overload;

    procedure Benchmark(const Name: string; const Code: TProc); overload;
    function Benchmark<T>(const Name: string; const Code: TFunc<T>): T; overload;

    property Warmups: Integer read FWarmups write FWarmups;
    property Iterations: Integer read FIterations write FIterations;
  end;

This API has a couple of interesting features. The constructor takes method reference argument indicating where output - the results of the benchmarking - will go. This idiom makes it easy for users of the class to direct the output. It's loosely coupled, just like an event (after all, an event - a method pointer - is almost the same thing as a method reference), but it also doesn't require that the user create a whole method just for the purpose of sending the output off to whereever it ends up (on the console, in a UI, etc.).

Secondly, the Benchmark overloaded methods themselves - these take the actual code to be measured. The Benchmark overloads will execute the passed-in code a number of times for warmup, and then a number of times for the actual measurement. The return value of the class function version is the number of seconds an average iteration took; the instance function versions send off the result to the reporting sink.

These two idioms - data sinks and sources, and taking in a block of code which can be executed a carefully constructed context - are common usage patterns of anonymous methods. I'll get into them further in later posts.

Here's the Benchmark class in practice:

procedure UseIt;
const
  CallDepth = 10000;
var
  b: TBenchmarker;
  x: TSomeClass;
  intf: ISomeInterface;
begin
  b := TBenchmarker.Create(procedure(Name: string; Time: Double)
  begin
    Writeln(Format('%-20s took %15.9f ms', [Name, Time * 1000]));
  end);
  try
    b.Warmups := 100;
    b.Iterations := 100;

    x := TSomeClass.Create;
    intf := x;
      
    b.Benchmark('Static call', procedure
    begin
      x.StaticCall(x, CallDepth);
    end);

    b.Benchmark('Virtual call', procedure
    begin
      x.VirtCall(x, CallDepth);
    end);

    b.Benchmark('Interface call', procedure
    begin
      intf.IntfCall(intf, CallDepth);
    end);
    
  finally
    b.Free;
  end;
end;

The benefits of variable capture should be clear here. The segments of code to be benchmarked can freely access variables in the outer scope.

Finally, here's the complete implementation, including TBenchmark definition and use:

program am_profiler;

{$APPTYPE CONSOLE}

uses
  Windows, SysUtils;

type
  TBenchmarker = class
  private
    const
      DefaultIterations = 3;
      DefaultWarmups = 1;
    var
      FReportSink: TProc<string,Double>;
      FWarmups: Integer;
      FIterations: Integer;
      FOverhead: Double;
    class var
      FFreq: Int64;
    class procedure InitFreq;
  public
    constructor Create(const AReportSink: TProc<string,Double>);
    class function Benchmark(const Code: TProc; 
      Iterations: Integer = DefaultIterations; 
      Warmups: Integer = DefaultWarmups): Double; overload;
    procedure Benchmark(const Name: string; const Code: TProc); overload;
    function Benchmark<T>(const Name: string; const Code: TFunc<T>): T; overload;
    property Warmups: Integer read FWarmups write FWarmups;
    property Iterations: Integer read FIterations write FIterations;
  end;
  
{ TBenchmarker }

constructor TBenchmarker.Create(const AReportSink: TProc<string, Double>);
begin
  InitFreq;
  FReportSink := AReportSink;
  FWarmups := DefaultWarmups;
  FIterations := DefaultIterations;
  
  // Estimate overhead of harness
  FOverhead := Benchmark(procedure begin end, 100, 3);
end;

class procedure TBenchmarker.InitFreq;
begin
  if (FFreq = 0) and not QueryPerformanceFrequency(FFreq) then
    raise Exception.Create('No high-performance counter available.');
end;

procedure TBenchmarker.Benchmark(const Name: string; const Code: TProc);
begin
  FReportSink(Name, Benchmark(Code, Iterations, Warmups) - FOverhead);
end;

class function TBenchmarker.Benchmark(const Code: TProc; Iterations,
  Warmups: Integer): Double;
var
  start, stop: Int64;
  i: Integer;
begin
  InitFreq;
  
  for i := 1 to Warmups do
    Code;

  QueryPerformanceCounter(start);
  for i := 1 to Iterations do
    Code;
  QueryPerformanceCounter(stop);
  
  Result := (stop - start) / FFreq / Iterations;
end;

function TBenchmarker.Benchmark<T>(const Name: string; const Code: TFunc<T>): T;
var
  start, stop: Int64;
  i: Integer;
begin
  for i := 1 to FWarmups do
    Result := Code;
  
  QueryPerformanceCounter(start);
  for i := 1 to FIterations do
    Result := Code;
  QueryPerformanceCounter(stop);
  
  FReportSink(Name, (stop - start) / FFreq / Iterations - FOverhead);
end;

type
  ISomeInterface = interface
    procedure IntfCall(const Intf: ISomeInterface; depth: Integer);
  end;
  
  TSomeClass = class(TInterfacedObject, ISomeInterface)
  public
    procedure VirtCall(Inst: TSomeClass; depth: Integer); virtual;
    procedure StaticCall(Inst: TSomeClass; depth: Integer);
    procedure IntfCall(const Intf: ISomeInterface; depth: Integer);
  end;

{ TSomeClass }

procedure TSomeClass.IntfCall(const Intf: ISomeInterface; depth: Integer);
begin
  if depth > 0 then
    Intf.IntfCall(Intf, depth - 1);
end;

procedure TSomeClass.StaticCall(Inst: TSomeClass; depth: Integer);
begin
  if depth > 0 then
    StaticCall(Inst, depth - 1);
end;

procedure TSomeClass.VirtCall(Inst: TSomeClass; depth: Integer);
begin
  if depth > 0 then
    VirtCall(Inst, depth - 1);
end;

procedure UseIt;
const
  CallDepth = 10000;
var
  b: TBenchmarker;
  x: TSomeClass;
  intf: ISomeInterface;
begin
  b := TBenchmarker.Create(procedure(Name: string; Time: Double)
  begin
    Writeln(Format('%-20s took %15.9f ms', [Name, Time * 1000]));
  end);
  try
    b.Warmups := 100;
    b.Iterations := 100;

    x := TSomeClass.Create;
    intf := x;
      
    b.Benchmark('Static call', procedure
    begin
      x.StaticCall(x, CallDepth);
    end);

    b.Benchmark('Virtual call', procedure
    begin
      x.VirtCall(x, CallDepth);
    end);

    b.Benchmark('Interface call', procedure
    begin
      intf.IntfCall(intf, CallDepth);
    end);
    
  finally
    b.Free;
  end;
end;

begin
  try
    UseIt;
  except
    on E:Exception do
      Writeln(E.Classname, ': ', E.Message);
  end;
end.

Venting on Vista

2008-08-22T05:59:00.022+01:00

First up - apologies! This post has no technical content whatsoever about compilers, programming languages or Delphi. It's just a rant: I want to document my Vista annoyances so that I can hopefully move on. You know, denial, acceptance, and all that. Maybe I'll even look back on this post a few years from now and see where I was wrong!

Shell

Almost all my annoyances about Vista come from the Explorer shell. I've reached the point where I am somewhat seriously considering writing my own shell that supports the bare minimum, but the fact that file dialogs would be beyond my reach without some fairly hardcore system DLL replacement holds me back. For now.

Non-configurable Explorer Toolbar

The toolbar is no longer configurable, and in particular, it is no longer possible to move all three components - menu, tool buttons and location - onto a single row to maximize client area. Here's what I mean: my default Explorer setup has a height, from top of window to start of listview client area, of 65 pixels:

The equivalent in Vista has a height of 125 pixels, i.e. wasting over 90% more screen space for no benefit:

And yes, I run Vista without any themes, for a number of reasons: I'm not impressed, the compositing uses resources I'd rather spend on other things, and I often interact with Vista using RDP and I'd rather not have to deal with two different UI styles. And yes, I want that menu bar: it has useful commands like, you know, map network drive.

Missing XP-style Start Menu

This is the next biggest issue. If they had put in an option to have an XP-style menu combined with the new search box, a good deal of grief would have been forgiven. As it is, I detest the new start menu. The only backward-compatible option is a Windows 95 option, which is bizarre from my point of view - XP has been Microsoft's longest selling OS, and it's the immediate predecessor to their new version, and the backward compatible option they offer is for an obsolete style that's over 10 years old? It makes no sense to me.

Here are some of the niggles with the new menu that annoy me so much.

Constant clicking

With XP, the fact that a menu expanded when hovered over meant that muscle memory could be used for navigation. I've used TweakUI to reduce this hover time so that it's just long enough that mouse navigation doesn't cause redundant sub-menu opening. On Vista, I have to click and scroll around to find things. I'm almost in the same situation as if I had to browse through the shortcuts in the file system directly with Explorer.

Constrained tiny little box

With the XP menu, I have the entire height of the screen in which to show a submenu. Since I keep my top-level submenus strictly categorized, with headers like Development, Tools, CodeGear etc. for direct access to application shortcuts, and a catch-all group called Groups which contains all those start-menu folders that application vendors add, I have very dense menus with an efficient navigation experience, a lot like the Control Panel menu (more on that next). Not so on Vista. Everything is crammed into a tiny little box, complete with wee little scrollbars, even while I have a relatively vast expanse of 24" monitor begging to be used.

Missing GUI Navigation in Control Panel

I mostly use the Control Panel menu from the Start Menu to access control panel applets, because (as a developer) I'm always tweaking this or that setting.

Unfortunately, Microsoft have added more hierarchy to the control panel (not a problem, in my view, because there are more options in Vista), but have provided less means of navigating it! Here are some concrete examples.

No submenus in Control Panel menu from Start Menu

Look at the XP Control Panel menu:

Now take a look at the Vista Control Panel menu:

Spot the differences? The XP menu provides direct access to printers, network adapters and scheduled tasks, etc.; whereas the Vista menu has hidden those things away inside the applets themselves.

Now, the Vista equivalent of Scheduled Tasks is a lot more capable, but it's also a lot more complicated, seems to expose some innards of the Windows system such that it's easier to break, and has a dog-slow UI with three - I counted them, three - nested client areas in the center panel. I'm not convinced that the old shell view extension mechanism wasn't better.

Inconsistent Explorer / Control Panel navigation

It's a similar story for network adapters. I occasionally have need to change IP or other settings for various reasons. For example, all my desktop machines have multiple ethernet adapters and I ocassionally route wireless traffic from a base station in one port and out the other to the broadband router.

Since the Control Panel submenu is no longer available, I have to go through the new "Network and Sharing Center" and try to figure out where the adapter configuration is hidden. Eventually I alight upon "Manage network connections", but this pops up a separate window which appears to be a subfolder of the Control Panel called "Network Connections" - at least, judging by the location bar:

However, try to find this folder either by navigating the control panel or by browsing the control panel's shell namespace tree, and you won't find it. The quickest way to get back to it is by creating a shortcut, but that's not so easy to figure out either, seeing how Microsoft removed the "Favorites" menu. What you need to do is click and drag the small icon in the location bar into some Explorer folder view, like the desktop.

And that brings me to another point. In Vista, you can't explore the Control Panel namespace using Explorer's treeview. In fact, if you start out in an Explorer window that has a treeview visible, and you select the Control Panel child of the Desktop namespace, the treeview disappears. I find this disturbing and disconcerting. It's almost like the feature had bugs, so they had to disable that way of accessing the Control Panel. Even the new context-sensitive Explorer toolbar disappears when the Control Panel is entered, removing with it the ever useful "rotate icon size" (Views) button that looks like a menu, and the Organize menu that looks like a button.

Missing Security tab for multiple selection

Onwards, to more practical every-day matters. I have multiple hard drives (11 3.5" disks at last count, totalling 4.75 ISO-TB, or about 4.3 real TB), installed across three desktop machines. These drives are almost all formatted with NTFS, with a single ext3 disk for Linux. Apart from OS boot drives, most of these drives have no fixed abode; they are liable to be swapped around or accessed from laptops after being installed in enclosures (I have two USB enclosures that can take any one of SATA, 3.5" IDE and 2.5" IDE drives).

If you've done this yourself, you'll know the problem that crops up (and it is somewhat exacerbated by Cygwin): the permissions for files and directories on the disks often embed machine-specific SIDs, meaning that you have to reset permissions to get access. This isn't a totally trivial matter: sometimes, you need one recursive pass to take ownership, and a second pass to replace permissions, if the original permissions were restrictive.

So, resetting permission on a handful of folders using Explorer should be a piece of cake, right? Here's the dialog for three selected folders in XP:

And here it is in Vista:

Or rather, here it isn't. I see No Good Reason for this.

Missing menus

It has become fashionable for applications designed for Vista to hide menu bars. Unfortunately, they usually haven't been replaced by a viable alternative. For example, examine the Windows Media Player for Vista:

Suppose you have copied the URL of a movie stream from the Internet and want to watch it in full screen etc. in a proper media player, rather than in a tiny plugin window - which by itself often slows down and destabilizes the browser. Now, I know that previous versions of WMP have an 'Open URL' menu item. I know that the Open command is on the File menu, and has been since the days of Windows 3.0 and before.

The only question is - where the heck is the File menu? I'm being deadly serious: I have been in this exact scenario, and I had no idea where to go. It turns out that the menu has been hidden as a context menu on some of the gaps in the toolbars. This is only one of the reasons I use Media Player Classic for almost all video playback.

You know, it's this kind of behaviour - prioritizing asthetics above functionality - that makes me hate Apple. At least Apple are usually more consistent and slightly more usable, if you're willing to accept the concomitant lack of functionality and user freedom, and general vibe of submission to the will of a tyrant. A tyrant (Jobs) with good taste is still a tyrant, and ought be shunned, if you value long-run freedom.

Missing keyboard accelerator hints

And on the topic of menus... where are the keyboard accelerator hints? You know, those little underlines that show which key, in combination with the Alt key, will select that menu item. They were disabled in XP by default too, but were easily re-enabled in Display Properties | Appearance | Effects. The analogous location in Vista has far fewer options.

Inconsistently extended right-click area in detailed listviews

Onwards to the rest of the main Explorer window itself. This bug - I can only call it a bug - catches me every time I work with a large folder in Vista. Observe, a folder with lots of files, and one selected; a common starting point:

Note the full selection width, which is different from XP, where only the icon and its associated text were marked selected.

Suppose I want to create a new folder. Where should I right-click? In XP, anywhere outside the selection and not directly on an icon or its associated text would do. Let's try that:

Ha ha! You thought wrong, buddy!

If you've played around with the new selection rules in Vista, you'll know that any text associated with a row in a detailed listview counts as item area. Now, I don't like this new behaviour: I use detailed view all the time, and because I like dense information, there is relatively little free space for folder context operations - most of the columns are filled with text.

It gets worse, though. How do you select multiple items using a drag rectangle in this new paradigm? To do this, you must deliberately leave wasted space to the right of all columns, so that you can begin your drag rectangle there. If you don't, the initial drag operation is interpreted as initiating a file move operation.

But wait! What about the weird behaviour seen above, where the item context menu pops up even though I'm not clicking on any text? This is a listview bug, and still hasn't been fixed even though Vista has been out for ages now. Let me demonstrate. This is the logical item area, highlighted as best I can in yellow:

And this is the actual item area:

The selection logic doesn't take account of the column alignment. This causes me amazing amounts of frustration, because the biggest chunk of free space for right-click operations for me is between the left-aligned Name column and the right-aligned Size column. There's usually plenty of space here to account for huge files and long names; but there's an invisible item-associated click area right down the middle of it.

Treeview draw gaps

This one is minor, but still annoying. With effects turned off, treeviews that don't have either the focus or the cursor inside their bounds don't draw plus/minus boxes for folders that have children. It just looks plain ugly:

Listview deletes kill focus

Suppose you're reviewing a list of files, and deleting some of them as you scroll through the list. I often do this with the keyboard, as it's more efficient - the arrows navigate nicely and the delete button is nearby (I have confirmation dialogs disabled for deletion). Unfortunately, if you happen to delete multiple items in one go, you're in for a surprise.

To be more specific, if you select a range of items by holding the shift key down while scrolling through a long list, like this:

And then delete them, you'll notice that the focus rectangle has disappeared:

Where did it go? I sure hope I didn't lose my place in that long list of files I was reviewing! Let's see, I press the Up arrow to see if that teases out the focus from hiding, but no luck. I press the Down arrow, and hey presto!

I'm right back at the start. Now I need to scroll through all those files again and pick up where I left off. This does not make me happy.

File system watching maintains sorted order

I often keep a folder open while a background process is creating files in it: anything from an automated build producing log files to a wget mass download job. Now, maybe I'm a really odd fellow, but I rather appreciate the way XP behaves in this scenario: periodically, the kernel notifies Explorer that the underlying directory has changed, and XP will add the new items at the end of the existing listing - even though this may be out of the correct sorting order for the folder. I know that I can just press 'F5' to refresh the view, and everything will be resorted. However, knowing that new files are just appended to the end, I can scroll down there and watch the output appear, and even open it up when I see that the next output file has been created.

In Vista, no longer. Explorer is now "smarter", for some smart-ass value of smarter. Instead, it incorporates new items into the existing sorting order. Now I know some people would consider the old behaviour a bug and the new a fix, but the old behaviour was long-standing, and I had learned to rely on it.

Conclusion

Considering some of the lower-level enhancements in Vista, none of the above items individually would (or should) have been enough to turn me against it. However, when you add it all up, the charge starts getting more serious. I can't use Vista for more than 10 minutes without hitting one or more of these snags (or others that I haven't gone into); and these are just the snags I can't really do anything about.

Other things, like the indexing service, overhead of desktop composition etc., I have all disabled as either inessential or things I already have solutions for.

What I would have liked most is the Vista kernel with an optional selection of Vista applets, combined with an option for selecting the XP shell. In other words, I would have been far happier with a whole lot less. It's not like value for money comes into it: if you have to buy a Microsoft OS to put on a machine you build, the purchase feels more like a tax than it does choice. It was never a matter of a new OS driving me to purchase it, or a new PC.

The product feels oddly like a guilty company's justification for selling a product at a high price but a low marginal cost. It reminds me of government spending; they collect all this money, then have to find ways to spend it, but because of their monopoly position, they don't have the correct incentives, and consequently much of that money would have been better left with its original owner.

Tiburon: fun with generics and anonymous methods

2008-08-20T20:50:00.011+01:00

Update: I've added more code to the end of this entry.

The next release, Delphi 2009 (codename Tiburón) has some new language features: generics and anonymous methods in particular. I've decided to write up some of my experiments, playing with the new tools to see what can be done with them.

First, though, a disclaimer: I am of course working with the development tip for both compiler and RTL, so some details mentioned here (RTL in particular) may change before final release. However, the basics of generics and anonymous methods are pretty solid and should not change, so any gaps should be fillable if needs be.

Here's a generic method reference:

type
  TFunc<T> = reference to function: T;

This guy (a "method reference") can refer to any global function, method or anonymous method which takes no parameters and returns a value. It's a managed type, like strings and interfaces, because it can contain state that needs to be freed when the last reference to it goes out of scope. Here's a trivial example of a method reference in use with an anonymous method:

{$APPTYPE CONSOLE}

uses
  SysUtils;

function MakeCounter(Start, Increment: Integer): TFunc<Integer>;
begin
  Result := function: Integer
  begin
    Result := Start;
    Inc(Start, Increment);
  end;
end;

procedure WriteList(const Source: TFunc<Integer>; Count: Integer);
begin
  while Count > 1 do
  begin
    Write(Source, ', ');
    Dec(Count);
  end;
  Writeln(Source);
end;

procedure DoIt;
var
  evenNumbers: TFunc<Integer>;
  decades: TFunc<Integer>;
begin
  evenNumbers := MakeCounter(0, 2);
  decades := MakeCounter(0, 10);

  WriteList(evenNumbers, 10);
  WriteList(decades, 10);
end;

begin
  try
    DoIt;
  except
    on E:Exception do
      Writeln(E.Classname, ': ', E.Message);
  end;
end.

The code should be pretty easy to follow. It prints out the first 10 odd numbers, and the first 10 numbers evenly divisible by 10, starting at 0. Here's the exact output:

0, 2, 4, 6, 8, 10, 12, 14, 16, 18
0, 10, 20, 30, 40, 50, 60, 70, 80, 90

Notice how the value returned from MakeCounter has captured its parameters, and that these parameters have become internal state of the return value. This action is called variable capture, and an anonymous method that performs variable capture is a closure. TFunc<T> is useful enough that it is predefined in SysUtils; there are similar versions taking up to 4 arguments, and there are also TProc method references, also taking up to 4 arguments.

This example suggests to me an easy way of creating enumerators in Delphi. Rather than having to define a separate enumerator class, and implement the GetCurrent and MoveNext functions, as well as a property that reads from GetCurrent, we can use an anonymous method that simply returns each value in sequence. To signal termination, we'll use a special exception. With these tools, we can write a counter generator that has an upper bound too:

{$APPTYPE CONSOLE}

uses
  SysUtils;

type
  EEnumerationFinished = class(Exception)
    constructor Create;
  end;
  
  TSimpleEnumerator<T> = class
  private
    FSource: TFunc<T>;
    FCurrent: T;
    FFinished: Boolean;
    function GetCurrent: T;
  public
    constructor Create(const ASource: TFunc<T>);
    function MoveNext: Boolean;
    property Current: T read GetCurrent;
  end;

{ EEnumerationFinished }

constructor EEnumerationFinished.Create;
begin
  inherited Create('Enumeration finished');
end;
  
{ TSimpleEnumerator<T> }

constructor TSimpleEnumerator<T>.Create(const ASource: TFunc<T>);
begin
  FSource := ASource;
end;

function TSimpleEnumerator<T>.GetCurrent: T;
begin
  Result := FCurrent;
end;

function TSimpleEnumerator<T>.MoveNext: Boolean;
begin
  if FFinished then
    Exit(False);
  try
    FCurrent := FSource;
  except
    on e: EEnumerationFinished do
    begin
      FFinished := True;
      Exit(False);
    end;
  end;
  Exit(True);
end;

function MakeCounter(Start, Increment, Count: Integer): TSimpleEnumerator<Integer>;
begin
  Result := TSimpleEnumerator<Integer>.Create(function: Integer
  begin
    if Count <= 0 then
      raise EEnumerationFinished.Create;
    Result := Start;
    Inc(Start, Increment);
    Dec(Count);
  end);
end;

function ToString(e: TSimpleEnumerator<Integer>): string;
var
  sb: TStringBuilder;
begin
  sb := TStringBuilder.Create;
  try
    while e.MoveNext do
      sb.Append(e.Current).Append(', ');
    if sb.Length > 2 then
      sb.Length := sb.Length - 2;
    Result := sb.ToString;
  finally
    sb.Free;
  end;
end;

procedure DoIt;
var
  oddNums: TSimpleEnumerator<Integer>;
begin
  oddNums := MakeCounter(1, 2, 20);
  try
    Writeln('Odd numbers: ', ToString(oddNums));
    Writeln('And again: ', ToString(oddNums));
  finally
    oddNums.Free;
  end;
end;

begin
  try
    DoIt;
  except
    on E:Exception do
      Writeln(E.Classname, ': ', E.Message);
  end;
end.

Unfortunately, this has several drawbacks. First, the for-in syntax can't be used, because that expects a collection of some kind that has a method called GetEnumerator, whereas we only have the enumerator itself. Secondly, the enumeration can only be performed once. You can see this in the output:

Odd numbers: 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39
And again:

We can fix both of these problems, however, by adding another layer of indirection. Rather than working with TFunc<T>, we'll work with TFunc<TFunc<T>>; and we'll write a TSimpleEnumerable<T> that returns our enumerator.

Now, inside one of the new units, Generics.Collections, are a couple of new base classes, TEnumerator<T> and TEnumerable<T>. I'll use those base classes too:

{$APPTYPE CONSOLE}

uses
  SysUtils, Generics.Collections;

type
  EEnumerationFinished = class(Exception)
    constructor Create;
  end;

  TSimpleEnumerable<T> = class(TEnumerable<T>)
  private
    FSourceMaker: TFunc<TFunc<T>>;
  public
    type
      TEnumerator = class(TEnumerator<T>)
      private
        FSource: TFunc<T>;
        FCurrent: T;
        FFinished: Boolean;
        constructor Create(const ASource: TFunc<T>);
        function GetCurrent: T;
      protected
        function DoGetCurrent: T; override;
        function DoMoveNext: Boolean; override;
      public
        function MoveNext: Boolean;
        property Current: T read GetCurrent;
      end;
  protected
    function DoGetEnumerator: TEnumerator<T>; override;
  public
    constructor Create(const ASourceMaker: TFunc<TFunc<T>>);
    function GetEnumerator: TEnumerator;
  end;
  
{ EEnumerationFinished }

constructor EEnumerationFinished.Create;
begin
  inherited Create('Enumeration finished');
end;
  
{ TSimpleEnumerable<T>.TEnumerator }

constructor TSimpleEnumerable<T>.TEnumerator.Create(const ASource: TFunc<T>);
begin
  FSource := ASource;
end;

function TSimpleEnumerable<T>.TEnumerator.DoGetCurrent: T;
begin
  Result := GetCurrent;
end;

function TSimpleEnumerable<T>.TEnumerator.DoMoveNext: Boolean;
begin
  Result := MoveNext;
end;

function TSimpleEnumerable<T>.TEnumerator.GetCurrent: T;
begin
  Result := FCurrent;
end;

function TSimpleEnumerable<T>.TEnumerator.MoveNext: Boolean;
begin
  if FFinished then
    Exit(False);
  try
    FCurrent := FSource;
  except
    on e: EEnumerationFinished do
    begin
      FFinished := True;
      FCurrent := Default(T); // don't keep alive if refcounted
      Exit(False);
    end;
  end;
  Result := True;
end;

{ TSimpleEnumerable<T> }

constructor TSimpleEnumerable<T>.Create(const ASourceMaker: TFunc<TFunc<T>>);
begin
  FSourceMaker := ASourceMaker;
end;

function TSimpleEnumerable<T>.DoGetEnumerator: TEnumerator<T>;
begin
  Result := GetEnumerator;
end;

function TSimpleEnumerable<T>.GetEnumerator: TEnumerator;
begin
  Result := TEnumerator.Create(FSourceMaker());
end;

function MakeCounter(Start, Increment, Count: Integer): TSimpleEnumerable<Integer>;
begin
  Result := TSimpleEnumerable<Integer>.Create(function: TFunc<Integer>
  var
    myStart, myIncrement, myCount: Integer;
  begin
    myStart := Start;
    myIncrement := Increment;
    myCount := Count;
    
    Result := function: Integer
    begin
      if myCount <= 0 then
        raise EEnumerationFinished.Create;
      Result := myStart;
      Inc(myStart, myIncrement);
      Dec(myCount);
    end;
  end);
end;

function ToString(Collection: TEnumerable<Integer>): string;
var
  sb: TStringBuilder;
  item: Integer;
begin
  sb := TStringBuilder.Create;
  try
    for item in Collection do
      sb.Append(item).Append(', ');
    if sb.Length > 2 then
      sb.Length := sb.Length - 2;
    Result := sb.ToString;
  finally
    sb.Free;
  end;
end;

procedure DoIt;
var
  oddNums: TEnumerable<Integer>;
begin
  oddNums := MakeCounter(1, 2, 20);
  try
    Writeln('Odd numbers: ', ToString(oddNums));
    Writeln('And again: ', ToString(oddNums));
  finally
    oddNums.Free;
  end;
end;

begin
  try
    DoIt;
  except
    on E:Exception do
      Writeln(E.Classname, ': ', E.Message);
  end;
end.

This did require a little extra complexity - making a copy of the state in the outer anonymous method of MakeCounter - but it also now performs as expected:

Odd numbers: 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39
And again: 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39

So there we have it: an easy way to create enumerators and simple collection wrappers using a combination of generics and anonymous methods. There's more that can be built on this foundation, but I'll leave that until later.

Update:

Joylon in the comments prompts me to show the alternative - i.e. how to write the above without using anonymous methods. Here's a basic enumerator which does the same thing as the above - i.e. generate an integer sequence of a specified length and stride:

type
  TEnumerator = class
  private
    FCurrent: Integer;
    FCount: Integer;
    FIncrement: Integer;
    function GetCurrent: Integer;
  public
    constructor Create(Start, Increment, Count: Integer);
    function MoveNext: Boolean;
    property Current: Integer read GetCurrent;
  end;
  
{ TEnumerator }

constructor TEnumerator.Create(Start, Increment, Count: Integer);
begin
  FCurrent := Start;
  FCount := Count;
  FIncrement := Increment;
end;

function TEnumerator.GetCurrent: Integer;
begin
  Result := FCurrent;
end;

function TEnumerator.MoveNext: Boolean;
begin
  if FCount <= 0 then
    Exit(False);
  Inc(FCurrent, FIncrement);
  Dec(FCount);
  Result := True;
end;

At 35 lines, it is quite a bit (3x) more verbose than the directly equivalent MakeCounter function (11 lines; this isn't one that supports resetting or recreating the enumerator, but the translation above doesn't either):

function MakeCounter(Start, Increment, Count: Integer): TSimpleEnumerator<Integer>;
begin
  Result := TSimpleEnumerator<Integer>.Create(function: Integer
  begin
    if Count <= 0 then
      raise EEnumerationFinished.Create;
    Result := Start;
    Inc(Start, Increment);
    Dec(Count);
  end);
end;

However, even then, I wouldn't necessarily recommend using the above technique to implement all enumerators in general - the fact that exceptions are used to signal termination will cause some performance loss and, more importantly, quite a bit of annoyance when running in a debugger.

Rather, I intend, over the next few posts in this blog, to use anonymous methods in all sorts of ways so that you, the reader, might see opportunities for their creative use in your own code.

Anonymous method details

2008-07-28T19:15:00.003+01:00

There's an item on Reddit that caught my attention - it has a great title, Pascal gets closures before java - why hasn't the world ended?

I've contributed some replies and clarifications to the thread, so if you're interested in some of the details of one of the upcoming Delphi 2009's new features, pop over and take a glance.

I am going to write some more detailed posts here, focusing on use cases for anonymous methods in particular. Until I find the time to do that, the Reddit comments will have to do.

Be Bold!

2008-07-17T08:28:00.002+01:00

I saw this yesterday on programming.reddit.com (still occasionally has something worthy of a glance): Don't write from scratch:

Asked what I was not learned in school I would answer: “how to fight the urge to rewrite everything”. To a die hard software writer “rewrite it” seems like the perfect solution to every problem.

[...]

So think twice. And then think again. Wouldn’t a tiny update or bug fix do ? You need to add new features and the original system was written in Cobol/Fortran/Delphi and you do not have a clue of these languages ? Perhaps you can add the new stuff with your super-duper framework/language and just integrate it.

Delphi in the same breath as Cobol and Fortran! Oh, the pain!

The Delphi compiler, ironically enough, is one of those C programs that has you itching to rewrite. Of course, it's deeply integrated with the IDE and the debugger, and many millions of lines of customer code expect it to behave in very specific ways. Throwing it away and starting again - not a smart business move.

Unfortunately, the same reasons that prevent you from throwing it away are the same reasons to be conservative about changes; but conservative changes are local changes, local changes are short-sighted changes, and after enough years (or decades) of short-sighted changes, it's very hard to make out enough structure (no matter how long you stare) such that you can make changes that affect the program gestalt without fear of everything crashing down around your ears.

So, here's my advice for all those noble maintainers out there: when you feel like you want to rewrite, put that energy into refactoring some slice of your code base while you're implementing a new feature or fixing a particularly deep-rooted bug. Try to fully understand what it is you're changing; create test cases that verify, both positively (what it does) and negatively (what it doesn't), every aspect of the current or desired behaviour (or both, if you need to live with backward-compatibility switches and knobs).

If you've selected your slice well, and you have the test cases to back it up, you can feel free to really rip it apart and, yes, rewrite it, and spend some time fixing up all the places it integrated with the rest of the code. While you're looking into those integration spots, you'll probably notice patterns in the usage of your slice that haven't been abstracted, due to aforementioned short-sightedness. Go on. Improve the surface API of your slice in view of your now global knowledge of how it's used. Remove the cruft. Eliminate dead code paths - pernicious are those that appear to have effect locally, but have no global observable side-effect due to other effects later in time. Such code competes strongly in the Darwinian evolution of maintenance, because few people have time to confirm their suspicions that it's safe to remove - but checking this gets more costly as time goes by. Be a stern judge of unused functions. Rewrite or remove stale comments. Source control is there for a reason.

Normalization is generally good for your database design, right? Maybe the code could do with some normalization too - splitting it up and arranging the pieces where they belong. Some of the pieces might already exist - and since you'll be moving similar stuff closer together, you might get into one of those Tetris-like micro-reward feedback loops, as the code collapses in on itself. Think of the fun you'll have!

Is your code indented to 10 levels because of exception handling, pre and post conditions, superstitious lock acquiring, etc.? You know there's a simple program in there, struggling to get out. There must be - if you think you could rewrite everything more elegantly, you must surely be able to better express whatever that tiny fraction of code is doing, right? Right? :)

Small changes in code so knotted it makes you want to rewrite it is a foolish economy. Small changes are like small credit-card debts you never bother to pay down. They compound over the years. $100 a month at an introductory rate [1] - you can handle that, right? Well, 20 years of that and you'll owe over a million. If you're not brave enough to reduce the entropy of the code today, consider two things: tomorrow, you (or the next guy) will need to be even braver; and every day you fail to overcome your fear of the code, a little bit of you dies.

Just try to be quick about it, though - don't bite off more than you can chew ;)

[1] For posterity (i.e. after link death), the rate was approx. 27.9% APR

Life with Cygwin: Paths, Notepad and Clipboard

2008-05-21T11:00:00.004+01:00

I have in the past written about my Cygwin setup, but several weeks ago, while I was in Scotts Valley and having dinner with Adam Markowitz and Steve Trefethen, Steve mentioned that I should write a bit more about my setup.

While the defaults for a new Cygwin install today are better than they have ever been, there are still a lot of things to be desired. Using, as I do, a bash shell as my main command line, yet still being a Windows programmer running on Windows, means that I need to integrate with Windows command-line programs. Herein lies a problem: Cygwin uses Unix-like paths with '/' and no drive letter or colon (which is a path separator on Unix systems), while Windows inherits the usual CP/M/DOS traditions. Incidentally, I mount those drives to root letters to make converting between Windows and Cygwin paths easy:

$ mkdir /c
$ mount 'c:\' /c

Mounting removable drives like floppy disks and DVD-drives in the same way is more problematic, as the 'ls --color=auto' command (which wants to colour in files and directories corresponding to thier types) will try to read the contents of these directories, which of course will be mounted to removable drives. This would normally cause delays when doing a listing of the root directory, as the removable drives in the system spin up etc. Consequently, for removable drives I use a different technique. For example, my DVD-drive is 'O:' (because it's round, and because I frequently add and remove drives and I don't like drive letters changing because it breaks things), so this is how I integrate the DVD-drive into the Cygwin file system:

$ ln -s '/cygdrive/o' /o

This creates a symbolic link which will just be a broken link when there is no DVD in the drive. I do similar things for my iPods, pen drives, floppy drive (I still keep one around, just in case :), etc.

Anyway, back to Cygwin/Windows path interaction. Cygwin does provide a command to convert between paths, called 'cygpath'. It can be used fairly easily in an ad-hoc way on the command-line:

$ notepad /etc/bash.bashrc
# (this will fail, as notepad can't cope)

$ notepad $(cygpath -w /etc/bash.bashrc)
# (this will work here but fails when the Windows path has spaces)

$ notepad "$(cygpath -w /etc/bash.bashrc)"
# (this is more resilient)

winexec

Using cygpath manually is a bit of a pain, so I wrote a little bash script I call winexec to capture the pattern:

#!/bin/bash

function usage
{
    echo "usage: $(basename $0) [options]  [...]"
    echo "Executes an executable with arguments, converting non-options into Win32 paths."
    echo "Options:"
    echo "  -f    Only convert paths to files or directories which actually exist."
    echo "  -s    Use cygstart to execute detached from console."
    echo "  -k    Skip converting paths until '**' found in arguments (and remove the '**')."
    echo "  --    Terminate $(basename $0) options processing."
    exit 1
}

# Process options to winexec itself.

while [ "$1" ]; do
    case "$1" in
        -f)
            ONLY_FILES=1
            ;;
        
        -s)
            USE_CYGSTART=1
            ;;
        
        -k)
            SKIP_TO_STAR=1
            ;;
        
        --)
            shift
            break
            ;;
        
        -*)
            # Give an error on unknown switches for future compat.
            usage
            ;;
        
        *)
            break
            ;;
    esac
    shift
done

EXECUTABLE="$1"
shift

test -z "$EXECUTABLE" && usage

# Options conversion and caching.

declare -a OPTS
function add_opt
{
    OPTS[${#OPTS[@]}]="$1"
}

function add_file_opt
{
    if [ -n "$SKIP_TO_STAR" ]; then
        if [ "$1" = "**" ]; then
            SKIP_TO_STAR=
            # Eat '**' but don't add.
        else
            # Haven't seen star yet, so add unconverted.
            add_opt "$1"
        fi
    else
        if [ -n "$ONLY_FILES" ]; then
            if [ -f "$1" -o -d "$1" ]; then
                add_opt "$(cygpath -w "$1")"
            else
                add_opt "$1"
            fi
        else
            add_opt "$(cygpath -w "$1")"
        fi
    fi
}

# Process arguments to executable.

while [ "$1" ]; do
    case "$1" in
        -*)
            add_opt "$1"
            ;;
        
        *)
            add_file_opt "$1"
            ;;
    esac
    shift
done

# Actually start the executable.

if [ "$USE_CYGSTART" ]; then
    cygstart -- "$EXECUTABLE" "${OPTS[@]}"
else
    "$EXECUTABLE" "${OPTS[@]}"
fi

For an example of how I use that, I have another script called 'dir', for when I feel like I need classic 'dir' options:

#!/bin/bash

winexec -f -k cmd /c dir '**' "$@"

All these scripts, BTW, go in my ~/bin directory and are chmod'd 0755 to make them executable:

$ mkdir ~/bin
$ chmod -R 0755 ~/bin/*

My system's PATH (i.e. the Windows PATH, from System Properties | Advanced | Environment Variables) includes my home directory's bin directory before the Cygwin bin directories, but it also includes those. There can be some knots here though, which I won't get into today. The scripts also need to use Unix line-endings, though Cygwin was less strict about this in the past. It's easily enough done, though: the dos2unix command will normalize to Unix any text files given as arguments.

n

Notepad is a classic programmer's tool - as in "all I need is Notepad and the compiler" (or maybe just Notepad ;), etc. Since Notepad doesn't react so well to multiple file arguments, it isn't completely suitable to the winexec trick. I have a customized script for Notepad:

#!/bin/bash

if [ -z "$1" ]; then
    echo "usage: $(basename $0) ..."
    echo "Starts notepad on the file(s)."
    echo "If  is -, then standard input is redirected to a temp file and opened."
    exit 1
fi

for file in "$@"; do
    if [ "$file" = "-" ]; then
        file=$(mktemp)
        cat '-' > $file
        (
            notepad "$(cygpath -w "$file")"
            rm $file
        ) &
    else
        cygstart -- notepad "$(cygpath -w "$file")"
    fi
done

Having created this little utility, I can open multiple files in notepad just using the bash wildcards:

$ n /c/windows/*.txt
# (there aren't too many of these guys)

Similarly, I can capture a program's output into Notepad for reference in a separate window and possible printing:

$ dir /c | n -
# (opens a notepad window containing the directory listing for C:\)

Copy and Paste

Finally (for now), good Windows integration requires good clipboard integration. The native-Windows rxvt terminal which ships with Cygwin already support automatic copy on selection and paste with middle-cilck or Shift+Ins, familiar to Unix console and X users. However, I often want to copy the output of a command to the clipboard, or get a copied piece of text into a file, or transform the contents of the clipboard (perhaps to do a search and replace on it), etc. Thus, I wrote two little utilities in Delphi, copy-clipboard.dpr and paste-clipboard.dpr:

Copy

{$APPTYPE CONSOLE}

uses
  SysUtils, Classes, Clipbrd;

var
  list: TStringList;
  line: string;
begin
  try
    list := TStringList.Create;
    while not Eof(Input) do
    begin
      Readln(line);
      list.Add(line);
    end;
    Clipboard.AsText := list.Text;
  except
    on e: Exception do
      Writeln(ErrOutput, e.Message);
  end;
end.

(Freeing objects that have no external effect when freed before you're about to exit the program is the height of pointlessness, in case you were wondering.)

Paste

{$APPTYPE CONSOLE}

uses
  SysUtils, Clipbrd;

begin
  Write(Clipboard.AsText);
end.

These two utilities, having been compiled, renamed to c.exe and p.exe, and moved to my ~/bin directory, come in very handy. For example, should I myself have wanted to copy one of the above scripts, I normally just select and copy script text, and:

$ p > ~/bin/winexec
$ chmod 0755 ~/bin/winexec

Similarly, I sometimes want to search and replace on text on the clipboard:

$ p
Similarly, I sometimes want to search and replace on text on the clipboard:
# (showing what's on the clipboard)
$ p | sed 's| |_|g' | c
# (replace all spaces with underscores)
$ p
Similarly,_I_sometimes_want_to_search_and_replace_on_text_on_the_clipboard:

A not usually unwelcome side-effect of my clipboard commands is that they normalize line endings and add a newline sequence at the end of the text, if there isn't one already.

I hope I've given a few folk some ideas about optimizing their environment, particularly if they're command-line junkies like me.

In Defense of Steve Vinoski and Erlang

2008-05-18T20:16:00.002+01:00

There's been a minor scuffle going on between Ted Neward and Steve Vinoski over the wisdom of Erlang's approach to concurrency: whether it should be baked into the language or not on one hand, and whether it should be running on the JVM or CLR on the other.

I've already articulated my position on VMs, and I think it makes a lot of sense, particularly for prototyping, to build a VM specifically for a language implementation, particularly if the language has some primitives that are not normally available in commodity VMs. And to be frank, if one's language doesn't have some interesting new primitives or combination of primitives, it is unlikely to be moving the state of the art forward.

Erlang uses the actor concurrency model combined with lightweight aka green threads, though the execution engine may spawn as many threads as needed in order to get genuine concurrency from an underlying parallel architecture, such as multiprocessor or multicore. Erlang works under a shared-nothing model, however, so the "green threads" are more like "green processes".

I think Ted misses some appreciation of the power of the Erlang model, and in particular, its choice of primitives. Ted points to an implementation of the Actor model using Lift (written in Scala), and in particular some ballpark performance numbers:

We also had an occasion to have 2,000 simultaneous (as in at the same time, pounding on their keyboards) users of Buy a Feature and we were able to, thanks to Jetty Continuations, service all 2,000 users with 2,000 open connections to our server and an average of 700 requests per second on a dual core opteron with a load average of around 0.24... try that with your Rails app.

One of the obvious problems with this comment is that it doesn't sound very impressive when actually compared with Yaws, implemented in Erlang:

Our figure shows the performance of a server when subject to parallel load. This kind of load is often generated in a so-called "Distributed denial of service attack".

Apache dies at about 4,000 parallel sessions. Yaws is still functioning at over 80,000 parallel connections.

What this disparity tells me is that the JVM and CLR are likely lacking some primitives that help Erlang achieve this kind of result. For straight-up processing code, Erlang isn't terribly fast, by all accounts. The reason it wins is likely because it is avoiding the context-switching overhead through the use of lightweight processes. This in turn suggests to me that the equivalent of green threads, or some kind of automatic CPS transformation or native support for continuations is needed for CLR and JVM to be credible target platforms for Erlang. Lift is currently using Jetty Continuations, and when you read up about its implementation:

Behind the scenes, Jetty has to be a bit sneaky to work around Java and the Servlet specification as there is no mechanism in Java to suspend a thread and then resume it later. The first time the request handler calls continuation.suspend(timeoutMS) a RetryRequest runtime exception is thrown. This exception propagates out of all the request handling code and is caught by Jetty and handled specially. Instead of producing an error response, Jetty places the request on a timeout queue and returns the thread to the thread pool.

When the timeout expires, or if another thread calls continuation.resume(event) then the request is retried. This time, when continuation.suspend(timeoutMS) is called, either the event is returned or null is returned to indicate a timeout. The request handler then produces a response as it normally would.

Thus this mechanism uses the stateless nature of HTTP request handling to simulate a suspend and resume. The runtime exception allows the thread to legally exit the request handler and any upstream filters/servlets plus any associated security context. The retry of the request, re-enters the filter/servlet chain and any security context and continues normal handling at the point of continuation.

... you can see that it's clearly a hack to work around the limitations of the JVM - i.e. the fact that it doesn't have user-schedulable green threads (on top of native threads, not as a replacement, a bit like fibers on Windows), or an automatic CPS with some AOP-style weaving, or native continuation support.

In conclusion, the primitives in the VM matter a great deal. With the right primitives, wholly different styles of application become possible, because of the radically different performance profiles.

The point of VMs

2008-05-18T19:35:00.002+01:00

There was a post on the Delphi newsgroups that stuck in my head for some reason, and I felt I had to write a reply. The reply ended up being a lot longer than I originally intended, because I felt I had to justify my stance. I'm reposting it here in edited form.

"Virtual machine" has acquired pejorative overtones due to historical and social reasons that are probably too emotive to go into. Suffice it to say that I think it's another case of "good ideas don't win, proponents of bad ideas die out instead".

The way I see it, a virtual machine (in the context of programming language implementations) is a software implementation of an abstract machine with a closed-by-default set of semantics.

Let's take that definition apart:

software implementation: Here, I don't mean that the machine cannot be implemented in hardware. Rather, I mean that if it's going to be "virtual", it is usually implemented in software, which gives rise to certain characteristics, which in turn imbue "virtual machine" with extra shades of meaning. It turns out that software implementation is better than implementing in hardware, largely because of flexibility.
abstract machine: Every programming language has an abstract machine implicit or explicit in its definition, or otherwise its promised semantics are meaningless - you need a machine at some point to actually do things, and have effects. So, the abstract machine bit isn't controversial; it's its qualities that matter. Note that I differentiate between two different abstract machine concepts: a language's abstract machine, which it uses to model effectful operations, and a platform as an abstract machine. A CPU (+ memory + etc.) specification is an abstract machine, and a platform; the physical device, however, is a real machine, running on the laws of physics.
closed-by-default semantics: Here, I mean that at the abstraction level of the abstract machine in question, undefined behaviour is outlawed. In defining our machine, we humbly accept our human frailties, and do our best to prevent "unknown unknowns" becoming a problem by reducing the scope of the problem domain. We limit the power of the machine, in other words.
Since we do, eventually, want to be able to talk to hardware, legacy software and the rest of the real world, there do need to be carefully controlled holes and conduits built-in. But they're opt-in, not opt-out.

Let's look at some of the ramifications of this conception of VMs.

Software implementation delivers a tremendous amount of flexibility. Some examples: runtime metaprogramming (e.g. runtime code generation, eval); dynamic live optimization (e.g. Hotspot JVM [1]); auto-tuning garbage collection; run-time type-aware linking (solving the template instantiation code-bloat problem); rich error diagnostics (e.g. break into REPL in dynamic languages).
Abstract machine: Developments in programming language fashions have made object orientation come to the fore (perhaps even too much to the fore). However, our physical machines map much closer to procedural code and a separation between code and data than the trends in language and architecture design.
In other words, the platforms that historically popular type-unsafe [2] languages (like C++ and Delphi) have targeted aren't a close match for those languages' abstract machines. When they want to interoperate, either with other modules or with modules written in different languages, they face barriers, because their common denominator is the abstraction of the physical CPU. Hence C-level APIs being de facto industry standards, along with limited attempts to raise the abstraction level with COM (largely defined at the binary level in terms of C, explicitly referring to vtable concepts that are otherwise just hidden implementation details of other languages).
So, moving the abstraction level of the target machine closer to the average language abstract machine makes compiler implementation easier, reduces interoperation barriers, and provides more semantic content for the (typically) software implementation to work its flexibility magic.
Closed-by-default eliminates whole categories of bugs. Type-safety can be guaranteed by the platform. Never again [3] have a random memory overwrite that shows up as a crash 5 minutes or 5 hours later. It also improves security [4] by having a well-defined whitelist of operations, rather than trying to wall things in with blacklists and conventions ("this structure is opaque, only pass to these methods" etc.).

[1] Some notable optimizations that become feasible when the program is running live include virtual method inlining, lock hoisting and removal, redundant null-check removal (think about argument-checking at different levels of abstraction), etc. Steve Yegge's latest blog post, while rambling, covers many optimizations that apply equally to static languages running in a virtual machine and to dynamic languages (but of course he's interested in promoting them as the apply to dynamic languages):
http://steve-yegge.blogspot.com/2008/05/dynamic-languages-strike-back.html

[2] Any language that has dynamic memory allocation that it expects to be reclaimable (i.e. no infinite memory) and doesn't have a GC isn't type-safe. A single dangling pointer to deallocated memory kills your type safety: if a value of a different type gets allocated at the same location, you have a type violation.

[3] Unfortunately, RAM may occasionally flip bits due to cosmic rays etc. So, we want to use ECC RAM and checksum critical structures when it matters. Edge case nit.

[4] IMO, the capability-based security model is the best of those available, ideally including eliminating ambient authority.
http://en.wikipedia.org/wiki/Capability-based_security
Guess what: you need a type-safe virtual machine to make some strong guarantees about capabilities, otherwise someone could come along and steal all your capabilities by scanning your memory.
See Capability Myths Demolished for more info:
http://srl.cs.jhu.edu/pubs/SRL2003-02.pdf

In an odd coincidence...

2008-05-16T15:13:00.001+01:00

Jeff Atwood has a new post up about forking open source projects, and in particular, pointing out how difficult it is. This very closely corresponds with the point I made yesterday...

The new "Open" isn't as open as it seems to be

2008-05-16T00:09:00.003+01:00

I was reading Scott Koon's (lazycoder) post about RIAs (rich internet applications) being a platform play, what with Adobe AIR, Microsoft Silverlight and JavaFX. Scott noted that these platforms are all "open enough" that independent implementations can be made.

This idea reminded me of a podcast on open source business models with Dirk Riehle that I listened to a number of weeks back. The core ideas are also on the Dirk's website.

Dirk makes clear a number of features of the open software market. In particular, he distinguishes between community open source and commercial open source, where a single vendor controls the direction of the project and employs the key contributors. Even though e.g. Silverlight isn't exactly open source, Microsoft has been open enough to let Novell's Moonlight be implemented. The strategies of Sun and Microsoft for their new platforms appear to be based around the ideas of commercial open source. Their profit items are hardware and services in the case of Sun, and OS and database licenses in the case of Microsoft. What Adobe's long-term strategy for monetizing its platform play isn't yet clear to me, but when you've got folks locked in, you can start selling your captive audience one way or another.

Anyhow, my point is that this new openness isn't as open as it seems to be. Community open source needs strong personalities to deliver direction ~~, and even then, it seems to work best when reimplementing a previously proprietary, closed-source technology~~. Commercial open-source has several key advantages in controlling the platform, because focus and longer-term strategy means it can usually force any potential competitors into trying to keep up with it, rather than forking and going their own way. Open platforms tend to rally around key personalities, which essentially become brands, and the commercial style means that the body corporate owns that brand. Microsoft can come out with all the IronPython and IronRuby they like, but they are unlikely to get much acceptance if they try to introduce features that Guido or Matz don't agree with. More corporately, it's unlikely that many competitors to Sun would ever become "go-to guys" for issues with the Java platform (though if it would be anybody, I'd bet on Azul in the long term).

Upshot is, going open isn't as open (or risky) as it might seem, provided that you've got something else to sell alongside.

Update: Fuzzyman in the comments has convinced me that I was wrong to suggest that the most used open source isn't that innovative, hence the overstrike. However, that wasn't really essential to the point of the post...

1001 Books you must read before you die

2008-05-13T01:38:00.004+01:00

A long list of books, with many titles where I've said "I must read that some day". I read a lot more when I was a kid, before I got into this whole computer racket, and started focusing on more non-fiction. I've only read 50 or so from the list. At this rate, I'll never get more than 15% or so.

I wonder how much you can tell about a person from their reading list? Here are the ones I read, I may have missed one or two though:

Slow Man – J.M. Coetzee
Choke – Chuck Palahniuk
Super-Cannes – J.G. Ballard
Memoirs of a Geisha – Arthur Golden
The Information – Martin Amis
Time’s Arrow – Martin Amis
London Fields – Martin Amis
The Long Dark Teatime of the Soul – Douglas Adams
Dirk Gently’s Holistic Detective Agency – Douglas Adams
The Old Devils – Kingsley Amis
Money: A Suicide Note – Martin Amis
The Hitchhiker’s Guide to the Galaxy – Douglas Adams
High Rise – J.G. Ballard
One Hundred Years of Solitude - Gabriel García Márquez
The Third Policeman – Flann O’Brien
One Day in the Life of Ivan Denisovich – Aleksandr Isayevich Solzhenitsyn
A Clockwork Orange – Anthony Burgess
Stranger in a Strange Land – Robert Heinlein
Catch-22 – Joseph Heller
The Tin Drum – Günter Grass
Breakfast at Tiffany’s – Truman Capote
The Lord of the Rings – J.R.R. Tolkien
Lord of the Flies – William Golding
Foundation – Isaac Asimov
The Catcher in the Rye – J.D. Salinger
I, Robot – Isaac Asimov
Nineteen Eighty-Four – George Orwell
Animal Farm – George Orwell
The Glass Bead Game – Herman Hesse
Of Mice and Men – John Steinbeck
The Hobbit – J.R.R. Tolkien
Brave New World – Aldous Huxley
The Castle – Franz Kafka
The Trial – Franz Kafka
A Passage to India – E.M. Forster
Heart of Darkness – Joseph Conrad
The Hound of the Baskervilles – Sir Arthur Conan Doyle
The War of the Worlds – H.G. Wells
The Invisible Man – H.G. Wells
Dracula – Bram Stoker
The Island of Dr. Moreau – H.G. Wells
The Time Machine – H.G. Wells
The Adventures of Sherlock Holmes – Sir Arthur Conan Doyle
The Adventures of Huckleberry Finn – Mark Twain
The Brothers Karamazov – Fyodor Dostoevsky
Around the World in Eighty Days – Jules Verne
Through the Looking Glass, and What Alice Found There – Lewis Carroll
War and Peace – Leo Tolstoy
Crime and Punishment – Fyodor Dostoevsky
Alice’s Adventures in Wonderland – Lewis Carroll
A Christmas Carol – Charles Dickens
Castle Rackrent – Maria Edgeworth
Aesop’s Fables – Aesopus

HT to Jason Kottke.

C++ evaluation order gotcha

2008-04-08T00:16:00.005+01:00

My girlfriend was looking through an introductory C++ programming book the other day, but while she was comparing actual results with expected results, she saw a discrepancy and I was called in to figure out what was going on.

The program is pretty simple:

#include <iostream>

int f(int x, int y)
{
    std::cout << "f()\n";
    return x + y;
}

int main()
{
    std::cout << "Calling f()\n";
    std::cout << "Result is: " << f(3, 4);
    std::cout << "\n";
    return 0;
}

The book indicated that it should print out the following, which indeed it does (using bcc32 6.10, g++ 3.4.4 and cl 9):

Calling f()
f()
Result is: 7

The question my astute girlfriend has is: why is 'f()' printed out before 'Result is: ', when 'Result is: ' appears earlier in the expression? In other words, why doesn't it print out:

Calling f()
Result is: f()
7

... as you might expect, following the logic from top to bottom and left to right?

The answer comes down to how C++'s designers have, in their infinite wisdom, decided to implement I/O. The left shift operator, '<<', is overloaded and so the critical expression gets parsed as a set of function calls, roughly like this:

operator<<(operator<<(std::cout, "Result is :"), f(3, 4));

This is somewhat explained on the MSDN page allegedly describing Order of Evaluation (C++).

So, the most nested things need to get evaluated first, that's pretty unavoidable. Because of the associativity of the '<<' operator, things on the left end of the line get printed first, followed by each successive item.

Here's where the subtlety is, though: that most noble order, C++ definers, have decreed that the order of evaluation of arguments is beneath their dignity; that is to say, order of argument evaluation is undefined.

However, there are some general things we can say about C++ as implemented on x86. It usually defaults to the C calling convention, which pushes arguments on the stack from right to left, in order to support varargs. Since the arguments need to be pushed from right to left, the compiler will generally take a hint and evaluate them from right to left too. That's where our strange out of order result comes from.

Delphi isn't much less guilty on this specific front, however: it doesn't have a standard in the first place, and it also generally evaluates arguments from right to left. That's often more efficient when starved for registers: usually one will want to use EAX, EDX and ECX - the registers available for Delphi in the default calling convention - for purposes of evaluating the excess arguments (if more than three), which will end up pushed on the stack. If the first argument, which will ultimately end up in EAX, got evaluated first, and so on, many valuable registers would be tied up only to calculate values that end up pushed on the stack, no longer needing a register. The alternatives, spilling to the stack or evaluating to a temporary, are wasteful.

However, for the specific instance of I/O - Writeln - Delphi breaks up multiple outputs into separate calls. So, our code, in Delphi:

 Writeln('Result is: ', f(3, 4));

get translated, behind the scenes, into something vaguely like:

Write0LString(Output, 'Result is: ');
WriteLong(Output, f(3, 4));
WriteLn(Output);

... with much less confusion for the beginner.

Procedurally-typed expressions redux

2008-03-13T04:01:00.004Z

A few days ago I blogged about some issues that the Delphi parser has with certain constructs. A little discussion ensued in the comments, so I think I want to clarify what I meant a little.

Specifically, there were two problems I pointed out:

Calling procedurally-typed values in non-trivial expressions
Creating procedurally-typed values from no-arg procedures (and functions and methods etc.) that appear in slightly non-trivial expressions.

The first problem can be solved by interpreting the appearance of an argument list (introduced by '(') in an expression as an attempt to call what is effectively the left hand side of the '(' operator. The second problem can be solved by more deeply analysing the expression tree during argument processing so that it isn't confused by something as simple as an extra set of parentheses. The first problem is more pressing as it's affecting certain features I'm trying to get into the product.

Nothing will be imposed. There will be no breaking changes in syntax or semantics, if it can possibly be helped. All that should change is that previously invalid code becomes valid.

While there is an ambiguity when looking at some hypothetical function to a function to a function, where, when calling f()(), it might appear unclear from the rules which function is being called, this syntax is currently not valid at all. Currently, the first set of parentheses is parsed as part of the first call to f, but the attempt to call the return value (of type function to a function) will fail. Extending this so that the second call succeeds shouldn't be problematic, because there's a simple rule: the '()' on a no-arg function is optional, but it will be parsed if it's found. It can't be "delayed", such that the raw 'f' is interpreted as a function call and then the '()' applied to the return value. The parser eats the tokens when it sees them and it has a rule for matching them.

The further testing I did for this post exposed another problem, potentially more severe than the others - it's a type hole:

{$apptype console}
{$T+} // you'd like typed-@ to help you here, but it doesn't...

type
 TF = function: Integer;
 PF = ^TF;

function MyF: Integer;
begin
 Result := 42;
end;

// P is separate procedure so 'f' stands out as a stack variable
procedure P;
var
 f: TF;
 x: PF;
 // use absolute to get around oddities of procedural types
 f1: Integer absolute f;
 x1: Integer absolute x;
begin
 Writeln('MyF is at ', Integer(@MyF));
 Writeln('f is at ', Integer(@@f));
 f := MyF;
 Writeln('f is pointing to ', f1);
 x := @f;
 Writeln('x should be pointing to f, but is pointing to ', x1);
 // The following line doesn't do what you'd expect: it crashes.
 // Writeln(x^);
end;

begin
 P;
end.

Unhappily enough, this prints out the following on my machine, with no warnings or errors during compilation:

MyF is at 4211536
f is at 1245092
f is pointing to 4211536
x should be pointing to f, but is pointing to 4211536

The line commented out does in fact crash.

Update: Craig in the comments asks why it's wrong. There are at least two things that could be wrong, and one of the unfortunate problems here is that there's no standard for Delphi beyond what the compiler currently does, so we can't say for sure. Either the '@f' when assigned to x should take the address of f rather than just inhibit calling the function pointer, or it should result in a compiler error - particularly as typed-@ operators are turned on here. The commented out line, x^, ought to call the function pointer being pointed to by x, but it doesn't, since it's simply pointing to the function 'MyF', rather than the function pointer 'f'.

Not a Delphi post: PC Games

2008-03-11T14:57:00.004Z

A couple of things I saw yesterday got me thinking about games, something I've been meaning to write down my thoughts about for some time. From long-time experience, I've gathered that my tastes in games are somewhat (but only somewhat) off the beaten track, if only because of the lack of market supply for what I like to play.

First off, "PC game" or "video game" etc. is too broad a category to talk about meaningfully, so it needs to be broken up. However, I'm not so happy with the usual division of games into genres like real-time strategy (RTS), turn-based strategy (I'll call this TBS), first-person shooter (FPS), third-person shooter (I'll call this TPS), etc., though sometimes those divisions accidentally coincide with the divisions I have in mind.

I look at games using several axes: the kind of skills being exercised, the depth of immersion and storytelling, and the nature of the in-game stress / release cycle and pacing.

By the kinds of skills, I mean things like strategic thinking (e.g. Civilization - non-repeatable long-term plans to achieve goals), tactical thinking (e.g. most FPSes - repeatable short-term templates of action that solve categories of problems), mastery (e.g. simulation games), hand-eye coordination (twitch games like almost every arcade game, and also including many FPSes, RTSes and TPSes)

By the depth of storytelling, I'm talking about how essential the story is to one's experience of playing the game. Is the story just an add-on to rationalize the gameplay? Is it just very effective atmosphere, made effective by how the level design directly reflects the story? Or is the story essential to successfully playing the game, or perhaps even ultimately user-written, as they make choices in the world? And by immersion, how easily can I forget than I'm at a computer, and instead think of myself as being a character in the game?

When I talk about an in-game stress / release cycle, I'm thinking in particular of how stress builds up in the player, to what degree it builds up, how it is built up, what options the player has to reduce this stress, and the pacing refers to how long the stressful periods are versus the (relatively) relaxed periods. For example, many FPSes have "action bubbles", where lots of bad guys surround some kind of goal than the player usually has to physically get to. If the FPS is heavily corridor-oriented (e.g. pretty much all the Doom games), where there's really only one way to go, then the player will probably have to kill almost every bad guy met, and can only stop for a breather if any pursuing bad guys have been killed off. On the other hand, there may be relatively quiet corridors linking areas that trigger action after a certain point is reached, something done very well by Half-Life (the original).

My favourite games have been Thief series, Far Cry, Deus Ex, Outcast and Civilization 2, roughly in that order. I've enjoyed playing games like Doom, Half-Life, Crysis, Bioshock, Oblivion, System Shock 2, but none of them had the long-lasting appeal to me that my favourites have. I tried to replay Half-Life several years ago, but it didn't take long in-game before I discovered I'd lost my love for it. On the other hand, I've replayed Thief 2 (in particular) pretty much at least once a year since it came out - an older game (older technology-wise as it uses the same engine as Thief 1, which was weak compared to the upgraded Quake engine behind Half-Life, both being 1998 vintage), but one with far more potency for me.

So, coming back to those axes, what do I like in a game? Story and immersion is very, very important, probably the most important thing. Almost all the games above are FPSes, because that's the format which lends itself best to immersion. Civilization is so sparse on the story side - the only real identity you have is as a nation of peoples, rather than a character - that one's imagination fills in the gap. This usually leads to even more identification with the game than a heavy-handed plot, because it's entirely user-driven. Far Cry has the weakest story of the lot, but its immersion is extremely effective - you really do feel like you're on a tropical island, sneaking through the bushes. Far Cry also makes up for the weak story on the other axes. The other games, in particular the Thief series, are strongly story-driven, but they don't lack in the other axes. Deus Ex has a degree of user participation in the story creation, as certain choices you make affect the plot fairly substantially - for example, you can choose to save your brother or leave him to die (which he urges you to do). The music in Outcast is amazing and highly atmospheric. The feeling of being in an Arabic-style souk is pretty strong in the city of Okriana in Talanzaar, and I have visited e.g. the souks of Marrakesh, with that atmosphere coming back to me.

I like to use strategic skills over tactical or twitch skills in games. So, even though Doom can be fun for a 30-minute blast (on a Windows 3D port, with jump and mouse-look in the Y dimension enabled), it's not what gets me hooked. The Thief series' player character, Garrett, is sneaky enough to be able to assess the ground and the disposition of enemies without being seen. The player's job is then to plan and navigate a path through the ground without being seen or heard, within the resource constraints of the gadgets available. A good friend of mine, far and away my better in twitch games like Quake multiplayer, found progressing in e.g. Thief 2's Bank level very difficult - he got stuck and ultimately bored in many situations that simply increased my appetite for the problems. Civilization is all about strategy - there isn't even a constraint on turn time. Far Cry, Outcast and Deus Ex have sufficient freedom of movement that you can usually plan your encounters from afar and engage on your own terms. All things considered, I prefer engaging from a position of strength (usually means being higher up) and unseen where possible. Up-close and twitchy is too risky: I don't like dying in a game, because that breaks my immersion. In real life, there's no way back from death: why should I play my games like it was any different? Evaluating the enemy, navigating unseen to that position of strength and planning the encounter is usually more fun for me than the encounter itself; however, there is the gratification of a plan well executed and performing as anticipated, something very akin to the pleasure of programming. It also turns out that freedom of movement is very important to permitting a strategic approach to the game: strictly linear games like Half-Life 2 almost actively prohibit strategic thinking.

About the stress & release cycle: one is usually stressed in a game because one is threatened with in-game death. There are different graphs one could draw of the typical stress patterns of different games and gaming styles. A game like Doom 3 or Half-Life 2 often rely on "surprises" - quiet areas / dark alcoves which are obvious traps, and the only "surprise" is the exact trigger location or time. This is probably a feature I hate most about some games: knowing that something bad is going to happen, but not being able to control it. Half-Life wasn't too bad, because one had tactical weapons like grenades and strategic weapons like trip-mines wherein action bubbles could be analysed and solved pre-trap-triggering, but Half-Life 2 (and especially Doom 3) used such cheap tension tactics that I stopped playing the games in disgust. These games often have a ::^^::^^::^^:: kind of tension graph: medium tension interspersed with high tension. On the other hand, a game like Thief 2 looks more like ..:..:..:^^.^^.^^:...: lots of low-tension observation, occasional medium-tension moments when encountering danger areas while scouting, followed by a long stretch of alternating high-stress navigation and resting safely in shadows. The key is that the player has control over the resting and the initiation of the next high-stress section. I far prefer games where I have control over the stress level pacing and have time to consider my options before proceeding.

If you've read this far, well done for putting up with me! I just wanted to get those thoughts out of my head, but if it's been interesting to someone else, then that's gravy.

Odd corner of Delphi: procedural expressions are not expressions

2008-03-07T21:03:00.004Z

Here's an odd corner of Delphi: expressions of a callable type (e.g. a function pointer or method pointer) are not fully-fledged expressions; or rather, the expression grammar for function application doesn't acknowledge function pointer types as proper first-class parts of the type system. For example:

type
  TFoo = procedure(x: Integer);
  TBar = function: TFoo;

var
  bar: TBar;
begin
  bar(42); // doesn't compile; too many args for TBar
  (bar)(42); // doesn't compile; bar's value doesn't flow through
  bar()(42); // still no good; bar()'s value doesn't flow through
  (bar())(42); // again, no good, for same reasons as previous two
end.

The reasons are probably directly related to two things: the historical lack of general function pointers in Pascal and the rule that no-argument procedures can omit the parentheses.

The following are valid expressions that call the function pointer, but the resulting value can't be invoked in turn:

  bar; // ok: return value dropped
  bar(); // ok: return value dropped

The above results in some serious drawbacks if one wants to program Delphi in a functional style. Currying can't work, for example: there's no way you could turn foo(1, 2, 3) into foo(1)(2)(3), since the latter syntax isn't valid.

I personally consider it a bug, but this behaviour, at the heart of expression parsing, is tricky to fix while guaranteeing not to break anything that already works. For example, there are other odd semantics around these Delphi function pointers:

type
  TFrob = function: Integer;

function MyFrob: Integer; begin Result := 42; end;

procedure Baz1(x: TFrob); begin end;
procedure Baz2(x: Integer); begin end;

procedure BazO(x: TFrob); overload; begin end;
procedure BazO(x: Integer); overload; begin end;

begin
  Baz1(MyFrob); // passing MyFrob
  Baz2(MyFrob); // calling MyFrob and passing result
  BazO(MyFrob); // guess which?
end.

The above call to Baz1 is currently handled, believe it or not, by parsing as a function call and then later, in the middle of function application, throwing away the call bit and turning it back into taking the address of the function. You can see this by hiding the function call just a tiny bit, so the function application logic can't see it so easily:

  Baz1((MyFrob)); // no longer passing MyFrob

The lesson to me in the above case is pretty clear. If you want to have function pointers in your language, you shouldn't make function application look like a function value - that way madness lies. This is why the '@' operator was invented:

  Baz1((@MyFrob)); // works again; passing MyFrob

Unfortunately, its use in Delphi for these cases is optional.

The two issues discussed in the above post are distinct. However, I may need to fix the first one in order to get certain features into the product...

Lang.NET Symposium videos are up - in WMV

2008-02-20T22:15:00.004Z

The Lang.NET symposium videos are up, but the user interface over there is pushing Silverlight. The videos are actually in WMV format. The URLs are hidden in StartPlayer.js. If you want to avoid having to install Silverlight, these urls should do (mind the spaces):

http://langnetsymposium.com/talks/Videos/1-00 - Keynote - Jason Zander.wmv
http://langnetsymposium.com/talks/Videos/1-01 - CSharp3 - Anders Hejlsberg.wmv
http://langnetsymposium.com/talks/Videos/1-05 - Lively Kernel - Dan Ingalls - Sun.wmv
http://langnetsymposium.com/talks/Videos/1-06 - JScript - Pratap Lakshman.wmv
http://langnetsymposium.com/talks/Videos/1-07 - Irony and ERP Language Challenges - Roman Ivantsov.wmv
http://langnetsymposium.com/talks/Videos/2-00 - Democratizing the Cloud with Volta - Erik Meijer.wmv
http://langnetsymposium.com/talks/Videos/2-01 - Newspeak - Gilad Braha - Cadence.wmv
http://langnetsymposium.com/talks/Videos/2-02 - Resolver One - Giles Thomas - Resolver.wmv
http://langnetsymposium.com/talks/Videos/2-03 - Retargeting DLR - Seo Sanghyeon.wmv
http://langnetsymposium.com/talks/Videos/2-04 - Visual Basic - Paul Vick.wmv
http://langnetsymposium.com/talks/Videos/2-06 - PHP - Wez Furlong.wmv
http://langnetsymposium.com/talks/Videos/2-07 - Phalanger - Tomas Petricek.wmv
http://langnetsymposium.com/talks/Videos/2-08 - Pex - Peli de Halleux.wmv
http://langnetsymposium.com/talks/Videos/2-09 - Numerical Computing with the CLR - Jeffrey Sax - Extreme Optimization.wmv
http://langnetsymposium.com/talks/Videos/2-10 - remotion Mixins - Stefan Wenig and Fabian Schmied - rubicon.wmv
http://langnetsymposium.com/talks/Videos/2-11 - CodeIt - Serge Baranovsky - submain.wmv
http://langnetsymposium.com/talks/Videos/3-00 - IronRuby - John Lam.wmv
http://langnetsymposium.com/talks/Videos/3-01 - Ruby.NET - Wayne Kelly.wmv
http://langnetsymposium.com/talks/Videos/3-02 - FSharp - Luke Hoban.wmv
http://langnetsymposium.com/talks/Videos/3-03 - Parsing Expression Grammars in FSharp - Harry Pierson.wmv
http://langnetsymposium.com/talks/Videos/3-04 - NStatic - Wesner Moise - SoftPerson.wmv
http://langnetsymposium.com/talks/Videos/3-05 - Moonlight and Mono - Miguel de Icaza.wmv
http://langnetsymposium.com/talks/Videos/3-06 - Visual Studio Shell - Aaron Marten.wmv
http://langnetsymposium.com/talks/Videos/3-07 - Modeling and Languages - Don Box.wmv
http://langnetsymposium.com/talks/Videos/3-07 - Modeling and Languages - Don Box_1.wmv
http://langnetsymposium.com/talks/Videos/3-08 - Cobra - Chuck Esterbrook.wmv
http://langnetsymposium.com/talks/Videos/3-09 - Intentional - Magnus Christerson.wmv

You didn't read it here :)

Edit: As nbrooks commented, you'll need to install the WVC1 codec to view the videos (if you haven't actually installed Silverlight). You can get it here: http://support.microsoft.com/kb/942423

Continuations: Wistfully yearning

2008-02-02T05:47:00.000Z

During the past week, there was a conference at Microsoft's campus in Redmond, Lang.NET. I didn't attend, but I did look over again at the videos from the previous speakers (one of which was by Danny Thorpe).

However, it wasn't Danny's talk that I found most interesting. Instead, it was Shriram Krishnamurthi's presentation on continuation-based web application programming. Ian Griffiths wrote a disparaging post on continuations describing how they can work in a web application, in case you're not aware of their nature. I strongly disagree with Ian, though, to the point that I'm not actually sure if he's willfully misrepresenting those who would advocate continuations.

In my previous job, we developed a web application framework, running on top of ASP.NET, for data-entry intensive applications in the finance industry. The product is now called Topoix. I contributed a bunch of things to the underlying architecture and implementation, but one of them is particularly relevant to continuations: the way Topoix implements modal dialog boxes that ask the user a question. Essentially, displaying a dialog caused execution of business code on the server to stop and resume correctly, based on the reply, when the dialog was dismissed. The stopping and resuming didn't tie up a thread on the server, and nor did it require stickiness to a particular server in the farm, but obviously it required some state - persisted to disk and perhaps cached in memory, depending on how you wanted to configure things.

Now, I want to address some of the (IMHO) mistaken criticisms in Ian's article.

This requires a certain amount of magic under the covers. Supporting continuations in special cases such as function calls or iterators is much easier than providing completely generalised support. Continuations do not fit all that well with the stack-oriented execution model offered by the JVM or CLR.

I agree to the point that code that hasn't been transformed into continuation-passing style doesn't fit well with a stack-oriented execution model. But, however, bear in mind that translation from stack-orientation to continuation-passing style is a safe and semantics-preserving operation. Things really only get hairy if one uses callbacks from non-managed code, and one expects to be able to pass around a continuation with the non-managed code on the stack.

Ian continues:

Continuations can look attractive on the web, because they offer a tool that lets you capture the shape of a sequential user journey in the structure of your code.

Continuations can do more than capture sequential user journeys; if you take care to capture values, rather than references, they can capture an arbitrary history tree of independent, concurrent user journeys. This is because the stack in CPS is essentially converted into a linked list of activation records in the heap, where each activation record points to its parent. It's trivial to see that continuing at an earlier point (equivalent to pressing the back button in your browser) simply creates a new activation record which points to some tail of the linked list, and doesn't disrupt the concurrent "main trunk" of interaction. Providing that you don't mutate variables from previous activation records (unless that's desirable - consider e.g. site preferences, or login status), you don't have a problem with non-sequential navigation.

However, I think this is a bad idea. Although the relationship between the code and the user navigation path is apparently simple, it hides subtle but significant details. This makes the same mistake as we did in the 1990s with distributed object models. We’d like to believe we’re hiding a lot of implementation details behind a simple abstraction. In practice we’re hiding important features behind an inappropriate abstraction. Our industry has more or less learned the lesson that procedure calls are an unworkably naive abstraction for request/response messaging over a network. I suspect that it’s equally naive to attempt to manage the complexities of user/web server interactions with simple sequential code.

Ian here is saying that bad abstractions are a bad idea. I fully concur; when building abstractions, it's important to abstract the correct things, and not encourage writing the wrong sorts of programs. There are a few things to say about this, though. The first is that the really egregious abstractions are those which enable writing programs that one would not actually *want* to write, if one fully understood the abstractions in hand. I'm thinking in particular here of cross-machine COM or CORBA: we should prefer REST or document-style SOAP for reasons that are beyond the scope of this post, but I'll just say that they relate to the nature of object orientation as used in the small, with shared memory, on local machines, and how that falls apart when distributed.

However, I think Ian will have to come up with something better than condemning continuations as only being capable of abstracting "simple sequential code", if for no other reason than it's a falsehood.

So, Ian tries to come up with other reasons to slay the continuation beast. However, it's worth bearing in mind, when considering his objections, what the alternative is, and then asking one's self if the alternative isn't actually a continuation written out the long way.

Let's see.

Abandoned Sessions. Sometimes the user just walks away.

Well, a continuation that one persists to a cookie, hidden form fields, encoded in the URL, or to server-side storage, as necessary / appropriate, puts this one to rest. And besides, how does one solve this issue in the average trivial shopping-cart site? One must save state in exactly the same locations, but you have to encode the resumption of logic yourself, rather than having it done for you. The abstraction doesn't look weak here.

Now, there are things Ian says that aren't related to continuations per se, but rather to coding a web application as if it had state.

Continuation-based web servers aren't a way of pretending that the server is stateful when it needs to be stateless. Rather, they're a way of easing the pain of getting back to where you left off. That's why, when Ian says:

The problem with this is that a lot of the techniques we have learned for resource management stop working. Resource cleanup code may never execute because the function is abandoned mid-flow.

... it's not very relevant. One can't be holding any non-persistable resources when persisting a continuation, and with language and library support, this can be flagged at runtime or ideally at compile time (I can't help it, I'm a static guy, even though it's not fashionable in the web world). And since the continuation-persisting code needs to, you know, actually persist the objects on the linked-list stack, it can trivially flag the obvious problems when it discovers something it can't persist.

Thread Affinity. With an ordinary sequentially executing function, I can safely assume one thread will run the function from start to finish. But if I’m using continuations to provide the illusion that I’ve got sequential execution spanning multiple user interactions, then I might get a thread switch every time I generate a web page.

I see this as kind of a bogus problem. How often, when writing an ASP.NET application, does one work with objects or resources that have thread affinity, and expect them to be on the same thread when you next enter the server? I should think one doesn't expect this at all - one doesn't normally have the ability, much less the "problem", of handing an object from one request/response cycle to the next.

Web Farms. This is essentially the same problem as the thread affinity issue, but at the machine level: in a web farm, your sequential function might end up executing on a variety of machines over its lifetime. However, you’d probably avoid this problem in practice using sticky sessions. (And unless your continuations are serializable across machine boundaries you’ll have to do this.)

I don't see any point to using continuations if they can't be saved and resumed at will, across process boundaries, machine boundaries, server restarts, etc. If you limit the power of the continuations you consider, it's pretty easy to condemn them as not being powerful enough.

The Back Button and Branching

This one’s the killer.

Your web site may present linear user journeys, but that doesn’t mean your users necessarily follow them. I often don’t.

I habitually do two things that will confound any web site that expects the user to do things in a particular order. First, sometimes I use the back button. Second, sometimes I bifurcate my navigation - I’ll open a link in another tab. Both of these will confuse any web site that thinks it knows what my ‘current page’ is. The notion of a current page is not enshrined in either HTTP or HTML, and I enjoy the flexibility this offers me when browsing sites. Indeed, it’s one of the reasons I really like tabbed web browsers.

Here, I don't know what Ian is talking about. I mean, I understand exactly what he's saying, but it's a complete non-sequitur to jump from this behaviour to saying that it's incompatible with continuations. Continuation state forms a linked list on the heap. One can share the tail of a linked list among an arbitrary number of heads with zero problems.

This means I have to write my function in such a way that it can cope not only being rewound, but also to being split so that multiple threads execute the function simultaneously, each taking different paths. But of course because I’m using continuations, each of these threads gets to use the same set of local variables. The fact that I enabled users to inject gotos into my code at will is now looking like a walk in the park - now they can add arbitrary concurrency!

Here, when Ian says "use the same set of local variables", he's talking about mutating the tail of the list, which might be shared by other heads. And he's right in one sense: if you modify the tail, you better mean it, because you're modifying shared state, not local state.

However, I have a couple of more aces up my sleeve. If desired, the transformation that turns sequential code into CPS can also turn mutating assignments into single static assignments. Single static assignment is a form used in some compilers in the back end to ensure that a variable can only ever have a single definition. If one could annotate one's variables, indicating if they should be shared across multiple continuations (stored in the tail) or strictly local to every continuation that redefines it (essentially, hidden in a scoping sense by the redefining activation record), this problem goes away.

The deeper objection I have to Ian's criticism is that you have to deal with this problem anyway, and program transformation just makes your life easier. Consider what you'd have to do to handle Back Button and Branching without using the approach sketched above. You have all the same problems. You still need to make sure that wherever you stuff away your state, that it isn't inappropriately used by the branches. SSA transformation can do this automatically and declaratively.

Consequently, this approach requires you to write your code in such a way that it can tolerate sudden halts, thread switches, rewinding, and forking of execution.

Sudden halts, thread switching, rewinding, forking: what is it in the tear-down and re-setup of the ASP.NET page cycle that stops you from seeing these things, if you choose to describe them that way? Tearing down the page is surely a violent halt. Setting up again, possibly on another machine, is surely a wrenching thread switch away from your carefully constructed state. To support rewinding / forking (aka Back button / new tab / window), you still need need to juggle your state so that it's correctly stored, keyed and associated with its page which was originally displayed to the user. But continuations can do *all* of these things with easier to read code, and selective SSA transformation turns a fiddly choice (should this data be in the database, in memory, in a cookie, querystring, hidden field, client-side state sent back through AJAX) into a declarative form which your Web library should be abstracting for you.

Does your web development environment supporting continuations? If not, why not?

I will give Ian something, though. It's certainly not true (and shouldn't be true) that one simply writes a sequential application using continuations without thought for the network and then expect it to work fine across the web. That can't happen. However, I do believe that with the correct libraries, language, annotations and transformations, a far better language for web apps can be created. Whether it'll be along the lines of Volta, or one of the frameworks described herein, I don't know. However, I strongly suspect new language constructs, or at least flexible DSL support, is necessary. I can even think of implementing continuations using monads, so perhaps it'll be Haskell!

Async via LINQ

2008-01-16T12:15:00.000Z

Andrew Davey has posted an interesting article on composing async operations that doesn"t require a spaghetti-code style state machine. It doesn"t look particularly hardened to exceptions on End* calls, but the technique is interesting, using the monad-like nature of LINQ to compose continuations.

I blogged about something very similar over a year ago, and it looks like it's getting easier to do now.

Monads in C#

2008-01-11T02:54:00.001Z

Probably the best outline of monads I've seen yet. Easy to understand for the C# programmer.

Volta, Continuation-passing style

2007-12-22T13:29:00.000Z

Over a year ago, I pointed to a particular pattern in C#, using delegates with asynchronous methods, that used continuation-passing style (CPS) to make writing scalable IO-heavy code easier:

A lot of work? Yes, but better than people who write business code for a living having to work in a nest of hand-written continuations just to get scalability.

If the folks advising asynchronous code are serious about recommending this approach to scalability, then the enabling tools need to be available. It's conceivable that the CLR could do this automatically, with some kind of [AutoAsync] attribute, along with a couple of utility methods to access the generated Begin/End pair via reflection or whatever. That would keep the C# language clean while leaving the CLR open to a lazy implementation approach (using ThreadPool threads), but also with the power to create the transformations discussed above.

Now it looks like some of the folks over at MS are having similar ideas, in their Volta preview. It's not quite the same, you have to write your async method in a particular way, but with the automatic transformation of the callsite into the appropriate format, it's a good step forward:

Asynchronous Calls
Hiding network latency requires asynchronous calls. In the first technology preview, Volta allows programmers to add asynchronous versions of methods on tier boundaries.

To make a method asynchronous, define the CPS-equivalent method signature and annotate it with the Async attribute. Volta will generate the body and modify the call-sites accordingly.
    [Async]
    public static void F(string s, Action k);
If the programmer invokes an asynchronous method F, then Volta will launch the invocation on another thread and invoke the continuation upon completion of the call to F.

I'm not entirely delighted with some of the ideology behind Volta - I don't think hiding the network's existence in and of itself is necessarily a good thing - but making the right kind of code easier to write is definitely a step in the right direction.

Cygwin

2007-12-10T18:03:00.000Z

It's been a long time since I last posted. I've been working on the Delphi compiler all the while, but with uninteresting bug fixes (usually too boring to talk about), learning more about the code base (not general enough to talk about) and working on new features (not public enough to talk about), it's been rare enough that I found something interesting enough to talk about. So, I've decided to take a different tack.

I've had the "opportunity" to set up a number of PCs and laptops recently for my personal use, general and development work. Quite a bit of customization is necessary before I'm comfortable with a system. Apart from the usual handful of utilities (Firefox with extensions, Winzip, Winamp, Forte Agent), there's one other thing that I can't really live without - Cygwin. The bash shell running in an rxvt terminal window is my main interface with Windows.

There's one big reason for this. The shell is very programmable, so any time I need to do work of a repetitive nature, I can write a script. Whenever I find myself doing similar things, I can refactor my work and write a new utility script containing the commonality. My life would be a lot harder without Cygwin. Sometimes I wonder why it isn't more popular than it is; but then, the default Cygwin setup isn't very appealing. I remember when I first installed it, and got to use the usual Unix utilities I was familiar with from Linux, only this time in Windows, but I was still using the crippled cmd.exe shell from NT, running in the crappy console that Windows provides by default. I'm going to write a series of posts on how I beautify my Cygwin environment.

Installation

The first step is to install Cygwin. I do this in a four-step process:

Download setup.exe from cygwin.com.
Run setup.exe, and tell it to download (but not install) everything to a local directory. I choose c:\cygwin\opt\var\cygwin-cache. I then rename the ugly directory name it generates (based on the mirror you chose) to something briefer.
I then run setup.exe again (setup.exe normally resides in c:\cygwin\opt\var\cygwin-cache on my system), and perform an install, selecting those packages that I know I want and need. Those include:
- All the programming languages, from clisp and SWI-Prolog through byacc and cocom to gcc and nasm.
- The text editor joe and the rxvt terminal.
- ImageMagick, Ghostscript, TeX - stuff I seldom use, but like to have available.
Finally, I add the main binaries directory (c:\cygwin\bin by default) to my system path.

Actually, I'm lying. I don't normally use setup.exe to download the cygwin-cache directory, since I already have one. I actually use wget to download the cygwin packages directly from a mirror on a monthly basis, but that presents a bootstrapping problem: one wouldn't normally have wget without already having installed cygwin.

In any case, once I've gotten Cygwin installed, it's time for me to set up my home directory (the ~ directory in Unix parlance; defaults to c:\cygwin\home\<username>). This is created the first time you run a Cygwin login shell, such as from the shortcut the setup.exe program creates (or by running bash --login). All the stuff up until now is pretty regular Cygwin orthodoxy: people usually stumble along this far all on their own. I know I did the first time, but I found bash running in NT's command window pretty unpleasant to use. Here's where I make Cygwin usable, at least to me.

Beautifying

The main objective is to get bash running inside rxvt. This can be done pretty trivially:

Create a shortcut to c:\cygwin\bin\rxvt.exe (assuming one chose the default install directory)
Modify the shortcut and change the target so that it has a few extra arguments: "c:\cygwin\bin\rxvt.exe -e bash --login".

That tells rxvt to use bash rather than sh as the shell, and tells bash to run ~/.bash_profile (amongst others) as its startup script, rather than ~/.bashrc.

However, the default shell is still pretty unappealing: an ugly white window with black text. That's why I use some customizations. Rxvt reads in .Xdefaults from your home directory when it starts up, even though it's a Windows program, not an X one. .Xdefaults uses a pretty simple line-oriented file format. '!' starts a comment, which extends to the end of the line. Here are some lines I add to make things more suited to my preferences:

Rxvt*geometry:120x43

Rxvt*background:rgb:00/00/20
Rxvt*foreground:rgb:C0/C0/C0

Rxvt*color1:red
Rxvt*color2:rgb:72/A0/32
Rxvt*color4:skyblue

Rxvt*color3:yellow
Rxvt*color5:magenta
Rxvt*color6:rgb:20/C0/A0
Rxvt*color7:rgb:C0/C0/C0

Rxvt*color9:red
Rxvt*color10:rgb:72/A0/32
Rxvt*color12:skyblue

Rxvt*color11:yellow
Rxvt*color13:magenta
Rxvt*color14:rgb:20/C0/A0
Rxvt*color15:rgb:C0/C0/C0

Rxvt*colorBD:rgb:C0/C0/C0

This remaps the 16 console colours a little, inverting the colour scheme. I get the names for these variables (called resources in X parlance) from the rxvt manual page, available from "man rxvt". Here are some other relevant lines in my .Xdefaults:

Rxvt*jumpScroll:True

! I use Dina-9, from the font Dina, which I installed separately
!Rxvt*font:-*-lucidatypewriter-medium-*-*-*-12-*-*-*-*-*-*-*
Rxvt*font:Dina-9

! I have an ego
Rxvt*title:Barry's Bash

! Scrollbar on the left looks odd.
Rxvt*scrollBar_right:True

! In case I forget something; this is somewhat better than cmd.exe's usual limit
Rxvt*saveLines:30000

Rxvt*termName:rxvt

! This is the number of pixels between text rows; aesthetic issue, depends on font and size
Rxvt*lineSpace:1

After having done this, I have something I can live with.

Broken by Default

2007-06-11T16:39:00.001+01:00

I recently had reason to use Firefox's bookmarks' feature, "Open All in Tabs". I was unpleasantly surprised to discover that it closed my open tabs, and navigated away from my existing pages (including breaking my VPN connection to Borland's network). It's one of those features that's broken by default, by design, because - well, I don't know why. Apparently there's been some secret discussion somewhere 3+ years ago, that decided that the current behaviour is best. I have no doubt that the reasons are bogus :)

Anyway, I found out about about:config setting browser.tabs.loadFolderAndReplace, which fixes this behaviour and sensibly creates new tabs, rather than overwriting your current tabs and bringing your network down around your ears.

Here's another, more verbose link, describing how to fix the broken behaviour. Yes, I'm editorializing, but I'm just pissed because I had to fix everything back up again, after this "feature" exploded in my face.

Acropolis: The Second Coming of MFC

2007-06-04T22:33:00.000+01:00

I notice that MS have released some early bits of a new rich client application framework. I also note that the XAML namespace prefix in the demo video ("Introducing Acropolis") is Afx, the same as the old MFC header file name.

The initial wizard looks eerily familiar, very MFC - but everything has been updated, and something that's particularly interesting to me is how the Application XAML - an object serialization format, not necessarily limited to UIs - is presented in a design view that looks quite similar to a web page. In a past life I worked on a system that used a lot of metadata, and one of the many design metaphors we looked at was document-like layout for non-document (or at least, non-traditional document) data.

I'm waiting for the day when people incorporate 3D zooming transitions into these document layouts, taking advantage of the rich client power and modern hardware / WPF, to pack more data in the spatial screen landscape. Defining a 2D/2.5D (I count zoomed depth as 0.5 of a dimension) mapping for an application's structure has for a long time seemed to me like a good way of getting a higher-level, more abstract visualization / editing experience for today's larger application source bases.

Having worked on some fairly complex systems from front to back, top to bottom, and known how everything was put together - having written most of it - it was always frustrating to me not having first-order unified view (as opposed to derived, or via stale documentation) that explained how the application fitted together.

My comment is at quite a tangent to the specifics of the Acropolis release, but this little artefact hinted of a direction that I hope development UIs take in the future. For what it's worth, I don't believe in UML - I'm talking about something which is qualitatively different, in that the visual mapping function is domain-specific and tailored to the different functional aspects of an application, is 2-way with its component structure, and has hyperlinks connecting related parts. Perhaps the mapping function could be rotated around different axes, to get different perspectives on the app. Making the source code for a system look more like blueprints. Musings for the future...

XML, the right format for object graph serialization

2007-05-22T06:08:00.001+01:00

I was reading this blog entry, and my annoyance meter was piqued:

One of the advantages of having a canonical representation of an object tree, is that it serves as a great interchange enabler. That canonical representation doesn't need to be Xml, but it seems like a good choice.

Sigh. The assumption of an "object tree" - object graphs usually aren't trees, they typically have lots of cross-references. Objects in memory form edge-labeled graphs, while XML is a node-labeled tree. Converting objects to XML requires some naming scheme for those objects which have relationships more complex than parent-child.

If you design your objects along functional lines and make them immutable after the constructor has finished executing, this scheme can work, but I don't believe there are many useful structures with no cross-references whatsoever. It works best if you have a rooted namespace context like TComponent and its Owner, or something similar where objects can be identified by a URL - ideally one and only one URL.

I believe that in some decades from now, we'll look back at this objectification of the world, this current habit of seeing the power of objects in e.g. GUI libraries and then applying the same hammer to all manner of delicate problems, as one of the bigger mistakes in the history of programming. Basically, both hierarchical data (e.g. XML) and relational data (collections of fact tuples) are bad fits for object orientation, and in the code side of the house (as opposed to data) lightweight processes (think Erlang) haven't had their due. And popular programming languages are starved of higher-order abstraction facilities.

I wonder how this is going to change. C# is gaining its extensions (and cruft - having both lambdas and anonymous delegates in the language is a bit of an eyesore), but it's still pretty poor in many other ways. It's very deeply wedded to imperative, linear thinking, with very few transformations before execution. Static typing is fine, but metaprogramming and dynamic programming's rise show why it is also constraining. Statically typed languages that lack a higher order, a way of programming over the type domain as well as the value domain, end up falling back to reflection and other weakly typed loopholes to overcome traditional (C, Pascal, Java) static typing's inflexibility.

Silverlight and DLR announcements

2007-05-02T06:31:00.000+01:00

The latest buzz in the dev community online is all about Silverlight. From my perspective, there are a number of things to tease apart:

Silverlight as a Flash alternative
Silverlight as a WPF-lite, with CLR
Silverlight as a dynamic language runtime, and the DLR itself (standalone) - one can preview this framework in IronPython

Flash alternative

I know I'm not a typical web user, but my main experiences with Flash have been:

Amazingly annoying advertisements
This is the main reason I disable Flash by default, with FlashBlock in Firefox. If I wasn't able to use Flashblock, I would uninstall Flash instead - I'd rather lose video than suffer distraction.
A video solution
One of Flash's nice advantages is that it keeps the Linux folks onside, as even though it's not open-source, they can still consume.
Extremely crummy rich applications
I have never encountered a Flash application that (a) had good keyboard support and wasn't terminally mouse-dependent or (b) didn't prioritise flashy (ha!) animation over and above actually making use of the richer platform than poor/pure HTML or (c) whose rich vector animations didn't regularly peg a CPU at 100%.

So, hopefully folks will excuse me if I view Flash as effectively a video codec, and that MS will face a somewhat uphill battle trying to supplant it as a preferred codec.

WPF-lite with CLR

There's another thing I find striking about the Silverlight story: how similar it is to Java applets. Things that make Java applets suck are (a) the cold start cost (chuggalug of disk, bloat of memory) and (b) ugly Swing UI controls, and (c) the plain fact of JVM dependency.

Cold starts are always important, and I feel the CLR has a better handle on controlling those costs than most JVMs, and certainly expected browser memory usage is a lot higher these days, regularly climbing above 200MB on my machine for one.

It ought not to be hard for WPF to improve on Java's controls, and there are folks out there already looking to market for this platform.

The dependency is the most troubling issue. Flash has gotten to where it is chiefly (I believe) because of video; MS needs some similar mass-market hook to get adoption, and I'm not sure its video implementation is a differentiator, much less an advantage - mainly because I haven't seen it yet. But really: how much better could it be, that would make a difference?

DLR: Dynamic Language Runtime

As a language guy, this is the most interesting part of the whole enchilada. JavaScript/EcmaScript in the browser is slow, and needs techniques such as JIT compilation, dynamic call optimization based on caching, etc. that DLR makes available in order to be made faster.

The DLR is also an interesting platform play, creating an interoperability platform suited to dynamically typed languages with late-bound types, methods and fields. Most dynamic languages permit things like expando methods, jamming on fields and closures to existing objects and extending them, very rich reflection and metaprogramming, runtime 'eval' support, etc. - but all in quite similar ways. In some respects, DLR is a little like late-bound COM for the .NET generation.

It's interesting that the Java platform never developed this, even though it's the other main target for dynamic languages looking for performance improvements. The open-source movements for e.g. Jython, JRuby etc. never really get together and try to find the commonalities, and implement them in a shared library, and eliminate duplicated effort. It's one of the structural deficiencies of open source - once the code's been implemented in specific layer, it tends not to migrate to a lower layer. It's also an obvious move that it's taken someone like MS to make - I wonder if Sun regrets not doing something like this. Finally, it's notable that Java doesn't have anything like Reflection.Emit, one of the most interesting features of .NET for me ever since it came out, and one that DLR leverages heavily for its performance benefits. Java users have to work a lot harder to get the same effect, dynamically generating .class files.

Conclusion

I think there's a big need for a rethink of JavaScript in the browser, but I'm not sure that Silverlight is the solution. Part of me hopes that it is, but I'm afraid that when people wake up out of their daydreaming, and look at things in the cold light of the dawn, they'll see that Silverlight needs to do so much to prove itself as a simple video platform (or some other hook) and get adoption, over the next (say) 3 years, before it can hope to be considered an application development platform. Proving that it's not just Java Applets Mark II, or limp along as a second-rate competitor like QuickTime, is going to be tough.

On the other hand, the DLR, as a thing in itself, is great stuff. I can see opportunities to add DLR awareness to more traditional statically typed languages and get benefits from both worlds.

Eric Lippert, C# 3.0 Type Inference, Charlie Calvert & Turbo Pascal

2006-11-17T18:48:00.000Z

Some great details in a video linked from Eric Lippert's blog.

There's a lot of detail on the new algorithm for type inference in C#. It all looks increasingly hard to parse without build a whole tree without typing for the expression containing the LINQ query, and because lambdas can contain statements, that implies a whole tree for statements too. In other words, a compiler implementing this functionality wouldn't always be able to annotate expression types as it parses - it'll need another descent / transform through the parse tree.

Also interesting, for me at least, is the Turbo Pascal box in the background on Charlie's shelf, about 25 minutes in - given that I'm now helping maintain the Delphi compiler, the descendant of that product.

Considering CLR & JVM as Manycore Paradigms

2006-09-21T06:48:00.000+01:00

Larry O'Brien asks " Are CLR and JVM suited to manycore?" My first instinct is to say no, because they're built on sequential execution and mutable data structures. That said, RPN-stack-based code like IL and JVM opcodes (modulo control flow instructions) is basically an expression graph serialization format, so there's a shadow of hope in there, also considering Expression<T> and friends in LINQ. However, I definitely don't think either of them are in the shape of the end of the road, a suitable UNCOL.

I'm sure you're familiar with Wesner Moise's blog, where he's made some entries relating to the idea of moving away from structures requiring mutability, and towards more functional structures. One recent post that's still in my RSS reader is http://wesnerm.blogs.com/net_undocumented/2006/09/modelview.html, where he hints at some interesting ways of using immutable structures in document / view architectures.

For better or worse, I don't fully share Larry's pessimism (privately related) about functional / dataflow and other "different" ideas. I think we'll see more stratification in the software industry, as people who need the extra performance of parallelism seek out new local development optima, while people who only need current-day levels of performance for tasks that are relatively trivially parallelized (such as today's request/response server code) use other, more procedural languages, like Ruby, C#, Delphi, etc.

IMO, one of the worst things historically to have ever happened in programming was the fashion for C as the "real" programming language. With its primitive strings and its unsafe standard library (i.e. including functions which are literally unsafe no matter which way you call them, consider gets() for example), I think it's wrought unnecessary and disproportionate harm. I hope that any coming stratification doesn't fall into similar social trip-ups that blight us for another few decades.

Growth of the Internet through the Lens of the Social Sector

2006-09-07T23:18:00.000+01:00

Facinating post by Stirling Newberry at TPM: "... let me boil down one of the simplest and most important ideas of the next half century into a short space."

Interfaces in Delphi / Win32

2006-08-29T22:38:00.000+01:00

Craig Stuntz comments on my remarks about interfaces in Delphi / Win32:

Regarding interfaces, I'd argue that Delphi Win32 interfaces are more similar to .NET interfaces than COM interfaces are to COM+ 2.0 (a.k.a. .NET) interfaces insofar as they don't completely dictate lifetime management. In Delphi Win32 I can (and frequently do) override reference counting and use interfaces to provide multiple interface inheritance of classes without reference-counted lifetime management of instances.

Sure. Delphi/Win32's interfaces are a superset of COM interfaces; they include support for native Delphi types (such as AnsiString), and when one is working in single-language / single-vendor (taking BCB into account) environment, it can be useful to discard the language-neutral COM conventions. That doesn't stop the Delphi compiler from performing all the refcounting operations anyway, though.

I can't cast from an interface to an object, but in other respects it's pretty similar to what I do with interfaces in .NET. The underlying mechanisms are very different, yes (e.g., GUIDs as IIDs), but in the end I find myself doing similar things in code.
When you say interfaces are different in Delphi Win32 and .NET you seem to be talking about lifetime management.

I'm talking about slightly more than that. I'm talking about the basic services that IUnknown provides: lifetime management (AddRef and Release) and interface negotiation (QueryInterface). All Delphi/Win32 interfaces derive from an interface that supports these three operations (whether it's IInterface or IUnknown depending on version). Delphi/Win32 implements interface casting (in so far as it does at all, excluding Supports() etc.) through calls to QueryInterface, via 'as'. Delphi/Win32 doesn't support 'as' casting unless the interface has a GUID, a COM-ism. Delphi/Win32 classes can dynamically change which interfaces they support (within or without COM rules) by explicitly implementing QueryInterface() - that won't work in .NET (I use IServiceProvider for this). All COM interfaces consumed in Delphi in the orthodox way (ignoring the old Delphi 2 stuff) are also Delphi/Win32 interfaces. Delphi/Win32 interfaces and COM interfaces are basically made of the same "stuff", with the same binary format.

.NET interfaces are entirely different; they're a runtime feature, and they aren't a binary standard. They're not ref-counted. They don't have the same layout. Casting is defined by the implementing class, and can't be dynamically changed (RealProxy etc. aside). They don't require GUIDs for full support. COM interfaces get wrapped in runtime callable wrapper (RCW), rather than being actual .NET interfaces.

But the lifetime management features in Delphi Win32 are something I generally try to work around because (1) I mostly don't use them for COM and (2) I find having two wildly different lifetime management schemes coexisting inconvenient. When I work in .NET I use the GC; I would find doing a mixture of GC and explicit allocation / disposal messy. Similarly, I only want my object instances reference counted in Win32 when I can't avoid it, like when I must use COM. Otherwise I want to do things explicitly, for the sake of consistency.

Sure - but you have to do this yourself! Delphi's TInterfacedObject, the normal base for a class supporting interfaces, implements COM rules. I think it can even be useful to work within the COM rules too, when restricted to Win32-only code, since the automated ref-counted GC supports shared ownership fairly well.

Delphi Native Closures, Part II

2006-08-29T16:47:00.000+01:00

A few days back, I made a post on the difficulties of implementing closures in a non-GC language.

Craig Stuntz made a comment:

Barry, I don't see how this problem is any different than in operator overloading, which is already supported in Win32, albeit in very limited conditions. So there's a fourth possibility not mentioned in your list, which is to only support it for functions with argument data types such as strings and value types which can be simply cleaned up. It's far from ideal, but given the OO example not unprecedented.

I agree with Craig re possibilities, there are more ways to slice it - but some slices are bigger than others! In my previous post, I cut things into two basic slices: how to free the delegate, and which captured variables to free. Of the two, the first one is about 90% (or more, FinalizeRecord in the Delphi RTL can do the second job) of the problem.

I don't agree with the comparison to operator overloading. Implementing closures is far more complex than operator overloading, because closures aren't limited to traditional Standard Pascal downward funargs; they can live long after the creating frame goes away. That isn't the case for temporaries created through support for operator overloading. The bulk of the work would be in putting the stack frame on the heap and refcounting it, and in implementing reference counting on every Delphi Win32 method pointer. I could then see people (ab)using COM interfaces to get deterministic destruction, effectively the same as the notional 'finalization' section I described.

Lest one think that one could get away without refcounting by limiting closure support to downward funargs, well, that would be a problem: closures gain a lot of power through composability. By composability in this context, I mean the ability to write a function that takes a function and returns a function, where the returned function is a function of the argument function, and thus relies on closure or some other way of tracking the passed in argument.

I should make that concrete. Consider this predicate, in C#:

public static Predicate<T> Not<T>(Predicate<T> pred)
{
    return delegate(T value) { return !pred(value); };
}

This snippet can't be implemented with just downward funargs because the stack frame of Not disappears when Not returns.

This is the heart of the problem: not only a transformation of stack into heap (of the lexically closed & captured variables etc.), but implementing refcounting everywhere a method pointer exists. Whether or not simple types like string and record and interface (and thus 'simple types' is open ended) are supported or not, is relatively trivial.

Another thing this brings up: the (ab)use of COM interfaces to implement simplify lifetime management of plain old Delphi objects, something which effectively would add the power of a 'finalization' section, without being explicit about it. It gets at another issue in my earlier post: the divergence of .NET and Win32 forms of Delphi. How important is it that the two are the same? Because interfaces don't work in a similar way at all in .NET, they're completely different. They're so different they probably deserve different names.

Specfiying Ownership

2006-08-28T21:06:00.000+01:00

Raymond Chen's post today, railing against boolean parameters, reminds me of a small detail that made one of my APIs easier to use.

The reason boolean parameters are bad is that it's often hard to figure out, from reading the code, what 'true' and 'false' refers to. Raymond points to StreamReader's constructor overload, StreamReader(Stream, bool). ~~In this case, the boolean argument applies to the ownership of the stream - that is, will the StreamReader dispose of the Stream when it itself is disposed?~~ Update:No it doesn't - a salutary reminder of the problem with boolean arguments! It indicates whether or not the StreamReader pays attention to byte order marks. In any case, my comment below refers to resource ownership.

For this situation in my own APIs, where transferral of ownership needs to be flexible, I use a little enum:

/// <summary>
/// Describes who controls a resource that is transferred between objects.
/// Useful for negotiating who should call IDisposable.Dispose when done.
/// </summary>
public enum ResourceOwnership
{
    /// <summary>
    /// Don't change the status quo regarding ownership of any resources.
    /// </summary>
    Preserve,
    
    /// <summary>
    /// The ownership is transferred to the callee in the case of a resource setter, 
    /// or transferred to the caller in the case of a resource getter.
    /// </summary>
    Transfer
}

I'm not 100% happy with the name of the first option, Preserve, but I can't think of a better one. Anyway, the little insight behind the enum is that rather than thinking about source and destination ownership as you interact with a class and hand it a resource, you think about how you're changing the existing ownership (i.e. transfer) or preserving the status quo. From a calculus perspective, the enum describes the derivative of the ownership, rather than the ownership itself. I find this works better than a boolean, which tries to describe the ownership directly, and also better than a special-purpose enum which contextualizes the ownership.

Delphi Closures / Anonymous Delegates

2006-08-26T18:22:00.000+01:00

Fredrik Haglund's post today reminded me of a post I made in the newsgroups about the difficulty of implementing anonymous delegates or closures in Delphi.

I'm a big fan of closures, as I've written about them in the past. I hope that Delphi gets some form of anonymous delegate, closure or lambda or some similar feature, while also being less verbose than local procedures and functions. Indeed, with LINQ coming along in the next version of C# and its corresponding .NET version, there'll be a requirement to integrate with it. LINQ pretty much needs lambdas, as well as expression trees, for good integration.

The problem comes in implementing closures in native code. It would be unfortunate if Delphi, the language, diverged further between the two main platforms it supports, .NET and Win32. Closures gain much (if not most) of their power by capturing local variables and arguments. If any captured local variables refer to object instances whose lifetime is logically associated with the lifetime of the stack frame which creates the closures, how does one ensure that those objects will get freed?

For example, in C# 2.0, one can write:

using System;

static class App
{
    static Action<string> CreatePrefixer(string prefix)
    {
        return delegate(string value)
        {
            Console.WriteLine("{0}: {1}", prefix, value);
        };
    }

    static void Main()
    {
        Action<string> prefixer = CreatePrefixer("foo");
        prefixer("bar");
        prefixer("baz");
    }
}

This keeps things simple by only using native .NET types, but hopefully it can illustrate the problem. By calling CreatePrefixer(), one creates an argument value (i.e. similar to a local - I'd have made it a local, but I wanted to keep the sample simple) in the stack frame associated with the CreatePrefixer() invocation, called "prefix". This value is captured by the created anonymous delegate, which is returned. That means that "prefix" must live on beyond the lifetime of the stack frame. So, the questions come:

How do you free the returned delegate?
- Manually? Delphi users aren't used to freeing procedures or functions of object.
- Refcounted? Is there a type system difference between existing method pointers and these new delegates (confusing) or would all method pointers now be refcounted (wasteful)? What if you got a cycle? A cycle involving method pointers would be extremely hard to spot since the graph depends on the runtime execution flow graph, much harder than a cycle in data structures, which is part of the statically declared data structure graph (assuming no funny stuff with typecasting).
How do you free the captured variables?
- How do you know which ones the stack frame has ownership semantics over? In Native Delphi, strings have the nice property of being reference counted, so the solution is trivial for that datatype, so long as we are informed when the delegate is no longer needed. But what if it's an arbitrary user-defined datatype?
- Should the anonymous delegate automagically create code to call TObject.Free?
- Should there be a "destructor" or "finalization" block in the inline delegate definition? And won't this code be ignored for .NET execution?

For that last option, consider something like:

program Test;

type
  TActionOfString = procedure(const s: string) of object;

function CreatePrefixer(const prefix: string): TActionOfString;
begin
  Result := procedure(const value: string)
    begin
      Writeln(prefix, ': ', value);
    finalization
      // An optional section, any finalization to execute
      // when the anonymous delegate ultimately goes out of scope.
    end;
end;

var
  prefixer: TActionOfString;
begin
  prefixer := CreatePrefixer('foo');
  prefixer('bar');
  prefixer('baz');
end.

These two problems are why this construct is (to the best of my knowledge) typically restricted to garbage collected languages. Should Native Delphi have an optional compile mode that simultaneously turns on this language feature, and links in a conservative GC similar to the Boehm collector (which is currently used by Mono)?

Two other alternatives are possible: only support closures in the .NET compiler, but not in the native compiler; or don't support them at all.

Attribute Design

2006-08-25T05:10:00.000+01:00

Krzysztof Cwalina is running a little poll attribute design on his blog. I made a comment, but I thought I'd post my thoughts here too.

The question is: is it better to have (i) lots of different attributes, or (ii) fewer attribute but use enumerations in the constructor? Naturally, this dichotomy is limited to those attributes that don't have any other arguments, i.e. only "marker" attributes.

Attributes
- [Foo]
- [Bar]
- [Baz]
Enumeration
- [Foo(Kind.Foo)]
- [Foo(Kind.Bar)]
- [Foo(Kind.Baz)]

In many ways, it seems to me to be analogous to writing several methods versus one method with parameters. It depends! How related are the attributes? Enums are quite discoverable - all the options pop up when you type in the enum name. With multiple methods / attributes, it's harder to find the related group.

If the different attributes / methods aren't closely related, then it would be wrong to conflate them into an enum.

What about user extensibility? With methods / attributes, one can define new classes / descendants and add new methods / classes that look just like the old ones. With the enums, they're baked in. This can be both good and bad - it's more encapsulated etc, less risk of confusion.

Another aspect: types for a purpose versus flexible types. Sometimes, people who are beginners to a problem look for something which is the perfect solution. Trouble is, most people's problems are diverse. This can lead to a large number of "simple" types for solving each particular class of problem, but the overall result is that the solution space is *more* complex because there's more of it. Beginners and experts alike become frustrated; the first daunted, the other feeling the clutter. In this light, fewer types that are configurable sounds better - leading to the attributes with enum arguments approach. But then - only if it makes sense!

A rule of thumb: if the attributes would probably start or end with a common prefix or suffix, then it would probably make more sense to use an enum instead.

The Nature of Blogging

2006-08-23T02:37:00.000+01:00

Interesting post about the nature of blogging.

Capability-based Security

2006-08-23T00:44:00.000+01:00

A post on Raymond Chen's blog happened to coincide with a paper I was reading, Capability Myths Demolished. More on capabilities.

It's interesting to see how our existing systems and solutions, and how popular they are, subtly influence the way we see the world. It's all about assumptions - if you don't question them, you're likely to be stuck in a local maximum, rather than wandering out to find a better maxima elsewhere.

I recommend reading the paper. It's written in a relatively colourful style, somewhat less dry and academic than some. Just thinking about the details of implementing a usable capability-based system has me thinking about how it influences other things, involving system maintainability etc. I've always thought that ACLs are a pain to manage and that Unix's 3*3 bits + sundry are better, if not for power, then for usability. I can see ways for capability-based systems to be even better, especially for things like elevating security privileges (like in Linux, MacOS X, Vista), and running less-trusted applications in the current user's account.

Food for thought.