This article assumes some basic knowledge of protobuf and Qt.

Protobuf is a nice library for data serialization. It is fast and efficient. The API is ugly (which is not uncommon for google products), but usable. I have played a bit with protobuf with the aim to replace a self-written serializer in a C++ Qt project. As usual the difficulties start with deserialization (maybe that is the reason why all these tools are named “serializers”, I am not aware of any product named “deserializer”). For my current project (a client server application based on message passing) protobuf has two drawbacks:

1. No transport mechanism
2. No dynamic deserialization

The first point means protobuf does not define any method to send/receive serialized messages over the wire, it even defines no ways to send/receive a sequence of messages over one connection. That is not a major problem and can be fixed with a few lines of code.
The second point is more important: the old mechanism generated a Qt-signal from the receiving function with a signature like this:

signal:
  void gotMessage(const QVariant& v);

The current message was wrapped into a QVariant. Our old serializer (we used our own message file compiler comparable to the protoc compiler) generated the necessary wrapper code and the right qRegisterMetaType() calls. So each message got a unique type-id. For the wire transfer we used a QDataStream, sent first the type-id and after that the serialized message. The receiving side was able to create the right type from this id (wrapped into a QVariant) and fill it from the serialized message. Each client (in Qt speech: the slot connected to the signal above) was able to restore the original type:

void handleMessage(const QVariant& v);
if (v.userType() == ExpectedMessage::typeId) {
  ExpectedMessage msg = v.value();
  handleExpectedMessage(msg);
}

v.userType() returns the type-id transferred over the wire, where ExpectedMessage::typeId is the “static” type-id returned from qRegisterMetaType(). So each module can register itself as a listener (in Qt: connect) for the gotMessage() signal, filter out the interesting message types and handle them.

This is what I mean by “dynamic deserialization”: feed the deserializer with some data and get back a parsed instance of the right message class. In protobuf each message declared in .proto file becomes a C++ class derived from a basic Message class. That is the same
mechanism we used in our implementation, which makes porting a bit easier. Protobuf does not guess the message type, to read a message protobuf needs know which kind of message it has to read. In an application one have to instantiate the right Message subclass and read the data:

ExpectedMessage msg;
msg.parseFromArray(...)

ExpectedMessage is a class declared as a message in .proto file and derived from google::protobuf::Message. But what I would like to have is:

Message *msg = magicallyReadTheMessage();
if (name(msg) == "expectedmessage") {
  ExpectedMessage *sub = dynamic_cast<ExpectedMessage*>(msg);
  handleSubclass(sub);
}

So is this possible with protobuf too? Fortunately yes, with two small tricks: we include the .proto file into our application and use some magic from the protoc compiler.

The first thing to do is to make the source code of the .proto file available at runtime. In the Qt world we just create a resource file and include the .proto file. (In a real world application, where we create different executables for server and client, we put this resource and all the message handling code into a library and link it to both client and server). Now we read the .proto file at startup and generate type-id from each message in the same manner with qRegisterMetaType() in the old version:

QFile data(":/demo.proto");
if (!data.open(QIODevice::ReadOnly | QIODevice::Text)) {
  qFatal("cannot read proto resource file");
return;
}
QByteArray protoText = data.readAll();

