Saturday, July 11, 2009

Сказ о том, как Python С++ обогнал

Я всегда защищаю С++, когда приверженцы других языков ругают его за невыразительный синтаксис, чрезмерную сложность или раздутость, потому что, по-моему мнению, на С++ можно писать красиво, и особенно в этом помогают различные высокоуровневые конструкции из стандартной библиотеки.
В одном из споров в c_plus_plus@c.j.r речь зашла о том, какой же из языков лучше - простой С или всё же С++? В качестве одного из аргументов я предложил провести эксперимент - сколько времени понадобится для решения простой задачи: из stdin считываются строки текста, и после этого в обратном порядке записываются в stdout, т.е., первая строка в stdin становится последней в stdout. Длина строк не ограничена, поэтому для решения ее на С понадобится выделять и перевыделять память, от этого код на С разбухнет, что станет наглядной демонстрацией превосходства высокоуровневых конструкций С++. Более того, я предположил, что код на С++ может быть даже производительней кода на С, написанного без дополнительного профилирования - ведь контейнеры С++ выделяют память так, чтобы reallocate происходил реже. Пример кода на С++, написан за пару минут для демонстрации:

#include <iostream>
#include <string>
#include <vector>

int main() {
std::vector<std::string> v;
while(std::cin)
{
std::string s;
std::getline(std::cin,s);
v.push_back(s);
}
for (std::vector<std::string>::reverse_iterator it = v.rbegin();it!=v.rend();++it)
{
std::cout<<*it<<"\n";
}
}
Как видите, код далеко не оптимален, однако мне хотелось показать, что даже такое решение лучше, чем код на С.
Тут же захотелось проверить, а как другие языки справятся с этой задачей. Например,однострочник на Ruby:
$stdin.readlines.reverse.join.display
Когда я протестировал его на небольших файлах, С++ решение оказалось быстрее решения на Ruby в десятки раз, что меня нисколько не удивило. Однако для чистоты эксперимента я решил увеличить размер файла. Я сгенерировал файл в 100 строк общим размером ~600mb(исходник на Python):
open("/tmp/z.txt",'w').write((''.join(map(str,xrange(1000000)))+'\n')*100
Результаты тестирования на нём были просто поразительны:
ruby 1.8.6 (2009-06-08 patchlevel 369) [i686-linux]:
real 0m9.841s
user 0m0.849s
sys 0m7.206s

gcc (GCC) 4.1.2 (Gentoo 4.1.2 p1.3):
real 0m51.902s
user 0m48.682s
sys 0m1.429s
Я тут же решил проверить решение на Python:
import sys
sys.stdout.write('\n'.join(reversed(sys.stdin.readlines())))
Результаты:
Python 2.6.2
real 0m4.855s
user 0m0.913s
sys 0m1.233s
Т.е., еще быстрее, чем ruby (что уже не удивительно ;) ). Просмотрев код на С++, я добавил простейшую оптимизацию, которую изначально добавлять не хотел, чтобы код совсем не был похож на С. Я добавил хранение в векторе указателей, а не строк, что должно было убрать ненужное копирование:
#include <iostream>
#include <string>
#include <vector>

int main() {
std::vector<std::string*> v;
while(std::cin)
{
std::string * s = new std::string();
std::getline(std::cin,*s);
v.push_back(s);
}
for (std::vector<std::string*>::reverse_iterator it = v.rbegin();it!=v.rend();++it)
{
std::cout<<*(*it)<<"\n";
delete *it;
}
}
Но результат всё так же не вдохновляет:
real 0m46.444s
user 0m43.462s
sys 0m1.379s
Назначив ответственным за тормоза std::string, я попытался переписать всё на QString из Qt, которые, по слухам, умеют copy-on-write и вообще быстрые. Наивный код:
#include <iostream>
#include <QtCore/qstring.h>
#include <QtCore/qlist.h>
#include <QtCore/qtextstream.h>
#include <vector>

