Tuesday, October 20, 2020

Cargo-style dependency management for C, C++ and other languages with Meson

My previous blog post about modern C++ got a surprising amount of feedback. Some people even reimplemented the program in other languages, including one in Go, two different ones in Rust and even this slightly brain bending C++ reimplementation as a declarative style pipeline. It also got talked about on Reddit and Hacker news. Two major comments that kept popping up were the following.

  1. There are potential bugs if the program is ever extended to support non-ASCII text
  2. It is hard to use external dependencies in C++ (and by extension C)
Let's solve both of these problems at the same time. There are many "lite" solutions for doing Unicode aware text processing, but we're going to use the 10 000 kilogram hammer: International Components for Unicode. The actual code changes are not that big, interested parties can go look up the details in this Github repo. The thing that is relevant for this blog post is the build and dependency management. The Meson build definition is quite short:

project('cppunicode', 'cpp',
        default_options: ['cpp_std=c++17',
                          'default_library=static'])
             
icu_dep = dependency('icu-i18n')
thread_dep = dependency('threads')
executable('cppunicode', 'cppunicode.cpp',
           dependencies: [icu_dep, thread_dep])

The threads dependency is for the multithreaded parts (see end of this post). I developed this on Linux and used the convenient system provided ICU. Windows and Mac do not provide system libs so we need to build ICU from scratch on those platforms. This is achieved by running the following command in your project's source root:

$ meson wrap install icu
Installed icu branch 67.1 revision 1

This contacts Meson's WrapDB server and downloads build definition files for ICU. That is all you need to do. The build files do not need any changes. When you start building the project, Meson will automatically download and build the dependency. Here is a screenshot of the download step:

Here it is building in Visual Studio:

And here is the final built result running on macOS:

One notable downside of this approach is that WrapDB does not have all that many packages yet. However I have been told that given the next Meson release (in a few weeks) and some upstream patches, it is possible to build the entire GTK widget toolkit as a subproject, even on Windows. 

If anyone wants to contribute to the project, contributions are most welcome. You can for example convert existing projects and submit them to wrapdb or become a reviewer. The Meson web site has the relevant documentation

Appendix: making it parallel

Several people pointed out that while the original program worked fine, it only uses one thread. This may be a bottleneck and that "in C++ it is hard to execute work in parallel". This is again one of those things that has gotten a lot better in the last few years. The "correct" solution would be to use the parallel version of transform_reduce. Unfortunately most parallel STL implementations are still in the process of being implemented so we can't use those in multiplatform code. We can, however, roll our own fairly easily, without needing to create or lock a single mutex by hand. The code has the actual details, but the (slightly edited) gist of of it is this:

for(const auto &e:
    std::filesystem::recursive_directory_iterator(".")) {
    futures.emplace_back(std::async(std::launch::async,
                                    count_word_files,
                                    e));
    if(futures.size() > num_threads) {
        pop_future(word_counts, futures);
    }
}
while(!futures.empty()) {
   pop_future(word_counts, futures);
}

Here the count_word_files function calculates the number of words in a single file and the pop_future function joins individual results to the final result. By using a share-nothing architecture, pure functions and value types all business logic code can be written as if it was single threaded and the details of thread and mutex management can be left to library code. Haskell fans would be proud (or possibly horrified, not really sure).

Thursday, October 15, 2020

Does C++ still deserve the bad rap it has had for so long?

Traditionally C++ has been seen by many (and you know who you are) as just plain bad: the code is unreadably verbose, error messages are undecipherable, it's unsafe, compilation takes forever and so on. In fact making fun of C++ is even a fun pastime for some. All of this was certainly true in the 90s and even as recent as 10 years ago. But is it still the case? What would be a good way to determine this?

A practical experiment

Let's write a fairly simple program that solves a sort-of-real-worldish problem and see what comes out of it. The problem we want to solve is the following:
Find all files with the extension .txt recursively in the subdirectories of the current directory, count the number of times each word appears in them and print the ten most common words and the number of times they are used.

We're not going to go for extreme performance or handling all possible corner cases, instead going for a reasonable implementation. The full code can be found by following this link.

The first thing we need is a way to detect files with a given extension and words within text. This calls for regular expressions:

const std::regex fname_regex("\\.txt$", std::regex_constants::icase);

