6 ms·

I rarely ever do need a sorting algorithm for what I do. I might not have done even one sort call in 2021. Usually the data I have is sorted by construction, or

I rarely ever do need a sorting algorithm for what I do. I might not have done even one sort call in 2021. Usually the data I have is sorted by construction, or doesn't need to be sorted in any particular order. When I do need to sort, I just use qsort from libc. It's also easy to write my own version of qsort. I once measured qsort vs std::sort on plain ints (basically the most pessimistic case for qsort vs std::sort) and the difference was like 2x. If this becomes a bottleneck then it's worth investigating how to take advantage of additional context to speed up the sorting much more than any generic sorting algorithm could do anyway. Simple example: bucket sort. (I'm 100% confident sorting performance hasn't ever been noticeable in my career so far, but I've done simple optimizations like that once in a while for fun). > Both solutions are really bad. Due to what I described above, I'm actually in favour of qsort - no new code is generated, just a simple library call that takes a pointer to the comparison function. Really really easy to use.

dnautics 5y ago
I don't know what you do, but for our codebase, we run transactions against the database in most of the integration tests. We can't generally be sure the database won't return rows in some order it likes that aren't the rows we expect -- so if we don't have a generic sorting function we will have flaky tests.
- jstimpfle 5y ago
  If you can't bring the database to return the values in a well defined order, absolutely go ahead and sort it! No need for _generics_ though, qsort() will do just fine. (C probably isn't great for DB interop in any case).
tsimionescu 5y ago
qsort is a horrible function, and infamously so. First, since it's part of the C stdlib, it is almost universally dynamically linked, precluding any chance for it to be inlined, and even worse, it calls a function pointer. Even ignoring performance, it has no support for checking the types, which in C means it can easily mess up memory badly. For example, I can call `qsort(arrayOfInts, num, sizeof(float), funcThatComparesTwoStrings)` and I'll get a really bad time, with absolutely no way for the compiler to tell me I'm doing something obviously wrong.
- jstimpfle 5y ago
  It does not matter. Your concerns are entirely academic. Simplicity wins. > I can call `qsort(arrayOfInts, num, sizeof(float), funcThatComparesTwoStrings)` Don't do this. Do "qsort(a, n, sizeof *a, compare)" > with absolutely no way for the compiler to tell me I'm doing something obviously wrong. In the event that it does not work, two things are very likely true. 1) it was a really dumb mistake. 2) you will notice immediately and can fix the mistake. The idea that everything must be caught by the compiler is narrow-minded and ultimately can't be achieved. Stop worrying about hypothetical problems that aren't problems in practice. There are enough real problems to work on.
  - hota_mazi 5y ago
    > you will notice immediately No, you won't notice immediately. You will only notice when you run your code, because it will crash. And it might not crash right away, because the bad code is not being run, so you have a crash waiting to happen at some time in the future, which might have been avoided with a competent type system. Users of statically typed languages have a different understanding of "immediately" than you do. If the compiler knows my code will crash, it should simply refuse to compile it until I fix it. > The idea that everything must be caught by the compiler is narrow-minded and ultimately can't be achieved. Ah, the famous fallacy "We can't reach 100% so let's just be content with 0%". That's not how the world works. Static types provide not just non crash guarantees but plenty of other advantages (automatic refactorings, performance, code that's easier to read and maintain, etc...). You have just gotten used to a crappy developer experience because you are using a dynamically typed (or very badly typed) programming language. Get out of that boiling pot and be more exigent from your programming language, there are some very good ones available today which will make you go back to your statements above in a few years and think "Yeah... that was a pretty silly thing to say, but I know better now".
    - jstimpfle 5y ago
      > You will only notice when you run your code How did you infer that that's not immediately? > If the compiler knows my code will crash, it should simply refuse to compile it until I fix it. Sure but what if it doesn't know that, then I won't complain about the next best opportunity, which is pressing F5 once and seeing the code I just typed doesn't work as intended. > Static types provide not just non crash guarantees How about no? > Ah, the famous fallacy "We can't reach 100% so let's just be content with 0%". If using a void-pointer parameter once in a blue moon for some convenience (callback function pointer), how is that 0% and not 99%? I recognize I've written too many comments, seeing as the replies are starting to get extremely poor. Ignoring the rest.
jeeeb 5y ago
Maybe it’s lack of imagination but I cannot see how qsort is easier to use than std::sort. In particular because std::sort is templated you can use anything callable including a lambda or function pointer as the comparator. But if you already have operator< defined for the type you don’t even need to define a comparator. It seems like std::sort is shorter and simpler to write, safer, faster and generic across container types (including c arrays).
- jstimpfle 5y ago
  I _believe_ std::sort used to be more complicated because you had to define a class with a compare method for custom comparison functions, or something like that. Looking here https://en.cppreference.com/w/cpp/algorithm/sort https://en.cppreference.com/w/cpp/algorithm/sort , I cannot be arsed to find out what works since which version of C++. Come on, look at that link and tell me with a straight face you can't grok the qsort() signature much more easily than that mess. Other than that, the STL is generally slower compiling compared to only including plain C headers, which is also taxing on the "ease of use" department.
  - dataangel 5y ago
    `sort(begin(foo), end(foo))` Has worked in C++ for ~25 years as long as `foo` is a container of items with an `operator<`. It has never required defining a separate class. It will also optimize better than qsort when qsort fails to inline.
    - slavik81 5y ago
      Your main point is correct, but std::begin and std::end were added in C++11. You would have used pointers or begin/end member functions for most of those 25 years.
    - deleted 5y ago
      [deleted]
    - deleted 5y ago
      [deleted]
