This article is based on the compilable objC4-750 version of the source code for the discussion, there are mistakes in the article, I would like you to correct.

When we read the source code to study the principle of weak implementation, layer by layer dive to weak_entry_t before, can not open StripedMap

structure; Or if you just want to understand the implementation differences between the various keywords of the property, you can’t go into the reallySetProperty() method without seeing something like StripedMap

. You’ll come to a template class called StripedMap

with a “Map” in its name, which is similar to the implementation of hashMap. However, it doesn’t seem relevant to the problem we’re working on, and it doesn’t matter if we just call it a hashMap, as many blogs have done in a couple of sentences. But when I stayed a little longer in one of them, I also gained a little. This article is just to record my little experience of exploring StripedMap

.



First the conclusion:
  1. Its main function is caching.”Class or structure with spinlock locking capability“(such as:spinlock_t,SideTable), the number of structures it can store inside is fixed and limited (8 on a real iPhone, depending on the size of its internal array).
  2. It uses the address of the object as the key to get the corresponding<T>.
  3. It has on<T>The visits played a triage role while the<T>The access triage is carried out to avoid high frequency calls where access is<T>The resulting performance bottlenecks optimize overall efficiency.
Look at the usage scenario:

Let’s look at two scenarios where StripedMap

is used:

  1. StripedMap<spinlock_t>
// 1. Declare StripedMap<spinlock_t> PropertyLocks; Static inline void reallySetProperty(id self, SEL _cmd, id newValue, ptrdiff_t offset, bool atomic, bool copy, bool mutableCopy) { // ... spinlock_t& slotlock = PropertyLocks[slot]; slotlock.lock(); / /... slotlock.unlock(); / /... }Copy the code

You end up in this function when you call the default property setting method. The actual assignment of an object pointer is protected by the Spinlock_t lock, which is obtained from the pre-declared and initialized PropertyLocks (StripedMap<spinlock_t> structure).

  1. StripedMap<SideTable>
