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.

Tuesday, July 7, 2009

Bachelor Thesis in Computer Science. Part 3. Слайды в LaTeX-beamer

Лучше поздно, чем никогда - предлагаю вам обещанную третью часть с описанием того, что есть LaTeX-beamer и как его можно использовать при написании бакалаврской работы.
beamer - класс LaTeX, который позволяет быстро создавать красивые слайды. Если вы не знаете, что это такое или ни разу не пробовали - попробуйте, и вам больше никогда не захочется запускать громоздкие системы WISIWYG для создания слайдов.
Основные достоинства beamer, на которые хотелось бы обратить внимание:

  • Полное разделение оформления и содержания. Сначала пишите текст, а оформление можно сменить в любой момент
  • Очевидный плюс, но забывать о нём нельзя: можно использовать все возможности LaTeX
  • Красивые и удобные темы оформления "из коробки"
  • Широкие возможности в настройке и доводке

Пример применения

Эта статья не задумывалась как учебное пособие по beamer, ее цель - дать представление и заинтересовать. Поэтому сразу перейдём к скриншотам и некоторым советам. Титульная страница, которую любезно сгенерирует вам beamer после заполнения некоторых полей:
Один из слайдов:

Как видите, слайды выглядят весьма привлекательно. К тому же, представьте, что каждый слайд - это всего пара строчек текста. А теперь, как я и обещал, несколько советов подкрепленные кодом:
  • Не пытайтесь изменить шрифт, чтобы вместить на слайд как можно больше информации. Выполненные в PowerPoint с 12pt шрифтом презентации навевают тоску и абсолютно нечитаемы с расстояния в 5-10 метров. Если уж очень нужно разместить на слайде побольше, а количества строк не хватает - используйте двухколоночную вёрстку. Тогда даже большое количество формул может поместиться на один слайд:
    Для верстки в две колонки используйте пакет multicol(на примере вставки изображений в две колонки):
    \usepackage{multicol}
    %%....
    \begin{multicols}{2}
    \begin{figure}[!ht]
    \begin{center}
    \includegraphics[width=\columnwidth]{../img/positioning_slides1}
    \end{center}
    \end{figure}

    \begin{figure}[!ht]
    \begin{center}
    \includegraphics[width=\columnwidth]{../img/positioning_slides2}
    \end{center}
    \end{figure}
    \end{multicols}
  • Создатели тем оформления beamer не подумали, что название может быть длинным и сократить его будет нельзя. Поэтому во многих темах длинные названия не влазят на слайд. Однако это можно исправить - например, использование подправленной темы оформления, которую вы видели на скриншотах:
    \usetheme{Antibes}
    \useinnertheme{rounded}
    \setbeamertemplate{headline}
    {%
    \begin{beamercolorbox}[wd=\paperwidth,ht=6.5ex,dp=1.125ex,%
    leftskip=.3cm,rightskip=.3cm plus1fil]{title in head/foot}
    \usebeamerfont{title in head/foot}\parbox[b]{0.95\paperwidth}{\@title}
    \end{beamercolorbox}
    \begin{beamercolorbox}[wd=\paperwidth,ht=2.5ex,dp=1.125ex,%
    leftskip=.3cm,rightskip=.3cm plus1fil]{section in head/foot}
    \usebeamerfont{section in head/foot}%
    \ifthenelse{\value{page}>1}{\hskip2pt\raise1.9pt\hbox{\vrule width0.4pt height1.875ex\vrule width 5pt height0.4pt}}{}
    \hskip1pt%
    \insertsectionhead
    \end{beamercolorbox}
    \begin{beamercolorbox}[wd=\paperwidth,colsep=1.5pt]{lower separation line head}
    \end{beamercolorbox}
    }


    \setbeamertemplate{footline}
    {%
    \leavevmode%
    \hbox{\begin{beamercolorbox}[wd=.5\paperwidth,ht=2.5ex,dp=1.125ex,leftskip=.3cm plus1fill,rightskip=.3cm]{author in head/foot}%
    \usebeamerfont{author in head/foot}\insertshortauthor
    \end{beamercolorbox}%
    \begin{beamercolorbox}[wd=.5\paperwidth,ht=2.5ex,dp=1.125ex,leftskip=.3cm,rightskip=.3cm plus1fil]{title in head/foot}%
    \usebeamerfont{title in head/foot}Слайд \insertframenumber
    \end{beamercolorbox}}%
    \vskip0pt%
    }
    Этот небольшой сниппет может стать отправной точкой для написания собственных тем оформления - в нём совсем несложно разобраться по названиям команд
  • Скриптованные презентации никому не нужны. Я имею в виду моргающие анимированные слайды со сложной системой переходов, которые можно создать в Microsoft Office или OpenOffice. Для улучшения восприятия достаточно простейших эффектов, которых можно легко добиться в beamer. Единственной полезной вещи, которой может не хватать в beamer по сравнению с PowerPoint и Impress - воспроизведение видео. Однако встроить видео в PDF тоже можно! Пример:
    \usepackage{movie15}
    %%...
    \frame
    {
    \includemovie[externalviewer]{}{}{../vid/mouse_emulation.avi}
    }
    Этот код отводит отдельный слайд под видео. Стоит отметить, что видео можно будет проиграть только в Adobe Reader (я не знаю свободных альтернатив, которые бы поддерживали видео). Также обратите внимание, что я использую внешний плеер. Использование внешнего плеера гарантирует максимальную кросс-платформенность вашего PDF документа

Выводы

Используйте LaTeX, используйте beamer. Забудьте о медленных, неудобных офисных пакетах, полных недостатков и ошибок.

P.S.

Здесь вы можете найти исходники презентации (без изображений и видео)