понедельник, 12 декабря 2016 г.

[prog.c++] Разбор asfikon's "C vs C++". Часть 3.

Продолжаем тему (предыдущий пост здесь). Сегодня поговорим о влиянии на скорость работы программ таких вещей, как исключения, шаблоны, лямбды, STL и Boost.

Исключения

Исключения негативно влияют на производительность за счет двух основных факторов:

  • Во-первых, проброс, поимка и обработка исключений не бесплатна.
  • Во-вторых, расходы на проброс, поимку и обработку исключений сложно предсказуемы. Из-за этого исключения сложно использовать при решении задач реального времени, где предсказуемость времени работы определенного участка кода гораздо важнее самого времени работы этого участка.

Про особенности систем реального времени нам придется поговорить отдельно. Поэтому сейчас остановимся на первом факторе -- стоимости исключений, а предсказуемость пока рассматривать не будем.

Давно известно, что исключения, сами по себе, работают намного медленнее, чем возврат int-а с последующей его проверкой обычным if-ом. Однако, тут нужно отметить несколько моментов, которые могут быть не очевидны.

Начнем с того, что у убеждения "исключения тормозят" очень древние корни. Из самого начала 1990-х годов, когда основным компилятором C++ был Cfront, транслирующий C++ в код на C, а уже результат этой трансляции обрабатывался обычным C-шным компилятором, который ничего не знал ни про C++ные исключения, ни про их последствия (например, раскрутку стека с вызовом деструкторов сконструированных к этому моменту объектов).

В те времена для поддержки исключений Cfront был вынужден генерировать дополнительный C-шный код, который и обеспечивал работу всей этой кухни. Наличие этого дополнительного C-шного кода, понятное дело, негативно сказывалось как на объеме результирующего бинарника, так и на скорости работы. Ибо накладные расходы приходилось нести на всем: и на блоках try, и на throw, и в catch-ах, и даже при конструировании объектов (например, в случае наследования, когда конструкторы базовых классов могли бросать исключения или если у объекта были атрибуты (члены класса), которые сами могли бросать исключения в конструкторе).

Так что на начало 1990-х, т.е. 25 лет назад, тезис "исключения тормозят" имел под собой веские основания.

Однако, прогресс не стоит на месте, все течет, развивается и совершенствуется. В 2006-ом году был опубликован документ "Technical Report on C++ performance, TR18015", в котором проблеме производительности исключений посвящен отдельный раздел 5.4. И в котором рассматриваются два основных подхода к механизму реализации исключений, включая связанные с каждым из подходов накладные расходы.

Один из описанных в 2006-м году подходов к реализации исключений базируется на специальных таблицах. Накладные расходы в этом подходе возникают только при выбрасывании исключений. Т.е. вход и выход в try-блок, при отсутствии исключений, бесплатен. Равно как и на работу конструктора сложного объекта, подразумевающего вызовы конструкторов базовых классов и/или конструкторы других членов класса.

На данный момент реализация исключений на базе специальных таблиц, AFAIK, является реализацией по умолчанию для основных C++ компиляторов (по крайней мере для платформы x86_64).

Кроме того, в C++98/03 были т.н. динамические спецификаторы исключений, т.е. можно было указывать перечень выбрасываемых функцией/методом исключений в специальной секции throw: void f() throw(runtime_error). Проверка этих спецификаций должна была осуществляться в run-time, что, понятное дело, было не бесплатно. Однако, в C++11 эту фичу объявили устаревшей и современные версии C++компиляторов вообще не дают ее использовать в коде.

Для желающих поразбираться в теме самостоятельно несколько ссылок. На русском: "Нет ничего проще, чем вызвать функцию, я сам это делал неоднократно", на английском: "Are Exceptions in C++ really slow", "C++ exception handling internals".

Так что сейчас тезис "исключения тормозят" верен лишь частично -- исключения тормозят лишь тогда, когда их выбрасывают. Что дает нам возможность немного поговорить о том, а как же именно исключения влияют на производительность кода в современном мире? А вот это уже зависит от радиуса кривизны рук разработчика.

Поскольку проброс и поимка исключения -- это весьма дорогие операции (по разным оценкам от 20 до 50 раз дороже, чем использование кодов возврата с последующими проверками в if-ах), то использоваться исключения должны именно как исключения. Т.е. как способ проинформировать программу о том, что что-то пошло сильно не так. Не удалось выделить память. Индекс вышел за пределы массива. Номер месяца в дате почему-то получил значение 13. И т.д.

