Моя жизнь с Boost Graph Library

Статья, первая часть которой здесь представлена, содержит различные соображения автора, накопившиеся в ходе длительной разработки специализированной системы поиска социальных связей, базирующейся на библиотеке Boost Graph Library (BGL). В этом (техническом) разделе суммируются впечатления автора от работы с этой библиотекой, поднимаются вопросы инструментовки при создании графовых приложений и затрагиваются некоторые практические проблемы метапрограммирования на C++.

BGL и с чем его едят

Шаблонная библиотека BGL ^[1] наверняка известна любому разработчику, сталкивавшемуся с графовыми задачами. Появившись в составе Boost 1.18.1 в 2000 году, она сразу же заслужила одобрительные отзывы таких классиков жанра, как Александр Степанов. Руководство к библиотеке, составленное Джеререми Сиком, Лай-Кваном Ли и Эндрю Ламсдейном вышло в русском переводе в 2006 в издательстве «Питер» (оригинал – Jeremy G. Siek, Lie-Quan Lee и Andrew Lumsdaine, «The Boost Graph Library», 2001, Addison-Wesley). Библиотека интенсивно обновлялась и развивалась практически до конца 2013 года (Boost 1.55.0). В частности, в 2005 году появился анонс ее распределенной версии (PBGL), которая вошла в состав Boost с версии 1.40 в 2009 году и по сию пору остается чем-то вроде стандарта де-факто для графовых вычислений на высокопроизводительных кластерах, во всяком случае, в академическом мире. Насколько можно судить по истории коммитов, до 2005 года основным разработчиком библиотеки был Джерерми Сик, после 2005 – Дуглас Грегор (Douglas Gregor), а вообще в разное время над библиотекой работало немалое количество разнообразного люда. Посвященные ей публикации неоднократно появлялись и на habr.com: в первую очередь нужно отметить серию статей Вадима Андросова: [1 ^[2], 2 ^[3], 3 ^[4]]. Таким образом, библиотеке в принципе посвящена хорошая и разнообразная литература, но собственная ее документация, также, вообще говоря, довольно обширная, несколько страдает из-за того, что:

1. Ее оглавление и корневые разделы, претендущие на то, чтобы давать исчерпывающий перечень ключевых сущностей, не изменялись с самого 2001 года. Например, автор этих строк, наивно поверивший, что:
   

   The BGL currently provides two graph classes and an edge list adaptor:

   adjacency_list
   adjacency_matrix
   edge_list

   , спустя некоторое время с удивлением обнаружил реализованное еще в 2005 году представление compressed_sparse_row_graph (разряженную матрицу). Аналогичная история имела место с алгоритмом Брона-Кербоша. Не верьте оглавлениям, используйте прямой поиск по заголовочным файлам;

2. Отсутствия единого комментированного перечня внутренних категорий библиотеки (container_category, parallel_edge_traits, iterator_stability и т. д., и т. п.), необходимых для реализации собственных представлений. Проблемы с пониманием происходящего настигают, видимо, всех пользователей библиотеки, желающих копнуть поглубже, что приводит к появлению «как бы работающего кода», доведение которого до вполне завершенного состояния отнимает много сил и времени: см., например, типичное обсуждение ^[5].

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

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

Нужно с сожалением отметить, что в настоящее время основные разработчики, видимо, утратили интерес к дальнейшей работе над библиотекой и последние шесть лет она, отнюдь не исчерпав потенциала своего развития и даже не освободившись вполне от внутренних несогласованностей и прямых ошибок, находится в свободном полете. Озвучивавшиеся в районе 2011 года планы по существенному расширению набора методов и покрытию новых областей теории графов (в том числе за счет добавления внутренней поддержки graph partitioning к возможности читать формат METIS) остались нереализованными. Представляется также, что библиотека могла бы многое выиграть (как минимум, в отношении читаемости) от широкого использования новинок, вошедших в стандарт после 2011 года.

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

