Cコード - メモリアクセス/プリエンプション

Question

データ請求Iは、コードの一部を書かれている：

unsigned char buf[4096]; // data in chunks of size 4k 
unsigned counter[256]; 

私はすべての3つの連続したバイトのためのI/Pのデータを加算し、ANSを記憶しています。 ex：temp [4096]; temp [0] = buf [0] + buf [1] + buf [2]; ... 4096

までヒストグラムは、コードを使用して、温度の結果から生成される：

for(i = 0; i < 4096; i++) 
counter[temp[i]]++; 

ヒストグラムがソート（バブルソート）し、次いで8最も繰り返し値が取られている先頭です。コードはLinuxカーネル（2.6.35）で実行されます

私が直面している問題は、コードを実行するのにかかる時間が非常に高速です（私のラップトップで6マイクロ秒、 gettimeofday func）。しかし、ソーティングを導入した後、プロセスは大幅に遅くなります（44マイクロ秒）。ソート機能自体は20マイクロ秒かかるので、時間がそんなに長くなっているのがなぜ分かりません。私はcachegrindを使用してメモリ解析を行いました。結果は正常で、プリエンプションを無効にしてみても、まだ違いは見られません。もし誰かが私をここで助けてくれるなら。ありがとう！

Answer 1

バブルソートが遅い... O（N^2）複雑であるあなたはより高速なパフォーマンスをしたい場合は...、ヒープのようなデータ構造を使用するか、またはあなたのアレイ上のクイックソートアルゴリズムを実行して、どちらの並べ替えプロセスの複雑さをO（N log N）にします。さらに、両方の方法は、固定長配列に対してもうまく機能します。

Answer 2

バブルソートは、それが比較され、4096 * 4096 = 16,777,216回まで自分の価値観を交換、遅いです。 8つの最良値だけが必要な場合は、1スイープの選択が確実に速くなります。そのようなもの。

const uint_t n = 8; 
uint_t best[n] = {0}; 
uint_t index[n] = {0}; 
uint_t j; 

for(uint_t i=0; i<4096; i++) { 

    if(counter[i] > best[n-1]) { 
    for(j=n-2; j && counter[i] > best[j]; j--);   /* Find the insertion position, as our value might be bigger than the value at position n-1. */ 
    memmove(&best [j+1], &best[j] , (n-1 -j) * sizeof best[0]);  /* Shift the values beyond j up 1 */ 
    memmove(&index[j+1], &index[j], (n-1 -j) * sizeof index[0]); 
    best[j] = counter[i];         /* Put the current best value at the top */ 
    index[j] = i;           /* Store the index in the second array to know where the best 
    } 

値でした。 */ } }

これで、選択配列が小さいため、memmoveのコストはごくわずかです。 配列をソートする必要はありません、このアルゴはO（n）は、最高のソートはO（n.log2 n）で

EDIT次のようになります。私は、インデックスの配列を追加しました。 EDIT2：私は最初のインスタンスに持っていた基本的なバグを修正するために導入秒。 EDIT3：コメント：memmoveサイズ0とはせ、基本的にはNOPです。