К сожалению, далеко не всегда разработчики действуют с позиций здравого смысла. Очень легко начать бросать исключения всегда, когда разработчику кажется, что что-то пошло не так. Например, кто-то может реализовать свою хитрую hash_table, которая будет бросать исключения при попытках неудачного поиска в таблице, при попытке вставить дубликат в таблицу или при попытке удалить элемент, которого в таблице нет. Ничто в C++ не препятствует такому использованию исключений. Значит, кто-нибудь так будет делать (и, что характерно, временами делают).

Еще одна возможность злоупотребить исключениями -- это реализовать "логику на исключениях". В C++ нет алгебраических типов данных и нет паттерн-матчинга. Поэтому иногда возникает соблазн использовать для этих целей C++ные исключения. Т.е. делать что-то вроде:

void analyze_and_make_result(some_data & d) {
   ...
   if(first_condition)
      throw one_result(...);
   else if(second_condition)
      throw second_result(...);
   ...
   throw some_another_result(...);
}

try {
   analyze_and_make_result(data);
}
catch(const one_result & r) { ... }
catch(const second_result & r) { ... }
...
catch(const some_another_result & r) { ... }

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

Так что исключения, определенно, окажут влияние на производительность кода.

Однако, если кто-то думает, что достаточно просто отказаться от исключений и получить серьезный прирост производительности, то это всего лишь приятное заблуждение.

Дело в том, что исключения -- это всего лишь способ информирования об ошибках. Один из лучших, кстати говоря. Но сейчас речь не о достоинствах исключений, а их стоимости. Так вот, если мы отказываемся от использования исключений для информирования об ошибках, то сами ошибки от этого никуда не исчезают. Следовательно, нам придется использовать какой-то другой механизм.

Так как мы противопоставляем C и C++, то в C у нас не будет никакого другого выхода, кроме использования кодов возврата.

Я специально оставляю за рамками разговора подход, когда признак успешности выполнения операции фиксируется в какой-то глобальной переменной, вроде errno. Во-первых, такой подход плохо дружит с многопоточностью (нужно уходить в сторону thread-local storage, что уже дороже простых кодов возврата). Во-вторых, проверка глобальных переменных так же будет дороже проверки кода возврата, возвращаемого, скорее всего, через регистры.

Это означает, что наш код начнет представлять из себя лапшу из if-ов. Что, насколько я понимаю, не есть хорошо с точки зрения объема кода. Плюс к тому, современные процессоры вынуждены делать предсказания ветвления дабы конвейер не простаивал. А наличие большого количества if-ов (то бишь jmp-ов в машинном коде) не способствуют упрощению этого самого предсказания.

Так что если мы начинаем писать типичный C-шый код в стиле goto cleanup (а по другому на C при работе с ресурсами сложно):

int f() {
   int h1 = 0, h2 = 0, h3 = 0;
   int r = -1;
   if(-1 == (h1 = try_acquire_resource1()))
      goto cleanup;
   if(-1 == (h2 = try_acquire_resource2()))
      goto cleanup;
   if(-1 == (h3 = try_acquire_resource3()))
      goto cleanup;
   ...
   r = 0;
cleanup:
   if(h3)
      free_resource3(h3);
   if(h2)
      free_resource2(h2);
   if(h1)
      free_resource1(h1);
   return r;
}

то в реальном большом проекте затраты на подобную обработку ошибок с точки зрения влияния на скорость работы не будут так уж сильно отличаться от нормального использования исключений.

В завершение этой темы со скоростью исключений могу поделиться своим опытом, хотя выжиманием максимальной производительности из железа мне не приходилось заниматься так уж часто. Но, все-таки, исключения никогда не были узкими местами. Гораздо чаще проблемы были в алгоритмах, а так же в чрезмерном использовании динамической памяти. Уменьшение new/delete давало прибавку к производительности несравнимую с затратами на обработку исключений. А смена алгоритма (или выбор более подходящей структуры данных) позволяла разгонять код даже не в разы, а на порядки.

Шаблоны

Каким образом шаблоны попали в список вещей, способствующих снижению скорости исполнения кода, мне сложно вообразить. Поэтому даже не знаю, как этот пункт можно прокомментировать.

Может быть речь идет об еще одном старом мифе, согласно которому шаблоны "раздувают" итоговый машинный код. Объемный исполнимый код не есть хорошо для современных архитектур, т.к. подкачка кода из основной памяти в кэш обходится дорого.

Как и в случае с исключениями этот миф уходит своими корнями во времена начала 1990-х, когда поддержка шаблонов только-только начала появляться в C++ных компиляторах. И когда техники оптимизации в компиляторах и линкерах были далеки от современного уровня. Сейчас ситуация с этим гораздо лучше.

