Скотт Мейерс - Эффективное использование STL

Предположим, вы хотите отсортировать вектор чисел типа doubleпо убыванию. Простейшее решение этой задачи средствами STL основано на использовании алгоритма sortс объектом функции типа greater:

vector v;

…

sort(v.begin(), v.end(), greater());

Вспомнив о «плате за абстракцию», программист решает заменить объект функции «настоящей» функцией, которая к тому же оформлена как подставляемая ( inline):

inline bool doubleGreater(double d1, double d2) {

return d1 > d2;

}

…

sort(v.begin(), v.end(), doubleGreater);

Как ни странно, хронометраж двух вызовов sort показывает, что вызов с greaterпочти всегда работает быстрее. В своих тестах я сортировал вектор, содержащий миллион чисел типа double, на четырех разных платформах STL с оптимизацией по скорости, и версия с greaterвсегда работала быстрее. В худшем случае выигрыш в скорости составил 50%, в лучшем он достигал 160%. Вот тебе и «плата за абстракцию»…

Факт объясняется просто. Если функция operator()объекта функции была объявлена подставляемой (явно, с ключевым словом inline, или косвенно, посредством определения внутри определения класса), большинство компиляторов благополучно подставляет эту функцию во время создания экземпляра шаблона при вызове алгоритма. В приведенном выше примере это происходит с функцией greater::operator(). В результате код sortне содержит ни одного вызова функций, а для такого кода компилятор может выполнить оптимизацию, недоступную при наличии вызовов (связь между подстановкой функций и оптимизацией компиляторов рассматривается в совете 33 «Effective C++» и главах 8-10 книги «Efficient C++» [10]).

При вызове sortс передачей doubleGreaterситуация выглядит иначе. Чтобы убедиться в этом, необходимо вспомнить, что передача функции в качестве параметра другой функции невозможна. При попытке передачи функции в качестве параметра компилятор автоматически преобразует функцию в указатель на эту функцию, поэтому при вызове передается указатель. Таким образом, при вызове

sort(v.begin(), v.end(), doubleGreater);

алгоритму sortпередается не doubleGreater, а указатель на doubleGreater. При создании экземпляра шаблона объявление сгенерированной функции выглядит так:

void sort(vector::iterator first, // Начало интервала

vector:iterator last, // Конец интервала

bool (*comp)(double, double)); // Функция сравнения

Поскольку compявляется указателем на функцию, при каждом его использовании внутри sort происходит косвенный вызов функции (то есть вызов через указатель). Большинство компиляторов не пытается подставлять вызовы функций, вызываемых через указатели, даже если функция объявлена с ключевым словом inlineи оптимизация выглядит очевидной. Почему? Наверное, потому, что разработчики компиляторов не считают нужным ее реализовать. Пожалейте их — народ постоянно чего-нибудь требует, а успеть все невозможно. Впрочем, это вовсе не означает, что требовать не нужно.

Подавление подстановки кода функций объясняет один факт, который кажется невероятным многим опытным программистам C: функция C++ sortпочти всегда превосходит по скорости функцию C qsort. Конечно, в C++ приходится создавать экземпляры шаблонов функций и вызывать operator(), тогда как в C все ограничивается простым вызовом функции, однако все «излишества» C++ теряются во время компиляции. На стадии выполнения sortобращается к подставленной функции сравнения (при условии, что функция была объявлена с ключевым словом inline, а ее тело доступно на стадии компиляции), тогда как qsortвызывает функцию сравнения через указатель. Результат — sortработает гораздо быстрее. В моих тестах с вектором, содержащим миллион чисел double, превосходство по скорости достигало 670%, но я не призываю верить мне на слово. Вы легко убедитесь в том, что при передаче объектов функций в качестве параметров алгоритмов «плата за абстракцию» превращается в «премию за абстракцию».

Существует и другая причина для передачи объектов функций в параметрах алгоритмов, не имеющая ничего общего с эффективностью. Речь идет о компилируемости программ. По каким-то загадочным причинам некоторые платформы STL отвергают абсолютно нормальный код — это связано с недоработками то ли компилятора, то ли библиотеки, то ли и того и другого. Например, одна распространенная платформа STL отвергает следующий (вполне допустимый) фрагмент, выводящий в coutдлину всех строк в множестве: