7 ms·

So if you get rid of bounds check, reimplement your own feature-limited vector and hash table and change the algorithm moving from a general purpose exact sort

So if you get rid of bounds check, reimplement your own feature-limited vector and hash table and change the algorithm moving from a general purpose exact sort to an inexact, domain-specific one, you can improve your run time from 572ms to 320ms. What does this have to do with C++?

CoolGuySteve 8y ago
Ya after changing the hash table and sort algorithms, the rest of the improvements are fairly minor (other than MSVC’s debug performance). This is more like “is C++’s STL fast for me”.
- lultimouomo 8y ago
  For me the proper title of the article would be "std::unordered_set is slow and MSVC debug runtime is even slower", but I guess that wouldn't generate as many views as pretty much everyone knows it.
throwawaymath 8y ago
I interpret the title to mean, "Is standard usage of C++ language features and the STL competitive with C?". The author is basically showing how you improve performance by selectively tearing out more and more features C++ hands you out of the box. This is characteristic of writing C++ in a more C-like style. In that sense I think the author is correct. However I'd also say this is something already well known by most C and, particularly, C++ developers. Yes, you can get better performance by reimplementing much of what C++ gives you, and that is typical of writing C code instead of C++. But there's a fair bit of productivity trade off in doing so.
- vectorEQ 8y ago
  if you don't use any of the slow language features it's fast
  - Retra 8y ago
    If you use special-purpose tools rather than robust ones, you can get better performance. But nobody wants to ship a language without robust general-purpose tools.
  - krapp 8y ago
    Even the slow language features are fast enough for most use cases, though. I think the actual comparison here isn't between 'slow' and 'fast' but 'probably fast enough' and 'as fast as possible.'
