Введение
Когда на IT-форумах задают вопрос «Быстрее ли язык программирования X языка Y», это обычно вызывает потоки эмоций и считается некорректным. Сродни вопросу про религию или предпочтение той или иной политической партии. Действительно, язык — это способ выражения мысли, идеи. В данном случае идеи программной системы. Он не быстр и не медлен. Он может быть более или менее лаконичным, более или менее точным. А скорость определяется не столько языком, сколько конечным кодом, который генерирует компилятор этого языка. Или скоростью интерпретатора в случае интерпретируемого языка.
Но это всё философия. А на практике обычно есть практическая задача разработки ПО. И, действительно, реализовать это ПО можно на десятке разных языков программирования. Поэтому, хоть это и «религиозный вопрос» в случае публичного обсуждения, вопрос этот часто возникает в голове IT-специалиста, стоящего перед конкретной задачей. «Сколько времени мне потребуется для реализации задачи на языке X и какие у полученного ПО будут характеристики, в том числе скоростные, по сравнению с реализацией этой задачи на языке Y». Понятное дело, точного ответа на этот вопрос нет, специалист опирается на свой личный опыт и отвечает как-то типа «с вероятностью 95%, написанная на ассемблере, эта задача будет работать быстрее, чем на php». Но, положа руку на сердце, опыт этот редко базируется на точных цифрах реальных задач, которые сам этот специалист реализовал. Нет, ну кто в здравом уме будет писать сложное ПО сначала на php, а потом его же переписывать на ассемблере, только чтобы измерить характеристики? В основном ограничиваются синтетическими тестами типа сортировки массива, построения и обхода бинарного дерева и тому подобных.
Я, как специалист, пишущий 90% на C++, часто натыкаюсь на «холливарные» темы сравнения этого языка с другими. И один из них — это прародитель — язык C. На том же quora.com часто поднимают этот вопрос «А быстрее ли язык C языка C++» (что некорректно, как я объяснил выше), или «А почему ядро Linux или тонна GNU утилит пишется на C а не на C++» (что является вполне корректным вопросом). На второй вопрос я для себя ответил так:
- Освоение языка C требует на порядок меньших усилий, значит, больше людей могут поучаствовать в разработке этого ПО.
- Сложные действия, потенциально затратные по памяти или скорости на языке C займут, вероятно, больше строчек кода и потребуют усилия от автора. А значит, неоптимальность в программе легче будет заметить по ходу написания или ревью. Программа на языке C++ может быть куда более лаконична и, с виду, проста в понимании. Но заметить, что за перегрузкой оператора «+», к примеру, скрывается запуск космического корабля к луне, заметить будет сложнее.
Так как язык C является частью языка C++, мне по ходу моих каждодневных задач приходится решать, выразить ли какую-то часть логики «более в C стиле» (с работой с «сырыми» указателями, очисткой памяти через memset, передачей контекста через void*), или типобезопасно в C++ стиле (указатели обёрнуты в unique_ptr / shared_ptr, память зачищается нормально написанными конструкторами, контекст передаётся как типизированный объект: либо указателем на базовый класс с виртуальными функциями, либо вообще как шаблон).
Задачка
Для того, чтобы чуть более основательно ответить себе на этот вопрос, я решил написать ещё один (да-да, тоже немного синтетический) тест — кодирование данных методом Хаффмана. Навела на мысль статья «Алгоритм Хаффмана на пальцах» (https://habrahabr.ru/post/144200/).
Сначала я реализовал кодирование на чистом C. Если помните, для его реализации требуется очередь с приоритетом, потому как там для построения дерева кодирования нужно быстро находить символы, упорядоченные по числу их повторений. Алгоритмические подробности я опущу, отсылая читателя по ссылке выше (пардон за тавтологию). Собственно, на этом всё бы и закончилось, и не было бы никакой статьи, потому что кодирование я реализовывал только в качестве тренировки в алгоритмике. Но по ходу работы я заметил, как же быстро компилируется программа на C по сравнению с подобного размера исходниками на C++. И упомянул об этом коллеге по работе. Высказав предположение, что компиляция на C++ включает, наверное, ещё множество способов оптимизации. Так что подобно написанный код на C++, наверное, должен быть быстрее — там же будет работать магия самых-самых гуру в области написания оптимизирующих компиляторов. Ухмыльнувшись, коллега ответил: «Проверь».
И тогда я переписал кодирование Хаффмана на C++. Для чистоты эксперимента я не менял основополагающих принципов, к примеру, не вставлял пользовательский распределитель памяти. Это можно сделать и в C (более «кастомно») и в C++ (более «нативно»). В чём же тут тогда «C++-ность»?
Очередь с приоритетом
Первое, что логично выразить через шаблоны в C++, это очередь с приоритетом. На C она представлена в виде структуры, главный элемент которой — указатель на массив указателей на узлы с данными:
struct priority_queue
{
// A number of active (carrying data) nodes currently in the queue
unsigned int size;
// A total number of nodes in "nodes" array
unsigned int capacity;
// An array of pointers to nodes
struct priority_queue_node** nodes;
};
Узел с данными может быть любым типом, но его первым элементом должна быть следующая структура:
struct priority_queue_node
{
unsigned int weight;
};
Так как очередь не занимается управлением памятью под сами узлы, ей незачем знать, из чего реально состоит узел. Всё, что требуется для работы, это получить его вес: ((struct priority_queue_node*) node_ptr)→weight. Добавление узла в очередь с учётом возможного перевыделения памяти выглядит несколько громоздко:
int priority_queue_push(struct priority_queue* queue, struct priority_queue_node* node)
{
if (queue->size >= queue->capacity)
{
int new_capacity = queue->capacity * 2;
if (new_capacity == 0)
new_capacity = 1;
struct priority_queue_node** new_nodes = (struct priority_queue_node**) malloc(sizeof(struct priority_queue_node*) * new_capacity);
if (! new_nodes)
{
return 0;
}
memcpy(new_nodes, queue->nodes, sizeof(struct priority_queue_node*) * queue->size);
if (queue->capacity)
free(queue->nodes);
queue->nodes = new_nodes;
queue->capacity = new_capacity;
}
queue->nodes[queue->size++] = node;
heapify(queue);
return 1;
}
Создание очереди и её удаление с обработкой всех ошибок — тоже много строчек кода по сравнению с C++ версией, что ожидаемо. Собственно, версия очереди на C++ выглядит так (внимание — на представление данных):
template <class T> class priority_queue
{
struct node
{
unsigned int m_weight;
T m_data;
};
using node_ptr = std::unique_ptr<node>;
std::size_t m_capacity;
std::size_t m_size;
std::unique_ptr<node_ptr[]> m_nodes;
void heapify() noexcept;
void increase_capacity();
public:
explicit priority_queue(std::size_t capacity = 16) ;
// …
};
Налицо такое же расположение элементов узла в памяти, как и в C версии — сначала идёт вес, затем полезная нагрузка узла, которая, как будет показано ниже, состоит из целочисленного скаляра — высоты дерева, содержащегося в этом узле, и указателя на корень этого дерева. Сами узлы в этой очереди приоритетов хранятся также — указатель m_nodes указывает на массив указателей на узлы.
Для сравнения — положить новый элемент в очередь теперь выглядит более лаконично и типобезопасно (перевыделение памяти — в отдельном методе increase_capacity, что не меняет сути):
template <class U>
push(unsigned int weight, U&& obj)
{
if (m_size >= m_capacity)
increase_capacity();
m_nodes[m_size++].reset(new node({weight, std::forward<U>(obj)}));
heapify();
}
void increase_capacity()
{
const auto new_capacity = m_capacity ? m_capacity * 2 : 1;
std::unique_ptr<node_ptr[]> new_nodes(new node_ptr[new_capacity]);
for (auto src = m_nodes.get(), dest = new_nodes.get(); src != m_nodes.get() + m_size; ++src, ++dest)
*dest = std::move(*src);
m_nodes = std::move(new_nodes);
m_capacity = new_capacity;
}
Дерево символов (дерево кодирования)
В очередь впоследствии будут вставляться части дерева символов, которые затем будут объединяться в соответствии с числом повторений каждого символа так, чтобы в конце получить дерево кодирования. На C это дерево представляется простейшими структурами с сырыми указателями, базовая из них содержит идентификатор конечного типа:
#define NODE_TYPE_TERM 1
#define NODE_TYPE_NODE 2
struct char_node_base
{
int type;
};
struct char_node_terminal
{
struct char_node_base base;
char c;
};
struct char_node
{
struct char_node_base base;
struct char_node_base* left;
struct char_node_base* right;
};
А чтобы положить корень такого дерева в очередь с приоритетом, определена структура с, требуемым очередью, членом — хранителем веса узла:
struct char_node_root
{
struct priority_queue_node pq_node;
int height;
struct char_node_base* node;
};
На C++ всё это выражается несколько элегантнее:
struct char_node_base
{
virtual ~char_node_base() = default;
};
using char_node_ptr = std::unique_ptr<char_node_base>;
struct char_node_terminal : char_node_base
{
const unsigned char m_c;
char_node_terminal(char c) noexcept : m_c(c) {}
};
struct char_node : char_node_base
{
char_node_ptr m_left;
char_node_ptr m_right;
};
struct nodes_root
{
int m_height;
char_node_ptr m_node;
};
Здесь видно ключевое преимущество C++ — для корректного удаления этого дерева не нужно делать ничего. Просто удалить корень, авто указатели всё сделают сами. В C же для этой задачи написано изрядное количество кода.
Заполнение очереди и построение дерева
Этот шаг вообще не отличается для C и C++ реализации. Сначала просчитывается число повторений каждого символа во входном блоке данных, и заполняется табличка из 256 байт. Потом в очередь с приоритетом кладутся микро-деревья, состоящие только из одного терминального узла. Далее узлы объединяются путём последовательного извлечения из очереди пары, ближайшей к её вершине, и вставкой туда промежуточного узла, содержащего извлечённые прежде.
На C (здесь — без проверки на ошибки) это выглядит следующим образом:
static struct priority_queue* build_priority_queue(
char* buffer, unsigned int size)
{
unsigned char table[256];
memset(table, 0, sizeof(table));
for (unsigned int i = 0; i < size; ++i)
if (table[(unsigned char)buffer[i]] != 255)
++table[(unsigned char)buffer[i]];
struct priority_queue* queue = priority_queue_create(16);
for (unsigned short i = 0; i < 256; ++i)
{
if (table[i])
{
struct char_node_root* node = (struct char_node_root*) malloc(sizeof(struct char_node_root));
struct char_node_terminal* term = (struct char_node_terminal*) malloc(sizeof(struct char_node_terminal));
term->base.type = NODE_TYPE_TERM;
term->c = (char)i;
node->node = (struct char_node_base*) term;
node->height = 0;
node->pq_node.weight = table[i];
priority_queue_push(queue, (struct priority_queue_node*) node);
}
}
return queue;
}
static struct char_node_root* queue_to_tree(struct priority_queue* queue)
{
while (priority_queue_size(queue) > 1)
{
struct char_node_root* node1 = (struct char_node_root*) priority_queue_pop(queue);
struct char_node_root* node2 = (struct char_node_root*) priority_queue_pop(queue);
struct char_node_base* int_node1 = node1->node;
struct char_node_base* int_node2 = node2->node;
struct char_node* join_node = (struct char_node*) malloc(sizeof(struct char_node));
join_node->base.type = NODE_TYPE_NODE;
join_node->left = int_node1;
join_node->right = int_node2;
int new_weight = node1->pq_node.weight;
if (new_weight + node2->pq_node.weight <= 65535)
new_weight += node2->pq_node.weight;
else
new_weight = 65535;
node1->pq_node.weight = new_weight;
if (node1->height > node2->height)
++node1->height;
else
node1->height = node2->height + 1;
free(node2);
node1->node = (struct char_node_base*) join_node;
priority_queue_push(queue, (struct priority_queue_node*) node1);
}
return (struct char_node_root*) priority_queue_pop(queue);
}
На C++ — ещё короче и красивее при том, что любые ошибки выделения памяти будут обработаны корректно благодаря исключениям и применению авто указателей:
void fill_priority_queue(
const unsigned char* buffer,
std::size_t buffer_size,
queue_t& queue)
{
unsigned char counts_table[256]{};
for (auto ptr = buffer; ptr != buffer + buffer_size; ++ptr)
if (counts_table[*ptr] != 255)
++counts_table[*ptr];
for (unsigned short i = 0; i != 256; ++i)
if (counts_table[i])
queue.push(counts_table[i], nodes_root {0, char_node_ptr(new char_node_terminal(i))});
}
void queue_to_tree(queue_t& queue)
{
while (queue.size() > 1)
{
auto old_root1_node = std::move(queue.top());
const auto old_root1_weight = queue.top_weight();
queue.pop();
auto old_root2_node = std::move(queue.top());
const auto old_root2_weight = queue.top_weight();
queue.pop();
auto joined_node = std::unique_ptr<char_node>(new char_node);
joined_node->m_left = std::move(old_root1_node.m_node);
joined_node->m_right = std::move(old_root2_node.m_node);
const auto new_weight = std::min(old_root1_weight + old_root2_weight, 65535U);
const auto new_height = std::max(old_root1_node.m_height, old_root2_node.m_height) + 1;
queue.push(new_weight, nodes_root {new_height, std::move(joined_node)});
}
}
Таблица кодирования
Следующим этапом из дерева кодирования нужно построить таблицу, где каждому символу в соответствие поставлена последовательность бит, отражающих прохождение по, только что построенному, дереву кодирования до этого символа. Код для обхода дерева и «набивания» последовательности бит в обоих версиях практически идентичен. Наибольший интерес же представляет то, как хранить эту последовательность бит и оперировать ею. Ведь после построения этой таблицы начнётся то, ради чего всё затевалось. Проходя по входному буферу для каждого, найденного там символа, будет браться его битовая последовательность и добавляться к результирующей выходной последовательности.
В C версии последовательность бит представляется тривиальной структурой, состоящей из указателя на массив байт и счётчика реально заполненных бит. Каких-то специальных операций для работы с ней нет. На этапе построения таблицы кодирования для каждого символа заводится такая структурка, куда копируется, найденная для текущего символа, последовательность бит. Таким образом, таблица кодирования — это просто массив этих структур для каждого символа.
struct bits_line
{
unsigned char bits_count;
unsigned char* bits;
};
static int build_encoding_map_node(struct char_node_base* node, struct bits_line* bits_table, unsigned char* bits_pattern, int bits_count)
{
if (node->type == NODE_TYPE_TERM)
{
unsigned char index = (unsigned char)((struct char_node_terminal*)node)->c;
bits_table[index].bits_count = bits_count;
bits_table[index].bits = (unsigned char*) malloc(bytes_count_from_bits(bits_count + 1));
if (! bits_table[index].bits)
return 0;
memcpy(bits_table[index].bits, bits_pattern, bytes_count_from_bits(bits_count));
return 1;
}
static const unsigned char bit_mask[] = {1, 2, 4, 8, 16, 32, 64, 128};
bits_pattern[bits_count >> 3] &= ~bit_mask[bits_count & 7];
if (! build_encoding_map_node(((struct char_node*)node)->left, bits_table, bits_pattern, bits_count + 1))
return 0;
bits_pattern[bits_count >> 3] |= bit_mask[bits_count & 7];
if (! build_encoding_map_node(((struct char_node*)node)->right, bits_table, bits_pattern, bits_count + 1))
return 0;
return 1;
}
В C++ версии битовый массив удобнее представить полноценным классом, который будет не просто управлять ресурсами, но и поддерживать, нужную далее, операцию добавления другой битовой последовательности.
using unique_bytes_ptr = std::unique_ptr<unsigned char[]>;
class bit_ostream
{
std::size_t m_capacity;
unsigned long m_bits_count = 0;
unique_bytes_ptr m_data;
public:
explicit bit_ostream(std::size_t initial_capacity = 0) noexcept
: m_capacity(initial_capacity)
{
}
bit_ostream& push(const unsigned char* bits, unsigned long const bits_count)
{
if (bits_count == 0)
return *this;
const auto new_bits_count = m_bits_count + bits_count;
if (covered_bytes(new_bits_count) + 1 > m_capacity || m_bits_count == 0)
{
decltype(m_capacity) new_capacity = m_capacity * 2;
const auto cov_bytes = static_cast<decltype(m_capacity)>(covered_bytes(new_bits_count) + 1);
if (new_capacity < cov_bytes)
new_capacity = cov_bytes;
unique_bytes_ptr new_data(new unsigned char[new_capacity]);
std::memcpy(new_data.get(), m_data.get(), covered_bytes(m_bits_count));
m_capacity = new_capacity;
m_data = std::move(new_data);
}
unsigned char* curr = m_data.get() + (m_bits_count >> 3);
if ((m_bits_count & 7) == 0)
{
// All it's simple when current output data size is integer number of bytes
std::memcpy(curr, bits, covered_bytes(bits_count));
}
else
{
const unsigned char shift = m_bits_count & 7;
for (auto bytes_count = covered_bytes(bits_count); bytes_count > 0; ++curr, ++bits, --bytes_count)
{
unsigned short val = static_cast<unsigned short>(*bits) << shift;
val |= static_cast<unsigned short>(*curr & g_bits_fill_mask[shift]);
*curr = static_cast<unsigned char>(val & 0xff);
*(curr + 1) = static_cast<unsigned char>(val >> 8);
}
}
m_bits_count += bits_count;
assert(covered_bytes(m_bits_count) <= m_capacity);
return *this;
}
bit_ostream& push(const bit_ostream& other)
{
return push(other.data(), other.bits_count());
}
bit_ostream& clear_tail() noexcept
{
if (m_bits_count & 7)
m_data.get()[m_bits_count >> 3] &= g_bits_fill_mask[m_bits_count & 7];
return *this;
}
unsigned long bits_count() const noexcept { return m_bits_count; }
bool empty() const noexcept { return ! m_bits_count; }
unsigned char* data() noexcept { return m_data.get(); }
const unsigned char* data() const noexcept { return m_data.get(); }
};
template <class T>
constexpr inline std::size_t covered_bytes(T bits_count) noexcept
{
return (bits_count >> 3) + (bits_count & 7 ? 1 : 0);
}
Соберём всё воедино
Итак, все составляющие процедуры кодирования разобраны выше. Повторим ещё раз вкратце последовательность шагов. Здесь важно упомянуть, что для дальнейших измерений с целью сравнения производительности эта последовательность разбита на этапы. Измерения по этапам в самой программе я делал самым быстрым, известным мне, способом — чтением счётчика циклов CPU с помощью инструкции rdtsc.
- Запомнить точку во времени ts1 с помощью rdtsc.
- Заполнить очередь с приоритетом символами по числу их повторений.
- Построить дерево символов с помощью этой очереди. Удалить саму очередь.
- Вычислить число циклов t1, прошедшее с момента ts1, и запомнить следующую точку ts2.
- Построить таблицу кодирования, обходя дерево кодирования. Уничтожить дерево кодирования.
- Вычислить число циклов t2, прошедшее с момента ts2, и запомнить следующую точку ts3.
- Осуществить собственно кодирование входного потока, заменяя каждый входной символ последовательностью бит из таблицы кодирования.
- Вычислить число циклов t3, прошедшее с момента ts3.
Помимо подсчёта циклов по этапам есть ещё и общий таймер, замеряющий всё время кодирования входного буфера, использующий posix функцию clock_gettime.
Замеры и оптимизация
Нетерпеливый читатель, проглядевший столько кода выше, уже ёрзает на стуле, задаваясь вопросом: «Ну так что там получилось?». Попробуем запустить обе версии, скомпилированного компилятором gcc-5.4.0 с уровнем оптимизации «O3», упаковщика на файле размером около 31 Мб. Нужно отметить, что для кодирования можно выбирать разные размеры блока данных из входного файла. По умолчанию это 64 Кб. То есть, осуществляется кодирование 31 Мб / 64 Кб блоков, а все показатели времени суммируются.
> build-c/pack-c -m3 ../sample-1.dat data-c.dat
File packing is done. Read 31962362 bytes, written 32031809 bytes. Total ticks = 1053432 (0.754 seconds), t1 = 209957, t2 = 31023, t3 = 811377.
> build-cpp/pack-cpp -m3 ../sample-1.dat data-cpp.dat
File packing is done. Read 31962362 bytes, written 32031809 bytes. Total ticks = 1182005 (0.846 seconds), t1 = 228527, t2 = 52680, t3 = 894081
На опцию «-m3» можно не обращать внимание, это просто переключатель, означающий тестовый режим.
Ну что-ж, как-то не очень весело. То есть, C++ не дался бесплатно, провал по производительности порядка 12%. Все три этапа выполняются дольше, чем в C версии. А если размер блока выбрать поменьше, скажем, 1 Кб?
> build-c/pack-c -m3 -b1024 ../sample-1.dat data-c.dat
File packing is done. Read 31962362 bytes, written 31160081 bytes. Total ticks = 9397894 (6.731 seconds), t1 = 5320910, t2 = 1943422, t3 = 2094688.
> build-cpp/pack-cpp -m3 -b1024 ../sample-1.dat data-cpp.dat
File packing is done. Read 31962362 bytes, written 31160081 bytes. Total ticks = 11586220 (8.3 seconds), t1 = 6399593, t2 = 3125111, t3 = 1663035
Понятное дело, просело всё, потому что теперь нужно гораздо чаще перестраивать дерево кодирования. Но C опять вырвался вперёд — аж на 23%!
Оптимизация «на глазок»
Что не так с C++ реализацией? Вроде один компилятор, один и тот же оптимизатор там. По счётчикам циклов выше видно, что самый большой вклад дают шаги, где начинается манипуляция с битами. Класс bit_ostream получился хороший. Но при наполнении таблицы кодирования так ли хорош его, чрезмерно нагруженный для составления таблицы, метод push? Ведь положить массив бит в изначально пустой объект должно быть куда проще, чем весь код в том методе. Да и таблица кодирования, составленная из 256 сущностей этого класса, занимает гораздо больше места, чем 256 структур bits_line из C версии. Попробуем сделать вариант этого класса для таблицы кодирования.
class small_bit_ostream
{
unique_bytes_ptr m_data;
unsigned short m_bits_count = 0;
public:
small_bit_ostream& push(const unsigned char* bits, const unsigned short bits_count)
{
const auto cov_bytes {covered_bytes(bits_count)};
m_data.reset(new unsigned char[cov_bytes]);
std::memcpy(m_data.get(), bits, cov_bytes);
m_bits_count = bits_count;
return *this;
}
unsigned long bits_count() const noexcept { return m_bits_count; }
bool empty() const noexcept { return ! m_bits_count; }
unsigned char* data() noexcept { return m_data.get(); }
const unsigned char* data() const noexcept { return m_data.get(); }
};
Просто. Красиво. Ничего лишнего. Даёт ли это хоть что-то? (Не тронутую C версию не привожу тут.)
> build-cpp/pack-cpp -m3 ../sample-1.dat data-cpp.dat
File packing is done. Read 31962362 bytes, written 32031809 bytes. Total ticks = 1173692 (0.84 seconds), t1 = 229942, t2 = 46677, t3 = 890323
> build-cpp/pack-cpp -m3 -b1024 ../sample-1.dat data-cpp.dat
File packing is done. Read 31962362 bytes, written 31160081 bytes. Total ticks = 11198578 (8.02 seconds), t1 = 6404650, t2 = 2752852, t3 = 1641317
Ну что, для большого блока улучшение — на уровне погрешности. Для маленького блока улучшение чуть заметнее — теперь C++ хуже всего на 19%. Видно по показателю t2, что заполнение таблицы стало лучше работать.
Профилирование
Начнём с проверки, как поживают кэши CPU. Запустим обе версии ПО под valgrind'ом с инструментарием «cachegrind». Вот краткий вывод для C версии.
==2794== I refs: 2,313,382,347
==2794== I1 misses: 14,482
==2794== LLi misses: 1,492
==2794== I1 miss rate: 0.00%
==2794== LLi miss rate: 0.00%
==2794==
==2794== D refs: 601,604,444 (472,330,278 rd + 129,274,166 wr)
==2794== D1 misses: 3,966,884 ( 2,279,553 rd + 1,687,331 wr)
==2794== LLd misses: 7,030 ( 3,034 rd + 3,996 wr)
==2794== D1 miss rate: 0.7% ( 0.5% + 1.3% )
==2794== LLd miss rate: 0.0% ( 0.0% + 0.0% )
==2794==
==2794== LL refs: 3,981,366 ( 2,294,035 rd + 1,687,331 wr)
==2794== LL misses: 8,522 ( 4,526 rd + 3,996 wr)
==2794== LL miss rate: 0.0% ( 0.0% + 0.0% )
==2794==
==2794== Branches: 299,244,261 (298,085,895 cond + 1,158,366 ind)
==2794== Mispredicts: 8,779,093 ( 8,778,920 cond + 173 ind)
==2794== Mispred rate: 2.9% ( 2.9% + 0.0% )
А вот и вывод для C++ версии с теми же параметрами:
==2994== I refs: 2,464,681,889
==2994== I1 misses: 2,032
==2994== LLi misses: 1,888
==2994== I1 miss rate: 0.00%
==2994== LLi miss rate: 0.00%
==2994==
==2994== D refs: 633,267,329 (491,590,332 rd + 141,676,997 wr)
==2994== D1 misses: 3,992,071 ( 2,298,593 rd + 1,693,478 wr)
==2994== LLd misses: 8,292 ( 3,173 rd + 5,119 wr)
==2994== D1 miss rate: 0.6% ( 0.5% + 1.2% )
==2994== LLd miss rate: 0.0% ( 0.0% + 0.0% )
==2994==
==2994== LL refs: 3,994,103 ( 2,300,625 rd + 1,693,478 wr)
==2994== LL misses: 10,180 ( 5,061 rd + 5,119 wr)
==2994== LL miss rate: 0.0% ( 0.0% + 0.0% )
==2994==
==2994== Branches: 348,146,710 (346,241,481 cond + 1,905,229 ind)
==2994== Mispredicts: 6,977,260 ( 6,792,066 cond + 185,194 ind)
==2994== Mispred rate: 2.0% ( 2.0% + 9.7% )
Можно заметить, что по попаданию в кэш и по данным и по инструкциям C++ не хуже, а иногда даже и лучше, чем C код. Предсказание переходов вообще лучше работает. А почему же он проваливается слегка? Очевидно, что в нём просто выполняется больше инструкцкий — 2 464 млн. против 2 313. Что и даёт примерно ту разницу в производительности, что была заметна при использовании больших блоков.
При анализе инструментарием «callgrind» видно, что много инструкций тратится на работу с кучей — malloc и free. Но помимо этого в C++ версии встречаются ещё и значительные, с точки зрения инструкций, упоминания операторов new и delete. А всегда ли они нужны? Те самые операции с битовыми массивами, что отдельно упоминались выше, реализованы с использованием авто указателя unique_ptr, для которого память выделяется с помощью new[]. Вспомним, что данный оператор внутри обращается к C-шному malloc, а затем инициализирует каждый объект в созданном массиве. То есть в нашем случае заполняет массив нулями. А зачем это программе? Класс bit_ostream сразу после получения массива заполняет его битами, дописывая их в конец. И хранит счётчик записанных бит. Ему вовсе не нужно, чтобы массив байт был предварительно очищен. Попробуем написать простейший адаптер для управления памятью через malloc / free, но с использованием unique_ptr, чтобы так же удобно не думать о её очистке.
struct free_deleter
{
void operator()(void* p) const noexcept { std::free(p); }
};
template <class T> inline T* allocate_with_malloc(std::size_t size)
{
T* res = static_cast<T*>(std::malloc(sizeof(T) * size));
if (! res)
throw std::bad_alloc();
return res;
}
template <class T>
using unique_malloc_array_ptr = std::unique_ptr<T[], free_deleter>;
template <class T>
inline unique_malloc_array_ptr<T> unique_allocate_with_malloc(std::size_t size)
{
return unique_malloc_array_ptr<T>(allocate_with_malloc<T>(size));
}
// Typedefs for byte arrays
using unique_bytes_ptr = unique_malloc_array_ptr<std::uint8_t>;
inline unique_bytes_ptr allocate_bytes(std::size_t size)
{
return unique_bytes_ptr(unique_allocate_with_malloc<std::uint8_t>(size));
}
Проверим предположение на том же файле с кодированием большими и малыми блоками (как и прежде, C версия не менялась, так что её не привожу).
> build-cpp/pack-cpp -m3 ../sample-1.dat data-cpp.dat
File packing is done. Read 31962362 bytes, written 32031809 bytes. Total ticks = 1042665 (0.746 seconds), t1 = 250480, t2 = 45393, t3 = 740163
> build-cpp/pack-cpp -m3 -b1024 ../sample-1.dat data-cpp.dat
File packing is done. Read 31962362 bytes, written 31160081 bytes. Total ticks = 11068384 (7.93 seconds), t1 = 6488100, t2 = 2694562, t3 = 1501027
Ну что-ж, на больших блоках C++ реализация обогнала C! На малых всё пока что хуже, хотя лучше, чем в предыдущем эксперименте. Количество инструкций на всю программу — 2 430 млн. вместо 2 464. Количество обращений к данным тоже сократилось с 633 млн. до 536. Понятно, что на малых блоках новая реализация практически осталась как была — там же в основном играет роль построение дерева кодирования, а его код не менялся.
Ещё пару капелек
Обратим внимание на очередь с приоритетом, которую так красиво и лаконично удалось реализовать на C++. Она, как и всё остальное, использует авто указатели для управления памятью. Есть один главный указатель m_nodes, который указывает на массив указателей на узлы. В ходе выполнения любой изменяющей операции содержимое конечных указателей переставляется, как правило, выражением ptr1 = std::move(ptr2). Что тут «зарыто»? Указатель ptr1 должен проверить, что он ни на что не указывает, в противном случае удалить ресурс. Указатель ptr2 должен обнулиться после того, как ресурс у него заберут. Да, это малое количество инструкций, тут почти не о чем разговаривать. Но! Во всех операциях с очередью строго известно, когда и что на что указывает. Поэтому таких проверок и обнулений делать не надо. А копирование сырых указателей занимает одну (!) инструкцию. Давайте заменим конечные указатели в очереди с приоритетом на сырые и прогоним тесты ещё раз.
> build-cpp/pack-cpp -m3 ../sample-1.dat data-cpp.dat
File packing is done. Read 31962362 bytes, written 32031809 bytes. Total ticks = 1008990 (0.722 seconds), t1 = 221001, t2 = 44870, t3 = 736557
> build-cpp/pack-cpp -m3 -b1024 ../sample-1.dat data-cpp.dat
File packing is done. Read 31962362 bytes, written 31160081 bytes. Total ticks = 10683068 (7.65 seconds), t1 = 6101534, t2 = 2689178, t3 = 1505929
Ну что-ж, на больших блоках C++ быстрее на 4,3%, на малых — медленнее всего на 13,6%. Инструкций теперь 2 413 млн., обращений к данным — 531 млн.
Заключение
К каким мыслям я пришёл по ходу такого сравнительного анализа на примере задачки по кодированию Хаффмана?
- Сначала обе версии программы я реализовал «в лоб», не особенно задумываясь о каких-то специфических оптимизациях. Но так получилось, что C версия сразу получилась быстрее, а C++ я «дотягивал» до неё, изучал, профилировал и т. п. В результате я получил в среднем такое же быстрое решение. (Я думаю, что и этап построения дерева кодирования можно «допилить», чтобы он не «провисал» по скорости.) Но я хотел отметить то, что сам процесс написания программы на C «вёл меня» по пути создания быстрого кода, а в случае C++ пришлось заниматься дальнейшим анализом.
- Тем, кто хорошо знает C++, писать на нём гораздо удобнее, чем на C. Программы получаются лаконичнее и они лишены множества потенциальных ошибок, которые можно сделать на C. По ходу написания и отладки C программы я столкнулся с множеством (сравнивая с C++) случаев некорректного использования указателей, обращения к очищенной памяти, неверного преобразования типов. В хорошо типизированной C++ программе по максимуму действует правило — компилируется, значит корректна. Удаление сложных структур вместе с механизмом исключений — вообще сила, потому что здесь не нужно ни строчки пользовательского кода (разве что вывести сообщение об ошибке), а программа корректно обрабатывает такие ситуации «из коробки».
- Заметить, что что-то работает медленно в ходе профилирования очень сложно, потому что это субъективная оценка. У меня было две реализации, и я мог сравнить эквивалентные шаги. Но в реальности будет только одна реализация, потому что в начале выбрали для неё язык «XYZ». Как понять, быстро она работает, или медленно? Сравнить то не с чем. Если бы я написал только C++ реализацию и в конце замерил, что она обрабатывает 31 Мб за 0.85 секунды, я бы сразу считал, что это эталон скорости!
- Что же касается лично моих предпочтений при написании программ в будущем, то здесь подход следующий. Если мне нужно написать «молотилку», действия которой в основном будут состоять из миллионов похожих действий, то лучше писать её в C стиле, чтобы увидеть/реализовать самостоятельно все, пусть даже самые незначительные, шаги. Ведь каждая лишняя инструкция тут на миллионах повторений даст просадку. Если же я пишу сложную управляющую логику с очень разнообразными действиями, не сводящимися к «повторить вычисления A, B, C миллион раз», то лучше взять на вооружение всю мощь типизированного C++. Потому что конечное время работы такой программы уже не будет сводиться к вопросу «а за сколько времени она обработает терабайт данных», управляющая логика будет зависеть от множества внешних факторов и сценариев использования. И говорить о точных скоростных характеристиках не придётся. А вот корректность такой логики «из коробки» будет в сто крат ценнее, потому что никому не захочется вычищать из неё баги в C версии до скончания веков. И иметь в конце концов «жёсткую» версию кода, которую невозможно изменить, адаптировать под новые нужды, потому что, где бы ни тронул, всё посыпется. И начинай отладку сначала.
P.S. Исходный код можно взять тут: http://corosan.ru/data-exp/haffman_pack_for_article.tar.bz2
Update 1. По просьбам в комментариях я проверил работу упаковщиков, собранных компилятором clang-3.8.0. Результаты таковы.
C версия:
> build-c/pack-c -m3 ../sample-1.dat data-c.dat
File packing is done. Read 31962362 bytes, written 32031809 bytes. Total ticks = 1139373 (0.816 seconds), t1 = 206305, t2 = 29559, t3 = 902493.
Неоптимизированная C++ версия:
> build-cpp/pack-cpp -m3 ../sample-1.dat data-cpp.dat
File packing is done. Read 31962362 bytes, written 32031809 bytes. Total ticks = 1417576 (1.01 seconds), t1 = 223441, t2 = 53057, t3 = 1134400
Оптимизированная C++ версия:
> build-cpp/pack-cpp -m3 ../sample-1.dat data-cpp.dat
File packing is done. Read 31962362 bytes, written 32031809 bytes. Total ticks = 1174028 (0.84 seconds), t1 = 215059, t2 = 59738, t3 = 892821
Относительный расклад сил не меняется, а в абсолютном плане clang генерирует код чуть-чуть медленнее, чем gcc.
