7 ms·
True but I think the real cause of this is surely that C makes it too hard to use a sorting library that someone competent has written. I would not be surprised
by IshKebab 4y ago
True but I think the real cause of this is surely that C makes it too hard to use a sorting library that someone competent has written. I would not be surprised if the author was fully aware of the N^2 complexity but opted for a simpler implementation anyway.
- pjc50 4y agoqsort() not good enough for you? (More realistically, below people are discussing that in the kernel environment the set of standard or third party library available may be unavoidably limited)
- jart 4y agoqsort() is pretty slow if you're sorting something like long[]. In that case, radix sort goes 5x faster and vectorized quicksort goes 10x faster. If you're sorting int[] then vectorized quicksort goes 25x faster than qsort(). Nothing goes faster. The issue is it's a big ugly c++ monstrosity that's a huge pain to compile.
- rcxdude 4y agoThat's fair if the constant factor is relevant, but if bubble sort is terminating in any reasonable timescale then the difference between qsort, C++ std::sort, and a custom implementation is really not a factor.
- jart 4y agoPeople who don't compute much data don't need computer science.
- paulddraper 4y agoBut if you're comparing to bubblesort.....
- nice2meetu 4y agoThere is a quirk (almost a bug?) in FreeBSD's qsort where it will switch to insertsort for the whole array under certain conditions, which we hit in production given how our data was arranged. (I think this was the check) https://github.com/freebsd/freebsd-src/blob/main/lib/libc/stdlib/qsort.c#L171 https://github.com/freebsd/freebsd-src/blob/main/lib/libc/st...
- stefan_ 4y agoI like how someone felt the need to write out insertion sort in some 4 line code golf challenge in the midst of qsort. This right here is why no one wants to deal with C anymore.
- erk__ 4y agoDid a bit of digging and found that there used to be a comment for why it was done, but it got removed [0] when they switched to the implementation from Bentley & McIlroy's "engineering a sort function" [1] around 1992. [0]: https://github.com/weiss/original-bsd/commit/d3fcf71e0db57cb346606f3e100c17a565b1cc2f#diff-80cbaaf17a9c3baf31292416f97d13837515bdc13c94eedc285a79504409c708L167-L181 https://github.com/weiss/original-bsd/commit/d3fcf71e0db57cb... [1]: https://cs.fit.edu/~pkc/classes/writing/papers/bentley93engineering.pdf https://cs.fit.edu/~pkc/classes/writing/papers/bentley93engi...
- JdeBP 4y agoNonetheless, qsort() is available in libkern.
- canucker2016 4y agoNot at the time that the bubble-sort code was used though. see https://news.ycombinator.com/item?id=36005209 https://news.ycombinator.com/item?id=36005209
- JdeBP 4y agoYou mean written. It's been available for many of the years that it has been used. (-:
- IshKebab 4y agoNo. In most languages sorting a container is `foo.sort()` or something similar. `qsort()` is much more faff. I mean, clearly it wasn't good enough otherwise they would have used it, no? Perhaps integrating it was a huge faff.
- JohnFen 4y ago> that C makes it too hard to use a sorting library that someone competent has written. This makes no sense to me. What about C makes it hard to use a good library?
- jjoonathan 4y agoC arrays suck on the best of days and qsort requires that you understand function pointers and types which are some of the hairiest C syntax in common use. The C Clockwise Spiral rule is truly special. It's easy to lose sight of the climb once you're at the top.
- JohnFen 4y agoWell, we could debate this, but it's all irrelevant to the assertion that C makes it hard to use good libraries.
- jjoonathan 4y agoOh, right, I forgot that C's library/package management situation sucks so hard that makes the awful syntax look like a comparatively small problem.
- JohnFen 4y agoThis actually made me laugh out loud. Yes, if your problem with C is that it doesn't need a package management mechanism like some other languages, then C is clearly not for you. But C is very far from the only language like this. It's a bit like criticizing a fish for having no legs.
- IshKebab 4y ago> if your problem with C is that it doesn't need a package management mechanism like some other languages The problem isn't that it doesn't need one, it's that it doesn't have one. I have no idea why you would think that it doesn't need one. Well there is vcpkg now anyway so it finally does have one.
- cultofmetatron 4y agodownvote me if you want but this is probably the best argument for rust I've ever seen
- EuropeOverlords 4y ago[flagged]
- cultofmetatron 4y agoin what way did I misunderstand? > C makes it too hard to use a sorting library that someone competent has written. rust makes it easy to create generic data structures via generics. It would be trivial to swap between different underlying sorting algos as long as it was given a type compatible function for how to compare the contained items. what exactly am I not understanding here?
- TingPing 4y agoThe fact that this was a developers mistake and has nothing to do with the language.
- somat 4y agoSlight scarcasm. yes too hard. http://man.openbsd.org/qsort http://man.openbsd.org/qsort having said that this specific sort is somewhere deep in kernel boot land. and kernel code can't really use the standard library. I am not sure if there is a standard kernel sort.
- kllrnohj 4y agoOf course it can. Just extract the qsort implementation to a static library pulled in by the kernel and by libc.