DCompute: Running D on the GPU

Posted on

Nicholas Wilson is a student at Murdoch University, studying for his BEng (Hons)/BSc in Industrial Computer Systems (Hons) and Instrumentation & Control/ Molecular Biology & Genetics and Biomedical Science. He just finished his thesis on low-cost defect detection of solar cells by electroluminescence imaging, which gives him time to work on DCompute and write about it for the D Blog.He plays the piano, ice skates, and has spent 7 years putting D to use on number bashing, automation, and anything else that he could make a computer do for him.


DCompute is a framework and compiler extension to support writing native kernels for OpenCL and CUDA in D to utilize GPUs and other accelerators for computationally intensive code. Its compute API drivers automate the interactions between user code and the tedious and error prone APIs with the goal of enabling the rapid development of high performance D libraries and applications.

Introduction

This is the second article on DCompute. In the previous article, we looked at the development of DCompute and some trivial examples. While we were able to successfully build kernels, there was no way to run them short of using them with an existing framework or doing everything yourself. This is no longer the case. As of v0.1.0, DCompute now comes with native wrappers for both OpenCL and CUDA, enabling kernel dispatch as easily as CUDA.

In order to run a kernel we need to pass it off to the appropriate compute API, either CUDA or OpenCL. While these APIs both try to achieve similar things they are different enough that to squeeze that last bit of performance out of them you need to treat each API separately. But there is sufficient overlap that we can make the interface reasonably consistent between the two. The C bindings to these APIs, however, are very low level and trying to use them is very tedious and extremely prone to error (yay void*).
In addition to the tedium and error proneness, you have to redundantly specify a lot of information, which further compounds the problem. Fortunately this is D and we can remove a lot of the redundancy through introspection and code generation.

The drivers wrap the C API, providing a clean and consistent interface that’s easy to use. While the documentation is a little sparse at the moment, the source code is for the most part straightforward (if you’re familiar with the C APIs, looking where a function is used is a good place to start). There is the occasional piece of magic to achieve a sane API.

Taming the beasts

OpenCL’s clGet*Info functions are the way to access properties of the class hidden behind the void*. A typical call looks like

enum CL_FOO_REFERENCE_COUNT = 0x1234;
cl_foo* foo = ...; 
cl_int refCount;
clGetFooInfo(foo, CL_FOO_REFERENCE_COUNT, refCount.sizeof, &refCount,null);

And that’s not even one for which you have to call, to figure out how much memory you need to allocate, then call again with the allocated buffer (and $DEITY help you if you want to get a cl_program’s binaries).

Using D, I have been able to turn that into this:

struct Foo
{
    void* raw;
    static struct Info
    {
        @(0x1234) int referenceCount;
        ...
    }
    mixin(generateGetInfo!(Info, clGetFooInfo));
}

Foo foo  = ...;
int refCount = foo.referenceCount;

All the magic is in generateGetInfo to generate a property for each member in Foo.Info, enabling much better scalability and bonus documentation.

CUDA also has properties exposed in a similar manner, however they are not essential (unlike OpenCL) for getting things done so their development has been deferred.

Launching a kernel is a large point of pain when dealing with the C API of both OpenCL and (only marginally less horrible) CUDA, due to the complete lack of type safety and having to use the & operator into a void* far too much. In DCompute this incantation simply becomes

Event e = q.enqueue!(saxpy)([N])(b_res, alpha, b_x, b_y, N);

for OpenCL (1D with N work items), and

q.enqueue!(saxpy)([N, 1, 1], [1 ,1 ,1])(b_res, alpha, b_x, b_y, N);

for CUDA (equivalent to saxpy<<<N,1,0,q>>>(b_res,alpha,b_x,b_y, N);)

Where q is a queue, N is the length of buffers (b_res, b_x & b_y) and saxpy (single-precision a x plus y) is the kernel in this example. A full example may be found here, along with the magic that drives the OpenCL and CUDA enqueue functions.

The future of DCompute

While DCompute is functional, there is still much to do. The drivers still need some polish and user testing, and I need to set up continuous integration. A driver that unifies the different compute APIs is also in the works so that we can be even more cross-platform than the industry cross-platform standard.

Being able to convert SPIR-V into SPIR would enable targeting cl_khr_spir-capable 1.x and 2.0 CL implementations, dramatically increasing the number of devices that can run D kernel code (there’s nothing stopping you using the OpenCL driver for other kernels though).

On the compiler side of things, supporting OpenCL image and CUDA texture & surface operations in LDC would increase the applicability of the kernels that could be written.
I currently maintain a forward-ported fork of Khronos’s SPIR-V LLVM to generate SPIR-V from LLVM IR. I plan to use IWOCL to coordinate efforts to merge it into the LLVM trunk, and in doing so, remove the need for some of the hacks in place to deal with the oddities of the SPIR-V backend.

Using DCompute in your projects

