Circular Adventures IX: The Poor Ring Buffer That Had No Tail

“If you hold a cat by the tail, you learn things you cannot learn any other way.”
― Mark Twain

The typical use case for a ring buffer is a producer consumer scenario, where a producer sometimes produces data faster than the consumer can consume. Eventually, however, the consumer will catch up. This typical use case can be summarized as “short term buffering of bursts of data”.

But what happens if buffered data is not consumed fast enough and the ring buffer becomes full? Answer: adding another element will drop the oldest element, as can be seen by looking at the implementation of the ‘add’ method:

After the new element is added to the buffer, the head index is incremented (modulo ‘BUFSIZE’). If it now points at the tail index, the tail index is incremented (modulo ‘BUFSIZE’) as well, which effectively removes the oldest element from the ring buffer, making space for a new ring buffer element to be added. Here’s an example of this happening to a ring buffer that already holds 9 elements (why not 10? The head index is ‘exclusive‘ and points at the location where the next added element will go):

Calling ‘add’ in this situation advances the head and the tail index by 1:

This will be continue for every subsequent ‘add’. Here’s how the ring buffer looks like after six more calls to ‘add’:

Why am I telling you all this? Because there’s a ring buffer use case, where a producer endlessly produces data that is never consumed. I call this the “history buffer” use case where record is kept over the last N events, similar to how a flight recorder operates.

If a ring buffer is used as a history buffer, it is always fully loaded. Thus, the ‘add’ operation is unnecessarily inefficient, as the ‘if (head == tail)’ conditions is always true. So let’s get rid of it:

This naturally leads to another optimization: the incremented value of ‘head_’ is the current value of ‘tail_’. Thus, we just set the new ‘head_’ to the current value of ‘tail_’ and only increment ‘tail_’:

That’s even better, isn’t it? But there’s more! The tail is usually only used when consuming elements, which we don’t do for the history buffer use case. Why maintain it’s value at all? Plus, if we need it later (as we shall see shortly), we can always compute it from the head, since it is one element ahead of head (sounds a bit weird, doesn’t it? The tail is always ahead of the head):

Adding to the ring buffer has definitely become simpler and cheaper, but you probably ask yourself how to retrieve the history data stored in our ring buffer. As usual, there are many ways, but the one that I find most useful is through the standard library’s way of doing things, namely iterators. ‘begin()’ and ‘cbegin()’ simply return the tail, which is — as we already know — one element ahead of ‘head_’:

‘end()’ and ‘cend()’ just return ‘head_’.

In the simplest case, the iterators returned are forward iterators, which means that they only provide ‘operator++()’. As limited as forward operators are, they allow you to use many useful algorithms from the standard library, including:

But there’s probably another nagging question on your mind: what if the ring buffer is not fully loaded? What if, for instance, only 3 elements have been added so far to a 10-element ring buffer holding doubles? In this case, the 7 unused elements will hold default-initialized doubles, which can be easiliy skipped over:

Most of the time, this extra work is unnecessary in history buffer use cases, as a) the ring buffer is quickly filled and from this point on always fully loaded and b) default constructed elements don’t harm in typical history buffer use cases.

I like to call this particular variant of ring buffer “Manx buffer”, named after a peculiar breed of cat, called Manx, whose salient feature is the lack of tail.

Choosing a Manx buffer over a regular ring buffer may make sense in the following cases:

  • The elements added are never consumed but rather kept to have chronological, historical data.
  • The size of the element type is small, such that the cost of maintaining the tail is significant compared to the overall cost of adding an element.
  • Elements are added at a rapid rate.

An example of when a Manx buffer can prove useful is a data collection system for an aircraft that records the last 10 minutes of accelerometer readings for roll, pitch, and yaw as double values.

You can find my 70 lines implementation of a Manx buffer here.

How To Attract Great Software Developers, Part I: The Man In The Mirror

“Everything is energy and that’s all there is to it. Match the frequency of the energy you want and you cannot help but get that reality. It can be no other way”
— Albert Einstein

These days, almost every software company is looking for software developers. Not just any software developers, mind you, it’s great software developers that everybody’s craving.

