3 ms·

[Deleted, humour doesn't come through in text.]

mbustamanter 3y ago
Not even noon and Colin is already roasting. Reminds me of [0], also by him. [0] https://news.ycombinator.com/item?id=35079 https://news.ycombinator.com/item?id=35079
- cperciva 3y ago
  I haven't recovered from jetlag yet. Sorry, my snark went overboard.
klyrs 3y ago
I was mostly joking, but worst-cases include sorted and reverse-sorted lists. I've seen those happen accidentally, in practice, resulting in accidentally-quadratic runtime. This is why, when I taught that class, I made students compare sorting algorithms on real world data sets.
- cperciva 3y ago
  Sure. In this case though the list doesn't change from boot to boot, or for that matter from system to system; if we hit a worst-case we would notice before the release shipped. Also, the worst case would be "systems take 2 ms extra time to boot" so it's not exactly a disaster.
  - whimsicalism 3y ago
    > though the list doesn't change from boot to boot, or for that matter from system to system; if we hit a worst-case we would notice before the release shipped. Wait what - why don't you just sort it at build time then? I'm probably misunderstanding what you are saying or maybe just a premature optimization. e: Nevermind, read further in the thread and saw you answered [0] [0]: https://twitter.com/cperciva/status/1659561673278226432 https://twitter.com/cperciva/status/1659561673278226432
    - cperciva 3y ago
      We might end up doing that. A quicksort takes it from 2 ms down to 40 us though, and doing the sorting at build time would take a lot of linker magic. (The SYSINITs are records in separate object files which are marked as going into a particular ELF section, so we don't actually have a complete list of them until we finish linking the kernel.)
      - alberth 3y ago
        Any consideration to use Radix sort. It’s typically the fastest. It’s also a stable sort algorithm. https://youtu.be/BeoCbJPuvSE https://youtu.be/BeoCbJPuvSE
- sn9 3y ago
  Isn't the point of quicksort that the randomization of the pivot selection means that you're extremely unlikely to run into a pathological case for the specific pivot chosen? And perhaps even more unlikely if you permute the input sequence before sorting it. I'm basing this off of my understanding of Skiena's discussion of quicksort in The Algorithm Design Manual.

Not even noon and Colin is already roasting. Reminds me of [0], also by him. [0] https://news.ycombinator.com/item?id=35079 https://news.ycombinator.com/item?id=35079

cperciva 3y ago
I haven't recovered from jetlag yet. Sorry, my snark went overboard.

klyrs 3y ago

I was mostly joking, but worst-cases include sorted and reverse-sorted lists. I've seen those happen accidentally, in practice, resulting in accidentally-quadratic runtime. This is why, when I taught that class, I made students compare sorting algorithms on real world data sets.

cperciva 3y ago
Sure. In this case though the list doesn't change from boot to boot, or for that matter from system to system; if we hit a worst-case we would notice before the release shipped. Also, the worst case would be "systems take 2 ms extra time to boot" so it's not exactly a disaster.
- whimsicalism 3y ago
  > though the list doesn't change from boot to boot, or for that matter from system to system; if we hit a worst-case we would notice before the release shipped. Wait what - why don't you just sort it at build time then? I'm probably misunderstanding what you are saying or maybe just a premature optimization. e: Nevermind, read further in the thread and saw you answered [0] [0]: https://twitter.com/cperciva/status/1659561673278226432 https://twitter.com/cperciva/status/1659561673278226432
  - cperciva 3y ago
    We might end up doing that. A quicksort takes it from 2 ms down to 40 us though, and doing the sorting at build time would take a lot of linker magic. (The SYSINITs are records in separate object files which are marked as going into a particular ELF section, so we don't actually have a complete list of them until we finish linking the kernel.)
    - alberth 3y ago
      Any consideration to use Radix sort. It’s typically the fastest. It’s also a stable sort algorithm. https://youtu.be/BeoCbJPuvSE https://youtu.be/BeoCbJPuvSE
sn9 3y ago
Isn't the point of quicksort that the randomization of the pivot selection means that you're extremely unlikely to run into a pathological case for the specific pivot chosen? And perhaps even more unlikely if you permute the input sequence before sorting it. I'm basing this off of my understanding of Skiena's discussion of quicksort in The Algorithm Design Manual.