Ситуация эта вызывает некоторую печаль, т. к. создание универсального механизма, подобного BGL, само по себе является своего рода интеллектуальным подвигом, и как по мощности подхода, так и по богатству арсенала реализованных универсальных методов (добрых полторы сотни однопоточных и пара десятков распределенных) библиотека, насколько известно автору сих строк, по прежнему не имеет себе равных.

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

Слово «принципиально» здесь использовано не без причины. Рассматривая конкретную ситуацию на примере уже упоминавшегося выше многострадального класса compressed_sparse_row_graph, можно отметить, например, следующие отступления от высоких стандартов:

1. Оператор [] для списка смежности и разряженной матрицы по-разному обрабатывают внутренние и внешние свойства ребер (Internal and Bundled Properties): первый возвращает только внешние свойства (внутренние доступны только при помощи property_map), второй возвращает обрамляющую структуру property, содержащую общий перечень свойств.
2. Функция get для получения индекса ребра при помощи boost::property_map<compressed_sparse_row_graph, boost::edge_index_t>::type попала в boost::detail, а не в boost, как во всех прочих случаях.

Наконец, в шаблоне compressed_sparse_row_graph осталась нереализованной специализация для ненаправленного графа (boost::undirectedS).

В связи с этим при использовании свойства edge_index (порядкового номера ребра) дополнительные сложности возникают из-за того, что для списка смежности данное свойство должно явно задаваться как внутреннее и как таковое может изменяться по произволу, но для ненаправленного графа его значение не зависит от направления, в котором проходится ребро. Для разряженной же матрицы (всегда направленной) оно является встроенной константной property_map специального вида (вычисляющейся как индекс в массиве ребер). Соответственно, значения для встречных ребер (представляющих ненаправленный граф) не могут изменяться и всегда будут различными.

Все эти расхождения приводят к невозможности «простой замены представления графа на эквивалентное» при вызове алгоритмических функций, что существенно подрывает основное преимущество библиотеки. На практике в подобных случаях требуется либо избыточная специализация кода, либо его переработка для исключения элементов с различающимся поведением, либо такая подстройка шаблонов графов, чтобы они при различающихся определениях атрибутов «вели себя одинаково», либо, наконец, вынос из библиотеки отдельных файлов и создание «личной версии boost».

Дополнительно можно отметить следущие, не столь существенные, неудобства:

• Размерности внутренних дескрипторов графовых представлений оказывают существенное влияние на расход памяти, необходимой для хранения графа, а иногда и сказываются на производительности алгоритмов.

  Некоторые представления (тот же compressed_sparse_row_graph) позволяют управлять этими размерностями. Другие же (adjacency_list) не имеют подобных параметров и всегда используют 64-разрядные целые (как правило, избыточные), заменить которые невозможно без модификации кода;

• Несмотря на то, что авторы библиотеки предусмотрели очень и очень многое, некоторые явно необходимые примитивы в библиотеку не вошли. Например, отсутствует функция наподобие reverse_edge, выполняющая обращение ребра.

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

• Равным образом из библиотеки выпали некоторые далеко не бесполезные сценарии. Например, можно определить реберные предикаты, при помощи filtered_graph превращающие ненаправленный граф в направленный, но нет возможности довести эту трансформацию до сведения библиотеки. Соответственно, штатные алгоритмы для направленных графов не будут компилироваться с таким объектом, а алгоритмы для ненаправленных графов будут работать с ним неправильно.

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

