Pull to refresh

Меченые указатели, или как уместить объект в одном инте

High performance *Objective C *
Если вы когда-нибудь писали приложение на 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 битной системы). Даже массив с указателем на один элемент может уместиться в меченом указателе! В общем, любой достаточно маленький и широкоиспользуемый тип данных явлется отличным кандидатом на использование в рамках меченого указателя.

Что ж, довольно теории, переходим к практике!

За основу мы возьмем MANumber—кастомную реализацию NSNumber, и добавим туда поддержку меченых указателей.

Хочу отметить, что меченые указатели — это очень, очень закрытое API, поэтому нельзя даже и думать о том, чтобы использовать их в реальном проекте. Под определение класса объекта выделено всего три бита — итого одновременно могут быть задействованы всего восемь классов. Если вы случайно пересечетесь с классом, использованным Apple — все, беда. А, в силу того, что данная информация может поменяться абсолютно любым образом, в любой момент, вероятность того, что беда однажды случится равна ста процентам.

Однако, ничто не мешает нам с ними поиграться, пусть у нас никогда и не будет возможности их безопасно использовать.

Что ж, начнем. Функция private _objc_insert_tagged_isa позволяет закрепить некоторый класс за конкретным тэгом. Вот ее протоип:
  void _objc_insert_tagged_isa(unsigned char slotNumber, Class isa);

Вы передаете в нее номер слота(тэг) и необходимый класс, а она саязывает их в определенной таблице для дальнейшего использования во время исполнения.

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

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

Для хранения значения переменной я использовал объединение:
   union Value
    {
        long long i;
        unsigned long long u;
        double d;
    };

Далее следуют некоторые константы, опредеяющие информацию в меченом указателе. Сначала — номер слота, я принял его равным единице:
   const int kSlot = 1;

Так же я решил определить количество меченых указателей — это понадобиться для дальнейшего извлечения значений:
    const int kTagBits = 4;

MANumber помимо самого значения, хранит его тип, указывающий, как с ним взаимодействовать, и, так как нам необходимо сжимать все по-максимуму, а возможных типов у нас всего три, я выделил под это два бита:
    const int kTypeBits = 2;

Хоть я и не реализовал поддержку double, я все равно оставил под него место, дабы соблюсти единообразие с обычным MANumber и облегчить себе возможную поддержку double в дальнейшем.

И, наконец, так как тип целых, которые мы храним — long long, было бы неплохо доподлинно знать, сколько бит он занимает:
    const int kLongLongBits = sizeof(long long) * CHAR_BIT;

Здесь я предполагаю, что тип указателя — long long, я не пытался осуществлять поддержку 32-битных систем.

Для большего удобства, я написал несколько вспомогательных функций. Первая создает меченый MANumber, принимая на вход тип данных и значение:
    static id TaggedPointer(unsigned long long value, unsigned type)
    {

Напомню структуру меченого указателя. Младший бит всегда равен единице. За ним следуют три бита, указыающие класс объекта, и только потом сами данные объекта. В нашем случае это два бита, определяющие тип, и после них само значение. Вот строка, что объединяет и записывает всю эту информацию с помощью побитовых операций:
        id ptr = (__bridge id)(void *)((value << (kTagBits + kTypeBits)) | (type << kTagBits) | (kSlot << 1) | 1);

По-поводу странного двойного приведения типов — я использую ARC, а он весьма избирателен в этом вопросе. Поэтому когда вы преобразуете указатели на объекты в указатели на необъекты необходим __bridge, а уж в int он вам указатель тем более не даст преобразовать. Именно поэтому я сначала преобразую в void*, а потом все это в объект.

С этим все, и я теперь я возвращаю только что созданный указатель:
        return ptr;
    }

Также, я создал функцию, проверяющую, помечен указатель, или нет. Всё, что она делает—проверяет младший бит, но из-за дурацкого двойного приведения типов её пришлось вынести в отдельную функцию.
    static BOOL IsTaggedPointer(id pointer)
    {
        uintptr_t value = (uintptr_t)(__bridge void *)pointer;
        return value & 1;
    }

Ну и наконец, функция, которая извлекает из меченого указателя всю информацию. Так как Си не поддерживает возврат сразу нескольких значений, я создал для этого специальную структуру: в ней содержится тип и само значение
    struct TaggedPointerComponents
    {
        unsigned long long value;
        unsigned type;
    };

Эта функция сначала преобразует указатель в int, с помощью того самого приведения типов, только в обратную сторону:
    static struct TaggedPointerComponents ReadTaggedPointer(id pointer)
    {
        uintptr_t value = (uintptr_t)(__bridge void *)pointer;

Потом мы начинаем извлекать нужную информацию. Первые четыре бита можно игнорировать, а значение извлекается простым сдвигом:
        struct TaggedPointerComponents components = {
            value >> (kTagBits + kTypeBits),

Чтобы получить тип, необходимо не только сдвинуть, но и наложить маску
            (value >> kTagBits) & ((1ULL << kTypeBits) - 1)
        };


В итоге, все компоненты получены, и мы просто их возвращаем в виде структуры.
        return components;
    }