Such companies know that — as has been confirmed again and again in many studies over the last decades — great software developers are easily 10 times as productive as average software developers. Productive as in “able to craft quality products”. It’s not about intelligence, nor the talent to give great talks, write awesome research papers, file patents, implement one prototype after another. It’s not about ranks, titles, grades, number of diplomas or PhDs. It’s all about the great developer’s ability to ship money-generating products on time. Those people are few and far between.

The sad truth is that the main problem of such companies is often not that they have a shortage of great developers — they suffer from far too many below average developers (again, in terms of money-generating productivity). These companies don’t ship awesome products, not to mention on time.

As a countermeasure, they recruit for great developers. What they often forget to do is take a critical look in the mirror. If they did, they would understand that what they try to do is akin to a hobo courting a beautiful princess. It’s nothing more than an exercise in futility! To attract someone attractive, you have to be attractive yourself. It’s that easy!

Realistically, the great developers that such companies are after are already with a highly attractive employer. Why should they change down?

Desperate as these companies are, they employ tricks that are as old as mankind: making themselves appear more beautiful than they really are. They dye their hair, they apply tons of makeup, but it’s just a cover up for something that’s ugly or not there at all.

They try to lure great developers in by telling them that they will be working in a modern workspace, be part of a global, agile team of the brightest minds, that they will shape the future of a whole industry, and so on.

Obviously, everybody, not just great developers, knows that this is pure BS and that a company which resorts to such measures must be a) far from great and b) really desperate.

The latter naturally attracts a special breed of developers. Con artists, who also apply tons of makeup to hide their shortcomings, which I usually refer to as Non-Painters; and so the vicious circle continues for the poor company. Birds of a feather flock together. Pretenders attract pretenders. But the converse is equally true.

Let’s conclude this installment by postulating the first rule of hiring great developers:

To be able to attract truly great developers, a company has to be truly great itself.

In the next installment, we’ll take a look at the hallmarks of great software companies and what great developers are attracted to.

Avoid Static Class Members As Much As You Can

“Most people want to avoid pain, and discipline is usually painful.”
— John C. Maxwell

Ah, static class members! They pop up in every C++ project. In most cases, however, their use is not justified. I try to avoid static members as much as possible, and so should you. Here’s why.

Let’s start by revisiting the mother of all static member text book examples. It demonstrates that by using the ‘static’ keyword, state can be shared among all instances of a class:

The reasoning in these text books usually goes like this: The total number of employees obviously doesn’t belong to a particular employee instance. Such information is shared by all instances, so let’s use ‘static’ here.

Don’t write code like this. It’s so flawed I don’t even know where to start. But I’ll try anyway.

If you believe that something is not the responsibility of an instance, you should not add this responsibility to the instance’s class either. Calling the static member function like so:

Is still a call on Employee, so it’s still a responsibility of the class. Instead, assign the responsibility to keep track of employees to a higher-level entity, like a Company or an Employer class, which manages Employees in a container, a std::vector, for instance. Such a higher-level class would provide a regular instance method that returns the total number of employees:

With this new design, in order to find out how many employees work for a company, you do the natural thing — you ask the company, not a static member function of class Employee. (Also note that in class Company, employeeCount is declared as ‘const’ to signify that it doesn’t update any data. There’s no such thing as ‘const’ for a static member function.)

What else is uncool about the original Employee class? Like every non-const static member ‘s_employeeCount’ needs to be defined exactly once outside the class, which is typically done in the corresponding .cpp file.

Further, manually incrementing and decrementing the count is cumbersome — the std::vector in Company will do this automatically for us. On top of that, the original design is not exception-safe. Imagine that initialization code in the constructor body of Employee throws an exception after the count has already been updated. The Employee instance will have never officially existed but the count indicates otherwise. You need to add extra exception handling code around the count increment to safeguard against such cases.

The original design is also sub-optimal as static members impede unit testing. After every unit test case, you have to make sure that the static data is cleaned up (or reinitialized) for the next unit test case. Since the static data is usually private, one often has to add extra public static initialization or setter methods to do the job, thus complicating the class interface even more. In general, static member functions can’t be mocked (at least if you’re using Google Mock) so it might be difficult if not impossible to simulate particular behavior of a static method to obtain code/branch coverage in a client component.

So are there any legitimate uses of static members in C++ classes? In my view, there’s only one: public (and protected) symbolic constants:

Private constants or private utility methods that do not touch instance data are usually better defined as anonymous namespace members within the class’ .cpp file — this avoids cluttering up the class definition in the header file with things that bear no relevance to the user of a class (aka implementation details).

But what about public utility functions that don’t use instance data? Shouldn’t they be declared ‘static’?

The official answer is probably ‘yes’, and there are compilers and tools (like clang-tidy) that suggest that you should declare a method ‘static’ in such situations. These days, however, I rather tend to ignore/suppress such warnings based on this reasoning: if a function is declared ‘public’, it’s part of a class’ interface. The fact that its implementation doesn’t touch instance data (today) is just an implementation detail that doesn’t need to be conveyed to the user of a class. I’ll pick a regular (virtual) method that I can mock over a static method any day:

This design clearly differentiates between interface and implementation and achieves loose coupling between the class and its clients. At runtime, clients can replace one implementation with another (e. g. optimized for speed, with caching, with logging, a mock and so on) without having to change the client code. All this would not have been possible had ‘factorial’ been declared ‘static’.

To sum it up:

  • There’s only one legitimate use-case for static members: symbolic constants
  • State shared by all instances of a class should not be shared in that class, but rather in an instance of a higher-level class
  • Static members prevent late (i. e. runtime) binding
  • Static data and static member functions make unit testing difficult

10 Rules For Working Successfully With Pull Requests

“Don’t expect to build up the weak by pulling down the strong.”
— Calvin Coolidge

Software development has always been a rich source of religious wars: emacs vs. vi, tabs vs. spaces, brace placement. Where do I stand regarding “pull requests” vs. “trunk-based” development? Even though it looks like the really hip developers opt for “trunk-based” these days, I’m clearly on the side of “pull requests”. But only if certain rules are followed.

Rule 1: Keep pull requests short

Don’t work on a feature branch for days. That’s against the idea of continuous integration. Not only do you risk integration problems, people will have a hard time reviewing your large changeset. Instead, split-up the pull request into several small(er) pull requests, for instance: preparatory refactoring, main implementation, clean-up, additional unit tests to improve code coverage. A pull request comprising 50 changed lines is easy to review, a pull request comprising 1000 changed lines, hard. What is easy to do gets done, what is hard to do usually gets delayed.

Rule 2: Constantly collect ideas on your way

Resist the temptation to cram more into your pull request than necessary. If you discover a badly named class or a way-too-long function, don’t clean it up right now. Make a note of it, add a TODO, or, even better, create a technical debt ticket. This keeps your pull requests short (see rule 1) and provides you and your teammates with work while waiting for feedback (rule 3). When implementing, review existing code and always be on the lookout for things to improve. Collect ideas for hard times like a squirrel collects nuts.

Rule 3: Be patient while waiting for feedback

Most developers, after having published their pull requests, only have one thing on their mind: integrating it asap. If they haven’t got any feedback or approval within two hours, they start hassling teammates, complain that they are blocked, do all sorts of whining. Such developers need to realize that while their changes mean all the world to them, they most likely don’t mean much to others. What developers should really have on their mind after publishing a pull request is this: a) are there any open pull requests from others that I could review? b) are there any technical debt tickets that I could tackle? If developers follow rule 1 and rule 2, there’s little chance that they ever run out of work.

Rule 4: Be kind and grateful when giving and receiving feedback

Nobody likes being criticized but every criticism should be viewed as an opportunity to learn for all involved parties. When you give criticism, be constructive and avoid cynical and arrogant remarks like “Only rookies would use a for loop here”. If you get harsh and unfair criticism, don’t take it personally and don’t add to the fight. Calm is contagious.

Rule 5: The author has the final judgment

I once was part of a team where people had a pull request battle over what’s the best way to initialize a string constant in C++. “Proof of efficiency” was shown by contestants in the form of disassembly for various platforms and they all showed different results. This ridiculous battle went on for days. Let’s not forget this: everybody is welcome to criticize the author’s code, but in the end, it’s the author’s decision what to accept and what not. The pull request doesn’t have to satisfy everyone and a software project is not a democracy. A good way to end a fight is this: “Thanks for your feedback, but I’ve decided to keep the code as it is”.

Rule 6: Advertise your pull request

