Почему int в OCaml только 31 бит?

Question

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

Answer 1

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

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

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

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

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

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

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

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

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

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

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

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

Answer 2

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

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

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

Answer 3

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

Answer 4

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

Хотя название статьи кажется о float, это фактически говорит о extra 1 bit

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

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

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

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

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

Answer 5

Почему для int в OCaml только 31 бит?

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

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

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