5 ms·

Bit flips are quite useful for sorting huge arrays of data: https://news.ycombinator.com/item?id=28766154 https://news.ycombinator.com/item?id=28766154

smegma2 4y ago
That code has a race condition :^)
- xyzzyz 4y ago
  Did you mean ray's condition?
  - snoshy 4y ago
    Oddly apropos anecdote to your pun: About 15 years ago, while working on Windows at Microsoft, a test machine sitting at my desk hit a kernel panic (BSOD). As was standard working on the test team, the machine was already setup for kernel debugging, and so I set out to debug it a bit in order to file a decent bug report. Hours later, I couldn't make sense of it (I wasn't super experienced at this point). A few of the nearby devs couldn't either, and a small troop of us curious enough about the puzzler eventually escalated to the resident wizard, Raymond Chen[1]. Within 15 minutes of checking our work and poking at the machine, he traced the root cause down to a bit flip. Ray's condition indeed. :) [1] https://devblogs.microsoft.com/oldnewthing/ https://devblogs.microsoft.com/oldnewthing/
    - elevaet 4y ago
      Great story, a true random glitch. Interestingly, a blog post of his was up on HN front page the other day: "The x86 architecture is the weirdo, part 2" https://news.ycombinator.com/item?id=31077912 https://news.ycombinator.com/item?id=31077912
    - sbierwagen 4y ago
      Ray complained in 2005 that Microsoft sees lots of weirdo crash reports from computers with overclocked CPUs https://devblogs.microsoft.com/oldnewthing/20050412-47/?p=35923 https://devblogs.microsoft.com/oldnewthing/20050412-47/?p=35...
      - rvnx 4y ago
        Awwww, that Windows Me must have been overclocked out-of-the-box considering the amount of BSOD :D
charcircuit 4y ago
That's not a proper sort. A sort is not just a function that takes in a list and returns a list that is sorted. The result must also include all of the elements that you had when starting. That property isn't checked by the code you linked.
- layer8 4y ago
  Someone should calculate how many copies of the array you need (as a function of input data size) to make that sorting strategy work with reasonable assurance that the original data is maintained.
  - deleted 4y ago
    [deleted]
- hvdijk 4y ago
  Do you know of any sort routine that guarantees the result includes all of the input elements even in the event of random bit flips? If not, do you consider the sorting routines in your everyday libraries improper as well or is that a special restriction reserved for this particular implementation?
  - tshaddox 4y ago
    No, when we normally talk about code we have some vague notion of a formal system that works according to its specification, and thus that !isSorted loop example is pretty clearly invalid. And even if you do allow for random bit flips, surely that’s more likely to happen to the boolean returned by isSorted than for enough bits to flip to make the array sorted.
    - hvdijk 4y ago
      The objection that the GP raised, the lack of a check that the result includes all of the elements of the input, is not needed under your notion of a system that works according to its specification, as according to that specification it is a loop invariant. It is also not useful, as it is an infinite loop. Your view of why cosmic ray sort is not a proper sort therefore contradicts GP's explanation, even if you share the GP's conclusion. My question was aimed at further exploring the GP's view; I think an opposing view does not help here.

smegma2 4y ago

That code has a race condition :^)

xyzzyz 4y ago
Did you mean ray's condition?
- snoshy 4y ago
  Oddly apropos anecdote to your pun: About 15 years ago, while working on Windows at Microsoft, a test machine sitting at my desk hit a kernel panic (BSOD). As was standard working on the test team, the machine was already setup for kernel debugging, and so I set out to debug it a bit in order to file a decent bug report. Hours later, I couldn't make sense of it (I wasn't super experienced at this point). A few of the nearby devs couldn't either, and a small troop of us curious enough about the puzzler eventually escalated to the resident wizard, Raymond Chen[1]. Within 15 minutes of checking our work and poking at the machine, he traced the root cause down to a bit flip. Ray's condition indeed. :) [1] https://devblogs.microsoft.com/oldnewthing/ https://devblogs.microsoft.com/oldnewthing/
  - elevaet 4y ago
    Great story, a true random glitch. Interestingly, a blog post of his was up on HN front page the other day: "The x86 architecture is the weirdo, part 2" https://news.ycombinator.com/item?id=31077912 https://news.ycombinator.com/item?id=31077912
  - sbierwagen 4y ago
    Ray complained in 2005 that Microsoft sees lots of weirdo crash reports from computers with overclocked CPUs https://devblogs.microsoft.com/oldnewthing/20050412-47/?p=35923 https://devblogs.microsoft.com/oldnewthing/20050412-47/?p=35...
    - rvnx 4y ago
      Awwww, that Windows Me must have been overclocked out-of-the-box considering the amount of BSOD :D

charcircuit 4y ago

That's not a proper sort. A sort is not just a function that takes in a list and returns a list that is sorted. The result must also include all of the elements that you had when starting. That property isn't checked by the code you linked.

layer8 4y ago
Someone should calculate how many copies of the array you need (as a function of input data size) to make that sorting strategy work with reasonable assurance that the original data is maintained.
- deleted 4y ago
  [deleted]
hvdijk 4y ago
Do you know of any sort routine that guarantees the result includes all of the input elements even in the event of random bit flips? If not, do you consider the sorting routines in your everyday libraries improper as well or is that a special restriction reserved for this particular implementation?
- tshaddox 4y ago
  No, when we normally talk about code we have some vague notion of a formal system that works according to its specification, and thus that !isSorted loop example is pretty clearly invalid. And even if you do allow for random bit flips, surely that’s more likely to happen to the boolean returned by isSorted than for enough bits to flip to make the array sorted.
  - hvdijk 4y ago
    The objection that the GP raised, the lack of a check that the result includes all of the elements of the input, is not needed under your notion of a system that works according to its specification, as according to that specification it is a loop invariant. It is also not useful, as it is an infinite loop. Your view of why cosmic ray sort is not a proper sort therefore contradicts GP's explanation, even if you share the GP's conclusion. My question was aimed at further exploring the GP's view; I think an opposing view does not help here.