pja.name

Signed Distance Field File Format?

2025-08-06T00:00:00+00:00

I’ve never really gone very deep into graphics or rendering, but I’ve long been quite fascinated by the use of signed distance fields for defining geometry and implicit surfaces more generally. Like many people, I found out about this through Inigo Quilez’s work and Shadertoy in particular. A long time ago I did spend some time playing with it. I’d like to create more if I find the time / inspiration.

What I like most about SDFs for defining geometry is that simple geometry can be expressed simply. A sphere is defined with just a couple of mathematical operations:

float sphere(vec3 p, float r)
{
  return length(p) - r;
}

Compare this to regular triangle meshes where you can’t even define an exact sphere and trying to approximate it requires a huge number of vertices. This is not too difficult to define programmatically, but you are essentially forced to use authoring tools to deal with the complexity of defining geometry, no matter how simple. Many times when I’ve been prototyping game ideas, I’ve been frustrated that I’m forced to open up Blender just to create the most trivial piece of geometry.

What I’d really like is just some textual format for defining geometry similar to how you do it with SDF. OpenSCAD is there for CSG, but as far as I can tell you can’t do anything like smooth unions or domain transformations, which are needed for more organic-looking geometry. Using pure shader code is ok for this, but with shapes being represented as functions, transformations really need a language that supports first class functions (an SDF is a function of ℝ³→ℝ, then a union transformation is (ℝ³→ℝ)→(ℝ³→ℝ)→(ℝ³→ℝ)).

Finally, with LLMs in the picture, as cool as Blender MCP is, it would be nice if the LLM could just spit out a textual scene format. I tend to agree with Carmack here:

LLM assistants are going to be a good forcing function to make sure all app features are accessible from a textual interface as well as a gui. Yes, a strong enough AI can drive a gui, but it makes so much more sense to just make the gui a wrapper around a command line interface…
— John Carmack (@ID_AA_Carmack) December 31, 2024

To that end, I started playing around with an idea of an SDF-based file format. As far as I can find, there isn’t really anything like this (which was quite surprising!). Would be interested to know if something like this exists.

The basic idea is that you can define shapes textually via simple primitives, transformations, and operations:

# Define sphere at origin, and rotated cube.
shape s = sphere(radius: 2);
shape b = box(width: 3, height: 3, depth: 3) |> rotate(x: 100, y: 200, z: 100);

# Translate and then combine via smooth union.
# As the last expression in the file, this is the output shape.
smooth_union(
  s |> translate(x: -1, y: 0, z: 0),
  b |> translate(x: 1, y: 0, z: 0),
  k: 1.0
);

This file defines the shape. I haven’t put a lot of thought into syntax yet, but the shape type here actually is an SDF, and we have primitives such as sphere and box as leaf nodes and higher-order SDFs such as translate and smooth_union for transformations.

With geometry defined this way, you can then render via a simple tool that understands how to parse the format. The tool does basic parsing and semantic analysis producing a runtime data model that supports querying the field at any coordinate. The tool also supports rendering using basic raymarching (its only function right now).

sdftool demo.sdf -o demo.png

This produces:

Since we have an analytical shape, we can also extract normals via tetrahedron technique.

sdftool demo.sdf -o normals.png --render-mode normal

If we need a mesh, we can generate one (currently using marching cubes with basic QEM simplification):

sdftool demo.sdf -o mesh.obj --mesh

With this language in place, I can quite easily generate non-trivial meshes purely with text such as a chess pawn with smooth curves:

shape base = cylinder(radius: 1.4, height: 0.35) |> color(0.4, 0.35, 0.33);
shape base_rim = cylinder(radius: 1.2, height: 0.15) |> translate(y: 0.45);
shape stem = cylinder(radius: 0.36, height: 2.4) |> translate(y: 1.5);
shape mid_stem = cylinder(radius: 0.7, height: 1.4) |> translate(y: 0.5);
shape collar = cylinder(radius: 0.78, height: 0.01) |> translate(y: 2.7) |> expand(0.04);
shape head = sphere(radius: 0.7) |> translate(y: 3.5);

shape base_assembly = smooth_union(base, base_rim, k: 0.1);
shape mid = smooth_union(base_assembly, mid_stem, k: 0.4);
shape lower_pawn = smooth_union(mid, stem, k: 0.5);
shape pawn_collar = smooth_union(lower_pawn, collar, k: 0.1);
shape pawn = smooth_union(pawn_collar, head, k: 0.30);

translate(pawn, y: -2.5);

Another benefit of this format is size: the raw text for this pawn mesh is just 757 bytes, and this is without any attempt at compression. Could easily be under 100 bytes with minimal effort. The mesh by comparison is a few hundred kilobytes.

Of course, there are downsides to SDFs: rendering SDFs directly is still very expensive and complex geometry may end up being extremely difficult to model this way.

There are some future directions I’d like to take this:

A runtime library could load the file and support an API for evaluating the field at points, or raymarching.
The library could also allow creating the data format in memory at runtime.
Build more scaffolding to allow LLMs to create geometry from a prompt.
Support approaches to texturing.
And of course, improved algorithms for mesh generation and rendering.

Will continue tinkering on this and if it proves useful will maybe open source.

D and Garbage Collection

2025-01-21T00:00:00+00:00

I’ve been getting back into a bit of D programming recently and catching up on what’s been happening in the community. Some things have changed (Andrei isn’t around any more), but most things have stayed the same. Walter is still around and the language has a small and loyal following. DConf is still happening every year and people are still shipping things.

It is significantly smaller than both Rust and Go though. I think this is a real shame since I do feel that D fits a niche of languages that give you systems level access with quite powerful features around expressiveness and generally pleasant (and familiar) syntax. By comparison, I find Rust a bit too opinionated on how it should be written (yes, the borrow checker) and while Go is pleasant, it’s not very powerful when it comes to setting up scalable abstractions. D fits the gap quite nicely (while having problems of its own).

A perennial problem that D seems to have is that it can’t quite decide what it wants to be, and as a result tries to please everyone. As an example, D has always had a GC, but you get a subset of devs that really want to avoid the GC (for legitimate reasons). As a result, a long time ago, D added the @nogc attribute to functions, which statically checks if the function may allocate memory. The idea is that you can wrap your latency sensitive code (e.g. a game’s update loop) in @nogc and then rest assured that you will avoid GC pauses.

// Simple @nogc function - this compiles fine
@nogc int add(int a, int b) {
    return a + b;
}

// This won't compile - array literals allocate
@nogc int[] getNumbers() {
    return [1, 2, 3];
}

On the surface, @nogc is fine, but now you have a problem with what to do with common libraries: do they use the GC, avoid the GC, or provide the option of GC/no-GC? Whatever you choose, you are not going to win: either deal with endless complexity of supporting both, or make one camp unhappy.

I was not a fan when @nogc was originally proposed and I still think it was a mistake. I should mention that as a game developer, I do often want to avoid the GC!

I’d much prefer that D did not implement @nogc and instead:

Provide runtime tooling that helps you find GC allocations.
Try to avoid GC as much as possible in the standard library.
Continue to provide language features / utilities to avoid GC when needed.
Continue to invest in improving the GC pause times.

If you are a fan of @nogc, I’d further offer some other observations:

If you care about minimising pauses in your application, GC is only one source of those. You have to also avoid any sort of non-wait-free locks or concurrent data structures / blocking syscalls / pauses from reference counted deallocation cascades.
Modern GC implementations can get those pauses down <1ms (see Go as proof of life). This tech continues to improve, so it is a good bet.
You can achieve 99% of the desired outcome via runtime tooling (logging on each GC allocation). I’ve done a lot of work in Unity3D to avoid GC in C#. Yes, it does take some effort to track down those allocations and fix them, but really the work is not that different from fixing compilation errors from @nogc, and you have the option of just ignoring the GCs that happen on the rare paths that you don’t really care about.

All this being said, @nogc has shipped and I would never advocate for breaking existing code. However, there are active discussions going on about a “Phobos 3” and I would suggest that the approach is to go all-in and assume GC. Standard containers should just use GC unapologetically (but responsibly). There’s nothing stopping someone from creating an allocator-based container library and putting it on dub, but it doesn’t need to be in the standard library.

I continue to believe that D has its place in the set of useful and unique programming languages and really ought to have more usage. Complicating the language / compiler / libraries in order to try and make everyone happy I think goes against the pragmatism embodied by D and just stretches already thin contributor resources. Stay simple, choose a 90% solution over 100%, and focus on quality of what’s already there.

unique_ptr Type Erasure

2017-01-28T00:00:00+00:00

Often when building APIs we’d like the caller to provide some information in a format, or using a protocol defined by the library. For example, we might want access to a contiguous buffer specified by a (void*, size_t) pair.

void cool_feature(void* buffer, size_t len);

An API like this is fine if the buffer will be read synchonously, but sometimes we need asynchronous access. This introduces a lifetime problem: how does the caller know when it can free the buffer?

A common way to solve this is to provide a callback that will be invoked once the processing has completed:

void cool_feature(void* buffer, size_t len, void (*done)(void*));

Here, done will be called with buffer once cool_feature has asynchonously finished its work.

This works most of the time, but has a couple of problems:

You need to remember to call done in all cases.
It only works if done only needs to be called with the buffer pointer. What if my buffer is part of a larger object?

struct Object {
  // ...
  std::string buffer;
  // ...
};

void do_stuff(std::unique_ptr<Object> obj) {
  cool_feature(obj.buffer.data(), obj.buffer.size(), ???);
}

There’s no obvious choice of function to pass in. We want to free obj once buffer processing is done, but we’ll be given a pointer to the string data, not obj.

A possible solution is to pass in an std::function<void()> as the callback, so that obj can be captured and destroyed as necessary. This works, but std::function has difficulty with move-only types, and there’s no guarantees that a capturing std::function won’t allocate memory.

