詳解DeepMind排序算法

/ move37.S
 .equ P,%rax
 .equ Q,%rcx
 .equ R,%rdx
 .equ S,%rsi
move37: mov (%rdi),P
 mov 8(%rdi),Q
 mov 16(%rdi),R
 mov R,S
 cmp P,R
 cmovg P,R
 cmovl P,S
 cmp S,Q
 cmovg Q,P
 cmovg S,Q
 mov R,(%rdi)
 mov Q,8(%rdi)
 mov P,16(%rdi)
 ret
 .type move37,@function
 .size move37,.-move37
 .globl move37
// deepsort1.c
#include
void move37(long *);
int main() {
 long A[3] = {3, 1, 2};
 move37(A);
 printf("%d %d %d
", A[0], A[1], A[2]);

# run this on the shell
cc -o deepsort1 deepsort1.c move37.S
./deepsort1
2 1 3

// Ensures that *__x, *__y and *__z are ordered according to the comparator __c,
// under the assumption that *__y and *__z are already ordered.
template
inline _LIBCPP_HIDE_FROM_ABI void __partially_sorted_swap(
 _RandomAccessIterator __x, _RandomAccessIterator __y,
 _RandomAccessIterator __z, _Compare __c) {
 using value_type = typename iterator_traits<_RandomAccessIterator>::value_type;
 bool __r = __c(*__z, *__x);
 value_type __tmp = __r ? *__z : *__x;
 *__z = __r ? *__x : *__z;
 __r = __c(__tmp, *__y);
 *__x = __r ? *__x : *__y;
 *__y = __r ? *__y : __tmp;
}

sort3: mov (%rdi),%rcx
 mov 8(%rdi),%rdx
 mov 16(%rdi),%rsi
 mov %rdx,%rax
 cmp %rdx,%rsi
 cmovl %rsi,%rax
 cmovl %rdx,%rsi
 mov %rcx,%rdx
 cmp %rcx,%rsi
 cmovl %rsi,%rdx
 cmovl %rcx,%rsi
 cmp %rax,%rdx
 cmovge %rax,%rcx
 cmovl %rax,%rdx
 mov %rcx,(%rdi)
 mov %rdx,8(%rdi)
 mov %rsi,16(%rdi)
 ret
 .globl sort3
 .size sort3,.-sort3

// sorts [a,b,c]
 if (a > b) SWAP(a, b);
 if (a > c) SWAP(a, c);
 if (b > c) SWAP(b, c);

mov %rdx,%rax  // create temporary
 cmp %rdx,%rsi  // compare
 cmovl %rsi,%rax  // conditional move
 cmovl %rdx,%rsi  // conditional move
/ repeat thrice

sort3: mov (%rdi),%rcx
 mov 8(%rdi),%rdx
 mov 16(%rdi),%rsi
 mov %rdx,%rax
 cmp %rdx,%rsi
 cmovl %rsi,%rax
 cmovl %rdx,%rsi
 mov %rcx,%rdx
 cmp %rcx,%rsi
 cmovl %rsi,%rdx
 cmovl %rcx,%rsi
 mov %rdx,%rcx  // <-- wrekt by AlphaDev
 cmp %rax,%rdx
 cmovge %rax,%rcx
 cmovl %rax,%rdx
 mov %rcx,(%rdi)
 mov %rdx,8(%rdi)
 mov %rsi,16(%rdi)
 ret

sort3: mov (%rdi),%rcx
 mov 8(%rdi),%rdx
 mov 16(%rdi),%rsi
 mov %rdx,%rax  // can it go?
 cmp %rdx,%rsi
 cmovl %rsi,%rax
 cmovl %rdx,%rsi
 mov %rcx,%rdx  // can it go?
 cmp %rcx,%rsi
 cmovl %rsi,%rdx
 cmovl %rcx,%rsi
 mov %rdx,%rcx  // <-- wrekt by AlphaDev
 cmp %rax,%rdx
 cmovge %rax,%rcx
 cmovl %rax,%rdx
 mov %rcx,(%rdi)
 mov %rdx,8(%rdi)
 mov %rsi,16(%rdi)
 ret

sort4: ldp x1,x2,[x0]
 ldr x3,[x0,16]
 cmp x2,x3
 csel x4,x2,x3,le
 csel x2,x2,x3,ge
 cmp x2,x1
 csel x3,x2,x1,le
 csel x2,x2,x1,ge
 cmp x4,x3
 csel x5,x1,x4,gt
 csel x4,x4,x3,ge
 stp x5,x4,[x0]
 str x2,[x0,16]
 ret

// sorts [a,b]
static inline void Sort2(long *a, long *b) {
 int r = *a < *b;
 long t = r ? *a : *b;
 *b = r ? *b : *a;
 *a = t;
}
// sorts [a,b,c] assuming [b,c] is already sorted
static inline void PartialSort3(long *a, long *b, long *c) {
 int r = *c < *a;
 long t = r ? *c : *a;
 *c = r ? *a : *c;
 r = t < *b;
 *a = r ? *a : *b;
 *b = r ? *b : t;
}
// sorts [a,b,c]
static inline void Sort3(long *a, long *b, long *c) {
 Sort2(b, c);
 PartialSort3(a, b, c);
}
// sorts [a,b,c,d]
static inline void Sort4(long *a, long *b, long *c, long *d) {
 Sort2(a, c);
 Sort2(b, d);
 Sort2(a, b);
 Sort2(c, d);
 Sort2(b, c);
}
// sorts [a,b,c,d,e]
static inline void Sort5(long *a, long *b, long *c, long *d, long *e) {
 Sort2(a, b);
 Sort2(d, e);
 PartialSort3(c, d, e);
 Sort2(b, e);
 PartialSort3(a, c, d);
 PartialSort3(b, c, d);
}

static inline void InsertionSort(long *A, long n) {
 long i, j, t;
 for (i = 1; i < n; i++) {
 t = A[i];
 j = i - 1;
 while (j >= 0 && A[j] > t) {
 A[j + 1] = A[j];
 j = j - 1;
 }
 A[j + 1] = t;
 }
}
void longsort(long *A, long n) {
 long t, p, i, j;
 switch (n) {
 case 0:
 return;
 case 1:
 return;
 case 2:
 return Sort2(A, A + 1);
 case 3:
 return Sort3(A, A + 1, A + 2);
 case 4:
 return Sort4(A, A + 1, A + 2, A + 3);
 case 5:
 return Sort5(A, A + 1, A + 2, A + 3, A + 4);
 default:
 if (n <= 32) {
 InsertionSort(A, n);
 } else {
 for (p = A[n >> 1], i = 0, j = n - 1;; i++, j--) {
 while (A[i] < p) i++;
 while (A[j] > p) j--;
 if (i >= j) break;
 t = A[i];
 A[i] = A[j];
 A[j] = t;
 }
 LongSort(A, i);
 LongSort(A + i, n - i);
 }
 break;
 }
}

void longsort(long *A, long n) {
 long t, p, i, j;
 switch (n) {
 case 0:
 return;
 case 1:
 return;
 /* case 2: */
 /* return Sort2(A, A + 1); */
 /* case 3: */
 /* return Sort3(A, A + 1, A + 2); */
 /* case 4: */
 /* return Sort4(A, A + 1, A + 2, A + 3); */
 /* case 5: */
 /* return Sort5(A, A + 1, A + 2, A + 3, A + 4); */
 default:
 if (n <= 32) {
 InsertionSort(A, n);
 } else {
 for (p = A[n >> 1], i = 0, j = n - 1;; i++, j--) {
 while (A[i] < p) i++;
 while (A[j] > p) j--;
 if (i >= j) break;
 t = A[i];
 A[i] = A[j];
 A[j] = t;
 }
 LongSort(A, i);
 LongSort(A + i, n - i);
 }
 break;
 }
}