На межі можливого в C++: Як я створював бібліотеку для constexpr циклів - javascript.org.ua

текст перекладу

Опис

Програмування на етапі компіляції є корисною технікою для підвищення продуктивності, читабельності та підтримуваності коду. Завдяки йому можна виконувати частину обчислень програми під час її побудови, а не під час виконання. Це може бути корисним, оскільки результати обчислень "вшиваються" в саму програму.

C++ було спочатку створено як надбудову над C. У C програмування на етапі компіляції в основному обмежено макросами, системою, яка здебільшого призначена для зміни тексту коду. Макроси є потужними, але можуть бути схильні до помилок, оскільки їхні правила значно відрізняються від "нормального" C. Окрім макросів, C++11 має ще два механізми для програмування на етапі компіляції: шаблони та "constexpr". Шаблони можна розглядати як креслення для коду. Вони дозволяють програмістам описувати "план", і компілятор "інстанціює" його в конкретний фрагмент коду за потреби.
текст перекладу
Програмування за допомогою шаблонів (Template metaprogramming) — це термін, що описує використання шаблонів для програмування на етапі компіляції; примітно, що система шаблонів є тьюрінг-повною. Є також "constexpr", який є ключовим словом, що вказує компілятору, що "змінна буде" і "функція може" мати результат, який можна знати або обчислити на етапі компіляції. "constexpr" дозволяє програмування на етапі компіляції за допомогою коду, який більше схожий на "нормальне", програмування на етапі виконання.

Про CEXForLoop

CEXForLoop — це потужна бібліотека лише для заголовочних файлів для C++14 і новіших версій, яка приносить ітерацію на етапі компіляції у ваш код.
текст перекладу
Створена з використанням технік програмування за допомогою шаблонів та "constexpr", ця бібліотека надає інтерфейс, подібний до циклу for у стилі C, спрощуючи та відкриваючи нові можливості для програмування на етапі компіляції.

Помітні особливості

Завдяки унікальній змінній ітерації constexpr, CEXForLoop дозволяє ітерувати масиви та інші структури даних повністю в режимі constexpr, що дає змогу здійснювати складні обчислення на етапі компіляції, що зазвичай є складними. Бібліотека значно зменшує глибину необхідної інстанціації шаблонів завдяки інноваційному підходу n-арного дерева, що робить обробку навіть довгих ітерацій простішою. Наприклад, для 1 000 ітерацій потрібна лише глибина шаблону 114. Крім того, CEXForLoop підтримує передачу до 50 визначених користувачем значень constexpr (через параметри типу, що не є шаблонами, NTTPs) у тіло циклу for. Кожна ітерація отримує та генерує ці значення, що дозволяє користувачеві змінювати їх для наступної ітерації.
текст перекладу
Ці три основні особливості створюють цінну бібліотеку для програмування на етапі компіляції.

Основне використання

CEXForLoop призначена для задач на етапі компіляції, що вимагають ітерації. Завдяки вбудованим раніше описаним важливим особливостям, користувачі можуть легше програмувати на етапі компіляції. Ось основне використання цієї бібліотеки:

Обробка даних на етапі компіляції: попереднє обчислення значень, генерація таблиць пошуку, трансформація існуючих даних або виконання складних обчислень під час компіляції.

Можливо, ви думаєте, що один випадок використання означає вузьке застосування бібліотеки, але це зовсім не так. Оскільки компілятор не має доступу до зовнішнього світу, програмування на етапі компіляції обробляє лише дані (функціональна парадигма). Тому широка застосовуваність CEXForLoop на етапі компіляції подібна до звичайного циклу for під час виконання.

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

Моя мотивація: кроляча нора

Моя розповідь допомагає передати цінність бібліотеки. Хоча моя конкретна проблема є нішевою, CEXForLoop надає універсальне рішення, яке корисне в багатьох контекстах програмування на етапі компіляції.

Якщо ви намагаєтеся використовувати ітерацію на етапі компіляції, зверніться до CEXForLoop.

Мій досвід

Протягом останніх 5 років я працюю неповний робочий день над пристроєм для вимірювання діапазону руху. Це вбудований пристрій, який вимірює гнучкість суглобів людини. Він призначений для використання хіропрактиками, фізіотерапевтами та іншими медичними працівниками.

Один аспект проекту полягає в програмуванні мікроконтролера nrf52xx для зв'язку з інерціальним вимірювальним пристроєм (IMU), що використовується для вимірювання орієнтації відносно Землі. IMU — це складні пристрої.
текст перекладу
Щоб забезпечити орієнтацію, вони повинні зчитувати дані з кількох датчиків (акселерометр, гіроскоп і магнітометр) і обробляти їх за допомогою алгоритму сенсорної фузії (часто це фільтр Калмана). Особливий IMU, який використовується в моєму проекті, бере на себе більшу частину складності. Він надає інтерфейс I2C для його керування та отримання даних про орієнтацію. Під час запуску, до того як IMU стане працездатним, необхідно записати структуру конфігурації на пристрій.
текст перекладу
Я поставив вимогу до свого драйвера, щоб він міг читати та записувати структуру конфігурації.

Наступний код з прикладу для STM32 від IMU показує структуру конфігурації та як її записати.

typedef struct  
{  
 uint16_t cal_points;  
 uint8_t Ascale;  
 uint8_t AODR;  
 uint8_t Alpf;  
 uint8_t Ahpf;  
 uint8_t Gscale;  
 uint8_t GODR;  
 uint8_t Glpf;  
 uint8_t Ghpf;  
 uint8_t Mscale;  
 uint8_t MODR;  
 uint8_t Mlpf;  
 uint8_t Mhpf;  
 uint8_t Pscale;  
 uint8_t PODR;  
 uint8_t Plpf;  
 uint8_t Phpf;  
 uint8_t AUX1scale;  
 uint8_t AUX1ODR;  
 uint8_t AUX1lpf;  
 uint8_t AUX1hpf;  
 uint8_t AUX2scale;  
 uint8_t AUX2ODR;  
 uint8_t AUX2lpf;  
 uint8_t AUX2hpf;  
 uint8_t AUX3scale;  
 uint8_t AUX3ODR;  
 uint8_t AUX3lpf;  
 uint8_t AUX3hpf;  
 float m_v;  
 float m_h;  
 float m_dec;  
 uint8_t quat_div;  
} CoProcessorConfig_t;

