Add a compile time warning for qsort() about issues regarding execution time.

[• hselasky]

Summary

To make developers think carefully through the use of this function
under FreeBSD, until further.

MFC after: 1 week
Sponsored by: NVIDIA Networking

[jrtc27]

No. This is a widely-used ISO C function. If it has poor performance, fix that.

[jrtc27]

https://codesearch.debian.net/search?q=%5Cbqsort%5C%28&literal=0 - 13393 files grepped (16892 results)

[brooks]

Absolutely not.

[• hselasky]

In D39723#904040, @jrtc27 wrote:

No. This is a widely-used ISO C function. If it has poor performance, fix that.

The ISO C standard does not mandate any kind of performance nor implementation. So why not state that?

It doesn't look apparent to me FreeBSD developers know about this, when you grep through the FreeBSD sources:

freebsd-src % find . -name "*.[ch]" | xargs grep qsort | wc -l

600

freebsd-src % find . -name "*.[ch]" | xargs grep mergesort | wc -l

46

freebsd-src % find . -name "*.[ch]" | xargs grep heapsort | wc -l

34

freebsd-src % find . -name "*.[ch]" | xargs grep radixsort | wc -l

12

freebsd-src %

As long as qsort() is implemented like it is in libc it should be warned about or stated somewhere obvious.

--HPS

[jrtc27]

It's legal to implement malloc as sleep(UINT_MAX); /* actual malloc code */ per ISO C's specification, or any other standard function for that matter. Everyone understands that implementations should be efficient where reasonable. You're just being obtuse here at this point. I have no interest in furthering this inane discussion.

[zlei]

I have to admit that I get bitten by the function name. I almost always treat qsort() as quicksort but it is actually a generic interface for sorting.
So it should be treated / named as sort() .

A second thought about this, I think for STD C or POSIX, use an implementation as standard is not scalable, as there're so many sorting algorithms.

From qsort(3):

The qsort() function is a modified partition-exchange sort, or quicksort.

Regardless of the naming, maybe it is right direction to place emphasis about the standard / posix requirement of qsort(). What do you all think ?

[• hselasky]

In D39723#904466, @zlei wrote:

I have to admit that I get bitten by the function name. I almost always treat qsort() as quicksort but it is actually a generic interface for sorting.
So it should be treated / named as sort() .

A second thought about this, I think for STD C or POSIX, use an implementation as standard is not scalable, as there're so many sorting algorithms.

From qsort(3):

The qsort() function is a modified partition-exchange sort, or quicksort.

Regardless of the naming, maybe it is right direction to place emphasis about the standard / posix requirement of qsort(). What do you all think ?

@zlei : ISO C apparently on defines one standard sorting function, and it is named qsort(), and the definition of performance is very loose.

@zlei : I'm doing some research if a pre-step for QuickSort, may be a solution to completely avoid QuickSort going O(N*N). If you want to join, let me know. Maybe I can put something up on GitHub.

--HPS

[zlei]

In D39723#904488, @hselasky wrote:

In D39723#904466, @zlei wrote:

I have to admit that I get bitten by the function name. I almost always treat qsort() as quicksort but it is actually a generic interface for sorting.
So it should be treated / named as sort() .

A second thought about this, I think for STD C or POSIX, use an implementation as standard is not scalable, as there're so many sorting algorithms.

From qsort(3):

The qsort() function is a modified partition-exchange sort, or quicksort.

Regardless of the naming, maybe it is right direction to place emphasis about the standard / posix requirement of qsort(). What do you all think ?

@zlei : ISO C apparently on defines one standard sorting function, and it is named qsort(), and the definition of performance is very loose.

@zlei : I'm doing some research if a pre-step for QuickSort, may be a solution to completely avoid QuickSort going O(N*N). If you want to join, let me know. Maybe I can put something up on GitHub.

I'm interested in that, although I'm not talent at algorithm ;)

--HPS