[comp.prog.cpp] SCARY assignments: очередной акроним для C++

Прочитал статью Б.Страуструпа и Co Minimizing Dependencies within Generic Classes for Faster and Smaller Programs. Статья большая. В лучших традициях – с введением, подробным описанием, примерами программ, статистическими выкладками и графиками. И, как мне показалось, написанная обычным для Страуструпа стилем – после первого прочтения не понятно, что к чему. А через несколько прочтений не только все понятно, но и удивительно, почему так хорошо написанный текст не воспринимался в первый раз.

Итак, SCARY assignments. Что это за зверь? Оставляю общую формулировку так, как она приведена в стать, ибо переводить эту штуку на русский не возьмусь:

The acronym SCARY describes assignments and initializations that are Seemingly erroneous (appearing Constraibed by conflicting generic parameters), but Actually work with Right implementation (unconstrained bY the conflict due to minimized dependencies).

Не смотря на кажущуюся запутанность формулировки возьму на себя смелость утверждать, что речь идет о достаточно простой штуке. Хотя я об этом приеме раньше не слышал (как всегда – когда кто-то тебе рассказывает суть хитрого фокуса, все сразу становится просто и очевидно).

Предположим, что у нас есть некоторый set<int, C1, A1> и похожий на него set<int, C2, A2>. Различаются они только типами компараторов и аллокаторов. Поскольку итераторы для этих типов так же зависят от шаблонных параметров, то, по первому предположению, эти итераторы будут не совместимы между собой по типам:

set< int, C1, A1 >::iterator a;
set< int, C2, A2 >::iterator b;
a = b; // Разве это легально?

Вот такое присваивание a = b и является SCARY assignment. На первый взгляд, оно нелегально, поскольку итераторы принадлежат разным типам. Но, оказывается, причин для препятствования такому присваиванию, с технической точки зрения, не много. Ведь итераторы нужны только для обхода дерева. В процессе обхода дерево не модифицируется, поэтому ни компараторы, ни аллокаторы в этом процессе не задействованы. Следовательно, можно пропробовать “отвязать” тип итератора от шаблонных параметров C и A. Например, так:

template< class T >
class non_const_tree_iterator
  { ... };
template< class T, class Comparator, class Allocator >
class set
  {
  public :
    typedef non_const_tree_iterator< T > iterator;
    ...
  };

Или так:

template< class T >
class basic_search_tree
  {
  public :
    class iterator
      { ... };
  };
template< class T, class Comparator, class Allocator >
class set : public basic_search_tree< T >
  { ... };

В этом случае оказывается, что итераторы для разных set<T> будут совместимы между собой даже если эти set<T> будут использовать разные параметры C и A.

Что же это дает? Уменьшение кода, получаемого в результате инстанциирования шаблонов и ускорение его работы. В статье приводится пример простой реализации ассоциативного контейнера, который позволяет хранить информацию, упорядоченную по нескольким ключам (что-то вроде boost.multi_index). Замеры производительности показывают, что реализованные в стиле SCARY итераторы работают от 1.2 до 2.1 быстрее “обычных” STL итераторов.

Для исследования того, насколько можно уменьшить объем результирующего объектного кода, авторы статьи использовали технику template hoisting. Ее суть в том, что если у нас есть set<T, C, A>, то часть методов этого класса вообще не будут зависеть от шаблонных параметров (например, метод size()). Часть методов будут зависеть только от T, часть от T и C, часть от T и A, а часть от всех трех. Поэтому класс set можно выразить через несколько классов путем наследования.

Так, авторы статьи модифицировали класс Rb_tree из GCC STL для проверки своей идеи, и получили:

• базовые классы Rb_base<T> и Rb_alloc<T, A>;
• класс Rb_cmp<T, C>, производный от Rb_base<T>;
• класс Rb_tree<T, C, A>, производный от Rb_cmp<T, C> и Rb_alloc<T, A>.

Такое разбиение приводит к тому, что для множества различных std<int> в приложении будет всего одна реализация Rb_base<int>. Для множества std<int, less_than> в приложении будет всего одна реализация Rb_cmp<int, less_than> и т.д. Что может приводить к очень существенному (до 25-кратного в некоторых тестах) сокращению объектного кода.

В заключении статьи авторы говорят о том, что подобные техники могут оказаться полезными не только для C++, но и для других языков программирования, поддерживающих обобщенное программирование. Например, для C# и D.

PS. Мне в статье понравилось еще вот что. Говоря про SCARY и соответствующие итераторы авторы приводят пример их использования в реальном приложении. Это приложение является имитатором диспетчера задач для суперкомпьтеров (типа IBM BlueGene). Для имитации используются логи загрузки задач с реальных суперкомпьютеров. Т.е., как начинал Страуструп использовать C++ для имитационного моделирования, так и продолжает делать это до сих пор.