int main() {
QList<QString> v;
QTextStream st (stdin);
QTextStream sto (stdout);
while(!st.atEnd())
{
v.push_back(st.readLine());
}
QListIterator<QString> it(v);
it.toBack ();
while (it.hasPrevious ())
sto<<it.previous()<<"\n";
}
Однако это решение пожрало все 2 гигабайта моей оперативной памяти и я его остановил, попросив Qt-шников с c_plus_plus@c.j.r помочь с оптимизацией. После нескольких минут получился вот такой код, который использовал уже 1.4 гигабайта оперативки:
#include <iostream>
#include <QtCore/qstring.h>
#include <QtCore/qlist.h>
#include <QtCore/qtextstream.h>

int main ()
{
QList<QByteArray> v;
QTextStream st (stdin);
QTextStream sto (stdout);
int line = 0;
while (!st.atEnd ())
{
std::cerr << "Reading line... " << line++ << std::endl;
v.push_back (qCompress (st.readLine ().toUtf8 (), 9));
}
QListIterator<QByteArray> it (v);
it.toBack ();
while (it.hasPrevious ())
{
std::cerr << "Writing line... " << std::endl;
sto << qUncompress (it.previous ()) << "\n";
sto.flush ();
}
}
Однако он работал еще медленнее, чем на стандартных строках - более двух минут. Для чистоты эксперимента я также написал вариант на Python, который не использовал стандартные join и reversed, а был более похож на код на С++:
import sys
s = sys.stdin.readlines()
for x in xrange(len(s)-1,-1,-1):
sys.stdout.write(s[x]+'\n')
Его результаты:
real 0m2.198s
user 0m0.884s
sys 0m1.190s

Выводы

Если не учитывать опыты с Qt(всё равно ведь хороших результатов добиться не удалось), ни в одном из языков не было использовано каких-либо особых оптимизаций, напротив, были использованы те конструкции высокого уровня, которые предлагает сам язык. И удивительно, что программы на Python и Ruby смогли с большим отрывом обогнать аналогичную программу на С++. Я сам еще не знаю причину этого, и я был бы очень рад, если бы кто-то смог прогнать аналогичные тесты у себя на машине. Однако вне зависимости от причины, такой результат явственно говорит одно - нельзя безоговорочно верить в то, что С++ быстрее интерпретируемых языков, особенно если простейшие высокоуровневые конструкции в них, такие как строки, работают лучше.

P.S.

Я не старался создать идеальные условия для тестирования и не прогонял тесты сотни раз, чтобы получить идеальный результат. Достаточно всего-лишь заметить, что в этом синтетическом тесте Python был в 2-5 раз быстрее Ruby, а Ruby была в 4-5 раз быстрее С++. Спасибо за внимание!

Частичная реабилитация(update)

#include <iostream>
#include <fstream>
#include <string>
#include <vector>

int main() {
std::ifstream fin("/dev/stdin");
std::vector<std::string*> v;
while(fin)
{
std::string * s = new std::string();
std::getline(fin,*s);
v.push_back(s);
}
for (std::vector<std::string*>::reverse_iterator it = v.rbegin();it!=v.rend();++it)
{
std::cout<<*(*it)<<"\n";
delete *it;
}
}

real 0m1.783s
user 0m0.656s
sys 0m1.070s

Т.е., тормозил std::cin. Естественно, это не оправдание, поэтому реабилитация только частичная. Вывод: tools don't kill software. people kill software.