Now we have a string with our messages and can parse it (courtesy goes to https://cxwangyi.wordpress.com/2010/06/29/google-protocol-buffers-online-parsing-of-proto-file-and-related-data-files/):

using namespace google::protobuf;
using namespace google::protobuf::io;
using namespace google::protobuf::compiler;

FileDescriptorProto file_desc_proto;

ArrayInputStream proto_input_stream(protoText.data(), protoText.size());
Tokenizer tokenizer(&proto_input_stream, NULL);
Parser parser;
if (!parser.Parse(&tokenizer, &file_desc_proto)) {
  qFatal("Cannot parse .proto file");
}

Now we can read all message types from file_desc_proto and generate a unique id for each message. In fact we push each message name onto a vector and use the index as id:

    using MessageNames = std::vector<std::string>;
    MessageNames messageNames;
    for(int i=0; i < file_desc_proto.message_type_size();++i) {
        const DescriptorProto& dp = file_desc_proto.message_type(i);
        qDebug() << i << dp.name().c_str();
        messageNames.push_back(dp.name());
    }

All this stuff goes into a initialization function which have to be called at startup. Note I have ignored module prefix stuff (protobuf messages are declared inside a module and get names following the schema module.submodule.messageName).

Sending a message is straight forward:

void sendMsg(const Message& msg) {
    auto id = findIndexOf(msg.GetTypeName()); // looks up a message with this name in the messageNames vector
    QByteArray data((char*)&id, sizeof(id));
    string s = msg.SerializeAsString();
    data.append(QByteArray(s.data()),s.size());
    sendBuffer(data); // send a QByteArray however you like...
}

The corresponding receive method may look like this:

void recvMsg(const QByteArray &data) {
  MessageNames::difference_type idx = *(data.data());
  const string& name = messageNames[idx];
  const google::protobuf::Descriptor *desc = google::protobuf::DescriptorPool::generated_pool()->FindMessageTypeByName(name);
  const google::protobuf::Message *protoMsg = google::protobuf::MessageFactory::generated_factory()->GetPrototype(desc);
  google::protobuf::Message* resultMsg = protoMsg->New();
  resultMsg->ParseFromArray(data.data()+sizeof(MessageNames::difference_type), data.size()-sizeof(MessageNames::difference_type));
  emit handleReceivedMsg(*resultMsg);
  delete resultMsg;
}

After receiving the message type id and looking up the message name in our messagesNames vector we look up a Descriptor for this message and generate a prototype of this message type by calling GetPrototype(). The protoMsg is already an instance of the right subclass. Each protobuf message contains a virtual New() method, to create a fresh instance of this type. We use this to create our own instance and filling it with the received data. Finally we inform all our listening clients about the new message (in Qt speech: emit a signal).
One remaining drawback is, that we need to delete the message after processing it. So we cannot use this signal in queued connections. In my case this is not a problem.

The client (Qt: the receiving slots) can now filter for the right messages:

void handleReceivedMsg(const Message& msg) {
  if (msg.GetTypeName() == "therightmessage") {
    const TheRightMessage& trm = dynamic_cast<const TheRightMessage&>(msg);
    handleTheRightMessage(trm);
  }
}

This code looks very similar to our old code we started with.

Another nice feature of the inclusion of the .proto file is the possibility to create a hash of the contained .proto messages and send it to the server on connect. So we can ensure that both client and server use a compatible .proto declaration.

Of course one could send the message names (instead of the type-ids). But sending long strings instead of short integers is a waste of bandwith. Receiving a fixed size integer is much easier.

As the size of each protobuf message may differ (protobuf put a lot efforts to reduce the size of messages) I consider it a good idea to add a sentinel to each message.

A short demo (using byte buffers to simplify the message transfer part) can be found at https://github.com/valpo/protodemo.

The classic approach

Solving a sudoku puzzle is not very hard. Representing the puzzle as a thin wrapper around some kind of container (a std::array in this case), it could look like this:

template<typename T, size_t N>
class SudokuT
{
private:
  std::array<T,N*N> data;
public:
  SudokuT(const std::array<T,N*N>& a) : data(a) {}
  unsigned operator()(size_t row, size_t col) const { return data[row*N+col]; }
  SudokuT<T,N> replace(size_t row, size_t col, T val) {
    SudokuT<T,N> s(*this);
    s.data[row*N+col] = val;
    return s;
  }
  size_t dimension() const { return N; }
};
// the classic 9x9 sudoku
using Sudoku = SudokuT<unsigned, 9ul>;
using Cell = std::pair<size_t, size_t>;

The Sudoku class does not much more than simulating a two-dimensional matrix
over a one dimensional container. It is just for our convenience. It is a read-only class: there is no way to modify an instance, the only way to change fields (or cells) is calling Sudoku::replace to create a new instance containing the change. This allows a clean functional style which is easier to understand (at least for me) and will make it easier to transform the “classic approach” into the compile time solution later on.
We will use the value 0 (zero) to represent the unknown value, these are the cells which should be filled by the solver.

The solving function is just a simple backtracking algorithm:

constexpr Sudoku solve(const Sudoku& s)
{
  if (!valid(s)) return s;
  else {
    Cell n{next(s)};
    if (n.first == std::numeric_limits<Cell::first_type>::max()) return s;
    for(unsigned i=1;i<=s.dimension();++i) {
      auto ns = s.replace(n.first,n.second,i);
      Sudoku res = solve(ns);
      if (finished(res) && valid(res)) return res;
    }
    return s;
  }
}

valid() is a function which checks the validity (soundness) of a given sudoku (which may still contain 0 values), finish() checks the completeness of a given puzzle. The function next() returns a Cell with the coordinates of a Cell containing 0. If next() cannot find a free cell, it will return a cell with invalid coordinates. There are other (and maybe better) ways to check this, for instance calling finished() before ensuring next() can find a result or by throwing an exception in next().
I would not say this is a good solution, but it works (in a sense that valid input produces valid output, as usual all the error checking stuff was ignored). So lets go to the interesting part:

The compile time approach

C++ offers since C++11 the constexpr keyword. It is usable since C++11 and convenient since C++14. The latter added if-statements, and loops to the list of expressions allowed in a constexpr function. This allows us to just add the constexpr keyword to our solve() function:

constexpr Sudoku solve(const Sudoku& s)
{
  if (!valid(s)) return s;
  else {
    const Cell n{next(s)};
    if (n.first == std::numeric_limits<Cell::first_type>::max()) return s;
    for(unsigned i=1;i<=s.dimension();++i) {
      const auto ns = s.replace(n.first,n.second,i);
      const Sudoku res = solve(ns);
      if (finished(res) && valid(res)) return res;
    }
    return s;
  }
}

to turn it into a constexpr-function. As we are creating (modified) copies of our Sudoku class, it has to be constexpr too:

template<typename T, size_t N>
class SudokuT
{
  std::array<T,N*N> data;
public:
  constexpr SudokuT(const std::array<T,N*N>& a) : data(a) {}
  constexpr unsigned operator()(size_t row, size_t col) const {
    return row*N+col >= N*N ? 0
                            : data[row*N+col];
  }
  constexpr SudokuT<T,N> replace(size_t row, size_t col, T val) const;
  constexpr size_t dimension() const { return N; }
};

Fortunately std::array can be constexpr-constructed and has a constexpr-[]-operator. Our access function got an additional out-of-range check, and that is it. With one exception: the replace method becomes a small problem. We have to create the modified Sudoku in one step. As our Sudoku is just a thin wrapper around std::array, the question boils down to: how do we create a copy of an existing array with a value change at one position? What we are looking for is a function like this:

template<typename T, size_t N>
constexpr std::array<T,N> replace(const std::array<T,N>&a, const size_t offset, const T val);

This function should create a copy of a, change a[offset] to val, and return the resulting array. And it should be a constexpr function. It turns out to be a non-trivial problem.

Playing with std::array

std::array is just a wrapper over the old c-style-arrays. It provides not much functionality by itself. But it turns out the be a source of much fun in conjunction with variadic templates. Consider, for instance, a function make_unique_array, which creates an array were all elements have the same value:

template<typename T, size_t N>
constexpr std::array<T,N> make_unique_array(const T val);
auto a = make_unique_array<unsigned,40ul>(42);

std::array a should now contain 40 elements and each of it with value 42. This can be easily implemented using variadic templates and a little helper function:

template<typename T, size_t... Ids>
constexpr std::array<T,sizeof...(Ids)> make_unique_array_impl(const T val, const std::index_sequence<Ids...>)
{
  return { {(static_cast<void>(Ids), val)...} };
}
template<typename T, size_t N>
constexpr std::array<T,N> make_unique_array(const T val)
{
  return make_unique_array_impl(val, std::make_index_sequence<N>());
}

std::make_index_sequence was added in C++14. It creates a variadic template (with N elements), which we use to instantiate the right version of the make_unique_array_impl function. In this function we finally use a parameter pack to create our new array: “(static_cast(Ids), val)…” will be expanded during compilation to (note that Ids in our case is the list 0, 1, 2, …, N): (static_cast(0), val), (static_cast(1), val), …, (static_cast(N), val). The cast is used to just avoid a compiler warning(unused value). The comma operator returns always the last argument, which is “val” in our case. With this little trick we get a list of N elements each with value “val”, which we use to create our array.
The same idea can be used to merge two arrays depending on the result of select-function:

template<typename T, size_t N, typename Sel, size_t... Idx>
constexpr std::array<T,N> merge(const std::array<T,N>&a, const std::array<T,N>&b, Sel sel, std::index_sequence<Idx...>)
{
  return { {sel.select(a[Idx],b[Idx],Idx)...} };
}
template<typename T, size_t N, typename Sel>
constexpr std::array<T,N> merge(const std::array<T,N>&a, const std::array<T,N>&b, Sel sel)
{
  return merge(a,b,sel,std::make_index_sequence<N>());
}

Given two arrays a and b of the same size (N) and type (T), the merge function creates a merge array c of size N and type T where each element c[i] == sel.select(a[i],b[i]).
Note that all functions above are marked as constexpr, thus it can be evaluated at compile time.

The replace

Given the functions above it is finally easy to implement the replace function:

template<typename T>
struct Sel {
  size_t idx;
  constexpr Sel(size_t i) : idx{i} {}
  constexpr T select(T a, T b, size_t index) {
    return index==idx?b:a;
  }
};
template<typename T, size_t N>
constexpr std::array<T,N> replace(const std::array<T,N>&a, const size_t offset, const T val)
{
  return merge(a, make_unique_array<T,N>(val), Sel<T>{offset});
}

Note that Sel is a constexpr class too.
Obviously replace can be simplified further:

template<typename T, size_t N, typename Sel, size_t... Idx>
constexpr std::array<T,N> replace_impl(const std::array<T,N>&a, Sel sel, std::index_sequence<Idx...>)
{
  return { {sel.select(a[Idx],Idx)...} };
}
template<typename T, size_t N, typename Sel>
constexpr std::array<T,N> replace(const std::array<T,N>&a, Sel sel)
{
  return replace_impl(a, sel, std::make_index_sequence<N>());
}
template<typename T, typename S>
struct Selector
{
  T val;
  S offset;
  constexpr Selector(const T& v, const S& o) : val(v), offset(o) {}
  constexpr T select(T a, S index) const {
    return index==offset?val:a;
  }
};

Now we can write our Sudoku-replace:

template<typename T, size_t N>
class SudokuT
{
  ...
  constexpr SudokuT<T,N> replace(size_t row, size_t col, T val) const {
    return {::replace(data,Selector<T,size_t>(val,row*N+col))};};
  }
  ...
};

