Labeled pointers, or how to fit an object in one inte
If you have ever written an application in Objective-C, you should be familiar with the NSNumber class, a wrapper that turns a number into an object. A classic use case is the creation of a numeric array filled with objects of the form [NSNumber numberWithInt: someIntValue]; .
It would seem, why create an entire object, allocate memory for it, then clean it up if we need an ordinary small int? Apple also thought so, and therefore NSNumber is often not an object at all, and behind the pointer to it lies ... emptiness.
If you're wondering how this is how it turns out, and what's the point about tagged pointers - welcome to the cat!
')
Everyone knows that a pointer is a normal int, which the system takes as an address in memory. The variable containing the pointer to the object is an int with a value of the form 0x7f84a41000c0. The whole nature of "pointing" is how the program uses it. In C, we can get the index value by simply casting:
( uintptr_t is a standard typdef for integers that is large enough to hold a pointer. This is necessary because the pointer sizes vary depending on the platform)
Virtually every computer architecture has such a thing as pointer alignment . It means that a pointer to a data type must be a multiple of a power of two. For example, a pointer to a 4-byte int must be a multiple of four. Violation of restrictions imposed by alignment of pointers can lead to a significant decrease in performance or even a complete crash of the application. Also, correct alignment is necessary for atomic reading and writing to memory. In short, alignment of pointers is a serious thing, and you should not try to break it.
If you create a variable, the compiler can check the alignment:
However, things are not so simple in the case of dynamically allocated memory:
Malloc has no idea what kind of data it will be, it simply allocates four bytes, not knowing if it is an int , or two short , four char , or something else.
And therefore, in order to observe the correct alignment, it uses a very paranoid approach and returns a pointer aligned so far that this boundary is suitable for absolutely any type of data. On Mac OS X, malloc always returns pointers aligned on the 16-byte boundary.
Due to alignment, unused bits remain in the pointer. Here is what the hex pointer looks like, evened out by 16 bytes:
The last digit hex is always zero. In general, it may be quite a valid pointer that does not comply with these conditions (for example, char *), but the pointer to the object must always end in zero bits.
Knowing the empty bits at the end of the pointer, you can go further and try to use them. Why not use them as an indicator that this is not a real pointer to an object? Then we could store the data right here, in the pointer itself, without having to allocate expensive memory? Yes, yes, these are the very labeled pointers.
Systems that use labeled pointers perform an additional check — they look at the low-order bit, and if it is zero, then we have a real object. If this is a unit, then we are not an object but something else, and the information from the pointer will have to be extracted in a non-standard way. Typically, the data type is stored immediately after the low-order bit, and then the data itself follows.
This is how a valid binary object would look like:
And this is a labeled pointer:
All this can be implemented in various ways, but in Objective-C the low bit of the labeled pointer is always one, and the next three indicate the class of the pointer.
Labeled pointers are often used in languages where everything is an object. When 3 is agreed, 3 + 4 includes two objects, and even the creation of a third one, the allocation of memory for objects and the extraction of data from them begins to play a significant role in overall performance. All this fuss with the creation of objects, access to slow memory, entering values into an object that no one uses, many times exceeds the cost of the addition.
Using tagged pointers saves us from these adversities for all types that fit in those empty bits. Small ints are ideal candidates for this role - they take up very little space and are widely used.
This is what a regular triple would look like:
But the troika, hidden in a labeled pointer:
Here I assumed that the five is used to designate int, but in fact it remains at the discretion of the system, and everything can change at any time.
The observant reader probably already noticed that we only have 28 bits left on the 32-bit system and 60 on the 64-bit one. And the integers can take on large values. That's right, not every int can be hidden in a labeled pointer, for some you will have to create a full-fledged object.
When everything fits in one pointer, there is no need to allocate a separate memory, to clear it. Also, we simply save a small amount of memory, which we would have to allocate for a separate object. This may seem insignificant with the addition of three and four, but with a large number of operations on numbers, this increase is very noticeable.
The presence of bits indicating the type of data in the pointer makes it possible to store there not only int, but also floating-point numbers, and even several ASCII characters (8 for a 64-bit system). Even an array with a pointer to one element can fit in a labeled pointer! In general, any fairly small and widely used data type is an excellent candidate for use within a labeled pointer.
We will take MANumber as a basis — a custom implementation of NSNumber, and add support for labeled pointers there.
I want to note that labeled pointers are a very, very closed API, so you can't even think about using them in a real project. Under the definition of an object class, only three bits are allocated - in total, only eight classes can be involved simultaneously. If you accidentally intersect with the class used by Apple, that's all. And, due to the fact that this information can change in absolutely any way, at any time, the likelihood that trouble will happen once equals one hundred percent.
However, nothing prevents us from playing with them, even if we never have the opportunity to use them safely.
Well, let's begin. The private _objc_insert_tagged_isa function allows you to assign a certain class to a specific tag. Here is its prototype:
You transfer the slot number (tag) and the required class to it, and it tells them in a certain table for further use during execution.
Virtually any class on labeled pointers needs a close class that will create a normal object in the event that the value does not fit within the pointer. For NSNumber, these will be particularly large ints and doubles, which are very difficult to push into the pointer, and I will not do this here.
For this there are two approaches. The first is to create two completely different classes, with some common ancestor for the code, which will be repeated in both descendants. The second is that within the same class we will use different code, depending on the value that we need to keep. I will use the second approach, so it seemed to me easier for this particular case.
To store the value of a variable, I used a union :
This is followed by some constants that define the information in the labeled index. First - the slot number, I took it equal to one:
I also decided to determine the number of labeled pointers - this is needed to further extract the values:
MANumber, in addition to the value itself, stores its type, indicating how to interact with it, and since we need to compress everything to the maximum, and we have only three possible types, I allocated two bits to this:
Although I did not implement double support, I still left room for it in order to maintain uniformity with the usual MANumber and facilitate my possible double support in the future.
And finally, since the type of integers that we store is long long, it would be nice to know for sure how many bits it takes:
Here, I assume that the pointer type is long long, I did not try to support 32-bit systems.
For more convenience, I have written several helper functions. The first creates a labeled MANumber, taking as input the data type and value:
Let me remind the structure of the labeled pointer. The low bit is always one. It is followed by three bits indicating the class of the object, and only then the object data itself. In our case, these are the two bits that define the type, and after them the value itself. Here is a string that combines and records all this information using bitwise operations:
In connection with the strange double type conversion - I use ARC, and he is very selective in this matter. Therefore, when you convert pointers to objects into pointers to non-objects, a __bridge is needed, and the int pointer will not allow you to convert it to int. That is why I first convert to void *, and then all this into an object.
With this all, and now I return the newly created pointer:
Also, I created a function that checks whether a pointer is marked or not. All she does is check the low-order bit, but because of the stupid double type conversion, she had to be rendered into a separate function.
Finally, a function that extracts all the information from a labeled pointer. Since C does not support returning multiple values at once, I created a special structure for this: it contains the type and the value itself
This function first converts the pointer to an int, using the same type conversion, only in the opposite direction:
Then we start to extract the necessary information. The first four bits can be ignored, and the value is extracted by a simple shift:
To get the type, you must not only move, but also apply a mask
As a result, all components are received, and we simply return them in the form of a structure.
At some point, we have to tell the runtime that we are a class that runs on labeled pointers by calling the _objc_insert_tagged_isa function. Best suited for this + initialize. For security reasons, Objective-C Runtime does not like to overwrite a slot, and therefore you first need to write nil, and only then our new class:
Now we can proceed to the process of creating labeled pointers. I wrote two methods: + numberWithLongLong: and + numberWithUnsignedLongLong:. These methods attempt to create objects on labeled pointers, and if the value is too large, they simply create ordinary objects.
These methods can create a labeled pointer only for a specific set of values - they must fit in kLongLongBits - kTagBits - kTypeBits, or 58 bits in a 64-bit system. One bit is needed to designate a sign, for a total, the maximum value of long long is 2 in 57, the minimum in -57.
It remains the most simple. If the value is outside the limits, we perform the usual dance with alloc / init. Otherwise, we create a labeled pointer with the given value and the class INT:
For unsigned long long, everything is the same, except for increasing the set of values due to an unnecessary sign bit:
Now we need an accessor type for our pointers so that we can simply call the [self type], without worrying about the bits, the mask, and so on. All he does is check the pointer with the IsTaggedPointer function, and if it is tagged, call ReadTaggedPointer. If the pointer is normal, simply return _type:
The accessor of values will be somewhat more complicated due to difficulties with the sign. First of all, let's check if it’s a regular pointer:
For the tagged ones, we will first have to read the value using ReadTaggedPointer. At the output, we have unsigned long long, so we have to work a little if the value really has a sign.
Create a local variable of the union Value type for the return value:
If it is unsigned, then everything is simple - put the value in v, and that's it:
With signed, everything is not so simple. First, let's check the sign bit - it is hidden in bit 57:
If the bit is equal to one, then all the bits that follow 57 bits need to be filled with ones, this is necessary for the given long long to be a valid 64-bit negative number. This procedure is called sign extension, in short its essence is this: negative numbers begin with ones, and the first zero is the first significant bit. Therefore, to expand a negative number, you simply add units to the left:
With positive numbers, you do not need to do anything - they are already filled with zeros on the left. So just fill in v:
If we got some other type, then things are bad, we will have to throw out:
As a result, we return v:
Having written all this code, we get the opportunity to work with the new MANumber, as with the usual one, with the only difference being that we will have to access the values not directly, but through accessor methods. We can even compare labeled and regular MANumber using compare: and isEqual:.
Labeled pointers are a great addition to the Cocoa and Objective-C runtime, which allows you to significantly increase the speed of work and reduce memory costs when working with NSNumber.
We can write our own classes that work with labeled pointers to shed light on the internal structure of NSNumber, however, due to the very limited number of free slots, there is no way to use them in real code. This is purely Cocoa's pre -rigative, greatly accelerating its work.
Well, it runs perfectly, and we can only be glad that inside this simple NSNumber there is such a wonderful mechanism.
(Free translation of fresh Friday Q & A by Mike Ash)
It would seem, why create an entire object, allocate memory for it, then clean it up if we need an ordinary small int? Apple also thought so, and therefore NSNumber is often not an object at all, and behind the pointer to it lies ... emptiness.
If you're wondering how this is how it turns out, and what's the point about tagged pointers - welcome to the cat!
')
A bit of pointer alignment theory
Everyone knows that a pointer is a normal int, which the system takes as an address in memory. The variable containing the pointer to the object is an int with a value of the form 0x7f84a41000c0. The whole nature of "pointing" is how the program uses it. In C, we can get the index value by simply casting:
void *somePointer = ...; uintptr_t pointerIntegerValue = (uintptr_t)somePointer; ( uintptr_t is a standard typdef for integers that is large enough to hold a pointer. This is necessary because the pointer sizes vary depending on the platform)
Virtually every computer architecture has such a thing as pointer alignment . It means that a pointer to a data type must be a multiple of a power of two. For example, a pointer to a 4-byte int must be a multiple of four. Violation of restrictions imposed by alignment of pointers can lead to a significant decrease in performance or even a complete crash of the application. Also, correct alignment is necessary for atomic reading and writing to memory. In short, alignment of pointers is a serious thing, and you should not try to break it.
If you create a variable, the compiler can check the alignment:
void f(void) { int x; } However, things are not so simple in the case of dynamically allocated memory:
int *ptr = malloc(sizeof(*ptr)); Malloc has no idea what kind of data it will be, it simply allocates four bytes, not knowing if it is an int , or two short , four char , or something else.
And therefore, in order to observe the correct alignment, it uses a very paranoid approach and returns a pointer aligned so far that this boundary is suitable for absolutely any type of data. On Mac OS X, malloc always returns pointers aligned on the 16-byte boundary.
Due to alignment, unused bits remain in the pointer. Here is what the hex pointer looks like, evened out by 16 bytes:
0x-------0 The last digit hex is always zero. In general, it may be quite a valid pointer that does not comply with these conditions (for example, char *), but the pointer to the object must always end in zero bits.
Some theory of tagged pointers
Knowing the empty bits at the end of the pointer, you can go further and try to use them. Why not use them as an indicator that this is not a real pointer to an object? Then we could store the data right here, in the pointer itself, without having to allocate expensive memory? Yes, yes, these are the very labeled pointers.
Systems that use labeled pointers perform an additional check — they look at the low-order bit, and if it is zero, then we have a real object. If this is a unit, then we are not an object but something else, and the information from the pointer will have to be extracted in a non-standard way. Typically, the data type is stored immediately after the low-order bit, and then the data itself follows.
This is how a valid binary object would look like:
....0000 ^ And this is a labeled pointer:
....xxx1 ^ All this can be implemented in various ways, but in Objective-C the low bit of the labeled pointer is always one, and the next three indicate the class of the pointer.
Application of tagged pointers
Labeled pointers are often used in languages where everything is an object. When 3 is agreed, 3 + 4 includes two objects, and even the creation of a third one, the allocation of memory for objects and the extraction of data from them begins to play a significant role in overall performance. All this fuss with the creation of objects, access to slow memory, entering values into an object that no one uses, many times exceeds the cost of the addition.
Using tagged pointers saves us from these adversities for all types that fit in those empty bits. Small ints are ideal candidates for this role - they take up very little space and are widely used.
This is what a regular triple would look like:
0000 0000 0000 0000 0000 0000 0000 0011 But the troika, hidden in a labeled pointer:
0000 0000 0000 0000 0000 0000 0011 1011 ^ ^ ^ | | | (5) | Here I assumed that the five is used to designate int, but in fact it remains at the discretion of the system, and everything can change at any time.
The observant reader probably already noticed that we only have 28 bits left on the 32-bit system and 60 on the 64-bit one. And the integers can take on large values. That's right, not every int can be hidden in a labeled pointer, for some you will have to create a full-fledged object.
When everything fits in one pointer, there is no need to allocate a separate memory, to clear it. Also, we simply save a small amount of memory, which we would have to allocate for a separate object. This may seem insignificant with the addition of three and four, but with a large number of operations on numbers, this increase is very noticeable.
The presence of bits indicating the type of data in the pointer makes it possible to store there not only int, but also floating-point numbers, and even several ASCII characters (8 for a 64-bit system). Even an array with a pointer to one element can fit in a labeled pointer! In general, any fairly small and widely used data type is an excellent candidate for use within a labeled pointer.
Well, enough theory, go to practice!
We will take MANumber as a basis — a custom implementation of NSNumber, and add support for labeled pointers there.
I want to note that labeled pointers are a very, very closed API, so you can't even think about using them in a real project. Under the definition of an object class, only three bits are allocated - in total, only eight classes can be involved simultaneously. If you accidentally intersect with the class used by Apple, that's all. And, due to the fact that this information can change in absolutely any way, at any time, the likelihood that trouble will happen once equals one hundred percent.
However, nothing prevents us from playing with them, even if we never have the opportunity to use them safely.
Well, let's begin. The private _objc_insert_tagged_isa function allows you to assign a certain class to a specific tag. Here is its prototype:
void _objc_insert_tagged_isa(unsigned char slotNumber, Class isa); You transfer the slot number (tag) and the required class to it, and it tells them in a certain table for further use during execution.
Virtually any class on labeled pointers needs a close class that will create a normal object in the event that the value does not fit within the pointer. For NSNumber, these will be particularly large ints and doubles, which are very difficult to push into the pointer, and I will not do this here.
For this there are two approaches. The first is to create two completely different classes, with some common ancestor for the code, which will be repeated in both descendants. The second is that within the same class we will use different code, depending on the value that we need to keep. I will use the second approach, so it seemed to me easier for this particular case.
To store the value of a variable, I used a union :
union Value { long long i; unsigned long long u; double d; }; This is followed by some constants that define the information in the labeled index. First - the slot number, I took it equal to one:
const int kSlot = 1; I also decided to determine the number of labeled pointers - this is needed to further extract the values:
const int kTagBits = 4; MANumber, in addition to the value itself, stores its type, indicating how to interact with it, and since we need to compress everything to the maximum, and we have only three possible types, I allocated two bits to this:
const int kTypeBits = 2; Although I did not implement double support, I still left room for it in order to maintain uniformity with the usual MANumber and facilitate my possible double support in the future.
And finally, since the type of integers that we store is long long, it would be nice to know for sure how many bits it takes:
const int kLongLongBits = sizeof(long long) * CHAR_BIT; Here, I assume that the pointer type is long long, I did not try to support 32-bit systems.
For more convenience, I have written several helper functions. The first creates a labeled MANumber, taking as input the data type and value:
static id TaggedPointer(unsigned long long value, unsigned type) { Let me remind the structure of the labeled pointer. The low bit is always one. It is followed by three bits indicating the class of the object, and only then the object data itself. In our case, these are the two bits that define the type, and after them the value itself. Here is a string that combines and records all this information using bitwise operations:
id ptr = (__bridge id)(void *)((value << (kTagBits + kTypeBits)) | (type << kTagBits) | (kSlot << 1) | 1); In connection with the strange double type conversion - I use ARC, and he is very selective in this matter. Therefore, when you convert pointers to objects into pointers to non-objects, a __bridge is needed, and the int pointer will not allow you to convert it to int. That is why I first convert to void *, and then all this into an object.
With this all, and now I return the newly created pointer:
return ptr; } Also, I created a function that checks whether a pointer is marked or not. All she does is check the low-order bit, but because of the stupid double type conversion, she had to be rendered into a separate function.
static BOOL IsTaggedPointer(id pointer) { uintptr_t value = (uintptr_t)(__bridge void *)pointer; return value & 1; } Finally, a function that extracts all the information from a labeled pointer. Since C does not support returning multiple values at once, I created a special structure for this: it contains the type and the value itself
struct TaggedPointerComponents { unsigned long long value; unsigned type; }; This function first converts the pointer to an int, using the same type conversion, only in the opposite direction:
static struct TaggedPointerComponents ReadTaggedPointer(id pointer) { uintptr_t value = (uintptr_t)(__bridge void *)pointer; Then we start to extract the necessary information. The first four bits can be ignored, and the value is extracted by a simple shift:
struct TaggedPointerComponents components = { value >> (kTagBits + kTypeBits), To get the type, you must not only move, but also apply a mask
(value >> kTagBits) & ((1ULL << kTypeBits) - 1) }; As a result, all components are received, and we simply return them in the form of a structure.
return components; } At some point, we have to tell the runtime that we are a class that runs on labeled pointers by calling the _objc_insert_tagged_isa function. Best suited for this + initialize. For security reasons, Objective-C Runtime does not like to overwrite a slot, and therefore you first need to write nil, and only then our new class:
+ (void)initialize { if(self == [MANumber class]) { _objc_insert_tagged_isa(kSlot, nil); _objc_insert_tagged_isa(kSlot, self); } } Now we can proceed to the process of creating labeled pointers. I wrote two methods: + numberWithLongLong: and + numberWithUnsignedLongLong:. These methods attempt to create objects on labeled pointers, and if the value is too large, they simply create ordinary objects.
These methods can create a labeled pointer only for a specific set of values - they must fit in kLongLongBits - kTagBits - kTypeBits, or 58 bits in a 64-bit system. One bit is needed to designate a sign, for a total, the maximum value of long long is 2 in 57, the minimum in -57.
+ (id)numberWithLongLong: (long long)value { long long taggedMax = (1ULL << (kLongLongBits - kTagBits - kTypeBits - 1)) - 1; long long taggedMin = -taggedMax - 1; It remains the most simple. If the value is outside the limits, we perform the usual dance with alloc / init. Otherwise, we create a labeled pointer with the given value and the class INT:
if(value > taggedMax || value < taggedMin) return [[self alloc] initWithLongLong: value]; else return TaggedPointer(value, INT); } For unsigned long long, everything is the same, except for increasing the set of values due to an unnecessary sign bit:
+ (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); } Now we need an accessor type for our pointers so that we can simply call the [self type], without worrying about the bits, the mask, and so on. All he does is check the pointer with the IsTaggedPointer function, and if it is tagged, call ReadTaggedPointer. If the pointer is normal, simply return _type:
- (int)type { if(IsTaggedPointer(self)) return ReadTaggedPointer(self).type; else return _type; } The accessor of values will be somewhat more complicated due to difficulties with the sign. First of all, let's check if it’s a regular pointer:
- (union Value)value { if(!IsTaggedPointer(self)) { return _value; } For the tagged ones, we will first have to read the value using ReadTaggedPointer. At the output, we have unsigned long long, so we have to work a little if the value really has a sign.
else { unsigned long long value = ReadTaggedPointer(self).value; Create a local variable of the union Value type for the return value:
union Value v; If it is unsigned, then everything is simple - put the value in v, and that's it:
int type = [self type]; if(type == UINT) { vu = value; } With signed, everything is not so simple. First, let's check the sign bit - it is hidden in bit 57:
else if(type == INT) { unsigned long long signBit = (1ULL << (kLongLongBits - kTagBits - kTypeBits - 1)); If the bit is equal to one, then all the bits that follow 57 bits need to be filled with ones, this is necessary for the given long long to be a valid 64-bit negative number. This procedure is called sign extension, in short its essence is this: negative numbers begin with ones, and the first zero is the first significant bit. Therefore, to expand a negative number, you simply add units to the left:
if(value & signBit) { unsigned long long mask = (((1ULL << kTagBits + kTypeBits) - 1) << (kLongLongBits - kTagBits - kTypeBits)); value |= mask; } With positive numbers, you do not need to do anything - they are already filled with zeros on the left. So just fill in v:
vi = value; } If we got some other type, then things are bad, we will have to throw out:
else abort(); As a result, we return v:
return v; } } Having written all this code, we get the opportunity to work with the new MANumber, as with the usual one, with the only difference being that we will have to access the values not directly, but through accessor methods. We can even compare labeled and regular MANumber using compare: and isEqual:.
findings
Labeled pointers are a great addition to the Cocoa and Objective-C runtime, which allows you to significantly increase the speed of work and reduce memory costs when working with NSNumber.
We can write our own classes that work with labeled pointers to shed light on the internal structure of NSNumber, however, due to the very limited number of free slots, there is no way to use them in real code. This is purely Cocoa's pre -rigative, greatly accelerating its work.
Well, it runs perfectly, and we can only be glad that inside this simple NSNumber there is such a wonderful mechanism.
(Free translation of fresh Friday Q & A by Mike Ash)
UPDATE:
As promised, the practical application of labeled pointers was not long in coming.Source: https://habr.com/ru/post/149012/
All Articles