Last In-First Out Stack with GCD?

Question

I have a UITableView that displays images associated with contacts in each row. In some cases these images are read on first display from the address book contact image, and where there isn't one they are an avatar rendered based on stored data. I presently have these images being updated on a background thread using GCD. However, this loads the images in the order they were requested, which means during rapid scrolling the queue becomes lengthy and when the user stops scrolling the current cells are the last to get updated. On the iPhone 4, the problem isn't really noticeable, but I am keen to support older hardware and am testing on an iPhone 3G. The delay is tolerable but quite noticeable.

It strikes me that a Last In-First Out stack would seem likely to largely resolve this issue, as whenever the user stopped scrolling those cells would be the next to be updated and then the others that are currently off-screen would be updated. Is such a thing possible with Grand Central Dispatch? Or not too onerous to implement some other way?

Note, by the way, that I am using Core Data with a SQLite store and I am not using an NSFetchedResultsController because of a many-to-many relationship that has to be traversed in order to load the data for this view. (As far as I am aware, that precludes using an NSFetchedResultsController.) [I've discovered an NSFetchedResultsController can be used with many-to-many relationships, despite what the official documentation appears to say. But I'm not using one in this context, yet.]

Addition: Just to note that while the topic is "How do I create a Last In-First Out Stack with GCD", in reality I just want to solve the issue outlined above and there may be a better way to do it. I am more than open to suggestions like timthetoolman's one that solves the problem outlined in another way; if such a suggestion is finally what I use I'll recognize both the best answer to the original question as well as the best solution I ended up implementing... :)

Answer 1

Because of the memory constraints of the device, you should load the images on demand and on a background GCD queue. In the cellForRowAtIndexPath: method check to see if your contact's image is nil or has been cached. If the image is nil or not in cache, use a nested dispatch_async to load the image from the database and update the tableView cell.

- (UITableViewCell *)tableView:(UITableView *)tableView cellForRowAtIndexPath:(NSIndexPath*)indexPath
   {
       static NSString *CellIdentifier = @"Cell";
       UITableViewCell *cell = [tableView dequeueReusableCellWithIdentifier:CellIdentifier];
       if (cell == nil) {
            cell = [[UITableViewCell alloc] initWithStyle:UITableViewCellStyleDefault reuseIdentifier:CellIdentifier];
       }
       // If the contact object's image has not been loaded, 
       // Use a place holder image, then use dispatch_async on a background queue to retrieve it.

       if (contact.image!=nil){
           [[cell imageView] setImage: contact.image];
       }else{
           // Set a temporary placeholder
           [[cell imageView] setImage:  placeHolderImage];

           // Retrieve the image from the database on a background queue
           dispatch_queue_t queue = dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_HIGH, 0);
           dispatch_async(queue, ^{
               UIImage *image = // render image;
               contact.image=image;

               // use an index path to get at the cell we want to use because
               // the original may be reused by the OS.
               UITableViewCell *theCell=[tableView cellForRowAtIndexPath:indexPath];

               // check to see if the cell is visible
               if ([tableView visibleCells] containsObject: theCell]){
                  // put the image into the cell's imageView on the main queue
                  dispatch_async(dispatch_get_main_queue(), ^{
                     [[theCell imageView] setImage:contact.image];
                     [theCell setNeedsLayout];
                  });
               }
           }); 
       }
       return cell;
}

The WWDC2010 conference video "Introducing Blocks and Grand Central Dispatch" shows an example using the nested dispatch_async as well.

another potential optimization could be to start downloading the images on a low priority background queue when the app launches. i.e.

 // in the ApplicationDidFinishLaunchingWithOptions method
 // dispatch in on the main queue to get it working as soon
 // as the main queue comes "online".  A trick mentioned by
 // Apple at WWDC

 dispatch_async(dispatch_get_main_queue(), ^{
        // dispatch to background priority queue as soon as we
        // get onto the main queue so as not to block the main
        // queue and therefore the UI
        dispatch_queue_t lowPriorityQueue = dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_BACKGROUND, 0)
        dispatch_apply(contactsCount,lowPriorityQueue ,^(size_t idx){
               // skip the first 25 because they will be called
               // almost immediately by the tableView
               if (idx>24){
                  UIImage *renderedImage =/// render image
                  [[contactsArray objectAtIndex: idx] setImage: renderedImage];
               }

        });
 });

With this nested dispatch, we are rendering the images on an extremely low priority queue. Putting the image rendering on the background priority queue will allow the images being rendered from the cellForRowAtIndexPath method above to be rendered at a higher priority. So, because of the difference in priorities of the queues, you will have a "poor mans" LIFO.

Good luck.

Answer 2

The code below creates a flexible last in-first out stack that is processed in the background using Grand Central Dispatch. The SYNStackController class is generic and reusable but this example also provides the code for the use case identified in the question, rendering table cell images asynchronously, and ensuring that when rapid scrolling stops, the currently displayed cells are the next to be updated.

