Wednesday, March 21, 2012

PIMPL vs Pure Virtual Interfaces

In C++, separating the interface (public declarations) of a class from its implementation (private methods, members and definitions) serves several useful purposes:

  • Implementation details are hidden, making interfaces easier to read and understand.

  • Smaller header files with fewer dependencies means faster compile times.

  • A weaker coupling between the interface and the implementation gives greater freedom in reorganizing and refactoring the implementation internals.

In pure C, we can achieve this separation by using a pointer to a forward declared struct:

struct SoundWorld;
typedef unsigned SoundInstanceId;

SoundWorld *make_sound_world();
void destroy_sound_world(SoundWorld *world);
SoundInstanceId play(SoundWorld *world, SoundResource *sound);
void stop(SoundWorld *world, SoundInstanceId id);

The struct is opaque to the users of the API. The actual content is defined in the .cpp file:

struct SoundWorld {
    SoundInstance playing_instances[MAX_PLAYING_INSTANCES];
    Matrix4x4 listener_pose;
    ...
};

C++ programmers are often recommended to use the PIMPL idiom (pointer to implementation) to achieve the same thing:

class SoundWorldImplementation;

class SoundWorld
{
public:
    typedef unsigned InstanceId;

    SoundWorld();
    ~SoundWorld();

    InstanceId play(SoundResource *sound);
    void stop(InstanceId id);

private:
    SoundWorldImplementation *_impl;
};

Here, SoundWorld is the external interface of the class. All the messy stuff: instance variables, private methods, etc is found in the SoundWorldImplementation class, which is in the .cpp file.

The _impl pointer is created in the constructor and calls to the methods in SoundWorld are forwarded to the implementation object via method stubs:

SoundWorld::SoundWorld()
{
    _impl = new SoundWorldImplementation();
}

InstanceId SoundWorld::play(SoundResource *sound)
{
    return _impl->play(sound);
}

Another solution to the same problem is to write the interface as an abstract, pure virtual class in the .h file and then create the implementation as a subclass in the .cpp file.

You don't see this solution recommended as much (at least not as a solution to this particular problem), but I actually like it better. With this approach, the header file will look something like this:

class SoundWorld
{
public:
    typedef unsigned InstanceId;

    virtual ~SoundWorld() {}
    virtual InstanceId play(SoundResource *sound) = 0;
    virtual void stop(InstanceId id) = 0;

    static SoundWorld *make(Allocator &a);
    static void destroy(Allocator &a, SoundWorld *sw);
};

Note that since the class is now abstract, we cannot create actual instances of it, to do that we need the factory functions make() and destroy(). I've added an allocator parameter for good measure, because I always want to specify explicit allocators for all memory operations.

The corresponding .cpp file looks something like:

class SoundWorldImplementation : public SoundWorld
{
    friend class SoundWorld;

    SoundInstance _playing_instances[MAX_PLAYING_INSTANCES];
    Matrix4x4 _listener_pose;

    SoundWorldImplementation()
    {
        ...
    }

    virtual InstanceId play(SoundResource *sound) 
    {
        ...
    }

    virtual void stop(InstanceId) 
    {
        ...
    }
};

SoundWorld *SoundWorld::make(Allocator &a)
{
    return a.make<SoundWorldImplementation>();
}

SoundWorld *SoundWorld::destroy(Allocator &a, SoundWorld *sw)
{
    return a.destroy<SoundWorldImplementation>(sw);
}

The reason why most people recommend the PIMPL approach is that it has some distinct advantages:

  • Factory functions are not needed, you can use new(), delete() or create objects on the stack.

  • The SoundWorld class can be subclassed.

  • The interface methods are not virtual, so calling them might be faster. (On the other hand, we need an extra memory fetch to get to the implementation object.)

  • PIMPL can be introduced in an existing class without changing its external interface or its relation to other classes.

For my use cases, none of these advantages matter that much. Since I want to supply my own allocators, I'm not interested in new and delete. And I only use this for "big" objects, that are always heap (rather than stack) allocated.

I don't make much use of implementation inheritance. In my opinion, it is almost always a bad design decision that leads to strongly coupled code and hard to follow code paths. Inheritance should be limited to interface inheritance.

The performance issue of virtual calls is not a huge issue, since I only use this for "big" objects (Systems and Managers). Also, I design the API so that the number of API calls is minimized. I.e., instead of a function:

void set_sound_position(InstanceId id, const Vector3 &pos);

I have:

void set_sound_positions(unsigned count, const InstanceId *ids, const Vector3 *positions);

This reduces the virtual call overhead, but also has additional benefits, such as being DMA friendly and allowing for parallelization and batch optimizations.

In the words of Mike Acton: Where there's one, there's more than one.

The abstract class method has some advantages of its own:

  • Cleaner code and a lot less typing, since we don't have to write forwarding stubs for the methods in the public interface.

  • Multiple classes can implement the same interface. We can statically or dynamically select which particular implementation we want to use, which gives us more flexibility.

To me, not having to write a ton of stupid boilerplate cruft is actually kind of a big deal. I know some people don't mind boilerplate. It's just a little extra typing, they say. Since there is nothing complicated or difficult in the boilerplate code, it doesn't pose a problem. Programmers are not limited by typing speed, so how much you have to type doesn't matter.

I don't agree at all. In my view, every line of code is a burden. It comes with a cost that you pay again and again as you write, read, debug, optimize, improve, extend and refactor your code. For me, the main benefit of "higher-level" languages is that they let me do more with less code. So I'm happy to pay the overhead of a virtual call if it saves me from having 150 lines of idiotic boilerplate.

A nice thing about the interface and implementation separation is that it gets rid of another piece of hateful C++ boilerplate: method declarations (hands up everybody who enjoys keeping their .h and .cpp files synchronized).

Methods defined inside a C++ class do not have to be declared and can be written in any order. So if we want to add helper methods to our implementation class, that are not part of the public interface, we can just write them anywhere in the class:

class SoundWorldImplementation : public SoundWorld
{
    virtual InstanceId play(SoundResource *resource) {
        InstanceId id = allocate_id();
        ...
    }

    // A private method - no declaration necessary.
    InstanceId allocate_id() {
        ...
    }
};

It's interesting that this small, purely syntactical change -- getting rid of method declarations -- makes a significant different in how the language "feels". At least to me.

With this approach, adding a helper method feels like "less work" and so I'm more inclined to do it. This favors better structured code that is decomposed into a larger number of functions. More like Smalltalk than traditional C (home of the mega-method). The Sapir-Worf hypothesis appears to hold some merit, at least in the realm of programming languages.

Another interesting thing to note is that the pure C implementation of opaque pointers stacks up pretty well against the C++ variants. It is simple, terse and fast (no virtual calls, no forwarding functions).

Every year I'm a little more impressed by C and a little more depressed by C++.

Sunday, March 4, 2012

Caring by Sharing: The Bitsquid Documentation System

In a previous article I talked a bit about our documentation system. It has now solidified into something interesting enough to be worth sharing.

The system consists of a collection of Ruby files that read input files (with extension .bsdoc) written in a simple markup language:

# Header

Some text.

* And
* A list

and converts them to HTML:

<h1>Header</h1>

<p>Some text.</p>

<ul>
 <li><p>And</p></li>
 <li><p>A list</p></li>
</ul>

We then use the HTML Help Compiler to convert the help files to .chm.

You can find the repository at:

Motivation

Why have we created our own markup system instead of just using an existing one? (Markdown, Textile, RDoc, POD, Restructured Text, Doxygen, BBDoc, Wikimedia, Docbook, etc.)

For two reasons. First, none of these existing systems work exactly the way that we want.

An example. A large part of our documentation consists of Lua interface documentation. To make that as easy to possible to write, we use a special tag @api to enter an API documentation mode. In that mode, each unindented line documents a new Lua function. The indented lines that follow contain the documentation for the function.

## Application (singleton)

Interface to access global application functionality. Note that since the
application is a singleton (there is only one application), you don’t need
to pass any %r Application object to the application functions. All the
functions operate on the application singleton.

@api

resolution() : width, height
 Returns the screen resolution.
 
argv() : arg1, arg2, arg3, ...
 Returns the command line arguments supplied to the application.

The documentation system recognizes the Lua function definitions and formats them appropriately. It also creates index entries for the functions in the .chm file. In addition, it can create cross-references between classes and functions (with the %r marker).

No out-of-the-box system can provide the same level of convenience.

In any documentation system, the documentation files are the most valuable resource. What really matters is that documentation is easy to write and easy to modify. In particular, my main concerns are:

  • Preserving semantic information.

  • Avoiding unnecessary markup and clutter.

By preserving semantic information I mean that we should be able to say, for example, that something is a Lua function definition, or a piece of sample C++ code, rather than just saying that something is italic or preformatted. If we have enough semantic information, we can do all kinds of things to the data in post-processing. We can parse the function definition using a Lua parser, or run the C++ code through a syntax highlighter. We can convert the files to some other format if we ever decide to switch documentation system.

If the documentation format doesn't preserve semantic data, there is no way of getting that data back, except by going through all the documentation and adding it manually. That's painful.

