The historical origin and implementation principle of CFArray

In iOS development, NSArray is a very important data structure. Especially in the data caching and updating in TableView, NSArray is used to cache data and modify the displayed data. In Core Foundation, CFArray and NSArray correspond to each other, which aroused the author's interest in the native data structure implementation in Core Foundation and Foundation libraries, so let's study it.

CFArray History

NSArray and CFArray are Toll-Free Bridged. In opensource.apple.com, CFArray is open source. This is more helpful for our study and research. When Garan no Dou was working on his personal tool library, he once studied the history and implementation of CFArray. You can refer to his excellent blog before reading this article.

Array, an early document published in 2005, first introduced CFArray and tested its performance. It compared the performance of CFArray with that of the Vector container in STL. Since the implementation of the latter can be understood as an array encapsulation in C, most operations in the performance graph are linear. In the graph of CFArray, many differences can be found.

From the above analysis, we can see that the efficiency of CFArray during head insertion and tail insertion is almost constant, while the operation on the middle elements will suddenly change from linear efficiency of small data to linear efficiency at a threshold, and this jump can't help but remind us of the data structure transformation of HashMap in Java 8.

In the early days of ObjC, CFArray was implemented using a deque double-ended queue, so the head and tail operations were efficient, while the middle operations were linear. When the capacity exceeded about 300,000 (actually it should be 262140 = 2^18), the time complexity changed dramatically. In the source code, the threshold is defined by a macro as __CF_MAX_BUCKETS_PER_DEQUE. The specific code can be found in CF-550-CFArray.c (2011 version):

 if (__CF_MAX_BUCKETS_PER_DEQUE futureCnt) { 
 
 // Create a CFStorage reference 
 
 CFStorageRef store 
 
 // Convert CFArray to Storage 
 
    __CFArrayConvertDequeToStore(array); 
 
    store = (CFStorageRef)array->_store; 
 
 }

As you can see, when the data exceeds the threshold __CF_MAX_BUCKETS_PER_DEQUE, the data structure will be converted from CFArray to CFStorage. CFStorage is a balanced binary tree structure. In order to maintain the sequential access of the array, the weight of the Node is inserted and rotated using the subscript. The specific embodiment can be seen in the CFStorageInsertValues ​​operation. The specific code can be found in CF-368.18-CFStorage.c.

In the CF-635.15-CFArray.c version after 2011, CFArray canceled the data structure conversion function. Perhaps this feature was canceled to prevent the time jitter problem of binary tree construction when large data is used. Let's take a look at the description of the data structure directly:

 struct __CFArrayDeque { 
 
 uintptr_t _leftIdx; // Subscript position from the left 
 
 uintptr_t _capacity; // Current capacity 
 
 }; 
 
 struct __CFArray { 
 
 CFRuntimeBase _base; 
 
 CFIndex _count; // Number of elements 
 
 CFIndex _mutations; // Element jitter amount 
 
 int32_t _mutInProgress; 
 
 __strong void *_store; 
 
 };

From the name, we can see that CFArray is implemented by a single double-ended queue and records some container information.

Some issues with C arrays

An array in C language will open up a continuous memory space for data reading, writing and storage operations. In addition, arrays and pointers are not the same. There is a statement that is abused in many textbooks: a malloced memory space is equivalent to an array. This is wrong. The simplest explanation is that a pointer needs to apply for a pointer area to store (point to) the starting position of a space, while the array (head) is a direct access to the starting position of a space. In addition, if you want to know more, you can read the blog post Are pointers and arrays equivalent in C?

The most significant disadvantage of arrays in C is that when inserting at index 0, all elements need to be moved (that is, the principle of the memmove() function). Similarly, when deleting the first element and inserting an element before the first element, it will also cause an operation with O(n) complexity. However, arrays are containers that are often read and written, so O(n) operations will cause serious time overhead.

Some implementation details of CFArray in the current version

In CF-855.17, we can see the implementation of the current version of CFArray. The document describes CFArray as follows:

