How can I render line faster than CGContextStrokePath?

Question

I'm plotting ~768 points for a graph using CGContextStrokePath. The problem is that every second I get a new data point, and thus redraw the graph. This is currently taking 50% CPU in what's already a busy App.

Graph drawing is done in drawRect in a UIView. The graph is time based, so new data points always arrive on the right hand side.

I'm thinking a few alternative approaches:

1. Draw with GLKit (at cost of not supporting older devices) and seems like a lot of work.
2. Do some kind of screen grab (renderInContext?), shift left by 1 px, blit, and only draw a line for the last two data points.
3. Have a very wide CALayer and pan along it?
4. Smooth the data set, but this feels like cheating :)

It's also possible I'm missing something obvious here that I'm seeing such poor performance?

    CGContextBeginPath(context);
CGContextSetLineWidth(context, 2.0);
UIColor *color = [UIColor whiteColor];
CGContextSetStrokeColorWithColor(context, [color CGColor]);
…
        CGContextAddLines(context, points, index);
        CGContextMoveToPoint(context, startPoint.x, startPoint.y);
        CGContextClosePath(context);

        CGContextStrokePath(context);

Answer 1

Let's implement a graphing view that uses a bunch of tall, skinny layers to reduce the amount of redrawing needed. We'll slide the layers to the left as we add samples, so at any time, we probably have one layer hanging off the left edge of the view and one hanging off the right edge of the view:

You can find a complete working example of the code below on my github account.

Constants

Let's make each layer 32 points wide:

#define kLayerWidth 32

And let's say we're going to space the samples along the X axis at one sample per point:

#define kPointsPerSample 1

So we can deduce the number of samples per layer. Let's call one layer's worth of samples a tile:

#define kSamplesPerTile (kLayerWidth / kPointsPerSample)

When we're drawing a layer, we can't just draw the samples strictly inside the layer. We have to draw a sample or two past each edge, because the lines to those samples cross the edge of the layer. We'll call these the padding samples:

#define kPaddingSamples 2

The maximum dimension of an iPhone screen is 320 points, so we can compute the maximum number of samples we need to retain:

#define kMaxVisibleSamples ((320 / kPointsPerSample) + 2 * kPaddingSamples)

(You should change the 320 if you want to run on an iPad.)

We'll need to be able to compute which tile contains a given sample. And as you'll see, we'll want to do this even if the sample number is negative, because it will make later computations easier:

static inline NSInteger tileForSampleIndex(NSInteger sampleIndex) {
    // I need this to round toward -∞ even if sampleIndex is negative.
    return (NSInteger)floorf((float)sampleIndex / kSamplesPerTile);
}

Instance Variables

Now, to implement GraphView, we'll need some instance variables. We'll need to store the layers that we're using to draw the graph. And we want to be able to look up each layer according to which tile it's graphing:

@implementation GraphView {

    // Each key in _tileLayers is an NSNumber whose value is a tile number.
    // The corresponding value is the CALayer that displays the tile's samples.
    // There will be tiles that don't have a corresponding layer.
    NSMutableDictionary *_tileLayers;

In a real project, you'd want to store the samples in a model object and give the view a reference to the model. But for this example, we'll just store the samples in the view:

    // Samples are stored in _samples as instances of NSNumber.
    NSMutableArray *_samples;

Since we don't want to store an arbitrarily large number of samples, we'll discard old samples when _samples gets big. But it will simplify the implementation if we can mostly pretend that we never discard samples. To do that, we keep track of the total number of samples ever received.

    // I discard old samples from _samples when I have more than
    // kMaxTiles' worth of samples.  This is the total number of samples
    // ever collected, including discarded samples.
    NSInteger _totalSampleCount;

We should avoid blocking the main thread, so we'll do our drawing on a separate GCD queue. We need to keep track of which tiles need to be drawn on that queue. To avoid drawing a pending tile more than once, we use a set (which eliminates duplicates) instead of an array:

    // Each member of _tilesToRedraw is an NSNumber whose value
    // is a tile number to be redrawn.
    NSMutableSet *_tilesToRedraw;

And here's the GCD queue on which we'll do the drawing.

    // Methods prefixed with rq_ run on redrawQueue.
    // All other methods run on the main queue.
    dispatch_queue_t _redrawQueue;
}

Initialization / Destruction

To make this view work whether you create it in code or in a nib, we need two initialization methods:

- (id)initWithFrame:(CGRect)frame {
    if ((self = [super initWithFrame:frame])) {
        [self commonInit];
    }
    return self;
}

- (void)awakeFromNib {
    [self commonInit];
}

Both methods call commonInit to do the real initialization:

- (void)commonInit {
    _tileLayers = [[NSMutableDictionary alloc] init];
    _samples = [[NSMutableArray alloc] init];
    _tilesToRedraw = [[NSMutableSet alloc] init];
    _redrawQueue = dispatch_queue_create("MyView tile redraw", 0);
}

ARC won't clean up the GCD queue for us:

- (void)dealloc {
    if (_redrawQueue != NULL) {
        dispatch_release(_redrawQueue);
    }
}

Adding a sample

To add a new sample, we pick a random number and append it to _samples. We also increment _totalSampleCount. We discard the oldest samples if _samples has gotten big.

- (void)addRandomSample {
    [_samples addObject:[NSNumber numberWithFloat:120.f * ((double)arc4random() / UINT32_MAX)]];
    ++_totalSampleCount;
    [self discardSamplesIfNeeded];

Then, we check if we've started a new tile. If so, we find the layer that was drawing the oldest tile, and reuse it to draw the newly-created tile.

    if (_totalSampleCount % kSamplesPerTile == 1) {
        [self reuseOldestTileLayerForNewestTile];
    }

Now we recompute the layout of all the layers, which will to the left a bit so the new sample will be visible in the graph.

    [self layoutTileLayers];

Finally, we add tiles to the redraw queue.

    [self queueTilesForRedrawIfAffectedByLastSample];
}

We don't want to discard samples one at a time. That would be inefficient. Instead, we let the garbage build up for a while, then throw it away all at once:

- (void)discardSamplesIfNeeded {
    if (_samples.count >= 2 * kMaxVisibleSamples) {
        [_samples removeObjectsInRange:NSMakeRange(0, _samples.count - kMaxVisibleSamples)];
    }
}

To reuse a layer for the new tile, we need to find the layer of the oldest tile:

- (void)reuseOldestTileLayerForNewestTile {
    // The oldest tile's layer should no longer be visible, so I can reuse it as the new tile's layer.
    NSInteger newestTile = tileForSampleIndex(_totalSampleCount - 1);
    NSInteger reusableTile = newestTile - _tileLayers.count;
    NSNumber *reusableTileObject = [NSNumber numberWithInteger:reusableTile];
    CALayer *layer = [_tileLayers objectForKey:reusableTileObject];

Now we can remove it from the _tileLayers dictionary under the old key and store it under the new key:

    [_tileLayers removeObjectForKey:reusableTileObject];
    [_tileLayers setObject:layer forKey:[NSNumber numberWithInteger:newestTile]];

By default, when we move the reused layer to its new position, Core Animation will animate it sliding over. We don't want that, because it will be a big empty orange rectangle sliding across our graph. We want to move it instantly:

    // The reused layer needs to move instantly to its new position,
    // lest it be seen animating on top of the other layers.
    [CATransaction begin]; {
        [CATransaction setDisableActions:YES];
        layer.frame = [self frameForTile:newestTile];
    } [CATransaction commit];
}

When we add a sample, we'll always want to redraw the tile containing the sample. We also need to redraw the prior tile, if the new sample is within the padding range of the prior tile.

- (void)queueTilesForRedrawIfAffectedByLastSample {
    [self queueTileForRedraw:tileForSampleIndex(_totalSampleCount - 1)];

    // This redraws the second-newest tile if the new sample is in its padding range.
    [self queueTileForRedraw:tileForSampleIndex(_totalSampleCount - 1 - kPaddingSamples)];
}

Queuing a tile for redraw is just a matter of adding it to the redraw set and dispatching a block to redraw it on _redrawQueue.

- (void)queueTileForRedraw:(NSInteger)tile {
    [_tilesToRedraw addObject:[NSNumber numberWithInteger:tile]];
    dispatch_async(_redrawQueue, ^{
        [self rq_redrawOneTile];
    });
}

Layout

The system will send layoutSubviews to the GraphView when it first appears, and any time its size changes (such as if a device rotation resizes it). And we only get the layoutSubviews message when we're really about to appear on the screen, with our final bounds set. So layoutSubviews is a good place to set up the tile layers.

First, we need to create or remove layers as necessary so we have the right layers for our size. Then we need to lay out the layers by setting their frames appropriately. Finally, for each layer, we need to queue its tile for redraw.

- (void)layoutSubviews {
    [self adjustTileDictionary];
    [CATransaction begin]; {
        // layoutSubviews only gets called on a resize, when I will be
        // shuffling layers all over the place.  I don't want to animate
        // the layers to their new positions.
        [CATransaction setDisableActions:YES];
        [self layoutTileLayers];
    } [CATransaction commit];
    for (NSNumber *key in _tileLayers) {
        [self queueTileForRedraw:key.integerValue];
    }
}

