Почему Python быстрее, чем C при конкатенации двух строк?

Ответ 1

Накопленные комментарии (в основном от меня) преобразуются в ответ:

• Что произойдет, если вы используете свои знания о длинах строк и используете memmove() или memcpy() вместо strcpy() и strcat()? (Я отмечаю, что strcat() можно заменить на strcpy() без разницы в результатах - возможно, было бы интересно проверить время.) Кроме того, вы не включили <string.h> (или <stdio.h>), не хватает каких-либо оптимизаций, которые <string.h> может обеспечить!

Marcus: Да, memmove() быстрее, чем strcpy() и быстрее, чем Python, но почему? Выполняет ли memmove() копию ширины слова?

• Да; на 64-битной машине для хорошо выровненных данных он может перемещать 64-битные данные за раз, а не по 8 бит за раз; 32-битная машина, вероятно, 32 бита за раз. Он также имеет только один более простой тест для каждой итерации (подсчета), а не ('count или это нулевой байт)' - это нулевой байт.

Marcus: Но 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 GiB 1333 МГц RAM, 2,3 ГГц Intel Core 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-Test для учащихся двух наборов данных, а тайминги имеют очень существенную изменчивость (но у меня есть вещи как 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));

Итак, версия libc libc превосходит gcc builtin. (используя gdb, легко проверить, что точка останова на strcpy действительно не разбивается на вызов strcpy(), если включены заголовки)

В Linux (Debian 5.0.9, amd64) различия кажутся незначительными. Сгенерированная сборка (флаг -S) отличается только отладочной информацией, переносимой включенными.

Ответ 2

Я считаю, что причиной этого является то, что строки Python не заканчиваются на нуль.

в Python длина строки сохраняется вместе со строкой, позволяя ей пропускать неявный strlen(), используемый strcat() при конкатенации строк.

Добавление к тому факту, что конкатенация строк реализована непосредственно в C для Python, вероятно, является причиной.

Edit: ну, теперь, когда я действительно смотрю на код C и вижу, что он использует статические буферы, я тоже озадачен, так как не вижу, как Python может избежать динамических распределений, которые должны быть намного медленнее..