是什么导致我的经过时间比用户时间长？

Question

我正在对一些R语句进行基准测试(详见此处),发现我的经过时间比用户时间长.

   user  system elapsed 
  7.910   7.750  53.916 

有人可以帮助我了解哪些因素(R或硬件)决定用户时间和经过时间之间的差异,以及我如何改进它？如果有帮助:我在带有4GB RAM的Macbook Air 1.7Ghz i5上运行data.table数据操作.

更新:我粗略的理解是用户时间是我的CPU处理我的工作所需的时间.经过的时间是我提交作业到获取数据的长度.处理8秒后我的电脑还需要做什么？

更新:正如评论中所建议的,我在两个data.table上运行了几次:Y,有104列(抱歉,我随着时间的推移添加了更多列),而X作为Y的子集只有3个键.以下是更新.请注意,我连续运行了这两个程序,因此内存状态应该类似.

 X<- Y[, list(Year, MemberID, Month)]

 system.time(
   {X[ , Month:= -Month]
   setkey(X,Year, MemberID, Month)
   X[,Month:=-Month]}
  )
   user  system elapsed 
  3.490   0.031   3.519 

 system.time(
 {Y[ , Month:= -Month]
  setkey(Y,Year, MemberID, Month)
  Y[,Month:=-Month]}
 )
   user  system elapsed 
  8.444   5.564  36.284 

以下是我工作区中仅有两个对象的大小(添加了逗号).:

object.size(X)
83,237,624 bytes

 object.size(Y)
2,449,521,080 bytes

谢谢

Answer 1

用户时间是计算机花在计算上的时间.系统时间是操作系统响应程序请求所花费的时间.经过的时间是这两者的总和,加上你的程序和/或操作系统必须做的"等待".重要的是要注意这些数字是花费的时间的总和.您的程序可能会计算1秒钟,然后在操作系统上等待一秒钟,然后在磁盘上等待3秒钟,并在运行时多次重复此循环.

基于您的程序占用系统时间与用户时间一样多的事实,这是一个非常IO密集的事情.从磁盘读取很多或写入磁盘很多.RAM非常快,通常几百纳秒.因此,如果所有内容都适合RAM,则经过的时间通常比用户时间略长.但是磁盘可能需要几毫秒的时间来寻找,甚至更长时间来回复数据.这比较慢了一百万.

我们已经确定你的处理器是"做东西"~8 + ~8 = ~16秒.它为另一个做了什么~54 - ~16 = ~38秒？等待硬盘驱动器向它发送它要求的数据.

UPDATE1:

马修已经提出了一些很好的观点,我正在做出我可能不应该做的假设.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上.

现在我们要做一点改变.而不是读取非阻塞的/ 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

UPDATE2:

我想我会尝试解决马修的建议,即L2高速缓存未命中可能是问题的根源.Core i7有一个64字节的缓存线.我不知道你对缓存了解多少,所以我会提供一些细节.当你从内存中请求一个值时,CPU不会得到那个值,它会得到它周围的所有64个字节.这意味着如果你以一种非常可预测的模式访问内存 - 比如说array [0],array [1],array [2]等 - 它需要一段时间来获得值0,但是然后是1,2, 3,4 ......快得多.直到你到达下一个缓存行,就是这样.如果这是一个整数数组,0会慢,1..15会很快,16会慢,17..31会很快等等.

http://software.intel.com/en-us/forums/topic/296674

为了测试这个,我做了两个程序.它们都有一个1024*1024元素的结构数组.在一种情况下,struct中有一个double,另一个中有两个double.double是8个字节长,所以在第二个程序中,我们以最坏的方式访问内存以进行缓存.第一个将很好地使用缓存.

#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:~$

这是具有大结构的程序,它们每个占用64个字节的内存,而不是8个.

#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:~$ 

第二个程序 - 设计为具有缓存未命中的程序 - 运行完全相同数量的内存访问需要五倍的时间.

另外值得注意的是,在这两种情况下,花费的所有时间都花在用户身上,而不是sys.这意味着操作系统正在计算程序必须等待程序数据的时间,而不是操作系统.鉴于这两个例子,我认为缓存未命中导致您的经过时间远远超过用户时间.

UPDATE3:

我刚刚看到你的更新,真正瘦身的桌子比普通大小的桌子快了大约10倍.这也会向我表明(正如另一个马修也说的那样)你的RAM耗尽了.

一旦您的程序尝试使用的内存超过计算机实际安装的内存,它就会开始交换到磁盘.这比程序崩溃要好,但它比RAM慢很多,并且可能导致大幅减速.

我将尝试将明天显示交换问题的示例放在一起.

UPDATE4:

好的,这是一个与前一个程序非常相似的示例程序.但现在结构是4096字节,而不是8字节.总的来说,这个程序将使用2GB内存而不是64MB内存.我也改变了一点,并确保我随机访问而不是逐个元素,这样内核就无法变得聪明并开始预测我的程序需求.缓存由硬件驱动(仅由简单的启发式驱动)但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:~$ 

它只需要cachexmisses的8倍和cache_hits的40倍.这是在一台4GB内存的计算机上.我在这个程序中使用了50%的RAM,而cache_misses使用了1.5%,cache_hits使用了0.2%.它变得非常慢,即使它没有耗尽我的电脑所有的RAM.这足够重要.

我希望这是如何诊断程序运行缓慢的问题的一个很好的入门.