4 ms·

Can confirm, have used bubble sort in a production game engine to keep transparent objects mostly sorted. You do the compare-and-swap when you're iterating ove

Can confirm, have used bubble sort in a production game engine to keep transparent objects mostly sorted. You do the compare-and-swap when you're iterating over the objects to do some other render pass, so it adds almost nothing to the CPU time.

phkahler 3y ago
>> bubble sort in a production game engine to keep transparent objects mostly sorted. A single pass of bubble sort per frame is often enough to keep things in order. And if something glitches because it takes 2 passes it's just a single frame glitch!
jcalvinowens 3y ago
> so it adds almost nothing to the CPU time. If two threads go to CAS-sort at the same time, the cache coherency overhead would be apocalyptically bad. I'm assuming that's not what you meant?
- pengaru 3y ago
  > > so it adds almost nothing to the CPU time. > If two threads go to CAS-sort at the same time, the cache coherency overhead would be apocalyptically bad. I'm assuming that's not what you meant? I think it's apparent they didn't mean the CAS atomic instruction, just the compare-and-swap operation in bubblesort. Nothing in their comment suggested this was a multi-threaded situation.
  - jcalvinowens 3y ago
    >> You do the compare-and-swap when you're iterating over the objects to do some other render pass OP is describing using CAS to bubblesort an array while it is concurrently read by another thread rendering something based on its contents? That seems kind of wild to me but I don't know why else you add the words "some other". Sometimes sorting is an optimization and isn't necessary for correctness. The idea of two threads concurrently bubblesorting the same array with CAS is hilarious and intriguing. On x86 the double-wide CAS requires double wide alignment so I guess it couldn't actually work without extra trouble...
    - dekhn 3y ago
      You misunderstood. The CAS term isn't related to threads in aappleby's comment. aappleby is saying the following: He wrote a game engine, it renders transparent items using the painter's algorithm, which requires the items to be sorted in Z. He has a routine that iterates over all items to render them, and bubble-sorts the items in-place while iterating over the items (all in the same thread). The "compare and swap" in this case is the innermost functionality of bubblesort. I assume the author is https://github.com/aappleby https://github.com/aappleby but I don't see any obvious candidate for this code. Maybe this? https://github.com/aappleby/metroboy https://github.com/aappleby/metroboy but I can't see why a gate-level emulator woudl need to render transparent items using painter's algorithm.
      - aappleby 3y ago
        I was writing code for production game engines ~20 years ago.
    - NobodyNada 3y ago
      No, there was no mention of concurrency. As I understsand it, OP was describing a "render pass" that looked like this: for (int i = 0; i < length; i++) { // do some rendering or something } And adding a "compare and swap" to the loop: one step of a bubble sort, to keep the objects "mostly sorted": for (int i = 0; i < length; i++) { if (obj[i] > obj[i+1]) swap(&obj[i], &obj[i+1]) // do some rendering or something } Thus, "do[ing] the compare-and-swap when you're iterating over the objects to do some other render pass".
      - aappleby 3y ago
        This.
      - jcalvinowens 3y ago
        I explained another way to interpret what OP said. Your way is boring and uninteresting: this is a forum for discussion, so I picked the more interesting way :)

phkahler 3y ago

>> bubble sort in a production game engine to keep transparent objects mostly sorted. A single pass of bubble sort per frame is often enough to keep things in order. And if something glitches because it takes 2 passes it's just a single frame glitch!

jcalvinowens 3y ago

> so it adds almost nothing to the CPU time. If two threads go to CAS-sort at the same time, the cache coherency overhead would be apocalyptically bad. I'm assuming that's not what you meant?

pengaru 3y ago
> > so it adds almost nothing to the CPU time. > If two threads go to CAS-sort at the same time, the cache coherency overhead would be apocalyptically bad. I'm assuming that's not what you meant? I think it's apparent they didn't mean the CAS atomic instruction, just the compare-and-swap operation in bubblesort. Nothing in their comment suggested this was a multi-threaded situation.
- jcalvinowens 3y ago
  >> You do the compare-and-swap when you're iterating over the objects to do some other render pass OP is describing using CAS to bubblesort an array while it is concurrently read by another thread rendering something based on its contents? That seems kind of wild to me but I don't know why else you add the words "some other". Sometimes sorting is an optimization and isn't necessary for correctness. The idea of two threads concurrently bubblesorting the same array with CAS is hilarious and intriguing. On x86 the double-wide CAS requires double wide alignment so I guess it couldn't actually work without extra trouble...
  - dekhn 3y ago
    You misunderstood. The CAS term isn't related to threads in aappleby's comment. aappleby is saying the following: He wrote a game engine, it renders transparent items using the painter's algorithm, which requires the items to be sorted in Z. He has a routine that iterates over all items to render them, and bubble-sorts the items in-place while iterating over the items (all in the same thread). The "compare and swap" in this case is the innermost functionality of bubblesort. I assume the author is https://github.com/aappleby https://github.com/aappleby but I don't see any obvious candidate for this code. Maybe this? https://github.com/aappleby/metroboy https://github.com/aappleby/metroboy but I can't see why a gate-level emulator woudl need to render transparent items using painter's algorithm.
    - aappleby 3y ago
      I was writing code for production game engines ~20 years ago.
  - NobodyNada 3y ago
    No, there was no mention of concurrency. As I understsand it, OP was describing a "render pass" that looked like this: for (int i = 0; i < length; i++) { // do some rendering or something } And adding a "compare and swap" to the loop: one step of a bubble sort, to keep the objects "mostly sorted": for (int i = 0; i < length; i++) { if (obj[i] > obj[i+1]) swap(&obj[i], &obj[i+1]) // do some rendering or something } Thus, "do[ing] the compare-and-swap when you're iterating over the objects to do some other render pass".
    - aappleby 3y ago
      This.
    - jcalvinowens 3y ago
      I explained another way to interpret what OP said. Your way is boring and uninteresting: this is a forum for discussion, so I picked the more interesting way :)