Comment by ryao
4 months ago
I have used the preprocessor to avoid this sort of slowdown in the past in a binary search function:
https://news.ycombinator.com/item?id=43827857
Honestly, I think these weaknesses are more severe than qsort being unable to inline the comparator.
A comparator can be inlined just fine in C. See here where the full example is folded to a constant: https://godbolt.org/z/bnsvGjrje
Does not work if the compiler can not look into the function, but the same is true in C++.
That does not show the comparator being inlined since everything was folded into a constant, although I suppose it was. Neat.
Edit: It sort of works for the bsearch() standard library function:
https://godbolt.org/z/3vEYrscof
However, it optimized the binary search into a linear search. I wanted to see it implement a binary search, so I tried with a bigger array:
https://godbolt.org/z/rjbev3xGM
Now it calls bsearch instead of inlining the comparator.
With optimization, it will really inline it with an unknown size array: https://godbolt.org/z/sK3nK34Y4
That's not the most general case, but it's better than I expected.
1 reply →