CFArray implements a compact container that can be accessed sequentially by pointers. Its values ​​can be accessed through integer keys (index subscripts) ranging from 0 to N-1, where N is the number of values ​​in the array. It is called compact because when the container deletes or inserts a value, no gaps are left in the memory space. The access order is still arranged according to the original key value size, so that the effective retrieval set range is always in the integer range [0, N-1]. Therefore, the subscript of a specific value may change as other elements are inserted into the array or deleted.

There are two types of arrays: immutable, which means you can't add or remove elements from an array after it's created, and mutable, which means you can add or remove elements from it. A mutable array is limited in number (or limited only by constraints external to CFArray, such as the amount of available memory). As with all CoreFoundation collection types, arrays maintain strong references to their element objects.

To further clarify the details of CFArray, let's analyze several operations of CFArray:

 // Query element value by subscript 
 
 const void *CFArrayGetValueAtIndex(CFArrayRef array, CFIndex idx) { 
 
 // This function is not open source yet 
 
 // Verify that the specified element matches the Core Foundation bridge class with the given CFTypeID 
 
    CF_OBJC_FUNCDISPATCHV(__kCFArrayTypeID, const void *, (NSArray *)array, objectAtIndex:idx); 
 
 // Not open source yet 
 
 // Verify the Core Foundation type validity with the given CFTypeID 
 
    __CFGenericValidateType(array, __kCFArrayTypeID); 
 
    CFAssert2(0 idx && idx __CFArrayGetCount(array), __kCFLogAssertion, "%s(): index (%d) out of bounds" , __PRETTY_FUNCTION__, idx); 
 
    CHECK_FOR_MUTATION(array); 
 
 // Get the element from the memory location 
 
 return __CFArrayGetBucketAtIndex(array, idx)->_item; 
 
 } 
 
 // Return the address of the query element 
 
 CF_INLINE struct __CFArrayBucket *__CFArrayGetBucketAtIndex(CFArrayRef array, CFIndex idx) { 
 
    switch (__CFArrayGetType(array)) { 
 
 // Only two array types are allowed 
 
 // Immutable corresponds to ordinary linear structure, mutable corresponds to double-ended queue 
 
 case __kCFArrayImmutable: 
 
 case __kCFArrayDeque: 
 
 // Take the address and add the index offset to return the element address 
 
 return __CFArrayGetBucketsPtr(array) + idx; 
 
 } 
 
 return   NULL ; 
 
 }