The complete code is available at github.

Performance

Obviously the constexpr version runs faster, but we have to pay a price at compile time:

Version	Compile time (sec)	Run time (sec)
Dynamic classic	0.66	2.1
Compile time	720	0.005
Empty		0.005

The Empty version just returns immediately from solve(). This is just to show, that the runtime of the constexpr version is mainly caused by the output of the result.

Conclusion

There are two important (at least for me) results. The first one is: compile time calculation is very funny. The second one: one should think very careful if and where it is useful. It increases compile time dramatically. And there is (at least at the moment) no possibility to debug this code. Please do not forget the alternatives just because constexpr are so funny: “Write programs which write programs” (I do not remember the author). If you need some special values in your program, just write a program which calculates these values and generates an include file. Place this program in your build toolchain. Or run some initialization code at startup which fills lookup tables. All these techniques are well established, easy to maintain. Use constexpr only if you can prove, it makes sense (or if it is trivial to implement). Or if you have enough time and need some fun.

Mit etwas Abstand moechte ich mich mal an einer Art Fazit versuchen. In den letzten 5 Jahren habe ich leider etwas den Kontakt zu Qt verloren, mich hier wieder auf den aktuellen Stand zu bringen war einer meiner Hauptmotivatoren fuer den Besuch dieser Veranstaltung.

