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

Further reading

If you want to read more about generics and other potential problems that are not related to speed, as well as some good sides of generics and what they can do for you, you can head to Stefan Glienke's blog for some enlightenment:

https://delphisorcery.blogspot.com/2014/03/why-delphi-generics-are-annoying.html

https://delphisorcery.blogspot.com/2014/10/the-real-power-of-generics.html

https://delphisorcery.blogspot.com/2021/06/spring4d-20-sneak-peek-evolution-of.html

Comments

  1. Thanks, a good article and makes things a bit clearer for those of us who aren't knee deep in Generics, but don't want to be put off from using them in everyday code.

    ReplyDelete
    Replies
    1. IMHO authors of generic code should take a little care because it easily gets out of hand if you approach it very naively - i've seen large libraries where at the very basic foundations there are many generics and it lead to ginourmous compiletimes (mostly because of the situation I descrived in RSP-18080 and my articles) including completely failing to compile on some platforms where the compiler consumed more memory than the classic windows compilers do.
      This unfortunately includes the RTL which on one hand got some improvements with the collections refactoring that happened in XE7 (including a lot of regressions which got fixed over the duration of several releases) but still exists. Just recently in Delphi 11 there was fixed an issue which caused the inclusion of some generic classes inside the binary that were never used (see https://quality.embarcadero.com/browse/RSP-30870).

      Delete
  2. I feel like the Delphi community might not have absorbed the same awareness of the history of thought around generics as eg the C++ community, back to at least Alexander Stepanov.

    This video might be of interest - looking at generics and constraints across several languages:
    https://www.youtube.com/watch?v=Qh7QdG5RK9E

    ReplyDelete

Post a Comment

Popular posts from this blog

Just released eBook: Delphi Event-based and Asynchronous Programming

Virtual methods in Delphi

Magic behind FreeAndNil