.

Low-overhead components

My personal dream of an ideal programming language is one that allows defining flexible, configurable components that can be coupled together with very little overhead, producing in the end code that, if reverse-engineered, would appear to be hand-written and optimized for the specific task at hand. Preconfigured component configurations / presets would be available for common use, favoring safety and feature-completeness, but for performance-critical cases, the programmer could break them down and strip out unneeded features to reduce overhead, or customize by injecting their own components into the mix.

One typical example of such component composition is allocators. The HeapLayers project is a C++ library which allows combining and layering components to create allocators with various strategies. I understand that STL allocators are stateless, which is boring – we want freelists and regions with lifetimes we can manage.

Another example is XML parsing (which is frequently the target of benchmarks). Performance can depend on the exact demands. For example: do we need to store the parsed data somewhere, or just look at it while it’s being decoded? Do we know that the XML is well-formed? Do we care about namespaces? Do we want to decode XML entities in-loop, or lazily? Do we want to optimize for memory usage and intern all strings (which would also allow doing XML entity decoding only once per unique string), or should we rather store slices of the input string? (Some of the above are more related to policy-based design rather than composition, which is not entirely-unrelated.)

I was having some memory performance problems with a small personal project, so I wanted to have a go at implementing some kind of allocators in D. Not really to invent a wheel, or even invent a better one, but just to explore and play around with the concepts involved.

In C++, composition seems to be usually done using class inheritance (the top layer class inherits from the underlying layers). This approach is not applicable to D, since D doesn’t have value-type inheritance. So, my first approach looked like this:

struct LAYER(BASE)
{
	BASE base;
	// ... use base ...
}

Quite simple.

The base field is public, which means that the user code can initialize it, if needed, before use. Or access it directly, if needed. It could also be a pointer (thankfully D ditched C++’s ->), so e.g. two data structures can use the same allocator, albeit at the cost of the indirection.

There are two minor annoyances about this design, though:

  1. Having to use a pointer to the underlying layer is sometimes wasteful:

    struct Data
    {
    	// Instantiate our allocator template
    	alias FancyAllocator!(PerformancePolicy.awesome) Allocator;
    
    	// The first data structure contains the allocator
    	LinkedList!(Node, Allocator) list;
    
    	// The second data structure contains a pointer to the allocator
    	HashTable!(string, Node, Allocator*) hashTable;
    
    	void initialize() { hashTable.allocator = &list.allocator; }
    }

    At least one of the data structures needs to use a pointer to refer to the allocator it uses. However, hashTable can know exactly where the allocator is – it’s a few bytes before its own this pointer.

    If the allocator was a field in Data alongside HashTable, we could pass it as an alias parameter – however, HashTable wouldn’t be able to refer to it, because its this points to HashTable, and knows nothing about the outer Data type or where other Data fields are.

  2. Composition via “nesting” with many layers can result in rather ridiculous code. For example, here’s two lines from my small project:

    // Clear (but don't free) the XML parser's output buffer
    xmlParser.output.writer.allocator.clear();
    
    // Get the root node of the parsed XML
    auto root = xmlParser.output.writer.dom.root;

    We could use alias this to flatten the layers, but then we have issues with name collisions between components that should not know anything about each other’s internals.

Can we do better?

Well…

D has mixins. Mixins can be used as aggregates (they don’t introduce a scope, but you can name them to refer to them explicitly). You can pass mixins as alias template parameters.

So, now we have this:

mixin template LAYER(alias BASE)
{
	// ... use BASE ...
}

and used like this:

struct Data
{
	mixin Layer0!(..params..) layer0;
	mixin Layer1!(layer0, ..params..) layer1;
	// ...
}

This does solve both of the annoyances presented above. As a bonus, all layers share the same this pointer, so (not counting compiler optimization) we can shave a few instructions for inter-component calls.

However…

Using mixins for this purpose has its own share of problems.

The biggest problem is that you can’t take the address of a mixin. This means that it’s difficult to refer to a specific layer outside the aggregate where that layer is mixed in:

struct Data // actual code from my project
{
	alias heapAllocator baseAllocator;
	mixin RegionAllocator!(FreeListNode!Node, 1024*16, baseAllocator) bulkAllocator;
	mixin FreeListAllocator!(Node, bulkAllocator) freeListAllocator;
	alias freeListAllocator allocator;
}

struct SomeNode
{
	Data* data;
	mixin LinkedList!(Node, data.allocator) list; // error
}

What we could (or should be able to) do, is add “alias allocator this” to Data, then we can use data as an allocator directly. However, this a) is not elegant (pollutes Data’s symbol list), and b) doesn’t work (but you can generate aliases by enumerating the mixin members).

Expressions are no-go for template alias parameters, and data.allocator is an expression. We can only pass a symbol accessible from the current scope with no context. If mixin pointers were a thing, this would work:

@property auto allocator() { return &data.allocator; }

But since they’re not, we have to use string mixins.

mixin template MyAllocator(alias BASE)
{
	static if (is(typeof(BASE) == string))
		enum BASE_EXPR = BASE;
	else
		enum BASE_EXPR = q{BASE};
	
	// ... use mixin(BASE_EXPR) ...
}

// ...

struct SomeNode
{
	Data* data;
	mixin LinkedList!(Node, q{data.allocator}) list;
}

String mixins solve everything. Yay…

Note that passing an “expression” containing local symbols via string mixins only works for template mixins, and not templated structs as above. This is because the scope of instantiated templates is the scope where the template is declared (so it sees symbols from the template declaration’s context, but not the instantiation’s context), whereas template mixins are opposite – when instantiated, they see symbols from the instantiation context, but not their declaration context.

This can be a problem in itself, and is another issue with using template mixins for composable components. Here’s an example…

Mixins are not types, thus not usable by themselves – to get a real type you can pass around, you have to wrap a mixin in a struct or class. This happens fairly often, so it makes sense to declare a template to do this for us:

struct WrapMixin(alias M, ARGS...)
{
	mixin M!ARGS;
}

So, just type WrapMixin!(MyComponent, ..params..) to instantiate MyComponent with the specified params.

However… the mixin alias passed to WrapMixin will be instantiated in WrapMixin’s scope. This means that if any of the parameters you passed refer to local symbols, your instantiated mixin won’t see them.

Instead, we have to do this:

/// Declares a WrapMixin template in the current scope, which will
/// create a struct containing an instance of the mixin template M,
/// instantiated with the given ARGS.
/// WrapMixin is not reusable across scopes. Each scope should have an
/// instance of WrapMixin, as the context of M's instantiation will be
/// the scope declaring WrapMixin, not the scope declaring M.
mixin template AddWrapMixin()
{
	private struct WrapMixin(alias M, ARGS...) { mixin M!ARGS; }
}

Then, every time we want to use WrapMixin, we have to add AddWrapMixin to the current scope so our mixin in the mixed-in WrapMixin sees all our local symbols.

But wait, there’s more!

What if you want to make a template that wraps a mixin in a struct, but allows specifying the mixin’s parameters at a later time? So that you could do:

mixin template ListMixin(...) { ... }
alias MixinWrapper!ListMixin List;

List!(T, myAllocator) myList;

Well, it’s the same story, but now with template templates:

/// Declares a MixinWrapper template in the current scope, which will
/// create a struct template containing an instance of the mixin template
/// M, instantiated with the arguments passed to the struct template.
/// Similar to WrapMixin, MixinWrapper is not reusable across scopes.
/// Each scope should have an instance of MixinWrapper, as the context of
/// M's instantiation will be the scope declaring MixinWrapper, not the
/// scope declaring M.
mixin template AddMixinWrapper()
{
	private template MixinWrapper(alias M)
	{
		struct MixinWrapper(ARGS...)
		{
			mixin M!ARGS;
		}
	}
}

Headache yet? 🙂

A final nuisance with mixin templates is symbol pollution, and inability of creating a strong scope. Although you can name mixins when you instantiate them, specifying the mixin name is optional, and only mandatory when two mixins declare the same identifier. Thus, mixins mixed in the same scope always see each other’s symbols. This has once led to a bug in my code where in one component I accidentally used another component’s field:

mixin template Component1()
{
	int *ptr;
}

mixin template Component2()
{
	void f(int* p)
	{
		*ptr = 42; // oops
	}
}

Conclusion: mixin templates are a tempting way to design low-overhead components, but using them this way leads to certain problems one needs to be aware of.

What can we improve in D to make the situation better?

  • Being able to take the address of mixins. This seems to me like a low-hanging fruit – the result of this operation would be the same pointer as to the entire aggregate, but the particular mixin we refer to would be embedded in the pointer’s type.

  • Some kind of templated aggregate between structs and mixins, which introduces a new symbol scope (like structs), and the instantiated scope of which is its declaration (like structs), but doesn’t have its own this pointer (like mixins), would be ideal.

  • Failing that, having this syntax work would be neat:

    struct Data
    {
    	int someField;
    	MyStructTemplate!someField s;
    }

    The idea: If we pass a local symbol (from the same aggregate) to a template’s alias parameter, then the instantiated MyStructTemplate would be aware that it is a field of the Data struct at the specified offset, and that someField lies just 4 bytes above its own this pointer. “MyStructTemplate!someField s1, s2” would result in two distinct template instantiations, since their relative offset from someField would be different.

Code:

(Note that this code is more for the sake of experimentation, and is not meant for production.)

Commit aed79189 is the last commit with struct allocators.

Comments