The problem with policy-based design

by Jonathan

Policy-based design is a great way for library authors to provide more flexibility to the user. Instead of hard coding certain behaviors, policy-based design provides various policies the users can select to customize the behavior. If done properly, a library author can accommodate all use cases with a single implementation.

I’m a big fan of policy-based design for that reason. Whenever there’s a possible trade-off, where multiple solutions are possible, each with their own set of advantages and disadvantages, I make the decision available to the user. Instead of favoring a certain use case, I favor all of them. This is for example what I did with my variant implementation.

However, policy-based design isn’t perfect. In particular, it has a great problem: It creates lots and lots of different and incompatible types.

Quick introduction to policy-based design

The most popular example of policy-based design out in the wild are probably the allocators of STL containers. Take std::vector for example: it is a dynamic array of elements. As it is dynamic, it has to allocate memory somehow. But there are many strategies to allocate memory, each best for a given situation. If the memory allocation was hard coded, std::vector would be unusable for a wide range of performance critical applications.

Luckily, it isn’t hard coded. Instead, there is an allocation policy - an Allocator - that controls how the memory is allocated.

And a whole bunch of other things.

std::vector has a second template parameter - besides the element type. This is the allocation policy. You can define your own class with certain member functions, and plug that in. Then std::vector will use your way of allocating memory.

In most instances of policy-based design there is a policy implementation that is okay in most cases. That’s the case with std::vector as well. Using new for the memory allocation is good enough in the general case. As such an Allocator using new - std::allocator - is the default policy. It is used when no other Allocator is given.

So a regular user can use std::vector without worrying about allocators. Only an expert wanting full control needs to care about that. That’s the beauty of policy-based design.

The problem with policy-based design

Using a template parameter for the policy is the most common way of implementing policy-based design. The reason is simple: Templates are a zero cost abstraction, there is no runtime cost associated with using them.

As Alexandrescu put it, your class now becomes a code generator for different implementations.

I’m quoting Modern C++ Design from memory here.

But different template instantiations are different types. Your std::vector<int, pool_allocator> is a different type than std::vector<int, stack_allocator>, even though both are dynamic arrays of ints!

This means that if you have a function returning a std::vector<int, pool_allocator> and one taking a std::vector<int, stack_allocator>, they are not compatible, you have to convert the different vector types, which is expensive.

This is a particularly big problem for vocabulary types - types, which are meant to be the de-facto way of representing a situation. Take std::optional for example. It is meant to be the de-facto way of representing an object that might not be there. Or std::variant - it represents a union of types.

Both aren’t really a great implementation of the concept (in my opinion), but that’s a different topic.

Vocabulary types are essential for building APIs, and they are incredibly useful there.

Seriously, I’m currently working on an - awesome! - new project where I can use my type_safe library from the beginning. Only having ts::optional, ts::object_ref (basically a non-null pointer) and ts::optional_ref (basically a pointer) allows so much better APIs. But I’m drifting away from policy-based design…

But given the rule vocabulary types have in API design, it is from uttermost importance that you do not run into the problem of different types! If you have different variant implementations in a project, your APIs are incompatible.

It’s a shame the standard library versions of vocabulary types do not use their full potential and are coming too late.

This means that it is difficult to use policy-based design there as different policies have different types.

So policy-based design often involves creating different types, which can lead to API incompatibility. If you want to workaround it, you have to use templates all over the place.

But I don’t want to talk about problems only, I want to present solutions. So how can we solve the problem?

Solution 0: Don’t use policy-based design

I love zero indexing if I have points that aren’t really points.

The most obvious solution is simple: don’t use policy-based design. It is extremely powerful, but powerful things have the tendency of being overused.

Take my ts::variant for example, which is in fact ts::basic_variant with a policy controlling whether empty state is allowed and what happens if a move constructor throws. This was a big criticism of my ts::variant, as it is a vocabulary type.

And in hindsight, I probably went overboard with it: I should have just provided ts::variant<Ts...> and ts::variant<ts::nullvar_t, Ts...> for a std::variant like variant and one with empty state. There is no problem there as those two are substantially different types - like std::vector<int> and std::vector<float>.

So whenever you want to implement policy-based design, think whether it is really worth it. Ask yourself: Is the customization really that important? Is there a good general solution which is sufficient for 99% of users? And most important: Does a policy change the fundamental behavior of your class?

