Введение

Идея поста появилась после обсуждения дженериков в java с Slamur. Он продемонстрировал на примере задачи 20C - Алгоритм Дейкстры? скорость работы кода с дженериками и без. Большая ли получилась разница, судите сами. Вот код с дженериками и без. Внятных объяснений разницы я загуглить не смог, поэтому тех, кто знает в чем дело, прошу разьяснить ситуацию. После этого я заинтересовался: а как обстоят дела с шаблонами C++? Да и не только с ними, но и вокруг них. Итак...

Поехали

Шаблоны C++ есть только в коде. В исполняемом файле их уже нет. Для каждого нужного типа создается свой класс/структура или функция. Тестировать различные способы я решил все на той же задаче про алгоритм Дейкстры(сначала). После измерил у себя искуственную задачу, но об этом позже. Изначальное желание просто протестировать реализацию с шаблонами и без вылилось в более широкий набор интересностей.

• Реализация полностью на стандартных структурах данных
• Своя шаблонная пара
• Своя не шаблонная пара
• Своя не шаблонная пара + свой не шаблонный контейнер
• И наконец своя куча + свои пары, все не шаблонное

Стандартные структуры данных

Тут в общем-то рассказывать нечего. Просто протокол тестирования. Отмечу только время работы: 140 мс.

Свои шаблонные пары

Не раз видел комментарии, что std::pair — это тормозящая лажа. Я хоть и относился к ним с недоверием, но наивно полагал, что это не голословные утверждения. Точнее, полагал до тех пор, пока не заглянул в их исходный код. А вот и он. Да, выглядит страшно и непонятно, но если поразбираться, то становится совсем непонятно, почему же это они "тормозят". Однако я все равно решил написать свои шаблонные пары, и протестить их.

template<typename T, typename U>
struct Pair {
  T first;
  U second;
  
  Pair()
  { }
  
  Pair(T f, U s) :
    first(f),
    second(s)
  { }
  
  bool operator < (Pair<T, U> o) {
    return first < o.first 
        || (first == o.first && second < o.second);
  }
  
  bool operator > (Pair<T, U> o) {
    return first > o.first 
        || (first == o.first && second > o.second);
  }
  
  bool operator == (Pair<T, U> o) {
    return first == o.first && second == o.second;
  }
};

template<typename T, typename U>
Pair<T, U> make_Pair(T f, U s) {
  return Pair<T, U>(f, s);
}

Вот так они реализованы у меня. А теперь смотрим на протокол тестирования. Хм, те же 140 мс. Все получилось так же, как и со стандартными. Я не утверждаю, что стандартные плюсовые пары — идеал оптимизации, но они как минимум ничем не хуже своих "обычных" пар.

Уходим от шаблонов

Теперь давайте посмотрим, как поведут себя пары без шаблонов. Код прямо здесь приводить не буду, будет ссылка на посылку. Итог получился не сильно быстрее: 125 мс. Разница небольшая. Критично это или нет, наверное, стоит смотреть в индивидуальном порядке.

Финт ушами

Давайте вспомним, как объявляется очередь с приоритетами.
prioriry_queue< тип, контейнер, компаратор > С типом мы уже разобрались, это наши любимые не шаблонные пары. Компаратор тоже понятен. Давайте напишем свой контейнер на массиве, чтобы не происходили постоянные реаллокации. Для меня это было интересным опытом :) Сначала я написал то, что думаю, потом пытался скомпилить и исправлял вылезающие ошибки. И все-таки это удалось (:

struct cont {
  typedef Pair value_type;
  typedef Pair& reference;
  typedef const Pair& const_reference;
  typedef int size_type;
  
  int sz;
  Pair a[LIM];
  
  cont() :
    sz(0)
  { }
  
  value_type* begin() {
    return a;
  }
  
  value_type* end() {
    return a + sz;
  }
  
  void push_back(Pair x) {
    *(a + sz) = x;
    sz++;
  }
  
  void pop_back() {
    sz--;
  }
  
  const value_type front() {
    return *a;
  }
  
  size_type size() const  {
    return sz;
  }
  
  const_reference front() const  {
    return *a;
  }
  
  bool empty() const {
    return sz == 0;
  }
};

Результат получился интересный. 109 мс, но разница все равно небольшая...

Все мое!

Просто ссылка, результат не впечатлил. 156 мс. Не сильно, но дольше.

Поехали, дубль 2

Хорошая, конечно, задача, но там есть и еще всякие факторы, влияющие на время, да и данных не так много, да и тесты не идеальные. И вот, что сделал: создал файл, на достаточно большое количество данных и протестировал все на нем. Создавал так:

fout = open("in", "w")

arr = [100, 1000, 10000]

for m in arr:
    for i in xrange(1, m + 1):
        for j in xrange(1, m + 1):
            fout.write(str(i) + " " + str(j) + '\n')

Компилировал плюсовые коды так:

g++ -O2 -Wall -o "a" "a.cpp"

И вот, что получилось:

1) Только STL

2) Мои шаблонные пары

3) Мои не шаблонные пары

4) Мой контейнер

5) Моя очередь с приоритетами

Выводы

Ну что тут сказать... Мой код не претендует на премию за чудеса оптимизации, но он и не самый худший из того, что можно было бы написать. На мой взгляд разница совсем не существенная, что показало "тяжелое" тестирование. Особенно если принять во внимание, что на результаты влиял не только код, но и общее поведение системы(да и хром работал). Пожалуй, сказать можно только то, что моя реализация кучи проигрывает стандартной :) А остальное практически идентично отработало. Итого: STL — добро! Критика приветствуется. Все еще помните вопрос про дженерики в java? Очень хочется узнать ответ.