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

I suspect your problem is that allData is shared between the main queue and the background queue. If you make a change in allData on the main queue, that may shorten allData in the background queue, causing an index that used to be valid to become invalid.

It's also possible that the problem is not allData itself, but some array within the objects in allData. Try setting a breakpoint on exceptions (in Xcode, open the Breakpoints source list, click the plus button at the bottom, and choose "Add Exception Breakpoint...") so you can see exactly where the error occurs.

In either case, you have two possible solutions:

1. Copy the offending object before using it in the search. This protects the background queue from changes in the main queue, but depending on what you need to copy, it may be difficult to get the changes back into the UI—you might have to match the copies back to their originals.

2. Use a lock (like @synchronized) or a per-object queue to ensure only one queue is using the object at a time. NSManagedObjectContext uses the latter approach for its -performBlock: and -performBlockAndWait: methods. It may be a little tricky to do this without blocking the main queue, though.

Answer 2

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

Martin R has posted a correct answer. The only thing to point out that instead of

dispatch_sync(dispatch_get_main_queue()

it should be

dispatch_async(dispatch_get_main_queue()

The complete code in Swift would be:

        let remindersFetcherQueue = dispatch_queue_create("com.gmail.hillprincesoftware.remindersplus", DISPATCH_QUEUE_CONCURRENT)
        dispatch_sync(remindersFetcherQueue) {
            println("Start background queue")

            estore.fetchRemindersMatchingPredicate(remindersPredicate) {
                reminders in
                    // var list = ... Do something here with the fetched reminders.
                    dispatch_async(dispatch_get_main_queue()) {
                        self.list = list   // Assign to a class property
                        self.sendChangedNotification()      // This should send a notification which calls a function to ultimately call setupUI() in your view controller to do all the UI displaying and tableView.reloadData(). 
                    }                        
            }
        }

Answer 5

Try to modify your functions the next way:

function prototype;

- (void)searchInArray:searchText array:allData complete: (void (^)(NSArray *arr)) complete;

function itself

- (void)searchInArray:searchText array:allData complete: (void (^)(NSArray *arr)) complete { 
    NSArray * array = [NSArray new];
    // function code
    complete(array)//alarming that we have done our stuff
}

and when you are calling this function

dispatch_queue_t searchQueue = dispatch_queue_create("com.search",NULL);
dispatch_async(searchQueue,^{
 [PublicMeathods searchInArray:searchText array:allData complete:^(NSArray *arr) {
     searchArray = arr;
     dispatch_async(dispatch_get_main_queue(), ^{
         [myTable reloadData];
     });
 }];
});

Hope it will help you)

Answer 6

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.