We could, of course, define another interface (maybe call it ContiguousBufferProvider), but this also requires an extra memory allocation.

A little trick we can do to handle most of the common cases is to pass in a type-erased context to the function.

using Context = std::unique_ptr<void*, void(*)(void*)>;

void cool_feature(void* buffer, size_t len, Context context);

The context is essentially an extra piece of baggage that must be carried around until the buffer has been processed. Once processed, we just drop the context and it cleans up after itself.

We can also benefit from an extra function that converts any object into a Context through type erasure:

template <typename T>
void deleter(void* p) {
  delete static_cast<T*>(p);
}

template <typename T>
Context erase_type(std::unique_ptr<T> p) {
  return Context(static_cast<void*>(p.release()), &deleter<T>);
}

With this, the Object example is easy to solve:

void do_stuff(std::unique_ptr<Object> obj) {
  cool_feature(
      obj.buffer.data(),
      obj.buffer.size(),
      erase_type(std::move(obj));
}

This guarantees no extra memory allocations, and cool_feature just needs to drop the context once finished.

There are probably more general ways to solve this, but I like this approach as it is clean, simple, and solves all the problems I’ve encountered so far.

The Condenser Part 1

2014-12-14T00:00:00+00:00

Last night I rewatched Joe Armstrong’s excellent keynote from this year’s Strange Loop conference. He begins the talk with a fairly standard, but humorous lament about the sorry state of software, then goes on to relate this to some physical quantities and limits. He finishes by suggesting some possible directions we can look to improve things.

One of his suggestions is to build something called “The Condenser”, which is a program that takes all programs in the world, and condenses them down in such a way that all redundancy is removed. He breaks this task down into two parts:

He also explains the obvious, and easy way to do Part 1.

At this point I remembered that I hadn’t written a lot of D recently, and although Joe is talking about condensing all files in the world, I was kind of curious how much duplication there was just on my laptop. How many precious bytes am I wasting?

It turns out that The Condenser Part 1 is very easy to write in D, and even quite elegant.

import std.algorithm;
import std.digest.sha;
import std.file;
import std.parallelism;
import std.stdio;
import std.typecons;

auto process(DirEntry e) {
  ubyte[4 << 10] buf = void;  // 4kb buffer, uninitialized
  auto sha1 = File(e.name).byChunk(buf[]).digest!SHA1;
  return tuple(e.name, sha1, e.size);
}

void main(string[] args) {
  string[ubyte[20]] hash2file;  // hash table of SHA1 -> filename
  auto files = dirEntries(args[1], SpanMode.depth, false)
               .filter!(e => e.isFile);
  foreach (t; taskPool.map!(process)(files)) {
    if (string* original = t[1] in hash2file) {
      writefln("%s %s duplicates %s", t[2], t[0], *original);
    } else {
      hash2file[t[1]] = t[0];
    }
  }
}

I’ll explain the code a little, starting from main. The files variable uses dirEntries and filter to produce a list of files (the filter is necessary since dirEntries also returns directories). dirEntries is a lazy range, so the directories are only iterated as necessary. Similarly, filter creates another lazy range, which removes non-file entries.

The foreach loop corresponds to Joe’s do loop. While I could have just iterated over files directly, I instead iterate over a taskPool.map, a semi-lazy map from David Simcha’s std.parallelism that does the processing in parallel on multiple threads. It is semi-lazy because it eagerly takes a chunk of elements at a time from the front of the range, processes them in parallel, then returns them back to the caller to consume. The task pool size defaults to the number of CPU cores on your machine, but this can be configured.

The process function is where the hashing is done. It takes a DirEntry, allocates an uninitialized (= void) 4kb buffer on the stack and uses that buffer to read the file 4kb at a time and build up the SHA1. Again, byChunk returns a lazy range, and digest!SHA1 consumes it. Lazy ranges are very common in idiomatic D, especially in these kinds of stream processing type applications. It’s worth getting familiar with the common ranges in std.algorithm and std.range.

I ran the program over my laptop’s home directory. Since the duplicate file sizes are all in the first column, I can just use awk to sum them up and find the total waste:

$ sudo ./the-condenser . | awk '{s+=$1} END {print s}'
2347353793

That’s 2.18Gb of duplicate files, which is around 10% of my home dir.

In some cases the duplicates are just files that I have absentmindedly downloaded twice. In other cases it’s duplicate music that I have both in iTunes and Google Play. For some reason, the game Left 4 Dead 2 seems to have a lot of duplicate audio files.

So, in theory, I could save 10% by deduplicating all these files, but it’s not a massive amount of waste. It doesn’t seem worth the effort trying to fix this. Perhaps it would be nice for the OS or file system to solve this automatically, but the implementation would be tricky, and still maybe not worth it.

Part 2 of the Condenser is to merge all similar files using least compression difference. This is decidedly more difficult, since it relies on near-perfect compression, which is apparently an AI-hard problem. Unfortunately, solving AI is out of scope for this post, so I’ll leave that for another time :-)

Cube Vertex Numbering

2014-04-27T00:00:00+00:00

If you do any sort of graphics, physics, or 3D programming in general then at some point you are going to be working with cubes, and at some point you are going to need to assign a number to each vertex in those cubes. Usually this is because you need to store them in an array, or maybe you are labelling the children of an octree, but often you just need some consistent way of identifying vertices.

For whatever reason, a surprisingly common way of numbering vertices is like this, with the bottom vertices numbered in counter-clockwise order followed by the top vertices in counter-clockwise order (warning, incoming ASCII art):

        7-------6
       /|      /|
      4-+-----5 | 
      | |     | |   y
      | 3-----+-2   | z
      |/      |/    |/
      0-------1     +--x

Depending on what you are doing, there’s generally only a few applications of the numbering system:

Converting a number to a coordinate.
Converting a coordinate to a number.
Enumerating adjacent vertex numbers.

Unfortunately, this common numbering scheme makes none of these tasks easy, and you have no choice but to produce tables of coordinates and adjacency lists for each vertex number. This is tedious, error-prone, and completely unnecessary.

Here is a better scheme:

        3-------7
       /|      /|
      2-+-----6 | 
      | |     | |   y
      | 1-----+-5   | z
      |/      |/    |/
      0-------4     +--x

This numbering uses the Lexicographic Ordering of the vertices, with 0 being the lexicographically first vertex, and 7 being the last.

Number (decimal)	Number (binary)	Coordinate
0	000	0, 0, 0
1	001	0, 0, 1
2	010	0, 1, 0
3	011	0, 1, 1
4	100	1, 0, 0
5	101	1, 0, 1
6	110	1, 1, 0
7	111	1, 1, 1

I’ve included the binary representation of the vertex number in table above, because it illuminates the key property of this scheme: the coordinate of a vertex is equal to the binary representation its vertex number.

\[ \begin{aligned} coordinate(n) &= ((n \gg 2) \mathrel{\&} 1, (n \gg 1) \mathrel{\&} 1, (n \gg 0) \mathrel{\&} 1) \\ number(x, y, z) &= (x \ll 2) \mathrel{|} (y \ll 1) \mathrel{|} (z \ll 0) \end{aligned} \]

(Of course, the zero shifts are unnecessary, but I’ve added them to highlight the symmetry.)

This numbering scheme also makes adjacent vertex enumeration easy. As an adjacent vertex is just a vertex that differs along one axis, we just need to flip each bit using XOR to get the adjacent vertices:

\[ \begin{aligned} adj_x(n) &= n \oplus 100_2 \\ adj_y(n) &= n \oplus 010_2 \\ adj_z(n) &= n \oplus 001_2 \end{aligned} \]

It should be clear that this numbering scheme trivially extends into higher dimension hypercubes by simply using more bits in the representation, and extending the formulae in obvious ways.

So there you have it. Whenever you are looking to number things and aren’t sure what order to use, start with lexicographic. It usually has nice encoding and enumeration properties, and if not then it is probably no worse than any other ordering.

Range-Based Graph Search in D

2014-01-09T00:00:00+00:00

I’ve just made my first commit of a range-based graph library for D. At the moment it only contains a few basic search algorithms (DFS, BFS, Dijsktra, and A*), but I wanted to write a bit about the design of the library, and how you can use it.

As a bit of a teaser, the snippet below shows how you can use the library to solve those word change puzzles (you know, the ones when you have to get from one word to another by only changing one letter at a time?)

string[] words = File("/usr/share/dict/words")
                 .byLine
                 .filter!(w => w.length == 5)
                 .map!"a.idup"
                 .array();
enum string start = "hello";
enum string end = "world";
static d(string a, string b) { return zip(a, b).count!"a[0] != a[1]"; }
auto graph = implicitGraph!(string, u => words.filter!(v => d(u, v) == 1));
graph.aStarSearch!(v => d(v, end))(start).find(end).path.writeln();

This promptly produces the desired result:

["hello", "hollo", "holly", "molly", "mouly", "mould", "would", "world"]

The last two lines are the interesting part. The first of those lines defines our graph as an implicit graph of words connected by one-letter changes. The second line performs the A* search and writes the resultant path to stdout.

On the second-last line, graph is defined as an implicitGraph. An implicit graph is a graph that is represented by functions rather than in-memory data structures. Instead of having an array of adjacency lists, we just define a function that returns a range of adjacent words (that’s the second parameter to implicitGraph). This representation saves us the tedium of generating the graph beforehand, and saves your RAM from having to store it unnecessarily. It also makes for succinct graph definitions!

The last line is where the algorithm is called. Unlike most other graph libraries, stdex.graph implements graph searches as ranges – iterations of the graph vertices. aStarSearch returns a range of vertices in the order they would be visited by the A* search algorithm (parameterized by the A* heuristic). By implementing the search as a range, the user can take advantage of Phobos’ multitude of range algorithms.