In the index subscript query operation, CFArray still inherits the property of the continuous address space of the traditional array, so its time can still be maintained at O(1) complexity, which is very efficient.

 void CFArrayInsertValueAtIndex(CFMutableArrayRef array, CFIndex idx, const void *value) { 
 
 // Verify that the specified element matches the Core Foundation bridge given the CFTypeID 
 
    CF_OBJC_FUNCDISPATCHV(__kCFArrayTypeID, void, (NSMutableArray *)array, insertObject:(id)value atIndex:(NSUInteger)idx); 
 
 // Verify the Core Foundation type validity with the given CFTypeID 
 
    __CFGenericValidateType(array, __kCFArrayTypeID); 
 
    CFAssert1(__CFArrayGetType(array) != __kCFArrayImmutable, __kCFLogAssertion, "%s(): array is immutable" , __PRETTY_FUNCTION__); 
 
    CFAssert2(0 idx && idx __CFArrayGetCount(array), __kCFLogAssertion, "%s(): index (%d) out of bounds" , __PRETTY_FUNCTION__, idx); 
 
 // Type checking 
 
    CHECK_FOR_MUTATION(array); 
 
 // Call this function to perform specific array change process 
 
    _CFArrayReplaceValues(array, CFRangeMake(idx, 0), &value, 1); 
 
 } 
 
 // This function has not been dispatched by ObjC, i.e., the CF_OBJC_FUNCDISPATCHV method 
 
 // Therefore, for safety reasons, it can only be used after the entry of a function that has been scheduled and checked. 
 
 void _CFArrayReplaceValues(CFMutableArrayRef array, CFRange range, const void **newValues, CFIndex newCount) { 
 
 // Further type checking 
 
    CHECK_FOR_MUTATION(array); 
 
 // Lock operation, add spin lock to prevent competition 
 
 BEGIN_MUTATION(array); 
 
 //Declare callback 
 
    const CFArrayCallBacks *cb; 
 
 //Offset subscript, total number of elements, total number of elements after the array is changed 
 
    CFIndex idx, cnt, futureCnt; 
 
    const void **newv, *buffer[256]; 
 
 // Get the number of elements in the array 
 
    cnt = __CFArrayGetCount(array); 
 
 // Total number of new array elements = total number of original array elements - number of deleted elements + number of added elements 
 
    futureCnt = cnt - range.length + newCount; 
 
    CFAssert1(newCount futureCnt, __kCFLogAssertion, "%s(): internal error 1" , __PRETTY_FUNCTION__); 
 
 // Get the callback method defined in the array 
 
    cb = __CFArrayGetCallBacks(array); 
 
 //Construct allocation and release memory abstraction 
 
    CFAllocatorRef allocator = __CFGetAllocator(array); 
 
 //Hold the new element if necessary and allocate a temporary buffer for it 
 
 // The standard is whether the number of new elements exceeds 256 
 
    if ( NULL != cb->retain && !hasBeenFinalized(array)) { 
 
 newv = (newCount 256) ? (const void **)buffer : (const void **)CFAllocatorAllocate(kCFAllocatorSystemDefault, newCount * sizeof(void *), 0); 
 
 if (newv != buffer && __CFOASafe) __CFSetLastAllocationEventName(newv, "CFArray (temp)" ); 
 
 // Add data buffer for new elements 
 
 for (idx = 0; idx newCount; idx++) { 
 
    newv[idx] = (void *)INVOKE_CALLBACK2(cb->retain, allocator, (void *)newValues[idx]); 
 
 } 
 
 } else { 
 
 newv = newValues; 
 
 } 
 
 // Data jitter amount added automatically 
 
 array->_mutations++; 
 
 // Now the storage area of ​​an array is divided into three parts, each of which may be empty 
 
 // A: From index zero to the area smaller than range.location 
 
 // B: the passed range.location area 
 
 // C: from range.location + range.length to the end of the array 
 
 // Note that the index 0 is not necessarily located at the first position of available storage. When the number of new values ​​in the changed position is different from the number of old values, area B needs to be released and then replaced, and then the values ​​in A and C are shifted according to the situation. 
 
 if (0 range.length) { 
 
 // Normal release of the change area operation 
 
 __CFArrayReleaseValues(array, range, false ); 
 
 } 
 
 // Area B is now empty and needs to be refilled with data 
 
 if (0) { 
 
 // The judgment conditions and codes are hidden here. 
 
 // The general operation is to exclude other interference factors, such as incomplete release of data in area B, etc. 
 
    } else if ( NULL == array->_store) { 
 
 // Determine the release of area B by referencing the pointer at the first address of the data 
 
 if (0) { 
 
 // The judgment conditions and code are hidden here 
 
 // Eliminate interfering conditions, such as futureCnt being illegal, etc. 
 
 } else if (0 futureCnt) { 
 
 //Declare a double-ended queue object 
 
    struct __CFArrayDeque *deque; 
 
 // Determine the total number of elements that can be loaded in the circular buffer area based on the total number of elements 
 
    CFIndex capacity = __CFArrayDequeRoundUpCapacity(futureCnt); 
 
 // Determine the space allocation size based on the number of elements 
 
    CFIndex size = sizeof(struct __CFArrayDeque) + capacity * sizeof(struct __CFArrayBucket); 
 
 // Construct the storage cache through the buffer constructor 
 
    deque = (struct __CFArrayDeque *)CFAllocatorAllocate((allocator), size , isStrongMemory(array) ? __kCFAllocatorGCScannedMemory : 0); 
 
    if (__CFOASafe) __CFSetLastAllocationEventName(deque, "CFArray (store-deque)" ); 
 
 // Determine the left value of the double-ended queue 
 
    deque->_leftIdx = (capacity - newCount) / 2; 
 
    deque->_capacity = capacity; 
 
    __CFAssignWithWriteBarrier((void **)&array->_store, (void *)deque); 
 
 // Complete the construction of area B and release the array safely 
 
            if (CF_IS_COLLECTABLE_ALLOCATOR(allocator)) auto_zone_release(objc_collectableZone(), deque); 
 
 } 
 
 } else { // Deque 
 
 // Reposition the storage status of elements in area A and C according to the changes in area B elements 
 
 if (0) { 
 
 } else if (range.length != newCount) { 
 
 // Pass in the array reference, and finally update the A, B, and C partition rules of the array according to the changes 
 
    __CFArrayRepositionDequeRegions(array, range, newCount); 
 
 } 
 
 } 
 
 //Copy the new changes in area B to area B 
 
 if (0 newCount) { 
 
 if (0) { 
 
 } else { // Deque 
 
 // Access linear storage 
 
    struct __CFArrayDeque *deque = (struct __CFArrayDeque *)array->_store; 
 
 // Add a cache area based on the original 
 
    struct __CFArrayBucket *raw_buckets = (struct __CFArrayBucket *)((uint8_t *)deque + sizeof(struct __CFArrayDeque)); 
 
 // Change the data in area B, similar to memcpy, but with write barrier, thread-safe 
 
    objc_memmove_collectable(raw_buckets + deque->_leftIdx + range.location, newv, newCount * sizeof(struct __CFArrayBucket)); 
 
 } 
 
 } 
 
 // Set the new element count attribute 
 
    __CFArraySetCount(array, futureCnt); 
 
 // Release the cache area 
 
    if (newv != buffer && newv != newValues) CFAllocatorDeallocate(kCFAllocatorSystemDefault, newv); 
 
 //Remove thread safety protection 
 
 END_MUTATION(array); 
 
 }

