«Не пора ли, друзья мои, нам замахнуться на Вильяма, понимаете ли, нашего Шекспира? ».
Прочитал недавно пост про кастомную клавиатуру и в очередной раз подумал, что было бы неплохо написать эталонную (то есть такую, которую не стыдно подписать своим именем и выложить на всеобщее обозрение) реализацию клавиатуры. Мысль эта приходит ко мне НЕ в первый раз, но все как то останавливается на первом этапе — считывание исходной информации, ведь хочется сделать этот этап легко настраиваемым, удобным в использовании, универсальным и эффективным, и не нравится предложение «выбирать любые два».
Необходимое примечание — я вижу 4 слоя реализации клавиатуры: 0 — обнаружение события, 1 — считывание данных, 2 — очистка и хранение данных, 3 — формирование сообщений, 4 — перекодировка и прочее. Наиболее перспективным для слоя 1 и связанного с ним слоя 0 мне представляется применение шаблонов Антона Чижова для работы с пинами МК (основанными на классе Локи) и, может быть, когда-нибудь, получившимся результатом будет не стыдно поделится, но точно не сегодня. А сейчас я задумался над слоем 2.
Сформулируем задачу — необходимо хранить информацию о фиксированном наборе переключателей, принимающих одно из двух предопределенных значений — «замкнут» и «не замкнут». Наиболее естественным кандидатом являются логические переменные и библиотека bitset, как способ хранения набора. Поскольку требование эффективности является категорическим императивом, желательно оценить реализацию модуля с данной точки зрения.
Первая мысль была посмотреть исходные коды и все сразу станет ясно, но после краткого знакомства с оными я понял, что изучение чужих шаблонов не слишком интересное занятие (и не очень продуктивное). Кроме того, исходники не дают точной оценки эффективности реализации, так как она напрямую замкнута на компилятор. На самом деле исходный текст все равно пришлось изучать, иначе внесение в него изменений становится очень длительным процессом (если, конечно, нас интересует достижение определенного результата), но это тема отдельного поста.
Поэтому принята методика изучения «черного ящика» — подаем на вход различные фрагменты кода и рассматриваем порожденный ассемблер. К сожалению, использовать любимый сайт godbolt для привычной архитектуры AVR не представляется возможным, поскольку в данной реализации нет изучаемой библиотеки. Можно, конечно, притащить ее ручками, но нет гарантий, что это будет верный исходный код.
Поэтому будем смотреть на другой архитектуре. х51 для компилятора gcc не представлена, х86 мне никогда не нравилась, ARM имеет не слишком удобный (для человека) и понятный ассемблер, MIPS весьма специфичен и не слишком распространен, всякие SPARCи еще хуже (ну хорошо, не буду обижать кем то любимую архитектуру, не лучше), но есть великолепный кандидат MSP430, за основу которого была взята кристально прозрачная и элегантная архитектура PDP и TI не удалось ее сильно испортить (хотя ребята и старались). Библиотека множества битов для данной архитектуры представлена, так что можно приступать к изучению.
Начнем, как это тривиально не прозвучит, с начала, то есть с объявления множества. Сразу же увидим, что память для хранения выделяется четырехбайтными словами, несмотря на то, что естественной единицей в данной архитектуре является двух байтовое слово, и предусмотрена достаточно удобная и эффективна работа с байтами, что приводит к странным казусам. Можно понять автора, реализация 32-битного числа должна быть повсюду и опираться на него вполне естественно, но в данном случае 8-бит было бы предпочтительнее, а для AVR 8-бит будет единственно разумным решением.
Интересный вопрос, а как можно в процессе компиляции определить разрядность архитектуры, надо будет попробовать через uint8_t_fast. Отметим возможную оптимизацию и двинемся дальше.
Кроме выделения памяти, интерес представляет инициализация — для глобальных множеств она проводится стандартным образом — обнулением перед вызовом main, для локальных — тоже стандартным образом, то есть никак, если начальное значение явно не указано. Ну и, как всегда, если есть возможность описать статическое множество с начальным значением вне функции, этим следует пользоваться, чтобы не заводить лишних флагов и не тратить на них время исполнения. Но здесь мы никаких откровений и не ожидали, просто проверили общие правила.
Начнем работать с модификацией множества, для чего у нас есть левые квадратные скобки и методы set и reset. Мы вправе ожидать увидеть для установки элемента n во множестве M что-нибудь вроде:
M[n / w] |= (1<<(n % w))где w — количество битов в базовом элементе, что для данной архитектуры, статически определенного n (например, 4) и включенной оптимизации приводит к коду вида:
bis.w #0x0010, mДействительно, такой код мы и наблюдаем в правой половине окна, и вряд ли кто рискнет всерьез утверждать, что возможно более эффективное решение. Но это только для указанных условий, для произвольного n картина совершенно меняется, для методов мы наблюдаем проверку аргумента на допустимость с генерацией соответствующего исключения, а для скобок видим ограничение аргумента битовой маской допустимого диапазона со вполне предсказуемым неопределенным поведением, оба случая вполне соответствуют документации. Отрицательные значения обрабатываются вполне корректно, поскольку индексы рассматриваются, как без-знаковые числа.
Обратим внимание на то, что присваиваемым значением для элемента множества может быть не только 0 и 1, как можно было ожидать, но и любое целое, к которому применяется правило «Что есть единица? Не ноль», вполне логично, но слабо отражено в документации. Немного странно сделано, все-таки булевы значения были бы более естественны, пометим галочкой и идем дальше.
Сравнение кода, сгенерированного для случая статически неопределенного номера элемента множества показывает, что эффективность кода в обоих вариантах ([] и методы) весьма близка и невелика, поскольку для вычисления (1<<n) вызывается некая подпрограмма из стандартной библиотеки, причем подпрограмма эта сдвигает 32-битное число0х00000001, размещенное в двух регистрах. Посмотреть ее исходный текст мы не можем, но сам факт вызова наводит на грустные мысли. Дело в том, что в рассматриваемой архитектуре нет сдвига влево (и вправо тоже нет) на произвольное количество позиций, как во всеми (многими) любимом ARM. Есть сдвиг на 1 позицию (было бы странно, если бы его не было вовсе), есть сдвиг на 2,3,4 позиции (но на строго фиксированное в команде число, не на параметр), есть префикс REPT (но скорость его выполнения оставляет желать лучшего). Можно реализовать сдвиг младшей единицы (это важно, только одной единицы), то есть получение битовой маски по номеру бита за относительно небольшое время путем хитростей типа обмена тетрад, но это будет очень зависимая часть и, в общем случае, так лучше не делать.
Поэтому универсальным и быстрым методом было бы хранение битовых масок в массиве и индексирование, причем на данной архитектуре это еще и весьма эффективно, код выглядит тогда следующим образом:
M[n/w] |= BitArray[n %w]получая ассемблер вроде:
bis.b BitArray(r0),M(r1)Поскольку речь идет о шаблонах и w кратно размеру байта, то операции деления здесь реализуются весьма эффективно. Отметим явное преимущество минимально реализуемого элемента хранения, для байта в качестве элемента хранения потребуется массив размером 8 байт, для словной организации -2*16=32 байта, а для длинного слова в 32 бита — целых 4*32=128 байт для хранения всех требуемых масок, а зачем платить больше, если результат не меняется. Запомним еще одну возможную оптимизацию и идем дальше.
Отметим еще один факт — возможны и значительно более эффективные реализации операций работы с элементом множества, если в целевой архитектуре имеются область бит-размеченной памяти (вот тут опять вспоминается забракованный ранее ARM), где операция установки элемента вообще превращается в тыкву BitSetAddr[n]=1, что транслируется в одну команду ассемблера для константного n, но там и без того есть достаточно эффективные сдвиги, так что подобная оптимизация будет скорее избыточной, особенно принимая во внимание ее ограничения. В принципе, подобная бит-адресуемая область есть и в x51 и в AVR, но там есть эффективные команды только для константных номеров элементов, а с общим случаем все не так хорошо (откровенно плохо).
Ну а теперь внимательно посмотрим на полученный код и отметим, что мы наблюдаем артефакты, связанные с хранением множества в двойных словах. Компилятор для операции модификации элемента множества порождает последовательность команд, которые читают соответствующее двойное слово из памяти в 2 регистра (напомню, что регистры у нас 16-разрядные), модифицирует их и отправляет результаты назад в память. Если мы меняем только один элемент, то маска операции будет содержать ровно одну единицу из 32 возможных, остальные нули. Когда мы применяем статически определенный номер элемента, на этапе оптимизации должны быть исключены операции, не меняющие результат. Как правило, это и происходит, но для различных операндов что-то идет не так и в конечный код просачиваются артефакты вида:
bic #0,r0что выглядит особенно забавно, если заметить, что регистр назад в память не записывается, хотя и считывается. Строго говоря, результаты оптимизаций нигде не регламентированы, так что могут быть любыми, и обижаться не на что, но все равно «не аккуратненько как то получается». Повлиять напрямую на этот процесс мы никак не можем, если не рассматривать всерьез коррекцию исходного кода компилятора, поэтому пойдем в обход — поможем оптимизатору путем облегчения его задачи.
Кстати, до сих пор не могу найти ответ на вопрос — можно ли в С++ на уровне макроса или шаблона определить различную реализацию для статически определенного на этапе компиляции против статически не-определенного параметра. Если кто знает путь самурая, подскажите в комментариях, constexpr пробовал, не получилось.
Продолжаем исследования и обнаруживаем, что компилятор безудержно оптимизирует обращения к множеству (конечно же, если оптимизация включена), то есть порядок установки/очистки различных элементов совершенно не гарантирован и никак не связан с порядком операторов исходного кода. Создать же volatile множество мне не удалось, может быть, я что то не так делаю? Как и в случае любой локальной оптимизации, обращение к внешней функции заставляет компилятор принудительно провести все подготовленные операции для глобального массива, но это слишком сильное решение и с локальными не помогает. Ну тут, наверное, ничего не поделать и просто надо учитывать подобную особенность и не использовать множества для передачи информации между потоками при помощи последовательных интерфейсов (то есть их программных аналогов).
Можно сделать общий вывод: использование bitset в его нынешнем виде для архитектур с ограниченными ресурсами не может быть рекомендовано ввиду избыточных затрат как по памяти, так и по времени исполнения. Возможная модификация, в которой учтены все данные по тексту замечания, лежит на Github, все желающие могут ей пользоваться. История создания данного мода скоро будет размещена на Хабре, там были забавные моменты.
В заключение небольшое замечание — реализация хранилища данных «в лоб», даже на оптимизированном варианте множества потребует Н/8 байтов памяти данных (для 128 переключателей потребуется 16 байт) и, хотя операции потребуют О(1) времени, но множитель составит многие единицы (и даже до 10 и более) тактов МК. Поэтому, учитывая требования задачи и вводя определенные ограничения, можно предложить альтернативную реализацию хранения данных.
Если мы считаем, что в каждый момент времени может быть замкнут не более, чем один переключатель (все остальные мы игнорируем, пока не разомкнется нажатый в данный момент), то мы вполне можем обойтись одним байтом (при условии, что переключателей не более 256) и запись/чтения займет О(1) тактов процессора, причем множитель будет совсем скромный.
Данный подход легко расширить и хранить информацию об одновременно замкнутых n переключателях, но не следует делать n слишком большим, поскольку требуемый объем памяти возрастает, да и время выполнения операций обращения растет линейно при росте количества элементов в множестве, хотя и остается О(1) по отношению к количеству переключателей. Указанный рост времени может быть существенно уменьшен при помощи треугольной реализации бинарного дерева до О(loq2(n)), но для небольших n это не столь важно. Да и сомнительно, чтобы усложнение вычисления очередного индекса при поиске скомпенсировало бы уменьшение количества простых итераций. К недостаткам данной реализации следует отнести возможный отказ в записи элемента множества, что должно быть обработано в вызывающей программе (вариант с меняющимся размером буфера мы отвергаем сразу и с негодованием — это не для встроенных решений).
Реализация данного подхода будет приведена там же.
Автор: GarryC
