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

Ответ 1

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

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

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

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

Однако фокус в том, что с так называемыми неизменяемыми типами значений, такими как целые числа, вам обычно не нужны все метаданные в заголовке объекта: вы можете просто оставить все это и просто синтезировать его (что является виртуальной машиной) -нерд-говорить за "подделку" ), когда кому-то нужно смотреть. Целое число всегда будет иметь класс 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.

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

Ответ 2

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

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

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

Ответ 3

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

Ответ 4

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

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

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

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

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

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

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

Ответ 5

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

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

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

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