Die Veranstaltung

Die Organisation war erstklassig, falls irgendwann mal irgendetwas nicht geklappt haben sollte, ist es mir entgangen. Einziger Kritikpunkt aus meiner Sicht (und das trifft auch gar nicht die Organisatoren): einige Vortraege wurden von Leuten gehalten, deren technische Kompetenz ganz sicher ueber jeden Zweifel erhaben ist, die aber ihre Inhalte einfach nicht verstaendlich rueberbringen konnten. Programmieren und Praesentieren sind halt zwei voellig unterschiedliche Dinge.

Die Technik

Auf der technischen Seite gibt es auch nur Erfreuliches zu berichten: mit den QtQuick.Controls machen QtQuick und QML jetzt auch aus meiner Sicht Sinn. Ansonsten entwickelt sich alles ordentlich weiter, sowohl auf die Entwicklung von C++ als auch auf die Veraenderungen der zahlreichen Plattformen wird reagiert. Nicht immer so schnell wie man es sich wuenschen wuerde, aber es ist klar, das die Qt-Leute die Herausforderungen erkennen und in Angriff nehmen. Aus meiner Sicht durchweg zufriedenstellend.

Der Kommerz

Die kommerzielle Seite macht mir die meisten Sorgen und das ist nicht besser geworden. Digia kennt das Problem (natuerlich, sie sehen ja die Verluste als erste). Aus meiner Sicht faehrt Digia hier eine zweigleisige Strategie: zum einen wird versucht, Aufwand an die Community auszulagern, zum anderen echten Mehrwert auf der Bezahlseite anzubieten. Z.B. den QtQuick-Compiler gibt es ausschliesslich fuer kommerzielle Kunden. Beides schmeckt mir nicht besonders, wenngleich ich den Schritt durchaus gut nachvollziehen kann.