If you want to make sure that nobody looks at your pull request, use a meaningless title full of spelling mistakes like “REwork for prformace”. If not, craft the title carefully to express it’s purpose and importance. I’m sure that the same pull request with this title will be reviewed much sooner: “Fix: Use a faster scanning algorithm to prevent nightly build timeouts”. The same goes for the description of the pull request. Give a crisp executive summary of the motivation and what you are trying to achieve. Don’t give long sermons to avoid TL;DR.

Rule 7: Review your own pull request

Before publishing your pull request, carefully review it yourself. It’s amazing what you can detect yourself, especially silly goof-ups and typos. Make sure that the pull requests is of highest quality, to the best of your knowledge. Don’t waste your reviewer’s precious time or they will soon start wasting yours by not looking at your pull requests anymore.

Rule 8: Publish only when you’re done

There’s nothing more annoying for a reviewer than having to constantly re-review because the author keeps on pushing changes. If you find out that your code needs rework, set your pull request to draft state. Publish it again once you’re done.

Rule 9: Proactively explain unusual changes

Experienced developers know that code shall be written such that it is self-explanatory and comments should be only used to document surprises. Still, certain changes to obvious, non-commented code might still be surprising to reviewers. In such cases, add an explanatory review comment yourself such that reviewers don’t have to ask you about it.

Rule 10: Spread the word

If teammates unknowingly violate these rules, educate them about these rules. If they don’t care or continue to deliberately violate these rules, let them wait next time they want you to review their pull request. Show, don’t tell.

Bug Hunting Adventures #16: Lame Surveillance

“Under observation, we act less free, which means we effectively are less free.”
― Edward Snowden

Imagine a distributed surveillance system where recorded video files are uploaded to a central server at regular intervalls.

Due to limitations of the transport protocol, video files must be split up in chunks and no chunk may exceed 1 GB (10^9 bytes). On top of that, in high-load scenarios, the server might shorten a chunk even more, in which case instead of N bytes only K bytes are transmitted. Naturally, the N-K bytes that were not transmitted need to be sent with the next chunk upload.

Everything works fine, all unit and system tests passed. Once deployed, however, sysadmins from the central server team started lamenting that the video files were arriving at a glacial pace. What’s wrong with this code?

Solution

Do They Treat You Like A Superuser?

“A good workman is known by his tools”
— proverb

The process of getting admin rights as a corporate software developer is definitely on a spectrum. Over the last 20+ years, I’ve written code for more than ten companies and boy, do their policies differ!

In one case, I had full admin rights from day one. In more typical cases, I had to start a workflow to request admin rights which would arrive within hours to days. In one extreme case, I had to do an online training about the dangers of working with admin rights before I could start the workflow. After I passed the exam and once my request was approved (7 days later), I would be granted admin rights only for a limited number of time (180 days at most). Even worse — the online training course would need to be taken again as well!

Let’s meditate a little bit on this latter case. Too me, it’s an utter catastrophe. As software developers, we constantly need to maintain and tweak our PC, our beloved toolbox. We need to install or upgrade development tools, device drivers and the like, sometimes just for the purpose of experimentation and learning. What if I wanted to switch to a newer version of g++ one day only to find out that my ‘sudo’ rights had expired? Sure, I could start the workflow again, wait a couple of days for approval, but why? Such processes are nothing but a nuisance that break developers’ flow and inspiration while not adding any real security.

A software developer is not a regular user — a software developer is a superuser, literally. If a company has to have their software developers take training courses to ensure that they don’t work in a root shell all day they should not have been hired in the first place. Doesn’t it border on insulting if you learn in such a training that you should not open email attachments from unknown senders, especially while being logged-in as root? You don’t say!

If a company doesn’t give you unlimited superuser rights within a couple of hours, you’re definitely not treated like a superuser. You’re rather treated like a regular office worker who has no clue about how computers work, let alone computer security.

It’s not just about wasted time. It’s about lack of empowerment and trust. But it’s mainly about a missing software culture: are you viewed as precious human capital that develops top-notch software products which will make the company thrive, or are you rather viewed as a schmuck that poses an severe risk to the company?

A company with good software culture understands the chief need of creative makers, which is: working on interesting projects in a frictionless, libertarian environment where they can spend most of their time doing what they love most: craft exciting software.

Restricting software developers in terms of admin rights is just one problem of companies lacking good software culture, but it’s symptomatic. While such shops might manage to lure in great creators, they will certainly not be able to retain them in the long run.