If you want to use DCompute, you’ll need a recent LDC built against LLVM with the NVPTX (for CUDA) and/or SPIRV (for OpenCL 2.1+) targets enabled and should add "dcompute": "~>0.1.0" to your dub.json. LDC 1.4+ releases have NVPTX enabled. If you want to target OpenCL, you’ll need to build LDC yourself against my fork of LLVM.

Unit Testing In Action

Posted on

Mario Kröplin is a developer at Funkwerk AG, a German company whose passenger information system is developed in D and was recently highlighted on this blog. That post describes Funkwerk’s use of third-party unit testing frameworks and says, “the team recently discovered a way to combine xUnit testing with D’s built-in unittest, which may lead to another transition in their unit testing.” That’s Mario’s subject in this post.


There and Back Again

Ten years ago, programming in D was like starting over in our company. And, of course, unit testing was part of it right from the beginning. D’s built-in simple support made it easy to quickly write lots of unit tests. Until some of them failed. And soon, the failure became the rule. There’s always someone else to blame: D’s simple unit-test support is too simple. A look at Python reveals that the modules doctest and unittest live side by side in the standard library. We concluded that D’s unit test support corresponds to Python’s doctest, which means that there must be something else for the real unit testing.

Even back then, we immediately found such a unit testing framework in DUnit [An old D1 unit testing framework that you can read about at the old dsource.org – Ed.]. Thanks to good advice for xUnit testing, we were happy and content with this approach. At the end of life of D1, a replacement library for D2 was soon found. After a bumpy start, I found myself in the role of the maintainer of dunit [A D2 unit-testing framework that is separate from DUnit – Ed].

During DConf 2013, I copied a first example use of user-defined attributes to dunit. This allowed imitating JUnit 4, where, for example, test methods are annotated with @Test. By now, dunit imitates JUnit 5. So if you want to write unit tests in Java style, dunit is a good choice. But which D programmers would want to do that?

Recently, we reconsidered the weaknesses of D’s unit test support. Various solutions have been found to bypass the blockers (described in the following). On the other hand, good guidelines are added, for example, to use attributes even for unittest functions. So we decided to return to making use of D’s built-in unit test support. From our detour we retain some ideas to keep the test implementation maintainable.

Expectations

Whenever a unit test fails at run time, the question is, why? The error message refers to the line number, where you find something like assert(answer == 42). But what is the value of answer if it isn’t 42? The irony is that this need is well understood. If you use a static assert instead, the error message reads like: static assert 54 == 42 is false. The fear of code bloat is the reason why you don’t get this automatically at run time.

If you look at the Language Reference, you will notice that the chapter Unit Tests covers primarily the special unittest function. It is assumed that assert is used for test verification, which is introduced in the chapter Contract Programming. In theory, it’s completely OK to reuse assert for test verification. Any failure reveals a programming error that must be fixed. In practice, however, test expectations are quite different from preconditions, postconditions, and invariants. While the expectations are usually specific (actual == expected) the contracts rather exclude specific values ​​(value != 0 or value !is null).

So there are lots of implementations of templates like assertEquals or test!"==". The problem shows up if you want to have the most helpful error messages: expected 42 but got 54. For this, assertEquals is too symmetrical. In fact, JUnit’s assertEquals(expected, actual) was turned into TestNG’s assertEquals(actual, expected). Even with UFCS (Uniform Function Call Syntax), it is not clear how a.assertEquals(b) should be used. From time to time, programmers don’t write the arguments in the intended order. Then the error messages are the opposite of helpful. They are misleading: expected 54 but got 42.

Fluent assertions avoid this symmetry problem: actual.should.eq(expected) or expect(actual).to.eq(expected) are harder to use incorrectly. Thanks to UFCS and lazy parameters, the implementation in D is no problem. The common criticism is “the natural language formulation is too verbose”, or just “too many dots”. Currently, however, this seems to be the only way to get the most helpful error messages.

The next problem is that string comparisons are seldom as simple as: expected foo but got bar. Non-printable characters or lengthy texts, such as XML or JSON representations, sabotage error messages that were meant to be helpful. This can be avoided by escaping special characters and by showing differences. Finally, this is what the fluent-asserts library does.

Test Execution

At large, we want to get as much information as possible from a failed test run. How many test cases fail? Which test cases fail? Does the happy path fail or rather edge cases? Is it worth addressing the failures, or is it better to undo the change? The approach of stopping on the first error is contrary to these needs. The original idea was to run the unit tests before the start of the actual program. By now, however, separate test runners are often used, which continue in case of a failure. To emphasize this, test expectations usually throw their own exceptions, instead of the unrecoverable AssertError. This change already shows how many test cases fail.

Finding out what’s tested in the failing test cases is more difficult. At best, there are corresponding comments for documented unit tests. But an empty DDoc comment, ///, is all that’s needed to include the body of the unittest function as an example in the documentation. In the worst case, the unit test goes on and on verifying this and that.