Kudos to Ben M. whose answer to this question provided the initial code on which this was based. (His answer also provides code you can use to test the stack.) The implementation provided here does not require ARC, and uses solely Grand Central Dispatch rather than performSelectorInBackground. The code below also stores a reference to the current cell using objc_setAssociatedObject that will enable the rendered image to be associated with the correct cell, when the image is subsequently loaded asynchronously. Without this code, images rendered for previous contacts will incorrectly be inserted into reused cells even though they are now displaying a different contact.

I've awarded the bounty to Ben M. but am marking this as the accepted answer as this code is more fully worked through.

SYNStackController.h

//
//  SYNStackController.h
//  Last-in-first-out stack controller class.
//

@interface SYNStackController : NSObject {
    NSMutableArray *stack;
}

- (void) addBlock:(void (^)())block;
- (void) startNextBlock;
+ (void) performBlock:(void (^)())block;

@end

SYNStackController.m

//
//  SYNStackController.m
//  Last-in-first-out stack controller class.
//

#import "SYNStackController.h"

@implementation SYNStackController

- (id)init
{
    self = [super init];

    if (self != nil) 
    {
        stack = [[NSMutableArray alloc] init];
    }

    return self;
}

- (void)addBlock:(void (^)())block
{
    @synchronized(stack)
    {
        [stack addObject:[[block copy] autorelease]];
    }

    if (stack.count == 1) 
    {
        // If the stack was empty before this block was added, processing has ceased, so start processing.
        dispatch_queue_t queue = dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_HIGH, 0ul);
        dispatch_async(queue, ^{
            [self startNextBlock];
        });
    }
}

- (void)startNextBlock
{
    if (stack.count > 0)
    {
        @synchronized(stack)
        {
            id blockToPerform = [stack lastObject];
            dispatch_queue_t queue = dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_HIGH, 0ul);
            dispatch_async(queue, ^{
                [SYNStackController performBlock:[[blockToPerform copy] autorelease]];
            });

            [stack removeObject:blockToPerform];
        }

        [self startNextBlock];
    }
}

+ (void)performBlock:(void (^)())block
{
    @autoreleasepool {
        block();
    }
}

- (void)dealloc {
    [stack release];
    [super dealloc];
}

@end

In the view.h, before @interface:

@class SYNStackController;

In the view.h @interface section:

SYNStackController *stackController;

In the view.h, after the @interface section:

@property (nonatomic, retain) SYNStackController *stackController;

In the view.m, before @implementation:

#import "SYNStackController.h"

In the view.m viewDidLoad:

// Initialise Stack Controller.
self.stackController = [[[SYNStackController alloc] init] autorelease];

In the view.m:

- (UITableViewCell *)tableView:(UITableView *)tableView cellForRowAtIndexPath:(NSIndexPath *)indexPath {
    // Set up the cell.
    static NSString *CellIdentifier = @"Cell";

    UITableViewCell *cell = [tableView dequeueReusableCellWithIdentifier:CellIdentifier];
    if (cell == nil) {
        cell = [[UITableViewCell alloc] initWithStyle:UITableViewCellStyleDefault reuseIdentifier:CellIdentifier];
    }
    else 
    {
        // If an existing cell is being reused, reset the image to the default until it is populated.
        // Without this code, previous images are displayed against the new people during rapid scrolling.
        [cell setImage:[UIImage imageNamed:@"DefaultPicture.jpg"]];
    }

    // Set up other aspects of the cell content.
    ...

    // Store a reference to the current cell that will enable the image to be associated with the correct
    // cell, when the image subsequently loaded asynchronously. 
    objc_setAssociatedObject(cell,
                             personIndexPathAssociationKey,
                             indexPath,
                             OBJC_ASSOCIATION_RETAIN);

    // Queue a block that obtains/creates the image and then loads it into the cell.
    // The code block will be run asynchronously in a last-in-first-out queue, so that when
    // rapid scrolling finishes, the current cells being displayed will be the next to be updated.
    [self.stackController addBlock:^{
        UIImage *avatarImage = [self createAvatar]; // The code to achieve this is not implemented in this example.

        // The block will be processed on a background Grand Central Dispatch queue.
        // Therefore, ensure that this code that updates the UI will run on the main queue.
        dispatch_async(dispatch_get_main_queue(), ^{
            NSIndexPath *cellIndexPath = (NSIndexPath *)objc_getAssociatedObject(cell, personIndexPathAssociationKey);
            if ([indexPath isEqual:cellIndexPath]) {
            // Only set cell image if the cell currently being displayed is the one that actually required this image.
            // Prevents reused cells from receiving images back from rendering that were requested for that cell in a previous life.
                [cell setImage:avatarImage];
            }
        });
    }];

    return cell;
}