tiistai 16. heinäkuuta 2019

A personal story about 10× development

During the last few days there has been an ongoing Twitter storm about 10× developers. And like all the ones before it (and all the future ones that will inevitably happen) the debate immediately devolved into name calling and all the other things you'd except from Twitter fights. This blog post is not about that. Instead it is about a personal experience about productivity that I had to experience closer than I would have liked.

Some years ago I was working for company X on product Y. All in all it was quite a nice experience. We had a small team working on a code base that was pretty good. It had nice tests, not too many bugs, and when issues did arise they were usually easy to fix. Eventually the project was deemed good enough and we were transferred to work on different projects.

I have no idea what our "industry standard performance multiplier" was when we worked on that project, but for the sake of argument let's call it 1×.

The project I got transferred to was the thing of nightmares. It was a C++ project and all the bad things that have ever been said about C++ were true about that code base. There was not much code but it was utterly incomprehensible. There were massively deep inheritance hierarchies, , compilation speed was measured in minutes for even the most trivial changes, and so on. It was managed by an architecture astronaut that, as one is wont to do, rewrote existing mature libraries as header only template libraries that were buggy and untested (one could even say untestable).

Thus overnight I went from being a 1× down to being a 0.1× or possibly even a 0.01× developer. Simply trying to understand what a specific function was supposed to do took hours. There was, naturally, a big product launch coming up so we needed to get things finished quickly. All in all it was a stressful, frustrating and unpleasant situation to be in. And that was not the worst of it.

After a few weeks my manager wanted to talk to me in private. He was very concerned about the fact that I had not achieved any visible progress for a while. Then I explained to him in detail all the problems in the current project. I even demonstrated how compiling a simple helloworld-level program with the frameworks we had to use took tens of seconds on the beefiest i7 desktop machine I had available. He did not seem to be able to grasp any of that as his only response was "but you used to be so productive in your previous project". Shortly thereafter the same boss started giving me not-al-all-thinly-veiled accusations that I was just slacking off and that this could lead to serious reprimands.

This story does not have a happy ending. The project eventually failed (due to completely different reasons, though), money was squandered and almost everyone involved got fired. In the aftermath I seriously considered getting out of the software engineering business altogether. The entire experience had been so miserable that becoming a 0× developer was seriously tempting.

Is there something we can learn from this?

The "×ness" of any developer does not exist in a vacuum but depends on many organizational things. The most obvious one is tooling. If you have a CI where tests take 30 minutes to run or your developers have underpowered old laptops, everyone's performance goes down. In fact, the overall health of the code base probably has a bigger effect on developer productivity than all developers' skills combined.

But even more important than technical issues are things that promote healthy team dynamics. These include things like blameless postmortems, openness to ideas from everyone, permission to try new things even if they may fail, stern weeding out of jerk behaviour and, ultimately, trust.

If you work on getting all of these things in your working environment then you may find that you find yourself with a 10× team. And if you do, the entire concept of a single 10× developer becomes meaningless.

sunnuntai 14. heinäkuuta 2019

Initializing all local variables with Clang-Tidy

A common source of all kinds of bugs is using variables without properly initializing them. Out of all security problems this one is the simplest to fix, just convert all declarations of type int x; to int x=0;. The main reason for not doing that is laziness, manually going through existing code bases and adding initialization statements is boring and nobody wants to do that.

Fortunately nowadays we don't have to. Clang-tidy provides a nice toolkit for writing source code refactoring tools for C and C++. As an exercise I wrote a checker to do this. It is submitted upstream and is undergoing code review. Implementing it was fairly straightforward. There were only two major problems. The first one was that existing documentation consists mostly of reference manuals. There is no easy to follow tutorials, only Doxygen pages. But if you dig around on the net and work on it a bit, you can get it working.

The second, and bigger, obstacle is that doing anything in the LLVM code base is sloooow. Everything in LLVM and Clang is linked to single, huge, monolithic libraries which take forever to link. Because of reasons I started doing this work on my secondary machine, which is a 4 core i5 with 16 gigs of RAM. I had to limit simultaneous linker jobs to 2 because otherwise it would just crash spectacularly to an out of memory error. Presumably it is impossible to compile the code base on a machine that has only 8 gigs of RAM. It seems that if you want to do any real development on LLVM you need a spare data center to run the compilations, which is unfortunate.

There is an evil hack to work around this, though. Set the CMake build type to Debug and then change CMAKE_CXX_FLAGS_DEBUG and CMAKE_C_FLAGS_DEBUG from -g to -Og. This makes the compilation faster and reduces memory usage to a fraction of the original. The downside is that there is no debug information, but it turns out to not be necessary when writing simple Clang-Tidy checkers.

Once all that is done the actual checker is almost trivial. This is the part that looks up all local variables without initial values:

void InitLocalVariablesCheck::registerMatchers(MatchFinder *Finder) {
      varDecl(unless(hasInitializer(anything()))).bind("vardecl"), this);

Then you determine what the initial value should be based on the type of the variable and add a warning and a fixit:

diag(location, "variable %0 is not initialized")
    << MatchedDecl;
diag(location, "insert initial value", DiagnosticIDs::Note)
    << FixItHint::CreateInsertion(

All in all this amounts to about 100 lines of code plus tests.

But what about performance?

The other major reason not to initialize variables is that it "may cause a runtime performance degradation of unknown magnitude". That is true, but with this tooling the degradation is no longer unknown. You can run the tool and then measure the results. This is trivial for all code bases that have performance benchmarks.

perjantai 7. kesäkuuta 2019

Tweaking the parallel Zip file writer

A few years ago I wrote a command line program to compress and decompress Zip files in parallel. It turned out to work pretty well, but it had one design flaw that kept annoying me.

What is the problem?

Decompressing Zip files in parallel is almost trivial. Each file can be decompressed in parallel without affecting any other decompression task. Fire up N processing tasks and decompress files until finished. Compressing Zip files is more difficult to parallelize. Each file can be compressed separately, but the problem comes from writing the output file.

The output file must be written one file at a time. So if one compressed file is being written to the output file then other compression tasks must wait until it finishes before their output can be written to the result file. This data can not be kept in memory because it is common to have output files that are larger than available memory.

The original solution (and thus the design flaw alluded to) was to to have each compressor write its output to a temporary file. The writer would then read the data from the file, write it to the final result file and delete the temporary file.

This works but means that the data gets written to the file system twice. It may also require up to 2× disk space. The worst case happens when you compress only one very big file. On desktop machines this is not such a problem, but on something like a Raspberry Pi the disk is an SD card, which is very slow. You only want to write it once. SD cards also wear out when written to, which is another reason to avoid writes.

The new approach

An optimal solution would have all of these properties:
  1. Uses all CPU cores 100% of the time (except at the end when there are fewer tasks than cores).
  2. Writes data to the file system only once.
  3. Handles files of arbitrary size (much bigger than available RAM).
  4. Has bounded memory consumption.
It turns out that not all of these are achievable at the same time. Or at least I could not come up with a way. After watching some Numberphile videos I felt like writing a formal proof but quickly gave up on the idea. Roughly speaking since you can't reliably estimate when the tasks finish and how large the resulting files will be, it does not seem possible to choose an optimal strategy for writing the results out to disk.

The new architecture I came up with looks like this:

Rather than writing its result to a temporary file, each compressor writes it to a byte queue with a fixed maximum size. This was chosen to be either 10 or 100 megabytes, which means that in practice most files will fit the buffer. The queue can be in one of three states: not full, full or finished. The difference between the last two is that a full queue is one where the compression task still has data to compress but it can't proceed until the queue is emptied.

The behaviour is now straightforward. First launch compressor tasks as in decompressing. The file writer part will go through all the queues. If it finds a finished queue it will write it to disk and launch a new task. If it finds a full queue it will do the same, but it must write out the whole stream, meaning it is blocked until the current file has been fully compressed. If the compressions takes too long all other compression tasks will finish (or get full) but new ones can't be launched leading to CPU underutilization.

Is it possible to do better?

Yes, but only as a special case. Btrfs supports copying data from one file to another in O(1) time taking only an extra O(1) space. Thus you could write all data to temp files, copy the data to the final file and delete the temp files.

lauantai 1. kesäkuuta 2019

Looking at why the Meson crowdfunding campaign failed

The crowdfunding campaign to create a full manual for the Meson build system ended yesterday. It did not reach its 10 000€ goal so the book will not be produced and instead all contributed money will be returned. I'd like to thank everyone who participated. A special thanks goes out to Centricular for their bronze corporate sponsorship (which, interestingly, was almost 50% of the total money raised).

Nevertheless the fact remains that this project was a failure and a fairly major one at that since it did not reach even one third of its target. This can not be helped, but maybe we can salvage some pieces of useful information from the ruins.

Some statistics

There were a total of 42 contributors to the campaign. Indiegogo says that a total of 596 people visited the project when it was live. Thus roughly 7% of all people who came to the site participated. It is harder to know how many people saw information about the campaign without coming to the site. Estimating based on numbers based on the blog's readership, Twitter reach and other sources puts the number at around 5000 globally (with a fairly large margin of error). This would indicate a conversion rate of 1% of all the people who saw any information about the campaign. In reality the percentage is lower since many of the contributors were people who did not really need convincing. Thus the conversion rate is probably closer to 0.5% or even lower.

The project was set up so that 300 contributors would have been enough to make the project a success. Given the number of people using Meson (estimated to be in the tens of thousands) this seemed like a reasonable goal. Turns out that it wasn't. Given these conversion numbers you'd need to reach 30 000 – 60 000 people in order to succeed. For a small project with zero advertising budget this seems like a hard thing to achieve.

On the Internet everything drowns

Twitter, LinkedIn, Facebook and the like are not very good channels for spreading information. They are firehoses where any one post has an active time of maybe one second if you are lucky. And if you are not, the platforms' algorithms will hide your post because they deem it "uninteresting".  Sadly filtering seems to be mandatory, because not having it makes the firehose even more unreadable. The only hope you have is that someone popular writes about your project. In practice this can only be achieved via personal connections.

Reddit-like aggregation sites are not much better, because you have basically two choices: either post on a popular subreddit or an unpopulare one. In the first case your post probably won't even make it on the front page, all it takes is a few downvotes because the post is "not interesting" or "does not belong here". A post that is not on the front page might not as well even exist; no-one will read it. Posting on an non-popular area is no better. Your post is there but it will reach 10 people and out of those maybe 1 will click on the link.

New sites are great for getting the information out, but they suffer from the same popularity problem as everything else. A distilled (and only slightly snarky) explanation is that news sites write mainly about two things:
  1. Things they have already written about (i.e. have deemed popular)
  2. Things other news sites write about (i.e. that other people have deemed popular)
This is not really the fault of news sites. They are doing their best on a very difficult job. This is just how the world and popularity work. Things that are popular get more popular because of their current popularity alone. Things that are not popular are unlikely to ever become popular because of their current unpopularity alone.

Unexpected requirements

One of the goals of this campaign (or experiment, really) was to see if selling manuals would be a sustainable way to compensate FOSS project developers and maintainers for their work. If working this would be a good way for compensation, because there are already established legal practices for selling books across the world. Transferring money in other ways (donations etc) is difficult and there may be legal obstacles.

Based on this one experiment this does not seem to be a feasible approach. Interestingly multiple people let me know that they would not be participating because the end result would not be released under a free license. Presumably the same people do not complain to book store tellers that "I will only buy this Harry Potter book if, immediately after my purchase, the full book is released for free on the Internet". But for some reason there is a hidden assumption that because a person has released something under a free license, they must publish everything else they do under free licenses as well.

These additional limitations make this model of charging for docs really hard to pull off. There is no possibility of steady, long term money flow because once a book is out under a free license it becomes unsellable. People will just download the free PDF instead. A completely different model (or implementation of the attempted model) seems to be needed.

So what happens next?

I don't really know. Maybe the book can get published through an actual publisher. Maybe not. Maybe I'll just take a break from the whole thing and get back to it later. But to end on some kind of a positive note I have extracted one chapter from the book and have posted it here in PDF form for everyone to read. Enjoy.

sunnuntai 12. toukokuuta 2019

Emulating rpath on Windows via binary patching

A nice feature provided by almost every Unix system is rpath. Put simply it is a way to tell the dynamic linker to look up shared libraries in custom directories. Build systems use it to be able to run programs directly from the build directory without needing to fiddle with file copying or environment variables. As is often the case, Windows does things completely differently and does not have a concept of rpath.

In Windows shared libraries are always looked up in directories that are in the current PATH. The only way to make the dynamic linker look up shared libraries in other directories is to add them to the PATH before running the program. There is also a way to create a manifest file that tells the loader to look up libraries in a special place but it is always a specially named subdirectory in the same directory as the executable. You can't specify an arbitrary path in the manifest, so the libraries need to be copied there. This makes Windows development even more inconvenient because you need to either fiddle with paths, copy shared libraries around or statically link everything (which is slooooow).

If you look at Windows executables with a hex editor, you find that they behave much the same way as their unixy counterparts. Each executable contains a list of dependency libraries that it needs, such as helper.dll. Presumably what happens is that at runtime the dynamic linker will parse the exe file and pass the library names to some lookup function that finds the actual libraries given the current PATH value. This raises the obvious question: what would happen if, somehow, the executable file would have an absolute path written in it rather than just the filename?

It turns out that it works and does what you would expect it to. The backend code accepts absolute paths and resolves them to the correct file without PATH lookups. With this we have a working rpath simulacrum. It's not really workable, though, since the VS toolchain does not support writing absolute paths to dependencies in output files. Editing the result files by hand is also a bit suspicious because there are many things that depend on offsets inside the file. Adding or removing even one byte will probably break something. The only thing we can really do is to replace one string with a different one with the same length.

This turns out to be the same problem that rpath entries have on Unix and the solution is also the same. We need to get a long enough string inside the output file and then we can replace it with a different string. If the replacement string is shorter, it can be padded with null bytes because the strings are treated as C strings. I have written a simple test repository doing this, which can be downloaded from Github.

On unix rpath is specified with a command line argument so it can be padded to arbitrary size. Windows does not support this so we need to fake it. The basic idea is simple. Instead of creating a library helper.dll we create a temporary library called aaaaaaaaaaaaaaaaaaaaaaaa.dll and link the program against that. When viewed in a hex editor the executable looks like this.

Now we can copy the library to its real name in a subdirectory and patch the executable. The result looks like this.

The final name was shorter than what we reserved so there are a bunch of zero bytes in the executable. This program can now be run and it will always resolve to the library that we specified. When the program is installed the entry can be changed to just plain helper.dll in the same way making it indistinguishable from libraries built without this trick (apart from the few extra null bytes).

Rpath on Windows: achieved.

Is this practical?

It's hard to say. I have not tested this on anything except toy programs but it does seem to work. It's unclear if this was the intended behaviour, but Microsoft does take backwards compatibility fairly seriously so one would expect it to keep working. The bigger problem is that the VS toolchain creates many other files, such as pdb debug info files, that probably don't like being renamed like this. These files are mostly undocumented so it's difficult to estimate how much work it would take to make binary hotpatching work reliably.

The best solution would be for Microsoft to add a new linker argument to their toolchain that would write dependency info to the files as absolute paths and to provide a program to rewrite those entries as discussed above. Apple already provides all of this functionality in their core toolchain. It would be nice for MS to do the same. This would simplify cross platform development because it would make all the major platforms behave in the same way.

keskiviikko 8. toukokuuta 2019

Why crowdfunding freely licensed documentation is illegal in Finland

On the Meson manual crowdfunding page it is mentioned that the end result can not be put under a fully free license. Several people have said that they "don't believe such a law could exist" or words to that effect. This blog post is an attempt to to explain the issue in English as all available text about the case is in Finnish. As a disclaimer: I'm not a lawyer, the following is not legal advice, there is no guarantee, even that any of the information below is factual.

To get started we need to go back in time a fair bit and look at disaster relief funds. In Finland you must obtain a permit from the police in order to gather money for general charitable causes. This permit has strict requirements. The idea is that you can't just start a fundraising, take people's money and pocket it, instead the money must provably go to the cause it was raised for. The way the law is written is that a donation to charity is done without getting "something tangible" in return. Roughly if you give someone money and get a physical item in return, it is considered a sales transaction. If you give money to someone and in return get a general feeling of making the world better in some way, that is considered a donation. The former is governed by laws of commerce, the latter by laws of charity fundraising.

A few years ago there was a project to create a book to teach people Swedish. The project is page is here, but it is all in Finnish so it's probably not useful to most readers. They had a crowdfunding project to finish the project with all the usual perks. One of the goals of the crowdfunding was to make the book freely distributable after publishing. This is not unlike funding feature work on FOSS projects works.

What happened next is that the police stepped in and declared this illegal (news story, in Finnish). Their interpretation was that participating in this campaign without getting something tangible in return (i.e. paying less than the amount needed to get the book) was a "charitable donation". Thus it needs a charity permit as explained above. Running a crowdfunding campaign is still legal if it is strictly about pre-sales. That is, every person buys "something" and that something needs to have "independent value" of some sort. If the outcome of a project is a PDF and that PDF becomes freely available, it can be argued that people who participated did not get any "tangible value" in exchange for their money.

Because of this the outcome of the Meson manual crowdfunding campaign can not be made freely available. This may seem a bit stupid, but sadly that's the law. The law is undergoing changes (see here, in Finnish), but those changes will not take effect for quite some time and even when they do it is unclear how those changes would affect these kinds of projects.

keskiviikko 1. toukokuuta 2019

The Meson manual crowdfunding campaign

The Meson Build system has existed for over six years. Even though we have a fairly good set of documentation, there has not been a standalone user's manual for it. Until now.

A crowdfunding campaign to finance the manual has just been launched on Indiegogo. The basic deal is simple, for 30€ you get the final book as a PDF. To minimize work and save trees, there is no physical version. There are also no stickers, beer mats or any other tchotchkies. There are a few purchase options as well as opportunities for corporate sponsorships. Please see the Indiegogo project page for further details. If there are any questions about this campaign feel free to contact me. The easiest way is via email.

Overall I'm quite excited about this campaign. One reason is obviously personal, but the other has to do with sustainability of FOSS projects in general. There has been a lot of talk about how maintainers of open source projects can get compensated for their work. This campaign can be seen as an experiment to see if the crowdfunding model could work in practice.

So if you are just getting started with building software and want a user manual, buy this book. If you have basic experience with Meson and want to dive deeper, buy this book. If you are a seasoned veteran and don't really need a book but want to support the project (specifically me), buy this book. Regardless of anything else, please spread the word on your favourite social media and real world venues of choice.

Let the experiment begin!