The idea of the Sentence Style For Naming Unit Tests is that the name of the test function describes the test case. In D, however, the unittest functions are anonymous. On the other hand, D has user-defined attributes so that you can even use strings for the test description instead of CamelCase names. unit-threaded, for example, shows these string attributes so that you get a good impression of the extent of the problem in case of a failure. In addition, unit-threaded satisfies the requirement to execute test cases selectively. For example, only the one problematic test case or all tests except those tagged as “slow”. It’s promising to use unit-threaded as needed. You let D run the unittest functions as long as they pass. Only for troubleshooting should you switch to unit-threaded. You have to be careful, however, to only use compatible features.

By the way: the parallel test execution (from it’s name, the main goal of unit-threaded) was quite problematic with the first test suite we converted. On the other hand, the speedup was just 10%.

Coverage

The D compiler has built-in code-coverage analysis. The ratio of the lines executed in the test is often used as an indicator for the quality of the tests. (See: Testing in the D Standard Library) A coverage of 100% cannot be achieved, for example, if you have an assert(0). Lower thresholds for the coverage can always be achieved by cheating. The fact that the unittest functions are also incorporated in the coverage is questionable. Imagine that a single line that has not yet been executed requires a lengthy unit test. As a consequence, this new unit test could significantly raise the coverage.

In order to avoid such measurement errors, we decided from the beginning to extract non-trivial unit tests to separate modules. We place these in parallel to the src tree in a unittest directory. Test utilities are also placed in the unittest directory, so that reading the actual code is not encumbered by large version (unittest) sections. (We also have test directories for customer tests.) For the coverage, we only count the modules under src. Code-coverage analysis creates a report file for each module. For a summary, which we output at the end of each successful test run, we have written a simple script. By now, covered is a ready-made solution.

In order to fully exploit the code-coverage analysis, an unusual formatting is required, for example, for the short-circuit evaluation of expressions with &&, ||, and ?:. We hope that dfmt can be changed to reformat the code temporarily.

Fixtures

What can you do to prevent the test implementation from getting out of control? After all, test code is also code that needs to be maintained. Sometimes the test implementation is more obscure than the code being tested.

As a solution the xUnit patterns suggest a structuring of the test implementation as a Four-Phase Test: fixture setup, exercise system under test, result verification, fixture teardown. The term fixture refers to the test context. For JUnit, this is the test class with attributes that are available to all test methods. A method with the annotation @BeforeEach initializes the attributes. This is the fixture setup. Another method with the annotation @AfterEach implements the fixture teardown. All methods annotated with @Test focus on exercise and verification.

At first glance, this approach seems to be incompatible with D’s unittest functions. The unittest functions do not get automatic access to the attributes of a class, even if they are defined in the context of a class. On the other hand, one can mimic the approach, for example, by implementing the fixtures next to the unittest functions as a struct:

unittest
{
    Fixture fixture;
    fixture.setup;
    scope (exit) fixture.teardown;
    (fixture.x * fixture.y).should.eq(42);
}

The test implementation can be improved by executing the fixture setup in the constructor (or in opCall(), since default constructors are disallowed in structs) and the fixture teardown in the destructor:

unittest
{
    with (Fixture())
        (x * y).should.eq(42);
}

The with (Fixture()) pulls the context, in which test methods are executed implicitly in JUnit, explicitly into the unittest function. With this simple pattern you can structure unit tests in a tried and trusted way without having to use a framework for test classes ever again.

Parameterized Tests

A parameterized test is a means to reuse a test implementation with different values ​​or with different types. Within a unittest function this would be no problem. Our goal, however, is to get as much information as possible from a failing test run. For which values ​​or which types does the test fail? unit-threaded provides support for parameterized tests with @Values ​​and @Types. If unit-threaded is not used to run the unittest functions, these test cases do not work at all.

With the new static foreach feature however, it is easy to implement parameterized tests without the support of a framework:

static foreach (i; 0 .. 2)
    static foreach (j; 0 .. 2)
        @(format!"%s + %s == 1"(i, j))
        unittest
        {
            (i + j).should.eq(1);
        }

And if you run the failing test with unit-threaded, the descriptions of the failing test cases reveal the problem without the need to take a look at the test implementation:

0 + 0 == 1: expected 1 but got 0
1 + 1 == 1: expected 1 but got 2

Conclusion

D’s built-in unit test support works best when there are no failures. As shown, however, you do not need to change too much to be able to work properly in situations where you rely on helpful error messages. The imitation of a solution from another programming language is often easy in D. Nevertheless, one should reconsider such solutions from time to time.

If we had a wish, we would want separate libraries for expectations and for test execution. Currently, you get frameworks where not all features are great, or they are overloaded with alternative solutions. Such a separation should probably be supported by the Phobos runtime library. Currently, each framework defines expectations with its own unit test exceptions. In order to combine them, ugly interdependencies are required to match the exceptions thrown in one library to the exceptions caught in another library. A unit test exception in Phobos could avoid this problem.

The Making of ‘D Web Development’

Posted on

A long-time contributor to the D community, Kai Nacke is the author of ‘D Web Development‘ and the maintainer of LDC, the LLVM D Compiler. In this post, he tells the story of how his book came together. Currently, the eBook version is on sale for USD $10.00 as part of the publisher’s Back to School sale, as are ‘D Cookbook‘ by Adam Ruppe and ‘Learning D‘ by Michael Parker.


