Speed up search using dispatch_async?

Question

I'm trying to speed up my app search , it get lags when there is a lot of data.

so i'm trying to split search Predicate on UI by using dispatch_async not dispatch_sync cause no different if I use it.

The problem is when i use dispatch_async, the app crash sometimes because [__NSArrayI objectAtIndex:]: index "17" beyond bounds.

I now this happened because lets say the first one still work and reload the tableView and continue search will change the array size depend on result so in this case "CRASH" :(

this is my code:

    dispatch_async(myQueue, ^{
        searchArray = [PublicMeathods searchInArray:searchText array:allData];
    } );

    if(currentViewStyle==listViewStyle){
        [mytable reloadData];
    }

and i've tried this :

    dispatch_async(myQueue, ^{
        NSArray *tmpArray = [PublicMeathods searchInArray:searchText array:allData];
        dispatch_sync(dispatch_get_main_queue(), ^{
            searchArray = tmpArray;
            [mytable reloadData];
        });
    });

but in this case the lags still there.

Update -1- :

The search Predicate takes just 2ms :) after hard work :) but the keyboard still lags when the user searches, so the only thing I do after get result is reload table "change in UI" this what I think make it lags,

So what I search for split this two operation "typing on keyboard & refresh UI".

Update -2- :

@matehat https://stackoverflow.com/a/16879900/1658442

and

@TomSwift https://stackoverflow.com/a/16866049/1658442

answers work like a charm :)

Answer 1

If searchArray is the array that is used as table view data source then this array must only be accessed and modified on the main thread.

Therefore, on the background thread, you should filter into a separate temporary array first. Then you assign the temporary array to searchArray on the main thread:

dispatch_async(myQueue, ^{
    NSArray *tmpArray = [PublicMeathods searchInArray:searchText array:allData];
    dispatch_sync(dispatch_get_main_queue(), ^{
        searchArray = tmpArray;
        [mytable reloadData];
    });
});

Update: Using a temporary array should solve the crash problem, and using a background thread helps to keep the UI responsive during the search. But as it turned out in the discussion, a major reason for the slow search might be the complicated search logic.

It might help to store additional "normalized" data (e.g. all converted to lower-case, phone numbers converted to a standard form, etc ...) so that the actual search can be done with faster case-insensitive comparisons.

Answer 2

One solution might be to voluntarily induce a delay between searches to let the user type and let the search be performed asynchronously. Here's how:

First make sure your queue is created like this :

dispatch_queue_t myQueue = dispatch_queue_create("com.queue.my", DISPATCH_QUEUE_CONCURRENT);

Have this ivar defined in your class (and set it to FALSE upon initialization):

BOOL _scheduledSearch;

Write down this macro at the top of your file (or anywhere really, just make sure its visible)

#define SEARCH_DELAY_IN_MS 100

And instead of your second snippet, call this method:

[self scheduleSearch];

Whose implementation is:

- (void) scheduleSearch {
    if (_scheduledSearch) return;
    _scheduledSearch = YES;
    dispatch_time_t popTime = dispatch_time(DISPATCH_TIME_NOW, (int64_t)((double)SEARCH_DELAY_IN_MS * NSEC_PER_MSEC));
    dispatch_after(popTime, myQueue, ^(void){
        _scheduledSearch = NO;
        NSString *searchText = [self textToSearchFor];
        NSArray *tmpArray = [PublicMeathods searchInArray:searchText array:allData];
        dispatch_async(dispatch_get_main_queue(), ^{
            searchArray = tmpArray;
            [mytable reloadData];
        });
        if (![[self textToSearchFor] isEqualToString:searchText])
            [self scheduleSearch];
    });
}

[self textToSearchFor] is where you should get the actual search text from.

Here's what it does :

• The first time a request comes in, it sets the _scheduledSearch ivar to TRUE and tells GCD to schedule a search in 100 ms
• Meanwhile any new search requests is not taken care of, because a search is going to happen anyway in a few ms
• When the scheduled search happens, the _scheduledSearch ivar is reset to FALSE, so the next request is handled.

You can play with different values for SEARCH_DELAY_IN_MS to make it suit your needs. This solution should completely decouple keyboard events with workload generated from the search.

Answer 3

First, a couple notes on the code you presented:

1) It looks as if you're likely queuing up multiple searches as the user types, and these all have to run to completion before the relevant one (the most recent one) updates the display with the desired result set.

2) The second snippet you show is the correct pattern in terms of thread safety. The first snippet updates the UI before the search completes. Likely your crash happens with the first snippet because the background thread is updating the searchArray when the main thread is reading from it, meaning that your datasource (backed by searchArray) is in an inconsistent state.

