504876 - Optimize autocomplete matching for the common case

Status: RESOLVED FIXED

(Camino Graveyard :: Location Bar & Autocomplete, defect)

Description

[Stuart Morgan]

As discussed in the earlier bug and on IRC, we can make autocomplete faster by taking advantage of the fact that it's almost always the case that changes to the search string are adding characters at the end, so anything that didn't match before still won't.

My thought was an index set of everything that matched, and the last index examined, but if something better occurs to you I'm not married to that approach.

Comment 1

[Dan Weber]

Attachment: Patch 1

First attempt. Things are bit more complicated now, but it seems to be faster (although I haven't done any tests). I took up your suggestion of using an index set to keep track of previous matches. If the old search string is a substring of the new string, we check if all of the old matches still hold up. Then we continue searching from the last match (I suppose this should be the last index checked because these could be different).

Comment 2

[Stuart Morgan]

Comment on attachment 389375 [details] [diff] [review]
Patch 1

> (I suppose this should be the last index checked because
> these could be different).

Yes, we definitely want to store the index despite it being more variables to manage. The obvious case where that's important is when the user is typing a string that doesn't match anything; without storing the last checked index it'll do a complete search for each new character instead of doing no incremental work.

Since the variable list is mostly two parallel lists of grouped variables, I think this would benefit from a new class to hold the collection of related variables for each source (i.e., adding a new source should add one variable to your autocomplete class, not 5 or 6). Even if it's a dumb data-holder, it should still make the code cleaner, and should help with the argument lists to you processing function. But I suspect you'll find that there are methods that will naturally belong to this new object instead (the method to process the next chunk for one of the sources, for example).


>+  NSRange                 mBookmarkChunkRange;
>+  NSRange                 mHistoryChunkRange;

There's actually no reason for these to be ranges, since the length value is always the same constant. You can just store the start index instead, and pass that around, letting the chunk-processing function make a range.

>+  NSString*               mSearchString;                // owned

Should be called mPreviousSearchString, to eliminate potential confusion.

>+// Removes matches for the previous search string that don't match the
>+// current string.
>+- (void)updateSearchResults:(NSMutableArray *)results fromData:(NSArray *)data matches:(NSIndexSet *)indexes;

The name, and especially the comment, are misleading here, since it sounds like it's trimming things out of |results|, when in fact |results is empty and being re-populated. How about something like:
- (void)reprocessMatches:(NSIndexSet*)indexes fromData:(NSArray*)dataArray forResults:(NSMutableArray*)resultsArray
That seems clearer, and has a name paralleling the very similar chunk-processing method.

> // Iterates though a chunk of the data array and looks for matches to the
> // search string. When a match is found, it is added to the results array.
>-- (void)processChunkOfData:(NSArray *)dataArray forResults:(NSMutableArray *)resultsArray;
>+- (void)processChunkRange:(NSRange)range ofData:(NSArray *)data results:(NSMutableArray *)results matches:(NSMutableIndexSet *)indexes;

Comment needs an update to explain about |matches|. I'd keep the "for" in "forResults", since it makes the role of the array clearer.

Also, break this into for :-aligned lines since it's so long.

>+    [self updateSearchResults:mBookmarkResultsInProgress fromData:mBookmarkData matches:mMatchedBookmarkIndexes];
>+    [self updateSearchResults:mHistoryResultsInProgress fromData:mHistoryData matches:mMatchedHistoryIndexes];
>+    mBookmarkChunkRange = NSMakeRange([mMatchedBookmarkIndexes lastIndex], kNumberOfItemsPerChunk);
>+    mHistoryChunkRange = NSMakeRange([mMatchedHistoryIndexes lastIndex], kNumberOfItemsPerChunk);

Pull this whole block into a named method, to parallel processNextSearchChunk.

>+    if (!mMatchedBookmarkIndexes)
>+      mMatchedBookmarkIndexes = [[NSMutableIndexSet alloc] init];
>...
>+    if (!mMatchedHistoryIndexes)
>+      mMatchedHistoryIndexes = [[NSMutableIndexSet alloc] init];

Create these in the init; lazy creation doesn't buy us anything since they'll be needed as soon as there's a search, and it makes the code here less clear.

Comment 3

[Dan Weber]

Attachment: Patch 2

Comment 4

[Smokey Ardisson (offline for a while; not following bugs - do not email)]

This patch makes a world of difference in bug 506345 for me (10 MB/10 days).

Comment 5

[Smokey Ardisson (offline for a while; not following bugs - do not email)]

(In reply to comment #4)
> This patch makes a world of difference in bug 506345 for me (10 MB/10 days).

Belay that; apparently Gecko removed 7MB and at least 5K items from my history between the first time I tested and testing with this patch :-(  So the patch doesn't help noticeably.

Comment 6

[Stuart Morgan]

Comment on attachment 390375 [details] [diff] [review]
Patch 2

>+- (void)resetSearch;
>...
>+- (void)processNextSearchChunk;
>...
>+- (void)reportResults;

Why are these being made public?

>+- (BOOL)searchStringMatchesItem:(id)item;
>...
>+- (AutoCompleteResult *)autoCompleteResultForItem:(id)item;

Are these used by anything but AutoCompleteData? If not, they should be private methods of that class.

>+//
>+// This class stores data associated with an autocomplete data type
>+// (bookmarks and history items). It also includes methods to aid
>+// during the autocomplete search.
>+//
>+@interface AutoCompleteData : NSObject

Move this to its own file. It could also use a more descriptive name; it's really more about the in-progress search than the data itself, so maybe AutoCompleteSearchData?

>+  AutoCompleteDataSource* mDataSource;

Since this is just used to call methods that can probably move into this class, it can likely be removed.

>+  unsigned int            mChunkLocation;
>+  unsigned int            mLastIndex;

Are these actually separate concepts needing separate variables? It seems like both are just "the last index we looked at" (modulo an off-by-one), just at different times (search is in progress vs. current search is complete).

>+// Returns an item from the data array at the specified index.
>+- (id)dataItemAtIndex:(unsigned int)index;

This appears to be unused.

>+// Adds an item to the results array.
>+- (void)addResult:(AutoCompleteResult *)result;

This too.

>+- (void)clearResults;
>...
>+- (void)resetChunkLocation;

These should probably be one combined reset method, since that's the only way they are used.

>+- (void)incrementChunkLocation;
>...
>+- (void)processNextSearchChunk;

This is exposing too much internal state; it should just be one method to process the next chunk. It would also be good to have it take number of items to process, so this class is completely divorced from the decision of how much a chunk should entail.

>+- (void)clearMatchedIndexes;

Should be named in a way that reflects what behavior the client wants, rather than the implementation--or be made private. It would probably help to have this class receive the search string, so that it can make an internet determination about how to proceed. Whether it starts over or not would then be an internal detail that the driver class needn't worry about.

>+- (void)reprocessSearchResults;

This would then become private too.

>+// Returns YES if there are enough items in the results array to satisfy
>+// kMaxResultsPerHeading or if we have iterated through the entire data
>+// array; otherwise, returns NO.
>+- (BOOL)isSearchDone;

You probably want this count to be passed in too, so that the constant is just something that the driver class knows about.

>+// Adds the specified header the results array.
>+- (void)addHeader:(NSString *)header;

This seems like it belongs in the driver class, since it's not search-related.

>+  //NSLog(@"!!!!! %@", mURLToResultDict);

Remove

>+- (void)sortData
>+{
>+  NSSortDescriptor *visitCountDescriptor = [[[NSSortDescriptor alloc] initWithKey:@"numberOfVisits"
>+                                                                        ascending:NO] autorelease];
>+  [mData sortUsingDescriptors:[NSArray arrayWithObject:visitCountDescriptor]];
>+}

I'm not sure the sort should be hard-coded into this class. Perhaps the setter for data should be a whole array, rather than individual items, and the data should come in pre-sorted the way the driver wants.

>+  mPreviousSearchString = [searchString retain];

Copy, rather than retain.

Comment 7

[Stuart Morgan]

Comment on attachment 390375 [details] [diff] [review]
Patch 2

>+  [mAutoCompleteBookmarkData processNextSearchChunk];
>+  if ([mAutoCompleteBookmarkData isSearchDone])
>+    [mAutoCompleteHistoryData processNextSearchChunk];

Oh, one more thing: This needs to be |if (!bookmark search done) { do bookmark search } else { do history search }|, otherwise you'll blow past your chunk limit for one iteration.

Comment 8

[Stuart Morgan]

Comment on attachment 390375 [details] [diff] [review]
Patch 2

Marking as obsolete since this will need to be completely rewritten for the new implementation of autocomplete.

It would still be useful to do this optimization, especially for the "no matches" case, but hopefully the trie is fast enough in general that it won't really be an issue.

Comment 9

[Stuart Morgan]

Attachment: Fix, rewritten

Rewritten for the new autocomplete backend. While this is a largish patch, it's mostly refactoring as opposed to totally new code.

This doesn't optimize every possible case since the benefit-to-complexity ratio falls off pretty quickly; I only handle the case where the user keeps adding characters to the end of the query. People typing multi-word queries and then adding characters to the first word later are out of luck ;)

I did this primarily so that I can do efficient incremental growing of queries (i.e., run a search with a limit of n, then decide I want n+1 and not have to start from scratch) to support my plans for combining history and bookmark results in one list, but it won't hurt to make things faster for people with lots of history and/or bookmarks and a slower machine :)

Comment 10

[Stuart Morgan]

Attachment: fix, v2

This adds a missing dealloc I noticed when reviewing the patch, and also a leak I added earlier that I found while running 'leaks' to check for any other similar mistakes.

Per discussion I'll be landing this now, but I'd appreciate it if you could do a post-landing review when you get a chance.

Comment 11

[Stuart Morgan]

Landed as http://hg.mozilla.org/camino/rev/55751a3bab37