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.

Answer 1

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;
}