3 ms·
I agree with a bunch of points here, but this author reveals a spectacular gap when they mention qsort and bsearch without mentioning the high cost of the repea
by asveikau 4y ago
I agree with a bunch of points here, but this author reveals a spectacular gap when they mention qsort and bsearch without mentioning the high cost of the repeat function pointer calls on a modern CPU.
A good qsort or bsearch mechanism would allow the comparisons to be inlined. Performance critical code can't use the libc versions due to this.
- jstimpfle 4y agoHave you measured? These functions can still come in handy at times (and inlining increase the binary size), and if your bottleneck is in a sorting routine, you likely have other problems. Quicksort would probably be the wrong choice anyway.
- asveikau 4y agoI 100% agree with the idea that the bottleneck might be somewhere else and it probably doesn't matter. But yes, I have seen numbers comparing qsort and std::sort. There is no competition in this. The latter is pretty much always vastly better in wall clock time due to inlining. Yes you trade code size for that, but today memory and storage is cheap.
- camel-cdr 4y agoThis isn't an inherit problem with libc, but rather a problem with the libc implementations. IMO libc's should offer an extern inline definition of those functions, so the compilers are able to inline or function specialize them when needed.
- asveikau 4y agoI think that's a good idea. I remember the days when an optimizer didn't really optimize a function pointer call. Now they can probably pull it off if it's the same compilation unit. And if you have link time optimizations, I've seen it do inlines across object files, but obviously that won't work for dynamically linked libc. But a static inline qsort in a libc header is probably a good call.