const std::regex word_regex("([a-z]{2,})", std::regex_constants::icase);

This might a bit verbose, but quite readable. This only works for ASCII text, but for the purposes of this experiment it is sufficient. To calculate the number of times each word is seen, we need a hash table:

std::unordered_map<std::string, int> word_counts;

Now we need to iterate over all files in the current directory subtree.

for(const auto &e: std::filesystem::recursive_directory_iterator("."))

Skip everything that is not a .txt file.

if(!e.is_regular_file()) {
    continue;
}
if(!std::regex_search(e.path().c_str(), fname_regex)) {
    continue;
}

Process the file line by line:

std::ifstream current_file(e.path());
for (std::string line; std::getline(current_file, line); )

For each line we need to find all words that match the regular expression.

std::sregex_iterator word_end;
for(auto it = std::sregex_iterator(line.begin(), line.end(), word_regex); it != word_end; ++it)

This is a bit verbose, but it takes care of all the state tracking needed to run the regex multiple times on the same input string. Doing the same by hand is fairly tedious and error prone. Now that we have the matches, we need to convert them to standalone lowercase words.

std::string word{it->str()};
for(auto &c : word) {
    c = std::tolower(c);
}

Lowercasing strings is a bit cumbersome, granted, but this is at least fairly readable. Then on to incrementing the word count.

++word_counts[word];

That's all that is needed to count the words. This can't be done directly in the hash map so we need to convert the data to an an array. It needs some setup code.

struct WordCount {
    std::string word;
    int count;
};

std::vector<WordCount> word_array;
word_array.reserve(word_counts.size());

Since we know how many entries will be in the array, we can reserve enough space for it in advance. Then we need to iterate over all entries and add them to the array.

for(const auto &[word, count]: word_counts) {
    word_array.emplace_back(WordCount{word, count});
}

This uses the new structured bindings feature, which is a lot more readable than the old way of dealing with iterator objects or pairs with their firsts and their seconds and all that horror. Fortunately no more.

The simple way of getting the 10 most used entries is to sort the array and then grab the 10 first elements. Let's do something slightly swaggier instead [0]. We'll do a partial sort and discard all entries after 10. For that we need a descending sorting criterion as a lambda.

auto count_order_desc = [](const WordCount &w1, const WordCount &w2) { return w2.count < w1.count; };

Using it is straightforward.

const auto final_size = std::min(10, (int)word_array.size());
std::partial_sort(word_array.begin(), word_array.begin() + final_size, word_array.end(), count_order_desc);
word_array.erase(word_array.begin() + final_size, word_array.end());

All that remains is to print the final result.

for(const auto& word_info: word_array) {
    std::cout << word_info.count << " " << word_info.word << "\n";
};

Safety

As safety and security are important features in current sofware development, let's examine how safe this program is. There are two main safety points: thread safety and memory safety. As this program has only one thread, it can be formally proven to be thread safe. Memory safety also divides into two main things to note: use after frees (or dangling references) and out of bound array accesses.

In this particular program there are no dangling references. All data is in value types and the only references are iterators. They are all scoped so that they never live past their usages. Most are not even stored into named variables but instead passed directly as function arguments (see especially the call to partial_sort). Thus they can not be accessed after they have expired. There is no manual resource management of any kind. All resources are freed automatically. Running the code under Valgrind yields zero errors and zero memory leaks.

There is one place in the code where an out-of-bounds access is possible: when creating the iterator pointing to 10 elements past the beginning of the array [2]. If you were to forget to check that the array has at least 10 elements, that would be an immediate error. Fortunately most standard libraries have a way to enable checks for this. Here's what GCC reports at runtime if you get this wrong:

Error: attempt to advance a dereferenceable (start-of-sequence) iterator 100000 steps, which falls outside its valid range.

Not really a perfect safety record, but overall it's fairly good and certainly a lot better than implementing the same by manually indexing arrays.

Problems

Compiling the program takes several seconds, which is not great. This is mostly due to the regex header, which is known to be heavyweight. Some of the compiler messages encountered during development were needlessly verbose. The actual errors were quite silly, though, such as passing arguments to functions in the wrong order. This could definitely be better. It is reported that the use of concepts in C++20 will fix most of this issue, but there are no practical real-world usage reports yet.

