Performance Considered Essential

I sometimes hear fellow engineers say “performance is not a concern in our project”, or “performance doesn’t matter”. I can understand that, in certain projects, performance is not a major concern; and also that, following usual engineering techniques, performance will be in an acceptable range, without needing to dedicate time to performance related activities. But I cannot agree, even in these projects, that performance doesn’t matter.

What I find more worrying is that these performance ignoring projects lead to generalisations: programmers claim that performance should be ignored while building software.

The current article tries to counter this trend and argue that all software problems are, in one way or another, a performance problem. That is, performance cannot be fully ignored. I’ll give a couple of arguments as to why we can’t ignore performance; among them, I attempt to prove that without the performance concern, Software Engineering would be mostly a solved domain.

Misinterpreting Knuth

The proponents of the idea that performance should be ignored often quote Knuth, in the simplified form [Knuth74]:

premature optimization is the root of all evil

Just quoting this leaves out the context, which contains important details. A more appropriate quote would be [Knuth74]:

The real problem is that programmers have spent far too much time worrying about efficiency in the wrong places and at the wrong times; premature optimization is the root of all evil (or at least most of it) in programming.

This is a far more nuanced quote. It’s not a problem with efficiency in general, but a problem with spending too much energy on improving performance in the wrong places.

But even this larger quote does not capture Knuth’s full intent. In the surrounding paragraphs, he is criticising people who condemn program efficiency [Knuth74]:

I am sorry to say that many people nowadays are condemning program efficiency, telling us that it is in bad taste.

That is, often the simple quoting of Knuth contradicts the idea that Knuth tried to make.

Frequently, when I hear Knuth’s short quote in the wrong way, I have another quote ready:

Ignorance [is] the root and stem of all evil. ~ Plato (disputed)

Ignoring performance considerations can lead to unusable software. Moreover, as we will further explain, performance is an essential part of software engineering.

One algorithm to rule them all

In this section, we will assume that the performance of programs is not relevant at all. We are free to implement any algorithm, with any complexity, as long as it solves our problem; moreover, we should look for simpler algorithms.

We might be proving something that is obvious for many readers. We want to disambiguate some nuances and make it clear that performance is more important than we generally consider. The aim is not to simply convince software developers that performance matters, but rather to be more helpful to theoreticians of software industry. This might help in refocusing our perception of performance concerns.

Theorem. There is an algorithm that can solve all software problems, if one can define an acceptance function for such problems.

Before proving this theorem, we need some clarifications. First, we assume that all programs transform data, and we can express our algorithm as a data transformation. That is, we have input data In, and we are producing some output data Out. It is irrelevant for our goals how we encode information in the input and output data, and our treatment of time. For example, if the problem we are trying to solve is a GUI, then the inputs would be the set of key presses, mouse movements and clicks, all in relation to time; one can find a way to properly encode this into In data. Encoding time is not easy, but we assume that this can be done.

Another important assumption is that the problems we are trying to solve have solutions. We cannot solve a problem that can’t be solved. In other words, for each problem, there is at least one sequence of bits that would be accepted for that problem.

To properly build our algorithm, we need an acceptance function. In code, the acceptance function would have the following signature:

  bool solution_is_valid(In data, Out result);

Our algorithm can be represented by a function:

  Out the_one_algorithm(In data);

such as:

  solution_is_valid
    (data, the_one_algorithm(data)) == true.

We will define only one variant of the_one_algorithm, and we assume that the solution_is_valid is given for each type of software problem we need to solve.

To define our algorithm, we consider that In and Out are bitsets with variable number of bits. We also assume that we don’t have limitations on how many bits we can represent.

With all these discussed, Listing 1 is our fantastic algorithm.

bool check_solution(int n, In data, Out& res);

Out the_one_algorithm(In data) {
  Out res; // initially zero bits
  while (true) {
    // keep adding bits
    res.add_bit(0);
    // backtrack until we find an acceptable
    // solution
    if ( check_solution(0, data, res) )
      return res;
  }
}
bool check_solution(int n, In data, Out& res) {
  if ( n == res.size() ) {
    return solution_is_valid(data, res);
  }
  else {
    res[n] = 0;
    if ( check_solution(n+1, data, res) )
      return true;
    res[n] = 1;
    if ( check_solution(n+1, data, res) )
      return true;
  }
  return false;
}
			

