4 ms·

I don’t think the author really addresses the examples presented. The example of the FAST decision tree is based on a code generator, an abstraction which is p

I don’t think the author really addresses the examples presented. The example of the FAST decision tree is based on a code generator, an abstraction which is presumably more elegant than the generated code which is littered with goto statements. And what about std::sort? Say what you want about C++ in general, but it is definitely superior to a rudimentary qsort in C in terms of elegance and at least equivalent in terms of runtime efficiency. There are plenty of examples in either direction. It would seem that this is yet another case of “it depends.”

CoolGuySteve 8y ago
std::sort and other templates make you pay in terms of header complexity (no circular includes for example) and compilation time. For the most part it’s a good trade off, particularly std::sort and some of the other <algorithms>. But I’ve yet to work on a long lived low latency/high performance C++ project where some wizard coworker has not tanked the code base for purely theoretical gains that turn out to not meaningfully change the assembly or change it by an instruction or two. Godbolt is a revelation when these situations arise, but good luck even then convincing someone who just spent 4 days writing a dispatch or whatever that it was all a waste. I guess what I’m saying is that when it comes to template-oriented performance programming, std::sort is the exception, not the rule. Or maybe the good templates are small and modular so their footprint is 1/10th that of a bad template such that we just don’t notice them as much.
diegoperini 8y ago
Noob question: What does std::sort do (aside from sorting oc) ? Which feature of it were you highlighting?
- mattnewport 8y ago
  Compared to C style qsort what std::sort gives you are type safety, convenience (types that already define a suitable operator< will use it automatically without you having to explicitly create a comparison function), correctness/convenience (you don't have to manually specify the number of elements to sort, it's deduced from the range) and efficiency (the comparison can be inlined by the compiler much more easily than in a C style qsort which typically makes a meaningful performance difference for sorting).
  - deleted 8y ago
    [deleted]
  - jstimpfle 8y ago
    TBH the efficiency thing is irrelevant. I once compared std::sort and qsort on large integer arrays (which is where you can expect the greatest speedup) and the speedup was less than 2x on my machine. Furthermore the cases where sorting could ever become a noticeable bottleneck are pretty rare. Meanwhile each std::sort instantiation costs a few hundred bytes of machine code and increases the project's compilation times. When performance ever matters, you tune your sort algorithm and implementation to the data - you use a bucket sort for example. Much larger speedups than 2x to be had this way. std::sort cannot do that. I like the type safety of std::sort vs qsort, though, even though I don't find pursuing "type safety" a good idea in general.
    - mattnewport 8y ago
      I don't consider a 2x speedup "irrelevant". It's also not the case that large integer arrays are where I would expect the greatest speedup. The greatest speedup would be on arrays that fit in L1 cache where function call overhead is going to be the most significant factor rather than cache misses. Compile times and code bloat with templates are genuine issues but they are being improved both with improved compilers and linkers and with C++ standard changes (modules should be a big help for compile times). Type safety is in my opinion a good example of elegance and efficiency being generally aligned. Typically improving type safety makes code more elegant, catches bugs and give opportunities for better efficiency in my experience.
      - jstimpfle 8y ago
        Again, it was an artificial benchmark. I sorted millions of integers. 2x is not measured in a real-life program. It's the absolute upper limit what you can ever expect. Most programs don't spend a noticeable amount time in sorting at all. Program performance usually is dominated by other things, like I/O. Now what is 50% of "not a noticeable amount of time"? Right, it's irrelevant. But 2x is a hard number, so people tend to think it's important and forget about all the disadvantages which are hard to measure but have far more ramifications. And for the rare cases where a sort really matters, you should use an implementation that is tuned to the data. That will bring you larger speed-ups. I could have said "10x" to sound impressive, and it wouldn't be wrong in most cases, but it's simply not possible to make a blanket statement. It depends. It could be more than 10x. Even better, you can often construct the data so it falls out sorted. Speed-up: INFx. Machine code and compile time: Zero. It's the same story for types in general. They lead to wrong and bloated design and boilerplate code when you overdo it. Which prevents the important optimizations that could simplify program structure enormously, and kill many more bugs this way. > The greatest speedup would be on arrays that fit in L1 cache where function call overhead is going to be the most significant factor rather than cache misses. The smaller you make the data, the less time it takes to sort it with whatever implementation, the less important the implementation is. Furthermore, shouldn't we expect most sorting applications to be pretty cache-friendly? E.g. Quicksort scans the array sequentially, log n times.

