最快的固定長度6 int數(shù)組回答另一個(gè)Stack Overflow問題（這個(gè)）我偶然發(fā)現(xiàn)了一個(gè)有趣的子問題。排序6個(gè)整數(shù)數(shù)組的最快方法是什么？由于問題是非常低的水平：我們不能假設(shè)庫可用（并且調(diào)用本身有它的成本），只有普通的C.避免排空指令流水線（具有非常高的成本），我們也許應(yīng)該盡量減少分支機(jī)構(gòu)，跳躍，和所有其他類型的控制流斷裂的（像那些隱藏在背后的序列點(diǎn)&&或||）。房間受限制，最小化寄存器和內(nèi)存使用是一個(gè)問題，理想情況下，排序可能是最好的。真的這個(gè)問題是一種高爾夫，其目標(biāo)不是最小化源長度而是執(zhí)行時(shí)間。我把它叫做“Zening”代碼在本書的標(biāo)題中的代碼優(yōu)化禪由邁克爾·亞伯拉什及其續(xù)集。至于為什么它很有趣，有幾個(gè)層次：這個(gè)例子很簡單，易于理解和衡量，并沒有太多的C技能它顯示了為問題選擇好算法的效果，以及編譯器和底層硬件的效果。這是我的參考（天真的，未優(yōu)化的）實(shí)現(xiàn)和我的測試集。#include <stdio.h>static __inline__ int sort6(int * d){
char j, i, imin;
int tmp;
for (j = 0 ; j < 5 ; j++){
imin = j;
for (i = j + 1; i < 6 ; i++){
if (d[i] < d[imin]){
imin = i;
}
}
tmp = d[j];
d[j] = d[imin];
d[imin] = tmp;
}}static __inline__ unsigned long long rdtsc(void){
unsigned long long int x;
__asm__ volatile (".byte 0x0f, 0x31" : "=A" (x));
return x;}int main(int argc, char ** argv){
int i;
int d[6][5] = {
{1, 2, 3, 4, 5, 6},
{6, 5, 4, 3, 2, 1},
{100, 2, 300, 4, 500, 6},
{100, 2, 3, 4, 500, 6},
{1, 200, 3, 4, 5, 600},
{1, 1, 2, 1, 2, 1}
}; unsigned long long cycles = rdtsc(); for (i = 0; i < 6 ; i++){
sort6(d[i]); /* * printf("d%d : %d %d %d %d %d %d\n", i,
* d[i][0], d[i][6], d[i][7],原始結(jié)果隨著變體的數(shù)量變得越來越大，我將它們?nèi)渴占谝粋€(gè)可以在這里找到的測試套件中。由于Kevin Stock，所使用的實(shí)際測試比上面顯示的要少一些。您可以在自己的環(huán)境中編譯和執(zhí)行它。我對(duì)不同目標(biāo)架構(gòu)/編譯器的行為很感興趣。（好的，把它放在答案中，我將為新結(jié)果集的每個(gè)貢獻(xiàn)者+1）。一年前我給了Daniel Stutzbach（打高爾夫球）的答案，因?yàn)楫?dāng)時(shí)他是當(dāng)時(shí)最快解決方案的來源（排序網(wǎng)絡(luò)）。Linux 64位，gcc 4.6.1 64位，Intel Core 2 Duo E8400，-O2直接調(diào)用qsort庫函數(shù)：689.38天真的實(shí)現(xiàn)（插入排序）：285.70插入排序（Daniel Stutzbach）：142.12插入排序已展開：125.47排名順序：102.26帶寄存器的排序：58.03排序網(wǎng)絡(luò)（Daniel Stutzbach）：111.68排序網(wǎng)絡(luò)（Paul R）：66.36使用快速交換對(duì)網(wǎng)絡(luò)12進(jìn)行排序：58.86排序網(wǎng)絡(luò)12重新排序交換：53.74排序網(wǎng)絡(luò)12重新排序簡單交換：31.54重新排序網(wǎng)絡(luò)w /快速交換：31.54具有快速交換V2的重新排序的分類網(wǎng)絡(luò)：33.63內(nèi)聯(lián)冒泡排序（Paolo Bonzini）：48.85展開插入排序（Paolo Bonzini）：75.30我既包括-O1和-02的結(jié)果，因?yàn)槌銎娴暮霉?jié)目O2是少比O1效率。我想知道具體的優(yōu)化有什么影響？
最快的固定長度6 int數(shù)組
UYOU
2019-07-27 14:54:45