In the operation of inserting elements in CFArray, it can be clearly seen that this is an operation of inserting elements in a double-ended queue (dequeue), and it is a static implementation of a buffer nested map table that imitates the storage method of the C++ STL standard library. Use a schematic diagram to illustrate the data structure:

In STL, deque uses a map table to record mapping relationships, while in Core Foundation, CFArray directly uses the second-order pointer _store to ensure such a secondary mapping relationship. In the operation of modifying elements, CFArray is also a bit violent. It first partitions the array into large blocks, then fills the data in order to form a new double-ended queue. For example, in the double-ended queue in the figure above, add an element with a value of 100 before the element with subscript 7:

According to the index subscript, the specified part of the cache area will be found, taken out and reconstructed. During the construction process, it may be divided into three areas: A, B, and C. Area B is the modified part. Of course, if it is not enough, the system will expand the cache area by itself, that is, the memory allocation/release strategy officially provided by CFAllocatorRef.

CFAllocatorRef is a strategy for allocating and releasing memory in Core Foundation. In most cases, you only need to use the default allocator kCFAllocatorDefault, which is equivalent to passing in a NULL parameter, which uses the so-called "regular method" of Core Foundation to allocate and release memory. This method may change, and we should not rely on any special behavior. There are few cases where special allocators are used. The following are the standard allocators and their functions given in the official documentation.

The last judgment in the _CFArrayReplaceValues ​​method:

 if (newv != buffer && newv != newValues) 
 
 CFAllocatorDeallocate(kCFAllocatorSystemDefault, newv);

The number of buffers will be checked. If there are too many, the extra buffers will be released. This is because this method is universal and can be used not only in inserting elements, but also in adding (CFArrayAppendValue), replacing (CFArrayReplaceValues), and deleting (CFArrayRemoveValueAtIndex). Since the data structure is managed in blocks, the time is shared and the complexity is greatly reduced. Therefore, we can see that the time complexity of CFArray is at a high level in querying and adding elements.

In the implementation of NSMutableArray, Apple uses CFArray to add expandable cache areas at both ends to solve the small memory characteristics of mobile terminals, which will cause a lot of waste. In the article "Unveiling the Principle of NSMutableArray", a reverse idea is used to explore the implementation principle of NSMutableArray. Its approach is to use a ring buffer to maximize the compression of the cache part. This is a solution proposed by Apple to address the limitations of mobile devices.

References:

• Let's Build NSMutableArray

http://t.cn/Rxs9e2g

• GNUStep · NSArray

http://t.cn/RxsCzbj

• What is the data structure behind NSMutableArray?

http://t.cn/RxsCvcG

• Apple Source Code – CF-855.17

http://t.cn/RxsCho3