4 ms·

>> 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 i

>> 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 :)
  - dehugger 3y ago
    Picked a more belligerent interpretation, certainly. Your original comment made no allowances for the obvious interpretation and said that the consequences of the simple solution were "apocalyptically bad". While I found the ensuing discussion interesting you definitely did not approach it from a standpoint of engendering more interesting conversation. You could have gotten the same result much more easily by simply pointing out that this was not thread safe and only works in a single threaded application, and instead of nit picking we could have actually talked about better options for concurrency.
pengaru 3y ago
> OP is describing using CAS to bubblesort an array while it is concurrently read by another thread rendering something based on its contents? No. I'm not OP, but 99% certain this is not the case.

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 :)
- dehugger 3y ago
  Picked a more belligerent interpretation, certainly. Your original comment made no allowances for the obvious interpretation and said that the consequences of the simple solution were "apocalyptically bad". While I found the ensuing discussion interesting you definitely did not approach it from a standpoint of engendering more interesting conversation. You could have gotten the same result much more easily by simply pointing out that this was not thread safe and only works in a single threaded application, and instead of nit picking we could have actually talked about better options for concurrency.

pengaru 3y ago

> OP is describing using CAS to bubblesort an array while it is concurrently read by another thread rendering something based on its contents? No. I'm not OP, but 99% certain this is not the case.