Unique features

This code compiles, runs and works [1] on all major platforms using only the default toolchain provided by the OS vendor without any external dependencies or downloads. This is something that no other programming language can provide as of date. The closest you can get is plain C, but its standard library does not have the necessary functionality. Compiling the code is also simple and can be done with a single command:

g++ -o cppexample -O2 -g -Wall -std=c++17 cppexample.cpp

Conclusions

If we try to look at the end result with objective eyes it would seem to be fairly nice. The entire implementation takes fewer than 60 lines of code. There's nothing immediately terrible that pops up. What is happening at each step is fairly understandable and readable. There's nothing that one could immediately hate and despise for being "awful", as is tradition.

This is not to say you could still not hate C++. If you want to, go right ahead. There are certainly reasons for it. But if you choose to do that, make sure you hate it for real actual reasons of today, rather than things that were broken decades ago but have been fixed since.

[0] There is an even more efficient solution using a priority queue that does not need the intermediate array. Implementing it is left as an exercise to the reader.
[1] Reader beware, I have only proven this code to be portable, not tried it.
[2] The implementation in [0] does not have this problem as no iterators are ever modified by hand.

Tuesday, October 6, 2020

Is your project a unique snowflake or do you just think that it is?

If there is a national sport for programmers, it is reinventing existing things from scratch. This seems to be especially common inside corporations that tend to roll their own rather than, for example, using an existing open source library. If you try to ask around why this has been done, you typically get some variation of this:
We can't use off-the-shelf solutions because we have unique needs and requirements that no-one else has.

Now, there genuinely are cases where this is true, but it mostly happens only in very spesialised cases, such as when you are google-scale, do space engineering or something similar. There might also be legal or regulatory reasons that you must own all code in a product. Most projects are not like this. In fact almost always someone (typically hundreds of someones) has had the exact same problem and solved it. Yet people seem to keep reinventing the wheel for no real purpose. If you ever find yourself in a debate on why people should use existing solutions rather than roll your own, here are some talking points to consider.

How have you established that your needs are actually unique?

Very often when someone says "the needs for <project X> are unique" what they are actually saying is "this needs a feature I have never personally encountered before". This is not due to malice, it is just how human beings seem to behave. If one has a rough idea of how to solve a problem by coding it from scratch but no knowledge of an existing solution, people tend to go with the former rather than spend time on researching the problem. I don't know why. This is especially true if there is external pressure on "getting something going fast".

I know this, because I have actually done it myself. Ages ago I was working on some Java code and needed to communicate with a different process. I was starting to write a custom socket protocol when my coworker asked why am I not simply using regular HTTP with Jetty. The answer, to the surprise of absolutely no-one, is that I had never heard of it. This single sentence saved days of implementation work and probably the same amount in ongoing maintenance and debugging work.

We need more performance than existing solutions can provide

This splits nicely into two parts. In the first one you actually need the performance. This is rare, but it happens. Even so, you might consider optimizing the existing solution first. If you are successfull, submit the changes upstream. This way they benefit everyone and reduce the ongoing maintenance burden to roughly zero.

The other case is that all the performance you think you need, you don't actually need. This is surprisingly common. It turns out that modern computers and libraries are so fast that even "reasonably ok" is performant enough most of the time for most problems [0]. As an example I was working on a product that chose to roll its own functionality X rather than using the standard solution in Linux because it needed to do "thousands of operations per second". These operations were only done in response to human interaction, so there was no way it could generate more than 10 or so events per second. But still. Must have performance, so multiple months of hand-rolling it was.

To add insult to injury, I did some measurements and it turned out that the existing solution could do one thousand operations per second without even needing to go to C. The Python bindings were fast enough.

We need the ability to change the implementation at will

One major downside of using an existing open source solution is that you have to give up some control. Changes must be submitted to people outside your immediate control. They might say no and you can't override them with office politics. In-house code does not have this problem.

This control comes with a significant downside. What fairly often happens is that some developers write and maintain the new functionality and everything is rosy. Then time happens and the original coders switch teams and jobs, become managers and so on. They take the knowledge required to change the system with them. Unless your company has a very strong culture of transferring this knowledge, and most companies most definitely don't, the code will bitrot, fossilize and become a massive clump of legacy that must not be touched because there is no documentation, no tests and nobody really understands it any more.

