Wrapping a Dynamic C-Array

For version 0.2.0 of DTMarkdownParser I needed an array that would allow me to look up the string range for individual lines of a string. My initial approach was to simple use the provided method of NSValue to wrap an NSRange in it. The problem with this approach is that as the number of ranges in the array grows so does the time needed to find a range at a higher index.

Jan Weiß of Geheimwerk suggested to replace this approach with one based on C memory allocation and searching functions. This required me to brush up on my dynamic C-array allocation skills which had become somewhat rusty from only using Objective-C objects for everything. The techniques I’ll be discussing in this blog might be of great value to you, too, if you ever find yourself needing to quickly find a scalar value (i.e. a number or struct) in a dynamically sizing array.

The code discussed in this article is available on GitHub as DTRangesArray.m.

Strategy First

The design goal for DTRangesArray is to have a dynamically growing array of NSRange values where we can add values, retrieve values by index, and find the range or index containing a particular string location.

NSRange is a compound of two scalar values, location and length.

It is defined as a struct which tells the compiler that every time you are creating an NSRange variable it requires sufficient RAM for a location and a length value. The lengths of those depend on the “bitness” of the operating system. 64-bit OS use 64-bit integers, 32-bit OS uses 32-bits per value, so depending on the circumstances one NSRange might either be either 16 or 8 bytes in length. You don’t have to care about the actual length of those values because the handy C-operator sizeof always knows the number of bytes needed for a given type.

typedef struct _NSRange {
    NSUInteger location;
    NSUInteger length;
} NSRange;

C has arrays, though they don’t look at all like the convenient NSArray instances you might have been working with so far. In C an array is simply a contiguos  range of memory. An array variable is simply a pointer to the first element in the array and the rest is done with pointer arithmetic.

Not only do you not have to worry about the the sizes of the individual array elements, you also don’t have to think about alignment. Mostly for performance reasons the compiler will automatically align variables, structs and arrays such that they match with certain internal “word boundaries”.

Allocation, Allocation, Allocation

In C memory – at the most basic level – can be allocated either with malloc or calloc. For malloc you specify the number of bytes to allocate. For calloc you specify the number of elements and the size per element. The c in calloc stands for “clear” because in contrast to malloc which reserves the RAM as is, calloc also fills the memory with binary zeroes.

To allocate the initial amount of memory for our dynamic array we start with enough for 100 ranges:

_capacity = 100;
_ranges = malloc(_capacity * sizeof(NSRange));
 
// same as:
_ranges = calloc(_capacity, sizeof(NSRange));

We do not require the memory to be cleared since we are not going to access an array element before adding it to the array. So we prefer malloc which is faster by a very tiny margin. The other good reason to not clear it is that we want to get garbage values if we make a programming mistake and allow access of non-initialised values.

The system keeps track of how much memory was allocated for given pointer and so for releasing it back to the system we uniformly use free. You might get an uneasy feeling from seeing a -dealloc method being implemented in times of ARC, but the magic of automatic retain counting will never reach down to the C level.

- (void)dealloc
{
   free(_ranges);
}

We will keep track of the current capacity in our dynamic array in the _capacity instance variable. The _count instance variable keeps track of how many slots – counting from 0 – have been filled. Whenever we reach capacity we double the amount of allocated memory. Consider this method to add a new range to the end of the array:

- (void)_extendCapacity
{
   if (_capacity)
   {
      _capacity = _capacity*2;
      _ranges = realloc(_ranges, _capacity * sizeof(NSRange));
   }
   else
   {
      _capacity = 100;
      _ranges = malloc(_capacity * sizeof(NSRange));
   }
}
 
- (void)addRange:(NSRange)range
{
   if (_count+1>_capacity)
   {
      [self _extendCapacity];
   }
 
   _ranges[_count] = range;
   _count++;
}

You can spot the last of the useful memory allocation methods in here: realloc. This does by far the most work of all allocation methods. It first tries to extend the allocated space in place. If that fails – due to some other variables being in the way – it will allocate a fresh chunk of memory and then copy the contents of the previous memory region to the new place. Then it also frees the previous memory region.

This ability to – potentially – extend an array in place and the automatic copying makes it ideal for our use. Note that if you extend a region zeroed with calloc before does not also zero the extended parts.

Those are the three allocations mentioned in the sub heading: plain allocation, cleared allocation and re-allocation. And then there is free which cleans up after these three.

Getting it Back

We want to be able to know from outside the class how many elements are already stored and also be able to retrieve the value at a given index.

- (NSUInteger)count
{
   return _count;
}
 
- (NSRange)rangeAtIndex:(NSUInteger)index
{
   NSAssert(index<_count, @"Cannot retrieve index %lu which is outside of number of ranges %lu", 
      (unsigned long)index, (unsigned long)_count);
 
   return _ranges[index];
}

The count simply passes throughout he before mentioned _count instance variable. A -rangeAtIndex: method returns the appropriate value.