Our algorithm is also known as the backtracking algorithm. We are applying it to all possible problems for which we have an acceptance criterion.

The backtracking algorithm will iterate over all possible combinations of output bits, and we are guaranteed that there is at least one sequence of bits that satisfies the acceptance function. This means that we are guaranteed that our algorithm finds our solution.

Q.E.D.

Algorithm analysis

Positives:

• can be used to solve any problem (that is solvable, and that has an acceptance function)
• it’s simple to understand

Negatives:

• performance: complexity is O(2ⁿ), where n is the smallest number of bits for an acceptable solution

The programmers who argue that performance doesn’t matter should argue that this algorithm is great, as it doesn’t have any (major) negatives. It’s the perfect algorithm!

However, one might argue that we are moving the problem somewhere else. As it’s easy to solve the original problem, the difficulty moves towards encoding the problem and defining the acceptance function. Let’s analyse these.

We might have a complex system comprising multiple parts, and it might be hard to combine them into an appropriate encoding. But, as system parts should be simpler to encode, we can simply apply a recursive decomposition pattern to the problem of encoding. That would give us a process for encoding all the problems.

Moreover, encoding is also a software problem. We can apply the same algorithm to generate solutions for it. The reader should agree with me that deciding on the encoding of the problem should be less complex than solving the complete problem.

The other aspect is the acceptance function. In most cases, this is a simpler problem than the solution of the problem itself. As this is problem-dependent, we cannot give a universal algorithm for it; but, we can certainly apply our backtracking algorithm to simplify the acceptance test too.

Thus, even if the complexity doesn’t completely disappear, we’ve separated it into two parts, which, for the vast majority of problems, should be simpler than the entire problem (which needs to include encoding and acceptance testing).

Lehman’s taxonomy

Let us analyse whether this algorithm applies to different types of programs. We use the Lehman taxonomy [Lehman80] for this analysis.

Lehman divided the set of programs that can be built into 3 types :

• S-Programs
• P-Programs
• E-Programs

S-Programs are simple programs; the specification can be used to easily derive the functionality of the program. We can derive the acceptability of the solution directly from the specification of the problem. Most mathematical problems are good examples of S-Programs.

P-Programs are slightly more complex. Precise specifications cannot be directly used to derive the acceptability of the solution. The acceptance function can be derived from the environment in which the program operates.

The example that Lehman gives for P-Programs is a program to play chess. We cannot define the quality of the program just by looking at the chess rules. The rules can be relatively simple, but applying them can generate good chess programs or terrible ones. We have to define the acceptance criteria of the program by looking at how well the program fares in competition with other actors (humans, other chess programs, etc.). The evaluation of a chess program should always be done in its operating context.

A good technique for evaluating P-Programs is comparison: we can find a reference model, and then compare the behaviour of the program with this model.

E-Programs are programs that are even more complex. They embed human activities into their output. They can’t be separated from the social contexts in which they operate. Any program that has a feedback loop that includes human activities is an E-Program. A good current example of an E-Program is a road traffic program. The program gives traffic information to users; users take that into account when driving, and their driving behaviour is fed in as traffic input to the program. Users driving alternative routes will change the traffic conditions for the main routes and the alternative routes.

E-Programs should also be evaluated in their operating contexts. This time, the environment is more complex.

Kevlin Henney also frequently discusses this taxonomy in a more recent context. See for example [Henney19].

Now, let’s analyse how this taxonomy affects our algorithm.

For S-Programs, we can derive the acceptance functions directly from the specification of the problem. This is the simplest case.

P-Programs are harder to deal with. We cannot derive the acceptance function directly from the specification. But, if this is a software problem, there needs to be an acceptance criterion. Here, we have a hint: it’s often the case that it’s easier to compare the outputs of our program with another model (by another program or involving humans). The comparison can be slow (especially if it involves humans), but for the current discussions we have said that performance can be ignored.