• Что касается функции reverse_edge, взятой выше в качестве пример, то имеется и нисколько не невероятный вариант, что нужная функция присутствует где-нибудь в недрах библиотеки, но по каким-то причинам получила неочевидное имя. Это подводит к следующей проблеме, на первый взгляд несерьезной, но существенно замедляющей работу со сложными шаблонными библиотеками (не только BGL, хотя она по этому критерию явно находится среди лидеров): работать с обширными системами неявно увязанных между собой функций без явной типизации параметров и с неочевидной семантикой использования (зачастую тем менее прозрачной, чем более продуманной) физически трудно, и существующие среды разработки не оказывают в этом разработчику никакой поддержки:

  

  В самом деле, автоматические помощники:

  1. Рассчитаны в первую очередь на поддержку ООП, когда набор функций привязывается к объекту справа в соответствии с его типом. С глобальными функциями, которые могут стоять слева от типа (тем паче, набора типов) они помогают существенно хуже даже в том случае, если все типы известны.
  2. До смешного не умеют работать даже с простыми шаблонами. Используемая автором версия визуального помощника, имея перед собой определение шаблонного класса с дефолтными параметрами, предлагает специфицировать «тестовую подстановку», чтобы иметь возможность сгенерировать подсказку для класса. Если пойти ей навстречу, не происходит ровным счетом ничего.
  3. Еще того менее они способны разбираться в метапрограммных спецификаторах, даже простейших, таких, как enable_if.
  4. О типическом же сценарии: «мы находимся внутри шаблонной функции, вызывающейся из неопределенного количества неопределенной длины цепочек других функций, в том числе шаблонных», невозможно говорить без слез. В этом случае vim действительно остается лучшим другом программиста.

  Другой аспект той же ситуации можно проиллюстрировать при помощи первой строки кодового фрагмента, изображенного на предыдущем рисунке. Читателю предлагается выполнить запросы «boost current time» vs «CRT current time» и сравнить результаты. Да, boost::date_time (ныне частично переехавший в std) дает возможность правильно делать множество сложных вещей, в то время как CRT позволяет неправильно делать несколько тривиальных операций, но в повсеместно встречающихся простейших бытовых ситуациях CRT оказывается со всех точек зрения удобней, а многочленные конструкции вида posix_time::second_clock::local_time (пример щадящий) тяготеют к превращению в кочующие по программе иероглифы. Лишите разработчика доступа к личной библиотеке таких иероглифов и скорость разработки устремится к нулю ^[6].

  Boost::string_algo дает возможность делать со строками что угодно, но, положа руку на сердце, каждая не вполне тривиальная операция сопровождается сеансом повторного чтения документации для освежения общей логики библиотеки, наименований предикатов, а также отдельным упражнением по выяснению совместимости параметров. Схожая ситуация имеет место и с операциями токенизации в boost::regexp, при безупречной внутренней логике последних.

  Коли такая ситуация имеет место с самыми общеупотребительными библиотеками, неудивительно, что BGL, как библиотека более специализированная, в которой к тому же имеются, например, функции make_property_map_function и make_function_property_map, не имеющие отношения друг к другу, а также сакраментальная функция get, перезагруженная на любое число аргументов любого типа, порождает те же проблемы, но в гипертрофированном виде. Да-с, любая задача может быть решена цепочкой вызовов get, но, увы, не каждая цепочка get решает данную задачу.

  Читать такой код бывает легко и приятно, он даже может выглядеть как конспект формально записанного алгоритма на естественном языке, но при его написании сказывается невозможность заменять слова синонимами и т. п. проявления жесткости, для настоящего «естественного языка» нехарактерной.

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

  (С другой стороны, регулярно происходящие обновления boost и std приносят множество не вполне тривиальных и зачастую чрезвычайно полезных конструкций и неожиданных решений, действительно позволяющих с меньшими затратами писать более ясный и компактный код. Однако поток новинок настолько широк, неравноценен и слабо структурирован, что важнейшие дополнения к стандартной библиотеке, даже такие очевидные, как затронутые ниже variants/apply_visitor или any, если концептуальные преимущества их применения в контексте конкретного проекта не относятся к разряду самоочевидных, без помощи счастливого случая могут подолгу выпадать из фокуса внимания, если не тратить существенную долю рабочего времени непосредственно на вдумчивое отслеживание новинок, изучение нетривиальных примеров их использования и мысленные попытки приложить их к уже существующему коду. Видимо, при имеющейся интенсивности обновлений единственный способ управиться с этой проблематикой – держать на каждый пяток практикующих программистов C++ одного C++-теоретика, занятого только вопросами приоритетности новинок, их внедрения в проект и выборочного просвещения практиков. Вывод: не начинайте C++-проекты с меньшим числом разработчиков).

• Наконец, объективно самая серьезная проблема, возникающая при работе с шаблонным кодом BGL ^[7]. Предположим, что используется некий шаблонный алгоритм, осуществляющий проход по графу и принимающий представление графа G в качестве аргумента. В типичном случае это представление зависит от наложенных на вершины и ребра фильтров , и весовой схемы . Для работы с фильтрованными графами BGL предлагает уже упоминавшийся выше шаблонный класс filtered_graph, способ присоединения к которому весовой схемы остается на усмотрение пользователя. Функторы, представляющие , и , могут включать как минимум следующие представления:
  • Непосредственно обертку функции, представляющей весовую схему, и предикатов, представляющих фильтры (медленно, без потерь на инициализацию);
  • Кэши над этими обертками, отображающие дескрипторы ребер/узлов на индексы ребер/узлов, адресующие битовый массив и массив значений (без потерь на инициализацию, с постепенным повышением скорости по мере использования);
  • Прямое отображение дескрипторов узлов/ребер на заполненные массивы значений (требует инициализации, но может быть построено на основании предыдущего представления; скорость достигает максимума).

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

  Метапрограммный стиль должен спасать от этих неприятностей, позволяя поддерживать одну описывающую алгоритм метафункцию, неявно генерирующую все нужные реализации (а также, возможно, некоторое, и возможно немалое, количество ненужных, если runtime-структуры кода де-факто не генерируют некоторых сочетаний типов, что при комбинаторном взрыве вариантов может стать проблемой ^[8]), не содержащие обременения в виде дополнительных внутренних ветвлений.

  Работоспособность этой системы, как известно, сильнейшим образом зависит от способностей компилятора к глубокой подстановке inline-функций и упразднению избыточных переменных, которые в полной мере раскрываются только при компиляции с ключом –O2. Без использования полной оптимизации метакод сильнейшим образом проигрывает традиционному коду из-за драматического роста числа вызовов функций (характерное соотношение по скорости между оптимизированной и неоптимизированной сборками колеблется в таких случаях между 1:3 и 1:5, что зачастую приводит к необходимости отлаживаться непосредственно по оптимизированной сборке – а это удовольствие, понятное дело, на любителя ^[9]).

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

  Не лишним будет отметить, что профилятор в такой ситуации оказывается более чем бесполезен: он вводит в заблуждение, стимулируя на 100% бесполезную оптимизацию случайных пользовательских функций из числа часто вызываемых, хотя задержки явно происходят не в них, а в «невидимом» соединительном коде. (Решение же, исходя из изложенного выше, должно состоять скорее в какой-то специальной, в угоду компилятору, декомпозиции исходной шаблонной функции, что, вне зависимости от успеха подобных манипуляций, является дикостью).

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

  Бесхитростно написанный код, соответствующий этому случаю, выглядит примерно следующим образом:

        void type_selector_fun(type_a a, type_b b, ...) 
        {
        	if (condition_1(a, b, ...)) 
        	{
        		auto arg = get_type_1_obj(a, b, ...);
        		run_calc(arg, a, b, ...);
        	}
        	else if (condition_1(a, b, ...))
        	{
        		auto arg = get_type_2_obj(a, b, ...);
        		run_calc(arg, a, b, ...);
        	}
        	else ...
        }
  

  Его можно переписать несколько компактней с использованием variant<...> примерно в следующем виде:

        void type_selector_fun(type_a a, type_b b, ...)
        {
        	variant<type_1, type_2, ...> arg;
        	if (condition_1(a, b, ...))
        	{
        		arg = get_type_1_obj(a, b, ...);
        	}
        	else if ...
                ...
        	apply_visitor([&](auto arg_){run_calc(arg_, a, b, ...); }, arg);
        }
  

  Недостатком этой формы записи является необходимость явного перечисления типов type_1, type_2, … в декларации variant. Типы эти могут быть громоздкими, не менее громоздкой может быть и запись с использованием declval/result_of_t.

  При использовании any нет необходимости перечислять типы, но нет и возможности получить аналог apply_visitor.

  Напрашивается использование некой шаблонной функции make_variant, позволяющей писать код примерно следующего вида:

        auto arg = make_variant
        (
        	bind(condition_1, a, b, ...), bind(get_type_1_obj, a, b, ...),
          bind(condition_2, a, b, ...), bind(get_type_2_obj, a, b, ...),
        	...
        );
  

  , но лекарство выглядит не лучше болезни.

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

        // Автоматический выбор variant<...> для возвращаемого значения в зависимости 
        // от типов, использованных при возвратах: type_1, type_2 etc.
        variant<auto...> get_type_obj(typa_a a, type_b b, ...)
        {
        	if (condition_1(a, b, ...))
        	{
        		return get_type_1_obj(a, b, ...);
        	}
        	else if (condition_2(a, b, ...))
        	{
        		return get_type_2_obj(a, b, ...);
        	}
        	else ...
        }
  

  или даже:

        select_value_type(arg)
        {
        	if (condition_1(a, b, ...))
        	{
        		arg = get_type_1_obj(a, b, ...);
        	}
        	else ...
                ...
        }
        run_calc(arg, a, b, …);
  

  Последний вариант, хотя он вовсе выбивается из стиля C++, выглядит наиболее практичным, так как переменных arg, для которых подбирается тип, может быть больше одной, и предвосхищать логику их построения нет оснований ^[10].

• Обратная сторона этой же ситуации – использование вспомогательных структур (например, кэширующих), реализующих сценарий, заслуживащий названия «шаблонной переменной», но отличающийся от одноименного расширения стандарта С++14.

  Соответствующий код может иметь примерно следующий вид:

        struct CacheHolder
        {
        	boost::variant<
        		container<T1>,
        		container<T2>,
        		// ...
        		container<TN>> ct;
        
        	template<typename T>
        	struct result_type_selector
        	{
        		typedef typename if_c<is_compatible<T, T1>::value, T1,
        			if_c<is_compatible<T, T2>::value, T2,
        			// ...
        			if_c<is_compatible<T, TN>::value, TN,
        			std::decay_t<T>>>>::type type;
        	};
        
        	template<typename T>
        	auto get() const -> const container<typename result_type_selector<T>::type>&
        	{
        		return boost::get<container<typename result_type_selector<T>::type>>(ct);
        	}
        
        };
  

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

  Для краткости код приведен для случая, когда активным может быть только один тип, однако на практике чаще встречается ситуация, когда несколько контейнеров может существовать одновременно (она может быть легко реализована в том же стиле с использованием tuple и optional).

  Реализация функции get<...> предполагает, что вызывающий код имеет некоторое представление о том, к какой разновидности кэшируемого значения он хочет обратиться (например, к целочисленному или с плавающей запятой).

  Не менее распространенной является ситуация, когда точное значение типа вызывающей стороне безразлично. В этом случае воспроизводится сценарий select_value_type/apply_visitor из предыдущего пункта (с поправкой на возможную множественность значений, предполагающую просмотр типов по убыванию приоритета).

• До сих пор в данном тексте практически отсутствовали упоминания PBGL. Это объясняется исчезающе малым опытом работы с этой частью библиотеки у автора (в связи с чем автор и сам относится с известным скепсисом ко всему, что написано ниже в этом абзаце, и других к тому же призывает). Фактически такой опыт сводится к нескольким экспериментам, на однотипных поисковых задачах продемонстрировавшим на практических данных проигрыш распределенной версии локальному решению по памяти в 3-5 раз и по общей производительности в 15-20 раз (происхождение этой пугающей цифры поясняется здесь ^[11] и дополнительно комментируется следующими абзацами). С учетом большей сложности работы с распределенными структурами выбор в пользу локальной версии был в такой ситуации самоочевиден.

  Поясним механику работы PBGL на характерном примере алгоритма дельта-шагания. В этой параллельной версии алгоритма Дейкстры очередь с приоритетами заменяется на массив «ведерок». Элементы, попавшие в одно «ведерко», обрабатываются параллельно. В своей оригинальной форме дельта-шагание является типичным алгоритмом для систем с общей памятью.

  В распределенной же версии происходит следующее: в PBGL при загрузке граф разбрасывается между процессами, причем каждому процессу соответствует непрерывный диапазон номеров вершин. Таким образом, по глобальному номеру вершины легко узнать, какому процессу она принадлежит. Соответственно, каждый поцесс на каждом ходу алгоритма хранит часть «ведерка», содержащую принадлежащие этому процессу вершины. Все процессы одновременно выбирают и обрабатывают вершины из своих частей «ведерок» по одной, при этом рассылают сообщения о необходимости обновления следующих «ведерок» процессам, владеющим соседними вершинами. Легко видеть, что при прочих равных увеличение числа процессов ведет к увеличению количества рассылаемых ими сообщений. В результате время выполнения алгоритма может не только не уменьшаться, но даже возрастать. В частности, запуск нескольких MPI-процессов для решения этой задачи на одной физической машине с некоторой вероятностью приведет только к увеличению общей загрузки процессора без какого-либо выигрыша по времени.

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

  Таким образом, если граф предварительно не подготовлен, разбивать его следует на блоки максимального размера, по одному блоку на одну физическую машину. Под предварительной же подготовкой здесь подразумевается такая перенумерация вершин графа, чтобы непрерывные диапазоны номеров, которые использует PBGL, по возможности соответствовали слабо связанным подграфам. Для этих целей применяются такие пакеты, как METIS, paraMETIS и Zoltan. Работа с динамическими графами в таком режиме затруднена. ^[12]

  В целом по результатам описанных опытов у автора сложилось впечатление, что нормальная работа кластера PBGL возможна только при наличии специального коммуникационного оборудования, а в качестве узлов такого кластера имеет смысл использовать машины с минимальным числом ядер и максимальной производительностью на нить. Авторы Trinity ^[13] в своей статье утверждают, что их распределенное хранилище работает гораздо эффективней – прокомментировать это утверждение автор затрудняется, но, с учетом изложенных обстоятельств, находит это вполне возможным: архитектура PBGL несет отчетливую печать времени, когда многоядерные машины еще не получили массового распространения.

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

BGL и другие звери

Принимая во внимание достаточно длинный список специфических жалоб, не будет неуместным поинтересоваться: может ли автор в 2019 году порекомендовать BGL для новых проектов. Ответ будет таким: автор полагает, что у библиотек такого стиля и приложений на их основе обязано быть будущее ^[14]. Что до выбора опорной библиотеки для конкретного проекта, то над инструментовкой стоит серьезно поразмыслить, не упуская из вида перечисленных выше проблем. Ответ, очевидно, зависит от многих обстоятельств, включающих, но не ограничивающихся перечисленным в следующих пунктах:

• Является ли работа с графами в проекте основой функциональности или факультативной задачей;
• Может ли проект получить преимущество за счет использования множественных представлений или вполне достаточной для него будет работа с жестко типизированными алгоритмами;
• Наиболее выгодный для проекта тип параллелизма;
• Организационные нюансы: охота к метапрограммированию на C++ у сотрудников (особенно программистов-математиков) и т. п.

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

Что до возможных альтернатив, то их список включает в себя как минимум следующие пункты ^[15]:

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

1. Графовые СУБД (neo4j и др.).

   Системы такого рода ориентированы на выполнение транзактных операций над большими (распределенными дисковыми) графами. Хотя API такой системы может быть в высшей степени развитым, скорость выполнения собственно графовых алгоритмов, насколько можно судить, не является первым приоритетом. Система может даже не пытаться загружать граф целиком в память. Для модификации и обхода графа поддерживаются декларативные языки (SPARQL, Cypher, Gremlin). Большое значение придается обеспечению преемственности с традиционными SQL-системами.

2. Графовые расширения систем обработки больших данных, работающих в парадигме map/reduce (GraphX в Spark, Pegasus и Giraph для Hadoop) и независимые кластерные системы (MS Trinity/MS Graph Engine ^[13], GraphLab). Первые для выполнения операций над графом реализуют модель Google Pregel ^[30] (но не только ее) и могут конфигурироваться для использования в том числе массивно-параллельных вычислительных узлов. И те, и другие могут в числе прочего использоваться в качестве основы для корпоративных программных проектов.

   Хотя API таких систем может быть достаточно развитым (помимо прочего, GraphX поддерживает SPARQL и Cypher), основной упор при работе с ними приходится на решение инфраструктурных проблем. Для GraphX характерны иммутабельность данных и уклон в конвейеризацию всех операций. MS Trinity на данный момент не включает высокоуровневых методов и предоставляет только набор примитивов для работы с узлами и ребрами. Системы, работающие поверх Hadoop, в принципе малоприспособлены для решения произвольных графовых задач.

3. Собственно универсальные инструментальные библиотеки, реализующие более или менее широкие наборы методов (BGL/PBGL, LEMON etc.), в том числе массивно-параллельные (nvGraph, Gunrock).

   На их основе могут создаваться прикладные системы, адаптирующие графовые алгоритмы к конкретным предметным областям.

4. Системы и библиотеки, специализирующиеся на отдельных сложных задачах, имеющих универсальное значение (METIS, paraMETIS, Zoltran: graph partitioning, GraphViz, Gephi: визуализация, GraphBLAS: алгебраические алгоритмы для работы с графами и т. п.).

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

Неясная, но значительная часть графовых приложений ориентированы на задачи Network Analysis и, уже, Social Network Analysis (Community Detection). Как ни странно, существенно меньше распространены системы Link Analysis (использующиеся, как правило, различными «борцами с преступностью»), имеющие определенное сходство с разрабатываемой нами системой. Во всех случаях без специальной проверки трудным оказывается выяснить характер используемых различными системами моделей данных и сопутствующие ограничения по производительности, поддерживаемым объемам, наборам операций и т.п.

Примечания

