Оптимизация кода на C++ (C++11) на примере конкретной задачи

Хочется немного рассказать про оптимизацию С/C++ программ, ибо в интернете довольно мало информации. В посте будут объяснения некоторых оптимизаций на примере задачи, которую мне дали решить в институте (задача реализована на С++11, объяснение дается только для 64 битных систем).
В первую очередь статья писалась, чтобы больше узнать про оптимизацию, советы по которой, я надеюсь, вы оставите в комментариях.

Условие задачи и цель

Задача довольно тривиальна:

В городе M строятся N новых микрорайонов, между которыми запланировано M магистральных дорог. Каждая дорога имеет свою стоимость строительства Pij. В прошлом году из этих M дорог муниципалитет успел построить K штук. К сожалению, в этом году финансирование строительства решено было сократить, и теперь из запланированных, но непостроенных M-K дорог нужно оставить такие, чтобы из любого микрорайона в любой другой существовал хотя бы один путь, но при этом стоимость их строительства была минимальной (гарантируется, что такой набор существует).
Какова минимальная стоимость P завершения строительства дорожной сети по новому плану, и сколько новых дорог по нему предстоит построить?

и решается алгоритмом Крускала (построение минимального остовного дерева). Изначально в контесте были ограничения в 2 секунды на исполнение и 24 мб памяти. Не серьезно. Перед собой я поставил цель максимально оптимизировать программу и уложиться в 100мс для самого сложного теста, хочу заметить, что использовать можно только STL библиотеку и фиксированные настройки компилятора (как никак это задача из контеста). Поставленная задача была выполнена не до конца — я уложился в 122 мс и 11мб памяти. Для самых нетерпеливых привожу код программы:

#include <iostream> #include <vector> #include <algorithm>  /*  * Данная структура обусловлена форматом входных данных  */ template <class T> struct Triplet {     T first;   // Город, в котором дорога начинается     T second;  // Город, в котором дорога заканчивается     T third;   // Цена строительства дороги };  /*  * Каждый элемент UnionFind это множество  */ template <class T> class UF_element { public:     T parent;   // представитель множества     T size;     // размер множества      UF_element() {}      UF_element(T id)             : size(1)             , parent(id)     {     } };  template <class T> class UnionFind { private:     std::vector<UF_element<T>> Elements; public: /*  * Сначала город состоит из микрорайонов не соединенных дорогами  */     UnionFind(T n)             : Elements(n + 1)     {         for (register T i = 1; i < n + 1; ++i) {             Elements[i] = UF_element<T>(i);         }     }  /*  * При первом вызове поиска родителя, сокращаем путь до него.   *     первый поиск за О(log n),  *     последующие вызовы за O(1)  */     T find(T id){         UF_element<T>& current = Elements[id];          while (current.parent != Elements[current.parent].parent){             current.parent = Elements[current.parent].parent;         }         return current.parent;     }      void merge(T a, T b) {         UF_element<T>& UF_elem_A = Elements[find(a)];         UF_element<T>& UF_elem_B = Elements[find(b)];          if(UF_elem_A.parent == UF_elem_B.parent)             return;          if(UF_elem_A.size < UF_elem_B.size) {             UF_elem_A.parent = b;             UF_elem_B.size += UF_elem_A.size;         } else {             UF_elem_B.parent = a;             UF_elem_A.size += UF_elem_B.size;         }     } };  template <typename T> bool comp(const Triplet<T>& a, const Triplet<T>& b) {     return (a.third < b.third); }  template <typename T> void kruskal(std::vector<Triplet<T>>& data, size_t& cost, size_t& count, const size_t& n) {     UnionFind<T> N(n);      for (size_t i = 0; i < data.size(); ++i) {         if (N.find(data[i].first) != N.find(data[i].second)) {             if (data[i].third) {         // если стоимость дороги не 0 (т.е дорога еще не построена)                 cost += data[i].third;   // увеличиваем стоимость постройки дорог                 ++count;                 // увеличиваем количество дорог, которые надо построить             }              N.merge(data[i].first, data[i].second);         }     } }  /*  * Парсер для любых неотрицательных целочисленных типов  */ template <typename T> void read_unlocked(T &out) {     T c = getchar_unlocked();      for (; '0' <= c && c <= '9' ; c = getchar_unlocked()) {         if (c == ' ' || c == '\n')             return;         out = out * 10 + c - '0';     } }  int main() {     std::ios_base::sync_with_stdio(false);      size_t count = 0, cost = 0;     unsigned int n, m;      read_unlocked(n);     read_unlocked(m);      std::vector<Triplet<unsigned int>> input(m);      for (size_t i = 0; i < m; ++i) {         read_unlocked(input[i].first);         read_unlocked(input[i].second);         read_unlocked(input[i].third);     }      std::sort(input.begin(), input.end(), comp<unsigned int>);     kruskal(input, cost, count, n);      std::cout << cost << " " << count << '\n'; } 

