3 ms·

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

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
  > Most programs don't spend a noticeable amount time in sorting at all. I think a more important point is that most programs that depend on sorting data will use a data structure which can sort itself rather than trying to sort lists/arrays of such large numbers (especially when exceeding a certain threshold of data records). Consider if you're getting millions of records and need them in some order (potentially different from how they arrive), it makes more sense (especially with the IO delays) to spend the extra time on inserting into a sorted structure while waiting for the next piece of data to arrive. Interleaving the two activities, rather than waiting for all IO to finish and then sorting a massive list (forcing them to be serialized). The concurrent version can benefit from the inherent parallel nature of dealing with IO-bound and CPU-bound activities.
  - jstimpfle 8y ago
    I'm not positive that most sorts are "online" with I/O that reads the data to be sorted. It's not what I wanted to imply anyway. The kind of I/O I meant is just generally time consuming I/O (large amounts of data, too many small requests, too much synchronization) that most applications are doing. For other, non-I/O intensive applications, most of them likely have bottlenecks other than sorting. In any case I wouldn't want to tie my data to an incremental sorting structure (like a search tree instead of a flat array) before I've ensured that this online aspect was critical. If it is not critical choosing a more complicated incremental structure is probably premature optimization which constrains the project structure, and thus is likely to negatively affect performance and maintainability in the end.

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
> Most programs don't spend a noticeable amount time in sorting at all. I think a more important point is that most programs that depend on sorting data will use a data structure which can sort itself rather than trying to sort lists/arrays of such large numbers (especially when exceeding a certain threshold of data records). Consider if you're getting millions of records and need them in some order (potentially different from how they arrive), it makes more sense (especially with the IO delays) to spend the extra time on inserting into a sorted structure while waiting for the next piece of data to arrive. Interleaving the two activities, rather than waiting for all IO to finish and then sorting a massive list (forcing them to be serialized). The concurrent version can benefit from the inherent parallel nature of dealing with IO-bound and CPU-bound activities.
- jstimpfle 8y ago
  I'm not positive that most sorts are "online" with I/O that reads the data to be sorted. It's not what I wanted to imply anyway. The kind of I/O I meant is just generally time consuming I/O (large amounts of data, too many small requests, too much synchronization) that most applications are doing. For other, non-I/O intensive applications, most of them likely have bottlenecks other than sorting. In any case I wouldn't want to tie my data to an incremental sorting structure (like a search tree instead of a flat array) before I've ensured that this online aspect was critical. If it is not critical choosing a more complicated incremental structure is probably premature optimization which constrains the project structure, and thus is likely to negatively affect performance and maintainability in the end.