How to implement circular buffer in Objective C for high performance

Question

We want to add an array of doubles to a circular buffer in Objective C many times a second.

We are currently using a NSMutableArray nested within another NSMutableArray (2D array). This works fine but is too slow for our needs.

We want to add to the circular buffer many times a second. When we do this and do performance monitoring we see the call to removeObjectAtIndex:0 become a bottleneck (shift n-1 objects or O(n-1)). This is because we have many thousands of entries in our circular buffer.

We have looked at possibly using STL and std::deque. We have also looked at CHDataStructures. As you know, STL is in in C++ and can be integrated but is not as straight forward as an Objective C solution. CHDataStructures is getting dated and is not ARC compliant.

Please suggest how we should implement a circular buffer (for our array of doubles) for high performance with a code sample if possible.

norders · Accepted Answer · 2017-01-27T09:34:54.323

Having read your comment (and thought about it a bit more) I realised use of a regular NSArray would be better, as there are no memory management issues (NSArrays retain their objects naturally). Just define the capacity up front to avoid it having to reallocate memory as it runs. Calling [self resetBuffer] will quickly release all data and start again.

#define BUFFER_SIZE 1000

@implementation ViewController {
    NSMutableArray *circularBuffer;
    NSUInteger bufferHead;
}

- (instancetype)initWithCoder:(NSCoder *)aDecoder {
    if (self = [super initWithCoder:aDecoder]) {
        [self resetBuffer];
    }
    return self;
}

- (void)addArrayToBuffer:(NSMutableArray *)incoming {

    if (bufferHead < circularBuffer.count)
        [circularBuffer replaceObjectAtIndex:bufferHead withObject:incoming];
    else
        [circularBuffer addObject:incoming];

    bufferHead = (bufferHead + 1) % BUFFER_SIZE;
}

- (NSArray *)bufferContent {

    if (circularBuffer.count < BUFFER_SIZE) {
        return circularBuffer;
    } else {
        NSArray *arrHead = [circularBuffer objectsAtIndexes:[NSIndexSet indexSetWithIndexesInRange:NSMakeRange(0, bufferHead)]];
        NSArray *arrTail = [circularBuffer objectsAtIndexes:[NSIndexSet indexSetWithIndexesInRange:NSMakeRange(bufferHead, BUFFER_SIZE-bufferHead)]];

        return [arrTail arrayByAddingObjectsFromArray:arrHead];
    }
}

- (void)resetBuffer {
    circularBuffer = [NSMutableArray arrayWithCapacity:BUFFER_SIZE];
    bufferHead = 0;
}

This looks interesting. I have some questions for you. 1. Why are you using CFBridgingRelease and CFBridgingRetain with the circularBuffer NSMutableArray? Wouldn't objects added to circularBuffer be automatically managed? 2. If we wanted to read from circularBuffer from start to end how would we do that without a head variable, especially before the buffer is filled for the first time? 3. What would be the most efficient way to empty the circularBuffer? — philipfc, Jan 26 '17 at 16:59
The updated answer seems pretty good. It appears like the hotspot will be reading the buffer content. Would it be better to use an enumerator (fast enumerator if possible) so that the circular buffer would not need to be copied to new arrays once the buffer has looped? — philipfc, Jan 27 '17 at 23:11
I doubt that using enumerators will be faster, as it's only copying a range of pointers. Couldn't say 100% though. — norders, Jan 28 '17 at 17:04

How to implement circular buffer in Objective C for high performance

1 Answers1