Інтервали в С++, частина 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;
const char *sz_;
const char & 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(const char *s)
: 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.

Джерело: Хабрахабр

Залишити відповідь

Ваша e-mail адреса не оприлюднюватиметься. Обов’язкові поля позначені *

*