Adjusting the tile dictionary means setting up a layer for each visible tile and removing layers for non-visible tiles. We'll just reset the dictionary from scratch each time, but we'll try to reuse the layer's we've already created. The tiles that need layers are the newest tile, and preceding tiles so we have enough layers to cover the view.

- (void)adjustTileDictionary {
    NSInteger newestTile = tileForSampleIndex(_totalSampleCount - 1);
    // Add 1 to account for layers hanging off the left and right edges.
    NSInteger tileLayersNeeded = 1 + ceilf(self.bounds.size.width / kLayerWidth);
    NSInteger oldestTile = newestTile - tileLayersNeeded + 1;

    NSMutableArray *spareLayers = [[_tileLayers allValues] mutableCopy];
    [_tileLayers removeAllObjects];
    for (NSInteger tile = oldestTile; tile <= newestTile; ++tile) {
        CALayer *layer = [spareLayers lastObject];
        if (layer) {
            [spareLayers removeLastObject];
        } else {
            layer = [self newTileLayer];
        }
        [_tileLayers setObject:layer forKey:[NSNumber numberWithInteger:tile]];
    }

    for (CALayer *layer in spareLayers) {
        [layer removeFromSuperlayer];
    }
}

The first time through, and any time the view gets sufficiently wider, we need to create new layers. While we're creating the view, we'll tell it to avoid animating its contents or position. Otherwise it will animate them by default.

- (CALayer *)newTileLayer {
    CALayer *layer = [CALayer layer];
    layer.backgroundColor = [UIColor greenColor].CGColor;
    layer.actions = [NSDictionary dictionaryWithObjectsAndKeys:
        [NSNull null], @"contents",
        [NSNull null], @"position",
        nil];
    [self.layer addSublayer:layer];
    return layer;
}

Actually laying out the tile layers is just a matter of setting each layer's frame:

- (void)layoutTileLayers {
    [_tileLayers enumerateKeysAndObjectsUsingBlock:^(id key, id obj, BOOL *stop) {
        CALayer *layer = obj;
        layer.frame = [self frameForTile:[key integerValue]];
    }];
}

Of course the trick is computing the frame for each layer. And the y, width, and height parts are easy enough:

- (CGRect)frameForTile:(NSInteger)tile {
    CGRect myBounds = self.bounds;
    CGFloat x = [self xForTile:tile myBounds:myBounds];
    return CGRectMake(x, myBounds.origin.y, kLayerWidth, myBounds.size.height);
}

To compute the x coordinate of the tile's frame, we compute the x coordinate of the first sample in the tile:

- (CGFloat)xForTile:(NSInteger)tile myBounds:(CGRect)myBounds {
    return [self xForSampleAtIndex:tile * kSamplesPerTile myBounds:myBounds];
}

Computing the x coordinate for a sample requires a little thought. We want the newest sample to be at the right edge of the view, and the second-newest to be kPointsPerSample points to the left of that, and so on:

- (CGFloat)xForSampleAtIndex:(NSInteger)index myBounds:(CGRect)myBounds {
    return myBounds.origin.x + myBounds.size.width - kPointsPerSample * (_totalSampleCount - index);
}

Redrawing

Now we can talk about how to actually draw tiles. We're going to do the drawing on a separate GCD queue. We can't safely access most Cocoa Touch objects from two threads simultaneously, so we need to be careful here. We'll use a prefix of rq_ on all the methods that run on _redrawQueue to remind ourselves that we're not on the main thread.

To redraw one tile, we need to get the tile number, the graphical bounds of the tile, and the points to draw. All of those things come from data structures that we might be modifying on the main thread, so we need to access them only on the main thread. So we dispatch back to the main queue:

- (void)rq_redrawOneTile {
    __block NSInteger tile;
    __block CGRect bounds;
    CGPoint pointStorage[kSamplesPerTile + kPaddingSamples * 2];
    CGPoint *points = pointStorage; // A block cannot reference a local variable of array type, so I need a pointer.
    __block NSUInteger pointCount;
    dispatch_sync(dispatch_get_main_queue(), ^{
        tile = [self dequeueTileToRedrawReturningBounds:&bounds points:points pointCount:&pointCount];
    });

It so happens that we might not have any tiles to redraw. If you look back at queueTilesForRedrawIfAffectedByLastSample, you'll see that it usually tries to queue the same tile twice. Since _tilesToRedraw is a set (not an array), the duplicate was discarded, but rq_redrawOneTile was dispatched twice anyway. So we need to check that we actually have a tile to redraw:

    if (tile == NSNotFound)
        return;

Now we need to actually draw the tile's samples:

    UIImage *image = [self rq_imageWithBounds:bounds points:points pointCount:pointCount];

Finally we need to update the tile's layer to show the new image. We can only touch a layer on the main thread:

    dispatch_async(dispatch_get_main_queue(), ^{
        [self setImage:image forTile:tile];
    });
}

