Почему int в OCaml всего 31 бит?

Больше нигде не видел эту "фичу". Я знаю, что 32-й бит используется для сборки мусора. Но почему это так только для int, а не для других базовых типов?

Это называется представлением тегированного указателя и представляет собой довольно распространенный прием оптимизации, который десятилетиями используется во многих различных интерпретаторах, виртуальных машинах и системах времени выполнения. Практически каждая реализация Lisp использует их, многие виртуальные машины Smalltalk, многие интерпретаторы Ruby и так далее.

Обычно в этих языках вы всегда передаете указатели на объекты. Сам объект состоит из заголовка объекта, который содержит метаданные объекта (например, тип объекта, его класс (-а), возможно, ограничения управления доступом или аннотации безопасности и т. Д.), А затем сами фактические данные объекта. Таким образом, простое целое число будет представлено как указатель плюс объект, состоящий из метаданных и фактического целого числа. Даже при очень компактном представлении это примерно 6 байт для простого целого числа.

Кроме того, вы не можете передать такой целочисленный объект в ЦП для выполнения быстрой целочисленной арифметики. Если вы хотите добавить два целых числа, у вас действительно есть только два указателя, которые указывают на начало заголовков двух целочисленных объектов, которые вы хотите добавить. Итак, вам сначала нужно выполнить целочисленную арифметику над первым указателем, чтобы добавить смещение в объект, в котором хранятся целочисленные данные. Затем вам нужно разыменовать этот адрес. Повторите то же самое со вторым целым числом. Теперь у вас есть два целых числа, которые вы можете попросить добавить к процессору. Конечно, теперь вам нужно создать новый целочисленный объект для хранения результата.

Итак, чтобы выполнить одно целочисленное сложение, вам на самом деле нужно выполнить три целочисленных сложения плюс два разыграждения указателя плюс одно построение объекта. И вы занимает почти 20 байт.

Однако хитрость заключается в том, что с так называемыми неизменяемыми типами значений, такими как целые числа, вам обычно не нужны все метаданные в заголовке объекта: вы можете просто оставить все это и просто синтезировать его (что и есть VM-ботаник- говорите за "фальшивый"), когда кто-то хочет посмотреть. Целое число всегда будет иметь класс Integer, нет необходимости отдельно хранить эту информацию. Если кто - то использует отражение , чтобы выяснить класс целое число, вы просто ответить , Integerи никто никогда не узнает , что вы на самом деле не хранить эту информацию в заголовке объекта , и что на самом деле, там не даже заголовок объекта (или объект).

Таким образом, хитрость заключается в том, чтобы сохранить значение из объекта в пределах указателя на объект, эффективно разрушаясь два в одном.

Существуют процессоры, которые на самом деле имеют дополнительное пространство внутри указателя (так называемые биты тегов ), которые позволяют хранить дополнительную информацию об указателе внутри самого указателя. Дополнительная информация вроде «на самом деле это не указатель, это целое число». Примеры включают Burroughs B5000, различные Lisp-машины или AS / 400. К сожалению, большинство современных процессоров массового производства не имеют этой функции.

Однако выход есть: большинство современных центральных процессоров работают значительно медленнее, если адреса не выровнены по границам слов. Некоторые даже не поддерживают невыровненный доступ.

Это означает, что на практике все указатели будут делиться на 4, что означает, что они всегда будут заканчиваться двумя 0битами. Это позволяет нам различать настоящие указатели (которые заканчиваются на 00) и указатели, которые на самом деле являются замаскированными целыми числами (те, которые заканчиваются на 1). И это по-прежнему оставляет нам все указатели, которые 10позволяют делать другие вещи. Кроме того, большинство современных операционных систем резервируют очень низкие адреса для себя, что дает нам еще одну область, с которой можно возиться (указатели, которые начинаются, скажем, с 24 0с и заканчиваются 00).

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

Что нам делать с другими адресными пространствами? Ну, типичные примеры включают кодирующую floatс в другом большом адресном пространстве , а также ряд специальных объектов , таких как true, false, nil, 127 ASCII символов, некоторые часто используемые короткие строки, пустой список, пустой объект, пустой массив и так далее рядом с 0адрес.

Например, в интерпретаторах МРТ, YARV и Rubinius Рубинового, целые числа кодируются так , как я , описанным выше, falseкодируются как адрес 0(который просто так случается также будет представление falseв C), в trueкачестве адреса 2(который просто так случается, представление C со trueсдвигом на один бит) и nilas 4.

См. Подробное описание в разделе «Представление целых чисел, битов тегов, значений, выделенных в куче» https://ocaml.org/learn/tutorials/performance_and_profiling.html .

Короткий ответ: это для производительности. При передаче аргумента функции он передается либо как целое число, либо как указатель. На машинном уровне языка невозможно определить, содержит ли регистр целое число или указатель, это всего лишь 32- или 64-битное значение. Таким образом, среда выполнения OCaml проверяет бит тега, чтобы определить, было ли полученное значение целым числом или указателем. Если бит тега установлен, то значение является целым числом и передается в правильную перегрузку. В противном случае это указатель и ищется тип.

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

Это не совсем то, что «используется для сборки мусора». Он используется для внутреннего различения указателя и распакованного целого числа.

Я должен добавить эту ссылку, чтобы помочь OP лучше понять 63-битный тип с плавающей запятой для 64-битного OCaml

Хотя название статьи кажется оскорбительным float, на самом деле речь идет оextra 1 bit

Среда выполнения OCaml допускает полиморфизм через единообразное представление типов. Каждое значение OCaml представлено в виде одного слова, так что можно иметь единую реализацию, скажем, для «списка вещей» с функциями для доступа (например, List.length) и построения (например, List.map) этих списков. которые работают одинаково, будь то списки целых чисел, числа с плавающей запятой или списки наборов целых чисел.

Все, что не умещается в слове, размещается в блоке в куче. Слово, представляющее эти данные, тогда является указателем на блок. Поскольку куча содержит только блоки слов, все эти указатели выровнены: их несколько наименее значимых битов всегда не установлены.

Конструкторы без аргументов (например: type fruit = Apple | Orange | Banana) и целые числа не представляют столько информации, чтобы их нужно было разместить в куче. Их представление распаковано. Данные находятся непосредственно внутри слова, которое в противном случае было бы указателем. Таким образом, в то время как список списков на самом деле является списком указателей, список целых чисел содержит целые числа с одной косвенной ссылкой. Функции доступа и построения списков не замечают этого, потому что целые числа и указатели имеют одинаковый размер.

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

Вот почему неупакованные целые числа предоставляют программисту OCaml 31 бит (для 32-битного OCaml) или 63 бита (для 64-битного OCaml). В представлении за кулисами всегда устанавливается младший значащий бит слова, содержащего целое число, чтобы отличить его от указателя. 31- или 63-битные целые числа довольно необычны, поэтому любой, кто вообще использует OCaml, знает это. Пользователи OCaml обычно не знают, почему для 64-битного OCaml нет 63-битного распакованного типа с плавающей запятой.

Почему int в OCaml всего 31 бит?

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

Но почему это так только для int, а не для других базовых типов?

Не только int. Другие типы, такие как charи перечисления, используют то же представление с тегами.