37 comments:

  1. Самая большая ошибка всех священных войн: сравнивать не языки, а их конкретные реализации (то есть путать понятия Класс и Объект). Языки Python, Ruby и С++ имеют несколько различных реализаций (интерпретаторов/компиляторов), но все предпочитают выбирать конкретные реализации и думают, что сравнивают сами языки.

    PS. Ни один язык программирования не имеет такого понятия как "скорость выполнения".

    ReplyDelete
  2. @Rubynovich Вы правы, однако я сравниваю именно языки, в разрезе программных продуктов, которые с их помощью можно получить. Более того, если бы я получил результаты близкие, тогда Ваше замечание было бы более уместным, однако мои результаты скорее свидетельствуют о глобальных проблемах в С++(или gcc, я был бы очень рад, если бы кто-то указал мне реализацию компилятора/STL, на которой такого ужаса бы не было). В общем, ИМХО, нельзя разделять язык и его реализацию - ведь очень часто хорошие языки просто нельзя реализовать так, чтобы они работали быстро.

    ReplyDelete
  3. хм, уверен что вы где то лукавите!

    проделал то же самое, создал файл по такому же примеру как и у вас, запустил такой же код на питоне и руби, так оба отожрали по 1гб оперативки и были незамедлительно убиты, а вот утилиты из coreutils (Си) выполнили поставленную задачу за 19 секунд:

    $time cat z.txt | tac 2>/dev/null
    real 0m19.503s
    user 0m0.132s
    sys 0m2.140s

    ReplyDelete
  4. @Анонимный
    Не лукавлю. Я смотрел потребление памяти в top, у меня вроде Python не зашкаливал, но так как отрабатывал он быстро, то я мог не заметить. Попробуйте на файлах чуть меньшего размера. И какие у вас версии Python/Ruby?

    ReplyDelete
  5. tsarev@developer:~$ ls -al -h | grep z.txt
    -rw-r--r-- 1 tsarev tsarev 562M 2009-07-11 04:25 z.txt
    tsarev@developer:~$ cat reverse.py
    #!/usr/bin/python
    import sys
    sys.stdout.write('\n'.join(reversed(sys.stdin.readlines())))
    tsarev@developer:~$ cat z.txt | ./reverse.py > output
    tsarev@developer:~$ cat z.txt | ./reverse.py > /dev/null
    tsarev@developer:~$ time(cat z.txt | ./reverse.py > output)

    real 0m9.164s
    user 0m0.864s
    sys 0m3.128s
    tsarev@developer:~$ time(cat z.txt | ./reverse.py > /dev/null)

    real 0m2.263s
    user 0m0.896s
    sys 0m1.320s

    ReplyDelete
  6. tsarev@developer:~$ cat reverse.cpp
    #include <ostream>
    #include <iterator>
    #include <string>
    #include <vector>
    #include <algorithm>

    int main()
    {
    std::vector<std::string> buffer;
    std::copy( (std::istream_iterator<std::string>(std::cin)), (std::istream_iterator<std::string>()), std::back_inserter(buffer) );
    std::copy( buffer.rbegin(), buffer.rend(), (std::ostream_iterator<std::string>(std::cout)) );
    return 0;
    }
    tsarev@developer:~$ g++ -O3 reverse.cpp -o test_reverse_c++
    tsarev@developer:~$ time (cat z.txt | ./test_reverse_c++ > output)

    real 0m41.865s
    user 0m30.214s
    sys 0m3.564s
    tsarev@developer:~$ time (cat z.txt | ./test_reverse_c++ > /dev/null)

    real 0m32.497s
    user 0m30.334s
    sys 0m1.984s
    tsarev@developer:~$

    ReplyDelete
  7. @zabivator
    Вот приблизительно такой код на С++ почему-то все называют "невыразительным, чрезмерно сложным и раздутым". Приблизительно поэтому я сделал императивно, циклами.

    ReplyDelete
  8. Я подумал над вашим примером, и кажется нашёл объяснение
    Попробуем протестировать прямое копирование
    tsarev@developer:~$ time (cat z.txt > output)

    real 0m7.113s
    user 0m0.028s
    sys 0m2.160s
    tsarev@developer:~$ nano reverse.py
    tsarev@developer:~$ cat reverse.py
    #!/usr/bin/python
    import sys
    sys.stdout.write('\n'.join(sys.stdin.readlines()))
    tsarev@developer:~$ time (cat z.txt | ./reverse.py > output)

    real 0m9.312s
    user 0m0.940s
    sys 0m3.092s
    tsarev@developer:~$ nano reverse.cpp
    tsarev@developer:~$ cat reverse.cpp
    #include <iostream>
    #include <iterator>
    #include <string>
    #include <deque>
    #include <algorithm>

    int main()
    {
    typedef std::string T;
    std::copy( (std::istream_iterator<T>(std::cin)), (std::istream_iterator<T>()), (std::ostream_iterator<T>(std::cout)) );
    return 0;
    }
    tsarev@developer:~$ g++ -O3 reverse.cpp -o test_reverse_c++
    tsarev@developer:~$ time (cat z.txt | ./test_reverse_c++ > output)

    real 0m34.211s
    user 0m30.326s
    sys 0m2.248s
    tsarev@developer:~$

    С++ вынужден копировать данные на heap
    python & bash используют прямое перенаправление потоков.
    В этом и порылась собака.
    К сожалению, это фокус, а не реальный тест.

    ReplyDelete
  9. >>> Вот приблизительно такой код на С++ почему-то все называют "невыразительным, чрезмерно сложным и раздутым". Приблизительно поэтому я сделал императивно, циклами. <<<

    Эти люди НЕ ЗНАЮТ С++
    Уж поверьте
    http://www.brainbench.com/content/transcript/topicdetail.do?testid=9017670

    Это мой результат на brainbench
    Test: C++
    Date: 04-фев-2008
    Score: 4,84
    Correct/Total: (38/40)

    Я работаю с С++ семь с половиной лет.
    Участвую в разработке СУБД QD
    http://zabivator.livejournal.com/188396.html - обо мне
    http://zabivator.livejournal.com/335739.html - клиентах QD

    На С++ и способам программирования на нём, оптимизациях я собаку съел.
    Нету способа сделать быстрее С++ при одинаковых алгоритмах и одинаковом использовании нативного API.
    О читаемости кода и так далее - я молчу.
    Но данный пример непоказателен - тестируем разные механизмы ОС.

    zabivator.livejournal.com/336001.html - это пример реального теста. Ocaml vs C++.
    И я делаю вывод в пользу Ocaml. Хоть С++ и быстрее

    ReplyDelete
  10. Панове, з якого перепою ви користуєтеся для такої задачі std::vector? Вам треба довільний доступ до рядків по номеру?
    Переміряйте все з std::list.

    ReplyDelete
  11. Питон, как и руби, используют буферизацию данных при их считывании из потоков. C++ тормозит из-за того, что он, скорее всего, читает данные из файла по одному байту, что ОЧЕНЬ долго. Более высокоуровневые языки обычно поступают иначе - читают, скажем, по 8кб, а затем разбирают строку уже в памяти.

    ReplyDelete
  12. sakhnik
    На самом деле, использовать std::vector для именно этой задачи (сравнения языков программирования) довольно логично, т.к. в языках типа питона массивы обычно представляются аналогами именно C++-ных векторов.

    ReplyDelete
  13. А теперь попробуй Python 3.1 (или хотя бы 3.0, короче py3k), который мегаоптимизирован по сравнению с 2.x :)

    ReplyDelete
  14. @zabivator
    > Эти люди НЕ ЗНАЮТ С++
    Ну, вообще говоря, вы считаете, что i/ostream_iterators выглядят красиво? Я во многом согласен с теми, кто ругает С++ - можно было сделать куда красивее, хоть и при этом не считаю, что С++ нечитаем.
    >С++ вынужден копировать данные на heap
    >python & bash используют прямое перенаправление >потоков.
    >В этом и порылась собака.
    >К сожалению, это фокус, а не реальный тест.
    Python и bash так перенаправляют потоки, что они даже переворачиваются? Обратите внимание на второй пример, добавьте туда "sys.stderr.write(str(sum(map(len,s))))", чтобы убедиться, что Python всё считал в память. Так что я всё еще думаю, что проблема с C++ строками.
    P.S. Не используйте cat!!! Используйте "<"
    P.P.S. Не нужно давить авторитетом и результатами brainbench. Лично мне не нравится такое, не уверен, что это вообще кому-нибудь нравится.

    @sakhnik
    std::vector для цієї задачі по стандарту повинен працювати так саме швидко, як і std::list - ми ж додаємо лише в кінець вектору.

    ReplyDelete
  15. @[lol]2Fast4U
    Py3k еще рановато использовать. Боевой питон сейчас - 2.6. Если хотите - можете попробовать сами.

    ReplyDelete
  16. @FX Poster,
    Видимо, вы правы и я зря грешу на строки. Скорее всего дело как раз в небуфферизованном std::cin, ибо ifstream работает куда лучше.

    @zabivator
    Да, забыл сказать. Ваш вариант с i/ostream_iterators еще и неправильный. Он переворачивает не строки, а "слова".

    ReplyDelete
  17. ifstream, кстати, тоже небезгрешен. :) В ходе работы пришлось реализовывать бд, которая бы хранила данные на диске. И самый эффективный способ чтения - это читать данные в память как минимум по 8-16мб, а затем их уже в памяти обрабатывать. :)

    Кстати говоря, для считывания/записи больших объемов данных лучше использовать сишные IO-библиотеки (fopen, fread, fwrite, fclose), т.к. std::*stream все-таки сильно медленнее получается. :)

    ReplyDelete
  18. http://artlung.com/smorgasborg/Invention_of_Cplusplus.shtml

    ReplyDelete
  19. @FX Poster
    Ну, естественно, если нужно шустро работать, то в любом случае лучше использовать С. fstream - всего лишь более высокая штука с достаточной производительностью.
    @Vsevolod
    Данный fake здесь не уместен :)

    ReplyDelete
  20. FX… Дідько, мені не приходять повідомлення про нові коментарі.
    Ніякої гарантії, що python чи будь-який інший інтерпретатор використовує суцільний кусок пам’яті для масива. Подумайте тільки, заради неперервності С++ копіює весь масив щоразу, коли виділяє додаткову пам’ять. Навіть std::deque краще впорається із цим, дозволяючи при цьому довільний доступ (привіт мотузкам, якщо хто про них чув!).
    Словом, хлопці, занадто далекоглядні висновки ви тут робите.

    ReplyDelete
  21. @sakhnik
    З якої це радості С++ буде копіювати увесь масив? У std::vector дуже непогано push_back працює, я ж вже казав. Та й подивіться, там видно, що тормозить - це був std::cin, а не вектори.

    ReplyDelete
  22. sakhnik
    Лень ставить украинский язык...

    Гарантий нет, согласен. Есть реализация того же питона. Не думаю, что в руби для массивов применяется список - скорее всего это тоже вектор, а искать неохота.

    Насчет копирования и выделения дополнительной памяти - а так ли часто происходят эти действия? Для создания массива длинны n из пустого массива будет произведено меньше log2(n) копирований.
    К тому же - память все равно прийдется копировать и перевыделять для хранения самих строк. Так что я не думаю, что от использования std::list вместо вектора здесь вообще была бы хоть какая-нибудь ощутимая польза.

    ReplyDelete
  23. >>> Так что я не думаю, что от использования std::list вместо вектора здесь вообще была бы хоть какая-нибудь ощутимая польза. <<<
    Файл ~600 метров, в нём 100 строк - каждая 6 мегабайт.
    Всё-таки это изнасилование аллокатора

    ReplyDelete
  24. IMHO все дело тормозов c++ а этом приемере в том что память для string очень монго раз перераспределяется (особенно на длинных строках)

    Было-бы интересно глянуть на результаты если перенести "std:stirng s;" за пределы while (что-бы использовался один буфер), а если что-нить более высокоуровневое то с boost:tokenizer

    ReplyDelete
  25. @Vitaliy и @all: Вроде как уже разобрались, в чём была проблема. На лицо неоспоримый факт - решение задачи вполне стандартными и рекомендуемыми средствами на С++ может быть куда тормознее, чем аналогичное решение стандартными средствами на других языках. Выводы делайте сами, я не буду навязывать свою точку зрения.

    ReplyDelete
  26. Вместо указателей я бы использовал std::swap, что есть стандартный и рекомендуемый механизм для обмена "тяжёлыми" объектами.

    ReplyDelete
  27. Удивило, что человек, знающий про оптимизацию все, и пишущий на с++ целых 7 лет, использует istream_iterator вместо istreambuf_iterator. А ведь последний не буферизует ввод, и быстродействие в различных реализациях STL может достигать разницы в 40%. Попробуйте этот вариант, если интересно

    ReplyDelete
  28. Простое добавление в самый первый c++ вариант строчки std::ios_base::sync_with_stdio(0); в разы уменьшает время выполнения.

    На моей машине без этой строчки:
    real 1m19.459s
    user 1m5.628s
    sys 0m2.696s

    С ней:
    real 0m28.507s
    user 0m1.332s
    sys 0m1.928s

    ReplyDelete
  29. 28 секунд - не две секунды ;)

    ReplyDelete
  30. Последний код (из частичная реабилитация) на моей машине (два раза на всякий случай):

    real 0m46.791s
    user 0m1.384s
    sys 0m1.784s

    real 0m48.877s
    user 0m1.252s
    sys 0m1.788s

    ReplyDelete
  31. Странно. А просто из файла если? Что за ось, компилятор, STL?

    ReplyDelete
  32. Ubunutu 8.04, gcc version 4.2.4 (Ubuntu 4.2.4-1ubuntu4)
    Не понял про "просто из файла".
    И что именно странно?

    ReplyDelete
  33. Ну, в смысле не из /dev/stdin, а из обычного текстового файла. Странно, что так медленно.

    ReplyDelete
  34. Есть также подозрение, что конкретный результат зависит от политики выделения памяти. Какая реализация будет выделять память кусками побольше — та и победит. Ну ещё у кого ввод-вывод оптимальнее (реально, на моём ноутбуке эта задача больше тест для жёсткого диска, чем для процессора, а значит и не для компилятора).

    Думаю, оптимальным для сей задачи будет: 1) заграбастать огромный буфер (сколько свободной памяти хватает), 2) писать в него stdin без разбора на строки, 3) по достижении EOF делать обратный поиск символа конца строки и печатать, 4) работать с низкоуровневым вводом-выводом.

    Вот вариант на Си.

    Для сравнения, твой первый вариант на Си++ на моей машинке (файл 630 МБ, а диск не такой уж быстрый...):

    $ time ./cpprev < /tmp/huge.txt > /tmp/out.txt

    real 3m23.797s
    user 1m7.720s
    sys 0m5.676s


    Наблюдалась плавная аллокация памяти с пиком много выше 1 гигабайта.

    И мой вариант на Си:

    $ time ./crev < /tmp/huge.txt > /tmp/out.txt

    real 0m29.521s
    user 0m1.624s
    sys 0m3.112s


    Очевидная оптимизация для Си++ — свой аллокатор. Только вот после этого код станет чуть ли не сложнее и чуть ли не более громоздким, чем на Си с ручной работой с памятью.

    gcc 4.3.2, -O2

    ReplyDelete
  35. Да, последний опубликованный тобой вариант на Си++ —

    $ time ./cpprev2 < /tmp/huge.txt > /tmp/out.txt

    real 0m28.728s
    user 0m5.436s
    sys 0m3.600s

    То есть выходит примерно как и ручной Си.

    ReplyDelete
  36. Всім привіт.

    Взагалі-то цей тест є порівнянням апельсинів зі свинями, бо Python при:

    open(..).readlines()

    — це те саме що:

    open(...).read().split(os.linesep)

    Але-ж на отеє великого розуму не треба. Крім того, читати з повільної консолі нема чого — можна зчитати і з файлу з таким самим успіхом, забираючи час від cat програми.

    Я-б хотів побачити буферизований ввід-вивід на Python (3.x, бо 2.x його взагалі не підтримує). Далі, програма на Python має нульовий зміст, а також простацький дизайн: відсмоктує весь файл у память, тим самим викликаючи клавіатурні удари по Ctrl+C та десперативний російський народний фольклор... :-)

    Тут, через звичайний FileReader, дуже повільним System.in/out через локаль та UTF провірки, а також звичийне зчитування по рядках (їх є 100 тільки дуже довгих) я добився ось цього: (OSX Leopard 10.5, Java 6, Update 13):

    sphinx:$ time java -Xmx2G -jar dist/xxx.jar /tmp/z.txt > /dev/null

    real 0m12.934s
    user 0m12.815s
    sys 0m2.616s

    І це при тому, що я маю окремо рядки, окреме заалочування памяті під кожну стрічку.

    Якщо-ж зчитувати весь файл цілком за один раз у бінарному вигляді та будувати строки по байтах, то виходить десь близько 2-х секунд.

    *yawn*

    ReplyDelete