Алиса: А почему это место ОЧЕНЬ странное место?
Додо: А потому, что все остальные места — очень уж не странные. Должно же быть хоть одно ОЧЕНЬ странное место.

Итак, рассмотрим текст шаблонного класса BitSet с целью его адаптации к требованиям МК, основные направления оптимизации были определены ранее. Можно, конечно, написать свой собственный класс с нуля, но не будем пренебрегать возможностью ознакомиться с хорошими решениями, ведь библиотека STL (не путать с spl) известна давно и используется повсеместно. Для начала следует найти исходный код, после недолгого странствия по Инету я просто открыл директорию с моим MinGW и разыскал требуемый файл, который и намерен далее обсуждать.

В начале мы видим чуть более страницы с копирайтом и текстом лицензии, а также разнообразные предупреждениями — ну это можно пропустить, это для юристов. Далее идут инклуды и я выражаю благодарность авторам — каждый сопровождается комментарием, о том, что мы хотим получить из каждого файла — все бы так делали, работа ~~Индианы Джонса~~ исследователя была бы проще. Далее идут дефайны, я не фанатик чистоты кода и не буду спорить — пусть будут и сразу же вижу определении числа битов в единице хранения, которой является unsigned long. Продолжая движение по скользкому пути дефайнов, завожу свое определение единицы хранения, которая приравнивается uint8_fast, хотя и понимаю, что этого будет явно недостаточно. Кстати, сразу приношу еще одну благодарность авторам за стиль — в конце модуля они убирают за собой, уничтожая внутренние дефайны — уже и не надеялся, что увижу такое в современном продакшене.

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

Далее обнаруживаем основной класс class bitset (теперь именно класс), производный от шаблонной структуры (да, в С так можно, непонятно, зачем так делать, но можно), в котором опять определяется тип хранения и опять меняем на свой. Но здесь я задумался — а почему тип не наследовался от родительской структуры и с изумлением обнаружил (да с изумлением, шаблонные классы — это не то, чем я занимаюсь в повседневной жизни), что наследование шаблонных классов несколько отлично от обычных. То есть наследование как раз такое же и все сущности родителя доступны в дочернем (надеюсь, никто не примет меня за гендерного шовиниста) классе, но их необходимо указывать с полным именем. Ну это еще можно понять, иначе компилятор не догадается, какой из инстанцированных вариантов применить, но в случае использования определенных в классе типов надо еще добавить ключевое слово typename. Совершенно не очевидное решение, особенно меня порадовала диагностика компилятора, в переводе означающая «может быть, вы имели в виду тип из родительского класса» — да, спасибо капитан, именно его я и имел в виду, рад, что мы понимаем друг друга, но мне легче не становится. Впрочем, такая диагностика имеет место в старой версии GCC, в текущей сообщение становится более понятным «возможно, вы забыли ключевое слово typename». Понимание диагностических сообщений компилятора для шаблонных классов — это вообще тема отдельной песни, и песня эта отнюдь не радостная.

Так что, если мы не хотим в дочернем классе постоянно использовать конструкцию

std::_Base_bitset<Nb>::_WordT

(а мы не хотим, нег?) то у нас есть три пути

1) тривиальный

#define _WordT typename _Base_bitset<_Nb>::_WordT

2) очевидный – определение типа на глобальном уровне и мне больше понравился

3) для любителей странного

typedef  typename _Base_bitset<_Nb>::_WordT _WordT;

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

Есть еще и метод 4)

 using _WordT = std::_Base_bitset<Nb>::_WordT;

но в моей версии компилятора он не работает, так что его нет.

Примечание на полях (Пнп)- в замечательной книге «C++ for real programmers» (в свое время я ее закачал по ошибке, решив, что она посвящена С++ в реал-тайм системах) про язык сказано «Его элегантность заключается отнюдь не в простоте (слова С++ и простота режут слух своим явным противоречием), а в его потенциальных возможностях. За каждой уродливой проблемой прячется какая-нибудь умная идиома, изящный языковой финт, благодаря которому проблема тает прямо на глазах.» Поскольку книга действительно замечательная, значит и приведенная цитата верна (понимаю, что тут есть определенная логическая натяжка), но лично я, к сожалению, проблему вижу, а с умной идиомой напряженка.

Несмотря на оставшееся чувство легкого недоумения, задача решена и можно наслаждаться результатом — но не тут то было. При изменении размера тестового множества с 15 на 5 совершенно неожиданно возникла ошибка компиляции. Нет, все понятно, сработала не модифицированная инстанцинация с параметром шаблона 1, но со стороны выглядит это весьма странно — меняем константу и программа перестает компилироваться.

