连接两个字符串时,为什么Python比C更快？

Question

目前我想比较Python和C的速度,当它们用于做字符串时.我认为C应该提供比Python更好的性能; 但是,我得到了相反的结果.

这是C程序:

#include <unistd.h>
#include <sys/time.h>

#define L (100*1024)

char s[L+1024];
char c[2*L+1024];

double time_diff( struct timeval et, struct timeval st )
{
    return 1e-6*((et.tv_sec - st.tv_sec)*1000000 + (et.tv_usec - st.tv_usec ));
}

int foo()
{
    strcpy(c,s);
    strcat(c+L,s);
    return 0;
}

int main()
{
    struct timeval st;
    struct timeval et;
    int i;
    //printf("s:%x\nc:%x\n", s,c);

    //printf("s=%d c=%d\n", strlen(s), strlen(c));
    memset(s, '1', L);
    //printf("s=%d c=%d\n", strlen(s), strlen(c));
    foo();
    //printf("s=%d c=%d\n", strlen(s), strlen(c));
    //s[1024*100-1]=0;

    gettimeofday(&st,NULL);
    for( i = 0 ; i < 1000; i++ ) foo();
    gettimeofday(&et,NULL);

    printf("%f\n", time_diff(et,st));
    return 0;
}

这是Python之一:

import time

s = '1'*102400
def foo():
    c = s + s
    #assert( len(c) == 204800 )

st = time.time()
for x in xrange(1000):
    foo()
et = time.time()

print (et-st)

我得到了什么:

root@xkqeacwf:~/lab/wfaster# python cp100k.py 
0.027932882309
root@xkqeacwf:~/lab/wfaster# gcc cp100k.c
root@xkqeacwf:~/lab/wfaster# ./a.out 
0.061820

那有意义吗？或者我只是犯了任何愚蠢的错误？

Answer 1

累积评论(主要来自我)转换成答案:

• 如果你使用你对字符串长度的知识并使用memmove()或memcpy()代替strcpy()和strcat()？会发生什么？(我注意到strcat()可以替换为strcpy()结果没有区别 - 检查时间可能会很有趣.)此外,您没有包含<string.h>(或<stdio.h>)因此您缺少<string.h>可能提供的任何优化!

Marcus:是的,比Python memmove()更快strcpy(),速度更快,但为什么呢？一次memmove()做一个字宽复制吗？

• 是; 在64位机器上,对于精确对齐的数据,它可以一次移动64位而不是一次移动8位; 一台32位的机器,一次可能是32位.它在每次迭代(计数)中只有一个更简单的测试,而不是('计数或是空字节')'这是一个空字节'.

马库斯:但是memmove()在我制作之后仍然运作良好L=L-13,然后sizeof(s)放弃L+1024-13.我的机器有一个sizeof(int)==4.

• 代码memmove()是高度优化的汇编程序,可能是内联的(没有函数调用开销,但对于100KiB的数据,函数调用开销很小).好处来自更大的动作和更简单的循环条件.

Marcus: Python memmove()也是如此,或者是什么神奇的东西？

• 我没有看过Python源代码,但实际上它确实跟踪了它的字符串长度(它们是空终止的,但Python总是知道字符串的活动部分有多长).知道这个长度允许Python使用memmove()或memcpy()(memmove()即使源和目标重叠,这种差异也memcpy()能正常工作; 如果它们重叠,则没有义务正常工作).他们有可能比memmove/memcpy现有的更快.

我修改了C代码生成我的机器(Mac OS X的10.7.4,8吉布1333 MHz的内存,2.3 GHz的英特尔酷睿i7,GCC 4.7.1)对我更稳定的时序,并比较strcpy()和strcat()VS memcpy()VS memmove().请注意,我将循环计数从1000增加到10000以提高计时的稳定性,并且我重复整个测试(所有三种机制)10次.可以说,定时循环计数应该增加另一个因子5-10,以便定时超过一秒.

#include <stdio.h>
#include <string.h>
#include <unistd.h>
#include <sys/time.h>

#define L (100*1024)

char s[L+1024];
char c[2*L+1024];

static double time_diff( struct timeval et, struct timeval st )
{
    return 1e-6*((et.tv_sec - st.tv_sec)*1000000 + (et.tv_usec - st.tv_usec ));
}

static int foo(void)
{
    strcpy(c,s);
    strcat(c+L,s);
    return 0;
}

static int bar(void)
{
    memcpy(c + 0, s, L);
    memcpy(c + L, s, L);
    return 0;
}

static int baz(void)
{
    memmove(c + 0, s, L);
    memmove(c + L, s, L);
    return 0;
}