В какой-то момент мы должны сообщить runtime о том, что мы—класс, работающий на меченых указателях, вызвав функцию _objc_insert_tagged_isa. Лучше всего для этого подходит +initialize. В целях безопасности, Objective-C Runtime не любит, когда перезаписывают какой-то слот, и потому сначала туда нужно записать nil, и только потом наш новый класс:
    + (void)initialize
    {
        if(self == [MANumber class])
        {
            _objc_insert_tagged_isa(kSlot, nil);
            _objc_insert_tagged_isa(kSlot, self);
        }
    }

Теперь мы можем перейти к самому процессу создания меченых указателей. Я написал два метода: +numberWithLongLong: и +numberWithUnsignedLongLong:. Эти методы пытаются создать объекты на меченых указателях, а если значение слишком велико, просто создают обычные объекты.

Эти методы могут создать меченый указатель только для определенного множества значений — они должны умещаться в kLongLongBits — kTagBits — kTypeBits, или 58 бит в 64-битной системе. Один бит нужен для обозначения знака, итого, максимально значение long long равно 2 в 57, минимальное в -57.
    + (id)numberWithLongLong: (long long)value {
        long long taggedMax = (1ULL << (kLongLongBits - kTagBits - kTypeBits - 1)) - 1;
        long long taggedMin = -taggedMax - 1;

Осталось самое простое. Если значение лежит за пределами допустимого, мы исполняем обычный танец с alloc/init. В противном случае, мы создаем меченый указатель с данным значением и классом INT:
        if(value > taggedMax || value < taggedMin)
            return [[self alloc] initWithLongLong: value];
        else
            return TaggedPointer(value, INT);
    }

Для unsigned long long все то же самое, за исключением увеличения множества значений из-за ненужного знакового бита:
    + (id)numberWithUnsignedLongLong:(unsigned long long)value {
        unsigned long long taggedMax = (1ULL << (kLongLongBits - kTagBits - kTypeBits)) - 1;

        if(value > taggedMax)
            return [[self alloc] initWithUnsignedLongLong: value];
        else
            return (id)TaggedPointer(value, UINT);
    }

Теперь нам нужен аксессор типа для наших указателей, чтобы мы могли просто вызывать [self type], не заботясь о битах, маске и прочем. Все, что он будет делать, это проверять указатель функцией IsTaggedPointer, и если он меченый, вызывать ReadTaggedPointer. Если же указатель обычный, просто возвращаем _type:
   - (int)type
    {
        if(IsTaggedPointer(self))
            return ReadTaggedPointer(self).type;
        else
            return _type;
    }

Аксессор значения будет несколько сложнее из-за трудностей со знаком. Сперва-наперво проверим, не обычный ли это указатель:
    - (union Value)value
    {
        if(!IsTaggedPointer(self))
        {
            return _value;
        }

Для меченых нам сначала приедтся считать значение с помощью ReadTaggedPointer. На выходе мы имеем unsigned long long, поэтому нам придется немного поработать, в случае если значение реально имеет знак.
        else
        {
            unsigned long long value = ReadTaggedPointer(self).value;

Создаем локальную переменную типа union Value для возвращаемого значения:
            union Value v;

Если это unsigned, то все просто — помещаем в v значение, и все:
            int type = [self type];
            if(type == UINT)
            {
                v.u = value;
            }

С signed же все не так просто. Для начала проверим знаковый бит — он спрятан в бите под номером 57:
            else if(type == INT)
            {
                unsigned long long signBit = (1ULL << (kLongLongBits - kTagBits - kTypeBits - 1));

Если бит равен единице, то все следущие за 57 битом биты нужно заполнить единицами, нужно это для того, чтобы данный long long был валидным 64-битным отрицательным числом. Эта процедура называется sign extension, вкратце ее суть такова: отрицательные числа начинаются с единиц, и первый ноль — это первый значимый бит. Поэтому чтобы расширить отрицательное число, вы просто добавляете единицы слева:
                if(value & signBit)
                {
                    unsigned long long mask = (((1ULL << kTagBits + kTypeBits) - 1) << (kLongLongBits - kTagBits - kTypeBits));
                    value |= mask;
                }

С положительными числами ничего делать не нужно — они и так заполнены нулями слева. Поэтому просто заполняем v:
                v.i = value;
            }

Если же мы получили какой-то другой тип, то дела плохи, придется выкидывать:
            else
                abort();

В итоге, возвращем v:
            return v;
        }
    }

Написав весь этот код мы получаем возможность работать с новым MANumber, как с обычным, с той лишь только разницей, что нам придется обращаться к значениям не напрямую, а через методы-аксессоры. Мы даже можем сравнивать меченые и обычные MANumber с помощью compare: и isEqual:.

Выводы


Меченые указатели — это отличное дополнение в Cocoa и Objective-C runtime, позволяющее значительно увеличить скорость работы и уменьшить затраты на память при работе с NSNumber.

Мы можем написать свои собственные классы, работающие с мечеными указателями, чтобы пролить свет на внутреннее устройство NSNumber, однако, из-за сильно ограниченого числа свободных слотов, нет никакой возможности использовать их в реальном коде. Это чисто преригатива Cocoa, значительно ускоряющая ее работу.
Что ж, она выполняется идеально, и нам остается только порадоваться, что внутри простенького NSNumber скрывается такой замечательный механизм.

(Вольный перевод свеженького Friday Q&A от Mike Ash)
UPDATE:
Как и обещал, практическое применение меченых указателей не заставило себя долго ждать.
Tags:
Hubs:
Total votes 30: ↑25 and ↓5 +20
Views 8.3K
Comments Comments 20