Jakob Ƙstergaard Hegelund

Tech stuff of all kinds

A new-years KISS

2016-12-30

Anyone who says "less is more" is of course high, stupid, or both. Less is not more - but the message intended in that common cliche is that "less is better", which is certainly the case more often than not.

The problem

Without going into details... A developer is faced with the problem of generating a string like foo=42&bar=more&baz, given the following set of mappings:

KeyValue
foo42
barmore
baz

The diligent reader will recognize the string as the options part of a URI, and can also safely infer that the table of key/value mappings is indeed held in an STL map<string,string> structure.

The solution

During some early spring cleaning here before the very end of 2016, I stumbled across the code for this solution - it works and the code did not cause problems; but it is heavily depending on the boost library which I am trying to get rid of to the extent possible (and that would probably be the subject of an article on itself - suffice to say I'm trying to cut down on dependencies).

namespace { struct to_string { typedef std::string result_type; const result_type operator()(const HTTPOptions::options_t::value_type &pair) const { if (pair.second.empty()) { return pair.first; } return pair.first + std::string("=") + pair.second; } }; } const std::string HTTPOptions::to_uri() const { return boost::algorithm::join( m_options | boost::adaptors::transformed(to_string()) , "&"); }

The above is the code as I found it. It uses a boost algorithm to "join" the options with ampersands, and declares a struct to be able to apply an operator() using a transformer, to convert the pairs in the map to strings of the "key=value" form.

It is time to take a step back... Why is it we need all this? What is the actual job that we are performing? Take a moment to think about it... Given the mapping of strings, how would you imagine that you could construct the resulting string?

Another solution

I deleted the includes of boost headers and deleted the code above. Instead, I wrote this little bit:

std::string HTTPOptions::to_uri() const { std::ostringstream str; for (auto i = m_options.begin(); i != m_options.end(); ++i) str << (i == m_options.begin() ? "" : "&") << i->first << (i->second.empty() ? "" : "=") << i->second; return str.str(); }

This is a pretty straight forward solution really. It iterates though the mapping and simply inserts the string pairs one by one. No operator|() to apply a transformer to a map, no structs with operators that construct new strings based on the old ones, and no high-level transformers to abstract away the nitty gritty details.

I am not against abstractions. But we also have to consider the reality of things here:

Old solutionNew solution
Size20 lines10 lines
DependenciesBoost, STLSTL
Allocations2n + log nlog n

The allocations metric is a relevant performance metric; basically, when we perform an operator+ on two strings, we construct a new string using the two old (without modifying the two old). This costs us an allocation. Therefore, for every call to to_string::operator() we perform two new allocations. The boost join method will use insert to append each pair to the resulting string, and I think it is fair to assume that std::string is smart enough to incrementally grow its underlying buffer thereby giving us around log(n) allocations for adding n pairs to the string.

The new solution however uses a ostringstream which, like the std::string will perform something like log(n) allocations in order to append n strings to the result. No temporary strings are created during the operation of the new solution - therefore the number of allocations is negligible compared to the original solution.

Last but not least, the shorter solution is trivial. It is obvious what it does and it is obvious how it does it. It is simply more readable, not just because it is fewer lines, but because of its flow.

Something to take with us into the new year...

The morale of the story is: When you are implementing a solution to a conceptually very simple problem, and you find yourself writing a lot of code using clever and complex libraries and constructs, you need to take a step back.

For every simple problem, there is a large, complicated and expensive technological solution.

But it doesn't have to be like that. We can do better. Let's make 2017 a year where we do better. Happy new year everyone!