January 2nd, 2016

Слишком умная оптимизация? Не, это я сам себя перехитрил.

Си не умеет хранить тип значения. Для него это просто байты в памяти, которые можно так, а можно эдак. Об этом уже миллион раз говорено, но я снова и снова буду это вспоминать.

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

Сейчас я пишу всё заново, не торопясь, обсмакивая разные мелкие идеи. Например, однажды я подумал, что надо бы отказаться от динамического выделения памяти везде, где только это можно сделать - и вот кое-как написанная "библиотека" (несколько функций всего, несерьёзно) выдаёт и удаляет ячейки памяти. Потом пришла идея, банальная и неоригинальная, как надо вообще организовать хранение данных. Об этом я тоже уже писал, но повторю тут.
Каждая элементарная ячейка, миимальная единица памяти, представляет собой пару указателей. От этой корневой идеи всё и выводится: "атомы", заменяющие "просто данные" на типизированные значения, это пары из ТИПА и ДАННЫХ. "Тип" - это не просто тип, это фактически класс (хотя и реализован сугубо на Си), в котором прописаны определённые методы работы с данными: создание экземпляра, удаление, вывод на печать и сравнение (для тех типов, для которых эта операция имеет смысл). Туда же прописана строчка с названием, для отладки, и целочисленная константа, для удобства идентификации. И в итоге получается так, что с каждой порцией данных связан указатель на пачку методов. Это может показаться избыточным: мол, зачем нам хранить аж 32 (а то и 64!) бита указателя, если можно хранить просто небольшой индекс в массиве, внутри которого лежат вышеобозначенные структуры с методами? А щас объясню*.

Кроме "атомов", ещё есть "списки" - упорядоченные цепочки из ячеек. Каждая предыдущая ячейка хранит, опять же, два указателя: на какое-то свое значение и на следующую ячейку в цепи, при этом значение само может быть другой цепью. Признак конца списка - указатель на константу nil (это не очевидный ноль, а особая константа). Так вот, чтобы отличать ячейку, входящую в список, от ячейки-атома, нужно хранить какой-то признак различия, некий тэг. Раньше были такие машины, в которых в памяти, кроме собственно данных, хранились дополнительные биты, которые можно было использовать под это дело, но большинство ныне живущих архитектур ЭВМ не поддерживают тэгированную память. Так где же хранить тэг? А очень просто - прямо внутри указателя! Вспоминаем, что каждая ячейка это ВСЕГДА пара значений, без исключений. То есть, тут уже забрезжила идея - адресация по ячейкам неизбежно будет такой, что один (как минимум) младший бит физического адреса получается как бы лишним. Бинго! вот он, наш тэг.

И тут начинаем увлечённо стрелять себе по ногам: в коде появляются жутковатого вида конструкции типа switch (TAG_OF(car(CAR(lst)))), которые анализируют тэг первой половинки ячейки, на которую указывает первая половинка ячейки по имени lst (и это далеко ещё не самый весёлый пример). Везде и всюду нужно будет ставить макрос, максирующий лишний бит указателя (иначе мы попадём не куда надо, а куда-то между). Очень аккуратно, не всегда очевидно, выуживая данные из указателей на указатели на указатели,.. и всё это только для того, чтобы максимально спрятать типы данных в прикладной программе.

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

* так и не объяснил. В общем-то, ячейки не обязаны на самом деле хранить физические адреса. Нужны просто однозначные идентификаторы, которыми можно было бы указывать конкретные ячейки, просто такой способ наиболее очевиден - при некоторой рыхлости представления. Но, разумеется, ячейки можно сделать даже восьмиразрядными, только работать с ними будет уже совсем не удобно.

Адрес функции

А вот и первый реальный сюрприз: выравнивание кода функций в памяти разное для x86 и ARM - у первых младший бит адреса всегда нуль (ибо код, как минимум, 32-битный - DOS и т.п. не рассматриваю), а у вторых, похоже, не обязательно. Ишь ты как.