Since we never want to be able to retrieve a value outside of the valid range of indexes we put an assertion in there. This guards the method at DEBUG time. When building for RELEASE assertions are usually removed by the compiler. This way we notice if we have a programming error, but when releasing an app using this code there is no performance penalty.

Using Objective-C objects wrapping for scalar values will increase in speed for 64-bit systems, due to the use of tagged pointers.

A slightly more involved way of retrieving the range values is to enumerate over them. Fancy a block-based enumeration function?

- (void)enumerateLineRangesUsingBlock:(void(^)(NSRange range, NSUInteger idx, BOOL *stop))block
{
   NSParameterAssert(block);
 
   for (NSUInteger idx = 0; idx<_count; idx++)
   {
      NSRange range = _ranges[idx];
      BOOL stop = NO;
 
      block(range, idx, &amp;stop);
 
      if (stop)
      {
         break;
      }
   }
}

We get each value by index in a for loop, call the enumeration block and if our stop BOOL is set to YES we break out of the enumeration.

The NSParameterAssert is a shorter variant of the above mentioned NSAssert. It checks that a value is not equal to zero/nil and if it is will construct an appropriate exception message. We don’t want anybody to call this method without passing a block, since this would be nonsensical.

If Ye Seek …

My initial method for finding a specific range involved enumerating the values much similar to the above shown enumeration method. I would always begin from index 0 and then work my way upwards until a range would include the location I was looking for. This is called Linear Search.

The higher the index of the range we are looking for the more superfluous values we are going to skip. Fortunately there is a much smarter way of searching that does not have a linear increase in search time: Binary Searching.

It’s not called Binary because we are searching for computer bits. It’s called Binary because it is honing in on the sought value by dividing the remaining searched items in two halves of equal size. Divide and Conquer!

At each iteration the location we are looking for is compared with the range. If the location is less than the begin of the range then we know it must be “somewhere to the left”. If the location is higher then the end of the range then it must be “somewhere to the right” of it. If it is inside the range we have found it.

Fortunately for us, a binary searching function is part of C’s Standard Library stdlib. There are two flavours: bsearch which requires a C-function for comparing the key to the array element. And bsearch_b which conveniently lets us use a block.

- (NSRange *)_rangeInRangesContainingLocation:(NSUInteger)location
{
   int (^comparator)(const void *, const void *);
 
   comparator = ^(const void *locationPtr, const void *rangePtr) {
 
      NSUInteger location = *(NSUInteger *)locationPtr;
      NSRange range = *(NSRange *)rangePtr;
 
      if (location < range.location)
      {
          return -1;
      } 		       
 
      if (location >= NSMaxRange(range))
      {
         return 1;
      }
 
      return 0;
   };
 
   return bsearch_b(&amp;location, _ranges, _count, sizeof(NSRange), comparator);
}

The comparator block returns negative values if the location is before the range, positive values if the location is after the range and 0 it it is inside the range. The bsearch_b function takes a pointer to the sought value, a pointer to the array, the element count, the size of one element and the comparator block.

I prefixed the method with an underscore because it is used by two further public methods, one to retrieve the index of the range found and another to retrieve the found range.

- (NSUInteger)indexOfRangeContainingLocation:(NSUInteger)location
{
   NSRange *found = [self _rangeInRangesContainingLocation:location];
 
   if (found)
   {
      return found - _ranges; // calc index
   }
 
   return NSNotFound;
}
 
- (NSRange)rangeContainingLocation:(NSUInteger)location
{
   NSRange *found = [self _rangeInRangesContainingLocation:location];
 
   if (found)
   {
      return *found;
   }
 
   return NSMakeRange(NSNotFound, 0);
}

The searching method returns a pointer to the array element found. We can dereference it with the asterisk operator to return the value pointed to. Slightly more tricky is the calculation of the found index that might stump most Objective-C developers who have not an iron grasp of C pointer arithmetic.

In C if an addition or subtraction involves a pointer to an array you are not adding bytes, but array elements. Since found is a pointer to an NSRange and _ranges is a pointer to an NSRange a subtraction will be the number of NSRange chunks in between. This works for the same reason as the square brackets. _ranges[3] is the same memory address as _ranges+3, the square brackets are simply a more convenient way of writing this.

It is because of this that you only need to subtract the pointers from another instead of having to somehow divide by sizeof(NSRange).

Conclusion

Creating a custom array for scalar values has tremendous performance benefits for iterating and searching individual values. This allows us to realise those benefits but at the same time keep a nice Objective-C interface to it.

We have refreshed our memories as to the fundamental C memory allocation and deallocation methods. We created a C-array which automatically extends whenever it runs out of capacity. Retrieval of individual values as well as via enumeration is deceptively simple, we added assertions to shows us programming issues while we are working with development builds, but without performance penalty in release builds.

Finally we learned about a binary search function built into standard C that allows us to conquer the bottleneck previously incurred from linear searching.

The main message of this article should be that you don’t have to be afraid to drop to the pure C level if performance requires it. Now you know the basic tools to do that for dynamic arrays of scalar values.

Categories: Recipes