At the beginning of 2014, I was asked by Packt Publishing if I wanted to review the D Cookbook by Adam Ruppe. Of course I wanted to!

The review was stressful, but it was a lot of fun. At the end of the year came a surprising question for me: would I be willing to switch sides and write a book myself? Here, I hesitated. Sure, writing your own book is a dream, but is this at all possible on top of a regular job? The proposed topic, D Web Development, was interesting. Web technologies I knew, of course, but the vibe.d framework was for me only a large unit test for each LDC release.

My interest was awakened and I created a chapter overview, based solely on my experience as a developer and the online documentation of vibe.d. The result came out well and I was offered a contract. It came with an immediate challenge: I should set up a small project plan. How do you plan to write a book?!?

Without any experience in this area, I stuck to the following rules. For each chapter, I planned a little time frame. Each should include at least one weekend, for the larger chapters perhaps even two. I reserved some time for the Easter holiday, too. The first version of the book would therefore be ready at the beginning of July, when I started writing in mid-February.

Even the first chapter showed that this plan was much too optimistic. The writing went off quickly – as soon as I had something I could write about. But experimenting and testing took a lot of time. For one thing, I didn’t have much experience with vibe.d. There were sample programs that I wanted to develop Saturday to write about on Sunday. However, I was still searching for errors on Monday, without having written a single line!

On the other hand, there were still a few rough edges in vibe.d at the time, but I did not want to write that these would be changed or implemented in later versions of the library. So I developed a few patches for vibe.d, e.g. digest authentication. By the way, there were also new LDC releases to create. Fortunately, the LDC team had expanded, so I just took care of the release itself (thanks so much, folks!). The result was, of course, that I missed many of my milestones.

In May, the first chapters came back from the review process. Other content also had to be written, such as the text for the back of the book. In mid-December, the last chapter was finished and almost all review notes on the other chapters were incorporated. After a little Christmas break, the remaining notes were quickly incorporated and the pre-final version of each chapter was created in January. And then, on February 1, 2016, the news came that my book was now published. I’d done it! Almost exactly one year after I had started with the first chapter.

Was the work worth it? In any case, it was a very special experience. Would I do it again? Yes! Right now, I am playing with the idea of updating the book and expanding a chapter. Let’s see what happens…

The Evolution of the accessors Library

Posted on

Ronny Spiegel is a developer at Funkwerk AG, a German company whose passenger information system is developed in D and was recently highlighted on this blog. In this post, Ronny tells the story of the company’s open source accessors library, which provides a mechanism for users to automatically generate property getters and setters using D’s robust compile-time features.


A little bit of history.

We’ve always used UML tools to visualize the internal structure and document details of software. That’s true for me not only at Funkwerk, but also in the companies I worked before I joined the team here in Karlsfeld. One of the major issues of documentation is that at some point in time it will diverge from the actual implementation and become outdated. Additionally, if you have to support old versions of your components you will have to take care of old versions of your documentation as well.

The first approach to connecting code and model is to generate code from the model, which requires the model to reflect the current implementation. When I joined Funkwerk we were using ArgoUML to manage class diagrams which were used as input to generate code. Not only class or struct skeletons were generated (existing code was kept), but also methods to access members which were not even part of the model. In order to control whether a member should be accessible, annotations, similar to UDAs (User-Defined Attributes), were used as part of the member documentation. So it was very common for us to annotate a member with @Read or @Write even though it was only in the documentation. The tool which we used to generate code was powerful enough to create the implementation of these field accessor methods supported by annotations to synchronize access, or to automatically use invariants for pre- and post-conditions as well.

Anyway, the approach of using the model as a base for code generation always suffers from the same problem: it is very hard to merge models!

So we reversed the whole thing and decided to create documentation from code. We could still use code which had been generated before, but all the new classes had to be supplied with accessor functions. You can imagine that this was very annoying.

public class Journey
{
    private Leg[] legs_;

    public Leg[] legs()
    {
	return this.legs_.dup;
    }

...
}

(Yes, we’ve been writing Java and compiling as D.)

Code which was generated before still had these @Read and @Write annotations next to the fields. So I thought, “These look like UDAs. Why not just use those to generate the methods automatically?” I’d always wanted to use mixins and compile-time introspection in order to move forward with a more D-like development approach.

A first draft…

The very first version of the accessors library was able to generate basic read- and write-accessor methods using the allMembers trait, filtering by UDAs, and generating some basic code like:

public final Leg[] legs() { return this.legs_.dup; }

It works… Yes, it does.

We did not replace all existing accessor methods at once, but working on a large project at that time we introduced many of them. The automated generation of accessor methods was really a simplification for us.

…always has some issues.

The first implementation looked so simple – there must have been issues. And yes, there were. I cannot list all of them because I do not remember anymore, but some of these issues were:

Explicitly defined properties suppressed generated ones