static void timer(void)
{
    struct timeval st;
    struct timeval et;
    int i;

    memset(s, '1', L);
    foo();

    gettimeofday(&st,NULL);
    for( i = 0 ; i < 10000; i++ )
        foo();
    gettimeofday(&et,NULL);
    printf("foo: %f\n", time_diff(et,st));

    gettimeofday(&st,NULL);
    for( i = 0 ; i < 10000; i++ )
        bar();
    gettimeofday(&et,NULL);
    printf("bar: %f\n", time_diff(et,st));

    gettimeofday(&st,NULL);
    for( i = 0 ; i < 10000; i++ )
        baz();
    gettimeofday(&et,NULL);
    printf("baz: %f\n", time_diff(et,st));
}

int main(void)
{
    for (int i = 0; i < 10; i++)
        timer();
    return 0;
}

编译时不会发出警告:

gcc -O3 -g -std=c99 -Wall -Wextra -Wmissing-prototypes -Wstrict-prototypes \
    -Wold-style-definition cp100k.c -o cp100k

我得到的时间是:

foo: 1.781506
bar: 0.155201
baz: 0.144501
foo: 1.276882
bar: 0.187883
baz: 0.191538
foo: 1.090962
bar: 0.179188
baz: 0.183671
foo: 1.898331
bar: 0.142374
baz: 0.140329
foo: 1.516326
bar: 0.146018
baz: 0.144458
foo: 1.245074
bar: 0.180004
baz: 0.181697
foo: 1.635782
bar: 0.136308
baz: 0.139375
foo: 1.542530
bar: 0.138344
baz: 0.136546
foo: 1.646373
bar: 0.185739
baz: 0.194672
foo: 1.284208
bar: 0.145161
baz: 0.205196

有点奇怪的是,如果我放弃"没有警告"并省略<string.h>和<stdio.h>标题,就像在原始发布的代码中一样,我得到的时间是:

foo: 1.432378
bar: 0.123245
baz: 0.120716
foo: 1.149614
bar: 0.186661
baz: 0.204024
foo: 1.529690
bar: 0.104873
baz: 0.105964
foo: 1.356727
bar: 0.150993
baz: 0.135393
foo: 0.945457
bar: 0.173606
baz: 0.170719
foo: 1.768005
bar: 0.136830
baz: 0.124262
foo: 1.457069
bar: 0.130019
baz: 0.126566
foo: 1.084092
bar: 0.173160
baz: 0.189040
foo: 1.742892
bar: 0.120824
baz: 0.124772
foo: 1.465636
bar: 0.136625
baz: 0.139923

考虑到这些结果,它似乎比"更干净"的代码更快,虽然我没有对两组数据进行学生t检验,并且时间具有非常大的可变性(但我确实有像Boinc运行的东西后台的8个流程).效果似乎是在代码的早期版本中,当它只是更明显strcpy(),并strcat()进行了测试.我没有解释,如果它是真正的效果!

通过跟帖MVDS

由于问题已经结束,我无法正确回答.在几乎没有做任何事情的Mac上,我得到了这些时间:

(带标题)

foo: 1.694667 bar: 0.300041 baz: 0.301693
foo: 1.696361 bar: 0.305267 baz: 0.298918
foo: 1.708898 bar: 0.299006 baz: 0.299327
foo: 1.696909 bar: 0.299919 baz: 0.300499
foo: 1.696582 bar: 0.300021 baz: 0.299775

(没有标题,忽略警告)

foo: 1.185880 bar: 0.300287 baz: 0.300483
foo: 1.120522 bar: 0.299585 baz: 0.301144
foo: 1.122017 bar: 0.299476 baz: 0.299724
foo: 1.124904 bar: 0.301635 baz: 0.300230
foo: 1.120719 bar: 0.300118 baz: 0.299673

预处理器输出(-E标志)显示包含标头转换strcpy为内置调用,如:

((__builtin_object_size (c, 0) != (size_t) -1) ? __builtin___strcpy_chk (c, s, __builtin_object_size (c, 2 > 1)) : __inline_strcpy_chk (c, s));
((__builtin_object_size (c+(100*1024), 0) != (size_t) -1) ? __builtin___strcat_chk (c+(100*1024), s, __builtin_object_size (c+(100*1024), 2 > 1)) : __inline_strcat_chk (c+(100*1024), s));

所以strcpy的libc版本优于gcc内置版.(使用gdb它很容易验证,如果包含标题,断点strcpy确实不会在strcpy()通话中断开)

在Linux(Debian 5.0.9,amd64)上,差异似乎可以忽略不计.生成的程序集(-S标志)仅在包含的调试信息中有所不同.

Answer 2

我相信这样做的原因是Python字符串不是以null结尾的.

在Python中,字符串长度与字符串一起存储,允许它在连接字符串时跳过strcat()使用的隐式strlen().

添加字符串连接直接在C中实现Python的事实可能就是原因.

编辑:嗯,现在我实际上看了C代码,看到它使用静态缓冲区,我也很神秘,因为我没有看到Python如何避免动态分配,这应该慢得多......