Aus meiner Sicht ist das (die finanzielle Situation) ein echtes Problem bei der Einfuehrung von Qt in Unternehmen. Natuerlich werden die BWLer die Techniker fragen, warum sie in eine Technologie investieren sollen, die dem Hersteller Verluste bereitet. Aus Sicht des BWLers kann das keine Zukunft haben.

Ein zweites Problem ist die C++-Basis. In der langen Leidenszeit vor C++11 hat die C++-Community enorm an Substanz verloren. Und da Schulen und Universitaeten nach wie vor konsequent auf andere Programmiersprachen setzen, wird es wohl noch lange Zeit sehr schwierig sein, C++-Programmierer zu finden. Und, nicht zuletzt bedingt durch die Sprache selber, noch sehr sehr viel schwieriger, gute C++-Programmierer zu finden.

Beide Probleme wurden thematisiert (fand ich gut), die Antworten blieben aber (fuer mich) unbefriedigend (nicht gut).

Das Bleibende

Interessant war vieles, einiges ragte dann aber doch hinaus: link-time-dispatch kannte ich gar nicht, mit QtQuick habe ich mich versoehnt, QRemoteObjects muss ich mir genauer anschauen. Und ueberhaupt sollte ich wieder mehr mit Qt machen. Das Zeug macht halt einfach Spass.