Struct SideTable struct {spinlock_t slock; / /... weak_table_t weak_table; / /... template<HaveOld, HaveNew> static void lockTwo(SideTable *lock1, SideTable *lock2); template<HaveOld, HaveNew> static void unlockTwo(SideTable *lock1, SideTable *lock2); }; SideTables is a pre-initialized StripedMap<SideTable> static StripedMap<SideTable>& SideTables() {return *reinterpret_cast<StripedMap<SideTable>*>(SideTableBuf); Static id storeWeak(id *location, objc_object *newObj) {//... oldTable = &SideTables()[oldObj]; / /... newTable = &SideTables()[newObj]; / /... SideTable::lockTwo<haveOld, haveNew>(oldTable, newTable); // Lock both resources in the same order //... SideTable::unlockTwo<haveOld, haveNew>(oldTable, newTable); // Unlock two resources at the same time to ensure the sequence of the two locks //... }Copy the code

The SideTable structure contains a Spinlock_t and a Weak_table_t. It can be understood that each weak referenced object corresponds to a SideTable, and all weak Pointers referencing this object are stored in weak_table of SideTable. Therefore, when setting the weak object, the storeWeak() method is actually used. When the Weak_table is operated, the corresponding SideTable will also be protected by spintLock.

In both cases, spinlock is used to ensure atomicity of the operation. Imagine that the first scenario does not have a StripedMap<spinlock_t> object, and only globally initializes a spinlock_t. It is perfectly ok to use this spinlock_t wherever locks and unlock are needed. The same is true for the second scenario, if you don’t use a StripedMap and only initialize a SideTable object globally, it’s fine.

However, if there is only one Spinlock_T or SideTable in a place that is called so frequently, you can only operate on one object at a time and do nothing to the other objects, causing performance bottlenecks. However, creating a Spinlock_T or SideTable for each call, which is equivalent to creating one for each object, is neither practical nor necessary. To do this, prepare multiple Spinlock_T or sidetables and distribute them evenly when called, reducing blocking and waiting, which is the real purpose of StripedMap!

Finally, look at the internal implementation:

Let’s take a look inside the structure:

// StripedMap<T> is a map of void* -> T, sized appropriately // for cache-friendly lock striping. // For example, this may be used as StripedMap<spinlock_t> // or as StripedMap<SomeStruct> where SomeStruct stores a spin lock. template<typename T> class StripedMap { // ... Enum {StripeCount = 8}; / /... Struct PaddedT {// alignas is c++ alignment modifier, specifying alignment value // contains a member variable value of type T, and value is CacheLineSize byte alignment, // Cache Line is simply the smallest unit of Cache in the CPU Cache. The current CPU Cache Line size is 64Bytes. // Align the cacheline size with the cacheline size, which is an effective way to optimize efficiency. http://cenalulu.github.io/linux/all-about-cpu-cache/ T value alignas(CacheLineSize); }; PaddedT array[StripeCount]; // (p moves 4 bits to the right) xor (p moves 9 bits to the right) Static unsigned int indexForPointer(const void *p) {uintptr_t addr = reuintptr_t >(p); return ((addr >> 4) ^ (addr >> 9)) % StripeCount; } public: T& operator[] (const void *p) { return array[indexForPointer(p)].value; } const T& operator[] (const void *p) const { return const_cast<StripedMap<T>>(this)[p]; } // Shortcuts for StripedMaps of locks. // ... constexpr StripedMap() {} };Copy the code

(" / /..." Is omitted code)

This structure is a map with void * as the key and value of type

, which looks like a Dictionary (HashMap). We can see from the comments that

is mainly spinlock_t, or some other type containing spinlock_t (such as SideTable). As you can see from the public methods it provides, many of them are lock-related methods, from which you can see that its main purpose is to cache spinlock.

As you can see from this line, the StripedMap has a fixed-size array that actually holds values (of type

) :

PaddedT array[StripeCount];
Copy the code

This means that the total number of values is fixed, and the values are filled when the StripedMap is created. Assuming that the StripedMap< spinlock_T > is created when the StripedMap is created, then there are eight spinlock_t stored after the StripedMap is created. If a StripedMap is created as StripedMap

, then eight sideTables are stored after the StripedMap is created.

How to get a value from a void * pointer:

// (p moves 4 bits to the right) xor (p moves 9 bits to the right) Static unsigned int indexForPointer(const void *p) {uintptr_t addr = reuintptr_t >(p); return ((addr >> 4) ^ (addr >> 9)) % StripeCount; }Copy the code

The function of this method is very simple, just get the index value of an array based on the address of the pointer, and the bitwise manipulation ensures that it is very efficient. This method is similar to the hash method in Dictionary, except that the hash method ensures that the value of each key is as unique as possible, and even if it is not, there is an internal conflict handling mechanism to ensure that the corresponding value is unique. In this method, the values of all keys must fall into the finite array index, so it will be repeated. If enough keys are passed in, it should access all values in the array as evenly as possible.

Let’s draw a slightly less precise graph:

Finally:
  • The StripedMap is a special Map that does have a lot of similaritiesHashMapThere are some similarities. For example, key-value is used for storage, and the value can be obtained by key. But actually it’s not oneHashMapBecause theHashMapA key of a StripedMap can only correspond to a unique value, whereas a value of a StripedMap can be accessed through multiple keys.
  • Its real purpose is to cache and divert access to limited resources! The whole objC source is searched for three kinds: respectivelyspinlock_t,SideTableandSyncList)
  • In fact, earlier versions of objC’s source code did not have a StripedMap, and imagine that if you had only one spinlock for a place that needed to be called frequently, all access would have to wait for that lock, causing a performance bottleneck. Now using StripedMap for shunting, performance is naturally greatly improved.
  • The size of the array (StripeCount) varies from device to device depending on the macro definition, such as 8 for the iPhone and 64 for other devices (including emulators).