1. BGL не является чисто-заголовочной библиотекой, но на данный момент единственная функциональность, требующая линковки – это (довольно факультативная) работа с DOT-файлами формата GraphViz. Поэтому в подавляющем большинстве случаев в связывании не возникает необходимости и автоматического связывания с надлежащей версией libbost-graph по включению заголовков BGL в конфигурации Boost не предусмотрено. Таким образом, для согласования с библиотекой libboost-regex, используемой незаголовочными функциями BGL, удобно бывает просто подключить заголовок boostregex.hpp из кода проекта, даже если последний не использует регулярных выражений.
2. подталкивает к охоте на (возможно отсутствующих) черных кошек в темных комнатах ^[31].
3. Прежде чем перейти к ее описанию (на конкретном примере, где она проявилась особенно сильно и неприятно), отметим, что автор относится к числу сравнительно немногочисленных счастливчиков, работающих с нагруженным проектом в мощной операционной системе Windows и богоспасаемой линейке компиляторов MSVC. Не исключено, что описываемые ниже неприятности являются артефактами этой линейки компиляторов: разнообразные частные обстоятельства затрудняют проведение сравнительного опыта с gcc/clang в среде *nix. Если это так, можно только поздравить пользователей других компиляторов.
4. Смягчить которую в каких-то случаях наверняка поможет недавно появившийся constexpr if.
5. В нашем случае это привело к особенному вниманию к функции сохранения состояния, которая позволяет отлаживаться с удобствами, предварительно выводя систему в нужное исходное состояние в оптимизированной сборке.
6. звездой сияет подбор аргумента делением пополам ^[32], но, в целом, основные проблемы при таких операциях были всегда связаны с невозможностью экспорта подобранного типа за пределы области видимости, что и порождало экзотические схемы.
7. Обозначенный выше двадцатикратный проигрыш по скорости (в абсолютных цифрах — примерно 80 секунд против 4 на тестовом направленном графе с 50 миллионами вершин и 200 миллионами ребер, представленном в виде списка смежности) был получен на неподготовленном (разбитом случайным образом) графе при сравнении с локальной версией дельта-шагания на восьмиядерной машине. Соответственно, в сравнении с однопоточной реализацией алгоритма Дейкстры проигрыш распределенной версии будет в такой ситуации примерно двухкратным. Здесь нужно дополнительно отметить, что 6-8 потоков для графов такой плотности — это максимальное количество, до которого еще наблюдается практически линейный рост производительности.
8. В теории на этот случай имеются специальные методы, модифицирующие уже построенное разбиение вместо полного его пересчета. (Автор затрудняется сказать, как надлежит выбираться из закольцованной ситуации по-настоящему большого графа, который невозможно обработать на одной машине. На графе, разбросанном по серверам случайным образом, многие алгоритмы, включая сами алгоритмы разделения графа, окажутся неработоспособными, а пошаговый алгоритм локального улучшения разбиения будет, вероятно, работать неопределенно долго и сойдется неизвестно к чему).
9. В стародавние времена, когда деревья были большими, а аббревиатура ООП – новой и модной, автор однажды совершил серьезную ошибку, попытавшись использовать «объекты» для описания физических сущностей (слой-луч-граница и т.п.) в программе моделирования волновых полей. Выяснилось (это не анекдот, а печальная повесть), что единственная разновидность объекта, поведение которой «объект» действительно позволяет описать скрупулезно, не вставая на уши — это окно графического интерфейса (разработка которых тогда тоже была в большой моде и считалась чуть ли передним краем технологий). Мало сказать, что виртуальность, зависящая только от одного из участников, матушке-природе совершенно не присуща. Самым захватывающим, насколько сейчас можно вспомнить, было поведение наследования: «базовые» слои (жидкие или упругие изотропные) характеризовались коэффициентами, которые не дополнялись в «производных» (упругих анизотропных или пористых), а представляли собой некую свертку более общей системы коэффициентов, возникающей только в производном классе. При добавлении в систему новой уточняющей физической модели слоя ситуация воспроизводилась. Изменить направление наследования было невозможно как по соображениям производительности, так и из-за того, что начинать пришлось бы с «самой общей системы коэффициентов из всех возможных», а наука не знает такой гитики. Можно ли после этого обескураживающего опыта осмеливаться утверждать, что другая «многообещающая программная технология» обязательно сработает в новой области? Полагаю, что некоторую надежду в данном случае внушает то, что данная технология не пытается выдать себя за то, чем не является: метаязыки – это артефакт программных технологий, и, хотя при работе с ними возникают сложности, в том числе неожиданные, их место в процессе разработки четко определено и назначение самоочевидно.
10. Данная таблица является компиляцией. Автор не имеет существенного опыта работы с перечисленными библиотеками, не проводил сравнительных тестов самостоятельно, не гарантирует точности сообщаемых сведений и будет признателен за любые дополнения и исправления.
11. По запросам вида «LIBNAME C++ graph» или аналогичным, в зависимости от селективности наименования и наличия маркера раздела на stackoverflow. Для сравнения, у BGL несколько больше 500 упоминаний в разделе [boost-graph].

Автор: basil_pivovarov

Источник ^[33]