Here's how we actually draw the image for the layer. I will assume you know enough Core Graphics to follow this:

- (UIImage *)rq_imageWithBounds:(CGRect)bounds points:(CGPoint *)points pointCount:(NSUInteger)pointCount {
    UIGraphicsBeginImageContextWithOptions(bounds.size, YES, 0); {
        CGContextRef gc = UIGraphicsGetCurrentContext();
        CGContextTranslateCTM(gc, -bounds.origin.x, -bounds.origin.y);

        [[UIColor orangeColor] setFill];
        CGContextFillRect(gc, bounds);

        [[UIColor whiteColor] setStroke];
        CGContextSetLineWidth(gc, 1.0);
        CGContextSetLineJoin(gc, kCGLineCapRound);
        CGContextBeginPath(gc);
        CGContextAddLines(gc, points, pointCount);
        CGContextStrokePath(gc);
    }
    UIImage *image = UIGraphicsGetImageFromCurrentImageContext();
    UIGraphicsEndImageContext();
    return image;
}

But we still have to get the tile, the graphics bounds, and the points to draw. We dispatched back to the main thread to do it:

// I return NSNotFound if I couldn't dequeue a tile.
// The `pointsOut` array must have room for at least
// kSamplesPerTile + 2*kPaddingSamples elements.
- (NSInteger)dequeueTileToRedrawReturningBounds:(CGRect *)boundsOut points:(CGPoint *)pointsOut pointCount:(NSUInteger *)pointCountOut {
    NSInteger tile = [self dequeueTileToRedraw];
    if (tile == NSNotFound)
        return NSNotFound;

The graphics bounds are just the bounds of the tile, just like we computed earlier to set the frame of the layer:

    *boundsOut = [self frameForTile:tile];

I need to start graphing from the padding samples before the first sample of the tile. But, prior to having enough samples to fill the view, my tile number may actually be negative! So I need to be sure not to try to access a sample at a negative index:

    NSInteger sampleIndex = MAX(0, tile * kSamplesPerTile - kPaddingSamples);

We also need to make sure we don't try to run past the end of the samples when we compute the sample at which we stop graphing:

    NSInteger endSampleIndex = MIN(_totalSampleCount, tile * kSamplesPerTile + kSamplesPerTile + kPaddingSamples);

And when I actually access the sample values, I need to account for the samples I've discarded:

    NSInteger discardedSampleCount = _totalSampleCount - _samples.count;

Now we can compute the actual points to graph:

    CGFloat x = [self xForSampleAtIndex:sampleIndex myBounds:self.bounds];
    NSUInteger count = 0;
    for ( ; sampleIndex < endSampleIndex; ++sampleIndex, ++count, x += kPointsPerSample) {
        pointsOut[count] = CGPointMake(x, [[_samples objectAtIndex:sampleIndex - discardedSampleCount] floatValue]);
    }

And I can return the number of points and the tile:

    *pointCountOut = count;
    return tile;
}

Here's how we actually pull a tile off the redraw queue. Remember that the queue might be empty:

- (NSInteger)dequeueTileToRedraw {
    NSNumber *number = [_tilesToRedraw anyObject];
    if (number) {
        [_tilesToRedraw removeObject:number];
        return number.integerValue;
    } else {
        return NSNotFound;
    }
}

And finally, here's how we actually set the tile layer's contents to the new image. Remember that we dispatched back to the main queue to do this:

- (void)setImage:(UIImage *)image forTile:(NSInteger)tile {
    CALayer *layer = [_tileLayers objectForKey:[NSNumber numberWithInteger:tile]];
    if (layer) {
        layer.contents = (__bridge id)image.CGImage;
    }
}

Making it sexier

If you do all of that, it will work fine. But you can actually make it slightly nicer-looking by animating the repositioning of the layers when a new sample comes in. This is very easy. We just modify newTileLayer so that it adds an animation for the position property:

- (CALayer *)newTileLayer {
    CALayer *layer = [CALayer layer];
    layer.backgroundColor = [UIColor greenColor].CGColor;
    layer.actions = [NSDictionary dictionaryWithObjectsAndKeys:
        [NSNull null], @"contents",
        [self newTileLayerPositionAnimation], @"position",
        nil];
    [self.layer addSublayer:layer];
    return layer;
}

and we create the animation like this:

- (CAAnimation *)newTileLayerPositionAnimation {
    CABasicAnimation *animation = [CABasicAnimation animationWithKeyPath:@"position"];
    animation.duration = 0.1;
    animation.timingFunction = [CAMediaTimingFunction functionWithName:kCAMediaTimingFunctionLinear];
    return animation;
}

You will want to set the duration to match the speed at which new samples arrive.