Are generics slow?

In the TCoffeeAndCode session about "Code Profiling, Optimization, Performance, and Memory Leaks", it has been mentioned that generics are slow. However, no specific details were given, and this topic deserves to be explained in more detail before people start indiscriminately removing generics from their codebases, hoping to gain some speed.

You can watch the session replay at: https://www.youtube.com/watch?v=hCFZv0I9TUk (minute 56)

How generics work

In order to understand how generics can impact speed, we need to know how generics work under the hood and why they are useful.

The simplest way to explain generics is to imagine you have some particular code you need to run on different types. And to achieve that, you copy-paste the code and replace one type with another and nothing else.

This is how generics work in C++, where they are not called generics, but templates. Instead of you having to copy-paste code and replace types, the compiler does that for you. Generic code is not actually compiled until you compile the whole code. That approach allows you to write elaborate code on an as-yet unspecified type, but such code may fail to compile if the actual type used does not support some of the functionality you used.

function TCalculator<T>.Add(x, y: T): T;
begin
  Result := x + y;
end;

The above calculator can easily work on all kinds of types T: Int, Int64, Double and even string, but it would fail to compile if you used TObject, because the compiler doesn't know how to add two objects.

In Delphi, generics work a bit differently. You can still imagine that the compiler will copy-paste your code and replace the type placeholder T with a particular type, but in Delphi, the compiler will also actually compile your generic code as such and it will not allow you to do things on the generic placeholder T it does not know how to do. That significantly limits the generic code you can write.

To extend possible code and the usability of generics, Delphi generics have a feature called constraints. For a generic placeholder type, you can specify various constraints that the actual type used must satisfy. Since the compiler knows that the specific type will have to conform to a certain specification, it can compile code it wouldn't be able to compile otherwise.

To compile the previous example in Delphi, that would mean the compiler would have to know whether T supports the addition operator. Unfortunately, Delphi constraints don't support operators, so you cannot make such a generic calculator in Delphi. Constraints you can use in Delphi are: interface types; class types; and the reserved words constructor, class, and record.

For any kind of code where you want the same code to work with different types, you can use generics, provided that all of the code can work with the placeholder type T, or that you can declare appropriate constraints. Generics can significantly reduce the amount of code written, which also simplifies maintenance. If you need to add a new feature or fix a bug, you only need to make modifications in one place, versus the multiple modifications you would need for non-generic code.

If you are not familiar with Delphi generics or how to use constraints, you can read more in the official documentation: Generics

To get more detailed explanation about their inner workings, and how they compare to C++ templates and C# generics you can read the Comparing C#, C++, and Delphi (Win32) Generics blog post.

Compiler speed

When we talk about speed, there are two things we can talk about: compiler speed and our code speed at runtime. Those are two completely separate concerns. Compiler speed, or how much time the compiler needs to compile some code, is not directly related with how fast the actual, generated code will run.

When it comes to the compiler, generics do slow down things a bit (or a lot). How much, also depends on other things, not just generics themselves.

Without going into why the compiler needs more time to compile generics, compile time itself is not reason enough to remove generics from the code. You didn't decide to use generics for no reason, so removing it for compile speed to save your developer's time in one place will cost those developers time writing and maintaining more non-generic code in another.

Some issues around compiler speed are caused by inefficiencies in the compiler, and those are fixable problems. Of course, that does not mean that such issues can and will be fixed in your lifetime, but one can always hope.

Code bloat in DCU: https://quality.embarcadero.com/browse/RSP-18080

Runtime speed

Runtime speed is the one we are most interested in when it comes to optimization and performance. And this is the speed we want to know about when we ask "Are generics slow?"

The answer is NO and YES.

If you take a look at the principle of generics and how they work, the performance of the instantiated generic code should be the same as the performance of the same non-generic code you would write for that particular type. At least that is what the copy-paste rule would imply.

The only speed difference should be in the code you have to write to achieve some functionality because you are limited by the generic placeholder type T and what can you do with it. Often that involves using RTTI and examining the type more closely. Sometimes you will have more code in generics to avoid generic code bloat. Although you would have the same amount of bloat if you duplicated code for different types, with generics you can reduce some of the bloat, and in some situations that would take precedence over performance. All that additional code will inevitably run slower, or in the case of enhanced RTTI, much slower than code you could write for a specific, known type.

But what happens if generic code is exactly the same code you would write with a specific type? What happens if generic code is literally the copy-paste and replace type kind of code?

We expect that the compiler generates the same code in such situations, and the same code would be equally fast. But in reality, the compiler is not as optimized as it could be, and it doesn't always generate the same (better) code as it does for a non-generic implementation. And this is where the answer to the question "Are generics slow?" is sadly "Sometimes, yes".

Just like inefficiencies at compile time could be solved by a better compiler, inefficiencies in generated code could also be solved by a better compiler. Sometimes, the compiler takes a step back and generates worse code than the previous version. But just like compiler speed can be improved, so can generated generic code.

Compiler does not apply all possible optimizations in generic code: https://quality.embarcadero.com/browse/RSP-20897

[REGRESSION] RVO broken in generics: https://quality.embarcadero.com/browse/RSP-34930

Conclusion

While there are certain situations and code where using generics can result in slower—even significantly slower—code, there is no reason to avoid generics just because they sometimes generate less performant code. On the contrary, the generated code will quite often be exactly the same or only have negligible differences.

Avoiding generics because they can be slow is probably the worst case of premature optimization one can think of. Not only because you will not have any bottlenecks in plenty of code where you can use generics, so optimizing such code would be a waste of time anyway, but also because, without looking at very specific code, you cannot even know that the non-generic code will actually run faster.

If you have some particular, performance-critical code that uses generics, then inspecting whether that particular code can run faster is something to consider, but it is also something that needs to be proven and measured. But this is only a viable option if only a few types are involved. If there are more than a few generic instantiations of that code, removing generics will commonly cause way more trouble than some performance loss.

Comparing generated assembly code is the best way to determine whether there are potential speed issues in some code. If there is too much code involved for manual inspection, measuring speed is the next best option. I suggest using the Delphi port of Google Benchmark, which can be found at https://github.com/spring4d/benchmark

Search This Blog

Delphi Programming Tips & Tricks