4 августа 2012 в 00:59

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

Если вы когда-нибудь писали приложение на 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:
Как и обещал, практическое применение меченых указателей не заставило себя долго ждать.
Никита Пестров @pestrov
карма
17,0
рейтинг 0,0
Data Scientist
Самое читаемое Разработка

Комментарии (20)

  • +4
    Первый раз вижу статью, переведенную наполовину. Самое интересное — как самому сделать tagged pointer — оставили сугубо для англочитающей публики.
    • +2
      Что ж, тогда завтра будет продолжение)
      Просто могло оказаться так, что рассказ о том, как все это устроено, удовлетворил бы всеобщий интерес, и конекретная реализация не понадобилась бы.
  • 0
    А что делать, если на такой объект, который на самом деле меченый указатель, но для программиста он всё же объект, создать вторую ссылку? В этот момент рантайм выделит память в куче и переделает меченый указатель в настоящий объект?
    • 0
      Что-то типа
      id newObject = taggedPointer;
      
      ?
      Мне кажется, не должен он ничего переделывать, зачем?
    • 0
      Такие указатели полностью исключают необходимость менеджмента памяти. Что происходит, когда вы посылаете retain обычному объекту?

      NSNumber *otherNum = [originalNum retained];


      Вы получаете тот же указатель, а объект, на который этот указатель ссылается, имеет на один реф каунт больше.

      Если же у вас весь объект помещается в указатель, как в данном случае, никаких рефкаунтов ему и не нужно. Пока жив указатель, жив и объект.
  • 0
    Наличие же битов, указывающих тип данных в указателе, дает возможность хранить там не только int, но и числа с плавющей запятой, да даже несколько ASCII символов (8 для 64 битной системы). Даже массив с указателем на один элемент может уместиться в меченом указателе!

    Я не совсем понял, как упихать double в 60 бит (флоат в 28 бит). Разве что использовать знание о том, как кодируется число с плавающей точкой на уровне бит, использовать нестандартное кодирование на ограниченном диапазоне.

    Они в самом деле «ужимают» числа с плавающей точкой, или просто сообщают что это возможно теоретически?
    • 0
      Просто сообщают, на практикте так никто не делает.
      Опять-таки, не каждый double туда влезет, как и не каждый int.
      • 0
        Int намного проще кодируется, чем double. Так, если мы ограничиваем представимые числа по модулю, то несколько старших битов всегда можно отбросить без потери информации.

        А число с плавающей точкой устроено так:
        image
        • 0
          Вообще-то в статье ни слова о double, говорится только о числах с плавающей запятой, в которых не обязательна такая точность. Как-то я упустил этот момент, когда отвечал на первый комментарий, подумал, что я и правда про double писал.
          • 0
            А вот что пишут в коментах:
            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 сохраняется с точностью только до миллисекунд.
  • +3
    Используемый в статье термин «выравнивание указателей» допускает разночтения. Гороздо более общепринятая формулировка — выравнивание данных в памяти. О том, зачем она нужна подробно описано здесь. Я попробую резюмировать материал, доступный по ссылке (верным для большинства платформ образом).

    Ясно, что элементарной единицей адресации в памяти является байт-октет, и если вам понадобится получить октет, первые 4 бита которого — это последние 4 бита байта с адресом 100, а посление 4 — первые биты байта по адресу 101, то вам придется обратиться по обоим адресам, нужным образом обработать полученные данные и составить результат. Но элементарной единицей операций чтения/записи обыкновенно является не октет, а машинное слово (неоднозначный термин, здесь можно понимать как тип, шириной в разрядность процессора или в ширину шины памяти), что связано с практической равнозначностью по временным задержкам передачи по шине памяти сигнала в четверть ее ширины, в половину — или в полную ширину. Так что если на 32-битной машине вы запросите short (2 октета) по адресу 99, то на деле придется прочесть 2 машинных слова по адресам 96 и 100, выбрать из первого последний октет, из второго — первый и составить результат. Если данные размещать выровненно, будет достаточно одного обращения в память.

    Разночтения же я вижу в том, что указатели действительно «выровнены» — так как они также находятся в памяти, как и любой другой объект. Но младшие биты указателя нулевые не потому, что он выровнен, а потому, что он указывает на выровненный в памяти объект.
    • 0
      Спасибо, все дело в том, что я, честно говоря, сам никогда не сталкивался ни с выравниванием памяти, ни с выравниванием указателей, но увидев вчера такую реализацию, посчитал ее достойной того, чтобы ей поделиться.
      Поэтому, конечно, я мог не учесть некоторых деталей и не пытался исправлять автора, не считая себя достаточно компетентым.
      • +2
        С практической точки зрения полезно также погуглить о семействе pragma-директив препроцессора С/С++ pack(push, <alignsize>), pack(pop).

        «Свободные биты» в указателях используются не только для хранения RTTI. В некоторых простых аллокаторах (или менеджерах, если так удобнее) динамической памяти используется следующий подход: в любой момент времени система имеет указатель на начало динамической области памяти процесса. По этому адресу хранится модифицированный указатель на следующую границу между аллокациями, она, в свою очередь, на следующую и т.д. То есть, динамическая память оказывается прошитой в однонаправленный связный список, а информация о том, свободен элемент этого списка как аллокация или занят хранится в младшем бите указателей (в чем и состоит «модификация»). Реальные реализации malloc и new С/С++, аллокаторов Java/Objective-C значительно сложнее.

        В некоторых реализациях сборщиков мусора также используется последний бит указателя. Пусть была аллоцирована память. Указатель на нее в младшем бите хранит ноль. Если владение указателем было потеряно (например, переменная вышла из блока (за scope) или в нее выполнено присваивание), а в младшем бите по-прежнему ноль, можно считать, что других ссылок на объект за время его жизни сделано не было и память освобождается сразу, без вызова основного сборщика мусора. Если же напротив, была создана ссылка (например, с помощью присваивания указателя другому или передачи указателя во внешний код или подпроцедуру), то младший бит указателей, как копии, так и источника, устанавливается в единицу и там «залипает». Теперь при уничтожении указателя память не освобождается и это может быть сделано теперь только основным сборщиком по другим алгоритмам. Если есть возможность выделить не только бит, но, скажем, 4 бита, как это обсуждалось в статье, то появляется возможность инкрементально управлять памятью, отведенной под все объекты, число ссылок на которые никогда не пересекало отметки в 15 штук, не отводя под счетчик ссылок в самих объектах памяти.
    • 0
      Ах да, припомнил еще один способ использовать тот факт, что далеко не все значения указателей как целочисленных типов допустимы. Во многих системах также существуют ограничения на диапазоны значений указателей, по которым может обращаться пользовательский процесс. Например, во многих ОС, поддерживающих элементарные средства IPC и защиты процессов, можно гарантировать, что попытка обращения по нулевому адресу приведет к отправке процессу-нарушителю сигнала (например, SIGSEGV), который, впрочем, может быть им перехвачен и обработан. Предположим, что наш процесс работает с некоторой структурой данных, выход за границы которой — есть обращение по невалидному адресу — например, односвязный список, поле next последнего элемента которого есть нуль. Предпожим также, что для нас критична скорость работы этого списка, а попытка обращения за его пределы маловероятна. В таком случае с точки зрения производительности оказывается много выгоднее не проверять на каждом шаге итерации по списку, не ноль ли next, а итерироваться неглядя, а потом просто перехватить SIGSEGV. Более того. В качестве указателя-терминатора можно использовать не только 0, но и дргугие малые значения (1, 2, ..., или, к теме статьи, если на платформе доступ по невыровненному адресу не просто медленее, а недопустим — бросает SIGSEGV, то любое невыровненное значение), что часто позволяет вытащить в обработчике сигнала информацию о том, в в каком конкретно списке произошла попытка обратиться за его конец.
      • 0
        Ясно, что проверку валидности указателя «все равно кто-то выполяет». Ускорение достигается за счет избавления от двойной проверки, причем, от значительно более медленной компоненты: проверка на нуль, выполняемая пользовательским процессом, увеличивает размер цикла итерации (ему для работы нужно больше регистров, больший кеш инструкций, у него меньше шансов влезть в процессорный конвеер, а наличие проверки условия заставляет включаться в работу блок предсказания переходов современных процессоров, что также скорости не добавляет), контроль же со стороны ОС поддерживается процессором аппаратно и накладных расходов практически не добавляет. Во время самих проверок. Если обращение по невалидному адресу все-таки происходит, процессор лишь выполняет прерывание, а информации о случившемся до пользовательского обработчика еще нужно «провалиться» сквозь ОС — в некоторых «толстых» реализациях это происходит настолько долго, что весь профит испаряется.
  • +1
    Кстати «неиспользуемые» биты в указателях находят применение еще и в lock-free структурах данных.

    Идея lock-free состоит в том, чтобы вместо использования примитивов синхронизации, например мьютексов, использовать особые атомарные инструкции, реализованные на уровне железа. Например Compare-and-Swap(pointer,A,B): если значение по адресу [pointer] равно A, заменить его на B. Операция атомарна, это значит, что никакой другой процесс не может «вклиниться» между проверкой и обновлением значения в памяти.

    Единственная проблема — атомарно можно обработать только кусок данных размером с указатель. Поэтому если требуется атомарно изменять указатель+еще какие-то данные, пора вспомнить о неиспользуемых битах в указателе. Иногда даже вводят искуственно завышенные требования к выравниванию элементов lock-free структур данных, чтобы неиспользуемых битов было больше :)
  • +1
    Упомяну для галочки, что такая техника используется в интерпретаторе Ruby.
  • 0
    Главное не забывать что всё это машинозависимое нечто (зависит от поведения аллока, от битности, от ОС)
    • 0
      Ожидается, что OS — Mac OS X, как 32 так и 64 разрядная, а alloc тут не причем, разве нет?
  • 0
    Tagged pointer используется в Linux'овой реализации rb-деревьев для хранения цвета прямо в младшем бите pointer'а на parent'а.

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