Если вы когда-нибудь писали приложение на Objective-C, вы должны быть знакомы с классом NSNumber — оберткой, превращающей число в объект. Классический пример использования — это создание числового массива, заполненного объектами вида [NSNumber numberWithInt:someIntValue];.
Казалось бы, зачем создавать целый объект, выделять под него память, потом ее чистить, если нам нужен обычный маленький int? В Apple тоже так подумали, и потому NSNumber — это зачастую совсем не объект, и за указателем на него скрывается… пустота.
Если вам интересно, как же так получается, и при чем тут меченые указатели — добро пожаловать под кат!
Немного теории выравнивания указателей
Всем известно, что указатель—это обычный int, который система принимет за адрес в памяти. Переменная, содержащая в себе указатель на объект представляет из себя int со значением вида 0x7f84a41000c0. Вся природа «указательности» заключается в том, как программа её использует. В Си мы можем получить интовое значение указателя простым кастингом:
void *somePointer = ...;
uintptr_t pointerIntegerValue = (uintptr_t)somePointer;
(uintptr_t представлеят из себя стандартный сишный typdef для целых чисел, достаточно большой, чтобы вместить указатель. Это необходимо, так как размеры указателей варьируются, в зависимости от платформы)
Практически в каждой компьютерной архитектуре есть такое понятие, как выравнивание указателей. Под ним имеется в виду то, что указатель на какой-либо тип данных должен бцть кратным степени двойки. Например, указатель на 4-х байтовый int должен быть кратен четырём. Нарушение ограничений, накладываемых выравниваем указателей может привести к значительному снижению производительности или даже полному падению приложения. Также, верное выранивание необходимо для атомарного чтения и записи в память. Короче говоря, выравнивание указателей—штука серьёзная, и вам не стоит пытаться её нарушать.
Если вы создате переменную, компилятор может проверить выравнивание:
void f(void) {
int x;
}
Однако, всё становится не так просто в случае динамически выделяемой памяти:
int *ptr = malloc(sizeof(*ptr));
У malloc нет никакого представления о том, какого типа будут данные, он просто выделяет четыре байта, не зная о том, int это, или два shortа, четыре charа, или вообще что-то ещё.
И потому, чтобы соблюсти правильное выравнивание, он использует совсем уж параноидальный подход и возвращает указатель выравненный так далеко, чтобы эта граница подошла для абсолютно любого типа данных. В Mac OS X, malloc всегда возвращает указатели, выравненные по границе 16-и байтов.
Из-за выравнивания, в указателе остаются неиспользованные биты. Вот как выглядит hex указателя, выравненного по 16-и байтам:
0x-------0
Последняя цифра hex всегда нуль. Вообще, может быть и вполне себе валидный указатель, который не соблюдает эти условия (например, char *), но указатель на объект всегда должен заканчиваться на нулевые биты.
Немного теории меченых указателей
Зная о пустых битах в конце указателя, можно пойти и дальше и попытаться найти им применение. Почему бы не использовать их как индикатор того, что это не настоящий указатель на объект? Тогда мы могли бы хранить данные прямо здесь, в самом указателе, без необходимости выделять дорогую память? Да-да, это и есть те самые меченые указатели.
Системы, в которых используются меченые указатели, осуществляют дополнительную проверку — они смотрят на младший бит, и если он равен нулю — перед нами настоящий объект. Если же это единица, то перед нами не объект а что-то другое, и информацию из указателя придется извлекать нестандарнтым путем. Обычно тип данных хранится сразу за младшим битом, а далее следуют сами данные.
Вот так выглядел бы валидный объект в двоичном представлении:
....0000
^ нули на конце
А это меченый указатель:
....xxx1
^ здесь указан тип
Все это можно реализовать различными способами, но в Objective-C младший бит меченого указателя всегда равен единице, а последующие три обозначают класс указателя.
Применение меченых указателей
Меченые указатели зачастую используются в языках, где все — объект. Согласитесть, когда 3 — это объкет, а 3+4 включает в себя два объекта, да еще и создание третьего, выделение памяти для объектов и извлечение из них данных начинает играть значительную роль в общей производительности. Вся эта возня с созданием объектов, доступа к медленной памяти, занесения значения в объект, который никто не использует, в разы превышает затраты на само сложение.
Использование меченых указателей избавляет нас от этих невзгод для всех типов, которые поместятся в тех самых пустых битах. Маленькие инты — идеальные кандидаты на эту роль — они занимают совсем немного места и повсеместно используются.
Вот так выглядела бы обычная тройка:
0000 0000 0000 0000 0000 0000 0000 0011
А вот тройка, спрятанная в меченом указателе:
0000 0000 0000 0000 0000 0000 0011 1011
^ ^ ^ меченый бит
| |
| класс меченого указателя (5)
|
двойчная тройка
Здесь я предположил, что для обозначения int используется пятерка, но, на самом деле, это остается на усмотрение системы, и все может в любой момент поменяться.
Наблюдательный читатель, наверное, уже заметил, что у нас остается всего 28 бит на 32-разрядной системе и 60 на 64-разрядной. А целые могут принимать и большие значения. Все верно, не каждый int можно спрятать в меченом указателе, для некоторых придется создавать полноценный объект.
Когда всё умещается в одном указателе, отпадает необходимость выделять отдельную память, очищать её. Также, мы просто экономим небольшое количество памяти, которое пришлось бы выделить под отдельный объект. Это может показаться незначительным при сложении тройки и четвёрки, но при большом количестве операций над числами, этот прирост весьма ощутим.
Наличие же битов, указывающих тип данных в указателе, дает возможность хранить там не только int, но и числа с плавющей запятой, да даже несколько ASCII символов (8 для 64 битной системы). Даже массив с указателем на один элемент может уместиться в меченом указателе! В общем, любой достаточно маленький и широкоиспользуемый тип данных явлется отличным кандидатом на использование в рамках меченого указателя.
Что ж, довольно теории… переходить ли к парктике?
Если вам интересно, как это можно использовать в реальности и как Apple реализовала NSNumber, я могу продожить повествование, в котором мы соорудим свой NSNumber на меченых указателях и вы все увидите изнутри.
Продолжим?
(Вольный перевод свеженького Friday Q&A от Mike Ash)
Автор: pestrov