Avoiding markup and clutter is all about making the documents easy to write and easy to modify. That's the whole point of using a markup language (instead of plain HTML) in the first place.

Our custom markup language lets us achieve both these goals in a way that no off-the-shelf solution could.

The second reason for writing our own system is that there is no fundamentally hard problem that the existing systems solve. If they did something really advanced that would take us months to duplicate, then it might be better to use an existing system even if it wasn't perfectly adapted to our needs. But parsing some text and converting it to HTML isn't hard. The entire documentation system is just a few hundred lines of Ruby code.

(In contrast, Doxygen actually does solve a hard problem. Parsing general C++ code is tricky. That's why we use Doxygen to document our C++ code, but our own system for stand-alone documentation.)

The System Design

If I've done my job and convinced you that the best thing to do is to write your own documentation system, then what's the point of sharing my code with you?

Well, the system we use consists of two parts. One part (the bulk of it) is generic and can be used to implement any markup language. The rules that are specific to our markup language are all kept in a single file (bsdoc.rb). To write your own documentation system, you could re-use the generic parts and just write your own markup definition.

The generic part of the system consists of four files:

paragraph_parser.rb

Parses the paragraphs of a document into block-level HTML code.

span_parser.rb

Does span-level parsing inside a HTML block.

generator.rb

Generates the output HTML.

toc.rb

Adds section numbering and a table of contents to an HTML file.

Most of the code is pretty straight forward. A rule set is a collection of regular expressions. The expressions are tested in turn against the content and the first one that matches is applied. There are separate rules for parsing the document on the block level (the ParagraphParser) and inside each line (the SpanParser).

There are some ideas in the system that I think are interesting enough to mention though:

Line-by-line parsing

On the paragraph level, the document is parsed line-by-line. Each rule regex is tested in turn and the first one that matches is applied. This ensures that the process is speedy for all kinds of input (O(N) in the number of lines). It also makes the system simpler to reason about.

No intermediate representation

The system does not build any intermediate representation of the document. It is converted directly from the .bsdoc source format to HTML. This again simplifies the system, because we don't have to device an intermediate representation for all kinds of data that we want to handle.

HTML "contexts" for lines

When a rule is applied, it doesn't write raw HTML code to the output. Instead, it gives the generator a piece of text and a list of tags that should be applied to it. I call this the "context" of the text.

env.write(%w(ul li p), "Hi!")

The generator will add tags as appropriate to ensure that the line is printed in the right context:

<ul><li><p>Hi!</p></li></ul>

When several lines are printed, the generator only opens and closes the minimum number of tags that are necessary to give each line the right context. It does this by matching the list of contexts for neighboring lines:

This:

env.write(%w(ul li p), "First item!")
env.write(%w(ul li p), "First paragraph!")
env.write(%w(ul li), nil)
env.write(%w(ul li p), "First item, second paragraph!")
env.write(%w(ul), nil)
env.write(%w(ul li p), "Second item!")

ends up as:

<ul>
 <li>
  <p>
   First item!
   First paragraph!
  <p>
  <p>First item, second paragraph!</p>
 </li>
 <li><p>Second item!</p></li>
</ul>

Note the trick of writing nil to explicitly close a scope.

Since I really, really hate badly formatted HTML documents, I've made sure that the output from the generator looks (almost) as good as hand-written HTML.

Using contexts in this way gets rid of a lot of the complexities of HTML generation. When we write our rules we don't have to think about opening and closing tags, we just have to make sure that we use an appropriate context for each line.

Nested scopes

The final idea is to automatically handle nested markup by applying the rules recursively. Consider this input document:

* Caught in the jungle
 * By a bear 
 * By a lion
 * By something else
* Caught in the woods

I don't have any special parsing rules for dealing with nested lists. Instead, the first line of this document creates a scope with the context %w(ul li). That scope is applied to all indented lines that follow it. The system strips the indentation from the line, processes it using the normal rule set, and then prepends %w(ul li) to its context. When it reaches a line without indentation, it drops the scope. Scopes can be stacked for multiple levels of nesting.

This way we can deal with arbitrarily complex nested structures (a code sample in a list in a blockquote) without any special processing rules.

A Bonus for AltDevBlogADay Writers

As a bonus for my fellow AltDevBlogADay writers I've added a syntax module for writing AltDevBlogADay articles. It converts source documents to a format suitable for publishing on AltDevBlogADay. (This includes taking care of the tricky <pre> tags.)

There is also a package for Sublime Text 2 (my favorite text editor) that gives you syntax highlighting and a build command for converting a document to HTML and previewing it in a browser. I'm currently writing all my AltDevBlogADay articles in this way.

(This article has also been posted to The Bitsquid blog.)