- deng 8y ago
  I'm pretty sure I could make a faster 'printf' but which only supports '%d'. Does that mean 'C is slow'?
  - simias 8y ago
    I'd say that printf, with its own DSL, is actually pretty slow. It's meant for debugging or "slow" I/O, if you need to write a lot of data it should be avoided. A few years ago for debugging purposes I wanted to hexdump a large amount of data. Turns out that the standard hexdump tool was pretty slow at it, writing a simple C utility that would format the dump "by hand" instead of using printf was about an order of magnitude faster. You have fully static code instead of the interpreted format string, you can unroll all the formatting, you don't have to rewrite the characters that don't change in every line (spaces, delimiters etc...). It's lightning fast but of course not very flexible.
    - deng 8y ago
      > I'd say that printf, with its own DSL, is actually pretty slow. Yes, of course it is. That's why I took it as an example. Since I work on RealTime systems I usually have to use plain 'write' instead. But that is because 'printf' is an incredibly complex function, not because 'C is slow'.
      - simias 8y ago
        At this point I feel like it's almost a philosophical argument but: - printf is a standard function in C's stdlib. - Because of the nature of the function (using a special purpose format strings and varargs instead of some kind of generic system) the function can't really be aggressively optimized and inlined without compiler magic. This limitation is caused by C's own limitations when it comes to generic programming and type introspection, printf needs to be told explicitly through a "side-channel" (the format string) what types to expect because C lacks the infrastructure to do that by itself. It also means that you can't extend the function for custom types and that you can't type-check the parameters without compiler magic. - Even though some compilers do implement special magic around printf to perform more aggressive optimizations (like replacing it with "puts" if there's no formatting going on for instance) it's still generally trivial to beat its performance in non-trivial case with handwritten code. Given all of the above I would say that makes this particular corner of C rather slow indeed. Or at least slower than it might be compared to an hypothetical language that made it easier to optimize string formatting.
- vidarh 8y ago
  This is one of the defining principles of C++, after all: You pay only for what you use. Conversely, if you do opt-in to using more advanced features, it may come at a cost, but it's all optional. It's been one of the things that have most strongly shaped the evolution of the language and the library, for both good and bad, so absolutely, it is very much well known.
  - dfox 8y ago
    For me this principle is also what often causes performance issues, because for many advanced features this leads to convoluted language semantics and sub-optimal implementations.
  - jura_z 8y ago
    'You pay only for what you use' Sorry, have you read the article? He is not using any C++20, C++17, C++14... features, just adding a compiler key. And he's paying with compilation time. https://twitter.com/zeuxcg/status/1085781851568914432 https://twitter.com/zeuxcg/status/1085781851568914432 You might say that compilation time is nothing.. But it is C++, compilation time has a huge impact on big codebases.
    - vidarh 8y ago
      He started out with among others, std::vector. That has tradeoffs, in that the standard specifies requirements that he may or may not need. My point stands. The performance trade-offs you're paying for with various C++ features are extremely well understood, and better documented for C++ than most languages. That doesn't mean there aren't surprises here and there, and obviously there are compiler difference, but the point was that the language is designed so that these tradeoffs are known and documented and for the most part comes as a surprise to people mostly when they don't know the language very well. It is not a surprise that you can improve on things like std::vector by rolling your own that does exactly what you want; for starters if you know your requirements chances are you can speed up initialization, because you don't need to abide by standard semantics. For starters, if you know you're going to assign a fixed number of elements, you don't need to track size and capacity, and you can often avoid the need for bounds checking. As for compilation time, that too is very much a matter of paying for what you're using. You can choose to disable debug info, you can choose to not include headers that are bound to result in lots of time spent on parsing templates. That he's not using many advanced features is irrelevant; his starting point very much had made trade-offs in using functionality that comes with known costs.
- carlmr 8y ago
  That's why you measure first, and only if necessary go to these extreme measures if you find that this is the place that really costs you performance. Or if performance is basically your only goal (HFT) then you just need to spend this time on a lot of parts of your code. But then in 99% of code it's a waste of time.
- proginthebox 8y ago
  With proper use of constexpr, templates and types, you can make C++ at least as fast as C code without giving up on readability.
  - stochastic_monk 8y ago
    At least as. Often faster because of easier inlining.
- geezerjay 8y ago
  > The author is basically showing how you improve performance by selectively tearing out more and more features C++ hands you out of the box. In that case the author is showing what has been widely known by C++ developers for decades. In fact, the "don't use the STL because it's slow" is a mantra which, along with the old "replace STL's default allocators with your customized ones", is repeated ad nauseum in gamedev circles.
- Sharlin 8y ago
  The C++ standard library is pretty competitive with C given that C has no standard data structure and algorithms library! It's not even an apples and oranges comparison.
jcranmer 8y ago
Well, I can imagine there are some languages where the interpreted nature of the language keeps you from being able to build higher-performance highly-specialized data structures and algorithms that outperform the native implementations (say, JS). But even then, it still doesn't justify the title.
brohee 8y ago
It sure shows that the sentence "you only pay for the features you use" is wrong at least.
- kiriakasis 8y ago
  when he stopped using them he also stopped paying for them
- SeanBoocock 8y ago
  What? It demonstrates the opposite. He stopped using general purpose containers and algorithms, and replaced them with implementations more tailored to his use case. He didn't keep paying for std::sort or std::unordered_set once he stopped using them. By contrast in most managed languages with a GC, I can't opt out of the GC even if I want to take responsibility for memory management and object lifetime.
  - brohee 8y ago
    > The issue is that math.h includes cmath in gcc/clang which pulls in a lot of C++ machinery, and in C++17 in libstdc++ adds a slew of new special functions, that are rarely useful but will make compilation slower anyway. > This is definitely an area where libstdc++ and libc++ could improve in the future - I don’t think it’s reasonable to force users of C headers to pay for the C++ baggage.
    - eMSF 8y ago
      You're being obtuse on purpose. The sentence you claim is wrong has only ever been used to describe performance at run time.
  - rurban 8y ago
    Most managed language runtimes I know allow you to opt out of a GC, or to tune it to your workload.
    - jungler 8y ago
lucozade 8y ago
In fairness to the article, it is putting some flesh on the bones of an area that I have seen cause surprise. It's a variant of the observation that, although in C++ you aren't paying a direct abstraction cost, you are often paying a generalisation cost. This cost is obscured by the abstraction and may not be warranted in your application. In other words, an indirect abstraction cost.
MichaelMoser123 8y ago
C++ comes with the OOP mindeset: OOP is about polymorphism, inheritance and encapsulation. Now what if you are abstracting over the wrong library for a given task? Will you be able to question your basic assumptions, or is that an assumption that is not allowed to be questioned? (due to the encapsulation principle)
- thestoicattack 8y ago
  I don't think C++ comes with the OOP mindset. At least, not recently. Most people will tell you it's "multi-paradigm." And I would say C++ certainly gives you enough flexibility to dig underneath the abstractions, as TFA shows.
  - MichaelMoser123 8y ago
    I am not so sure about the multi-paradigm thing: In c++ everything is a class. Also of you try hard enough then you may implement any paradigm in any language.
    - thestoicattack 8y ago
      That's Java, isn't it? I write lots of C++ without classes.
      - mindcrime 8y ago
        Even though Java is still very "class-centric", in the strictest sense Java doesn't make "everything a class". There have always been primitives for things like int, long, boolean, float, double, etc. And now that we have MethodHandles and what-not, you can (sort of) start to think of functions as first class entities in Java. And there are Lambdas as well which effectively let you build a function without it needing a class to contain it.
        thestoicattack 8y ago
        I was being a little flippant and unfair to Java because I was trying to find where the claim "everything is a class" had appeared from.
deleted 8y ago
[deleted]
mynegation 8y ago
Came here to say almost exactly this. C++ is fast. All the things mentioned in the article are very specific replacements of C++ standard library implementations. C++ is a zero cost abstraction language, all these things could have been replaced with idiomatic C++. The fact that they were implemented in C is more of an authors language preference. Reimplementing some things might be easier in C because C is a simpler (and often more familiar) language. Idiomatic C++ may require knowledge of pretty arcane feature of already complicated language, like placement new and judicious use of references and move operators.
- stephencanon 8y ago
  All the things that were replaced were abstractions, which had costs. I think that there's a valid point that a lot of C++ programmers use these abstractions liberally, while sweeping the very real costs under the rug. There are also benefits to using them, of course.
- lasagnaphil 8y ago
  I would say C++ is more like a zero runtime-cost abstraction language (in release builds). You could achieve good release build runtime-speeds in modern idiomatic C++, but you have to trade off your compile times and Debug-build runtime-speeds for that.
  - vardump 8y ago
    > I would say C++ is more like a zero runtime-cost abstraction language (in release builds). Well, other than the "zero-cost" features that increase code size. For example careless use of heavy template classes can generate a lot of code. In other words, in C++ it's very easy to generate a lot of code from seemingly innocent constructs. Instruction cache misses, page faults (and to lesser amount TLB misses) are not zero cost.
    - ben509 8y ago
      To your point, cost (or strength) should always consider size as well as time. It would be nice to have a tool that could compute the size impact of a given line.
jblow 8y ago
> What does this have to do with C++? Given that most new C++ features in the "modern day" are implemented as std::whatever, in the "everything is a library" way, it's extremely relevant.
- Ace17 8y ago
  Just because I'm using a C++17 compiler doesn't mean I'm happy with the standard library. I still have to google every time I need to sleep the current thread ; and don't get me started on iostream! However, I'm happy to be able to return a buffer without copying it (move semantics), to precompute frequency tables at compile time (constexpr), to be able to pass around functions without having to create a dedicated class (lambdas), not to have to worry about having an extra conversion (auto) ... And soon, I will be happy to write serialization code without relying on dirty tricks (introspection).

CoolGuySteve 8y ago

Ya after changing the hash table and sort algorithms, the rest of the improvements are fairly minor (other than MSVC’s debug performance). This is more like “is C++’s STL fast for me”.

lultimouomo 8y ago
For me the proper title of the article would be "std::unordered_set is slow and MSVC debug runtime is even slower", but I guess that wouldn't generate as many views as pretty much everyone knows it.

throwawaymath 8y ago

I interpret the title to mean, "Is standard usage of C++ language features and the STL competitive with C?". The author is basically showing how you improve performance by selectively tearing out more and more features C++ hands you out of the box. This is characteristic of writing C++ in a more C-like style. In that sense I think the author is correct. However I'd also say this is something already well known by most C and, particularly, C++ developers. Yes, you can get better performance by reimplementing much of what C++ gives you, and that is typical of writing C code instead of C++. But there's a fair bit of productivity trade off in doing so.

vectorEQ 8y ago
if you don't use any of the slow language features it's fast
- Retra 8y ago
  If you use special-purpose tools rather than robust ones, you can get better performance. But nobody wants to ship a language without robust general-purpose tools.
- krapp 8y ago
  Even the slow language features are fast enough for most use cases, though. I think the actual comparison here isn't between 'slow' and 'fast' but 'probably fast enough' and 'as fast as possible.'
deng 8y ago
I'm pretty sure I could make a faster 'printf' but which only supports '%d'. Does that mean 'C is slow'?
- simias 8y ago
  I'd say that printf, with its own DSL, is actually pretty slow. It's meant for debugging or "slow" I/O, if you need to write a lot of data it should be avoided. A few years ago for debugging purposes I wanted to hexdump a large amount of data. Turns out that the standard hexdump tool was pretty slow at it, writing a simple C utility that would format the dump "by hand" instead of using printf was about an order of magnitude faster. You have fully static code instead of the interpreted format string, you can unroll all the formatting, you don't have to rewrite the characters that don't change in every line (spaces, delimiters etc...). It's lightning fast but of course not very flexible.
  - deng 8y ago
    > I'd say that printf, with its own DSL, is actually pretty slow. Yes, of course it is. That's why I took it as an example. Since I work on RealTime systems I usually have to use plain 'write' instead. But that is because 'printf' is an incredibly complex function, not because 'C is slow'.
    - simias 8y ago
      At this point I feel like it's almost a philosophical argument but: - printf is a standard function in C's stdlib. - Because of the nature of the function (using a special purpose format strings and varargs instead of some kind of generic system) the function can't really be aggressively optimized and inlined without compiler magic. This limitation is caused by C's own limitations when it comes to generic programming and type introspection, printf needs to be told explicitly through a "side-channel" (the format string) what types to expect because C lacks the infrastructure to do that by itself. It also means that you can't extend the function for custom types and that you can't type-check the parameters without compiler magic. - Even though some compilers do implement special magic around printf to perform more aggressive optimizations (like replacing it with "puts" if there's no formatting going on for instance) it's still generally trivial to beat its performance in non-trivial case with handwritten code. Given all of the above I would say that makes this particular corner of C rather slow indeed. Or at least slower than it might be compared to an hypothetical language that made it easier to optimize string formatting.
vidarh 8y ago
This is one of the defining principles of C++, after all: You pay only for what you use. Conversely, if you do opt-in to using more advanced features, it may come at a cost, but it's all optional. It's been one of the things that have most strongly shaped the evolution of the language and the library, for both good and bad, so absolutely, it is very much well known.
- dfox 8y ago
  For me this principle is also what often causes performance issues, because for many advanced features this leads to convoluted language semantics and sub-optimal implementations.
- jura_z 8y ago
  'You pay only for what you use' Sorry, have you read the article? He is not using any C++20, C++17, C++14... features, just adding a compiler key. And he's paying with compilation time. https://twitter.com/zeuxcg/status/1085781851568914432 https://twitter.com/zeuxcg/status/1085781851568914432 You might say that compilation time is nothing.. But it is C++, compilation time has a huge impact on big codebases.
  - vidarh 8y ago
    He started out with among others, std::vector. That has tradeoffs, in that the standard specifies requirements that he may or may not need. My point stands. The performance trade-offs you're paying for with various C++ features are extremely well understood, and better documented for C++ than most languages. That doesn't mean there aren't surprises here and there, and obviously there are compiler difference, but the point was that the language is designed so that these tradeoffs are known and documented and for the most part comes as a surprise to people mostly when they don't know the language very well. It is not a surprise that you can improve on things like std::vector by rolling your own that does exactly what you want; for starters if you know your requirements chances are you can speed up initialization, because you don't need to abide by standard semantics. For starters, if you know you're going to assign a fixed number of elements, you don't need to track size and capacity, and you can often avoid the need for bounds checking. As for compilation time, that too is very much a matter of paying for what you're using. You can choose to disable debug info, you can choose to not include headers that are bound to result in lots of time spent on parsing templates. That he's not using many advanced features is irrelevant; his starting point very much had made trade-offs in using functionality that comes with known costs.
carlmr 8y ago
That's why you measure first, and only if necessary go to these extreme measures if you find that this is the place that really costs you performance. Or if performance is basically your only goal (HFT) then you just need to spend this time on a lot of parts of your code. But then in 99% of code it's a waste of time.
proginthebox 8y ago
With proper use of constexpr, templates and types, you can make C++ at least as fast as C code without giving up on readability.
- stochastic_monk 8y ago
  At least as. Often faster because of easier inlining.
geezerjay 8y ago
> The author is basically showing how you improve performance by selectively tearing out more and more features C++ hands you out of the box. In that case the author is showing what has been widely known by C++ developers for decades. In fact, the "don't use the STL because it's slow" is a mantra which, along with the old "replace STL's default allocators with your customized ones", is repeated ad nauseum in gamedev circles.
Sharlin 8y ago
The C++ standard library is pretty competitive with C given that C has no standard data structure and algorithms library! It's not even an apples and oranges comparison.

jcranmer 8y ago

Well, I can imagine there are some languages where the interpreted nature of the language keeps you from being able to build higher-performance highly-specialized data structures and algorithms that outperform the native implementations (say, JS). But even then, it still doesn't justify the title.

brohee 8y ago

It sure shows that the sentence "you only pay for the features you use" is wrong at least.

kiriakasis 8y ago
when he stopped using them he also stopped paying for them
SeanBoocock 8y ago
What? It demonstrates the opposite. He stopped using general purpose containers and algorithms, and replaced them with implementations more tailored to his use case. He didn't keep paying for std::sort or std::unordered_set once he stopped using them. By contrast in most managed languages with a GC, I can't opt out of the GC even if I want to take responsibility for memory management and object lifetime.
- brohee 8y ago
  > The issue is that math.h includes cmath in gcc/clang which pulls in a lot of C++ machinery, and in C++17 in libstdc++ adds a slew of new special functions, that are rarely useful but will make compilation slower anyway. > This is definitely an area where libstdc++ and libc++ could improve in the future - I don’t think it’s reasonable to force users of C headers to pay for the C++ baggage.
  - eMSF 8y ago
    You're being obtuse on purpose. The sentence you claim is wrong has only ever been used to describe performance at run time.
- rurban 8y ago
  Most managed language runtimes I know allow you to opt out of a GC, or to tune it to your workload.
  - jungler 8y ago

lucozade 8y ago

In fairness to the article, it is putting some flesh on the bones of an area that I have seen cause surprise. It's a variant of the observation that, although in C++ you aren't paying a direct abstraction cost, you are often paying a generalisation cost. This cost is obscured by the abstraction and may not be warranted in your application. In other words, an indirect abstraction cost.

MichaelMoser123 8y ago

C++ comes with the OOP mindeset: OOP is about polymorphism, inheritance and encapsulation. Now what if you are abstracting over the wrong library for a given task? Will you be able to question your basic assumptions, or is that an assumption that is not allowed to be questioned? (due to the encapsulation principle)

thestoicattack 8y ago
I don't think C++ comes with the OOP mindset. At least, not recently. Most people will tell you it's "multi-paradigm." And I would say C++ certainly gives you enough flexibility to dig underneath the abstractions, as TFA shows.
- MichaelMoser123 8y ago
  I am not so sure about the multi-paradigm thing: In c++ everything is a class. Also of you try hard enough then you may implement any paradigm in any language.
  - thestoicattack 8y ago
    That's Java, isn't it? I write lots of C++ without classes.
    - mindcrime 8y ago
      Even though Java is still very "class-centric", in the strictest sense Java doesn't make "everything a class". There have always been primitives for things like int, long, boolean, float, double, etc. And now that we have MethodHandles and what-not, you can (sort of) start to think of functions as first class entities in Java. And there are Lambdas as well which effectively let you build a function without it needing a class to contain it.
      - thestoicattack 8y ago
        I was being a little flippant and unfair to Java because I was trying to find where the claim "everything is a class" had appeared from.

deleted 8y ago

[deleted]

mynegation 8y ago

Came here to say almost exactly this. C++ is fast. All the things mentioned in the article are very specific replacements of C++ standard library implementations. C++ is a zero cost abstraction language, all these things could have been replaced with idiomatic C++. The fact that they were implemented in C is more of an authors language preference. Reimplementing some things might be easier in C because C is a simpler (and often more familiar) language. Idiomatic C++ may require knowledge of pretty arcane feature of already complicated language, like placement new and judicious use of references and move operators.

stephencanon 8y ago
All the things that were replaced were abstractions, which had costs. I think that there's a valid point that a lot of C++ programmers use these abstractions liberally, while sweeping the very real costs under the rug. There are also benefits to using them, of course.
lasagnaphil 8y ago
I would say C++ is more like a zero runtime-cost abstraction language (in release builds). You could achieve good release build runtime-speeds in modern idiomatic C++, but you have to trade off your compile times and Debug-build runtime-speeds for that.
- vardump 8y ago
  > I would say C++ is more like a zero runtime-cost abstraction language (in release builds). Well, other than the "zero-cost" features that increase code size. For example careless use of heavy template classes can generate a lot of code. In other words, in C++ it's very easy to generate a lot of code from seemingly innocent constructs. Instruction cache misses, page faults (and to lesser amount TLB misses) are not zero cost.
  - ben509 8y ago
    To your point, cost (or strength) should always consider size as well as time. It would be nice to have a tool that could compute the size impact of a given line.

jblow 8y ago

> What does this have to do with C++? Given that most new C++ features in the "modern day" are implemented as std::whatever, in the "everything is a library" way, it's extremely relevant.

Ace17 8y ago
Just because I'm using a C++17 compiler doesn't mean I'm happy with the standard library. I still have to google every time I need to sleep the current thread ; and don't get me started on iostream! However, I'm happy to be able to return a buffer without copying it (move semantics), to precompute frequency tables at compile time (constexpr), to be able to pass around functions without having to create a dedicated class (lambdas), not to have to worry about having an extra conversion (auto) ... And soon, I will be happy to write serialization code without relying on dirty tricks (introspection).