If you can give the class with a certain policy a new name, this is a good hint that the policy is a fundamental change in behavior or that it is not really policy-based design but mere “I want to prevent code duplication”. The latter case is fine but consider hiding the “policy” and document the two classes as separate types sharing a common interface.

Solution 1: Use type-erasure

The most common solution to the policy-based design problem is type-erasure.

Take the smart pointers of the standard library for example. std::unique_ptr has a Deleter - a policy that controls how the object is freed. It is a separate template argument, so it creates a separate type.

But std::shared_ptr doesn’t have a Deleter template argument, even though you can also pass in a policy defining how to free the object. That’s possible because the implementation uses type-erasure. Instead of statically storing the Deleter, std::shared_ptr stores it type-erased, hides it away with dynamic memory allocation and virtual functions or callbacks.

And that’s the downside of using type-erasure: It is usually more expensive than the template argument version.

The standard library has a good guideline where type-erasure is used for policies: If there is already some form of indirect calls going on, use type-erasure. std::shared_ptr already has a control block on the heap, it can easily store a policy there as well.

But in other cases the overhead of type-erasure can be ignored. For example an input stream that has a policy from where to read can easily use type-erasure: The overhead of reading data from a file is much bigger compared to an indirect function call.

And in fact: that’s what std::istream is doing with the std::streambuf class hierarchy!

If you have something where policy-based design is essential and type-erasure would have too much overhead in some situations, you can also use policy-based design itself to solve the problem! Simply define a policy that uses type-erasure to forward to any other policy and use the type-erasure policy in all APIs.

That’s what my new Allocator model of memory is using: It doesn’t use type-erasure by default, but there is memory::any_allocator_reference which can store a reference to any allocator. You can use the memory::vector<T, memory::any_allocator> alias to have a std::vector that can use any allocator without changing the type.

That’s also what the new standard polymorphic memory resources are doing, even though type-erasure is the default.

There is also a different form of type-erasure you can employ. Consider the hypothetical function taking std::vector<int, stack_allocator> again. If the function doesn’t need to actually modify the container, just walk over it, you can use something like my ts::array_ref. which is a reference to any contiguous memory block. Then the function can accept anything that is contiguous, so also the std::vector<int, pool_allocator, i.e. a different policy.

Solution 2: Enforce policies automatically

My optional implementation in type_safe does also use policy-based design. There is ts::basic_optional accepting a storage policy. This policy controls how the optional value is stored, when it is invalid etc.

Originally I did it to easily implement both ts::optional - a “regular” optional type - and ts::optional_ref - a fancy pointer - without code duplication. And this is not a problem as ts::optional is a vocabulary type for an optional type, and ts::optional_ref for an optional reference to a type.

However, then I also implemented compact optional facilities.

The general optional implementation uses std::aligned_storage and bool invalid. This has a space overhead, however. For example, ts::optional_ref just stores a pointer, as it already provides a way to differentiate between “stores a value” and “doesn’t store a value”. The same can be done for other types.

But then someone might use a ts::compact_optional in an API whereas someone else accepts a regular ts::optional, leading to the policy-based design problem. There is a solution available though.

What we really want is an optional of type T. And that optional might be implemented in different ways. For example if T is a reference, use ts::optional_ref, when T is my_special_class use some compact optional, otherwise use the default one.

If an API always uses the “right” policy for a given type, the problem doesn’t happen. Selecting the right policy can be automated. In type_safe I have ts::optional_storage_policy_for, a trait which can be specialized for own types to override the optional storage policy. Then ts::optional_for uses that trait to select the best optional implementation for a type.

In general: If you have a policy that heavily depends on some other template parameter, consider automating the policy selection process, so that all foo<T> objects use the same policy for a given T. This way conceptually same types are actually the same types.

Solution 3: Use templates?

The ideal solution would be to simply use templates - everywhere you use a class with a policy-based design. So for example, never write std::vector<int> but std::vector<int, Allocator>, so you can catch all possible policies.

But using templates has technical disadvantages like requiring that everything is in the header file or code bloat. Maybe one day C++ will have a module system and better compilers so will not an issue anymore.

Conclusion

That was a rather abstract blog post without any code or general advice. I’d love to present a great solution to the problem, but I simply can’t, as there is none (I’m aware of).

The only general advice I can give is:

Policy based-design is great, it makes libraries much more generic. But sadly it also has a problem that can’t really be avoided.

This blog post was written for my old blog design and ported over. If there are any issues, please let me know.