We ran into a situation where we explicitly defined a setter method (e.g. because it had to notify an observer) but wanted to use the generated getter method. The result was that the defined setter method could be used but accessing the generated getter method (with the same name) was impossible.

According to the specification, the compiler places mixins in a nested scope and then imports them into the surrounding scope. If a function with the same name already exists in the surrounding scope, then this function overwrites the function from the mixin. So if there is a field with a @Read annotation and another explicitly defined mutating field accessor, then the @Read accessor is overwritten by the defined one.

The solution to this issue was rather simple. We had to use a string mixin to import the generated code into the class where it shall be used.

Flags

We have a guideline to avoid magic bools wherever possible and use much more verbose flags instead. So a simple attribute like:

private bool isExtraJourney_;

Becomes:

private Flag!”isExtraJourney” isExtraJourney_;

This approach has two advantages. Providing a value with Yes.isExtraJourney is much more verbose than just a true, and it creates a type. When there are two or more flags as part of a method signature, you cannot change the order of the flags (by accident) as you could with bools.

To generate the type of the return value (or in case of mutable access of the parameter) we used T.stringof, where T is the type of the field. Unfortunately, this does not work as expected for Flags.

Flag!”foo” fooFlag;

static assert(`Flag!”foo”`, typeof(fooFlag).stringof); // Fails!
static assert(`Flag`, typeof(fooFlag).stringof); // Succeeds!

Unit Tests

When using the mixin in private types defined in unit tests, a similar issue arose. Classes defined in unittest blocks have a prefix like __unittestL526_8. It was necessary to strip this prefix from the used type string.

Private Classes

While iterating over members of private classes, we stumbled across the issue that the allMembers (or derivedMembers) trait returns, in addition to __ctor, an unaccessible member called this. This issue remains unsolved.

The current implementation…

The currently released version covers the aforementioned issues, although there is still room for new features.

An example might be to provide a predicate which is then used for synchronizing access to the field. That was possible using the old version of the code generator by annotating it with @GuardedBy(“this”). Fortunately, we’ve advanced in our D coding skills and have moved away from Java code compiled with DMD to a more D-like style by using structs wherever we need value semantics (and we don’t have to deal with thousands of copies of that value). So at the moment, this doesn’t really hurt that much.

Another interesting (and still open issue) is to create accessors for aliased imported types. The generated code still refers to the real name of the type, which is then unknown to the compile unit where the code is mixed in.

…has room for improvement!

If you’re interested in dealing with this kind of problem and want to dive into CTFE and compile-time introspection, we welcome contributions!

Open Methods: From C++ to D

Posted on

Jean-Louis Leroy is not French, but Belgian. He got his first taste of programming from a HP-25 calculator. His first real programming language was Forth, where CTFE is pervasive. Later he programmed (a little) in Lisp and Smalltalk, and (a lot) in C, C++, and Perl. He now works for Bloomberg LP in New York. His interests include object-relational mapping, open multi-methods, DSLs, and language extensions in general.


Prelude


Earlier this year I attended C++Now, a major conference dedicated to C++. I listened to talks given by very bright people, who used all sorts of avant-garde C++ techniques to accomplish all sorts of feats at compile time. It was a constexpr party! However, at the end of the week I had severe doubts about the future of C++.

I’ll say this for the organizers, though: they were quite open minded. They reserved the largest auditorium for a two-hour presentation of competing languages, one every day. We had Haskell and Rust, and Ali Çehreli talked about D.

I knew next to nothing about D. You see, I learned to program in Forth. Later I did some Lisp programming just for fun. To me, the idea of CTFE was natural right off the bat. So when Ali talked about static if and mixins, he definitely got my attention.

In order to learn (and evaluate) D, I decided to reproduce parts of my C++ library yomm11. It implements open multi-methods and contains code that exercises the “interesting” parts of the language, both at compile time and run time. Initially, I thought I would just see how I could reimplement bits of yomm11, how nice (or ugly) the syntax for declaring methods would turn out to be. The result was satisfying. I would even say intoxicating. I ended up bringing the port to completion and I feel that the result–openmethods.d–is the best implementation of open methods I’ve crafted so far. And it’s all done in a library, relying only on existing language features.

But wait, what are open methods?

From Member to Free

Open methods are just like virtual functions, except that they are declared outside of a class hierarchy. They are often conflated with multi-methods, because they are frequently implemented together (as is the case with this library), but really these are two different concepts. The ‘open’ part is, I believe, the more important, so I will focus more on that in this article.

Here is an example of a virtual function:

interface Animal
{
  string kick();
}

class Dog : Animal
{
  string kick() { return "bark"; }
}

class Pitbull : Dog
{
  override string kick() { return super.kick() ~ " and bite"; }
}

void main()
{
  import std.stdio : writeln;
  Animal snoopy = new Dog, hector = new Pitbull;
  writeln("snoopy.kick(): ", snoopy.kick()); // bark
  writeln("hector.kick(): ", hector.kick()); // bark and bite
}

The direct equivalent, translated to open methods, reads like this:

import openmethods;
mixin(registerMethods);

interface Animal
{
}