You don't say if you're using a UISearchDisplayController or not, and it really doesn't matter. But if you are, one common issue is not implementing - (BOOL) searchDisplayController: (UISearchDisplayController *) controller shouldReloadTableForSearchString: (NSString *) filter and returning NO. By implementing this method and returning NO you are turning off the default behavior of reloading the tableView with each change to the search term. Instead you have opportunity to kick off your asynchronous search for the new term, and update the UI ([tableview reloadData]) only once you have new results.

Regardless of whether you're using UISearchDisplayController you need to take a few things into consideration when implementing your asynchronous search:

1) Ideally you can interrupt a search-in-progress and cancel it if the search is no longer useful (e.g. the search term changed). Your 'searchInArray' method doesn't appear to support this. But it's easy to do if your just scanning an array.

1a) If you can't cancel your search, you still need a way at the end of the search to see if your results are relevant or not. If not, then don't update the UI.

2) The search should run on a background thread as to not bog down the main thread and UI.

3) Once the search completes it needs to update the UI (and the UI's datasource) on the main thread.

I put together sample project (here, on Github) that performs a pretty inefficient search against a large list of words. The UI remains responsive as the user types in their term, and the spawned searches cancel themselves as they become irrelevant. The meat of the sample is this code:

- (BOOL) searchDisplayController: (UISearchDisplayController *) controller
shouldReloadTableForSearchString: (NSString *) filter
{
    // we'll key off the _currentFilter to know if the search should proceed
    @synchronized (self)
    {
        _currentFilter = [filter copy];
    }

    dispatch_async( _workQueue, ^{

        NSDate* start = [NSDate date];

        // quit before we even begin?
        if ( ![self isCurrentFilter: filter] )
            return;

        // we're going to search, so show the indicator (may already be showing)
        [_activityIndicatorView performSelectorOnMainThread: @selector( startAnimating )
                                                 withObject: nil
                                              waitUntilDone: NO];

        NSMutableArray* filteredWords = [NSMutableArray arrayWithCapacity: _allWords.count];

        // only using a NSPredicate here because of the SO question...
        NSPredicate* p = [NSPredicate predicateWithFormat: @"SELF CONTAINS[cd] %@", filter];

        // this is a slow search... scan every word using the predicate!
        [_allWords enumerateObjectsUsingBlock: ^(id obj, NSUInteger idx, BOOL *stop) {

            // check if we need to bail every so often:
            if ( idx % 100 == 0 )
            {
                *stop = ![self isCurrentFilter: filter];
                if (*stop)
                {
                    NSTimeInterval ti = [start timeIntervalSinceNow];
                    NSLog( @"interrupted search after %.4lf seconds", -ti);
                    return;
                }
            }

            // check for a match
            if ( [p evaluateWithObject: obj] )
            {
                [filteredWords addObject: obj];
            }
        }];

        // all done - if we're still current then update the UI
        if ( [self isCurrentFilter: filter] )
        {
            NSTimeInterval ti = [start timeIntervalSinceNow];
            NSLog( @"completed search in %.4lf seconds.", -ti);

            dispatch_sync( dispatch_get_main_queue(), ^{

                _filteredWords = filteredWords;
                [controller.searchResultsTableView reloadData];
                [_activityIndicatorView stopAnimating];
            });
        }
    });

    return FALSE;
}

- (BOOL) isCurrentFilter: (NSString*) filter
{
    @synchronized (self)
    {
        // are we current at this point?
        BOOL current = [_currentFilter isEqualToString: filter];
        return current;
    }
}

Answer 4

i believe your crash is indeed solved by the embedding of the display of the UI element for which searchArray is the backing element in a call to GrandCentralDispatch inside of the other call (as you show in your updated original post). that is the only way to make sure you are not causing the elements of the array to change behind the scenes while the display of the items associated with it is taking place.

however, i believe if you are seeing lag, it is not so much caused by the processing of the array at 2ms or the reload that takes 30ms, but rather by the time it takes GCD to get to the internal dispatch_sync call on the main queue.

if, by this point, you have managed to get the processing of your array down to only 2ms in the worst case (or even if you've managed to get it down to less than 30ms, which is about the time it takes to process a frame in the main run loop at 30 fps), then you should consider abandoning GCD altogether in your effort to process this array. taking 2ms on the main queue to process your array is not going to cause any buggy behavior.

you may have lag elsewhere (i.e. if you are incrementing search results by trying to go out to the net to get the results, you may want to do the call and then process the response on your separate dispatch queue), but for the times you are talking about, this bit of processing doesn't need to be split out onto separate queues. for any hard-core processing that takes over 30ms, you should consider GCD.