For the chess program example, for every possible solution of the program, after ensuring that it follows the basic rules, we can use the output to play against human players (or other computer programs). Finding a decent solution may take more than the expected lifetime of the universe, but performance is not a concern here.

Finding an acceptance function for E-Programs involves a similar process. There are some basic correctness checks that we can apply automatically, but then we can ask human opinion whether the generated program is acceptable or not. This time, it’s mandatory for us to involve human feedback. Again, this can be extremely expensive, but we are entirely ignoring performance aspects.

With this, we’ve argued that our algorithm applies to all types of problems.

Bottom line

If there are no performance constraints, we can solve all the problems by using the above algorithm. But the time to solve the problem can be incredibly large.

Typically, the more complex the problem we are solving, the more bits we need in the output data. If we require n bits for the solution, then the time complexity of the algorithm is in the order of O(2ⁿ).

The age of the universe is 14 billion years (approx. 4.4×10¹⁷ seconds). Let’s assume that we have a computer with the core frequency of 3.2 GHz (3.2×10⁹ cycles per second). With these, we can calculate that our computer can execute about 1.4×10²⁷ CPU cycles from the beginning of the universe. This number is less than 2⁹¹.

This means that problems that have more than 91 bits in the output require more than the entire life of the universe to compute. But, except for trivial problems, most problems require more than 91 bits in their output.

That is, we have a simple algorithm that can solve all the problems, but for performance reasons, we cannot apply it. Thus, all software problems are, in a way, performance problems.

This might be seen as a trivial result, but it is a fundamental aspect of software engineering. It’s just as fundamental as “software is essential complexity” [Brooks95]. We might be saying now that software is performance-constrained essential complexity.

Convergent perspectives

Breaking the Enigma

One of the important points in the history of programable computers was the development of the computers in World War 2 to break the Enigma cipher machine.

The Enigma machine at that time was not breakable with a brute force attack (i.e., performance limitations). As a consequence, the allies started building the Colossus computer; this was the world’s first programable, electronic, digital computer [WikiColossus]. So, one way to think of it, the building of programable computers is due to performance considerations.

Furthermore, to speed up attacks on the Enigma machine, the allies developed a series of strategies to allow them to have a higher likelihood of deciphering German messages in short time [WikiEnigma]. That is, at the birth of the computer industry, the first efforts were targeting improving performance.

Performance concerns were central to the development of computers.

The sorting algorithm

Let’s look at the sorting algorithms. One of the most well-studied fields in Software Engineering. Probably all software engineers spent hours at looking at various sorting algorithms. Why is that?

Bubble Sort is one of the simplest sorting algorithms. And yet, this is rarely used in practice. That’s because it is an inefficient algorithm. Its complexity is O(n²); and even so, it’s slower than Insertion Sort that has the same complexity.

And, Bubble Sort is not the simplest sorting algorithm. A simpler one would be BogoSort (permutation sort). This can be expressed (in Python as):

  def bogosort(elements):
    while not is_sorted(elements):
      shuffle(elements)
    return elements

Very simple to understand. Yet, the performance is terrible: O((n−1)n!).

This is also an indication of why performance matters a lot for Software Engineering.

Textbooks

If one wants to learn programming, one needs to learn about algorithms and data structures. One popular book for learning this is Introduction to Algorithms [Cormen22]. The first part of the book, called ‘Foundations’, spends a great deal of time talking about performance of algorithms. Performance-related discussions are present before introducing the first algorithm.

This is yet another strong indication that performance is an important aspect of Software Engineering.

Full-stack development

In recent times, we have often used the phrase ‘full-stack development’ to refer to a combination of skills for web development that includes expertise both in frontend and backend development. But, as Kevlin Henney points out [Henney19], this is just a narrow view of the stack. If we look at the bottom of the stack, we typically exclude device driver programming, operating-system programming, low-level libraries, etc.

Now, all these lower level layers in our stack are typically written in languages like C and C++. The reason for this is performance. To have decent performance at upper levels, we need to have good performance at lower levels.