class Dog : Animal
{
}

class Pitbull : Dog
{
}

string kick(virtual!Animal);

@method
string _kick(Dog dog) { return "bark"; }

@method
string _kick(Pitbull dog) { return next!kick(dog) ~ " and bite"; }

void main()
{
  updateMethods();
  import std.stdio : writeln;
  Animal snoopy = new Dog, hector = new Pitbull;
  writeln("snoopy.kick(): ", snoopy.kick()); // bark
  writeln("hector.kick(): ", hector.kick()); // bark an dbite
}

Let’s break it down.

  • The string kick() in interface Animal becomes the free function declaration string kick(virtual!Animal). The implicit this parameter becomes an explicit parameter, and its type is prefixed with virtual!, thus indicating that the parameter is used to resolve calls at run time.
  • The string kick() override in class Dog becomes the free function definition @method string _kick(Dog dog) { return "bark"; }. Three things here:
    • the override is preceded by the @method attribute
    • the function name is prefixed with an underscore
    • the implicit this argument is explicitly named: Dog dog
  • The same thing happens to the override in class Pitbull, with an extra twist: super.kick() becomes next!kick(dog)
  • The calls to kick in main become free function calls – although, incidentally, they could have remained unchanged, thanks to Uniform Function Call Syntax.
  • After importing the openmethods module, a mixin is called: mixin(registerMethods). It should be called in each module that imports openmethods. It matches method declarations and overrides. It also creates a kick(Animal) function (note: sans the virtual!), which is the entry point in the dynamic dispatch mechanism.
  • Finally, main calls updateMethods. This should be done before calling any method (typically first thing in main) and each time a library containing methods is dynamically loaded or unloaded.

Open Is Good

What does it gain us? Well, a lot. Now we can add polymorphic behavior to any class hierarchy without modifying it. In fact, this implementation even allows you to add methods to Object, in a matter of speaking. Because, of course, class Object is never modified.

Let’s take a more serious example. Suppose that you have written a nifty matrix math library. Matrices come in all sorts of flavors: diagonal, shallow, tri-diagonal, and of course dense (i.e. “normal” matrices). Depending on the exact nature of a matrix, you can optimize some operations. Transposing a diagonal or a symmetric matrix amounts to returning it, unchanged. Adding sparse matrices does not require adding thousands of zeroes; and so on. And you have exploited all these properties in your matrix library, varying the behavior by means of virtual functions.

Neat.

Now let me ask you a question: should you provide a print function? A persist function?

Almost certainly not. For starters, there are many ways to display a matrix. If it is sparse, you may want to show only the non-zero elements… or all of them. You may want to display the null matrix as [0]… or in full. It is the privilige of the application to decide what matrices should look like on screen or paper. The matrix library should do the maths, and the application should do the presentation. If it needs to display matrices at all, that is. In game programming, there may be no need to display matrices. However, if you provide a print function, given the way they are implemented, the print or the persist code will always be pulled in from the library. Not good.

Now the application programmer will have to write his print and persist functions, but immediately he will be facing a problem: certainly he wants to vary the behavior according to the exact matrix type; he wants polymorphism! So he will probably end up coding a set of type switches.

Open methods solve this problem more neatly:

void print(virtual!Matrix m);

@method
void _print(Matrix m)
{
  const int nr = m.rows;
  const int nc = m.cols;
  for (int i = 0; i < nr; ++i) {
    for (int j = 0; j < nc; ++j) {
      writef("%3g", m.at(i, j));
    }
    writeln();
  }
}

@method
void _print(DiagonalMatrix m)
{
  import std.algorithm;
  import std.format;
  import std.array;
  writeln("diag(", m.elems.map!(x => format("%g", x)).join(", "), ")");
}

Accept No Visitors (c) Yuriy Solodkyy

A popular existing solution to this problem comes in the form of the Visitor pattern. Your matrix library could provide one, thus allowing the application writer to process different matrices according to their type.

In truth, Visitor is more an anti-pattern than a pattern, because the base class is aware of all its derived classes – something that flies in the face of all OOP design rules.

Here it is anyway:

import std.stdio;

interface Matrix
{
  interface Visitor
  {
    void visit(DenseMatrix m);
    void visit(DiagonalMatrix m);
  }

  void accept(Visitor v);
}

class DenseMatrix : Matrix
{
  void accept(Visitor v) { v.visit(this); }
}

class DiagonalMatrix : Matrix
{
  void accept(Visitor v) { v.visit(this); }
}

class PrintVisitor : Matrix.Visitor
{
  this(File of) { this.of = of; }

  void visit(DenseMatrix m) { of.writeln("print a DenseMatrix"); }
  void visit(DiagonalMatrix m) { of.writeln("print a DiagonalMatrix"); }

  File of;
}

void main()
{
  Matrix dense = new DenseMatrix, diagonal = new DiagonalMatrix;
  auto printer = new PrintVisitor(stdout);
  dense.accept(printer);
  diagonal.accept(printer);
}