При этом нужно понимать еще такую вещь, что шаблоны в C++ сильно отличаются от генериков в других языках. Так, если я объявляю у себя в коде экземпляр std::list<MyType>, но вызываю для этого экземпляра только методы begin(), end(), push_back() и pop_front(), то C++ компилятор сгенерирует код только для этих методов (плюс, конечно же, код конструктора и деструктора). Но не более того. Т.е., если я не вызываю std::list::sort, то код этого метода даже не генерируется. Не говоря уже про попадание в результирующий бинарник после линковки.

Так что совершенно не понятно, как именно шаблоны могут негативно сказаться на производительности. Скорее, напротив, шаблоны как раз та штука, которая способствует увеличению производительности итогового кода. Хрестоматийный уже пример, когда шаблонный std::sort обгоняет qsort из стандартной библиотеки C++ за счет того, что в std::sort инлайнятся все операции сравнения элементов, а qsort вынужден дергать функцию сравнения по указателю.

Более того, за последние 20 лет был накоплен большой опыт использования шаблонов. Если использование шаблонов начиналось с реализации контейнеров вроде std::list или std::vector, а так же алгоритмов, вроде std::sort или std::transform, то затем распространение получили и другие техники использования шаблонов. Например, policy based design или метапрограммирование на шаблонах. Которые могут использоваться, в том числе и для повышения скорости работы кода.

Возьмем, для примера, простой класс void_ptr_stack из предыдущей заметки. Он не выполняет проверок возможности выполнения операции. Т.е. можно вызвать top для пустого стека или push для заполненного. И получить непонятно что в процессе работы.

Иногда на это можно пойти, если нам нужна максимальная скорость и мы уверены в том, что делаем. Иногда хотелось бы иметь проверку в runtime, если безопасность для нас важнее производительности. Какой выбор у нас был бы в C?

В чистом C нам бы потребовалось иметь два набора функций для работы со стеком -- один набор делает проверки в runtime, второй не делает. Соответственно, это бы отражалось и на коде, который использует стек.

А вот в C++ мы могли бы задействовать шаблоны и технику задаваемых шаблонами политик. Например, вот так:

// Политика для случая, когда не требуется выполнять проверок в runtime.
// Большинство методов не имеет реализации и их вызовы будут выброшены
// оптимизирующим компилятором.
struct no_runtime_checks {
   no_runtime_checks(size_t /*capacity*/) {}
   void ensure_push_contract(size_t /*size*/) {}
   void ensure_top_contract(size_t /*size*/const {}
   size_t handle_pop(size_t size) { return size - 1; }
};

// Политика для случая, когда требуется выполнять проверки в runtime.
// Все методы имеют соответствующие реализации.
struct with_runtime_checks {
   const size_t capacity_;

   with_runtime_checks(size_t capacity) : capacity_(capacity) {}
   void ensure_push_contract(size_t size) {
      if(size == capacity_) throw std::runtime_error("full stack");
   }
   void ensure_top_contract(size_t size) const {
      if(!size) throw std::runtime_error("empty stack");
   }
   size_t handle_pop(size_t size) {
      return size ? size - 1 : size;
   }
};

Тут нужно обратить внимание на то, что в no_runtime_check нет никаких атрибутов -- это пустой объект. Зато в with_runtime_check есть один атрибут -- capacity_. Это сыграет свою роль когда мы посмотрим на шаблонную реализацию void_ptr_stack:

template<typename Policy>
class void_ptr_stack : private Policy {
public :
   using void_ptr = void *;

   void_ptr_stack(size_t capacity)
      :  Policy(capacity)
      ,  data_(new void_ptr[capacity])
      {}
   ~void_ptr_stack() {
      delete[] data_;
   }

   void_ptr_stack(const void_ptr_stack &) = delete;
   void_ptr_stack(void_ptr_stack &&) = delete;

   void push(void_ptr v) {
      this->ensure_push_contract(size_);
      data_[size_] = v;
      ++size_;
   }

   void_ptr top() const {
      this->ensure_top_contract(size_);
      return data_[size_ - 1];
   }

   void pop() {
      size_ = this->handle_pop(size_);
   }