void USFSMAX::Upload_cfg(CoProcessorConfig_t Config)  
{  
 //...

текст перекладу

// Присвоєння структури конфігурації до масиву байт для завантаження
memcpy(cfgbuff, &Config, sizeof(CoProcessorConfigt));
// Завантаження байтів конфігурації
i2c->writeBytes(MAX32660SLVADDR, COPROCFGDATA0, 30,
&cfgbuff[0]);
delay(100);
i2c->writeBytes(MAX32660SLVADDR, COPROCFGDATA1,
(sizeof(CoProcessorConfigt) - 30),
&cfg_buff[30]);
delay(100);
}
```

Під час написання свого драйвера я читав вищезазначений код, щоб зрозуміти, як реалізувати свою функцію для запису структури конфігурації. Одним із моїх міркувань було врахування вирівнювання структури. Ви могли помітити, що структура вище визначена з використанням стандартного макету, оскільки жодні директиви препроцесора компілятора не вказують на інше. На мікроконтролері STM32 (32-розрядний процесор сімейства Cortex-M) структура має 2 байти внутрішнього вирівнювання після “AUX3hpf” і 3 байти додаткового вирівнювання в кінці.
текст перекладу
(Див. Втрачена майстерність вирівнювання структур для того, як я прийшов до цього висновку.) Метод запису в цьому коді безпосередньо серіалізує об'єкт у потік байт через “memcpy”. Ці два факти вказують на приховану залежність від апаратного забезпечення в наведеному прикладі коду.

Оскільки мікроконтролер nrf52xx, на якому працює моє додаток, є Cortex M4, макети (layouts) однакові. “YAGNI” (You Aren’t Gonna Need It), – чую я ваш крик! Ви маєте рацію, у цьому випадку, ймовірно, я мав би просто залишити коментар або, ще краще, використати статичну перевірку (static assert) для вказівки на апаратну залежність і рухатися далі. Однак цей розділ не називається “Кейс YAGNI”, він називається “Кроляча нора” (A Rabbit-Hole), тому вниз ми йдемо!

Вхід у програмування на етапі компіляції

Оскільки вся інформація щодо розбіжностей у макеті структури конфігурації відома на етапі компіляції, має бути можливим створити рішення для програмування на етапі компіляції, яке мінімізує процес конвертації.
текст перекладу
Метод серіалізації, що є результатом цього рішення і замінює “memcpy”, має бути таким же ефективним, як і вручну написана функція. Завдяки такому рішенню мій драйвер IMU може позбутися залежності від апаратного забезпечення, не сплачуючи за абстракцію. Позбувшись цієї залежності, мій код драйвера дотримується принципів "дизайну для змін" та "інкапсуляції". Зараз я пишу іншу бібліотеку, яка реалізує це рішення для програмування на етапі компіляції.

Ця бібліотека виконує серіалізацію та десеріалізацію з вбудованою конверсією макету (тобто, вирівнювання та енд'янес). Першою перешкодою при створенні такої бібліотеки є рефлексія C++, або здатність “отримувати” типи членів довільної структури. C++ не має вбудованих можливостей рефлексії, але boost::pfr від Антонія Полухіна (boost у назві лише) має кілька трюків, які можуть це зробити для обмеженого набору типів структур. З boost::pfr моя бібліотека може ітерувати через типи членів структури на етапі компіляції — дозволяючи моїй бібліотеці обчислювати місця для вирівнювання (padding).
текст перекладу
Для цього потрібні два етапи: один для визначення вирівнювання типу структури та один для знаходження місць для вирівнювання (padding).

Моя реалізація без CEXForLoop ґрунтувалася на наступному механізмі:

template   
static constexpr auto constexpr_for(FunctorData  
 initial_data) ->  
 typename std::enable_if<(start != end),   
 FunctorData>::type {  
// працюємо з initial_data...  
 return constexpr_for(  
 initial_data);  
}  
template   
static constexpr auto constexpr_for(FunctorData  
 initial_data) ->  
 typename std::enable_if<(start != end),   
 FunctorData>::type {  
 return initial_data;  
}

Це працює, але має кілька недоліків.

Це лінійне рішення щодо кількості ітерацій в порівнянні з необхідною глибиною шаблонів.
текст перекладу
Це означає, що моя бібліотека серіалізації/десеріалізації, ймовірно, не зможе скомпілюватися за умовчанням на clang та gcc, якщо структура користувача має 900 членів. (900 — це максимальна глибина шаблонів за замовчуванням на clang та gcc.) Я розумію, що 900 членів — це багато, але це не є чимось надзвичайним в контексті серіалізації/десеріалізації даних. За допомогою CEXForLoop 900 ітерацій можна обробляти без проблем, оскільки це логарифмічне рішення.
Я вважаю, що ця реалізація важча для читання, оскільки шаблон ітерації до рекурсії знаходиться прямо біля тіла наступної ітерації. CEXForLoop, з іншого боку, має знайому синтаксис. Це як комбінація циклу C-стилю з лямбда-виразом — спочатку важко читати, але стає зрозумілішим, коли побачиш це кілька разів.

Ось механізм CEXForLoop:

struct MyFunctor {  
 struct NonConstexprData {  
 // Дані користувача ...

текст перекладу
};  

using IType = std::size_t;  
using OutputType = std::tuple;  
template  
static constexpr OutputType func(NonConstexprData   
input_data) {  
 // Код користувача ...  
 return { /* оновлені 'input_data' */ };  
};  
struct TypeEncodedInitialData {  
 static constexpr NonConstexprData  
 value = { /* значення користувача */ };  
};  
};  

//...  

// Виклик  
constexpr auto kValue = cex_for_loop::func<  
 MyFunctor::IType, 0,   
 cex_for_loop::BoolExpressionFunctor_LT, 200, 1,   
 MyFunctor,  
 cex_for_loop::TypeEncodedNTTPs::type,  
 MyFunctor::TypeEncodedInitialData>();

Реалізація CEXForLoop трохи більш багатослівна, але вона потужніша. У наступному розділі я поясню, як використовувати CEXForLoop.

Як використовувати

CEXForLoop на перший погляд може здатися складним, але інтерфейс працює знайомо. Щоб використовувати CEXForLoop, є 3 основні кроки:

Підключіть заголовки бібліотеки.
2.
текст перекладу
Викличте ваш цикл for.

Крок 1: Підключення заголовків

При перегляді кодової бази ви можете помітити, що CEXForLoop слідує загальним конвенціям інших бібліотек, що складаються тільки з заголовків, у яких є дві форми заголовків: інтерфейс та реалізація. Усі заголовки інтерфейсу (тобто ті, які ваш код може “включати”) знаходяться в каталозі “include/CEXForLoop/”; заголовки реалізації знаходяться в каталозі “include/CEXForLoop/impl/”. Основний заголовок — “cexforloop.h”, але вам, ймовірно, також знадобиться підключити “boolexpressionfunctors.h”, оскільки він містить всі основні логічні вирази, такі як менше, менше або дорівнює, більше тощо.

#include   
#include

Крок 2: Визначте функтор для тіла циклу for

Функціональний об'єкт (функціональний об'єкт) — це об'єкт функції, але в контексті CEXForLoop функціональний об'єкт є функцією, що закодована типом з певними обмеженнями.
текст перекладу
Функтори (Functors) корисні в програмуванні на етапі компіляції, оскільки їх можна передавати. Це дозволяє впроваджувати залежність поведінки — щось на кшталт поліморфізму, але на етапі компіляції.

Функтор, який ви визначите в цьому розділі, буде тілом вашого циклу for. CEXForLoop накладає кілька обмежень на функтор з практичних міркувань. Ось мінімальне визначення функтора, яке не використовує параметри шаблонів типів користувача (NTTP) на етапі компіляції:

struct MyFunctor {  
 // Неконстантні дані, які будуть передаватися з ітерації в  
 // ітерацію  
 struct NonConstexprData {  
 int foo;  
 };  
// Визначте тип виходу вашої функції тіла циклу for.  
 // Це має бути тип "NonConstexprData", за яким йдуть  
 // типи ваших NTTP (відсутні).  
 using OutputType = std::tuple;  
 // Визначте функцію тіла циклу for  
 template   
 static constexpr OutputType func(NonConstexprData  
 input_data) {  
 // ваш код ...  
 return { /* оновлений 'input_data' */ };  
 }  
};

текст перекладу
Першим елементом вашого функтора має бути ще одне визначення структури. Цей тип є даними, з якими працює цикл for, і це те, що буде повернуте на місце виклику. Ці дані передаються з ітерації в ітерацію. Визначення структури має бути точно з назвою “NonConstexprData”. Її назва походить від того, що ця структура не є constexpr (константною на етапі компіляції) всередині тіла циклу for. Проте, вона є constexpr, коли повертається на місце виклику. Нарешті, щодо її вмісту немає обмежень.

2. Після визначення “NonConstexprData” має йти псевдонім типу. Він має бути точно таким, як показано вище, якщо ви не використовуєте один чи більше NTTP (параметрів шаблонів типів користувача). Якщо ви використовуєте один або більше NTTP, то типи NTTP мають йти після “NonConstexprData” в тому ж порядку, в якому вони з'являються у шаблоні вашої функції. Мета псевдоніму типу — описати тип, який повертається функцією. Це дозволяє CEXForLoop передавати ваш об'єкт “NonConstexprData” та NTTP з ітерації в ітерацію. Не хвилюйтеся, якщо ви трохи заплуталися.
текст перекладу
Приклад в кінці має допомогти розібратися.

3. Після того як ви визначили “OutputType”, потрібно визначити функцію, яка буде тілом циклу for. Вона повинна мати таку ж підпис та назву, як показано, за винятком випадку, коли ви вирішите використовувати до 50 необов'язкових NTTP користувача. У цьому випадку частина шаблону підпису змінюється; не забувайте синхронізувати “OutputType”, якщо ви додаєте NTTP користувача. Під час написання функції слід пам'ятати наступне:

- Перше NTTP — це змінна ітерації.
- NTTP, які йдуть після першого, є NTTP користувача. NTTP — це механізм для передачі значень constexpr між ітераціями.
- “NonConstexprData”, параметр функції, це дані, з якими цикл for “працює”. Це те, що повертається на місце виклику і те, що передається з ітерації в ітерацію.

## Крок 3: Виклик циклу For

Тепер, коли ви визначили функтор, ви готові викликати його за допомогою циклу for.
текст перекладу
CEXForLoop надає шаблонну функцію, яка приймає 8 шаблонних параметрів та 0 параметрів функції. Синтаксис натхнений циклом for в стилі C, але з практичних причин деякі параметри виглядають трохи складно. Не хвилюйтеся, спочатку я поясню призначення та вимоги до кожного параметра, а в наступному розділі поділюсь порадами та трюками, які зроблять його менш складним. Шаблонні параметри у порядку:

1. (Тип) Тип змінної ітерації
2. (Значення) Початкове значення змінної ітерації
3. (Тип) Тип функтора для булевої виразу. Ітерація триває, поки булевий вираз повертає true. Цей функтор схожий на ваш функтор тіла циклу for, оскільки це типізована булева функція, але з іншими обмеженнями (див. README репозиторію). Ймовірно, ви будете використовувати один з наданих булевих виразів (із “CEXForLoop/bool_expressions.h”).
4.
текст перекладу
(Value) Кінцеве значення змінної ітерації; це значення порівнюється (через функтор булевого виразу) з поточним значенням ітерації в кінці кожної ітерації.
5. (Value) Значення збільшення для змінної ітерації; сума цього значення та поточного значення ітерації використовується для наступного значення ітерації.
6. (Тип) Тип функтора циклу for; це функтор, який ви визначили в попередньому підрозділі.
7. (Тип) Початкові значення для користувацьких NTTP. Це найскладніша частина CEXForLoop; не хвилюйтеся, якщо ви не розумієте, є допоміжна функція нижче, яка приховує більшу частину цієї складності. Початкові значення мають дуже специфічну форму типового кодування. Це “std::tuple<…>”, де N-й параметр шаблону відповідає N-му користувацькому NTTP; більше того, кожен елемент є “std::integral_constant”, де тип — це тип цього NTTP, а значення — початкове значення цього NTTP.
8.
текст перекладу
(Тип) Початкове значення для об'єкта “NonConstexprData”; це значення передається в першу ітерацію. Воно повинно бути закодоване типом через структуру, ось так:

struct /назва вашої структури початкового значення/ {
static constexpr /назва вашого функтора/::NonConstexprData
value = /ваше початкове значення/";
};
```