If performance was not a concern at the operating system level, we would probably have OSes that would boot up in hours on modern hardware. I don’t believe this is something that is acceptable to our users.

Performance and the rest of quality attributes

Architecturally speaking, performance is a quality attribute for the software system. Other quality attributes that are generally applicable include modifiability (how easy it is to change the code), availability (what’s the probability for operating the system under satisfactory conditions at a given point of time), testability (how testable is the software), security (how secure is the software system), usability (how easy is it to use the software system).

We briefly investigate here whether we can say about other quality attributes what we said about performance.

One can argue that modifiability is as important as performance. This can be argued to a large extent, but one cannot get as far as we have with performance. Once we have a framework for writing code (language, input methods, building and running), we might not need to spend too much time on modifiability. Some programs are just written once, and then never changed (rare, but it is still the case).

While we are constantly striving to improve the techniques for writing software more easily (i.e., reduce accidental complexity) this is not the dominant concern in software. As Brooks argues [Brooks95], modifiability is an accidental concern, not an essential one. Thus, at least ontologically speaking, it’s not as important.

Don’t get me wrong: modifiability is very important to software engineering, but it’s not an essential part of it.

We won’t insist on the other quality attributes: availability, testability, security, usability. There is still a lot of software for which these may not be applicable. One may not think of the availability and security of a sorting algorithm, one might choose not to test certain software, and, for certain problems, it’s hard to define what usability means. These quality attributes are nowhere near as important as performance.

This leaves us with the thought that performance is the most important quality attribute for a software system, more important than modifiability (at least from a theoretical perspective).

Conclusions

Performance is at the core of Software Engineering. It’s not just important, it’s essential. Otherwise, this would have been a dull discipline: we have one algorithm that can be applied to all the problems, it’s just a matter of defining an appropriate acceptance function. But, as we know, this is completely impractical.

To some degree, all software solutions have performance as a concern. This is proven by the entire industry. This is why we use certain algorithms (e.g., QuickSort) over others (e.g., BogoSort). This is why we continuously spend money on researching how to make our programs faster. And, this is why we have books to teach us the best algorithms we know so far.

The fact that some projects may not have important performance constraints doesn’t mean they don’t have performance constraints at all. It’s just that, in those limited domains, it is highly unlikely to go outside those constraints. For example, sorting a 10-element integer array can be done almost in any way possible if the code needs to run in under 100ms. But, most projects aren’t like that. As software tends to compose (software is essential complexity) inefficient algorithms, when composed, tend to extrapolate slowness; after a certain limit, software built with inefficient algorithms would be too slow.

This might have been a very long article for such a simple idea. But, unfortunately, engineering is not always glamorous, shiny and cool. Oftentimes, it ought to be boring and predictable. Yes, predictable, that’s the word we should associate more with Software Engineering. However, that is a topic for another article (or, set of articles).

References

[Brooks95] Frederick P. Brooks Jr., The Mythical Man-Month (anniversary ed.), Addison-Wesley Longman Publishing, 1995

[Cormen22] T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms (third edition), MIT press, 2022

[Henney19] Kevlin Henney, ‘What Do You Mean?’, ACCU 2019, https://www.youtube.com/watch?v=ndnvOElnyUg

[Knuth74] Donald E. Knuth, ‘Computer Programming as an Art’, Communications of the ACM 17 (12), December 1974

[Lehman80] Meir M Lehman, ‘Programs, Life Cycles, and Laws of Software Evolution’, Proceedings of the IEEE 68, no. 9, 1980, https://www.ifi.uzh.ch/dam/jcr:00000000-2f41-7b40-ffff-ffffd5af5da7/lehman80.pdf

[WikiColossus] Wikipedia, ‘Colossus computer’, https://en.wikipedia.org/wiki/Colossus_computer

[WikiEnigma] Wikipedia, ‘Cryptanalysis of the Enigma’, https://en.wikipedia.org/wiki/Cryptanalysis_of_the_Enigma

Lucian Radu Teodorescu has a PhD in programming languages and is a Software Architect at Garmin. He likes challenges; and understanding the essence of things (if there is one) constitutes the biggest challenge of all.