Timeline for How AlphaDev improved sorting algorithms?
Current License: CC BY-SA 4.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 29, 2023 at 17:53 | comment | added | Peter Cordes |
With cmovg as shown, it can duplicate one of the input elements, e.g. sorting 2,1,1 to 2,1,2 instead of 1,1,2. (But apparently the change they committed to libc++ doesn't have this problem.)
|
|
| Jun 29, 2023 at 17:52 | comment | added | Peter Cordes |
An answer on Trying to understand the new sorting algorithm from AlphaDev: why does my assembly code not work as expected? points out that as well as being confusingly presented, their code for the final 2 steps isn't even correct in the image they show. They need to use cmovge not cmovg, for the compare that got optimized, since they're comparing a different element than they're selecting on (to reduce critical path latency I think, as well as saving an instruction on x86 but not AArch64.)
|
|
| Jun 29, 2023 at 15:30 | vote | accept | nico263nico | ||
| Jun 29, 2023 at 15:08 | history | answered | Discrete lizard♦ | CC BY-SA 4.0 |