Интервалы в С++, часть 3: представляем инкременторы (Iterable)

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

В конце предыдущего поста я просуммировал недостатки существующих интервалов:

• интервалы с ограничителями и бесконечные интервалы генерят плохой код
• им приходится моделировать более слабые концепции, чем они могли бы
• легко можно передать бесконечный интервал в алгоритм, который его не переварит
• их трудно использовать
• интервалы, которые могут быть бесконечными или очень большими, могут вызвать переполнение в difference_type

Первая проблема особенно трудная, поэтому начнём с неё.

Концепция интервалов

Для начала, давайте строго определим понятие интервала. В стандарте C++ это слово используется повсюду, но нигде не определяется. Можно понять, что интервал – это нечто, из чего можно извлечь begin и end, пару итераторов, которые устроены так, что до end можно добраться, начав с begin. В терминах моего предложения формализовать эту концепцию можно так:

using std::begin;
using std::end;
 
template<typename T>
using Iterator_type =
    decltype(begin(std::declval<T>()));
 
template<typename T>
concept bool Range =
    requires(T range) {
        { begin(range) } -> Iterator_type<T>;
        { end(range) }  -> Iterator_type<T>;
        requires Iterator<Iterator_type<T>>;
    };

Также есть улучшения концепции интервала Range, которые называются InputRange, ForwardRange, и т.д. На деле они просто больше требуют от своих итераторов. Ниже показана вся эта иерархия.