This approach is more verbose than using an open method, and it has a more fatal flaw: it is not extensible. Suppose that the user of your matrix library wants to add matrices of his own design. For example, a SparseMatrix. The Visitor will be of no help here. With open methods, on the other hand, the solution is available, simple, and elegant:

// from library

void print(virtual!Matrix m, File of);

@method
void _print(DenseMatrix m, File of)
{
  of.writeln("print a DenseMatrix");
}

@method
void _print(DiagonalMatrix m, File of)
{
  of.writeln("print a DiagonalMatrix");
}

// extend library

class SparseMatrix : Matrix
{
  // ...
}

@method
void _print(SparseMatrix m, File of)
{
  of.writeln("print a SparseMatrix");
}

Multiple Dispatch

Occasionally, there is a need to take into account the type of two or more arguments to select the appropriate behavior. This is called multiple dispatch. Most languages only support single dispatch in the form of virtual member functions. Once again, the “solution” involves type switches or visitors. A few languages address this situation directly by means of multi-methods. The most notorious example is the Common Lisp Object System. Recently, a string of new languages have native support for multi-methods: Clojure (unsurprising for a lispoid), Julia, Nice, Cecil, TADS (a language for developing text-based adventure games).

This library implements multi-methods as well. There is no limit to the number of arguments that can be adorned with the virtual! qualifier. They will all be considered during dynamic dispatch.

Continuing the matrix library example, you probably want to provide binary operations on matrices: addition, subtraction and multiplication. If both operands are matrices, you really want to pick the right algorithm depending on the respective types of both operands. There is no point wasting time on adding all the elements if both operands are diagonal matrices; adding the diagonals suffices. Crucially, adding two DiagonalMatrix objects should return a DiagonalMatrix, not a plain DenseMatrix. Adding a DiagonalMatrix and a TriDiagonalMatrix should return a TriDiagonalMatrix, etc.

With open multi-methods, there is no problem at all:

module matrix;

Matrix plus(virtual!Matrix, virtual!Matrix);

module densematrix;

@method
Matrix _plus(Matrix a, Matrix b)
{
  // fallback: add all elements, fetched via interface
  // return a DenseMatrix
}

@method
Matrix _plus(DenseMatrix a, DenseMatrix b)
{
  // add all elements, access representation directly
  // return a DenseMatrix
}

module diagonalmatrix;

@method
Matrix _plus(DiagonalMatrix a, DiagonalMatrix b)
{
  // just add the elements on diagonals
  // return a DiagonalMatrix
}

Once again, open methods make the library extensible. It is trivial to plug new types in:

module mymatrices;

@method
Matrix _plus(SparseMatrix a, SparseMatrix b)
{
  // just add the non-zero elements
  // return a SparseMatrix
}

@method
Matrix _plus(SparseMatrix a, DiagonalMatrix b)
{
  // still don't add all the zeroes
  // return a SparseMatrix
}

@method
Matrix _plus(DiagonalMatrix a, SparseMatrix b)
{
  return plus(b, a); // matrix addition is commutative
}

Implementation Notes and Performance

This implementation uses tables of pointers to select the appropriate function to call. The process is very similar to what happens when a regular, virtual member function is called.

Each class involved in method dispatch–either because it is used as a virtual argument in a method declaration, or because it inherits from a class or an interface used as a virtual argument–has an associated method table (mtbl). The pointer to the method table (mptr) associated to a given class is stored, by default, in the deallocator pointer of the class’s ClassInfo. The first entry in a class’s vtable contains a pointer to its ClassInfo. The deallocator pointer was used to implement the deprecated delete method, so it is reasonable to recycle it. The deallocator pointer may be removed some day, or one may want to use methods in conjunction with classes that implement delete, so an alternative is supported. Tagging a method with @mptr("hash") makes it fetch the method table pointer from an array indexed by a perfect integer hash calculated during updateMethods. In this case, finding the mptr amounts to multiplying the vptr’s value by an integer and applying a bit mask.

The method table contains one entry for each virtual parameter for each method. If the method has a single virtual argument, the entry contains the specialization’s address, just like an ordinary virtual function; otherwise, the entry contains a pointer to a row in a multi-dimensional dispatch table for the first argument, and integer indexes for the subsequent virtual arguments.

Since the set of methods applicable to a given class is known only at run time and may change in the presence of dynamic loading, the position of a method’s entries in the method table is not fixed; it is stored in a table associated with each method. Finally, in the presence of multiple dispatch, a per-method array of strides is used to convert the multi-dimensional index to a linear offset.

However, finding the specialization amounts to a few memory reads, additions and perhaps multiplications. As a result, open methods are almost as fast as virtual functions backed by the compiler. How much slower they are depends on several factors, including the compiler, or whether the call is issued from an interface or a class. The following table sums up some of my benchmarks. Rows come in groups of three: the “usual”, compiler-supported virtual member functions; the functional equivalent using open methods; and the cost, expressed as (method - virtual) / virtual:

mptr in deallocator dmd ldc2 gdc
vfunc (interface) 1.84 1.80 1.80
vs 1-method (interface) 10.73 3.53 6.05
delta% 484% 96% 236%
vfunc (class) 1.83 1.80 1.80
vs 1-method (class) 5.12 2.13 1.80
delta% 180% 18% 0%
double dispatch 4.11 2.40 2.13
2-method 7.75 3.14 3.40
delta% 88.45% 30.71 59.85

Times in nanoseconds, measured on my Asus ROG G751JT.

A few results stand out. The first is expected, the others are quite remarkable.

  1. gdc and ldc2 do a better job at optimizing method dispatch
  2. Method calls that take an object perform much better than those taking an interface; there may be some further improvements to be done here.
  3. Method calls from an object are almost as fast as plain virtual function calls when ldc2 is used; they are just as fast with gdc. The latter is surprising and calls for further investigation.
  4. Disappointingly, double dispatch beats binary methods. This is not the case in C++. My intuition is that extracting the method table pointer requires traversing too many indirections, to the point that it is more costly than a plain virtual function call. In contrast, yomm11 sticks the mptr right inside the object (but at the cost of requiring changes to the classes). This deserves further investigation, but I am convinced that a bit of help from the compiler (like reserving the second element of the vtbl for the mptr) would reverse this result.

Memory footprint is also a common concern when implementing table-based multiple dispatch: imagine a method with three virtual arguments, which can each be any of a dozen classes. This gives us a 12x12x12 table, containing 1728 function pointers. Fortunately, it is rare that a specialization is defined for each combination of arguments. Typically, there is a lot of duplication along each axis. This implementation takes advantages of this: it builds tables free of redundancies. The table is not “compressed” per se, as it never exists as a cartesian product of all the class sets; rather, it is built in terms of class partitions, not classes, where all the classes in the same group in the same dimension have the same set of candidate specializations. See
this article for an example.

Extending the Language – in D and in C++

Yomm11, the initial implementation of open methods in C++, takes 1845 lines of code (excluding comments) to implement; the D version weighs 1120 lines. Much of the difference is due to D’s ClassInfo. It contains information on the base class and inherited interfaces. It is used to build a bi-directional inheritance graph of the types that have methods attached to them.

C++’s type_info contains no such informaton, thus yomm11 comes with its own runtime class information system, and a macro that the user must call for each class participating in method dispatch. The usual difficulties with static constructors arise, and necessitates extra code to handle them.

Yomm11 can be used in two modes: intrusive and orthogonal. In the intrusive mode, the user augments the classes using macro calls. One of them allocates a method table pointer in the object; the other–called in each constructor–initializes the method pointer. In the orthogonal mode, no modification of the classes is required: the method pointer is stored in a hash map keyed by the type_info obtained via the typeid operator.

openmethods.d has two modes, too, but they are both orthogonal. The default mode stores the method pointer in the deallocator field of the ClassInfo. The ClassInfo of an object is available as the first pointer of the virtual function table; all this is documented. However, hijacking deallocator is a bit like cheating, and nothing guarantees that that field will be there forever.

For that reason, the library supports another mode, which is only slightly slower than the first: store the method pointer in an array indexed by a perfect integer hash of the virtual table pointer.

Unfortunately, it is not possible to use this approach in C++. It is possible to retrieve an object’s vptr, albeit by resorting to undocumented implementation details. However, the library needs to build the method tables without having instances of objects at hand; in D, on the other hand, the value of the vptr is available in the ClassInfo. Another idea would be to use a pointer to the type_info structure; alas, while a type_info can be obtained from a type as well as from an object, the standard explicitly states that the type_info object for a given type may not be unique.

Thus D provides at bit more information than C++, and that makes all the difference.

As for the meta-programming involved in processing the method declarations and specializations, it is easier, and yields a better syntax, in D than in C++, for several reasons.

Obviously, constructs like static if and foreach on type tuples make meta-programming easier. But the real advantage of D comes from the interplay
of template mixins, string mixins, compile-time reflection and alias. The mixin(registerMethods) incantation scans the entire translation unit and:

  • locates all the method declarations by detecting the functions that have virtual! in their signature
  • creates (via an alias created by a string mixin) a function with the same signature, minus the virtual qualifiers, which is what the user calls
  • finds all the method specializations (by locating the functions that have a @method attribute) and generates code that, at runtime, will register the specializations with the appropriate method

Conclusion

Object-oriented programming became popular in the nineties, but has been subjected to a lot of criticism in the last decade. This is in part because OOP promised modularity and extensibility, but failed to deliver. Instead we got “God” classes and Visitors. It is not the fault of the OOP paradigm per se, but rather of the unnatural and unnecessay fusion of class membership and polymorphism that most OO languages enforce. Open methods correct this mistake. As a bonus, this implementation also supports multiple dispatch. This is OOP done right: not objects “talking” to each other, but applying the appropriate algorithm depending on the arguments’ runtime types.

Open methods can be implemented as a library in C++ and in D, but D has a clear edge when it comes to meta-programming. As a result, the D version of the library delivers a lighter, cleaner syntax.

openmethods.d is available on dub