Можно, конечно, модифицировать и эту реализацию и другую, но выглядит такой подход, как грубое нарушение принципа DRY. Возможные решения есть и их более одного 1) очевидное – опять дефайн и 2) тривиальное – опять определение типа на глобальном уровне, но в этом случае он вылезет за пределы модуля, что, впрочем, он делает и в рассматриваемой реализации, высовываясь из базовой структуры, только еще и квалификатор писать будет не нужно.

Поэтому я склоняюсь к варианту 3) базовый класс для определения типа и наследование всех инстанцинаций от него. Причем сущности родительского класса защищенные, опять-таки, чтобы они не торчали наружу. Далее обнаруживаю забавное свойство, наверное, тут надо похвалить С++ за гибкость — для варианта с отсутствующим хранением тип не нужен, и язык позволяет использовать реализацию без наследования, хотя это и не особо нужно в данном конкретном случае. Сразу же обнаруживаю еще один недостаток библиотеки — во всех трех вариантах каждый раз задаются операции вычисления номера единицы хранения

static size_t _S_whichword

и маски бита в ней _S_maskbit и они совершенно идентичны — выносим их тоже в базовый класс. При этом обнаруживается «мертвый» код – метод _S_whichbyte, даже и не знаю что делать — с одной стороны, правила хорошего тона требуют его удаления, с другой — в случае шаблона это никак не сказывается на результирующем коде. Воспользуюсь правилом — «не понимаешь чего то — не трогай» и оставлю этот метод.

В принципе, модификации с точки зрения типа хранения закончены и можно приступать к тестированию. И сразу же обнаруживаю недостаток реализации — для архитектуры MSP430 почему то выделяются двух-байтовые слова вместо байтов. Конечно, не двойные слова, как раньше, но все-таки мы боремся за минимальный (во всех смыслах) код. Оказывается, компилятор уверен, что в этой архитектуре тип uint_fast8_t имеет размер 2, хотя в системе команд имеются операции работы с байтами и сам компилятор их вполне использует. Идея с использованием данного типа скомпрометирована и приходится задавать тип данных uint8_t напрямую. Ну что же, если найдется архитектура, в которой работа с байтами реализована неудачно и размер типа uint_fast8_t отличен от 1 (из имеющихся в компиляторе таковых не обнаружено), ей придется страдать ради быстродействия всех остальных.

Тестирование исправленной версии показывает ее правильную работу на различных архитектурах и с разными параметрами, но остался еще вопрос с вычислением битовых масок для МК без развитых сдвигов, в нашем случае это MSP430 и AVR. В принципе, можно просто сделать чтение битовой маски из массива методом для всех случаев, невзирая на архитектуру МК. Решение вполне себе рабочее, у развитых архитектур с индексированием все нормально, но все равно будет проигрыш по времени по сравнению с быстрыми сдвигами, а не хотелось бы, чтобы в мою сторону тыкали пальцами со словами «класс будет быстрее, говорил он, мы оптимизируем, говорил он».

Поэтому нам нужна различная реализация для наших двух слабых архитектур, которые отличаются от всех остальных размером типа uint_fast16_t — он составляет 2 против 4, либо 8 у 64 разрядных версий. Условная компиляция нам не поможет, а ставить условие в надежде на оптимизацию — это не путь самурая, остаются шаблоны. Пытаюсь создать шаблонный метод класса, но частичная специализация для него недоступна — оказывается, так и должно быть и даже нахожу статью, в которой написано, почему это хорошее решение. Честно говоря, я так и не понял, почему это решение хорошее, скорее всего, это обусловлено религиозными соображениями. Тем не менее, нас не спросили, и что остается делать — можно сделать дружественную шаблонную функцию (оказалось, что нельзя, причем по той же причине — запрещена частичная специализация), есть еще одно решение, выглядит забавно — частичная специализация метода вне тела класса. Можно вообще создать отдельную шаблонную функцию и обращаться к ней из методов класса, не знаю, какой способ правильнее, я выбрал именно этот. Да, она не имеет доступа к внутренним сущностям класса, но в данном конкретном случае это и не надо, что делать, если это потребуется, я пока не знаю, «будем решать проблемы по мере их возникновения».

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

Реализации второго варианта множества будет посвящен отдельный пост, и без того что-то много получилось.

Еще к вопросу о множествах