BenFrantzDale 5y ago
You may not need to sort, but std::rotate? std::partition? std::all_of? The list goes on. Without templates, these wouldn’t provide the value they do. (Thanks Stepanov!)

dnautics 5y ago

I don't know what you do, but for our codebase, we run transactions against the database in most of the integration tests. We can't generally be sure the database won't return rows in some order it likes that aren't the rows we expect -- so if we don't have a generic sorting function we will have flaky tests.

jstimpfle 5y ago
If you can't bring the database to return the values in a well defined order, absolutely go ahead and sort it! No need for _generics_ though, qsort() will do just fine. (C probably isn't great for DB interop in any case).

tsimionescu 5y ago

qsort is a horrible function, and infamously so. First, since it's part of the C stdlib, it is almost universally dynamically linked, precluding any chance for it to be inlined, and even worse, it calls a function pointer. Even ignoring performance, it has no support for checking the types, which in C means it can easily mess up memory badly. For example, I can call `qsort(arrayOfInts, num, sizeof(float), funcThatComparesTwoStrings)` and I'll get a really bad time, with absolutely no way for the compiler to tell me I'm doing something obviously wrong.

jstimpfle 5y ago
It does not matter. Your concerns are entirely academic. Simplicity wins. > I can call `qsort(arrayOfInts, num, sizeof(float), funcThatComparesTwoStrings)` Don't do this. Do "qsort(a, n, sizeof *a, compare)" > with absolutely no way for the compiler to tell me I'm doing something obviously wrong. In the event that it does not work, two things are very likely true. 1) it was a really dumb mistake. 2) you will notice immediately and can fix the mistake. The idea that everything must be caught by the compiler is narrow-minded and ultimately can't be achieved. Stop worrying about hypothetical problems that aren't problems in practice. There are enough real problems to work on.
- hota_mazi 5y ago
  > you will notice immediately No, you won't notice immediately. You will only notice when you run your code, because it will crash. And it might not crash right away, because the bad code is not being run, so you have a crash waiting to happen at some time in the future, which might have been avoided with a competent type system. Users of statically typed languages have a different understanding of "immediately" than you do. If the compiler knows my code will crash, it should simply refuse to compile it until I fix it. > The idea that everything must be caught by the compiler is narrow-minded and ultimately can't be achieved. Ah, the famous fallacy "We can't reach 100% so let's just be content with 0%". That's not how the world works. Static types provide not just non crash guarantees but plenty of other advantages (automatic refactorings, performance, code that's easier to read and maintain, etc...). You have just gotten used to a crappy developer experience because you are using a dynamically typed (or very badly typed) programming language. Get out of that boiling pot and be more exigent from your programming language, there are some very good ones available today which will make you go back to your statements above in a few years and think "Yeah... that was a pretty silly thing to say, but I know better now".
  - jstimpfle 5y ago
    > You will only notice when you run your code How did you infer that that's not immediately? > If the compiler knows my code will crash, it should simply refuse to compile it until I fix it. Sure but what if it doesn't know that, then I won't complain about the next best opportunity, which is pressing F5 once and seeing the code I just typed doesn't work as intended. > Static types provide not just non crash guarantees How about no? > Ah, the famous fallacy "We can't reach 100% so let's just be content with 0%". If using a void-pointer parameter once in a blue moon for some convenience (callback function pointer), how is that 0% and not 99%? I recognize I've written too many comments, seeing as the replies are starting to get extremely poor. Ignoring the rest.

jeeeb 5y ago

Maybe it’s lack of imagination but I cannot see how qsort is easier to use than std::sort. In particular because std::sort is templated you can use anything callable including a lambda or function pointer as the comparator. But if you already have operator< defined for the type you don’t even need to define a comparator. It seems like std::sort is shorter and simpler to write, safer, faster and generic across container types (including c arrays).

jstimpfle 5y ago
I _believe_ std::sort used to be more complicated because you had to define a class with a compare method for custom comparison functions, or something like that. Looking here https://en.cppreference.com/w/cpp/algorithm/sort https://en.cppreference.com/w/cpp/algorithm/sort , I cannot be arsed to find out what works since which version of C++. Come on, look at that link and tell me with a straight face you can't grok the qsort() signature much more easily than that mess. Other than that, the STL is generally slower compiling compared to only including plain C headers, which is also taxing on the "ease of use" department.
- dataangel 5y ago
  `sort(begin(foo), end(foo))` Has worked in C++ for ~25 years as long as `foo` is a container of items with an `operator<`. It has never required defining a separate class. It will also optimize better than qsort when qsort fails to inline.
  - slavik81 5y ago
    Your main point is correct, but std::begin and std::end were added in C++11. You would have used pointers or begin/end member functions for most of those 25 years.
  - deleted 5y ago
    [deleted]
  - deleted 5y ago
    [deleted]

BenFrantzDale 5y ago

You may not need to sort, but std::rotate? std::partition? std::all_of? The list goes on. Without templates, these wouldn’t provide the value they do. (Thanks Stepanov!)