For instance, suppose you want to count the number of nodes searched by the algorithm until it reaches the target node. For this task, you can just use countUntil from std.algorithm.

auto search = graph.aStarSearch!(v => d(v, end))(start);
writefln("%d nodes visited", search.countUntil(end));

For tuning and debugging, it might be useful to print out the nodes visited by the algorithm as it runs.

foreach (node; search.until(end))
    writeln(node);

When no path is available, graph search algorithms typically end up searching the entire vertex space. It is common to cut-off the search after a certain threshold of nodes have been searched. This can be accomplished by takeing only so many nodes from the search.

auto result = search.take(50).find(end);
if (result.empty)
    writeln("Not found within 50 nodes");

Similarly, you could have the search continue until 10 seconds have elapsed.

alias now = TickDuration.currSystemTick;
auto t = now;
auto result = search.until!(_ => (now - t).seconds > 10).find(end);
if (result.empty)
    writeln("Not found in 10 seconds");

The beauty of all this is that none of these features are part of the graph library – they come for free as a side-effect of being a range.

One unsolved part of the design for the graph searches is how to handle visitation. The Boost Graph Library solves this by having users implement a visitor object, which has to define a suite of callback methods, one for each event (vertex discovered, examine edge, etc.) This is certainly mimicable in D, but it may be more effective to model visitation with output ranges, which would again allow composition with existing Phobos constructs. This is what I will be investigating next.

Ranges Part 1 - Basics

2013-06-16T00:00:00+00:00

Iteration is one of the most common activities in programming. Few programming tasks can be accomplished without looping or recursing over some set of values, whether it be a stream of bytes from a file, elements of an array, rows in a database, or nodes in an implicitly generated graph. Programs need to iterate, and programming languages need to provide idioms for iteration.

In D, iteration is achieved through the use of ranges. Broadly speaking, a range defines a sequence of values. There are many styles of ranges. For example, some ranges lazily generate their values instead of iterating over data; some ranges are infinite; some ranges can be iterated from both ends; and some ranges allow you to jump around to any index (like arrays). For the most part, the details of how a particular range operates is up to the range implementor.

So how do you implement a range? At the most basic level, a range is just a type with three member functions: front, empty, and popFront.

front returns the value from the front of the range.
empty returns true if the range has been exhausted.
popFront removes the first value from the range.

As a simple example, here is a range that counts from 0 to ‘n’.

struct Iota
{
    private int m_current = 0;
    private int m_target;

    this(int n) { m_target = n; }
    @property int front() { return m_current; }
    @property bool empty() { return m_current == m_target; }
    void popFront() { m_current++; }
}

(The name Iota is a Greek letter. In a tradition started by the programming language APL, it is used to represent consecutive integers in several languages)

Notice that there is no need to inherit from any sort of IRange interface. There’s nothing magic about ranges, they are just simple types with those functions defined.

To iterate over a range, you can manually call those functions using a for loop, or use the built-in foreach loop in D, which knows about ranges.

void main()
{
    import std.stdio;
    foreach (x; Iota(10))
        writeln(x);
}

As expected, this will print out the numbers 0 through 9, one per line. Of course, writeln knows about ranges too, so writeln(Iota(10)) works as well, and will print out [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], formatted like an array.

Writing functions that work with ranges is not difficult. Suppose we want to write a function to count the number of elements in a range. This can be achieved by accepting the range as a template parameter and iterating the range using popFront() explicitly, like so:

size_t count(Range)(Range r)
{
    size_t n = 0;
    while (!r.empty)
    {
        ++n;
        r.popFront();
    }
    return n;
}

unittest
{
    assert(count(Iota(10)) == 10);
}

By using templates, we can create range types that are templated on other range types. For example, consider a skip range that skips every second element in another range. You could define it like this:

struct Skip(Range)
{
    private Range m_range;

    this(Range r) { m_range = r; }

    // front and empty just forward to the sub-range.
    @property auto ref front() { return m_range.front; }
    @property bool empty() { return m_range.empty; }

    // popFront also forwards to the sub-range, but pops off two
    // elements at a time, instead of one.
    void popFront()
    {
        m_range.popFront();
        if (!m_range.empty)
            m_range.popFront();
    }
}

We can then use Skip in conjunction with Iota to skip through consecutive integers.

void main()
{
    import std.stdio;
    writeln(Skip!Iota(Iota(10))); // [0, 2, 4, 6, 8]
}

Notice that we have to redundantly specify Iota as a template parameter to Skip. This is because D doesn’t currently support type inference for template type constructors. A common workaround is to create a module-level function that wraps the constructor:

auto skip(Range)(Range r) { return Skip!Range(r); }
auto iota(int n) { return Iota(n); }

We can then use these like so:

writeln(iota(10).skip());

The above code also makes use of another D feature: uniform function call syntax, which basically means f(x) can be written as x.f() as if f were a member function of x. If you come from the C# world, you can kind of think of it as every free function being an Extension Method. We could have also written 10.iota().skip() or just plain skip(iota(10)). There’s no difference, so choose whatever you think is most readable.

The ability to combine arbitrary ranges is perhaps their most powerful feature. There’s no reason we need to stop at combining just two ranges:

writeln(iota(10)); // [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
writeln(iota(10).skip()); // [0, 2, 4, 6, 8];
writeln(iota(10).skip().skip()); // [0, 4, 8];
writeln(iota(10).skip().skip().skip()); // [0, 8];

It shouldn’t be hard to imagine the kind of flexibility and expressiveness that can be achieved once you have a large vocabulary of ranges at your disposal.

In Part 2 we’ll look at some of the different categories of ranges.

DustMite - Code Minimizer

2013-06-13T00:00:00+00:00

Yesterday I discovered DustMite, a source code minimizer tool for D.

What’s a source code minimizer? It’s a program that takes some source code, and automatically removes lines, or even whole files from the source while maintaining some invariant (e.g. it still builds, or still gives a particular output). The usual use case is to produce a minimal reproduction test case for a bug, which is exactly what I used it for.

I had a problem in a medium-sized D project where anytime I had some sort of compile-time error, such as a typo in a variable name, DMD (the D compiler), would spew out pages and pages of false errors, triggered by some other module in my codebase. The errors were completely irrelevant. This was quite annoying because it made it difficult to see the actual error. So, like a good programmer, I decided to file a bug report.

Step one in filing a good bug report is to create a minimal test case. I tried to do this manually by pulling out what seemed to be the relevant parts of the code that would reproduce the error, but I couldn’t get it to happen. I could easily and consistently reproduce the bug in the full codebase, but the project is about 10,000 lines of code, so minimizing it manually from there would be very time consuming.

I’d heard about DustMite on the forums, so I thought I’d give it a go.

Installing was easy enough.

% git clone https://github.com/CyberShadow/DustMite.git
% cd DustMite
% dmd dustmite.d dsplit.d
% ln -s ~/DustMite/dustmite ~/bin

Next step was to prepare the project for minification. All you need to do is make a full copy of the codebase, and remove any unnecessary files (e.g. object files, data files – anything not needed for reproduction).

Next you need to devise a test command. This is a command that should return 0 if the bug is still present, and non-zero otherwise. For example, suppose we had this (trivial) program:

import std.stdio;
import std.string;

string world() { return "world!"; }

void main()
{
	write(hello());
	write(", ");
	write(world());
	write("\n");
}

I’ve got an obvious bug here in that hello() is undefined. Trying to compile this gives Error: undefined identifier hello. If we wanted to minimize this then we need a command, which, when run, will return 0.

Compiling and greping for the error would be perfect for this.

% dmd test.d 2>&1 | grep -q "undefined identifier hello"
% echo $?
0

This runs the compiler (dmd test.d), redirects the error messages to stdout (2>&1) then pipes the result (|) to grep, which searches for that string without producing output (-q = quiet). grep returns 0 if it finds anything, and 1 otherwise.

The DustMite wiki provides a list of useful test scripts.

Finally, we just run DustMite with that test command.

% dustmite testdir 'dmd test.d 2>&1 | grep -q "undefined identifier
hello"'
None => Yes
############### ITERATION 0 ################
[  0.0%] Remove [] => No
[  1.6%] Remove [0] => No (cached)
[  3.3%] Remove [01] => No
...
[ 82.4%] Remove [000001] => No (cached)
[ 88.2%] Remove [000000] => No (cached)
[ 94.1%] Remove [0000000] => No (cached)
Done in 36 tests and 10 secs and 165 ms; reduced version is in
testdir.reduced

And checking testdir.reduced/test.d confirms that the source has been reduced.

% cd testdir.reduced
% cat test.d
void main()
{
hello;
}

For my project, DustMite took 8 minutes, and reduced roughly 10,000 lines of code down to about 10, and perfectly reproduced the issue. The problem I was having trying to reproduce manually was that the repro required that you pass the files in a specific order to the compiler, and it also required an extra file that seemingly has nothing to do with the issue. I don’t think I would have ever minimized it without DustMite.

D Tip - Skipping main() for Unit Tests

2013-06-11T00:00:00+00:00

When you compile a D program with unit tests enabled (using the -unittest flag), the generated executable will first run the unit tests then continue with executing main().

Sometimes, you just want the unit tests to run in isolation.

A simple way to skip execution of main() for unit test builds is to use the unittest version identifier:

unittest
{
    assert(1 + 1 == 2, "Something horrible has gone wrong.");
}

void main()
{
    version(unittest)
        return;

    // This won't be run
}

Code inside the version(unittest) block will only be run when the code is compiled with -unittest, so the code above will exit main() immediately in unit test builds.

There are numerous pre-defined version identifiers, which you can find at http://dlang.org/version.html. Another handy one is version(assert), which is only compiled in when asserts are enabled.

