voodoo slide

Tundra, my build system

2010-08-31T14:55:00.002+02:00

I've been working on a build system, Tundra, to scratch my own itches and it's come along far enough that I've released the code in beta form over at github (http://github.com/deplinenoise/tundra).

Tundra has taken on many different architectures over the years I've hacked on it, but I've finally arrived at a Lua frontend and a C backend. Here are some of the goals I've had with Tundra:

Optimize for iterative builds
Flexible configuration frontend (easy to add configurations and variants)
Keep the build system core small and simple
Utilize multi-core hardware even for scanning and up-to-date checks
Reliably support code generation (passes, DAG scheduling)
Separate configuration and building to make it easier to optimize & debug

Of course now that Tundra is nearing completion it's fun to show some performance numbers. Noel Llopis did a great writeup on the various build systems available a few years back (http://gamesfromwithin.com/the-quest-for-the-perfect-build-system). Using his script to generate 10 libraries with 50 files each (500 files total) I ran a small benchmark. Here's the statistics output from a no-act run of Tundra on that dataset. This was on a Core i7 box running Win7/64 with everything in disk cache; but the disk itself is a slow 7200 RPM disk:

J:\Scratch\benchmark>tundra --debug-stats
*** build success, 0 jobs run
post-build stats:
  files tracked: 1511 (1511 directly from DAG), file table load 1.64%
  relations tracked: 1034, table load 1.12%
  relation cache load: 0.003s save: 0.000s
  nodes with ancestry: 513 of 513 possible
  time spent in Lua doing setup: 0.057s
    - time spent iterating directories (glob): 0.004s over 10 calls
  total time spent in build loop: 0.032s
    - implicit dependency scanning: 0.152s
    - output directory creation/mgmt: 0.000s
    - command execution: 0.000s
    - (parallel) stat() time: 0.039s (2010 calls out of 0 queries)
    - (parallel) file signing time: 0.031s (md5: 0, timestamp: 1500)
    - up2date checks time: 0.016s
  efficiency: 0.00%
total time spent in tundra: 0.0926s

I'd say 93 ms for a no-act build is pretty nice considering that this includes full #include scanning! We can see that 57 ms was spent in Lua code creating the input DAG and 32 ms was spent in the native build loop. This is nice because if the build master is complaining about slow builds we can easily see if it's due to his bad scripting or due to actual build performance ;)