CoolGuySteve 8y ago

std::sort and other templates make you pay in terms of header complexity (no circular includes for example) and compilation time. For the most part it’s a good trade off, particularly std::sort and some of the other <algorithms>. But I’ve yet to work on a long lived low latency/high performance C++ project where some wizard coworker has not tanked the code base for purely theoretical gains that turn out to not meaningfully change the assembly or change it by an instruction or two. Godbolt is a revelation when these situations arise, but good luck even then convincing someone who just spent 4 days writing a dispatch or whatever that it was all a waste. I guess what I’m saying is that when it comes to template-oriented performance programming, std::sort is the exception, not the rule. Or maybe the good templates are small and modular so their footprint is 1/10th that of a bad template such that we just don’t notice them as much.

diegoperini 8y ago

Noob question: What does std::sort do (aside from sorting oc) ? Which feature of it were you highlighting?

mattnewport 8y ago
Compared to C style qsort what std::sort gives you are type safety, convenience (types that already define a suitable operator< will use it automatically without you having to explicitly create a comparison function), correctness/convenience (you don't have to manually specify the number of elements to sort, it's deduced from the range) and efficiency (the comparison can be inlined by the compiler much more easily than in a C style qsort which typically makes a meaningful performance difference for sorting).
- deleted 8y ago
  [deleted]
- jstimpfle 8y ago
  TBH the efficiency thing is irrelevant. I once compared std::sort and qsort on large integer arrays (which is where you can expect the greatest speedup) and the speedup was less than 2x on my machine. Furthermore the cases where sorting could ever become a noticeable bottleneck are pretty rare. Meanwhile each std::sort instantiation costs a few hundred bytes of machine code and increases the project's compilation times. When performance ever matters, you tune your sort algorithm and implementation to the data - you use a bucket sort for example. Much larger speedups than 2x to be had this way. std::sort cannot do that. I like the type safety of std::sort vs qsort, though, even though I don't find pursuing "type safety" a good idea in general.
  - mattnewport 8y ago
    I don't consider a 2x speedup "irrelevant". It's also not the case that large integer arrays are where I would expect the greatest speedup. The greatest speedup would be on arrays that fit in L1 cache where function call overhead is going to be the most significant factor rather than cache misses. Compile times and code bloat with templates are genuine issues but they are being improved both with improved compilers and linkers and with C++ standard changes (modules should be a big help for compile times). Type safety is in my opinion a good example of elegance and efficiency being generally aligned. Typically improving type safety makes code more elegant, catches bugs and give opportunities for better efficiency in my experience.
    - jstimpfle 8y ago
      Again, it was an artificial benchmark. I sorted millions of integers. 2x is not measured in a real-life program. It's the absolute upper limit what you can ever expect. Most programs don't spend a noticeable amount time in sorting at all. Program performance usually is dominated by other things, like I/O. Now what is 50% of "not a noticeable amount of time"? Right, it's irrelevant. But 2x is a hard number, so people tend to think it's important and forget about all the disadvantages which are hard to measure but have far more ramifications. And for the rare cases where a sort really matters, you should use an implementation that is tuned to the data. That will bring you larger speed-ups. I could have said "10x" to sound impressive, and it wouldn't be wrong in most cases, but it's simply not possible to make a blanket statement. It depends. It could be more than 10x. Even better, you can often construct the data so it falls out sorted. Speed-up: INFx. Machine code and compile time: Zero. It's the same story for types in general. They lead to wrong and bloated design and boilerplate code when you overdo it. Which prevents the important optimizations that could simplify program structure enormously, and kill many more bugs this way. > The greatest speedup would be on arrays that fit in L1 cache where function call overhead is going to be the most significant factor rather than cache misses. The smaller you make the data, the less time it takes to sort it with whatever implementation, the less important the implementation is. Furthermore, shouldn't we expect most sorting applications to be pretty cache-friendly? E.g. Quicksort scans the array sequentially, log n times.