Associative Array Indexing

2013-05-27T00:00:00+00:00

I dislike how associative array indexing is handled in every language I know. In all cases it handled inconsistently with other parts of the language, and in all cases the inconsistency is unnecessary.

There’s two aspects of handling associative arrays that vary among languages:

Does array[key] automatically insert a value if the key isn’t present?
Do operations on array[key] have “magic” compiler support?

To illustrate these differences, here’s how things are handled in C++ and D.

C++

std::map<std::string, int> days;
days["Mon"] = 1;
std::cout << days["Tue"] << std::endl;

int[string] days;
days["Mon"] = 1;
writeln(days["Tue"]);

In C++, array[key] always returns a valid lvalue, whether the key was in the array or not. If the key was not in the array then a default-constructed value is added, so days["Tue"] defaults to 0.

In D, array[key] will return an lvalue only if key was in the array. However, the syntax array[key] = value is given magic compiler treatment, and is converted into a special opIndexAssign operator, which is a combination of indexing and assignment. The attempt to access days["Tue"] results in a range violation.

C++ answers ‘yes’ and ‘no’ to questions 1 and 2, and D answers ‘no’ and ‘yes’. As far as I’m aware, all modern languages follow either the C++ or D approach. For example, Ruby follows C++ and Python follows D.

Now I’ll explain why both of these approaches are bad.

Automatically inserting a default value when the key is present is bad because it is inconsistent with how normal, non-associative arrays work.

std::vector<std::string> days;
days[1] = "Mon"; // ERROR

Arrays don’t automatically expand their domain on indexing, so why should associative arrays? Aren’t arrays just a optimisation of an associative array where the key is a bounded integer? They should have the same semantics.

And the reason the D approach is bad is because it messes with your intuition about how expressions work. If I see an indexing operation and an assignment operation then I expect the AST to have two operation nodes, not one. This has some interesting consequences:

void set(ref int x, int y) { x = y; }

int[string] days;
days["Mon"] = 1;    // Okay
days["Tue"].set(2); // Error?

Intuitively, this should work. set is no different from the int assignment operator, so I would expect that I can replace all int assignments with calls to set. I can’t, only because of the compiler magic.

In my opinion, the correct approach is to disallow implicit insertions, and also avoid any compiler magic. Indexing should be an error when the key isn’t present (just like it is in an array), and if you want to expand the domain of an associative array then you should need to use a specific operation to do that (array.insert would be the obvious choice).

A likely complaint about this approach would be that you can’t write the three-line word count program, i.e.:

int[string] wc;
foreach (word; words)
    wc[word]++;

Under my suggested approach, this program would become:

int[string] wc;
foreach (word; words)
    if (word in wc)
    	wc[word]++;
    else
    	wc.insert(word, 1);

Yes, it’s longer, and no, I don’t think it’s an issue, nor do I think it is an argument for implicit insertions or magic. If shorter programs are a sound argument for inconsistent semantics then we’re in a lot of trouble. Besides, it wouldn’t be hard to introduce a lookup function where you can provide a default value if the key is missing.

int[string] wc;
foreach (word; words)
    wc.lookup(word, 0)++;

That’s it. Language designers, don’t throw away consistency for the sake of terseness – it’s not worth it!

Simplest Image Format

2013-01-29T00:00:00+00:00

Just a quick post to share something I discovered a few days ago: the simplest image format ever. I’m actually quite surprised it took me so long to find it, which is why I’m sharing now.

The format I’m talking about is the Portable Pixmap Format (.ppm). It’s so simple to write that it’s easier to describe using code:

// --------------------------------------------------------------------
//     file - the file to write to
//    width - width of the image in pixels
//   height - height of the image in pixels
// rgb_data - the image data, 3 bytes per pixel (R, G, B)
// --------------------------------------------------------------------
void write_ppm(FILE* file, int width, int height, void* rgb_data)
{
    fprintf(file, "P6 %d %d 255\n", width, height);
    fwrite(rgb_data, 1, 3 * width * height, file);
}

That’s it: a small header followed by the raw image data.

It’s incredibly useful to have a simple file format like this when you want to write out some images at runtime and don’t have any other image writing libraries available (or can’t be bothered hooking them up).

D Tip - Beware Narrow Strings

2012-12-22T00:00:00+00:00

In The D Programming Language, strings are arrays. They are literally aliases to arrays of immutable characters of various width, defined in druntime.

alias immutable(char)[]  string;
alias immutable(wchar)[] wstring;
alias immutable(dchar)[] dstring;

All string types in D express Unicode strings using different encodings. string uses UTF-8, wstring uses UTF-16, and dstring uses UTF-32. With the exception of UTF-32, these encodings are variable length encodings. A single “character” may be represented by a variable number of array elements. These string types are called “narrow strings”.

Variable length encoding is very space efficient, but at the cost of indexing. With string and wstring there is no way to retrieve the n’th character in O(1) time. When you use array indexing on narrow strings, you are actually indexing into the code units. For example, the string “こんにちは世界” has 7 code points (characters), but 21 code units. .length will report 21, and the element at index 0 is the code unit 227, which is not こ!

string s = "こんにちは世界";
writeln(s[0] == 'こ'); // false
writeln(s.length); // 21

As you can see, this behaviour isn’t much use when you want to work with the actual characters. The Phobos developers are aware of this, which is why, when you treat strings as ranges, they do what you would expect.

string s = "こんにちは世界";
writeln(s.front == 'こ'); // true
writeln(s.walkLength); // 7

This puts D programmers in a slightly unusual position. Narrow strings are both arrays of code units, and ranges of code points, depending on how you use them. When writing generic code, you need to be aware of this because it has some quite unintuitive consequences:

T[] is not always a range of T

For example, string (immutable(char)[]) is a range of dchar, not char. typeof("abc".front) is dchar. If you want to store the result of .front then you can use ElementType!R (or just use auto).

hasSlicing!T[] is not always true

The hasSlicing!R trait from std.range is true when R is sliceable. For strings, it returns false because they are only sliceable as arrays of code units.

hasLength!T[] is not always true

Similarly to above, hasLength!R is true when you can get the length of R in O(1) time. For strings, it is false because you can only the get the number of code units in O(1) time, not code points. walkLength on narrow strings runs in O(n) time.

With a T[], you can’t call .popFront() .length times

.length returns the number of code units, but .popFront() pops off a code point, which may be more than one code unit.

In short, try to avoid using arrays directly in generic code. Write your code to use arbitrary ranges, and add the necessary template constraints when you want to use array features:

For indexing, check isRandomAccessRange!R.
For slicing, check hasSlicing!R.
For .length, check hasLength!R.

If you follow those rules, your generic code should handle narrow strings just fine.

Using D Without The GC

2012-12-15T00:00:00+00:00

One of the major selling points of the D Programming Language is its “native efficiency”. I use the scare quotes because while D compilers do compile down to native machine code, your program will only run efficiently if you code with performance in mind!

In D, the easiest way to degrade performance (besides poor algorithms) is overuse of automatic memory managment. No matter what language you use, memory allocation is non-trivial, and has a non-trivial cost to go with it. With D’s automatic memory management, you not only incur the cost of allocation, but also the cost of automatic deallocation, i.e. garbage collection. If you want high throughput and low latency then you really need to avoid memory allocation as much as possible.

The most important thing to understand about the GC is that it can only run when you try to allocate. Unfortunately D doesn’t make it obvious when you are allocating memory, so I’ve listed the most common ways here.

Things That Allocate in D

Before I start, I should make it clear that these are things that could allocate in D. A good optimiser may be able to remove some of the allocations. When in doubt, test.

new

Any time you use the new keyword, you are allocating memory. Avoid creating class instances frequently, and use structs where possible.

Array literals

In most cases, array literals will allocate.

immutable int[3] a = [1, 2, 3];  // Won't allocate
immutable int[] b = [1, 2, 3];   // Will allocate once
int[] c = [1, 2, 3];             // Will allocate
int[3] d = [1, 2, 3];            // Will allocate
foo([1, 2, 3]);                  // Will allocate

The fact that the initialisation of d allocates may be surprising. It doesn’t need to, but DMD currently doesn’t do the optimisation to remove the allocation. In the meantime, you can do this:

immutable int[3] a = [1, 2, 3];  // Won't allocate
int[3] b = a;                    // Won't allocate

Calling dup or idup on an array will also lead to an allocation.

Array concatenation

Array concatenation won’t always result in an allocation, as arrays are sometimes over-allocated, but if you want to avoid allocations then it is best to avoid array concatenation. Modifying the .length property of an array could also cause allocation.

Associative arrays

Creating, adding, or removing elements from an associative array could cause an allocation. Lookups are safe.

Closures

A closure is a function reference that needs extra context beyond the stack. An example should illustrate this:

int delegate() foo(int x) { return () => x; }
int delegate() bar(int x) { return () => 1; }

Here, foo returns a closure because the returned function relies on the value of x, which will no longer be on the stack after foo returns. bar, on the other hand, does not return a closure, because the function () => 1 has no dependency on x.

In D, creating a closure allocates memory, i.e. every time you call foo you will allocate memory.

Detecting Allocations

The easiest way to detect unexpected allocations is to add some logging to the D runtime. Clone that project, and open up src/gc/gc.d. In there, there’s some functions with names like gc_malloc, gc_calloc, etc. Just add some calls to printf there, and build.

Style

When you try to avoid using the GC, you might find that your usual style of programming doesn’t work very well. If you are used to just building up arrays using concatenation, joining strings together, and creating lots of temporary objects then you’re going to have a hard time.

In general, to avoid these dynamic allocations, you need to make your program more static. Static arrays in particular are your friend. You’ll have to build hard limits into your code, and just “allocate” within those limits.