If you want to give Tundra a spin (it's beta quality software) you can get a binary drop and the documentation here: http://github.com/deplinenoise/tundra/downloads.

Visual Studio and your AppData\Temp directory

2010-07-23T11:25:00.000+02:00

Visual Studio has a tendency to leave a lot of junk files behind when you cancel builds. A colleague of mine at DICE had 22,000 temp files weighing in at over 14.5 GB in his AppData\Temp directory! Having more than a few hundered files in a single directory on NTFS is suicide, so you can imagine how much his compile times improved when he emptied that directory.

The real question is how to get Microsoft's CL to stop creating these temporary files, and failing that, how to make it clean them up when you abort it?

In the meantime, I'm relying on a little tool I have running on a schedule that wipes files that are older than a few days from my AppData\Temp directory. Lo-fi solution to a yucky problem.

How to stop Vista from trashing your disk

2010-06-08T10:25:00.001+02:00

Ever notice how Vista churns your HDD? I had the misfortune of having to install Vista on a machine again and finally took the time to figure out what to do to make it stop. I knew about the first four, but the last two were new to me and made all the difference:

Disable ReadyBoost
Disable SuperFetch
Disable the Windows Search service
Disable the scheduled Disk Defragmentation task
Disable the scheduled System Restore task (shows up as super-high System Volume Information traffic)
Go into the registry and disable prefetching entirely.

All these steps removes 99% of the extra disk activity and now the disk doesn't rattle all the time :)

c-amplify prototype available

2010-02-03T23:53:00.002+01:00

I've uploaded the c-amplify to gitorious so people can look at the code. It's pretty rough around the edges right now (it's a rant-fueled hack after all), but here's a basic guide to getting started:

Clone the repository here: http://github.com/deplinenoise/c-amplify
Get the excellent cl-match library and add it to your central ASDF registry
Load the c-amplify ASDF system into your lisp (Clozure and SBCL on Win32 should work well, it's what I'm using)
In the :se.defmacro.c-amplify package, evaluate this from the REPL:

(load-csys-file #p"test-input/test.csys")
(update-system (find-system :core))

You should now have an amplified core.c file that you can examine (and eventually compile, once a lot of quirks have been worked out in c-amplify itself) :)

As always, feel free to leave your comments.

Amplifying C

2010-01-22T17:26:00.009+01:00

On C++

Having programmed in C++ professionally for well over 10 years I have learned all of it. I have all the books, I know all the tricks. And I don’t like it anymore.

Update: This intro apparently made some people see red, because "no man could possibly know all of C++". If that includes you, you can read it as: "I've shipped 4 AAA games on MLOC code bases, and here's my take on the C++ abstractions you can reasonably use in projects that big".

Basically game teams using C++ fall into the same trap every time: they try to create abstractions with whatever is in the C++ toolbox and they fail miserably. On the next project they’re a little bit smarter from the experience so they set out to fix their abstractions and create new ones. And fail.

Quickly going over the major abstraction mechanisms C++ introduced over C I’m arguing that:

Templates suck as they cause link-time spam and compile times to skyrocket. They severely bloat the size of the debug symbol file, which on large projects can easily reach several hundred megabytes of data. Abstractions built with templates perform differently depending on whether compiler optimizations are enabled or not (every tried debugging Boost code?). They’re essentially unusable on large code bases beyond container-of-T and simple functions.
RTTI sucks because it doesn’t do what anyone wants, and you can’t even rely on it returning a type name formatted in a certain way.
Classes suck because their guts have to be in headers for all to see.

All these high-level concepts are flawed and you can’t alter their semantics because they’re set in ISO stone. What all teams do then is to reinvent all the language components that don’t work for them, and sets up rules forbidding the use of the other features. Every C++ shop has its own "accepted" subset.

Basically the C++ game developer community is slowly navigating away from C++'s abstraction patterns. We left operator overloading mostly in the 90’s (some vector libraries still use it). We ditched RTTI back in 2001. Exceptions are firmly off as they don’t even work on all platforms we develop for. A lot of people are advocating that we stop using member functions to reduce coupling.

This may sound harsh, but to me these are clear signs that C++ isn’t providing any real cost benefit for us, and that we should be writing code in other ways.

Coding C

Many C++ game programmers have started to turn towards C (or C-like C++) to get away from the flaws of C++. Targeting C manually with larger systems can be a lot of work, because it offers very basic abstraction facilities. There are functions, enums, tagged types (structs and unions) and a rudimentary type system, but that’s about it.

But let’s look at C as a platform for a minute. C is lean, compiles super fast, it’s supported everywhere and all the tools we need to ship games such as compilers and debuggers (including the obscure and proprietary) work well with it. If you need platform-specific intrinsics to get on with your job, you can rely on the target platform’s C compiler to provide them.

As C is such a simple, predictable language that works everywhere it makes a lot of sense to generate C code. Indeed many projects have done so, but typically the meat of the application has still been written in plain C as code generation is typically used for language interfaces or parser generators.

The Lisp Way

Having also programmed a lot of Common Lisp over the years, I’ve seen how the Lisp family of languages deals with extensibility. In Lisp, you write your own abstractions that become a part of the project’s language. This remarkable feature is enabled basically through two simple things:

Programs can be treated as data (because they can be thought of as parse trees)
There are macros which transform such data (that is, your programs) into other programs (implementing the abstractions).

I’m going to suggest something mildly radical: we should prefer C over C++. But not straight-up C. We should create our own C with the abstractions we need, built right into the language, customized for the problems we’re working on.

Amplification

We can apply many of the ideas that make Lisp powerful to C if we drop its Algol-like syntax. What is the difference between the following two program fragments?

int my_function(int a, int b) {
    return a + b;
}

(defun my-function ((a int) (b int) (return int))
  (return (+ a b))

Answer: none, they are equivalent as far as semantics go. The latter can trivially be parsed (using very simple rules) and transformed into the former, and so it is still the same C program. This is good news, because Lisp has shown us that if we represent programs as data, we can transform that data arbitrarily before evaluating or compiling it.

In my prototype system, c-amplify, I’m doing exactly this. The system introduces an "amplification" phase where s-expressions are transformed to C code before a traditional build system runs.

The c-amplify system has the following major parts:

A system definition facility (specifying input files and dependencies)
A reader, parsing ca source files
A persistent function and type database which is updated as source files are amplified.
A pretty-printing C code generator — important as we’re going to be debugging the generated code.

The system is intended to be run incrementally as source files are changed, re-reading changed files, updating the database and writing generated output. A traditional build system can then be used to the resulting files.

The persistent database is an interesting component that isn’t strictly needed for the system but enables a lot of neat features:

Type inference. Because all functions and types are known, c-amplify can easily supply a type-of operator for arbitrary expressions. This can be used as the basis for type inferring macros similar to auto in C++0x or var in C#.
Hook functions could be installed that run over the database and do additional work. For example, instrumenting all writes to a particular struct field, generating reflection info or performing project-specific checks on how types or functions are used. The possibilities are pretty much endless. Remember all those times you’ve thought: if we could only access this thing in the compiler we could give an error message if the code does this thing? Well, with hooks you could.

RAII, uncluttered

Let’s look at one such macro that solves a real problem: making sure a file handle is closed in an orderly manner, even when there are multiple exit points from the block.

In situations like this, C++ fans can’t wait to tell you about RAII. RAII means creating a stack object of some utility type that performs resource cleanup in its destructor. If we look at the AutoFile type we need to type up to implement RAII we find that exactly one line is providing the abstraction we need (the destructor), the rest is boilerplate:

class AutoFile // auxillary type
{
  private:
    FILE* f;

  public:
    AutoFile(const char* fn, const char* mode) {
      f = fopen(fn, mode);
    }
    ~AutoFile() { if (f) fclose(f); }
    operator FILE*() { return f; }

  private:
    AutoFile(const AutoFile&);
    AutoFile& operator=(const AutoFile&);
};

// later, that same day..
{
   AutoFile file("c:/temp/foo.txt", "w");
   fprintf(file, "Hello, world");
}

What Lisp programmers do to manage resources is to create block-wrapping macros (usually starting with the word with-). The macros sits around a body of code, indicating visually that the code wrapped by the macro will have access to some resource. The macro expansion is guaranteed to clean up the resource regardless of how the block terminates. Here’s an example of using such a macro with c-amplify:

(with-open-file (f "c:/temp/foo.txt" "w")
  (fprintf f "Hello, world"))

If we ask c-amplify to macro-expand this we see that the details of calling fopen and fclose are being handled as if we had written out everything by hand:

{
  FILE* f = (FILE *) 0;
  {
    f = fopen("c:/temp/foo.txt", "w");
    fprintf(f, "Hello, world");
  }
cleanup_8_:
  if (file) {
    fclose(file);
  }
}

Even if we add more complex code with multiple return paths, c-amplify doesn’t let us down:

(defun foo ((return int))
  (with-open-file (f "c:/temp/foo.txt" "w")
    (if (> (rand 10) 5)
       (return 20))
    (fprintf f "Hello, world")
    (return 10)))

This amplifies to the following C code. Note how the with-open-file block locally redefines what it means to return a value. This C code is a close representation of what a C++ compiler has to emit when RAII is used but as before there are no residual types left.

int foo(void)
{
  FILE* f = (FILE *) 0;
  {
    int result_13_;
    {
      f = fopen("c:/temp/foo.txt", "w");
      if (rand(10) > 5) {
        result_13_ = 20;
        goto cleanup_12_;
      }
      fprintf(f, "Hello, world");
      {
        result_13_ = 10;
        goto cleanup_12_;
      }
    }
    cleanup_12_:
    if (f) {
      fclose(f);
    }
    return result_13_;
  }
}

One possible c-amplify implementation of the with-open-file macro looks like this (on a real game project it would of course not use fopen, but some custom file manager):

(def-c-macro with-open-file ((var file-name mode) &body body)
  `(progn
     (declare (,var = (cast (ptr #$FILE) 0)))
     (unwind-protect
          (progn
            (= ,var (#$fopen ,file-name ,mode))
            ,@body)
       (when ,var
         (#$fclose ,var)))))

The funny #$foo syntax is just a reader macro to facilitate reading case sensitive symbols in a special package which corresponds to the C namespace. The implementation piggy-backs on unwind-protect, which makes sure that the body code always goes through the cleanup clauses:

(def-c-macro unwind-protect (form &body cleanup-forms)
  (with-c-gensyms (cleanup result)
    `(progn
       (ast-stmt-if (not (current-defun-void-p))
                    (declare (,result *current-return-type*)))
       (macrolet (return (&optional expr)
                         `(progn
                            (ast-stmt
                             (if (not (current-defun-void-p))
                                 `(= ,',',result ,,expr)
                                 `(cast void ,,expr)))
                            (goto ,',cleanup)))
         ,form)
       (label ,cleanup)
       ,@cleanup-forms
       (return ,result))))

If we decided to add exception handling (through e.g. setjmp or SEH exceptions), we only have to touch unwind-protect to enable exception cleanup in all our RAII-like resource macros. Layering pure compile-time abstractions like this to create programs is incredibly powerful.

Exploiting the database

As I mentioned, there are many advantages to having all your code parsed with type information sitting around in an in-memory database. Let’s highlight one such thing, automatic type inference for local variables. Consider the following c-amplify input:

(defstruct bar
  (x (const restrict volatile ptr int)))

(defstruct foo
  (barp (ptr struct bar)))

(defun my-function ((foop (ptr struct foo)) (return int))
  (let ((xp (-> foop barp x)))
     (return (* xp))))

This amplifies to:

struct bar { int * const volatile restrict x; };

struct foo { struct bar * barp; };

int my_function(struct foo * foop) {
  int * const volatile restrict xp = foop->barp->x;
  return *xp;
}

We can see that the lexical variable xp has the expected type. The c-amplify system knows how to compute the type of any C expression (including arithmetic promotion) so the this feature can be used extensively if desired.

Including what’s needed

Another great feature of having a complete function/type database is that generated C files do not need include statements. If a source file needs a bunch of declarations the generator will just emit them right there. There’s no need to maintain header files. If code in a generated file starts using a structure all of a sudden, a copy of its declaration will automatically pop in to the generated file.

For a full-out implementation of this idea to work, 3rd party declarations from the OS and C libraries must be imported into the amplification database. A separate tool must be devised for this but it would certainly be possible.

Compiling files generated like this would mean the the preprocessor wouldn’t touch disk except to read the input c file. Makefiles for generated files such as these will also be trivial to write as there are no implicit dependencies.

Further ideas

Here are additional ideas that could be explored within the c-amplify system:

Improved compile-time checking for traditionally dangerous functions (scanf, printf) (make macros that evaluate the format strings and types of arguments)
Add exception handling to C on top of setjmp, SEH or some other basic mechanism
Annotate structures for real-time tweaking.
Generate script language bindings at compile time via macros and hooks.
Inlining/code simplification at amplification time (trig function simplification, maths)
Add a proper sublanguage for vector math. Finally you can write that vector math library that combines plus and multiply to madd on altivec by analyzing the code at compile time, and you don’t need 3000 lines of C++ "expression templates" to do it
If you absolutely must have C++-like classes and templates, you could implement those too. Classes with single dispatch would be pretty easy (generate a couple of structs per class), and templates could be "done right" in the sense that you’d only generate a single expansion for each instantiated type and dump them all to a single source file, rather than compiling thousands of instantiations of std::vector and letting the linker sort through the carnage.

Conclusion

If there is a way (no matter how much work it would be) to express the semantics of an abstraction in C, chances are you can implement it as a set of macros and hooks in c-amplify.

However, c-amplify is still a prototype and a lot of work remains before it might be suitable for production use. I hope this rant has given you some new ideas on how we design programs. Send your feedback and flames my way.

Amiga remote launching

2009-04-19T13:29:00.006+02:00

I've been working with TBL on an Amiga production recently. Hardly anyone develops on the real Amiga hardware anymore. A modern PC is nice to develop on, but it's a pain to copy over the program and related test files for every test run.

Well, no more copying! Taking from console development tools from I've crafted a remote command launcher for the Amiga that can run arbitrary programs over a TCP/IP link and channel back file I/O too. You even get the standard output back locally, it's cross-development bliss :)

More details in the Aminet release where you can download the programs for Win32 and Amiga.

ReadyNAS NV+ UPS monitoring

2009-01-22T01:01:00.005+01:00

I just got one of these and a APC Smart-UPS 750 to back it up along with my little version control server at home. The ReadyNAS uses nut so it was pretty easy to make it slave to the Linux server which is polling the UPS status. Unfortunately the ReadyNAS only allows you to specify a master IP, but it works fine if you hardcode the user name, password and UPS name it expects: /etc/nut/upsd.users [monuser] password pass allowfrom = local remote upsmon master /etc/nut/ups.conf [UPS] driver = apcsmart port = /dev/ttyS0 desc = "APC Smart-UPS 750" (Remote above should be configured as an ACL for your LAN.) With these setting it's just a matter of entering your UPS monitoring master's IP in the ReadyNAS configuration frontend and it will connect. A quick battery test shows that the events cascade from the master to the ReadyNAS:

Thu Jan 22 00:57:00 CET 2009	UPS is on line power.
Thu Jan 22 00:56:51 CET 2009	UPS is on battery power.

You even get popups in the frontend!

Fix for the ClearType pixel junk in GVIM

2008-12-04T17:31:00.007+01:00

Update: This doesn't work for fonts that use the right-most column. In fact the issue seems to be cleartype writing outside the leftmost pixel in the bounding box. :-(

Here's a fix for this super-annoying bug (Lucida Console 11, insert spaces before the C to leave a trail of cleartype pixels).

===================================================================
--- gui_w32.c   (revision 1289)
+++ gui_w32.c   (working copy)
@@ -2234,6 +2234,8 @@
         * Note: FillRect() excludes right and bottom of rectangle.
         */
        rc.left = FILL_X(col);
+       if (rc.left > 0)
+           --rc.left;
        rc.top = FILL_Y(row);
 #ifdef FEAT_MBYTE
        if (has_mbyte)

Querying Wow64 registry keys from a 64-bit Python

2008-09-01T23:03:00.003+02:00

KEY_WOW64_32KEY gets the job done

import _winreg

key = None
KEY_WOW64_32KEY = 0x0200

try:
  key = _winreg.OpenKey(_winreg.HKEY_LOCAL_MACHINE, \
    r"SOFTWARE\Microsoft\VisualStudio\9.0", 0, \
    _winreg.KEY_READ | KEY_WOW64_32KEY)
  val, type = _winreg.QueryValueEx(key, "InstallDir")
  print val
except EnvironmentError, ex:
  print ex
finally:
  if key:
    _winreg.CloseKey(key)

Hardware Inventory

2008-02-16T21:40:00.004+01:00

Turning the basement upside down yielded

2 Commodore 64s (old style breadbox, one white and one brown)
2 1541 old-school drives (brown enclosure)
A Commodore 128
A 1541-II drive
An Amiga 500 w/ old-school slow 512 kb expansion memory
TrumpCard SCSI sidecar enclosure for A500
External memory expansion (2 MB) for A500
Power adapters for most of above
Extra floppy drives for Amigas
An Amiga 1200 vanilla
A HP-UX workstation box of unknown origin
A 680x0-based SUN box
Two SGI Octanes
External CD-ROM SCSI enclosures for the SGIs
And a shitload of cables and PSUs

Continuing upstairs:

One dual Opteron server (disconnected)
One Athlon-based generic Linux box (serving)
One desktop box
Another desktop box from el cheapo gear (dell)
A laptop
A fanless mini-server

Update: New addition: Amiga 1200 w/ 060 and an 14" CRT.

hash_map band aid

2007-09-09T00:47:00.001+02:00

Until TR1 is widely available, I'm using this wrapper to construct hash maps using the hash_maps distributed with Visual C++ and GCC. I thought it might be useful for someone else, so here goes.

#if defined(_MSC_VER)
#include <hash_map>
#elif defined(__GNUC__)
#include <ext/hash_map>
#endif

template <typename K> struct default_hash {};

template <> struct default_hash<int> {
 size_t operator()(int v) const
    { return size_t(v); }
};

template <> struct default_hash<unsigned int> {
 size_t operator()(unsigned int v) const
    { return size_t(v); }
};

#if defined(_MSC_VER)

template <
 typename KeyType,
 typename ValueType,
 class HashFun = default_hash<KeyType>
 >
struct HashMapOf
{
 struct Traits
 {
  static const size_t bucket_size = 4;
  static const size_t min_buckets = 8;

  HashFun hasher;

  inline size_t operator()
    (const KeyType& key) const
  {
   return hasher(key);
  }

  inline bool operator()
     (const KeyType& lhs,
      const KeyType& rhs) const
  {
   return lhs < rhs;
  }
 };


 typedef stdext::hash_map<
    KeyType,
    ValueType,
    Traits> Type;
};

#elif defined(__GNUC__)

template <
 typename KeyType,
 typename ValueType,
 class HashFun = default_hash<KeyType>
 >
struct HashMapOf
{
 typedef __gnu_cxx::hash_map<
    KeyType,
    ValueType,
    HashFun> Type;
};

#else
# error Unsupported toolchain.
#endif

Vista and Visual Studio, Oil and Water

2007-02-18T17:32:00.000+01:00

So I've installed Vista (Ultimate, in fact), but Visual Studio 2005 seems like a terrible Vista citizen. In order to run it you need to apply the service pack, but also a beta version of a hotfix package. Even then, Microsoft recommends you run Visual Studio as Administrator. Now, I ask myself: Does compiling source code demand complete access to the entire box? On Vista, that's apparently the case. It seemed to work fine on XP. Now to the most juicy bug of the day. Once you've started a debugging session from within Visual Studio, the target EXE file becomes locked. Closing Visual Studio removes the lock, but the devenv process doesn't hold any handles to the file. What gives? I'm starting to suspect that the SUA services might have something to do with this, so they're uninstalling right now. It's pretty annoying to restart the IDE after each debugging session to be able to recompile. Update I've identified SUA to be the problem. After uninstalling the SDK and removing the windows services it installs, I can recompile and debug again.. For now.

The pleasures of a stable ABI

2007-02-14T20:10:00.000+01:00

As broken as the Win32 API might appear, the thing I really like about it is its stable ABI. That, and the fact that Microsoft spend thousands of hours making sure that old programs work when they release a new version of Windows is worth a lot to me. Solaris has a decent ABI, and I assume most other unices have too. What would it take for Linux to achieve the same level of stability? The Linux kernel does have a fairly stable ABI as long as you say away from the proc file system and device nodes (devfs and whatnot come and go). The C library is also well designed. Most issues with Linux binary (in)compatibility have been in the C++ libraries. The C++ libraries have changed ABIs with each and every version of the compiler, sometimes even breaking with point releases. Breaking the C++ ABI isn't a problem in itself, it happens with the Visual Studio compilers all the time. The real problem is that when deployed, Linux binaries depend on the distribution to include a suitable C++ runtime library to which they can dynamically link, whereas on Windows, programs either carry their C++ runtime with them (pre-VC8) or rely on a separate distributable that can be installed side-by-side in the DLL cache so that a compatible version is always available. For the Battlefield Linux server builds I had this exact problem. I had to use at least GCC 3.x as GCC 2.x was (and still is) a severely outdated compiler without proper namespace support. However, using GCC 3.x meant that people with rented servers that ran older versions of Red Hat were left out in the cold, unless they could find a standard C++ library that would somehow let them run the binary! This was seen as a Bad Thing. The only solution I could think of at the time was to provide a statically linked executable in addition to the regular executable, so that older systems had a hope in hell to run it. That required me to tweak and override certain symbols of the standard library to avoid them from referencing versioned symbols from glibc that weren't present on the target systems, and the whole things was just a terrible mess that took too much time. In the end, linking statically turned out to be somewhat illegal (as we couldn't satisfy the LGPL on that binary) so that option had to be removed. I considered it fair use because there was indeed a dynamically linked executable available as well that did satisfy the LGPL, but it was thought safer to drop it. It would have been so much nicer to ship a C++ library redistributable for x86 and amd64 and let users install it if needed..

ODE, .NET, handles and references from hell

2006-11-27T10:56:00.000+01:00

I've recently toyed around with .NET in C# and I was excited to see that there are .NET bindings for a lot of free game development libraries in the Tao framework. I was especially interested in playing with the ODE bindings. ODE is a free physics and collision library that is starting to become usable for a lot of things. As with many .NET wrappers, the ODE wrapper is just a set of static functions that take System.IntPtr objects. You are supposed to juggle these handles carefully, because they correspond to some real unmanaged object. This is all good, but these APIs break down when the unmanaged objects form graphs on their own, which is the case with the ODE API. Assume we have a wrapper for the following API: public sealed class SomeApi { static IntPtr MakeContainer(); static void DestroyContainer(IntPtr i); static IntPtr MakeItem(); static void DestroyItem(IntPtr i); static void AddItem(IntPtr container, IntPtr item); // Many other functions. } Further, assume that the semantics of a "Container" in the API is that it destroys its contents when it is destroyed. Also assume that we've written our wrapper classes for Container and Item so that they correctly call the corresponding cleanup function in the API when objects are Disposed and finalized. With the prerequisites out of the way, consider this code fragment: Item i = new Item(); Container c = new Container(); c.AddItem(i); What is happening here is that the unmanaged code is forming a reference graph behind the covers, but the available tools for dealing with unmanaged resources can't see such graphs. The .NET process will crash because regardless of whether the item or the container is destroyed/finalized first, the other one still refers to a (now deleted) unmanaged object. Tao's ODE wrapper exhibits these exact problems, making it very hard to reason about code correctness. Essentially I'm finding it much harder to use in C# than in C because not only do I have to deal with my own code, I also have to consider how ODE maintains memory internally at every API invocation and what that does to the validness of my wrapper objects. The only solution I can see is to build wrapper APIs that explicitly maintain the life-time of handles as well. In the above example, such a wrapper would detect that the "AddItem" operation changes the cleanup origin of the item and that it shouldn't be destroyed when the Item wrapper is destroyed, because the container is now doing that. Sigh.

Non-ignorable return codes

2006-06-07T15:46:00.000+02:00

I'd like to have a nonignorable-type that could be used to wrap return values that must be handled, but using an exception would be to heavy-weight. Consider: bool IntersectLineAndPlane(...); I'd like to say nonignorable<bool> IntersectLineAndPlane(...); And then have code that doesn't handle the return value give a compile-time error (or warning) so that mistakes don't slip through into production code. You would think that perhaps something like this would work:

template <typename T>
class nonignorable {
  public:
      nonignorable(const T& v) : value_(v) {}

      // check() does the destruction and extracts the value
      friend T check(const nonignorable<T>&);

 private:
     ~nonignorable();
};

This could be used as:

nonignorable<bool> Function() {
 return nonignorable(false);
}

And in client code: if (!check(Function)) { /* take action */ } Alas, this will not work, because there are more destructions going on when the nonignorable instance is returned on the stack. I think the only way to solve this is to rely on the new C++0x proposition to add move semantics into the language so that there is only one destruction (in the check() template function).

Mixing Scheme and C

2006-03-17T21:48:00.000+01:00

In my quest to find the perfect Scheme/C mix I've found that Bigloo Scheme really goes a long way to overcome the language barriers. The cool part is that Bigloo compiles to efficient C code, and you can influence the generated code in a number of ways. For example, it's possible to include headers and declare functions with type annotations straight in the Scheme source code. Since the Scheme files are translated to C when compiled, there's no marshalling to consider. I'm assuming that annotated procedures yield a very low overhead compared to Python which requires a object allocations for everything (even integers). Using Bigloo with DLLs symbols on windows has one quirk though, the symbols must be imported as macros, and the header file with _declspec() crud must be included explicitly. This does the trick:

(module my-module
        (extern
          (include "include/mydll.h")
          (macro simple::int (::int) "simple")))

Given these declarations, you can call the function simple as if it were a Scheme procedure, which is awesome. When compiled, the resulting executable links properly to the DLL. I haven't found a tool that can produce these annotations automatically, but writing one should be trivial. I'm slightly confused about how to make a stringent build system for a combined Scheme/C project, but I'm sure it's possible. Armed with such a build tool it might actually become fun to program again..

Reducing boilerplate by embedding XSLT

2006-02-14T21:01:00.000+01:00

I've recently been working on an custom IDL compiler that can target Python and C++. Think COM, only portable between platforms and targeted towards a select few languages. A lot of patterns immediately appear in both the frontend and backends of the compiler that's just boilerplate work. Consider the classic implementation of an IDL parser (or any programming language parser, for that matter):

Parse the input, building an abstract syntax tree of the declarations.
Build a type graph and interconnect the type nodes so that types can be resolved.
Resolve all type references (using fixups or in a separate pass if forward references allowed.)
Invoke one or more backends if the resulting tree is valid.

The backends in turn will walk the tree (via some variation of the Visitor pattern) and produce output. This quickly becomes repetitive and mundane work. Visitor is well known for it's strong impact on code coupling and strong binding between entities. In another sandbox project of mine I tried out a completely different approach. Instead of writing yet another AST hierarchy to interface the frontend I experimented with XML as an intermediate format in the compiler itself. Given an input file, my LALR parser will essentially emit a well-formed XML document using the DOM APIs. This in itself doesn't buy much, but it provides tremendous flexibility down the road. Think of it as capturing the entire AST in a portable format. Indeed, the GCC project has recently added a AST-to-XML converter as part of their (excellent) compiler frontend so more people are thinking along these lines. With the AST swimming around in an XML DOM tree, it becomes possible to rewrite repetitive and boring tasks in XML query tools that are designed for those jobs rather than a general-purpose programming language such as C++. Whipping up flexible type resolvers, type and syntax checkers using a decent XSLT processor is a lot of fun, and it can be done with a surprisingly small amount of XSLT code. XQuery processors can easily build statistics and metrics with a minimal amount of code. Another interesting thing about keeping the AST in XML is that it becomes trivial to add whatever meta-data you like in a matter of seconds. That data can travel through the filters (for example in an XML namespace of its own) all the way to the backend, where it can be used to tweak the output. Also, changing the XML AST doesn't require recompiling hundreds of AST classes! The key concept to making this work is pipelining, which is a common design pattern anyway in compilers. Connecting the output of one XSLT processing filter to the input of the next nicely captures the pipelining pattern while at the same time enforcing the idea that one piece of code should have a single, well-defined purpose. XSLT also works wonders for code generation backends, because it designed for transforming data, something C++, Java and Python simply aren't. So what are the drawbacks? Simply put: speed and memory consumption. Clearly, a hand-written implementation of say a type resolver will have a lower memory consumption and better processing speed than a XSLT-based implementation. Also, while XSLT is a very useful language (especially with version 2) it's not very strong with error reporting or string handling, to name a few areas. If you're willing to strike a deal with the portability devil and settle on a single XSLT library it's possible to work around most of these problems. Given the prototyping advantages I still think this is a viable implementation strategy for compiler projects.