   size_t size() const {
      return size_;
   }

private :
   void_ptr * data_;
   size_t size_{};
};

Тут мы получаем одинаковую реализацию как для случая с наличием runtime-проверок, так и без оных. Причем, если runtime-проверки нужны, то внутри void_ptr_stack окажется константный атрибут capacity_. А если такие проверки не нужны, то у нас этого атрибута и не будет, т.е. размер void_ptr_stack<no_runtime_checks> будет меньше, чем размер void_ptr_stack<with_runtime_checks>. Но код void_ptr_stack одинаковый. И, соответственно, его интерфейс для обоих случаев одинаковый.

Это означает, что мы можем использовать сначала void_ptr_stack<with_runtime_checks>, а затем, когда протестируем свой код и убедимся, что проверки в runtime слишком дорогие, просто поменяем тип стека на void_ptr_stack<no_runtime_checks>. И все. При этом наш код и работать будет быстрее, и памяти будет потреблять меньше.

Так что тезис "шаблоны негативно влияют на скорость работы кода" крайне сложно воспринимать хоть сколько нибудь всерьез.

Лямбды

Еще одна претензия, суть которой не совсем понятна. Ведь лямбды в C++ -- это всего лишь синтаксический сахар над давным-давно известными в C++ объектами-функторами. Только раньше программист был вынужден реализовывать функторы вручную (например, наследоваться от std::unary_function или std::binary_function, определять атрибуты, инициализирующий конструктор, вручную описывать operator() и т.д.). А теперь все это за разработчика делает компилятор. Только и всего.

Так что как во времена C++98/03 использование объектов-функторов, скажем, со стандартными алгоритмами STL, не создавало проблем с производительностью, так и сейчас использование лямбда-функций не создает этих проблем. Все потому, что оптимизирующие компиляторы уже 20 лет назад могли инлайнить все необходимые вызовы. И за прошедшее время научились делать это еще лучше.

Более того, лямбды в C++ позволяют изображать "вложенные функции", известные в других языках программирования. Что дает возможность программисту писать короче и явным образом декларировать свои намерения, а компилятору открывает больше возможностей для оптимизации. Пример использования лямбды в виде локальной функции можно увидеть в старой заметке, посвященной рефакторингу кода ув.тов.asfikon-а. Вот здесь logErrorThenReturnNull как раз такая локальная функция и есть:

FileMappingUniquePtr fileMappingCreate(const char* fname) {
   auto logErrorThenReturnNull = [fname](const char * what) {
      std::cerr << "fileMappingCreate - " << what << " failed, fname = " << fname << std::endl;
      return FileMappingUniquePtr{ nullptr, &fileMappingClose };
   };

   FileMappingUniquePtr result{ new FileMapping, &fileMappingClose };

   result->hFile = CreateFile(fname, GENERIC_READ, 0nullptr, OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL, nullptr);
   if(result->hFile == INVALID_HANDLE_VALUE)
      return logErrorThenReturnNull( "CreateFile" );

   DWORD dwFileSize = GetFileSize(result->hFile, nullptr);
   if(dwFileSize == INVALID_FILE_SIZE)
      return logErrorThenReturnNull( "GetFileSize" );

   result->hMapping = CreateFileMapping(result->hFile, nullptr, PAGE_READONLY, 00nullptr);
   if(result->hMapping == nullptr// yes, NULL, not INVALID_HANDLE_VALUE, see MSDN
      return logErrorThenReturnNull( "CreateFileMapping" );

   result->dataPtr = static_castconst unsigned char* >(MapViewOfFile(result->hMapping, FILE_MAP_READ, 00, dwFileSize));
   if(result->dataPtr == nullptr)
      return logErrorThenReturnNull( "MapViewOfFile" );

   result->fsize = static_cast<unsigned int>(dwFileSize);

   return result;
}

Так что использование лямбда-функций, особенно в сочетании с шаблонами, само по себе вряд ли может негативно повлиять на производительность. Хотя, конечно же, кривые руки способны еще и не на такое.

А вот что может повлиять, как это чрезмерное злоупотребление преобразованием лямбд к std::function.

Если кто-то не в курсе, то std::function можно рассматривать как аналог std::shared_ptr, но только для функций и лямбда-функций. Т.е., если у нас есть что-то вроде:

// Реализована где-то в другом месте.
void do_some_task(std::function<void(int)> progress_indicator);
...
// Инициируем операцию и передаем лямбду для того, чтобы
// можно было отображать проценты выполнения операции посредством
// элемента GUI.
progress_bar * bar = get_appropriate_progress_bar();
do_some_task( [bar](int percents) { bar->set_value(precents); } );

То тогда мы, естественно, будем будем нести дополнительные накладные расходы. Связаны они, однако, будут не столько с самой лямбдой, сколько с std::function, в которую лямбда-функцию упрятывают.

Резюмируя данный раздел можно сказать следующее: лямбды в сочетании с шаблонами не создают дополнительных накладных расходов. Лямбды в сочетании с std::function такие накладные расходы будут создавать. Поэтому, если скорость работы важна, то к использованию std::function нужно подходить с некоторой осторожностью (т.к. под std::function может скрываться и работа с динамической памятью, и подсчет ссылок). Но вот сами по себе лямбды, без std::function, угрозу производительности не несут.

Для тех, кто думает, что std::function -- это "тормоз, тормоз", может быть интересна вот эта статья: "What you need _not_ know about std::function - Part 3". Когда std::function уже сконструирован, он работает с приличной скоростью. Не как прямой вызов, конечно, но косвенность, она никуда не денется. Так что опасаться нужно больше операций созданий и разрушения объектов std::function.

STL и Boost

Боюсь, здесь я вообще не смогу дать какой-нибудь предметный комментарий. STL сам по себе довольно большой и в нем есть разные вещи. Что и в каких условиях тормозит? Не знаю.

Boost еще больше. Как по мне, так Boost -- это даже не библиотека. Это некий конгломерат сильно разных вещей, собранных под одной крышей. Там есть, например, Boost.Container. Есть Boost.StringAlgorithms. Есть Boost.Filesystem. И есть Boost.MPI. По сути -- совершенно разные библиотеки, предназначенные для совершенно разных вещей. Что из этого тормозит? Где тормозит? Опять таки ответов нет.

Так что остается только высказать философские замечания.

Неоднократно доводилось слышать высказывания о том, что производительность STL-евских контейнеров никакая и что если вам нужно что-то серьезное, то вам придется делать что-то свое, а STL идет лесом. В таких высказываниях меня всегда смущают две вещи. Во-первых, обычно не уточняется, что именно тормозит. Вот, скажем, где и как может тормозить std::vector? Ну ведь не праздный же вопрос. Если std::vector тормозит потому, что есть куча push_back-ов, но нет предварительного reserve, то ведь это же не std::vector тормозит.

Во-вторых, есть ощущение, что большинство таких любителей похаить STL не отдают себе отчета в том, для чего вообще в стандартной библиотеке нужны контейнеры. Вовсе не для того, чтобы показывать наивысшую производительность всегда и везде. Ибо сие просто невозможно. Они нужны для упрощения интероперабильности кода, написанного разными разработчиками для разных целей. Вот есть библиотека A функции которой возвращают вектора значений. И есть библиотека B на вход которой нужно передавать эти самые вектора. Если библиотеки A и B написаны разными командами, в разных частях света, и даже в разное время, то как обе библиотеки задействовать в рамках одного проекта? Брать вектора из библиотеки A и преобразовывать их в вектора из библиотеки B? Спасибо, не надо, 20 лет назад по этому пути уже доводилось ходить. Ничего хорошего там нет.

А вот если A использует std::vector и B использует std::vector, то все намного проще. И эта самая простота как раз и является платой за то, что какой-то из STL-евских контейнеров не будет в каких-то конкретных условиях так же быстр, как какой-то кастомный контейнер, специально заточенный под специфический сценарий использования. Можно, конечно же, говорить "Как же так, приходится платить за скорость?!!!" Только это не конструктивно. Сделать что-то, что было бы в общем случае настолько же эффективно, как штатные контейнеры STL, задачка не из простых. И с годами она только усложняется, т.к. реализации STL-я постоянно вылизываются и переплюнуть то, во что было вложено столько труда, не так-то и просто.

Кроме интероперабильности средства STL позволяют быстро собрать proof-of-concept решение, погонять его под разными профилями нагрузки, выявить настоящие узкие места. И затем, за счет собственных кастомных контейнеров, разогнать только то, что требует разгона. Могу уверить читателей, что сейчас это делается намного проще, чем 25 лет назад, когда никакого STL-я еще и в помине не было, и под задачу нужные контейнеры приходилось либо делать самому, либо же искать их реализации в сторонних библиотек.

Так что, если и предъявлять STL-ю какие-то претензии, то не в части производительности, а в части скудности набора готовых контейнеров. Да и то, этот набор в C++11 серьезно пополнили. Плюс к тому, есть Boost. Плюс к тому есть сторонние библиотеки. Плюс к тому, C++ развивается за счет своего коммьюнити. Так что ничего не запрещает авторам своих кастомных контейнеров попробовать продвинуть свои творения сперва в Boost, а затем и в стандарт языка. Глядишь, и STL начнет тормозить меньше ;)

Продолжение...

Отправить комментарий