Using strings can be quite tricky when you want to avoid allocations. string in D is an alias for immutable(char)[], which is fine when you know what your string needs to contain beforehand, but if you want to create a string based on runtime data then you’ll need to build it up inside a char[N], which has no legal conversion to immutable(char)[].

To get around the string problem, you can use assumeUnique. This is a simple function that does nothing more than cast a mutable array to an immutable array. The caveat is that the cast is only safe if the reference is truly unique. Once you have built up your string in the mutable array, and casted using assumeUnique, you can’t safely use the mutable array again. This shouldn’t be a problem, but it’s something to be aware of.

char[16] buf;
snprintf(buf.ptr, buf.length, "1 + 1 = %d", 1 + 1);
string str = assumeUnique(buf[]);

Conclusion

While D was designed with GC use in mind, the language also provides all the necessary abstraction facilities to build usable “GC free” libraries (templates, aliases, delegates, static arrays). It can take a while to get used to not using the GC, but I certainly don’t feel hindered by its absence.

D Tip - Testing with TypeTuple

2012-11-18T00:00:00+00:00

When testing a function, it’s usually a good idea to test it with a range of different inputs. To do this, you can easily use a for loop over an array of input values, but what if your input is a type, as it often is with template code?

The D Programming Language allows you to iterate over a TypeTuple, so all you need to do is declare a tuple of all the types you want to test, and iterate over them in the normal way:

import std.typetuple;
alias TypeTuple!(int, long, double) Types;
foreach (T; Types)
    test!T();

You might wonder what this compiles to. After all, the body of the loop varies with T, so the generated code must also vary on each iteration. How does the compiler handle this?

The answer is that the loop is completely unrolled. The code above is literally the same as:

test!int();
test!long();
test!double();

For this reason, you might want to keep an eye on the size of your TypeTuples, to avoid code bloat.

Pythagorean Polygons - Part 2

2012-09-14T00:00:00+00:00

In my last post I showed how to solve the Project Euler problem, Pythagorean Polygons for N = 60 in under a minute. In this post I’ll show how to solve it for the target N = 120, and in under a second.

Our current algorithm uses a brute force depth first search, memoized using the generic Phobos memoize template. One common way to speed up searches is to prune branches that have no possibility of reaching the goal. In this problem, we can prune a search when the distance to the goal is greater than the remaining perimeter:

long dfs(int x, int y, int d, int i)
{
    import std.functional;
    alias memoize!dfs mdfs;

    if (x == 0 && y == 0 && d > 0) return 1;

    // Recurse
    long result = 0;
    foreach (int k; i..cast(int)vs.length)
        if (!(d == vs[k].d && x == -vs[k].x && y == -vs[k].y))
        {
            int nx = x + vs[k].x;  // new X
            int ny = y + vs[k].y;  // new Y
            int nd = d + vs[k].d;  // new used perimeter
            int rd = N - nd;       // remaining perimeter
            if (nx * nx + ny * ny <= rd * rd && rd >= 0)
                result += mdfs(nx, ny, nd, next(k));
        }
    return result;
}

This alone speed up the N = 60 solution to under 2 seconds, and gives us the solution to N = 120 in just over 2 minutes.

We can do better.

In the N = 120 case, the memoization cache uses up roughly 200MB of memory. This is much larger than my L2 cache, and since hash maps distribute elements randomly, we’ll be spending a lot of time going out to memory checking the memoization cache. Reducing memory usage and improving lookup patterns should help performance significantly.

One observation we can make is that dfs(..., i) always calls dfs(..., next(i)). If we change the algorithm from a top-down memoization algorithm to a bottom-up dynamic programming algorithm, then we could do the depth-first search backwards, in layers of different values of i. We start by computing dfs(..., vs.length-1) for all x, y, and d. That gives us everything we need to compute all of dfs(..., prev(vs.length-1)).

prev is just the opposite function to next – it returns the index j, previous to i such that vs[i] is not colinear with vs[j].

int prev(int i)
{
    // Find next, non-colinear edge
    int j = i - 1;
    while (j >= 0 && colinear(vs[i], vs[j]))
        --j;
    return j;
}

Since we aren’t going to be caching all of dfs anymore, we’ll get rid of the memoization and instead just use a big array as our cache. We’ll also need two of them: one for the previously computed layer of i, and one for the next layer that is being computed.

alias long[N+1][N+1][N+1] DP; // cache
DP[] dp = new DP[2];
dp[0][M][M][0] = 1; // start point
int r = 0, w = 1; // read index, write index

Here, dp[r] stores the previously computed layer. dp[r][M+x][M+y][d] represents the number of paths of length d from (0, 0) to (x, y) using the only the triples from the previous layers. Using dp[r] we compute dp[w] by using the next layer down from what dp[r] used. To do this, we start by copying all of dp[r] into dp[w] and then simply iterate over all x, y, and d, as well as all colinear edges in the current layer.

The algorithm looks something like this:

for (int i = cast(int)vs.length - 1; i >= 0; )
{
    dp[w] = dp[r];    // copy previous buffer
    auto j = prev(i); // colinear edges from j..i

    foreach (x; -M..M+1)
    foreach (y; -M..M+1)
    foreach (d; 0..N+1)
        if (dp[r][M+x][M+y][d] > 0)
            for (int k = i; k > j; --k)
                if (!(d == vs[k].d && x == -vs[k].x && y == -vs[k].y))
                {
                    int nx = x + vs[k].x;
                    int ny = y + vs[k].y;
                    int nd = d + vs[k].d;
                    int rd = N - nd;
                    if (nx * nx + ny * ny <= rd * rd && rd >= 0)
                        dp[w][M+nx][M+ny][nd] += dp[r][M+x][M+y][d];
                }

    i = j;       // move to next layer
    swap(r, w);  // swap read/write buffers
}

Once all this has run for each layer, dp[r] will contain the final path counts for each (x, y, d) tuple. All that’s left to do is count up the number of paths that reach back to (0, 0) (dp[r][M][M][...]).

alias reduce!("a + b") sum;
long total = sum(dp[r][M][M][1..N+1]);
writeln(total);

With this improvement, the N = 120 case now runs in just over 1 second, which is easily fast enough for us to be satisfied, but there’s much more that can be done.

Like many geometrical problems, Pythagorean Polygons has a symmetry to it that can be exploited for speed. Notice that we generate the Pythagorean triplets redundantly from all quadrants. If (3, 4) is a triplet, then so is (-3, 4), (3, -4), (-3, 4), (4, 3), (-4, 3), (4, -3), and (-4, -3). What this also means is that if there is a path from (0, 0) to (x, y, d) then there are also paths to (-x, y, d), (x, -y, d) etc. but we compute all of these redundantly!

Taking full advantage of the symmetry is tricky, but there’s one simple way that can speed up our algorithm up significantly. Notice that the first half of triplets travel upwards, and the second half travel downwards (due to the sort). This means our algorithm calculates all paths down to some point (x, y, d) using the second half of the triplets, then calculates all paths from there back to (0, 0) using the second half of the triplets. But we know from the symmetry that if there is a path to (x, y, d) using the first half then there is a path back to (0, 0) using the second half. In fact, there are the same number of paths, so the total unique paths is equal to the product of all combinations where the total distance is less than N.

To implement this, we only need to make one simple change, and add a combining step. The change is to modify the main loop to only use the first half of the triplets, i.e.

for (int i = cast(int)vs.length - 1; i >= 0; )

becomes

for (int i = cast(int)vs.length / 2 - 1; i >= 0; )

Next, instead of just summing up the dp[r][M][M][1..N] entries, we need to sum up the path products. To do this, we iterate over all (x, y, d) tuples and then multiply the cache value with those for (x, y, d2) where d2 <= N - d.

long total = 0;
foreach (x; -M..M+1)
foreach (y; -M..M+1)
foreach (d; 1..N+1)
    if (dp[r][M+x][M+y][d] > 0)
        foreach (d2; 0..N+1-d)
            total += dp[r][M+x][M+y][d] * dp[r][M+x][M+y][d2];
total -= vs.length / 2;

That last line needs some explanation. Previously our algorithm accounted for paths with only two edges, but we don’t do that anymore, so they will be included in the totals. What that line of code does is remove those paths from the total. That value is vs.length / 2 because every edge (dx, dy) has a corresponding edge (-dx, -dy) that will be included, so the total of these two-edge paths is equal to half the triplets.

With this improvement, the N = 120 case gives the solution in 0.36 seconds, which is more than fast enough for my liking. The other axes of symmetry can be exploited further, but I’ll leave that as an exercise for the reader :-)

Pythagorean Polygons - Part 1

2012-09-08T00:00:00+00:00

It’s been a while since I solved any coding problems, so I’ve decided to re-solve a Project Euler problem that I looked at years ago: Pythagorean Polygons. Back then I used C++, but this time I’ll use the D programming language :-)

In summary, the problem is to find the number of distinct convex polygons with vertices on integer coordinates, integer length sides, and a perimeter less than or equal to 120. The name of the problem comes from the fact that the edges are the hypotenuses of Pythagorean triples.

The brute force method is quite simple:

Generate all the Pythagorean triples (x, y, d) with d < 120.
Do a depth first search on the integer lattice from (0, 0) to (0, 0), using the triples as your edges, ensuring that you always turn anti-clockwise (or always clockwise).

Generating the Pythagorean triples is easy enough:

enum N = 120;    // Maximum perimeter
enum M = N / 2;  // Maximum edge length

struct V { int x, y, d; }
V[] vs;

foreach (dx; -M..M+1)
    foreach (dy; -M..M+1)
        foreach (dd; 1..M+1)
            if (dx * dx + dy * dy == dd * dd)
                vs ~= V(dx, dy, dd);

It will also help to have them in anti-clockwise order.

