3 ms·

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.
      - mattnewport 8y ago
        > It's the same story for types in general. They lead to wrong and bloated design and boilerplate code when you overdo it. I wouldn't recommend overdoing anything, by definition. My experience however is that when done correctly type safety usually makes code both more elegant and more efficient. Like anything in programming it is often done poorly however and people sometimes seem to confuse types with OOP concepts in C++. A lot of people seem to worry about certain programming practices because they fear other people abusing them. Those discussions are of little interest to me. I'm interested in how I can best write good code, not worrying about what other people are doing.
      - Jtsummers 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.
    - mattnewport 8y ago
      > It's the same story for types in general. They lead to wrong and bloated design and boilerplate code when you overdo it. I wouldn't recommend overdoing anything, by definition. My experience however is that when done correctly type safety usually makes code both more elegant and more efficient. Like anything in programming it is often done poorly however and people sometimes seem to confuse types with OOP concepts in C++. A lot of people seem to worry about certain programming practices because they fear other people abusing them. Those discussions are of little interest to me. I'm interested in how I can best write good code, not worrying about what other people are doing.
    - Jtsummers 8y ago