Выравнивание данных

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

struct A {     char a;     long int b;     int c; }; 

Эта структура занимает 24 байта (для этого выведем на экран результат sizeof(A)).
Теперь рассмотрим такую структуру:

struct B {     char a;     int c;     long int b; }; 

Она занимает всего 16 байт. Почему так? Дело в том, что на 64 битной ОС память считывается кусками по 8 байт и для ускорения обработки процессором идет выравнивание данных, конкретно для класса А структура расположения в памяти выглядит так:
(1 байт под a + 7 пустых байт) + (8 байт под b) + (4 байта под c + 4 пустых байта) = 24 байта.
Не очень экономно, правда? Для класса B занимаемая память выглядит так:
(1 байт под a + 3 пустых байта + 4 байта под c) + (8 байт под b) = 16 байт.
На такую мелочь стоит обращать внимание, потому что перемещение данных «туда-сюда» стоит времени и чем меньше данных перемещается, тем сильнее ускоряется ваша программа, да и потом, поменять местами пару строчек не самая сложная оптимизация.

Списки инициализации

Почему конструктор должен выглядеть так:

UF_element(T id)         : size(1)         , parent(id) { } 

А не так:

UF_element(T id) {     size = 1;     parent = id; } 

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

Спецификатор register

Немножко теории:

register — спецификатор автоматического класса памяти. Применяется к объектам, по умолчанию располагаемым в локальной памяти. Представляет из себя «просьбу»(необязателен к исполнению) к компилятору о размещении значений объектов, объявленных со спецификатором register в одном из доступных регистров, а не в локальной памяти.

В своем коде я использовал такую конструкцию:

for (register T i = 1; i < n + 1; ++i) {     idElements[i] = UF_element<T>(i); } 

Использовать этот спецификатор надо грамотно.
Если надо забить массив числами от 1 до n (почти как у меня в примере выше), то использование спецификатора даст прибавку в скорости, если тело цикла не такое тривиальное, то скорее всего register не только не изменит производительность, но может и уменьшить его, выделив под переменную регистр.

Работа с памятью

Очень коротко и хорошо написано тут. Вообще, когда начинаешь разбираться как программа использует память и, в особенности, ищешь утечки, вырабатываются некоторые правила. Для себя я уяснил одно: до тех пор, пока программист не в состоянии с ходу сказать когда и где освобождается память, выделенная с помощью оператора new и насколько удобно будет менеджеру памяти обращаться к освободившейся памяти после вызова delete, его надо бить ссаными тряпками за использование new/delete. Поэтому, чтобы не быть побитым, я избавился от использования этих операторов архитектурно:

 UnionFind(T n)             : Elements(n + 1) // тут я выделяю нужный мне кусок памяти     {         for (register T i = 1; i < n + 1; ++i) {             Elements[i] = UF_element<T>(i); // тут его заполняю         }     } 

Ввод и вывод данных

Руководствуясь этой статьей был значительно ускорен ввод. Так как в данной задаче выводятся только 2 числа, то использование putchar (putchar_unlocked) большого профита не приносит, но для тех кто не поверит, пока не проверит, привожу ниже реализацию вывода с использованием putchar_unlocked.

/*  * Подходит для всех неотрицательных целочисленных типов:  *     первый параметр - это число, которое необходимо вывести  *     второй параметр - это символ, который надо добавить после числа  */ template <typename T> void write_unlocked(T inp, char last=' ') {     if (!inp) {         putchar_unlocked('0');         putchar_unlocked(last);         return;     }      T out = 0;     unsigned char sz_inp = 0;     // переворачиваем число     for (; inp; inp /= 10, ++sz_inp) {         out = (out << 3) + (out << 1) + inp % 10;     }     // печатаем число     for (; out; out /= 10, --sz_inp) {         putchar_unlocked(out % 10 + '0');     }     // выводим нули, если они были в числе     for (;sz_inp; --sz_inp) {         putchar_unlocked('0');     }      putchar_unlocked(last); } 

ссылка на оригинал статьи http://habrahabr.ru/post/256929/