Сказ о том, как 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.