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

в 19:35, , рубрики: Cocoa, iOS, objective-c, высокая производительность, ненормальное программирование, перевод, переводы, указатели, метки: , , , , ,

В первой части мы познакомились с мечеными указателями и тем, как нам создать целый объект, не выделяя под него отдельной памяти.

NSNumber оказался идеальным кандидатом на то, чтобы применить полученые знания на практике—давайте же попробуем написать нашу собственную реализацию этого класса. За основу мы возьмем 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)

Автор: pestrov


* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js