double arg(V v)
{
    import std.math;
    return atan2(cast(real)v.y, cast(real)v.x);
}

import std.algorithm;
sort!((a, b) => arg(a) < arg(b))(vs);

Our triples are likely to contain several colinear edges. So we’ll need a way of avoiding those:

bool colinear(V a, V b)
{
    // a and b are colinear if a.x / a.y == b.x / b.y
    // We can avoid the division by multiplying out.
    return a.x * b.y == a.y * b.x;
}

int next(int i)
{
    // Find next, non-colinear edge
    int j = i + 1;
    while (j < vs.length && colinear(vs[i], vs[j]))
        ++j;
    return j;
}

Now all that’s left is to do the depth-first search. I’m just going to use simple recursion to implement it, just to save code.

// Returns number of paths from (x, y) to (0, 0) using less
// than d perimeter length, and only using edges with
// index >= i (to ensure convexity).
long dfs(int x, int y, int d, int i)
{
    if (d > N) return 0; // Perimeter too long
    if (x == 0 && y == 0 && d > 0) return 1;

    // Iterate edges, add them on, and recurse.
    long total = 0;
    foreach (int k; i..cast(int)vs.length)
        if (!(d == vs[k].d && x == -vs[k].x && y == -vs[k].y))
            total += dfs(x + vs[k].x, y + vs[k].y, d + vs[k].d, next(k));
    return total;
}

The if-condition inside the loop is to protect against degenerate polygons with two edges e.g. (0, 0), (60, 0), (0, 0), and the use of next ensures that we don’t use two colinear edges in a row, as this is disallowed in the problem.

Finally, we need to call it with the starting position:

import std.stdio;
writeln(dfs(0, 0, 0, 0));

If we change N to 30, we can test it using the given solutions in the problem.

% dmd -inline -O -release p292
% time ./p292
3655

Great. That matches with the solution and runs in under 2 seconds on my laptop. Unforunately, trying it with N = 60 took just shy of 50 minutes.

The problem with this is that the branching factor of the search is equal to the number of triples (hundreds) and the depth exponent is large enough to make the running time impractical for larger N. We need a way to speed it up.

Let’s look at the signature of dfs.

long dfs(int x, int y, int d, int i)

What’s the domain of each input?

x and y will be from -60 to 60.
d will be between 0 and 120.
i will be between 0 and the number of triples (448).

That gives us a maximum of 121 x 121 x 121 x 448 possible inputs. Since dfs is a pure function, that means we can memoize the results and re-use them for subsequent recursive calls. It’s a large number, but now the running time is polynomial rather than exponential, so it will scale better.

Fortunately, D’s standard library, Phobos, provides a memoize template just for this purpose. With a couple of quick modifications to dfs, we can memoize it.

long dfs(int x, int y, int d, int i)
{
    import std.functional;
    alias memoize!dfs mdfs;

    // ...
            total += mdfs(x + vs[k].x, y + vs[k].y, d + vs[k].d, next(k));
    // ...
}

We just introduce an alias for the memoized version of the function, and change the recursive call to use that version instead. Internally, memoize just maintains a hashtable of input tuples to outputs, so it’s quite fast.

With these changes, the N = 60 version is reduced from 50 minutes to 42 seconds. Unfortunately, N = 120 is still just out of reach. It will likely run in under an hour if you have enough memory, but we’d like it to run a lot faster than that.

In the next post, I’ll show how we can get N = 120 running in sub-second times.

A Better Assert for D

2012-09-02T00:00:00+00:00

Like C and C++, the D programming language provides an assert mechanism that allows you to check conditions at runtime, and halt execution if the condition fails. You can optionally print out a error if you’re in a particularly good mood.

float log(float x)
{
    assert(x > 0.0f, "Argument to log must be positive.");
    ...
}

Trying to call log(-1) will give you an error at runtime.

core.exception.AssertError@test.d(3): Argument to log must be positive.

In this example, I know that the argument was -1, but what if the argument was the result of some long calculation? It would be nice to know what was actually passed into log. Typically, D programmers will use std.string.format for this purpose:

float log(float x)
{
    import std.string : format;
    assert(x > 0.0f, format("Argument must be positive (x = %f).", x));
    ...
}

This solves the problem, but has a couple of issues:

You need to import std.string.format.
The call to format is a bit ugly.

Granted, these are relatively minor issues, but it would be nice if we could simply write:

float log(float x)
{
    assert(x > 0.0f, "Argument must be positive (x = %f).", x);
    ...
}

C and C++ programmers typically work around this by using some clever macros, but D doesn’t have a pre-processor, so we’ll need to use standard functions.

Here’s a first attempt:

void assertf(Args...)(bool test, Args args)
{
    import std.string : format;
    assert(test, format(args));
}

float log(float x)
{
    assertf(x > 0.0f, "Argument must be positive (x = %f).", x);
    ...
}

This works, giving the error:

core.exception.AssertError@test.d(4): Argument must be positive (x = -1).

Notice however, that the file and line number are of the assert inside assertf rather than log. This is less than ideal.

Fortunately, D has a tricky little feature designed just for this. D defines a couple of keywords, __FILE__ and __LINE__ that statically evaluate to the file name, and line number of the locations of those keywords respectively. Furthermore, if you use those keywords as default arguments to a function then you get the file name and line number of the calling function. For example:

void getInfo(string file = __FILE__, int line = __LINE__)
{
    import std.stdio;
    writeln(file, " : ", line);
}

// test.d
void main()
{
    getInfo(); // test.d : 10
    getInfo(); // test.d : 11
}

This is exactly what we need. There’s just one problem: you can’t put default arguments after variadic parameters; the compiler can’t figure out whether the last arguments refer to the variadic parameters or the optional parameters.

The way to work around this is to make the file and line template parameters, that way they can be automatically deduced, and the user won’t need to specify them manually.

void assertf(string file = __FILE__, int line = __LINE__, Args...)
            (bool test, Args args)
{
    import std.string : format;
    import core.exception : AssertError;
    if (!test)
    {
    	throw new AssertError(format(args), file, line);
    }
}

Our function is working as expected now, but suffers a major, obvious flaw: it works in -release builds.

While D provides a standard way to detect -debug builds (using the debug keyword), there is currently no standard way to detect builds where an assert should fire.

I say “currently” because I have requested the feature, and as of DMD 2.061, you’ll be able to write:

version(assert) if (!test)
{
    throw new AssertError(format(args), file, line);
}

This is conditionally compile the test only in builds where asserts are meant to fire, similar to how we can currently use version(unittest) to detect unit testing builds.

The final remaining difference between our function and the built-in assert is the evaluation strategy. When asserts are compiled out of your build, not only does the assert do nothing, but the arguments aren’t even evaluated. For example:

assert(printf("Hello, world") > 0);

In -release builds, this will print out nothing, however the analgous call to our formatting assert will still print out.

The way to work around this is to use lazy evaluation.

void assertf(string file = __FILE__, int line = __LINE__, Args...)
            (lazy bool test, lazy Args args)
{
    import std.string : format;
    import core.exception : AssertError;
    version(assert) if (!test)
    {
        throw new AssertError(format(args), file, line);
    }
}

Note the addition of the lazy storage class in the parameter list. This tells the compiler to not evaluate the arguments until they are used, and since the arguments will not be used in -release builds, they will not be evluated, solving the final issue with our formatted assert.

That’s it! Remember, version(assert) won’t work until DMD 2.061 (or unless you get HEAD from git). Until then, you could either just leave it in all builds, or use debug to enable it only in -debug builds.

Generating Variable Frequency Waves

2012-08-17T00:00:00+00:00

I’ve been playing around with some simple digital signal processing recently – generating PCM streams and playing them back with OpenAL. The first thing I tried was a simple sine wave. Coding this up is easy enough:

uint sampleRate = 16000;
uint numSamples = sampleRate * 10;
double[] samples = new double[numSamples];
double freq = 440;
foreach (i; 0..numSamples)
{
    double t = cast(double) i / sampleRate;
    samples[i] = sin(2 * PI * freq * t);
}

How about a wave whose frequency oscillates up and down, like a siren? Just oscillate the freq, right?

freq = 440 + 100 * sin(2 * PI * t);
samples[i] = sin(2 * PI * freq * t);

Looks good, but if you play that back, you’ll notice that something’s wrong. The frequency goes up and down, but much more than expected, and at unexpected rates.

What’s wrong? The problem is the in the 2 * PI * freq * t.

It’s easy to see why this is wrong by considering a different frequency function. Suppose we had instead:

freq = 440 / t;
samples[i] = sin(2 * PI * freq * t);

If you substitute freq into the sin argument, the ts will cancel out, leaving the argument – and whole expression – as a constant, which is not going to produce a wave of any form.

The problem is that the argument to sin should be the current phase. When the frequency is constant (like in the first code snippet) the current phase is given by freq * t, but in general the phase is:

\[ \int_0^t \! f(t) \, \mathrm{d} t. \]

where \( f(t) \) is the frequency as a function of time.

When you are generating a discrete-time waves, the integral becomes a sum. We can realise this in code by using what’s called a phase accumulator.

double phase = 0;
double dt = 1.0 / sampleRate; // time between samples
foreach (i; 0..numSamples)
{
    samples[i] = sin(2 * PI * phase); // use accumulated phase

    double t = cast(double) i / sampleRate;
    freq = 440 + 100 * sin(2 * PI * t);
    phase += freq * dt; // accumulate phase
}

As you can see, the phase accumulator simply adds up the frequency multiplied by the delta time. You might recognise this as an Euler integrator.

Using this method, you can vary the frequency however you like, even in discontinuous ways, and still get a nice smooth sine wave.

Derivation of Smoothstep

2012-08-11T00:00:00+00:00

Here’s the formula for smoothstep: \[ f(t) = 3t^2 - 2t^3 \] but where does that come from?