So even if the corporation has the possibility to change the code at will they lack the ability to do so.

Sometimes people just plain lie

There are two main reasons that explain pretty much everything what people do, say and recommend:
  1. The reason they give to others
  2. The real reason
Even for "purely technical" decisions like these, the two can be drastically different. Suppose some developer has done several similar "boring" projects. Then when the time comes to choose the approach for the new project. If they choose an existing system, they know that the next project will be just like the preceding five. If, on the other hand, some new tech is chosen, then the entire task becomes more meaningful and exciting. In this case the stated reason is technical fitness, but the real reason is frustration. Another way of stating this is that when asked "should we use library X or write our own from scratch" the answer the coder would want to give is "I don't want to work on that project". 

This is not something that people won't say out loud because it gets you easily labeled as a "prima-donna", "work avoider" or "elitist". Many people will also have trouble saying it because it comes from a "bad" emotional response. All of this leads to shame and people are willing to go to great lengths to avoid feeling ashamed.

The same reasoning applies to other "impure" emotions such as infatuation ("OMG this new tech is so cool"), disgust ("using tech X means I have to work with Bob from department X"), infidelity ("either you give me this or I'm accepting the job offer from a competitor"), megalomania ("creating this new framework will make me a superstar celebrity coder") and the ever-popular self-disappointment ("I got into programming because I wanted to create new things like an architect, but ended up as a code janitor").

Tuesday, September 15, 2020

Want GCC's cleanup attribute in Visual Studio? Here's what to do.

A common pain point for people writing cross platform C code is that they can't use GCC's cleanup attribute and by extension GLib's g_auto family of macros. I had a chat with some Microsoft people and it turns out it may be possible to get this functionality added to Visual Studio. They add features based on user feedback. Therefore, if you want to see this functionality added to VS, here's what you should do:

  1. Create a Microsoft account if you don't already have one.
  2. Upvote this issue.
  3. Spread the word to other interested people.


Sunday, September 13, 2020

Proposal for a computer game research topic: the walk/game ratio

I used to play a fair bit of computer games but in the recent years the amount of time spent on games has decreased. Then the lockdown happened and I bought a PS4 and got back into gaming, which was fun. As often is the case, once guy get back into something after a break you find yourself paying attention to things that you never noticed before.

In this particular case it was about those parts of games where you are not actually playing the game. Instead you are walking/driving/riding from one place to another because the actual thing you want to do is somewhere else. A typical example of this is Red Dead Redemption II (and by extension all GTAs). At first wondering the countryside is fun and immersive but at some point it becomes tedious and you just wish to be at your destination (fast travel helps, but not enough). Note that this does not apply to extra content. Having a lush open sandbox world that people can explore at their leisure is totally fine. This is about "grinding by walking" that you have to do in order to complete the game.

This brings up several interesting questions. How much time, on average, do computer games require players to spend travelling from one place to another as opposed to doing the thing the game is actually about (e.g. shooting nazis, shooting zombie nazis, hunting for secret nazi treasure and fighting underwater nazi zombies)? Does this ratio vary over time? Are there differences between genres, design studios and publishers? It turns out that determining these numbers is fairly simple but laborious. I have too many ongoing projects to do this myself, so here's a research outline for anyone to put in their research grant application:

  1. Select a representative set of games.
  2. Go to speedrun.com and download the fastest any-% glitchless run available.
  3. Split the video into separate segments such as "actual gameplay", "watching unskippable cutscenes", "walkgrinding" and "waiting for game to finish loading".
  4. Tabulate times, create graphs

Hypothetical results

As this research has not been done (that I know of and am able to google up) we don't know what the results would be. That does not stop us from speculating endlessly, so here are some estimates that this research might uncover:
  • Games with a lot of walkgrdinding: RDR II, Assassin's Creed series, Metroid Prime.
  • Games with a medium amount of walkgrinding: Control, Uncharted
  • Games with almost no walkgrinding: Trackmania, Super Meat Boy.
  • Games that require the player to watch the same unskippable cutscenes over and over: Super Mario Sunshine
  • Newer games require more walkgrinding simply because game worlds have gotten bigger

Sunday, August 30, 2020

Resist the urge to argue about app store security

