ユーザー時間は、コンピューターが計算に費やした秒数です。システム時間は、オペレーティング システムがプログラムの要求に応答するのに費やした時間です。経過時間は、これら 2 つの合計に、プログラムや OS が実行しなければならなかった「待機」時間を加えたものです。これらの数値は、費やされた時間の合計であることに注意してください。プログラムは 1 秒間計算し、次に OS で 1 秒間待機し、次にディスクで 3 秒間待機し、実行中にこのサイクルを何度も繰り返す場合があります。
プログラムがユーザー時間と同じくらい多くのシステム時間を費やしたという事実に基づいて、それは非常に IO 集約的なものでした。ディスクからの読み取りが多い、またはディスクへの書き込みが多い。RAM は非常に高速で、通常は数百ナノ秒です。そのため、すべてが RAM に収まる場合、通常、経過時間はユーザー時間よりも少しだけ長くなります。ただし、ディスクがシークするのに数ミリ秒かかり、データを返すのにさらに時間がかかる場合があります。それは100万分の1遅いです。
お使いのプロセッサが ~8 + ~8 = ~ 16 秒間「処理を行っていた」と判断しました。残りの ~54 - ~16 = ~38 秒間は何をしていたのでしょうか? ハードドライブが要求したデータを送信するのを待っています。
更新1:
Matthew は、私がおそらくすべきではない仮定を行っているという優れた点を指摘していました。Adam さん、テーブルのすべての行のリストを公開したい場合 (必要なのはデータ型だけです)、何が起こっているのかをよりよく理解することができます。
ユーザー空間とカーネル空間で費やされていない時間は IO の待機に費やされている可能性が高いという私の仮定を検証するために、何もしない小さなプログラムを作成しました。
#include <stdio.h>
int main()
{
int i;
for(i = 0; i < 1000000000; i++)
{
int j, k, l, m;
j = 10;
k = i;
l = j + k;
m = j + k - i + l;
}
return 0;
}
結果のプログラムを実行して時間を計ると、次のようになります。
mike@computer:~$ time ./waste_user
real 0m4.670s
user 0m4.660s
sys 0m0.000s
mike@computer:~$
調べてみるとわかるように、プログラムは実際の作業を行っていないため、RAM にロードして実行を開始する以外にカーネルに要求することはありません。したがって、ほぼすべての「リアルタイム」時間は「ユーザー」時間として費やされます。
これで、カーネルを大量に使用する何もしないプログラム (時間を合理的に保つために反復回数を少し減らします):
#include <stdio.h>
int main()
{
FILE * random;
random = fopen("/dev/urandom", "r");
int i;
for(i = 0; i < 10000000; i++)
{
fgetc(random);
}
return 0;
}
それを実行すると、次のようなものが表示されます。
mike@computer:~$ time ./waste_sys
real 0m1.138s
user 0m0.090s
sys 0m1.040s
mike@computer:~$
ここでも、プログラムがカーネルにランダムなバイトを与えるように要求する以上のことを行っていないことは、調べてみれば簡単にわかります。/dev/urandom はエントロピーのノンブロッキング ソースです。どういう意味ですか？カーネルは疑似乱数ジェネレータを使用して、小さなテスト プログラム用の「乱数」値をすばやく生成します。つまり、カーネルは何らかの計算を行う必要がありますが、非常に迅速に戻ることができます。したがって、このプログラムはほとんどの場合、カーネルが計算するのを待ちます。これは、ほぼすべての時間が sys に費やされるという事実に反映されていることがわかります。
ここで、1 つの小さな変更を行います。ノンブロッキングの /dev/urandom から読み取る代わりに、ブロッキングしている /dev/random から読み取ります。どういう意味ですか？多くの計算は行いませんが、カーネル開発者が経験的にランダムであると判断したことがコンピューターで発生するのを待ちます。(これにはかなり時間がかかるため、反復回数もはるかに少なくなります)
#include <stdio.h>
int main()
{
FILE * random;
random = fopen("/dev/random", "r");
int i;
for(i = 0; i < 100; i++)
{
fgetc(random);
}
return 0;
}
このバージョンのプログラムを実行して時間を計測すると、次のように表示されます。
mike@computer:~$ time ./waste_io
real 0m41.451s
user 0m0.000s
sys 0m0.000s
mike@computer:~$
実行に 41 秒かかりましたが、ユーザーと実際の時間は計り知れません。何故ですか？すべての時間はカーネルで費やされましたが、アクティブな計算は行われませんでした。カーネルは何かが起こるのを待っていました。十分なエントロピーが収集されると、カーネルが復帰し、データをプログラムに送り返します。(すべての状況に応じて、コンピューターでの実行にかかる時間が大幅に短縮または大幅に短縮されることに注意してください)。user+sys と real の時間差は IO だと思います。
では、これはどういう意味ですか？私の答えが正しいことを証明するものではありません。なぜなら、あなたが自分の行動を見ている理由について他の説明があるかもしれないからです. しかし、ユーザーの計算時間、カーネルの計算時間、および私が主張しているのは IO の実行に費やされた時間の違いを示しています。
/dev/urandom と /dev/random の違いのソースは次のとおりです:
http://en.wikipedia.org/wiki//dev/random
更新 2:
おそらく L2 キャッシュ ミスが問題の根底にあるという Matthew の提案に対処しようと思いました。Core i7 には 64 バイトのキャッシュ ラインがあります。キャッシュについてどれだけ知っているかわかりませんので、詳細を説明します。メモリから値を要求すると、CPU はその 1 つの値だけを取得するのではなく、その周囲の 64 バイトすべてを取得します。つまり、配列 [0]、配列 [1]、配列 [2] など、非常に予測可能なパターンでメモリにアクセスしている場合、値 0 を取得するのに時間がかかりますが、その後 1、2、 3、4... ははるかに高速です。つまり、次のキャッシュ ラインに到達するまでです。これが int の配列である場合、0 は遅く、1..15 は速く、16 は遅く、17..31 は速くなります。
http://software.intel.com/en-us/forums/topic/296674
これをテストするために、2 つのプログラムを作成しました。どちらも 1024*1024 要素の構造体の配列を持っています。構造体に 1 つの double が含まれている場合もあれば、8 つの double が含まれている場合もあります。double は 8 バイトの長さであるため、2 番目のプログラムでは、キャッシュに対して可能な限り最悪の方法でメモリにアクセスしています。最初のものは、キャッシュを適切に使用できるようになります。
#include <stdio.h>
#include <stdlib.h>
#define MANY_MEGS 1048576
typedef struct {
double a;
} PartialLine;
int main()
{
int i, j;
PartialLine* many_lines;
int total_bytes = MANY_MEGS * sizeof(PartialLine);
printf("Striding through %d total bytes, %d bytes at a time\n", total_bytes, sizeof(PartialLine));
many_lines = (PartialLine*) malloc(total_bytes);
PartialLine line;
double x;
for(i = 0; i < 300; i++)
{
for(j = 0; j < MANY_MEGS; j++)
{
line = many_lines[j];
x = line.a;
}
}
return 0;
}
このプログラムを実行すると、次の出力が表示されます。
mike@computer:~$ time ./cache_hits
Striding through 8388608 total bytes, 8 bytes at a time
real 0m3.194s
user 0m3.140s
sys 0m0.016s
mike@computer:~$
これは大きな構造体を含むプログラムです。それぞれが 8 バイトではなく 64 バイトのメモリを占有します。
#include <stdio.h>
#include <stdlib.h>
#define MANY_MEGS 1048576
typedef struct {
double a, b, c, d, e, f, g, h;
} WholeLine;
int main()
{
int i, j;
WholeLine* many_lines;
int total_bytes = MANY_MEGS * sizeof(WholeLine);
printf("Striding through %d total bytes, %d bytes at a time\n", total_bytes, sizeof(WholeLine));
many_lines = (WholeLine*) malloc(total_bytes);
WholeLine line;
double x;
for(i = 0; i < 300; i++)
{
for(j = 0; j < MANY_MEGS; j++)
{
line = many_lines[j];
x = line.a;
}
}
return 0;
}
実行すると、次のように表示されます。
mike@computer:~$ time ./cache_misses
Striding through 67108864 total bytes, 64 bytes at a time
real 0m14.367s
user 0m14.245s
sys 0m0.088s
mike@computer:~$
2 番目のプログラム (キャッシュ ミスが発生するように設計されたプログラム) は、まったく同じ回数のメモリ アクセスを実行するのに 5 倍の時間がかかりました。
また、注目に値するのは、どちらの場合も、費やされた時間はすべて、sys ではなくユーザーで費やされたことです。これは、OS が、オペレーティング システムに対してではなく、プログラムに対してデータを待機する必要がある時間をカウントしていることを意味します。これら 2 つの例を考えると、キャッシュ ミスによって経過時間がユーザー時間より大幅に長くなる可能性は低いと思います。
更新3:
本当にスリム化されたテーブルが通常サイズのテーブルよりも約 10 倍高速に実行されたというあなたの更新を見たところです。それもまた、（別のマシューも言ったように）RAMが不足していることを示しています。
プログラムが、コンピュータに実際にインストールされているよりも多くのメモリを使用しようとすると、ディスクへのスワップが開始されます。これは、プログラムがクラッシュするよりはましですが、RAM よりもはるかに遅く、大幅な速度低下を引き起こす可能性があります。
明日、スワップの問題を示す例をまとめてみます。
更新 4:
さて、これは前のものと非常によく似たサンプルプログラムです。しかし、構造体は 8 バイトではなく 4096 バイトになりました。全体として、このプログラムは 64MB ではなく 2GB のメモリを使用します。また、少し変更を加えて、要素ごとではなくランダムにアクセスするようにしています。これにより、カーネルがスマートになり、プログラムのニーズを予測し始めることができなくなります。キャッシュはハードウェアによって駆動されます (単純なヒューリスティックのみによって駆動されます) が、kswapd (カーネル スワップ デーモン) がキャッシュよりも大幅にスマートになる可能性は十分にあります。
#include <stdio.h>
#include <stdlib.h>
typedef struct {
double numbers[512];
} WholePage;
int main()
{
int memory_ops = 1024*1024;
int total_memory = memory_ops / 2;
int num_chunks = 8;
int chunk_bytes = total_memory / num_chunks * sizeof(WholePage);
int i, j, k, l;
printf("Bouncing through %u MB, %d bytes at a time\n", chunk_bytes/1024*num_chunks/1024, sizeof(WholePage));
WholePage* many_pages[num_chunks];
for(i = 0; i < num_chunks; i++)
{
many_pages[i] = (WholePage*) malloc(chunk_bytes);
if(many_pages[i] == 0){ exit(1); }
}
WholePage* page_list;
WholePage* page;
double x;
for(i = 0; i < 300*memory_ops; i++)
{
j = rand() % num_chunks;
k = rand() % (total_memory / num_chunks);
l = rand() % 512;
page_list = many_pages[j];
page = page_list + k;
x = page->numbers[l];
}
return 0;
}
私が cache_hits から cache_misses に呼び出したプログラムから、メモリのサイズが 8 倍に増加し、実行時間が 5 倍に増加したことがわかりました。このプログラムを実行すると、何が表示されると思いますか? cache_misses の 32 倍のメモリを使用しますが、同じ数のメモリ アクセスがあります。
mike@computer:~$ time ./page_misses
Bouncing through 2048 MB, 4096 bytes at a time
real 2m1.327s
user 1m56.483s
sys 0m0.588s
mike@computer:~$
cache_misses の 8 倍、cache_hits の 40 倍の時間がかかりました。そして、これは4GBのRAMを搭載したコンピューター上にあります。このプログラムでは RAM の 50% を使用しましたが、cache_misses では 1.5%、cache_hits では 0.2% を使用しました。私のコンピューターが持っているすべてのRAMを使い果たしていなくても、かなり遅くなりました。意味のあるもので十分でした。
これが、実行速度の遅いプログラムの問題を診断する方法についての適切な入門書になることを願っています。