Oddly, when you search for “derivation of smoothstep”, none of the results are able to answer that question. So here’s my contribution to the Internet: a simple derivation of smoothstep. (To be honest, I just want an excuse to test out MathJax on my blog).

Here’s what smoothstep looks like:

So, to start, what are we actually looking for? What are the requirements of smoothstep? Well, it starts at 0 when t is 0 and ends at 1 when t is 1, and at both those points the curve is flat, i.e. the derivative is zero. Formally:

\[ \begin{aligned} f(0) &= 0 \\ f(1) &= 1 \\ f'(0) &= 0 \\ f'(1) &= 0 \end{aligned} \]

That’s a good start, but there’s infinite functions that satisfy those equations. We need to restrict ourselves further. One way to do that would be to assume that the solution is a polynomial, and since there are two points where the derivative is zero we might as well assume a 3-degree polynomial (in general, a n-degree polynomial has at most n-1 critical points i.e points where the derivative is zero).

\[ f(t) = at^3 + bt^2 + ct + d \]

and the derivative is

\[ f'(t) = 3at^2 + 2bt + c \]

Substituting in the values from our formal requirements gives us a nice system of linear equations:

\[ \begin{aligned} f(0) = 0 &\implies d = 0 \\ f(1) = 1 &\implies a + b + c = 1 \\ f'(0) = 0 &\implies c = 0 \\ f'(1) = 0 &\implies 3a + 2b = 0 \end{aligned} \]

Solving that system of equations (manual elimination of variables is the simplest way here) gives:

\[ a = -2, b = 3, c = 0, d = 0 \]

Et voila! Plugging those back into the original polynomial gives us smoothstep.

Linking Frameworks With DMD

2012-06-01T00:00:00+00:00

Little tip for OS X D Programming Language users: if you want to link with frameworks, the correct flags for dmd are:

dmd -L-framework -LCoreFoundation test.d

This goes in general for any linker flags with arguments, because dmd uses -Xlinker to pass the arguments to ld.

D's Conservatism

2012-05-27T00:00:00+00:00

The D Programming Language is still my current favourite programming language, but I’m really starting to dislike its conservatism in several areas. It’s great that D tends to take the safe approach to many problems, but often it is at the expense of expressiveness, and to make matters worse, there’s often no workaround.

One example of this conservatism is with static constructors and destructors. Static constructors are per-module functions that are run on thread initialisation and static destructors are run on thread shutdown. The purpose of these is to initialise and deinitialise global data.

The problem with static constructors and destructors is that you cannot use them with cyclic imports. For example:

module A;
import B;

int x;
static this()
{
    x = 1;
}

module B;
import A;

int y;
static this()
{
    y = 2;
}

This will compile fine, but if you try to run it, you will get an error:

Cycle detected between modules with ctors/dtors:
A -> B -> A
object.Exception@src/rt/minfo.d(331): Aborting!

The reason this is disallowed is because your static constructor could assume that any imported module’s static constructor has already been run. If there are cycles in the imports then there is no order to run the static constructors that would allow this assumption, so D disallows it altogether.

The problem is that in this case, there is no cyclic dependency – it doesn’t matter what order the constructors are run, but D disallows it anyway. D is being conservative against my will and now I’ll have to refactor my code just to please the compiler.

D’s type system also exhibits similar conservatism. const/immutable, shared, and pure all provide their guarantees by conservatively disallowing anything that could possibly break those guarantees, regardless if they actually do.

For example, it’s not possible to create a pure function that uses a global store to do caching because pure functions aren’t allowed to read or modify global state.

With const and immutable, you are forced to use physical constness, which is a subset of logical constness. This means that you can’t do things like lazy initialisation of data members within a const “getter” function, or cache the result of a const function.

D disallows these for a good reason: multithreaded code requires physical constness in order to avoid data races. The problem is that now interfaces will be requiring const functions even when there is no intention for them to be multithreaded. For physical constness to work, interfaces should only require it when concurrency is intended.

These issues have all been raised on the forums, but it all seems to be ignored. Fortunately it’s fairly easy to avoid these issues by not using the type constructors at all, and avoiding much of the standard library. Hopefully, useful functions like std.algorithm.sort won’t start requiring pure functions as predicates.

Holism

2012-05-13T00:00:00+00:00

Here’s some SSE code to normalize a 3-vector:

; vector in xmm0
movaps  xmm2,   xmm0
mulps   xmm0,   xmm0
movaps  xmm1,   xmm0
shufps  xmm0,   xmm0,   _MM_SHUFFLE (2, 1, 0, 3)
addps   xmm1,   xmm0
movaps  xmm0,   xmm1
shufps  xmm1,   xmm1,   _MM_SHUFFLE (1, 0, 3, 2)
addps   xmm0,   xmm1
rsqrtps xmm0,   xmm0
mulps   xmm0,   xmm2

Here’s some SSE code to normalize four 3-vectors:

; x's in xmm0, y's in xmm1, z's in xmm2
movaps  xmm3,   xmm0
movaps  xmm4,   xmm1
movaps  xmm5,   xmm2
mulps   xmm0,   xmm0
mulps   xmm1,   xmm1
mulps   xmm2,   xmm2
addps   xmm0,   xmm1
addps   xmm0,   xmm2
rsqrtps xmm0,   xmm0
mulps   xmm3,   xmm0
mulps   xmm4,   xmm0
mulps   xmm5,   xmm0
; x's in xmm3, y's in xmm4, z's in xmm5

As you’ve no doubt noticed, normalizing four vectors in the right format is just about as fast as normalizing one vector.

This is nothing new. It’s fairly well known that using structure of arrays opens up more optimization opportunities than arrays of structures.

The interesting thing here is that there is no API with a function called normalize(vec3 v) that can take advantage of this. There is no way to break down the problem of normalizing four vectors in a way that recombining the parts is as efficient as the whole.

Holism is the idea that systems should be viewed as wholes rather than the sum of their parts. The opposite of Holism is Reductionism. A Reductionist, when presented with the problem of normalizing 100 vectors would first find a way to normalize one vector, then apply that 100 times. A Holist would see the problem as a whole, and realize that the normalizations can be done in parallel. The Reductionist would use the first code snippet. The Holist would use the second.

I like this quote from Stepanov on the subject:

It is essential to know what can be done effectively before you can start your design. Every programmer has been taught about the importance of top-down design. While it is possible that the original software engineering considerations behind it were sound, it came to signify something quite nonsensical: the idea that one can design abstract interfaces without a deep understanding of how the implementations are supposed to work. It is impossible to design an interface to a data structure without knowing both the details of its implementation and details of its use. The first task of good programmers is to know many specific algorithms and data structures. Only then they can attempt to design a coherent system. Start with useful pieces of code. After all, abstractions are just a tool for organizing concrete code.

If I were using top-down design to design an airplane, I would quickly decompose it into three significant parts: the lifting device, the landing device and the horizontal motion device. Then I would assign three different teams to work on these devices. I doubt that the device would ever fly. Fortunately, neither Orville nor Wilbur Wright attended college and, therefore, never took a course on software engineering. The point I am trying to make is that in order to be a good software designer you need to have a large set of different techniques at your fingertips. You need to know many different low-level things and understand how they interact.

I think the take-away point here is that you should consider your problem as a whole before you begin breaking it down into smaller parts. It’s tempting to start creating a separate class for every noun in your application domain, but more often than not there is a better design involving a more holistic approach.

Imagine C++ Without Function Overloading

2012-04-29T00:00:00+00:00

I’ve spent quite a lot of time in the D programming language community, and one thing I’ve noticed is that people are very quick to suggest new features, but rarely do people suggest to remove a feature (unless it is outright broken). It’s easy to see the benefits of adding to a language, but the costs are often harder to see, or are simply ignored.

For a bit of fun, this post will explore the benefits of removing a useful feature from C++: function overloading.

Quick recap: function overloading is a feature of C++ that allows you to have two functions with the same name that vary only on their parameters. In C, you would to name your functions differently, e.g. with min and fmin.

int min(int x, int y) { return x < y ? x : y; }
float fmin(float x, float y) { return x < y ? x : y; }

int a = min(1, 2);
float b = fmin(1.0f, 2.0f);

In C++, you give them the same name, and the version is chosen based on parameters.

int min(int x, int y) { return x < y ? x : y; }
float min(float x, float y) { return x < y ? x : y; }

int a = min(1, 2);
float b = min(1.0f, 2.0f);

In C, you could use macros as a hacky form of overloading, and in C++ you could use templates, but I’ll ignore those for the moment.

One clear advantage to overloading is that you don’t need to name your functions differently if they do the same things, but on different types. It makes things easier to remember and arguably makes the intent of your code clearer. It also means that you can change the types of your arguments (e.g. changing from float to double) without having to go around changing all your function names. It can also help with generic programming.

I’m sure there are other benefits, but those are the main ones. Now let’s go through the costs.

The first cost is the cost of name mangling. In C, since there can only be one function for a given name, the symbol assigned to that function is just the name of the function. In C++, two functions can have the same name, but they need to have different symbols, so C++ compilers must mangle the names to include the parameter type information.

Using g++, the two C++ min functions above mangle to __Z3minii and __Z3minff. Those are quite simple examples. Things get more nasty when more intricate types are involved. For example the std::sort of an std::deque<std::pair<int,int>> mangles to __ZSt4sortISt15_Deque_iteratorISt4pairIffERS2_PS2_EEvT_S6_.

Why does this matter? It matters if you have to look at call stacks, or object dumps, or care about the size of your debug files. Many tools handle common C++ name mangling schemes, but this is extra work for the tool developers. It also doesn’t help that every compiler mangles names differently, which is why you can rarely link code generated by two different C++ compilers.

Without function overloading, there would be no need to mangle the parameter types into the symbol name.

Another cost of function overloading is the quality of compile time errors. If I try to call min(1, 2.0f) in C++, I will get an error because it cannot figure out whether I want to call the int version or the float version. The only way to express my intent is to cast one of the arguments min(1, (int)2.0f). Without funcition overloading, if I want to call the int version, I call min, and if I want to call the float version, I call fmin.

Having no direct way to specify what overload I want to use has other consequences. Suppose I want to get the address of one of the overloads because I want to use it as a parameter to a higher-order function.

int a[] = {3, 2, 5, 1, 4};
int amin = std::accumulate(a, a + 5, a[0], &min); // get the min

// ERROR!
// error: no matching function for call to 'accumulate(int [5], int*,
int, <unresolved overloaded function type>)'