Recently Miguel de Icaza wrote a blog post arguing that closed computing platforms where a major US corporation decides what software users are allowed to install are a good thing. This has, naturally, caused people to become either confused, disappointed or angry. Presumably many people are writing responses and angry comments. I almost started one writing one pointing out all the issues I found in the post.

Doing that would probably create a fairly popular blog post with followups. It might even get to the reddits and hackernewses and generate tons of comments where people would duke it out on issues on user choice vs the safety provided by a curated walled garden. There would be hundreds, if not thousands, of snarky tweets that make their poster feel superior for a while but are ultimately not productive. To quote Star Trek Deep Space Nine:
Spare me please-think-of-the-children speech and I'll spare you the users-must-have-control-over-their-own-devices speech [1].
Having us, the user and developer community, argue about this issue is pointless, unproductive and actively harmful. This particular phenomenon is not new, it even has a name. In fact this approach is so old that the name is in latin: Divide et impera. Divide and conquer. All the time and energy that we spend on arguing this issue among ourselves is time not spent on working towards a solution.

The actual solution to this issue is conceptually so simple it could be called trivial. The entire problem at hand is one that has been created by Apple. They are also the ones that can solve it. All they have to do is to add one new piece of functionality to iOS devices. Specifically that users who so choose, can change an option in the device they own allowing them to download, install and use any application binaries freely from the Internet. Enabling this functionality could be done, for example, in a similar way to how Android phones enable developer mode. Once implemented Apple would then make a public statement saying that this workflow is fully supported and that applications obtained in this way will, now and forevermore, have access to all the same APIs as official store apps do.

This is all it takes! Further, they could make it so that IT departments and concerned parents could disable this functionality on their employees' and children's devices so that they can only obtain apps via the app store. This gives both sets of users exactly what they want. Those who prefer living in a walled curated garden can do so. Those with the desire and willingness to venture outside the walls and take responsibility of their own actions can do so too and still get all the benefits of sandboxing and base platform security.

Apple could do this. Apple could have done this at launch. Apple could have done this at any time since. Apple has actively chosen not to do this. Keep this is mind if you ever end up arguing about this issue on the Internet. People who have different priorities and preferences are not "the enemy". If you get into the flaming and the shouting you have been divided. And you have been conquered.

[1] Might not be a word-for-word accurate transcription.

Friday, August 28, 2020

It ain't easy being a unique snowflake, the laptop purchasing edition

As the lockdown drags on I have felt the need to buy a new laptop as my old one is starting to age. A new category in the laptop market is 2-in-1 laptops with full drawing pen support. It has been a long time since I have done any real drawing or painting and this seemed like a nice way to get back into that. On the other hand the computer also needs to be performant for heavy duty software development such as running the Meson test suite (which is surprisingly heavy) and things like compiling LLVM. This yields the following requirements:

  • A good keyboard, on the level of Thinkpads or 2015-ish Macbook Pros
  • 13 or 14 inch screen, at least Retina level resolution, HDR would be nice, as matte as possible
  • Pressure and tilt support for the pen
  • At least 16GB of RAM
  • USB A, C and HDMI connectors would be nice
  • At least Iris level graphics with free drivers (so no NVidia)
  • A replaceable battery would be nice
  • Working dual boog (I need Win10 for various things), full Linux support (including wifi et al)
After a bunch of research it turns out that this set of requirements might be impossible to fullfill. Here are the tree best examples that I found.

HP Elite Dragonfly

The documentation is unclear on whether the pen supports tilting. More importantly this model is only available with Intel 8th gen processors and online reviews say the screen is super glossy.

Lenovo Yoga X1 Gen5

Pen does not support tilting. The graphics card is a standard Intel HD, not Iris.

Dell XPS 13 2-in-1 7390

This is the one that gets the closest. There is no USB A or HDMI connectors, and the pen requires an AAAA battery. This is annoying but tolerable. Unfortunately the keyboard is of the super thin type, which is just not usable.

So now what?

Probably going to stick with the current ones for now. New models come out at a fairly steady pace, so maybe this mythical white whale will become available for purchase at some point. Alternatively I might eventually just fold, give up on some requirements and buy a compromise machine. Typically this causes the dream machine to become available for purchase immediately afterwards, when it is too late.