4 ms·
Let's look at the signature of qsort() from libc: void qsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *));
by asveikau 13y ago
Let's look at the signature of qsort() from libc:
void qsort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *));
qsort is a function inside of libc.so. It's already been compiled. It doesn't know about the "compar" pointer you're going to pass it. That function might not even exist yet.
qsort doesn't know if you're sorting integers, sorting strings, sorting struct foo which is still being ironed out. It knows how to sort arrays. You give it the size of each element, the number of elements, and a function pointer that it will call to compare elements. It will call you back and you can stick your data-structure-specific knowledge into that function.
(This turns out to be a lousy way to sort arrays, by the way. If you used a C++ template instead, the comparison function could be inlined directly in the sort algorithm, which gives you better object code. But you lose the possibility that the caller and callee exist in different modules, for example.)
- Radle 13y agothanks, that helped me out <3
- exDM69 13y ago> qsort is a function inside of libc.so. It's already been compiled. Unfortunately, this is also why it is so damn slow. Try comparing C++ std::sort with C qsort, the performance gap is HUGE. The reason is that the "function pointer" std::sort gets inlined but qsort will actually invoke a function call via function pointer. If you'd move qsort to a header file as an inline function, the performance problem would go away.
- asveikau 13y agoThis is one thing I don't understand about HN sometimes. I always get replies that seen to angrily "disagree". But I've already made your point in my parenthetical remark. There are of course other times where the function pointer overhead doesn't matter as much and the modularity of not having things as templates is desirable. Sorting is just a bad example.