Comments 20
Первый раз вижу статью, переведенную наполовину. Самое интересное — как самому сделать tagged pointer — оставили сугубо для англочитающей публики.
А что делать, если на такой объект, который на самом деле меченый указатель, но для программиста он всё же объект, создать вторую ссылку? В этот момент рантайм выделит память в куче и переделает меченый указатель в настоящий объект?
Что-то типа
Мне кажется, не должен он ничего переделывать, зачем?
id newObject = taggedPointer;
Мне кажется, не должен он ничего переделывать, зачем?
Такие указатели полностью исключают необходимость менеджмента памяти. Что происходит, когда вы посылаете retain обычному объекту?
Вы получаете тот же указатель, а объект, на который этот указатель ссылается, имеет на один реф каунт больше.
Если же у вас весь объект помещается в указатель, как в данном случае, никаких рефкаунтов ему и не нужно. Пока жив указатель, жив и объект.
NSNumber *otherNum = [originalNum retained];Вы получаете тот же указатель, а объект, на который этот указатель ссылается, имеет на один реф каунт больше.
Если же у вас весь объект помещается в указатель, как в данном случае, никаких рефкаунтов ему и не нужно. Пока жив указатель, жив и объект.
Наличие же битов, указывающих тип данных в указателе, дает возможность хранить там не только int, но и числа с плавющей запятой, да даже несколько ASCII символов (8 для 64 битной системы). Даже массив с указателем на один элемент может уместиться в меченом указателе!
Я не совсем понял, как упихать double в 60 бит (флоат в 28 бит). Разве что использовать знание о том, как кодируется число с плавающей точкой на уровне бит, использовать нестандартное кодирование на ограниченном диапазоне.
Они в самом деле «ужимают» числа с плавающей точкой, или просто сообщают что это возможно теоретически?
Просто сообщают, на практикте так никто не делает.
Опять-таки, не каждый double туда влезет, как и не каждый int.
Опять-таки, не каждый double туда влезет, как и не каждый int.
Int намного проще кодируется, чем double. Так, если мы ограничиваем представимые числа по модулю, то несколько старших битов всегда можно отбросить без потери информации.
А число с плавающей точкой устроено так:
А число с плавающей точкой устроено так:
Вообще-то в статье ни слова о double, говорится только о числах с плавающей запятой, в которых не обязательна такая точность. Как-то я упустил этот момент, когда отвечал на первый комментарий, подумал, что я и правда про double писал.
А вот что пишут в коментах:
А всего-то надо было не выпендриваться, и не использовать double для представления времени. Между прочим при сериализации в plist NSDate сохраняется с точностью только до миллисекунд.
One interesting finding is that although Apple did the «safe» thing with NSNumbers representing doubles, they went with all the trouble for NSDate: NSDate objects are conceptually equivalent to an NSTimeInterval (a double). If the double value «fits» in the 7 first bytes, the NSDate is actually a tagged pointer.
А всего-то надо было не выпендриваться, и не использовать double для представления времени. Между прочим при сериализации в plist NSDate сохраняется с точностью только до миллисекунд.
Используемый в статье термин «выравнивание указателей» допускает разночтения. Гороздо более общепринятая формулировка — выравнивание данных в памяти. О том, зачем она нужна подробно описано здесь. Я попробую резюмировать материал, доступный по ссылке (верным для большинства платформ образом).
Ясно, что элементарной единицей адресации в памяти является байт-октет, и если вам понадобится получить октет, первые 4 бита которого — это последние 4 бита байта с адресом 100, а посление 4 — первые биты байта по адресу 101, то вам придется обратиться по обоим адресам, нужным образом обработать полученные данные и составить результат. Но элементарной единицей операций чтения/записи обыкновенно является не октет, а машинное слово (неоднозначный термин, здесь можно понимать как тип, шириной в разрядность процессора или в ширину шины памяти), что связано с практической равнозначностью по временным задержкам передачи по шине памяти сигнала в четверть ее ширины, в половину — или в полную ширину. Так что если на 32-битной машине вы запросите short (2 октета) по адресу 99, то на деле придется прочесть 2 машинных слова по адресам 96 и 100, выбрать из первого последний октет, из второго — первый и составить результат. Если данные размещать выровненно, будет достаточно одного обращения в память.
Разночтения же я вижу в том, что указатели действительно «выровнены» — так как они также находятся в памяти, как и любой другой объект. Но младшие биты указателя нулевые не потому, что он выровнен, а потому, что он указывает на выровненный в памяти объект.
Ясно, что элементарной единицей адресации в памяти является байт-октет, и если вам понадобится получить октет, первые 4 бита которого — это последние 4 бита байта с адресом 100, а посление 4 — первые биты байта по адресу 101, то вам придется обратиться по обоим адресам, нужным образом обработать полученные данные и составить результат. Но элементарной единицей операций чтения/записи обыкновенно является не октет, а машинное слово (неоднозначный термин, здесь можно понимать как тип, шириной в разрядность процессора или в ширину шины памяти), что связано с практической равнозначностью по временным задержкам передачи по шине памяти сигнала в четверть ее ширины, в половину — или в полную ширину. Так что если на 32-битной машине вы запросите short (2 октета) по адресу 99, то на деле придется прочесть 2 машинных слова по адресам 96 и 100, выбрать из первого последний октет, из второго — первый и составить результат. Если данные размещать выровненно, будет достаточно одного обращения в память.
Разночтения же я вижу в том, что указатели действительно «выровнены» — так как они также находятся в памяти, как и любой другой объект. Но младшие биты указателя нулевые не потому, что он выровнен, а потому, что он указывает на выровненный в памяти объект.
Спасибо, все дело в том, что я, честно говоря, сам никогда не сталкивался ни с выравниванием памяти, ни с выравниванием указателей, но увидев вчера такую реализацию, посчитал ее достойной того, чтобы ей поделиться.
Поэтому, конечно, я мог не учесть некоторых деталей и не пытался исправлять автора, не считая себя достаточно компетентым.
Поэтому, конечно, я мог не учесть некоторых деталей и не пытался исправлять автора, не считая себя достаточно компетентым.
С практической точки зрения полезно также погуглить о семействе pragma-директив препроцессора С/С++ pack(push, <alignsize>), pack(pop).
«Свободные биты» в указателях используются не только для хранения RTTI. В некоторых простых аллокаторах (или менеджерах, если так удобнее) динамической памяти используется следующий подход: в любой момент времени система имеет указатель на начало динамической области памяти процесса. По этому адресу хранится модифицированный указатель на следующую границу между аллокациями, она, в свою очередь, на следующую и т.д. То есть, динамическая память оказывается прошитой в однонаправленный связный список, а информация о том, свободен элемент этого списка как аллокация или занят хранится в младшем бите указателей (в чем и состоит «модификация»). Реальные реализации malloc и new С/С++, аллокаторов Java/Objective-C значительно сложнее.
В некоторых реализациях сборщиков мусора также используется последний бит указателя. Пусть была аллоцирована память. Указатель на нее в младшем бите хранит ноль. Если владение указателем было потеряно (например, переменная вышла из блока (за scope) или в нее выполнено присваивание), а в младшем бите по-прежнему ноль, можно считать, что других ссылок на объект за время его жизни сделано не было и память освобождается сразу, без вызова основного сборщика мусора. Если же напротив, была создана ссылка (например, с помощью присваивания указателя другому или передачи указателя во внешний код или подпроцедуру), то младший бит указателей, как копии, так и источника, устанавливается в единицу и там «залипает». Теперь при уничтожении указателя память не освобождается и это может быть сделано теперь только основным сборщиком по другим алгоритмам. Если есть возможность выделить не только бит, но, скажем, 4 бита, как это обсуждалось в статье, то появляется возможность инкрементально управлять памятью, отведенной под все объекты, число ссылок на которые никогда не пересекало отметки в 15 штук, не отводя под счетчик ссылок в самих объектах памяти.
«Свободные биты» в указателях используются не только для хранения RTTI. В некоторых простых аллокаторах (или менеджерах, если так удобнее) динамической памяти используется следующий подход: в любой момент времени система имеет указатель на начало динамической области памяти процесса. По этому адресу хранится модифицированный указатель на следующую границу между аллокациями, она, в свою очередь, на следующую и т.д. То есть, динамическая память оказывается прошитой в однонаправленный связный список, а информация о том, свободен элемент этого списка как аллокация или занят хранится в младшем бите указателей (в чем и состоит «модификация»). Реальные реализации malloc и new С/С++, аллокаторов Java/Objective-C значительно сложнее.
В некоторых реализациях сборщиков мусора также используется последний бит указателя. Пусть была аллоцирована память. Указатель на нее в младшем бите хранит ноль. Если владение указателем было потеряно (например, переменная вышла из блока (за scope) или в нее выполнено присваивание), а в младшем бите по-прежнему ноль, можно считать, что других ссылок на объект за время его жизни сделано не было и память освобождается сразу, без вызова основного сборщика мусора. Если же напротив, была создана ссылка (например, с помощью присваивания указателя другому или передачи указателя во внешний код или подпроцедуру), то младший бит указателей, как копии, так и источника, устанавливается в единицу и там «залипает». Теперь при уничтожении указателя память не освобождается и это может быть сделано теперь только основным сборщиком по другим алгоритмам. Если есть возможность выделить не только бит, но, скажем, 4 бита, как это обсуждалось в статье, то появляется возможность инкрементально управлять памятью, отведенной под все объекты, число ссылок на которые никогда не пересекало отметки в 15 штук, не отводя под счетчик ссылок в самих объектах памяти.
Ах да, припомнил еще один способ использовать тот факт, что далеко не все значения указателей как целочисленных типов допустимы. Во многих системах также существуют ограничения на диапазоны значений указателей, по которым может обращаться пользовательский процесс. Например, во многих ОС, поддерживающих элементарные средства IPC и защиты процессов, можно гарантировать, что попытка обращения по нулевому адресу приведет к отправке процессу-нарушителю сигнала (например, SIGSEGV), который, впрочем, может быть им перехвачен и обработан. Предположим, что наш процесс работает с некоторой структурой данных, выход за границы которой — есть обращение по невалидному адресу — например, односвязный список, поле next последнего элемента которого есть нуль. Предпожим также, что для нас критична скорость работы этого списка, а попытка обращения за его пределы маловероятна. В таком случае с точки зрения производительности оказывается много выгоднее не проверять на каждом шаге итерации по списку, не ноль ли next, а итерироваться неглядя, а потом просто перехватить SIGSEGV. Более того. В качестве указателя-терминатора можно использовать не только 0, но и дргугие малые значения (1, 2, ..., или, к теме статьи, если на платформе доступ по невыровненному адресу не просто медленее, а недопустим — бросает SIGSEGV, то любое невыровненное значение), что часто позволяет вытащить в обработчике сигнала информацию о том, в в каком конкретно списке произошла попытка обратиться за его конец.
Ясно, что проверку валидности указателя «все равно кто-то выполяет». Ускорение достигается за счет избавления от двойной проверки, причем, от значительно более медленной компоненты: проверка на нуль, выполняемая пользовательским процессом, увеличивает размер цикла итерации (ему для работы нужно больше регистров, больший кеш инструкций, у него меньше шансов влезть в процессорный конвеер, а наличие проверки условия заставляет включаться в работу блок предсказания переходов современных процессоров, что также скорости не добавляет), контроль же со стороны ОС поддерживается процессором аппаратно и накладных расходов практически не добавляет. Во время самих проверок. Если обращение по невалидному адресу все-таки происходит, процессор лишь выполняет прерывание, а информации о случившемся до пользовательского обработчика еще нужно «провалиться» сквозь ОС — в некоторых «толстых» реализациях это происходит настолько долго, что весь профит испаряется.
Кстати «неиспользуемые» биты в указателях находят применение еще и в lock-free структурах данных.
Идея lock-free состоит в том, чтобы вместо использования примитивов синхронизации, например мьютексов, использовать особые атомарные инструкции, реализованные на уровне железа. Например Compare-and-Swap(pointer,A,B): если значение по адресу [pointer] равно A, заменить его на B. Операция атомарна, это значит, что никакой другой процесс не может «вклиниться» между проверкой и обновлением значения в памяти.
Единственная проблема — атомарно можно обработать только кусок данных размером с указатель. Поэтому если требуется атомарно изменять указатель+еще какие-то данные, пора вспомнить о неиспользуемых битах в указателе. Иногда даже вводят искуственно завышенные требования к выравниванию элементов lock-free структур данных, чтобы неиспользуемых битов было больше :)
Идея lock-free состоит в том, чтобы вместо использования примитивов синхронизации, например мьютексов, использовать особые атомарные инструкции, реализованные на уровне железа. Например Compare-and-Swap(pointer,A,B): если значение по адресу [pointer] равно A, заменить его на B. Операция атомарна, это значит, что никакой другой процесс не может «вклиниться» между проверкой и обновлением значения в памяти.
Единственная проблема — атомарно можно обработать только кусок данных размером с указатель. Поэтому если требуется атомарно изменять указатель+еще какие-то данные, пора вспомнить о неиспользуемых битах в указателе. Иногда даже вводят искуственно завышенные требования к выравниванию элементов lock-free структур данных, чтобы неиспользуемых битов было больше :)
Упомяну для галочки, что такая техника используется в интерпретаторе Ruby.
Главное не забывать что всё это машинозависимое нечто (зависит от поведения аллока, от битности, от ОС)
Tagged pointer используется в Linux'овой реализации rb-деревьев для хранения цвета прямо в младшем бите pointer'а на parent'а.
Sign up to leave a comment.
Меченые указатели, или как уместить объект в одном инте