Совет 46. Передавайте алгоритмам объекты функций вместо функций

Совет 46. Передавайте алгоритмам объекты функций вместо функций

Часто говорят, что повышение уровня абстракции языков высокого уровня приводит к снижению эффективности сгенерированного кода. Александр Степанов, изобретатель STL, однажды разработал небольшой комплекс тестов для оценки «платы за абстракцию» при переходе с С на С++. В частности, результаты этих тестов показали, что код, сгенерированный для работы с классом, содержащим double, почти всегда уступает по эффективности соответствующему коду, непосредственно работающему с double. С учетом сказанного вас может удивить тот факт, что передача алгоритмам объектов функций STL — то есть объектов, маскирующихся под функции, — обычно обеспечивает более эффективный код, чем передача «настоящих» функций.

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

vector<double> v;

sort(v.begin().v.end(),greater<double>());

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

inline

bool doubleGreater(double d1, double d2) {

return d1>d2;

}

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

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

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

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

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

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

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

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

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

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

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

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

set<string> s;

transform(s.begin(), s.end(),

ostream_iterator<string::size_type>(cout." "),

mem_fun_ref(&string::size)

);

Проблема возникает из-за ошибки в работе с константными функциями классов (такими как string::size) в этой конкретной платформе STL. Обходное решение заключается в использовании объекта функции:

struct StringSize:

public_unary_function<string,string::size_type> { // См. совет 40

string::size_type operator() (const string& s) const

{

return s.size();

}

transform (s.begin(),s.end(),

Ostream_iterator<string::size_type>(cout," "),

StringSize();

Существуют и другие обходные решения, но приведенный фрагмент хорош не только тем, что он компилируется на всех известных мне платформах STL. Он также делает возможной подстановку вызова string::size, что почти наверняка невозможно в предыдущем фрагменте с передачей mem_fun_ref(&string:: size). Иначе говоря, определение класса функтора StringSize не только обходит недоработки компилятора, но и может улучшить быстродействие программы.

Другая причина, по которой объекты функций предпочтительнее обычных функций, заключается в том, что они помогают обойти хитрые синтаксические ловушки. Иногда исходный текст, выглядящий вполне разумно, отвергается компилятором по законным, хотя и неочевидным причинам. Например, в некоторых ситуациях имя экземпляра, созданного на базе шаблона функции, не эквивалентно имени функции. Пример:

template<typename FPType> //Вычисление среднего

FPType average(FPType val1,FPType val2) //арифметического двух

{ //вещественных чисел

return (vail + val2)/2;

};

template<typename InputIter1. typename InputIter2>

void wrteAverages(InputIter begin1, //Вычислить попарные

InputIter end1, //средние значения

InputIter begin2, //двух серий элементов

ostream& s) //в потоке

{

transform(

begin1,end1,begin2,

ostream_iterator<typename iterator_traits<InputIter1>::value_type>(s," "),

average<typename iterator traits<lnputIter1>::value_type> // Ошибка?

};

};

Многие компиляторы принимают этот код, но по Стандарту С++ он считается недопустимым. Дело в том, что теоретически может существовать другой шаблон функции с именем average, вызываемый с одним параметром-типом. В этом случае выражение average<typename iterator_traits<InputIter1>:: value_type> становится неоднозначным, поскольку непонятно, какой шаблон в нем упоминается. В конкретном примере неоднозначность отсутствует, но некоторые компиляторы на вполне законном основании все равно отвергают этот код. Решение основано на использовании объекта функции:

template<typename FPType>

struct Average:

public binary_function<FPType,FPType,FPType>{ // См. совет 40

FPType operator()(FPType val1, FPType val2) const

{

return average(val1,val2);

}

};

template<typename InputIter, typename InputIter2>

void writeAverages(InputIter1 begin1, InputIter1 end1,

InputIter2 begin2, ostream& s)

{

transform( begin1,end1,begin2,

ostream_iterator<typename iterator_traits<InputIter1>::value_type>(s." "),

Average<typename iterator_traits<InputIter1>::value_type()

);

}

Новая версия должна приниматься любым компилятором. Более того, вызовы Average::operator() внутри transform допускают подстановку кода, что не относится к экземплярам приведенного выше шаблона average, поскольку average является шаблоном функции, а не объекта функции.

Таким образом, преимущество объектов функций в роли параметров алгоритмов не сводится к простому повышению эффективности. Объекты функций также обладают большей надежностью при компиляции кода. Бесспорно, «настоящие» функции очень важны, но в области эффективного программирования в STL объекты функций часто оказываются полезнее.

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг:

Объявление функций

Из книги автора

Объявление функций Прежде чем функция будет использована где-то в Web-сценарии, ее нужно объявить. Функцию объявляют с помощью ключевого слова function:function <имя функции>([<список параметров, разделенных запятыми>])<тело функции>Имя функции, как уже говорилось, должно


Вызов функций

Из книги автора

Вызов функций После объявления функции ее можно вызвать из любого Web-сценария, присутствующего на этой же Web-странице. Формат вызова функции:<имя функции>([<список фактических параметров, разделенных запятыми>])Здесь указывается имя нужной функции и в круглых


Совет 5. Используйте интервальные функции вместо одноэлементных

Из книги автора

Совет 5. Используйте интервальные функции вместо одноэлементных Есть два вектора, v1 и v2. Как проще всего заполнить v1 содержимым второй половины v2? Только не надо мучительно размышлять над тем, что считать «половиной» при нечетном количестве элементов в v2. Просто


Совет 39. Реализуйте предикаты в виде «чистых» функций

Из книги автора

Совет 39. Реализуйте предикаты в виде «чистых» функций Для начала разберемся с основными терминами.Предикатом называется функция, возвращающая тип bool (или другое значение, которое может быть автоматически преобразовано к bool). Предикаты широко используются в STL. В


Совет 43. Используйте алгоритмы вместо циклов

Из книги автора

Совет 43. Используйте алгоритмы вместо циклов Каждому алгоритму передается по крайней мере одна пара итераторов, определяющих интервал объектов для выполнения некоторой операции. Так, алгоритм min_element находит минимальное значение в интервале, алгоритм accumulate вычисляет


Вызовы функций

Из книги автора

Вызовы функций Синтаксис:<выражение> (<список-выражений>)Значением <выражения> должен быть адрес функции. В простейшем случае это идентификатор функции. <Список выражений> содержит выражения, разделенные запятыми. Значение каждого из этих выражений


Объявление функций

Из книги автора

Объявление функций Правила применения модификаторов near и far в объявлениях функций аналогичны правилам применения их в объявлениях данных. Если непосредственно за модификатором следует имя функции, то данное ключевое слово определяет, в каком сегменте будет размещена


10. Шаблоны функций

Из книги автора

10. Шаблоны функций В этой главе рассказывается, что такое шаблон функции, как его определять и использовать. Это довольно просто, и многие программисты применяют шаблоны, определенные в стандартной библиотеке, даже не понимая, с чем они работают. Только пользователи,


12.3.5. Адаптеры функций для объектов-функций

Из книги автора

12.3.5. Адаптеры функций для объектов-функций В стандартной библиотеке имеется также ряд адаптеров функций, предназначенных для специализации и расширения как унарных, так и бинарных объектов-функций. Адаптеры – это специальные классы, разбитые на следующие две


4.6.1 Описания Функций

Из книги автора

4.6.1 Описания Функций Описание функции задает имя функции, тип возвращаемого функцией значения (если таковое есть) и число и типы парамеров, которые должны быть в вызове функции. Например:extern double sqrt(double); extern elem* next_elem(); extern char* strcpy(char* to, const char* from); extern void exit(int);Семантика


19.11. Вызов функций

Из книги автора

19.11. Вызов функций В завершение этой главы рассмотрим два различных способа работы с функциями: вызов функций из исходного файла и применение функций, размещенных в


19.11.2. Вызов функций из файла функций

Из книги автора

19.11.2. Вызов функций из файла функций Мы уже рассматривали, каким образом функции вызываются из командной строки. Эти типы функций обычно используются утилитами, создающими системные сообщения.А теперь воспользуемся снова описанной выше функцией, но в этом случае


Вызовы функций

Из книги автора

Вызовы функций Вызовы функций имеют такой же синтаксис, как и вызовы процедур. Они могут быть квалифицированные и неквалифицированные: в первом случае используется нотация с многоточием. При соответствующих объявлениях класса и функций, они, например, таковы:b.fb.g(x, y,


Объявление функций

Из книги автора

Объявление функций Прежде чем функция будет использована где-то в сценарии, ее нужно объявить. Объявление функции выполняется с помощью ключевого слова function. function <Имя>([<Список параметров, разделенных запятыми>]) <Тело функции> Имя функции, как уже говорилось,


Вызов функций

Из книги автора

Вызов функций После того как мы объявили функцию, мы можем вызвать ее из любого места кода в пределах области видимости. Для этого используется следующий формат: <Имя функции>([<Список фактических параметров, разделенных запятыми>]) Здесь указывается имя нужной