With C++17’s constexpr functions and C++20’s consteval specifier, it is easy to do io-independent pre-calculations of algorithms while compiling the program. This may not be useful or even possible in long running programs and is unlikely to make a difference in their performance, but in binaries that do short calculations with a set of parameters fixed at compile-time, a Sieve of Eratosthenes array, or roots of unity used for calculating DFT loaded right from the binary could make a difference.
Here’s an example of a compile-time is_prime implementation under -std=c++98.
// \file compile-time-cpp/is-prime-98.cc#include <iostream>// HasDivisorGE::value = true if v is divisible by d or any number greater// than or equal to d.template<int v,int d>struct HasDivisorGE {staticconstbool value =(v % d ==0)|| HasDivisorGE<v, d +1>::value;};template<int v>struct HasDivisorGE<v, v>{staticconstbool value =false;};// IsPrime::value = true if v is prime, flase otherwise.template<int v>struct IsPrime {staticconstbool value =!HasDivisorGE<v,2>::value;};int main(){std::cout <<7<<" : "<< IsPrime<7>::value <<std::endl;// fatal error: template instantiation depth exceeds maximum of 900// (use ‘-ftemplate-depth=’ to increase the maximum)// std::cout << 2000 << " : " << IsPrime<2000>::value << std::endl;return0;}
We are sweeping all values from 2 to a - 1 to check if any of them divide a, which is not efficient. To improve that, we can implement a compile-time sqrt using binary search or Newton’s method. In the following examples, I’ll stick to the full sweep all the way to a - 1 for simplification, but the square root improvement can be plugged in in all of them.
The first problem with this approach is readability. Tedious template syntax make the code harder to understand and simple modifications might cause many lines to change. In addition to that, implementing the actual Sieve algorithm with good performance in a top-down, recursive, template-friendly format requires more effort. The code will also look a lot more convoluted.
A more serious problem is the maximum depth issue. In this case, a bit disappointing as well, given that we wouldn’t need to look past HasDivisorGE<2000, 2> to see that 2000 is not prime.
The following snippets are takes on eliminating these two problems.
C++14
Equipped with constexpr and enable_if, let’s try to fix the depth issue. Here is a try at limiting the template instantiation when it is not needed.
// \file compile-time-cpp/is-prime-14.cc#include <iostream>template<int v,int d,typename=std::enable_if_t<(d <= v)>>struct HasDivisorGE {staticconstbool value =(d < v)&&((v % d ==0)|| HasDivisorGE<v, d +1>::value);};template<int v>struct IsPrime {staticconstbool value =!HasDivisorGE<v,2>::value;};int main(){// In instantiation of ‘const bool HasDivisorGE<7, 7, void>::value’:// recursively required from ‘const bool HasDivisorGE<7, 3, void>::value’// required from ‘const bool HasDivisorGE<7, 2, void>::value’// required from ‘const bool IsPrime<7>::value’// required from here// error: no type named ‘type’ in ‘struct std::enable_if<false, void>’// | ((v % d == 0) || HasDivisorGE<v, d + 1>::value);// ^~~~~std::cout <<7<<" : "<< IsPrime<7>::value <<std::endl;// fatal error: template instantiation depth exceeds maximum of 900// (use ‘-ftemplate-depth=’ to increase the maximum)std::cout <<2000<<" : "<< IsPrime<2000>::value <<std::endl;return0;}
This won’t compile. In HasDivisorGE<v, d>::value with say, [v = 7, d = 7], we already know that (d < v) is false, however the lazy evaluation of && helps with the value of HasDivisorGE<v, d + 1>::value if it was already there, not with the initialization of the class template HasDivisorGE with [v = 7, d = 8]. Even though we already know the result at [v = 7, d = 7], we haven’t been able to keep the template instantiation from propagating further.
As a result, this approach also fails to keep HasDivisorGE<2000, 2> from exceeding the maximum instantiation depth. std::enable_if imposes the limitation after an instantiation is requested. We somehow need to stop the “unnecessary” instantiation from being requested in the first place.
C++17
Using an immediately invoked function expression (to turn multiple statements into a single expression) and if constexpr, we can do:
// \file compile-time-cpp/is-prime-17.cc#include <iostream>template<int v,int d>struct HasDivisorGE {staticconstexprbool value =[]{ifconstexpr(d >= v){returnfalse;}elseifconstexpr(v % d ==0){returntrue;}else{return HasDivisorGE<v, d +1>::value;}}();};template<int v>struct IsPrime {staticconstbool value =!HasDivisorGE<v,2>::value;};int main(){std::cout <<7<<" : "<< IsPrime<7>::value <<std::endl;std::cout <<2000<<" : "<< IsPrime<2000>::value <<std::endl;// fatal error: template instantiation depth exceeds maximum of 900// (use ‘-ftemplate-depth=’ to increase the maximum)// std::cout << 2003 << " : " << IsPrime<2003>::value << std::endl;return0;}
Good, the code inside if constexpr just has to be well-formed. If the condition is false, the enclosed code will not be evaluated. IsPrime<2003> still exhausts the depth however. To mitigate that, we can use constexpr functions:
// \file compile-time-cpp/is-prime-17-constexpr-func.cc#include <iostream>constexprbool is_prime(int v){for(int i =2; i < v; i++){if(v % i ==0){returnfalse;}}returntrue;}template<int v>struct IsPrime {staticconstexprbool value = is_prime(v);};int main(){std::cout <<7<<" : "<< IsPrime<7>::value <<std::endl;std::cout <<2000<<" : "<< IsPrime<2000>::value <<std::endl;std::cout <<2003<<" : "<< IsPrime<2003>::value <<std::endl;return0;}
Where struct IsPrime is left in to keep main() similar to previous examples. The allowed number of loop iterations is a limitation here, similar to the maximum depth issue. However for evaluating a single value per template instantiation, the default compiler settings for maximum number of iterations seem to be more permissive than the maximum instantiation depth.
C++20
When a function is marked with consteval, every potential call to it must produce compile-time results. This way, we can force functions to be compile-time evaluated, making them uncallable from the a non-constexpr context. Contrary to constexpr functions, non-constexpr expressions are not allowed in consteval function bodies. consteval functions appear to be faster in this case as well. In the Sieve example, a consteval function generates the sieve array ~2 times faster than a constexpr function (g++ 10.2.0 on Linux).
// \file compile-time-cpp/is-prime-20-consteval-func.cc#include <iostream>#include <array>template<int v>constevalstd::array<int, v +1> sieve(){std::array<int, v +1> arr ={};for(longlong i =2; i <= v; i++){if(arr[i]){continue;}for(longlong j = i * i; j <= v; j+= i){ arr[j]=1;}}return arr;}int main(){auto sieve_array = sieve<12345>();std::cout <<7<<" : "<< sieve_array[7]<<std::endl;std::cout <<2000<<" : "<< sieve_array[2000]<<std::endl;std::cout <<2003<<" : "<< sieve_array[2003]<<std::endl;size_t i =0;std::cin >> i;std::cout << sieve_array[i]<<std::endl;return0;}
Here, we can end up doing a lot of duplicate work in compile time if we are not careful since for example sieve<1001> cannot use sieve<1000>’s result, but this can be resolved or improved by creating an indirection level over the sieve template. On the other hand, the array easily escapes to run-time land, allowing it to be used in non-constexpr contexts.
Down the rabbit hole: Template interface around a C library in C++
Calling C code from within C++ happens quite a lot. With isolation of coding standards in mind, it makes sense to try to keep the C++ code separate from the C code. How?
Here I’m going to create an interface around libibverbs, to be able to frame the issue around a real-world problem and as you might guess from the title, this post has nothing else to do with libibverbs. I won’t be discussing its internals, neither am I going to assume any knowledge about it.
One problem however is running the examples. Since you probably do not have infiniband hardware on your laptop, you won’t be able to run the examples successfully, but you’ll be able to compile them by installing libibverbs using your distro’s package manager, and also see at least the error handling part in action, as the calls will fail since there would be no device on your everyday computer for the userspace library to talk to.
Other libraries with “resource-based” APIs can probably be be treated similarly. I just don’t want to invent an imaginary C API, casting doubt on the usefulness of the discussion.
Resource based APIs?
Many C libraries, specially the ones which provide a way to access a particular hardware or a resource of a lower abstraction provide a resource management API that works in pairs: there are function calls that create/allocate/whatever the resources, and there are ones that delete/free/etc. the resources. I think the popularity of this way of thinking can be traced back to the UNIX syscall API and how the terminologies have propagated up the stack as we’ve built different layers of abstractions.
libibverbs, the userspace library for talking to infiniband devices works this way too (for the most part). The first thing you’d probably do while working with this library is opening a device:
// $ man ibv_open_deivcestruct ibv_context *ibv_open_device(struct ibv_device *device);// returns a pointer to the allocated device context, or NULL if the request fails.int ibv_close_device(struct ibv_context *context);// returns 0 on success, -1 on failure.
One thing you’ll probably do after opening a device is allocating a protection domain:
struct ibv_pd *ibv_alloc_pd(struct ibv_context *context);// returns a pointer to the allocated PD, or NULL if the request fails.int ibv_dealloc_pd(struct ibv_pd *pd);// returns 0 on success, or the value of errno on failure.
We don’t need to discuss what these mean. The point is these and many other resources work this way.
An interesting but kind of natural note you’ll come across in the man pages says that if you happen to free these resources in the wrong order, say, ibv_close_device the struct ibv_context* before your get rid of an ibv_pd corresponding to that class with ibv_dealloc_pd, there might be errors. Reading on, you’ll see why this reinforces the argument that we’d better encapsulate this logic when writing code in C++.
(Psst.. If you know what RAII is click here to skip over the following material that you’re probably familiar with so you won’t kill me the next time we meet.)
The problem
There’s nothing wrong with the above API per se. In fact, there’s barely enough going on for anything to go wrong. But just given the above “look and feel”, you’re probably already concerned about the use of these in your C++ application because of the Ssme old dilemma: who’s responsible for cleaning up who by calling what. The sophisticated task of resource management in the face of possible errors has to be done manually, and with the imposed order in creating/deleting the resources, it’s likely as complex as all the other low level resource management scenarios, (e.g. file descriptors), for which we have wrappers in C++ library. (e.g. std::fstream)
All the complexity, machinery, rules, and conventions in C++ alongside a number of the books about the language are there to accomplish probably two and a half things, one of which is that in the following piece of code (from cppreference) …
… you (unless willing to deal with consequences (exceptions)) can refrain from explicitly calling close on the std::ifstream and the std::ofstream objects after you’re done with them. Why this is desired and how managing resources correctly (mainly defining their construction, duplication, and destruction) makes a lot of things click and fall into place (e.g. the fact that there’s no finally block in C++) is a longer story, however by accepting that there’s value in managing resources like this, we now have the incentive to create a C++ friendly interface around libibverbs’s resources.
A simple take
From this point on I’ll be referencing code that lives at https://github.com/farnasirim/c-iface. This section’s code is under c-iface/a-simple-take.
(If you know how to write a class like std::unique_ptr from scratch, click here to skip over some stuff you already know)
The first thing that comes to my mind: let’s encapsulate resource management. As an example, let’s try to encapsulate the management of an ibv_pd. Here’s one way:
// c-iface/a-simple-take/ib.cc#include "ib.h"#include <exception>IbPd::IbPd(struct ibv_context *ib) {struct ibv_pd *maybe_pd = ibv_alloc_pd(ib);if(maybe_pd == NULL) {// for examplethrowstd::exception(); }pd_ = maybe_pd;}struct ibv_pd *IbPd::get() const {returnpd_;}IbPd::~IbPd() {if(pd_ != NULL) {int status = ibv_dealloc_pd(pd_);if(status) {// Oops, cannot throw out of the dtor. Not much we can do anyway. } }}
// c-iface/a-simple-take/main.cc#include <infiniband/verbs.h>#include "ib.h"int main() {// In the real world this will be an actual ibv_context obtained by calling// `ibv_device_open`.struct ibv_context *device_context = NULL; IbPd pd(device_context);// Pass the underlying pointer where required in the future: pd.get()return0;}
A few important things to notice:
We had to explicitly delete IbPd(const IbPd&) = delete;. Otherwise we would have been allowed to write code like IbPd duplicated_pd = pd; in main(). This would be a disaster as we’d be ibv_dealloc_pding the same underlying ibv_pd two times when the two IbPds (pd and duplicated_pd) would eventually go out of scope. Similar story for the assignment operator, although we can manage the underlying resource in a well defined manner and provide a correct assignment operator. That’s not the main discussion here therefore I have decided to delete it for now.
Notice that we were unable to effectively handle the possible error in the destructor. Pretty much the only solution would be a providing a public method IbPd::close() similar to fstream::close() and allow the caller to explicitly run the destructor and catch any exceptions that it throws. This issue is important, but it’s parallel to what I’m discussing in this post. This will be present in the other code snippets too, but I’m going to ignore it here to concentrate on the main problem.
The fact that the “ibv_alloc_pd” is being called behind the scenes is, well, hidden from the API user.
A decent take
(No forward links this time: Even if you’re a C++ wizard, for the love of God read this section so you’ll know what the discussion is about)
We can greatly simplify IbPd by using std::unique_ptrs:
This makes things much simpler. There’s no need to remember out of the blue that you need the copy constructor deleted, as the compiler cannot automatically generate it for us now since std::unique_ptr deletes it. The dangerous IbPd duplicate_pd = pd; will therefore not compile.
We have to remember to override the std::unique_ptr’s deleter to avoid the disastrous default, namely [](struct ibv_pd *pd) { delete pd; } to take place upon destruction.
This is far from good: the next thing you’ll do after creating a protection domain (pd) is creating a memory region (mr). Before you’re able to do that, you’ll have to write a whole bunch of boilerplate code to encapsulate the mr creation too:
ibv_reg_mr, ibv_dereg_mr - register or deregister a memory region (MR)struct ibv_mr *ibv_reg_mr(struct ibv_pd *pd, void *addr, size_t length, int access);int ibv_dereg_mr(struct ibv_mr *mr);
So here we go again.
class IbMr {public: IbMr(const IbPdHandle&, void*, size_t, int);std::unique_ptr<struct ibv_mr, void_deleter<ibv_mr>> ibv_mr_;};IbMr::IbMr(const IbPdHandle& pd, void* addr, size_t length, int flags):ibv_mr_(nullptr, ibv_dereg_mr ) /* return value will be ignored by std::unique_ptr */{struct ibv_mr *mr = ibv_reg_mr(pd.ibv_pd_.get(), addr, length, flags);if(mr == NULL) { perror("ibv_reg_mr");std::abort(); }ibv_mr_.reset(mr);}
That’s too much duplicate boilerplate code to achieve a seemingly simple, or at least easy to describe (in human language) operation. There has to be a better way.
Enter templates
Imagine an xkcd about C++ templates here. (I’m actually surprised that I couldn’t find one)
Well I wish I could explain this final part in actual snapshots, showing how I actually came up with it. Unfortunately I found myself unable to switch back and forth between documenting the process and actually going forward. Even if I had written everything down, my failed solutions would have made a huge pile of code, only useful for checking to see if your compiler will include specific personal life threats against you among the compile errors.
Therefore I’ll take a “horizontal” approach here, presenting the fragments of the solution component by component. Caveat: Some steps may seem magical. Bear with me.
What would make me happy
I’d like to refrain from writing multiple resource handler classes by hand. Here’s roughly what I’d like to do in ib.h to be able to use interfaces to ibv_alloc_pd and ibv_reg_mr in my C++ application:
using IbPd = some_magical_template<ibv_alloc_pd, maybe some other params>;using IbMr = some_magical_template<ibv_reg_mr, maybe some other params>;
A possibly controversial design decision that I made was a one to one mapping from C++ classes to resource function pairs in the C library. That is, instead of having for example an IbPd class, I went for creating an IbAllocPd from the ib_alloc_pd resource allocator. And, I don’t want maybe some other params to be too expressive and “difficult” to write. Oh no. I want it be a constant number of parameters, only dependent on the names of the allocator and the deleter. We’re way past the point of sanity. Let’s get .
I hear you shouting and you have every right to hate me now:
Q: What about resources that can be created using multiple functions? (e.g. ibv_reg_mr, ibv_reg_mr_iova) A: Either forget about them for now (don’t use them interchangeably, and/or duplicate your interfaces, which surprisingly does work in most scenarios I thought about), or… well, give up and create a new resource type (e.g. IbPd) and make the two “factory” classes inherit the resource class, and use the resource super class in interfaces. (This is still not a “solution” because a decision to add a new “factory” of a type that already has a factory requires a surgery on every single interface that has been using the previous one.
Q(Hyperbole? Concern?): Class names will end up sounding like function names. A: Well I would have liked them to sound like actual resource names too, but making them just a transliteration of the ibv_* functions makes writing the class definitions like using IbMr = some_magical_template<ibv_reg_mr, maybe some other params>; that go in ib.h almost trivial: no more decision making. If you have a pair of resource allocator/deleters, you can quickly get your resource manager class in compile time as a template instance. The only complex task that we have to go through to add a new function to the interface would be capitalizing the original name and removing the underscores from it, for which you can type the following into bash: sed -Ee 's/(^.)?(_.)?/\U\1\2\E/g'<(echo"ibv_function_name"). But really, naming them anything other than the function that is actually being called will mask important information at the call site. Why not make the constructor call self documenting?
I’ll explain how I did it but it’s dangerous to go alone: we’ll have to equip our sleeves with a couple of handy tricks.
Capturing variadic template args
It easy to realize that we’ll need a way to somehow capture any number of parameters of any type, as the resource allocator functions come in all sorts of shapes and sizes:
This is not trivial because we’re not able to directly “name” the variadic args. Let’s write the following FnpTypes traits class to capture the return type and the argument types of any function pointer using template specialization:
With the hope of using the likes of FnpTypes<ibv_open_deivce>::ReturnType or FnpTypes<ibv_reg_mr>::FuncArgs later on.
During template declaration (1), we say hey, FnpTypes is a struct template and takes a single type argument. That’s all. EXCEPT, we’ll only provide the definition for function pointers (2). If you thought you knew what template specialization was, but you’re still skeptical of what’s going on with the template parameters in 2, have a look here:
// 1template<typename T>class Vector;// 2template<>class Vector<int> {// definition of a vector class};
It’s the exact same thing and now we can conclude that the template params in 2 are just “parametrizing” (=helping to define) the type(s) that the specialization will apply to.
Back to the main issue: using FuncArgs = Args; won’t compile. Let’s go to the solution:
How would this help? Well, first of all its sole presence doesn’t cause a compile error. More importantly, the Pack can be pulled away by pattern matching in the type parameters. Here’s an example usage:
#include <functional>// The second template parameter has a default type of ↓template<typename FunctionPointer, typename = typename FnpTypes<FunctionPointer>::PackedArgs>class Example;using SpecType = int (*)(int);template<typename... Args>class Example<SpecType, Pack<Args...>> {// Example specilization, where the first argument is "int (*)(int)", and the// second one "pattern matches away" the `Pack<>`, and names the inner// `Args...`, allowing us to use it directly:public: Example(SpecType fptr): fptr_(fptr) { }int forwarder(Args&&... args) {return close(std::forward<Args...>(args)...); }private: SpecType fptr_;};
(On a side note, if you liked how that little arrow was correctly aligned with the start of the type description, you’re gonna like the alt text of https://xkcd.com/688/)
One more thing that is not hard to realize is that we need some way of intervention when the creations/deletions of the resources go wrong, at least for debugging purposes. For now lets assume we’re going to log a message and exit the program if anything wrong happens for all of the resource creation/deletion functions. Here’s one way to do this:
All they do is forward the args to the underlying function pointer and print a message if anything goes wrong. The usage would look something like:
auto new_deleter = int_deleter_wrapper(ibv_dealloc_pd, "ibv_dealloc_pd");
And then you’ll probably pass the new_deleter as the deleter to a std::unique_ptr somewhere.
But that requires writing that little string literal. Why do I not like it? The compiler will never complain about its correctness. (what if you copy/paste the above line for different types and forget to change the message string?) So how do we do this? (If you’re thinking of using macros, click the button to claim your reward: )
// c-iface/a-template-take/fnp_traits.h#ifndef FNP_TRAITS_H_#define FNP_TRAITS_H_#include <typeinfo>#include <algorithm>#include <string>// Want to accept any function pointer as value:// For every type T, accept the type and a value of that type: template<typename T, T f>// As can see this is not "tight": f can have any type really, but that's good// enough for a function that will only be used for debugging purposes. And if// you're concerned, you can make it as "tight" as you need with very little// work.template<typename T, T f>struct FnpTraits {staticstd::string name() {std::string pretty_name = __PRETTY_FUNCTION__;// type of f will be written in front of it like so:// f = ibv_alloc_pdstd::string start_marker = "f = ", maybe_end_chars= ";,]";// Diferent delimiters are there because of clang/gcc, and the possibility// that the f might be the last thing written in __PRETTY_FUNCTION__// as it will look something like [ T = text text, f = text text ].auto start_index = pretty_name.find(start_marker) + start_marker.size();auto end_index = pretty_name.find_first_of(maybe_end_chars, start_index);return pretty_name.substr(start_index, end_index - start_index); }};#endif // FNP_TRAITS_H_
This is not exactly the same thing, but it will extract the type of f from the pretty name and works both in gcc and clang (and probably nothing else). Of course you’ll not use this for anything serious, right? RIGHT?
But seriously these last two class templates work well for debugging purposes and make things convenient, specially since they allow you to specialize per class for a correct/different behavior.
Believe it or not, at this point we have all we need for the IbResource class template that will provide a C++ style resource management scheme for our C types from libibverbs:
// c-iface/a-template-take/ib.h#ifndef IB_H_#define IB_H_#include <memory>#include <functional>#include <type_traits>#include <infiniband/verbs.h>#include "fnp_traits.h"#include "fnp_types.h"#include "ib_utils.h"// Ask for the type of the Factory (allocator func), and the factory itself.// Same goes for the deleter.// Finally using the packing technique, ask ask for the Args that are// extracted from the function pointer in the `FnpTypes` trait.template<typename Factory, Factory f, typename Deleter, Deleter d,typename = typename FnpTypes<decltype(f)>::PackedArgs>class IbResource;// The only reason that we need to specilize (as opposed to defining the template// right away is pattern matching the Args... out of the decltype(f)>::PackedArgs.template<typename Factory, Factory f, typename Deleter, Deleter d, typename... Args>class IbResource <Factory, f, Deleter, d, Pack<Args...>> {public:// Removing the pointer, and then working with the type makes things a bit// more readable in the uniquee_ptr and the get function. Again, we'll have to// do a bit more work to do the correct thing in the rare cases when the// functions that return a struct as opposed to a pointer to a struct.using ResourceType = std::remove_pointer_t<typename FnpTypes<decltype(f)>::ReturnType>;// This is hiding the flexibility of std::unique_ptr from the user of// IbResource. Might make more sense to directly ask for the final deleter// type when you're creatin a concrete IbResource from the IbResource template.std::unique_ptr<ResourceType, VoidDeleter<ResourceType>> ptr_; IbResource(Args... args): ptr_( factory_wrapper(f, FnpTraits<Factory, f>::name())(std::forward<Args...>(args)...), int_deleter_wrapper(d, FnpTraits<Deleter, d>::name())) { } ResourceType *get() const {returnptr_.get(); }};// A function like ibv_device_context_by_name is not present in the ibv library.// The way it works is you obtain a list of devices, iterate over them, and open// whichever you chose.// What do we do? We create our own function, do the resource allocation// manually, and wrap it in an IBResource similar to original ibv_* allocators.// See ib.cc for the implementation.struct ibv_context *ibv_device_context_by_name_(constchar *name);using IbvDeviceContextByName = IbResource<decltype(&ibv_device_context_by_name_), &ibv_device_context_by_name_,decltype(&ibv_close_device), &ibv_close_device >;using IbvAllocPd = IbResource<decltype(&ibv_alloc_pd), &ibv_alloc_pd,decltype(&ibv_dealloc_pd), &ibv_dealloc_pd >;using IbvRegMr = IbResource<decltype(&ibv_reg_mr), &ibv_reg_mr,decltype(&ibv_dereg_mr), &ibv_dereg_mr >;#endif // IB_H_
Is the flaw with naming, and the fact that for example IbvAllocPd is the name of an object which is essentially a struct ibv_pd, and the possibility of a future shotgun surgery because of multiple allocators worth the easy creation of new interfaces? I think it depends on the usage and how deep these classes are expected to go in your class hierarchy. Intuitively, the fact that you’re using a very low level resource hints that regardless of the interface you choose, its a good idea to keep them encapsulated and far away from the logical core of the application. This does make sense in my case, particularly with libibverbs. YMMV.