Эти концепции являются основой для библиотеки Boost.Range (http://www.boost.org/libs/range)

Проблема 1: Генерация плохого кода

Если помните, для реализации интервалов как с ограничителем, так и бесконечных, в виде пары итераторов, итератор end должен быть сигнальным. И такой итератор представляет собой больше концепцию, чем физическое положение элемента в последовательности. Можно представлять его, как элемент с позицией «последний + 1» – разница лишь в том, что вы не узнаете, где его позиция, пока не достигнете её. Поскольку тип сигнального итератора такой же, как у обычного, требуется проверка на этапе выполнения программы, чтобы определить, является ли данный итератор сигнальным. Это приводит к медленному сравнению итераторов и неудобным реализациям методов.

Концепция инкременторов (Iterable)

Для чего нужны итераторы? Мы увеличиваем их, разыменовываем и сравниваем, так ведь? А что можно сделать с сигнальным итератором? Не особенно много чего. Его позиция не меняется, его нельзя разыменовать, т.к. его позиция всегда «последний + 1». Но его можно сравнить с итератором. Получается, что сигнальный итератор – слабый итератор.

Проблема с интервалами в том, что мы пытаемся превратить сигнальный итератор в обычный. Но он им не является. Так и не будем это делать – пусть они будут другого типа.

Концепция Range требует, чтобы begin и end были одного типа. Если можно их сделать разными, это уже будет более слабая концепция – концепция Iterable. Инкременторы – они как итераторы, только у begin и end разные типы. Концепция:

template<typename T>
using Sentinel_type =
    decltype(end(std::declval<T>()));
 
template<typename T>
concept bool Iterable =
    requires(T range) {
        { begin(range) } -> Iterator_type<T>;
        { end(range) }  -> Sentinel_type<T>;
        requires Iterator<Iterator_type<T>>;
        requires EqualityComparable<
            Iterator_type<T>, Sentinel_type<T>>;
    };
 
template<typename T>
concept bool Range =
    Iteratable<T> &&
    Same<Iterator_type<T>, Sentinel_type<T>>;

Естественно, концепция Range входит в концепцию Iterable. Она просто уточняет её, добавляя ограничение на равенство типов begin и end.



Так выглядит иерархия, если мы рассматриваем интервалы, инкременторы и итераторы, но совершенно не обязательно именно так определять их и в программе. Заметьте, что «интервальность» – т.е., схожесть типов begin и end, ортогональна силе итератора begin. Когда нам надо включать в код моделирование RandomAccessRange, мы можем сказать requires RandomAccessIterable && Range и просто сменить всю концепцию.

Разница между, к примеру, BidirectionalIterable и ForwardIterable в концепции, моделируемой итератором begin из Iterable.

Iterable и алгоритмы STL

Но постойте – ведь алгоритмы STL не будут работать с инкременторами, потому что им требуется, чтобы у begin и end было один тип. Так и есть. Поэтому я прошерстил весь STL, чтобы проверить, что можно переписать. Например, std::find

template<class InputIterator, class Value>
InputIterator
find(InputIterator first, InputIterator last,
     Value const & value)
{
    for (; first != last; ++first)
        if (*first == value)
            break;
    return first;
}

Сейчас std::find использует Ranges. Но заметьте, что алгоритм не пытается поменять позицию итератора end. Алгоритм поиска можно легко поменять так, чтобы он работал с Iterables вместо Ranges:

template<class InputIterator, class Sentinel, class Value>
InputIterator
find(InputIterator first, Sentinel last,
     Value const & value)
{
    for (; first != last; ++first)
        if (*first == value)
            break;
    return first;
}

Вот и всё – изменение настолько малое, что его даже заметить трудно.

Так какие алгоритмы C++98 можно приспособить к работе с Iterables вместо Ranges? Оказывается, почти все. Легче перечислить те, которые не поддаются. Это:

• copy_backward
• алгоритмы работы с множествами и пирамидами (push_heap, pop_heap, make_heap, sort_heap)
• inplace_merge
• nth_element
• partial_sort и partial_sort_copy
• next_permutation и prev_permutation
• random_shuffle
• reverse и reverse_copy
• sort и stable_sort
• stable_partition

Остальные полсотни требуют чисто механического изменения в коде. Определив концепцию Iterable так, как она определяется в Range, мы даём любому алгоритму, работающему с Iterable, возможность точно так же работать и с Ranges. Это полезно и важно – для итераторов написано слишком много кода, чтобы делать для них какую-то несовместимую абстракцию.

Доказательство в Perf

И что мы получим? Вернёмся к нашим С-строкам. Я описал класс c_string_range и нашёл, что перебор символов генерит плохой код. Начнём снова, только при помощи range_facade, чтобы построить Iterable вместо Range.

using namespace ranges;
struct c_string_iterable
  : range_facade<c_string_iterable>
{
private:
    friend range_core_access;
    char const *sz_;
    char const & current() const { return *sz_; }
    void next() { ++sz_; }
    bool done() const { return *sz_ == 0; }
    bool equal(c_string_iterable const &that) const
    { return sz_ == that.sz_; }
public:
    c_string_iterable(char const *sz)
        : sz_(sz) {}
};

Код получился гораздо проще, чем старый. Всю работу делает range_facade. Итератор и сигнальный итератор реализованы в виде примитивов. Чтобы проверить его, я сгенерил оптимизированный машинный код для следующих функций, одна из которых использует старый класс c_string_range, а другая – новый c_string_iterable:

// Range-based
int range_strlen(
    c_string_range::iterator begin,
    c_string_range::iterator end)
{
    int i = 0;
    for(; begin != end; ++begin)
        ++i;
    return i;
}

// Iterable-based
int iterable_strlen(
    range_iterator_t<c_string_iterable> begin,
    range_sentinel_t<c_string_iterable> end)
{
    int i = 0;
    for(; begin != end; ++begin)
        ++i;
    return i;
}

Даже не зная ассемблера, можно понять разницу.

;Range-based strlen pushl %ebp movl %esp, %ebp pushl %esi leal 8(%ebp), %ecx movl 12(%ebp), %esi xorl %eax, %eax testl %esi, %esi movl 8(%ebp), %edx jne LBB2_4 jmp LBB2_1 .align 16, 0x90 LBB2_8: incl %eax incl %edx movl %edx, (%ecx) LBB2_4: testl %edx, %edx jne LBB2_5 cmpb $0, (%esi) jne LBB2_8 jmp LBB2_6 .align 16, 0x90 LBB2_5: cmpl %edx, %esi jne LBB2_8 jmp LBB2_6 .align 16, 0x90 LBB2_3: leal 1(%edx,%eax), %esi incl %eax movl %esi, (%ecx) LBB2_1: movl %edx, %esi addl %eax, %esi je LBB2_6 cmpb $0, (%esi) jne LBB2_3 LBB2_6: popl %esi popl %ebp ret

;Iterable-based strlen pushl %ebp movl %esp, %ebp movl 8(%ebp), %ecx xorl %eax, %eax cmpb $0, (%ecx) je LBB1_4 leal 8(%ebp), %edx .align 16, 0x90 LBB1_2: cmpb $0, 1(%ecx,%eax) leal 1(%eax), %eax jne LBB1_2 addl %eax, %ecx movl %ecx, (%edx) LBB1_4: popl %ebp ret

Код с инкременторами гораздо круче. И он практически идентичен с ассемблером, полученным из итераторов «голого» С.

Итераторы, сигнальные итераторы и паритетность

Но что означает сравнение двух объектов разных типов на эквивалентность?

Немного для непосвященных: N3351 определяет, в каких случаях допустимы сравнения разных типов. Недостаточно, чтобы синтаксис «x==y» был допустим и выдавал булевское значение. Если у х и у будут разные типы, то эти типы должны быть сами по себе EqualityComparable, и у них должен быть общий тип, к которому их можно преобразовать, и он также должен быть EqualityComparable. Допустим, мы сравниваем char и short. Это возможно, поскольку они EqualityComparable, и их можно преобразовать в int, который тоже EqualityComparable.

Итераторы можно сравнивать, а сигнальные итераторы сравниваются тривиальным образом. Сложность в том, чтобы найти для них общий тип. Вообще, у каждого итератора и сигнального есть общий тип, который можно создать так: предположим существование нового типа итератора I, который представляет собой тип-сумму, и содержит либо итератор, либо сигнальный итератор. Когда их сравнивают, он ведёт себя семантически так, будто их обоих сначала преобразовали в два объекта типа I, назовём их lhs и rhs, и затем сравнили по следующей табличке:

lhs сигнальный итератор?	rhs сигнальный итератор?	lhs == rhs?
true	true	true
true	false	done(rhs.iter)
false	true	done(lhs.iter)
false	false	lhs.iter == rhs.iter

Эта табличка напоминает ту, которая получилась при анализе поведения оператора сравнения c_string_range::iterator. Это не случайно – то был особый случай этой, более общей, схемы. Она подтверждает интуитивное заключение, которое вы уже можете заметить, просмотрев два моих класса, c_string_range и c_string_iterable. Один – пара итераторов, другой – пара итератор/сигнальный, но их схема работы схожи. Мы чувствуем, что возможно построить эквивалентный Range из любого Iterable, если пожертвовать небольшой толикой быстродействия. И теперь мы нашли подтверждение этому.

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

Возражения

Идея дать разные типы begin и end не нова, и придумал её не я. Я узнал о ней от Дэйва Абрахамса (Dave Abrahams) много лет назад. Недавно сходную идею подал Дитмар Кюэль (Dietmar Kuehl) в списке рассылки Ranges, а в ответ на его письмо Шон Пэрент (Sean Parent) высказал следующее возражение:

Мне кажется, мы возлагаем на итераторы слишком многое. Алгоритмы, работающие с окончанием на основании проверки сигнального итератора или на основании подсчёта – это разные сущности. См. copy_n() и copy_sentinel()

stlab.adobe.com/copy_8hpp.html

Касательно интервалов – я уверен, что можно построить его при помощи:

1. пары итераторов
2. итератора и количество
3. итератора и сигнала

И в этом случае copy(r, out) может выдать нужный алгоритм.

Если я правильно его понял, он говорит о существовании трёх параллельных концепций интервалов: IteratorRange, CountedRange и SentinelRange. И эти иерархии не нужно пытаться связать между собой. Алгоритм копирования должен содержать три разные реализации, по одной на каждую концепцию. Тогда придётся утроить порядка 50 алгоритмов – и это слишком много повторения в коде.

Хуже того, некоторые алгоритмы основаны на уточнённых концепциях. Например, в libc++ алгоритм rotate выбирает одну из трёх реализаций, в зависимости от того, передаёте вы ему прямые, двунаправленные или итераторы произвольного доступа. А для включения трёх разных реализаций Iterator, Counted и SentinelRanges потребовалось бы 9 алгоритмов rotate! При всём уважении, это безумие.

Итого

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

Весь код можно найти в репозитории на github.

Благодарности

Я хотел бы поблагодарить Эндрю Суттона (Andrew Sutton) за помомщь с синтаксисом Concpets Lite и за объяснение требований концепции EqualityComparable для разных типов и общее улучшение и формализацию многих идей. Статьи стали значительно лучше благодаря его большому вкладу.
Другие статьи цикла
Интервалы в С++, часть 1: Интервалы с ограничителями
Интервалы в С++, часть 2: Бесконечные интервалы
Интервалы в С++, часть 4: к бесконечности и далее