594223 - Don't call searchFunction unnecessarily in MatchAutoCompleteFunction::OnFunctionCall

Status: RESOLVED FIXED

(Toolkit :: Places, defect)

Description

[Justin Lebar (not reading bugmail)]

We search for the each token in the record's tags, title, and URL, even if we could have stopped after we saw it in the tags or after we saw it in the title.

Fixing this probably wouldn't yield a substantial perf win, since most of the time we *don't* find what we're looking for, so we have to search everywhere.  Still, it seems like we shouldn't leave this on the table.

Comment 1

[Justin Lebar (not reading bugmail)]

Attachment: Patch v1

Comment 2

[Shawn Wilsher :sdwilsh]

(In reply to comment #0)
> We search for the each token in the record's tags, title, and URL, even if we
> could have stopped after we saw it in the tags or after we saw it in the title.
Wouldn't it be easier to just change this line:
if (HAS_BEHAVIOR(TITLE) && !matches)
to:
if (HAS_BEHAVIOR(TITLE) && matches)
and then update the comment accordingly?

Comment 3

[Justin Lebar (not reading bugmail)]

(In reply to comment #2)
> Wouldn't it be easier to just change this line:
> if (HAS_BEHAVIOR(TITLE) && !matches)
> to:
> if (HAS_BEHAVIOR(TITLE) && matches)
> and then update the comment accordingly?

Well, then we wouldn't be able to short-circuit upon searchFunction(token, tags) returning true.

Comment 4

[Shawn Wilsher :sdwilsh]

(In reply to comment #3)
> Well, then we wouldn't be able to short-circuit upon searchFunction(token,
> tags) returning true.
but the common case is that it'd be false, right?

Comment 5

[Justin Lebar (not reading bugmail)]

(In reply to comment #4)
> but the common case is that it'd be false, right?

Yes, of course.  But by that logic, we could just WONTFIX and be done, right?

Maybe one way of looking at it is that the patch makes the intent of the code more clear, both to humans and to the compiler -- as a result, we get the added bonus of its running faster in some cases.

Comment 6

[Shawn Wilsher :sdwilsh]

(In reply to comment #5)
> Maybe one way of looking at it is that the patch makes the intent of the code
> more clear, both to humans and to the compiler -- as a result, we get the added
> bonus of its running faster in some cases.
I spent a good ten minutes on the train verifying that both code paths did the same thing because I didn't think either one was terribly clear.  Adding comments to yours may help in that regard though.

Comment 7

[Justin Lebar (not reading bugmail)]

Sure, I'll add a comment.

Comment 8

[Justin Lebar (not reading bugmail)]

Attachment: Patch v2

Added comment.

Comment 9

[Marco Bonardo [:mak]]

would make sense to search title before tags? not many pages have tags while all pages have titles, thus I'd expect that in most cases searchFunction(token, tags) is false and a useless call.

Comment 10

[Justin Lebar (not reading bugmail)]

I thought about this, but it's probably not a big deal, since searchFunction will immediately return return false when it notices that the search string is empty.

If we really wanted to optimize it, I'd try writing three loops rather than branching within the loop.  But I've never seen this function in a profile (except as a caller of hot functions), so I was trying to resist the urge to optimize it (except by reducing the number of hot functions it calls, of course). The functions are only hot when they actually iterate over some history data.

Anyway, I'd be happy to make the change, if only so the order reflects our expectations.

Comment 11

[Shawn Wilsher :sdwilsh]

(In reply to comment #10)
> Anyway, I'd be happy to make the change, if only so the order reflects our
> expectations.
Let's do that please.

Comment 12

[Shawn Wilsher :sdwilsh]

Comment on attachment 480365 [details] [diff] [review]
Patch v2

r=sdwilsh with comment 11 addressed

Comment 13

[Justin Lebar (not reading bugmail)]

Attachment: Patch v3

Addressing review comments.

Comment 14

[Benjamin Smedberg]

Comment on attachment 491702 [details] [diff] [review]
Patch v3

Please don't request approval without indicating the risks/rewards/testing associated with the patch. It's not clear to me whether we can test this performance optimization, or whether there are tests which already adequately cover this condition.

Comment 15

[Justin Lebar (not reading bugmail)]

sdwilsh, can you comment on the coverage of the testsuite with respect to this patch?

I don't expect this to have particularly large performance effects.  It's significant when you're searching for something which is common, such as the string "th" -- in this case, you get to skip many calls to searchFunction.  But if the search term is common, my understanding of the code is that you'll quickly find enough results to fill up the awesomebar, and then you'll stop searching.

Comment 16

[Shawn Wilsher :sdwilsh]

(In reply to comment #15)
> sdwilsh, can you comment on the coverage of the testsuite with respect to this
> patch?
The location bar behavior is fully tested.  I'm not worried about any regressions here.

Comment 17

[Marco Bonardo [:mak]]

Comment on attachment 491702 [details] [diff] [review]
Patch v3

I'm re-requesting approval based on comment 16, even small performance gains in the locationbar can make a great difference, since it's one of the most used UI pieces in the browser. The autocomplete code has lots of tests, and it's easy to add further in case anything would break.

Comment 18

[Shawn Wilsher :sdwilsh]

(In reply to comment #17)
> I'm re-requesting approval based on comment 16, even small performance gains in
> the locationbar can make a great difference, since it's one of the most used UI
> pieces in the browser. The autocomplete code has lots of tests, and it's easy
> to add further in case anything would break.
Note: I can't think of anything that isn't tested in this code path.  Luckily, the location bar algorithm was written well after we started focusing on tests landing with the code, so reviewers have made sure every new piece of functionality is tested.

Comment 19

[Justin Lebar (not reading bugmail)]

I'm marking this with [check-in-after-branch] so I remember to come back to this after we branch 4.0, but I don't mean to negate mak's request for a2.0.

Comment 20

[Justin Lebar (not reading bugmail)]

http://hg.mozilla.org/mozilla-central/rev/85edf194b461