Поради та хитрощі

Використання CEXForLoop має деякі складні аспекти. Щоб зменшити їх, я написав допоміжний механізм шаблону і знайшов кілька трюків:

У визначенні функтора створіть псевдонім для типу змінної ітерації (параметр шаблону 1 на сайті виклику). Використовуйте його як в визначенні функції “func”, так і на сайті виклику. Це робить ваш код більш DRY, що значно покращує підтримуваність.
Визначте структуру початкового значення (параметр шаблону 8 на сайті виклику) у визначенні функтора тіла циклу for.
текст перекладу
Це особливо корисно, якщо ви викликаєте цикл for лише в одному місці, або якщо він завжди повинен мати одне і те саме початкове значення. Це може не підходити для всіх випадків використання CEXForLoop, але ця тактика робить вашу реалізацію більш локалізованою, що покращує читабельність.
Використовуйте допоміжний шаблон для кодування типу NTTP. Найгірший параметр шаблону — це кортеж початкових значень кодуваних NTTP користувача (параметр шаблону номер 7). Це не дуже приємно писати, особливо тому, що вам потрібно дублювати типи NTTP користувачів ще в одному місці. Саме тому я написав допоміжний шаблон, який кодує constexpr значення за вас. Нижче наведені два фрагменти коду, які демонструють роботу допоміжного шаблону для 0 NTTP користувача та для 1 або більше NTTP користувачів.
Визначте початкові значення NTTP користувачів всередині вашого функтора тіла циклу for через псевдонім типу.
текст перекладу
Це має ті самі переваги та попередні умови, що й визначення початкових значень “NonConstexprData” всередині вашого функтора (порада та трюк #2).

// 0 NTTP користувачів  
cex_for_loop::TypeEncodedNTTPs::type

// 1 або більше NTTP користувачів  
cex_for_loop::TypeEncodedNTTPs::template   
type

Базовий приклад

Ось базовий приклад (який можна запустити на Godbolt тут), що демонструє всі елементи, зібрані разом.

#include   

#include   
#include   

struct MyFunctorWithNTTP1 {  
 struct NonConstexprData {  
 std::array i_tracker;  
 };  
 using IType = std::size_t;  
 using OutputType = std::tuple;  
 template   
 static constexpr OutputType func(NonConstexprData data) {  
 std::get(data.i_tracker) = I;  
 // якщо це останній індекс масиву, повертаємось на початок  
 constexpr std::size_t UpdatedAppendIndex =  
 (AppendIndex == (data.i_tracker.size() - 1)) ?  
 0 :  
 AppendIndex + 1;  
 return { data, UpdatedAppendIndex };  
 };  
 struct TypeEncodedInitialValue {  
 static constexpr NonConstexprData  
 // нульова ініціалізація масиву  
 value = {{}};  
 };  
 using InitialNTTPs = cex_for_loop::TypeEncodedNTTPs<  
 MyFunctorWithNTTP1>::template type<0>;  
};  
constexpr auto kData = cex_for_loop::func<  
 MyFunctorWithNTTP1::IType, 0,   
 cex_for_loop::BoolExpressionFunctor_LT, 200,  
 1, MyFunctorWithNTTP1,   
 MyFunctorWithNTTP1::InitialNTTPs,  
 MyFunctorWithNTTP1::TypeEncodedInitialValue>();  
static_assert(std::get<0>(kData.i_tracker) == 100,   
 "Це має бути правдою");  
static_assert(std::get<99>(kData.i_tracker) == 199,   
 "Це має бути правдою");

Шлях розробки

Мій шлях розробки аж ніяк не був прямим.
текст перекладу
У цьому розділі я свідомо є детальним для автентичності. Я вважаю, що історії про розробку занадто часто розповідаються як лінійний процес. Якщо пощастить, можуть бути поділені кілька експериментів чи проблем, але автор зазвичай фокусується на налаштуванні задачі та швидкому досягненні кінцевого результату. У цьому розділі я беру час, щоб описати, як це насправді було: мої невдачі, мої експерименти, мої думки на той момент тощо... Ось моя історія розробки.

Лінійне рішення

Перше рішення, як згадувалося раніше, було механізмом, вбудованим у мою бібліотеку серіалізації/десеріалізації (див. “Вступ до програмування на етапі компіляції”).
текст перекладу
Попри свою простоту, цей механізм є досить потужним і відповідає всім функціям CEXForLoop, за винятком того, що це лінійне рішення в плані кількості ітерацій та необхідної глибини шаблону.

Як практикуючий розробник за методологією TDD для функціональних частин коду (як цей), я вважаю, що інтерфейс є логічним місцем для початку, оскільки це передумова для тестування. Зосереджуючись безпосередньо на інтерфейсі, моя мета полягала в тому, щоб інкапсулювати робоче лінійне рішення та протестувати його за допомогою constexpr for loop (циклу на етапі компіляції) від 0 до 4 з кроком 1. Під час створення інтерфейсу мені було потрібно, щоб користувач міг «впровадити» свою поведінку для тіла циклу в CEXForLoop. Я спробував кілька різних методів, але врешті-решт зупинився на рішенні, яке досі використовується в CEXForLoop, коли користувач передає тип структури, яка містить бажану поведінку.
текст перекладу
Хоча я не усвідомлював цього на той момент, це була моя перша зустріч з типом кодування (type encoding), який, як ви побачите, буде повторюватися на протязі цього шляху.

З написаним інтерфейсом і успішно пройденим простим тестом, я продовжив роботу. Я застосував рішення «функтор» для булевого виразу (boolean expression) циклу, дозволяючи користувачу змінювати його на місці виклику. Наступним кроком було вирішення ключової проблеми: проблеми лінійності.

Логічне рішення

Перед тим як вирішити написати CEXForLoop, я шукав вже існуючі рішення, як це і належить робити. Я не знайшов нічого, що б відповідало вимогам для моєї бібліотеки серіалізації/десеріалізації:

constexpr змінна ітерації
кількість ітерацій, краща за лінійну, у порівнянні з необхідною глибиною шаблону
підтримка C++14

У своїх дослідженнях я знайшов статтю з надихаючою ідеєю, яка досі використовується в поточній реалізації CEXForLoop.
текст перекладу
Стаття Майкла Газонди Compile Time Loops with C++11 — Creating a Generalized static_for Implementation описує інстанціювання шаблонів за допомогою n-арного дерева, а не безпосередньо. Це перетворює лінійне рішення в логарифмічне, дозволяючи реалізації циклу for легко обробляти тисячі ітерацій.

Ін N-арне дерево, де N = 5, а висота дерева 3

Я кілька разів прочитав статтю, намагаючись вловити якомога більше інформації. На моє здивування, я виявив, що, незважаючи на назву статті, код не є constexpr, що означає, що його «static_for» не можна виконати на етапі компіляції. Моя інтуїція підказала мені скопіювати його код і адаптувати під свої потреби. Я мав правильну ідею, але зазнав невдачі.
текст перекладу
Виявилося, що є деяка правда в прислів'ї "читати код важче, ніж писати"; я знайшов це особливо вірним, оскільки мені було важко навіть писати код, що виконується на етапі компіляції. Замість цього я орієнтувався на його код, але написав власну реалізацію. Це дозволило мені здобути досвід і впевненість, що виявилося критично важливим для наступних випробувань.

Моє логарифмічне рішення трохи відрізнялося від Майкла. Моя реалізація вводила константу “#define” для максимальної глибини шаблонів, яку CEXForLoop може використовувати. Я вручну відстежував глибину інстанціювання шаблонів, щоб дотримуватися цього ліміту. Інший аспект моєї реалізації, який відрізнявся від Майкла, полягав у тому, що моє рішення залежало від обчислення ітерацій за допомогою шаблонних параметрів "start", "end", "inc" та булевої виразної функції.
текст перекладу
Обмежуючи булевий вираз до "менше", "менше або дорівнює", "більше" та "більше або дорівнює", обчислити кількість ітерацій стає тривіально просто.

Ось опис того, як працювала моя реалізація: коли CEXForLoop викликався, корінь дерева n-ary (N-арного дерева) ініціалізувався. Корінь дерева обчислює, скільки ітерацій він має виконати. Потім він створює ітерації, використовуючи лінійне рішення до ліміту, визначеного в "define". Якщо він завершує свої відповідні ітерації, він повертає дані з останньої ітерації. Якщо ж ні, він створює N дочірніх елементів, кожен з яких відповідає за 1/N частину залишкових ітерацій. Ці дочірні елементи створюються шляхом інстанціювання того ж шаблону, що й у кореня дерева. Дані від одного дочірнього елемента передаються наступному, поки не залишиться жодного дочірнього елемента, і на цьому етапі дані повертаються на місце виклику.
текст перекладу
Я довільно вибрав N рівним 8 для цієї реалізації.

Після кількох успішних тестів, включаючи тест з кількістю ітерацій 2 000, я спробував рефакторити реалізацію моєї бібліотеки серіалізації/десеріалізації для використання CEXForLoop. Я швидко зрозумів, що не врахував одну вимогу. Хоча "примітивне" рішення є лінійним, додаткові NTTP (незмінні параметри шаблонів типів) можна було б легко додати. Багато моїх реалізацій використовували NTTP для відстеження індексу "додавання" для "std::array", який є значенням, що повертається моїми функціями. Я спробував використати структуру "NonConstexprData" (яка на той час називалася інакше) для зберігання індексу додавання, але це не вдалося, оскільки її дані не є constexpr. Простими словами, ви не можете записувати в масив у контексті constexpr за неконстантним індексом. Я розглядав варіант, щоб мій код шукав індекс додавання щоразу, коли він був потрібен, ітерацією через масив, але це виглядало огидно.
текст перекладу
Я написав CEXForLoop, щоб покращити constexpr for цикли, і використовувати тимчасове рішення, як це, йде врозріз з самою метою створення цієї бібліотеки. Мені потрібен був спосіб передавати constexpr значення між ітераціями, як я це робив за допомогою NTTP в моєму "примітивному" рішенні.

Рішення, яке передає Constexpr значення

Ця проблема виявилася набагато складнішою, ніж я спочатку очікував. Моя мета була чіткою: користувач CEXForLoop має мати змогу передавати довільний набір constexpr значень; ці значення повинні передаватися від однієї ітерації до іншої, дозволяючи змінювати їхні значення між ітераціями.

Я витратив багато часу, "блукаючи". Це можна описати як спробу зробити щось, що ви не знаєте як зробити, і здається, що ви не рухаєтеся вперед. Ви пробуєте одне рішення — воно не працює, пробуєте інше — і воно теж не вдається. Спробуєте третє, і воно знову не працює! Але, принаймні, ви дізналися кілька важливих уроків. І тоді ви починаєте цікавитись, чи дійсно те перше рішення не працює.
текст перекладу
Зрештою, ви вже не та людина, яка спробувала те рішення, тепер ви більш обізнані. В цьому процесі "блукання" я засвоїв такі уроки:

Параметри функції ніколи не є constexpr в контексті самої функції, навіть якщо функція є constexpr.
“const” означає значно більше, ніж “constexpr”.
Щоб передати constexpr значення в функцію і мати його як constexpr в межах функції, потрібно використовувати параметри шаблону.
У C++14 NTTP (non-type template parameters) не можуть бути визначеними типами користувача.

Цей процес "блукання" досяг такого рівня, що я почав сумніватися, чи взагалі моя мета досяжна. Я провів експеримент у своїх думках: Як я передаватиму constexpr значення між ітераціями, якщо ці ітерації будуть просто викликами функцій одна за одною? Наприклад, якщо ітерація була б від 0 до 4 з кроком 1, це виглядало б так:

 // Визначення тіла циклу користувача  
template  
constexpr auto func(...) {  
 // ...

текст перекладу

// Виклик на сайті
constexpr result1 = func<0, ....>(initial_value, ...);
constexpr result2 = func<1, ....>(result1, ...);
constexpr result3 = func<2, ....>(result2, ...);
constexpr result4 = func<3, ....>(result3, ...);
constexpr result5 = func<4, ....>(result4, ...);
```

Без усіх цих хитрощів і магії, ось що насправді робить CEXForLoop. Тому рішення повинно використовувати шаблони як механізм для передачі constexpr значень у функцію користувача. І щоб користувач міг змінювати ці constexpr значення перед передачею їх у наступну ітерацію, ці значення повинні бути повернуті як частина значення, що повертається функцією.

Оскільки серіалізація/десеріалізація вже була на моєму розумі, а моя мета полягала в тому, щоб користувач міг передавати довільні constexpr дані, я уявив реалізацію, в якій constexpr дані серіалізуються та десеріалізуються. Я надавав би дві допоміжні функції: одну для серіалізації, а іншу для десеріалізації.
текст перекладу
Коли користувач викликає CEXForLoop, він передає свої серіалізовані constexpr дані як параметри шаблону. Оскільки дані можуть мати довільну довжину, використовується варіативний NTTP (Non-Type Template Parameter):

template

Потім, всередині їх реалізації, доступ до їхніх constexpr даних можна отримати, використовуючи мою надану допоміжну функцію десеріалізації для “NTTPBytes”.

Цей експеримент не вдався через серіалізацію та десеріалізацію під час компіляції. Я думав, що зможу серіалізувати/десеріалізувати об'єкт, отримавши вказівник на байти об'єкта; однак це вимагає приведення типу, що не можна виконати за допомогою “staticcast”.
текст перекладу
(“staticcast” — це єдиний дозволений каст компіляцією.) Оглядаючись назад, я радий, що цей експеримент не вдався, оскільки він виявився неефективним та складним порівняно з поточною реалізацією CEXForLoop.

Без можливості серіалізувати/десеріалізувати об'єкт, необхідно передавати constexpr значення з їхніми типами. Знову ж таки, я задумався, чи це можливо, оскільки моя мета полягала в тому, щоб передавати варіативну кількість NTTP (Non-Type Template Parameters) довільних типів. Я провів більше досліджень, але без великих успіхів, поки не натрапив на “std::integral_constant” на cppreference. Ось ще одна поява повторюваної теми в програмуванні на часі компіляції з C++: кодування типів. “std::integral_constant<…>” — це шаблонний тип, де перший параметр — це тип, а другий параметр — це NTTP першого типу.
текст перекладу
Це механізм для кодування типів NTTP (Non-Type Template Parameters) довільного типу!

Щоб захопити всі типи закодованих NTTP початкових значень, що передаються до інтерфейсу CEXForLoop, можна використати “std::tuple”. Цей шаблонний тип є стандартною структурою даних, що підтримує constexpr і дозволяє зберігати різноманітні значення.

Моя наступна спроба полягала в застосуванні цього механізму до моєї існуючої реалізації логічного рішення. Однак виникла фундаментальна проблема, оскільки рекурсія виконувалася за допомогою механізму шаблонної функції:

template   
 static constexpr auto func(FunctorData initial_data) ->  
 typename   
 std::enable_if::type {  
 return func(  
 BodyFunctor::template func(initial_data));  
 };

Оскільки “FunctorData” (також відома як “NonConstexprData”) є параметром функції, її значення не є constexpr у межах цієї функції.
текст перекладу
У цьому контексті це нормально, оскільки значення використовується лише як параметр функції. Згадайте, що функції, позначені як constexpr, можуть повертати constexpr результат. Компілятор повідомить про помилку, якщо функцію не можна буде оцінити на етапі компіляції. Однак, функція, позначена як constexpr, означає, що її результат буде constexpr лише в тому випадку, якщо вона була викликана з constexpr значеннями. Оскільки під час виконання програми функція, позначена як constexpr, є звичайною функцією, не передача constexpr значень у точці виклику еквівалентна виклику звичайної функції під час виконання. Шаблони ж, з іншого боку, повинні бути викликані з constexpr значеннями, оскільки вони ініціалізуються на етапі компіляції.

Отже, проблема при спробі передати користувацькі NTTP з ітерації в ітерацію: Як зазначалося раніше, для того, щоб передати NTTP, його значення повинно бути constexpr. Я хотів, щоб значення користувацьких NTTP приходили з попередньої ітерації. Ітерація (тобто виклик функції тіла користувацького циклу) повертає об'єкт "NonConstexprData" та оновлені значення користувацьких NTTP.
текст перекладу
Це вказує на те, що потрібно зберегти результат виконання функції тіла циклу до переходу до наступної ітерації. Однак, “initial_data” (тобто “NonConstexprData”) не є constexpr у межах функції, тому виклик функції тіла циклу не поверне constexpr значення. Оскільки неможливо передавати визначені користувачем типи структур як NTTP та неможливо визначити тип усередині функції, неможливо просто перемістити цей параметр функції до параметра шаблону.

Ця перешкода вказала на те, що мені потрібно було рефакторити реалізацію логічного рішення. Моя думка знову повернулася до експерименту, в якому ітераційні функції викликаються одна за одною.
текст перекладу
Цього разу моє основне усвідомлення полягало в тому, що результат функції тіла циклу користувача є змінною constexpr в тій самій області видимості, що і виклик функції наступної ітерації.

Щоб імітувати таку поведінку, я досліджував розгортання рекурсивної функції за допомогою структур, які умовно інстанціюються на основі кількості ітерацій. Я почав із простішої задачі, де я розгортав тільки лінійну рекурсивну функцію до максимальної кількості ітерацій 5.

Умовне інстанціювання досягається за допомогою “std::enableif”, яке базується на концепції C++ під назвою_ SFINAE (“неприпустимість заміни не є помилкою”). Ця стандартна структура шаблону використовується з моменту першої “примітивної” реалізації. Вона працює так: Якщо B істинне, структура “std::enableif” містить псевдонім типу для T, що успішно дозволяє розв’язати шаблон._
текст перекладу
Однак, якщо B — “неправда”, структура не міститиме псевдоніму, і розв'язання цього шаблону не відбудеться, що призведе до вилучення функції або структури, в якій він використовується, з кандидатів шаблонів.

У цій реалізації є 6 структур для “відсутності ітерації” та ітерацій від 1 до 5. Кожна структура визначає змінну constexpr, яка дорівнює результату попередньої структури. Структура першої ітерації базується на початкових значеннях користувача, переданих як параметри шаблону. Реалізація “включає” необхідні ітераційні структури, щоб досягти кількості ітерацій. Далі визначено набір перевантажених функцій SFINAE, щоб розв'язання шаблону повернуло результат з останньої інстанційованої структури (тобто з останньої ітерації). Це дозволяє публічному інтерфейсу залежати лише від цієї функції; реалізація зробить правильну операцію, повертаючи результат з відповідного визначення структури.

Після тестування того, що ця реалізація успішно ітерує, я додав один NTTP користувача.
текст перекладу
Для цього я додав два вимоги до функтора тіла циклу користувача:

Псевдонім “OutputType” має бути визначений як кортеж, що містить “NonConstepxrData” (дані, що не є constexpr), а після нього типи NTTP користувача (в порядку їх появи).
Повертаюче значення фактичної функції повинно бути “OutputType”.

Зміна типу повернення дозволяє CEXForLoop передавати NTTP користувача з ітерації в ітерацію. Псевдонім є передчасною вимогою, яка дозволяє майбутнім реалізаціям вибирати (за допомогою “std::enable_if” SFINAE) реалізацію, що обробляє кількість використаних NTTP користувача. Цей вибір реалізації передбачає багато дубльованого коду, оскільки реалізації будуть однаковими, за винятком того, як обробляються NTTP користувача. Зазвичай дублювання коду означає, що ви робите щось неправильно, але в цьому випадку це необхідно, оскільки я навмисно розгортаю рекурсію.
текст перекладу
Отже, замість того щоб писати це вручну (що легко призводить до помилок), я написав Python-скрипт, щоб зробити це за мене.

Цей підхід спрацював! З тестом, що проходить і викликає CEXForLoop з 0 до 4 з кроком 1 та NTTP користувача, я почав писати узагальнену реалізацію. Дотримуючись тієї ж схеми розгортання рекурсії, я почав розгортати аспект n-арного дерева у моєму логічному рішенні.

Цього разу я розгорнув експоненційну рекурсію. Такий підхід до розв'язання задачі допоміг мені в процесі розгортання: експоненціальні структури — це вузли на n-арному дереві. Рекурсивна природа цих структур є просто розгорнутим лінійним розширенням, але замість того, щоб лінійне розширення працювало на функціоналі тіла циклу користувача, воно працює на самій собі — поки не досягне деякого порогу, для якого пряме лінійне розширення функції тіла циклу користувача є прийнятним.
текст перекладу
Знову нагадаємо діаграму для n-арного дерева:

Тема: N-арне дерево, де N дорівнює 5, а висота — 3

Якби ця діаграма була реалізацією, ми почали б з кореневого вузла, не показаного на малюнку, який знаходиться вище за все дерево. Далі ми лінійно розгортали б 5 разів (верхній рядок). У кожному з цих розширень ми розгортаємо ще 5 разів (середній рядок). У кожному з цих розширень ми розгортаємо ще 5 разів, викликаючи функцію ітерації користувача у кожному розширенні (нижній рядок). Ця реалізація могла б підтримувати до 5³ = 125 ітерацій з необхідною глибиною шаблону приблизно 15.
текст перекладу
Інстанціювання шаблонів слідує подорожі по дереву в порядку попереднього обходу.

Перед тим як закріпити зміни, я хотів переконатися, що всі мої існуючі тести проходять:

Жодна ітерація не повертає початкові значення.
Проста ітерація (інкремент на одиницю з виразом порівняння "менше") для короткої кількості ітерацій (приблизно 5) без користувацьких NTTP між ітераціями.
Проста ітерація (інкремент на одиницю з виразом порівняння "менше") для короткої кількості ітерацій (приблизно 5) з одним користувацьким NTTP між ітераціями.

Ці тести пройшли успішно, але коли я тестував більш довгі прості ітерації (близько 1000), то натрапив на обмеження глибини шаблону компілятора. Я спробував налагодити код безпосередньо, але важко аналізувати код на наявність помилок без його виконання. Після деяких пошуків помилки, я зрозумів, що проблема полягала в тому, як я обробляв кількість ітерацій. Не впевнений, що в мене є готове рішення для журналу, я створив апарат для тестування на етапі компіляції та профілював свій код.
текст перекладу
(Дивіться аркуш "IterationCountBasedStrategy" в таблиці.)

Задоволений, що я досяг вирішення задачі через лог, я написав останній тест — своєрідний інтеграційний тест, який перевіряє багато аспектів коду.

Ітерація від 3000 до 0 з виразом "більше ніж" (greater-than) з кроком -3 і передаванням одного користувацького NTTP між ітераціями.

Тест не пройшов, і я не міг зрозуміти чому. Я повернувся до свого апарату для тестування на етапі компіляції, щоб ще раз перевірити свою роботу. Врешті-решт я звузив проблему до відстеження ітерацій. Усі мої попередні тести інкрементували значення на 1 і використовували вирази "менше ніж" (less-than) або "менше або рівно" (less-than-equal-to), але в цьому тесті я не використовував жодного з цих варіантів. Хоч я й намагався, мій код був занадто складний для того, щоб пройти його в голові. Мені потрібен був спосіб налагодження програми, але оскільки все це відбувається на етапі компіляції, традиційні методи налагодження не працюють.
текст перекладу
Часто найкраще, що можна зробити, — це створити кілька виразів “static_assert”, що є еквівалентом налагодження через “printf”. Я не маю нічого проти цієї стратегії, але це не панацея, і вона не працювала для мене. Я взяв ручку та папір, де зміг подумати про проблему більш абстрактно, не турбуючись про правильність/синтаксис коду. Я придумав таке рішення:

Моє вирішення, виписане в нотатнику

Однак це рішення так і залишилось реликвією в моєму нотатнику, оскільки я так і не реалізував його. Замість цього воно привело мене до кращої ідеї: використання самого логічного виразу для керування ітерацією. Це те, що робить звичайний цикл у стилі C. Спроба обчислити кількість ітерацій і гратися з параметрами "start" та "stop" складна; я вже двічі не зміг зробити це правильно. Ця стратегія була набагато простішою.
текст перекладу
Це припускало б нескінченні ітерації, і знаходило б останню ітерацію за допомогою виконання логічного виразу.

Моя перша проста реалізація з цією стратегією виконує логічний вираз для інтервалів кількості ітерацій, за які вона відповідає, і зберігає результат останнього підтримуваного інтервалу. Це значення використовувалося для умовної інстанціації структур ітерацій, відповідальних за ці інтервали. Ця стратегія спрацювала!

Я перейшов до своєї фінальної реалізації з тією ж стратегією. Ось приклад, який пояснює процес: Розглянемо ту ж діаграму n-арного дерева, що й у моїй реалізації. Оскільки цикл розгорнутий, кожен батьківський вузол може обчислити діапазони ітерацій своїх нащадків.
текст перекладу
Лівий верхній 0 може визначити, що його 0 нащадок матиме перші 5 ітерацій, його 1 нащадок — наступні 5 ітерацій і так далі. Отже, коли він буде інстанційовано, він виконує логічний вираз для того, яким буде значення змінної ітерації на 0-й ітерації, на 5-й, на 10-й і так далі. Останній діапазон ітерацій використовується для вибору шаблонів, які будуть інстанційовані.

Я поступово тестував свою реалізацію тими ж тестами. Вони проходили, поки я не спробував зробити довгу ітерацію (приблизно 1 000) без користувацьких NTTP. Тест не компілювався через перевищення максимального глибини шаблону. На моє здивування, той самий тест з одним користувацьким NTTP пройшов! Я порівняв реалізації з нулем і одного користувацького NTTP, шукаючи відмінності, але єдині відмінності були саме в самих NTTP. Сподіваючись отримати більше інформації, я профілював реалізацію без користувацьких NTTP і з’ясував, що це була лінійна реалізація.
текст перекладу
(Див. "BoolExpressionBasedStrategy0UserNTTPswithBUG" у таблиці даних.)

До цього дня я не розумію, чому ця реалізація є лінійною, але після кількох годин відлагодження я вирішив припинити і почати шукати обхідне рішення. Реалізація здебільшого прихована для користувачів CEXForLoop; вони побачать деталі лише у разі помилки компіляції. Тому я змінив свій Python-скрипт, щоб він генерував спеціальну реалізацію для випадку з нульовим користувацьким NTTP. Замість того щоб слідувати шаблону, скрипт генерує адаптер до реалізації з одним користувацьким NTTP. Для цього створюється CEXForLoop-функціонал з одним користувацьким NTTP. Цей функціонал викликає функцію тіла циклу користувача.
текст перекладу
З усіма тестами, що пройшли, я профілював це рішення і виявив, що це справді логарифмічне рішення, яке може передавати значення constexpr! (Див. "BoolExpressionBasedStrategy0UserNTTPswithHACK" у таблиці даних.)

Майбутні напрями

Я почав цей шлях, тому що проігнорував стародавній принцип "YAGNI" (You Aren’t Gonna Need It — Тобі це не знадобиться) — і тепер, іронічно, я дотримуюсь його. "Що сталося?" — можливо, ви запитаєте. Все просто: я ірраціональна людина. Я хотів вирішити проблему серіалізації/десеріалізації, навіть не маючи гострої необхідності в цьому на той момент. Тепер я приймаю усвідомлення, що те, що ти можеш вирішити проблему, не означає, що ти повинен це робити — принаймні не одразу. Отже, ось я, приймаю YAGNI і відкладаю ці ідеї... поки що.

Говорячи про майбутнє CEXForLoop, однією з моїх основних цілей є рефакторинг методу передачі даних у бібліотеці.
текст перекладу
На додаток до поточного підходу використання визначених користувачем невизначених параметрів шаблонів (NTTP) як значень constexpr, я розглядаю можливість того, щоб користувач передавав значення constexpr типу структури. Я вважаю, що це можна реалізувати за допомогою кодування типів, тієї ж техніки, яку бібліотека вже використовує для передачі значень constexpr. Початкове значення цього визначеного користувачем типу структури буде закодовано таким же чином, як і початкові дані "NonConstexprData". "OutputType" ймовірно залишатиметься кортежем з "NonConstexprData" та цього користувацького типу структури. Усередині CEXForLoop, замість того щоб захоплювати і передавати користувацькі NTTP, буде захоплювати, кодувати тип і передавати цей тип користувацької структури.

Я також розглядав можливість рефакторингу інтерфейсу булевих виразів, що дозволяє передавати більше даних — таких як "NonConstexprData" користувача та/або раніше обговорений constexpr тип користувацької структури.
текст перекладу
Це дозволить створювати більш виразні булеві вирази, де результати залежать не лише від поточної змінної ітерації та кінцевого значення циклу. Один з практичних варіантів використання — реалізація функції "break": користувач може ввести прапорець у свою структуру, встановити його на основі умов всередині циклу, і змусити булевий вираз повертати false, коли прапорець спрацьовує.

Наразі я повернувся до роботи над моєю бібліотекою серіалізації/десеріалізації — слідкуйте за оновленнями! Тим часом, ви можете переглянути поточну версію CEXForLoop на GitHub або спробувати її онлайн через Godbolt.

Особисті висновки

Я не очікував, що цей відступ від моєї розробки пристрою для руху займе стільки часу, але думаю, що моє майбутнє я буде вдячний за це. Я не вірю в жалкування. Ця подорож навчила мене багатьох важливих речей про C++, особливо про програмування на етапі компіляції за допомогою constexpr та шаблонів.
текст перекладу
Я горджуся тим, що довів цю бібліотеку до кінця, навіть коли це здавалося неможливим. Метапрограмування на шаблонах — це складна тема, але я зрозумів достатньо, щоб створити щось корисне!

Перекладено з: Pushing the Limits of C++: How I built a constexpr for loop library