How do you do it? &min could refer to either the int or float version.

Do you know how to do it?

You have to cast the function pointer to the resolved overload function pointer type, i.e. (int (*)(int, int))&min gives you a pointer to the int version. This would be easier if the functions were named separately.

In the above scenario, things would be easier if min were a template as you could just refer to them as &min<int> and &min<float>. Just be careful when you mix overloads and specialisation though, as they don’t play nicely with each other.

While we’re talking about things that don’t play nicely with each other. Have you ever tried to override a particular function overload in a derived class? That’s not simple either.

So, it would seem there are at least a few costs to overloading. I’m not sure if the costs are so great to warrant its removal from C++, but it’s worth thinking about these things every once in a while.

Small Object Overhead

2012-04-20T00:00:00+00:00

One problem that seems to come up quite a lot is the issue of per-object overhead when you have lots of small objects. For example, consider a small class to represent a bullet in a side-scrolling shooter:

struct Bullet
{
    void update(float delta);

    Vec2 m_position;
    Vec2 m_velocity;
}

That’s how it starts at least. What happens when the bullet hits something? It needs to inform the scoring system that you’ve scored some points. You’ll also probably want to play some sound effects, perhaps control a sprite; maybe some bullets increase the health of the player when they hit things. Before long, your simple Bullet class looks more like this:

struct Bullet
{
    void update(float delta);

    ScoringSystem m_scoringSystem;
    AudioSystem m_audioSystem;
    SpriteSystem m_spriteSystem;
    Player m_player;
    Vec2 m_position;
    Vec2 m_velocity;
}

One solution is to bunch up all of those systems into a separate object.

struct Bullet
{
    void update(float delta);

    Systems m_systems;
    Vec2 m_position;
    Vec2 m_velocity;
}

This is certainly better for the size of your object (one word overhead vs. four), but it still smells a bit funky.

A better solution, in my opinion, is to take responsibility away from the Bullet.

class BulletSystem
{
    void update(float delta)
    {
        foreach (bullet; m_bullets)
        {
            bullet.m_position += bullet.m_velocity;
            ...
        }
    }

    ScoringSystem m_scoringSystem;
    AudioSystem m_audioSystem;
    SpriteSystem m_spriteSystem;
    Player m_player;
    Bullet[] m_bullets;
}

struct Bullet
{
    Vec2 m_position;
    Vec2 m_velocity;
}

Now, the Bullet is nothing more than the data associated with the bullet itself. All the logic and responsibility is pushed up into a less granular BulletSystem. This has a few advantages:

No unnecessary overhead per bullet.
Only one function call to update N bullets, rather than N function calls.
Opens up opportunities to parallelize updates.
Has much better data flow.

When information and logic are too granular, you increase overhead and lose control, which means losing opportunities to make high-level optimisations. In this case, the whole seems to be greater than the sum of the parts.

Data Structures

2012-02-27T00:00:00+00:00

Something I’ve realised recently is that it’s usually a bad idea to use data structures to structure your data… yeah.

That probably doesn’t make much sense. What I mean is that you shouldn’t use data structures to organise high-level information in your programs. Data structures exist to make operations and algorithms faster, and should have nothing to do with how your “objects” are organised logically.

As an example, consider a game that has several worlds, and within each world there are several stages. Each stage has a bunch of stars you have to collect, and we want to know how many stars there are and how many you’ve collected.

How might you structure this in your program? Until recently, I would have used something like this:

class Game
{
    World[] worlds;
}

class World
{
    Stage[] stages;
}

class Stage
{
    Star[] stars;
}

class Star
{
    bool collected;
}

This seems reasonable. Let’s try to use it:

int totalStars(Game game)
{
    int count = 0;
    foreach (world; game.worlds)
        foreach (stage; world.stages)
            count += stage.stars.length;
    return count;
}

int starsCollected(Game game)
{
    int count = 0;
    foreach (world; game.worlds)
        foreach (stage; world.stages)
            foreach (star; stage.stars)
                if (star.collected)
                    ++count;
    return count;
}

I don’t know about you, but I’m not impressed. It’s not too difficult to write these functions, but I can’t help but thinking, “what am I gaining from structuring the code like this?”

If we step back and look at the problem that needs to be solved, surely the following would be a better way to structure the data?

class Game
{
    Star[] stars; // ALL the stars
}

class Star
{
    bool collected;
    int stageId;
}

This way, the queries are straightforward loops over all the stars. If we want to count only the stars in a particular stage then we can filter using the star’s stageId.

In the end, what matters is how you use the data, and what algorithms need to be implemented efficiently on the data. Any relationship between things in the application domain is of little relevance when choosing data structures.

Scoped Imports in D

2012-01-26T00:00:00+00:00

One of the nice things about the D programming language is that it has very convenient syntax for conditional compilation. For example, suppose you want to print out some useful info in debug builds. You just use:

debug writeln("Value of x is ", x);

One problem that I constantly run into in cases like this is that I haven’t imported std.stdio, so I have to go right up to the top of the file, add debug import std.stdio;, back down again, and continue. Sigh.

Not so fast! D has scoped imports, so you can put the import std.stdio; right where you need it.

void main(string[] args)
{
  debug import std.stdio;
  debug writeln(args);
  // ...
}

It’s the little things like this that make D so pleasant to use.

API Performance

2012-01-25T00:00:00+00:00

One thing that I’ve never given much thought about until recently is the performance of APIs. I don’t mean things like avoiding virtual function calls in your interfaces. I mean designing an API so that it promotes usage that is optimal for the hardware you are running on.

A good example of this was explored in Noel Llopis’ post Data-Oriented Design Now And In The Future. Imagine you are designing the API for a physics system. One key operation of a physics system is to perform ray casts. The obvious API for this would be:

RayHitInfo rayCast(PhysicsWorld, Ray);

Many physics systems use an API like this. For example, it’s very similar to the API provided by Unity3D.

Most game engines also have some sort of game object system, whose main task usually involves looping through each game object, calling an update function. Many of those update functions will need to perform ray casts; perhaps something like this:

void update()
{
  // ...
  if (rayCast(world, forwardRay))
    doSomething();
  // ...
}

If you have many objects doing this then you are going to run into performance problems. The ray cast is going to touch lots of data (and code) to perform the query, causing multiple cache misses as it traverses through space partitioning data structures, mesh data, etc. Then, once the ray cast is complete, you will continue processing update functions, likely pushing most or all that ray cast data and code out of the cache. When the next ray cast comes up, you have to pull it all back in again.

In addition to the poor memory performance, you also can’t parallelize the ray casts. The call is blocking, so no other object updates can happen until the ray cast completes, meaning that no other ray casts are available for parallelization.

From a performance point of view, the ideal use case would be to

Gather all the queries up front from each game object.
Batch process those queries.
Feed the results back to game objects to continue updating.

The key thing to note here is that this ideal is impossible to achieve with the current API. In order to make this change, you will have to go through and re-shuffle the logic for each raycasting update function.

If you want a performant API then it is something that should be considered beforehand, as it may not be easy to fix later on. In general, APIs that encourage asynchronicity and batched execution tend to have higher potential for good performance than synchronous, one-at-a-time functions.

Simplicity in Everything

2012-01-22T00:00:00+00:00

This website is now created using Jekyll. Originally, I had used Joomla, a big, industrial-strength content management system.

Joomla worked well for a while, but I quickly reached a point where I found myself unable to do, what should have been, simple things. For example, I couldn’t see any obvious way of extracting all the text from my posts – it was stored in a database somewhere. There was no simple way to test changes to my site locally because I couldn’t see how everything pieced together. It was just too complex for something that should have been very simple.

So I got thinking about what would be the simplest way to generate my website.

Well, what is my website? It’s just a collection of pages with the same layout, but with different blobs of text inserted in the middle for each post. I’d also like to generate some lists: recent posts, related posts, that kind of thing.

Ideally, what I want is something that transforms this

<body>
<h1>{{ page.title }}</h1>
{{ page.content }}
</body>

into this

<body>
<h1>Simplicity in Everything</h1>
<p>This website is now created using Jekyll...</p>
...
</body>

That’s exactly what Jekyll does. It just goes through all your pages and uses Liquid to transform them into a static site. Don’t believe me? The entire source for this site is on GitHub.

To test my website locally, I just run jekyll --server and head on over to http://0.0.0.0:4000. To deploy, I just run jekyll && rsync ..., which generates the site and copies it over to my remote server. That’s it.

Why can’t everything be this simple?

Homepage 2.0

2012-01-22T00:00:00+00:00

Well, I’ve done it again. New website from scratch.

This time, I’ve gone for simplicity. I got sick of the incredible bloat of Joomla and all its features that were unnecessary for what I wanted to achieve: an essentially static website that I can easily configure.

This time, I’ve gone with Tom Preston-Werner’s excellent Jekyll static site generator. I just write my posts in Markdown, run jekyll, and it generates all the HTML for me. I have full control over the layout of the site, and everything is there in plain text.

The source for this site is hosted on GitHub.