Pingcap talent plan merge sort 题

[wangwangwar]

1. 串行版本
2. 去掉了大部分不必要的内存分配
3. 并行 merge sort，但 merge 是串行
4. 当子列表长度较小时，并行 merge sort 替换为串行 insertion sort
5. 并行 merge
6. 当子列表长度较小时，并行 merge 替换为串行

[wangwangwar]

测试环境：

Intel(R) Xeon(R) CPU E5-2680 v3, 48 CPUs, 96 Threads
L1d cache: 32K
L1i cache: 32K
L2 cache: 256K
L3 cache: 30720K

Normal Sort

BenchmarkNormalSort-48 1 5115363515 ns/op 64 B/op 2 allocs/op
BenchmarkNormalSort-48 1 5096126214 ns/op 64 B/op 2 allocs/op
BenchmarkNormalSort-48 1 5113312413 ns/op 64 B/op 2 allocs/op
BenchmarkNormalSort-48 1 5093389838 ns/op 64 B/op 2 allocs/op
BenchmarkNormalSort-48 1 5117013671 ns/op 64 B/op 2 allocs/op

Merge Sort 串行版本

BenchmarkMergeSort-48 1 11081671441 ns/op 15467209264 B/op 83943410 allocs/op
BenchmarkMergeSort-48 1 11028132302 ns/op 15467195552 B/op 83943379 allocs/op
BenchmarkMergeSort-48 1 11010225827 ns/op 15467193568 B/op 83943374 allocs/op
BenchmarkMergeSort-48 1 11347588701 ns/op 15467193504 B/op 83943373 allocs/op
BenchmarkMergeSort-48 1 11075893715 ns/op 15467191584 B/op 83943369 allocs/op

去掉了大部分不必要的内存分配

BenchmarkMergeSort-48 1 4507767001 ns/op 3221237376 B/op 16777243 allocs/op
BenchmarkMergeSort-48 1 4441730368 ns/op 3221227488 B/op 16777220 allocs/op
BenchmarkMergeSort-48 1 4442203780 ns/op 3221225472 B/op 16777215 allocs/op
BenchmarkMergeSort-48 1 4557373011 ns/op 3221225472 B/op 16777215 allocs/op
BenchmarkMergeSort-48 1 4598785747 ns/op 3221227488 B/op 16777220 allocs/op

并行 merge sort，但 merge 是串行

BenchmarkMergeSort-48 1 8845809789 ns/op 4064576064 B/op 36118795 allocs/op
BenchmarkMergeSort-48 1 8387374903 ns/op 3809258800 B/op 35857847 allocs/op
BenchmarkMergeSort-48 1 9060866170 ns/op 3642190448 B/op 35475370 allocs/op
BenchmarkMergeSort-48 1 9259004049 ns/op 3642332304 B/op 35481486 allocs/op
BenchmarkMergeSort-48 1 8531796291 ns/op 3612807088 B/op 35106374 allocs/op

当子列表长度较小时(< 1024)，并行 merge sort 替换为串行 merge sort

BenchmarkMergeSort-48 1 1295087594 ns/op 3498497824 B/op 33601187 allocs/op
BenchmarkMergeSort-48 1 1698284980 ns/op 3504455792 B/op 33642980 allocs/op
BenchmarkMergeSort-48 1 1252282032 ns/op 3492079056 B/op 33585747 allocs/op
BenchmarkMergeSort-48 1 1217609458 ns/op 3492321632 B/op 33588518 allocs/op
BenchmarkMergeSort-48 1 1527300107 ns/op 3493724464 B/op 33605759 allocs/op

当子列表长度较小时(< 1024)，并行 merge sort 替换为串行 insertion sort

BenchmarkMergeSort-48 2 836777567 ns/op 2014107880 B/op 69571 allocs/op
BenchmarkMergeSort-48 2 826732576 ns/op 2014044352 B/op 69077 allocs/op
BenchmarkMergeSort-48 2 878752747 ns/op 2014066656 B/op 69495 allocs/op
BenchmarkMergeSort-48 2 762676641 ns/op 2014074176 B/op 69410 allocs/op
BenchmarkMergeSort-48 2 827631123 ns/op 2014126624 B/op 70066 allocs/op

并行 merge

BenchmarkMergeSort-48 1 27221580957 ns/op 6335677136 B/op 253129477 allocs/op
BenchmarkMergeSort-48 1 28722008977 ns/op 6148575184 B/op 252920328 allocs/op
BenchmarkMergeSort-48 1 29262024729 ns/op 6137474800 B/op 252672503 allocs/op
BenchmarkMergeSort-48 1 29510851510 ns/op 6127630640 B/op 252805549 allocs/op
BenchmarkMergeSort-48 1 29536423564 ns/op 6113501936 B/op 252615838 allocs/op

当子列表长度较小时(< 1 << 17 )，并行 merge 替换为串行

BenchmarkMergeSort-48 2 553334312 ns/op 2014331720 B/op 71360 allocs/op
BenchmarkMergeSort-48 2 579339834 ns/op 2014045232 B/op 69741 allocs/op
BenchmarkMergeSort-48 2 578149785 ns/op 2014097352 B/op 70341 allocs/op
BenchmarkMergeSort-48 2 572350636 ns/op 2014649448 B/op 72815 allocs/op
BenchmarkMergeSort-48 2 565520438 ns/op 2014092960 B/op 70448 allocs/op

[wangwangwar]

改进：simd加速merge？avx2 min max对64bit数不支持，bitonic算法不能直接实现，修改后的加速效果不明显