I use to read papers, books, posts, etc. related to Computer Science.
Sometimes I like to try (some of) the things described and try to keep a
personal record of what I have found and done.
Now with this, kind of personal on-line record, I think it might be a good
idea to make these notes digital (I mostly take my notes on paper).
So, this could be a series, I do not know.
Anyways, this would be the first entry.
Disclaimer: I tend to write the obvious a lot, be warned.
I saw a paper written by Bjarne Stroustrup at BLOG@CACM [1],
which present recent advances on the design of C++ that should allow
to write simpler software while maintaining backwards compatibility.
Stroustrup's paper is interesting because it gives us a glimpse into the
current state of mind of the creator of C++: a language used in a plethora
of domains which is often a synonym of speed, efficiency and of course
difficulty.
Right from the start one of the first statements caught my eye right away:
(C++) evolved to meet challenges, but many developers
use C++ as if it was sill the previous millennium. This is suboptimal
from the perspective of ease of expressing ideas, performance,
reliability, and maintainability.
My immediate first question was: "Am I one of them?" I don't know, probably.
But beyond the personal self-check, it is notable the impact on the
perspectives Stroustrup refers to: ease of expressing ideas, performance,
reliability and maintainability.
We write software to solve a problem.
Solving a problem involves to be able to express our ideas in a suitable
language.
The language could be a natural language like English, a formal language
like mathematics or a programming language.
The "simple" fact of expressing our own ideas is a difficult
problem in itself, let alone to express it in a formal language in such a
way that other human beings are able to decode what is written in the
language and reach the conclusion that we are solving the problem we are
claiming we are solving.
Understanding what a piece of code does, is a prerequisite for maintaining
said software.
You can not maintain something you don't understand.
And the easier complex ideas are expressed, the more probable it is
the resulting code is maintainable.
Hence, the first perspective (ease of expressing ideas) imply the last
perspective (maintainability).
Software is not like a mechanical motor it does not tend to wear with time.
If you have a motor running 24/7 then some of its parts will wear and will
end up failing.
That does not happen with software.
Reliability comes in the sense of functional bugs absence.
A piece of software does what it is meant to do nothing more and nothing less.
It is clear that the easier ideas can be expressed, the easier they can be
understood and so the easier is to spot errors.
However, ease is not enough, the language must also be precise.
If two (quite) different ideas are barely distinguishable in the language,
then changes of bugs introduced by a misconception increases.
Performance is sometimes at odds with ease, and in this paper that dichotomy
is clear.
In Section 3.2 after one of the running examples have been reviewed to
increase its performance a final performance optimization is not described
because it involves only conventional low-level
techniques and
well, low-level is by definition not simple and not what this paper is
all about.
Now, let's dive into the examples!
Natural language is often used as a first specification of a code's purpose.
In this paper that is not different and the first
example is explained as follows:
Consider a simple program that writes every unique line
from input to output
The program is the following:
import std; // make all of the standard library available using namespace std; int main() // print unique lines from input { unordered_map<string,int> m; // hash table for (string line; getline (cin;line); ) if (m[line]++ == 0) cout<<line<<'\n'; }
I typed this and compiled it with Clang19 on FreeBSD. It failed to compile
the module for std.
So I decided to try on Fedora 41 and got similar results.
The standard C++23 is quite new, so it stands to reason that changing a
core feature of the language like std should take time.
I'm not looking to find out how I can build the std
module so the example can be executed, I was hoping it would be a kind of
"straight-forward" example.
For more information on modules from Clang and GCC's perspectives you can
consult [2] and [3].
Next step is to change the import line for the
corresponding #include directives.
And sure enough the program compiled.
Stroustrup mentions some advantages of this code compared to older C++
syles like the absense of pointers and casts while maitaining efficiency:
-it is- more efficient than most programmers could write
given a reasonable amount of time.
However, since Stroustrup does not provide an example using older C++,
I think it is difficult to see these advances if you are not
savy of older C++.
Most of the time, software development begins with a natural language
description or specification.
In this case this description is: ... a ... program that
writes every unique line from input to output.
A software developer takes this decription and crafts a program that fulfills
the description.
Once we have said program, the next natural question is:
can the program be simpler?
There are many definitions for simplicity in software, at this moment I'm
interested in: is there an equivalent program such that it uses a simpler
(hopefully faster) main data structure?
Using a hash table surprised me a bit, because it is a map from a set of
keys to a set of values.
This is a significant machinery just to implement a check-list.
The main question we must answer is: have I seen this
string before?
I think a natural choice would be to use a set or an
unordered_set (in C++ lingo).
using namespace std; int main() { unordered_set<string> s; // A set to hold the lines for (string line; getline (cin;line); ) if (s.find(line)==s.end()){ cout<<line<<'\n'; s.insert(line); } }
How does this version compares to the original?
Well, it is slower. I tested both 20 times each with the same 10M random strings
of lenght at most 20 characters.
The average (wall-clock) time of Stroustrup's solution is 17.136296 seconds.
On the other hand the average time of the version using sets is:
18.090042 seconds.
This is because in the second program we query the data structure at least
two times, one to see if line is in the set and
another when we insert the string; the second
query is inherent to the insert
operation.
While in the first example, it is only queried once.
So, we need to remove one query.
using namespace std; int main() { unordered_set<string> s; // A set to hold the lines auto cs = s.size(); //The previous size of the set for (string line; getline (cin;line); ) s.insert(line); if (s.size() != cs){ cout<<line<<'\n'; cs++; } }
In this version each line is inserted in the set,
if the set doesn't contain line, then the set's
size increases by one and that's how we detect unseen lines.
We just need to keep track of the previous size (the cs
variable).
This version is faster than the first example with an average of
16.866531 seconds.
But we are still doing overwork because insert returns a tuple such that
the second field is true if and only if an
insertion was made so we can trim the code to something similar to
Stroustrup's example:
using namespace std; int main() { unordered_set<string> s; // A set to hold the lines for (string line; getline (cin;line); ) if (s.insert(line).second) cout<<line<<'\n'; }
This new version has an average of 16.659581 seconds.
| Solution | Time (seconds) |
|---|---|
| Stroustrup | 17.136296 |
| Set_V1 | 18.090042 |
| Set_V2 | 16.866531 |
| Set_V3 | 16.659581 |
Overall, a fraction of a second or so improvement for 10M entries is well within
measurement error or acceptable in my opinion.
However, I feel this last version is a conceptually simpler and closer to
the natural language specification; and hence more resilient to client-coder
misunderstandings.
The second example is similar to the Set_V3 solution in the previous section. It shows a function that keeps unique strings obteined from the standard input and returns a vector containing the strings.
import std; using namespace std; vector<string> collect_lines(istream& is) // collect unique lines from input { unordered_set s; for (string line; getline (cin;line); ) s.insert(line); return vector{from_range, s}; } auto lines = collect_lines(cin);
Unfortunately this example fails to compile with Clang 19 on FreeBSD because
the compiler can not deduce the type of s.
This is without counting the import std; failure.
If s is "fully" typed as
unordered_set<string> then the program compiles just fine.
Later this example is rewritten to a simpler form:
import std; using namespace std; vector<string> collect_lines(istream& is) // collect unique lines from input { unordered_set s {from_range,istream_iterator<string>{is}}; return vector{from_range, s}; } auto lines = collect_lines(cin);
Once again, we need to "fully" type s but even if
we do that, this example also fails to compile because to initialize an
unordered_set with a range, the iterator must be
"container-compatible-range" and when Clang makes this check, it fails.
Perhaps for istream_iterator to pass this test,
it must be coaxed (casted) into a suitable type, but I do not know exactly
as the paper clearly claims that
istream_iterator<string>{is} allows us to treat the input from
is as a range of elements ....
Then, for the sake of experimentation I will stick to the first version.
The return statement (return vector{from_range, s})
makes a copy of the elements of s and place that
copy in the vector that is returned.
To avoid this copy, the paper suggests to change the return statement to:
return vector{from_range,std::move(s)};
Which tells the compiler to move the elements from s
to the vector instead of copying them.
The reason given for this change is (I)n principle, the
compiler could deduce that we don't use s again after making the vector
and just move the string elements, but today's compilers are not that
smart...
The explanation sounds striking similar to a live-variables analysis [4],
on the other hand, if this is not possible, it might indicate there are
some complex operations under-the-hood preventing the compiler to deduce
to use a move constructor instead of a copy constructor.
We can quickly verify this and other behaviors with the following code:
#include <utility> #include <iostream> #include <unordered_map> enum class Created {copy,moved,movedAssig,defc,construct}; int globalTag; class TestClass { public: int ident; Created creation; int tag; TestClass():ident(0),creation(Created::defc),tag(globalTag++){} TestClass(int i):ident(i),creation(Created::construct),tag(globalTag++){} TestClass(const TestClass& a):ident(a.ident),creation(Created::copy), tag(globalTag++){} TestClass& operator=(const TestClass& a){ auto tmp = TestClass(a); std::swap(tmp,*this); return *this; } TestClass(TestClass&& a):ident(std::move(a.ident)),creation(Created::moved), tag(globalTag++){} TestClass& operator=(TestClass&& a){ ident = std::move(a.ident); creation = Created::movedAssig; tag = std::move(a.tag); return *this; } void inc(){ident++;} inline bool operator==(const TestClass& a)const{ return a.ident == ident; } ~TestClass(){ std::cout << "Tag " << tag << " was released\n"; } }; struct Hash { size_t operator() (const TestClass& tc) const{ return tc.ident; } };
In particular we can test std::move behavior with unordered_map: