1287277 - Awesomebar autocomplete perf optimizations

Status: RESOLVED FIXED

(Toolkit :: Places, defect)

Description

[Simon Lindholm]

In the hopes of alleviating bug 1283329 a bit, while also being generally useful, I did some profiling of awesomebar autocomplete and tried to optimize it.

On the test case of searching for a random three-letter string, I managed to improve the SQL parts of the performance by ~30% on my machine (i5-4200U, Linux, clang, -O2), mostly by removing unnecessary memory allocations.
Perf profiles before/after: http://bit.ly/29TJuNQ http://bit.ly/2a28y7I

I'm entirely new to this code, so let me know I'm doing something dumb, optimizing unnecessarily, setting the wrong reviewer, or whatever.

Comment 1

[Simon Lindholm]

Attachment: 0001-Avoid-repeated-string-reallocations-in-NS_UnescapeUR.patch

Comment 2

[Simon Lindholm]

Attachment: 0002-Add-mozIStorageValueArray.AsDependentUTF8String-and-.patch

Comment 3

[Simon Lindholm]

Attachment: 0003-Avoid-unnecessary-string-copies-in-MatchAutoComplete.patch

Comment 4

[Simon Lindholm]

Attachment: 0004-Silly-micro-optimization.patch

(hey, I did see memcmp show up in profiles a tiny bit, this might have been it)

Comment 5

[Simon Lindholm]

Attachment: 0005-Avoid-querying-bookmark-title-and-tags-for-non-bookm.patch

I measured this to be a ~10% improvement.

Comment 6

[Marco Bonardo [:mak]]

Hi, thank you for looking into these improvements, I'm glad you did it, cause very often we lack the time to go micro-optimizing all the stuff.
I may take a little bit to review all of the changes since I have a couple higher priority fixes and requests, so please be patient.

Comment 7

[Marco Bonardo [:mak]]

Comment on attachment 8771675 [details] [diff] [review]
0001-Avoid-repeated-string-reallocations-in-NS_UnescapeUR.patch

Review of attachment 8771675 [details] [diff] [review]:
-----------------------------------------------------------------

I cannot review code in this component, so forwarding

::: xpcom/io/nsEscape.cpp
@@ +579,5 @@
>      NS_NOTREACHED("null pointer");
>      return false;
>    }
>  
> +  NS_ASSERTION(aResult.IsEmpty(),

In new code I'd probably suggest to use MOZ_ASSERT, that is a fatal assertion.

Comment 8

[Nathan Froyd [:froydnj]]

Comment on attachment 8771675 [details] [diff] [review]
0001-Avoid-repeated-string-reallocations-in-NS_UnescapeUR.patch

Review of attachment 8771675 [details] [diff] [review]:
-----------------------------------------------------------------

Looks good to me!  Please modify the patch to include Mak's suggestion of using MOZ_ASSERT.  Glancing through the callers, I don't think a fatal assertion will cause problems here.

Comment 9

[Marco Bonardo [:mak]]

Comment on attachment 8771679 [details] [diff] [review]
0005-Avoid-querying-bookmark-title-and-tags-for-non-bookm.patch

Review of attachment 8771679 [details] [diff] [review]:
-----------------------------------------------------------------

I need some more details about this change, since I'm not sure where the saving generates, and maybe once figured the main cost, we could look into an approach that doesn't execute twice the group_concat.

::: toolkit/components/places/UnifiedComplete.js
@@ +115,5 @@
>  
>  // TODO bug 412736: in case of a frecency tie, we might break it with h.typed
>  // and h.visit_count.  That is slower though, so not doing it yet...
> +// NB: as a slight performance optimization, we only evaluate the "btitle"
> +// and "tags" queries for bookmarked entries.

I'd like to better understand where we are saving, cause the slowness here is:
1. the tags concact
2. looking through the tags in SQLFunctions

We don't seem to save anything on the concat, since SQL_BOOKMARK_TAGS_FRAGMENT} doesn't have a CASE WHEN, and ideally non bookmarked entries atm should not have tags. so in those cases we should pass to AUTOCOMPLETE_MATCH an empty string.

instead this seems to execute twice the group_concat, that doesn't look like a perf improvement to me.

@@ +126,5 @@
>       LEFT JOIN moz_openpages_temp t ON t.url = h.url
>       WHERE h.frecency <> 0
>         AND AUTOCOMPLETE_MATCH(:searchString, h.url,
> +                              CASE WHEN bookmarked THEN
> +                                IFNULL(${SQL_BTITLE_FRAGMENT}, h.title)

don't we already have btitle here, since the query includes SQL_BOOKMARK_TAGS_FRAGMENT?

@@ +129,5 @@
> +                              CASE WHEN bookmarked THEN
> +                                IFNULL(${SQL_BTITLE_FRAGMENT}, h.title)
> +                              ELSE h.title END,
> +                              CASE WHEN bookmarked THEN
> +                                ${SQL_TAGS_FRAGMENT}

and ditto for tags

Comment 10

[Simon Lindholm]

The idea is to do lazy evaluation: when performing |SELECT expensive_function(...) WHERE ...|, the function only gets evaluated when the WHERE condition is fulfilled.

> don't we already have btitle here, since the query includes SQL_BOOKMARK_TAGS_FRAGMENT?

We do, but if I refer to it, sqlite will eagerly evaluate it (even when bookmarked is false).

I'll recheck that what I'm saying is correct and rewrite the comment when I get time.

Comment 11

[Marco Bonardo [:mak]]

Comment on attachment 8771677 [details] [diff] [review]
0003-Avoid-unnecessary-string-copies-in-MatchAutoComplete.patch

Review of attachment 8771677 [details] [diff] [review]:
-----------------------------------------------------------------

I like the idea, I suggest to use the (start, end) constructors though, for coherence, what do you think?

::: toolkit/components/places/SQLFunctions.cpp
@@ +221,5 @@
>      if (aMatchBehavior == mozIPlacesAutoComplete::MATCH_ANYWHERE_UNMODIFIED)
> +      return fixedSpec;
> +
> +    if (StringBeginsWith(fixedSpec, NS_LITERAL_CSTRING("http://"))) {
> +      fixedSpec.Rebind(fixedSpec, 7);

To rebind on the same string, there is a constructor taking (start, end) that would probably be a better choice (ideally one could optimize the functions differently when binding to the same string vs to a different string, even if that doesn't currently happen).
The end value can easily be buffered before the first if and reused.

@@ +231,3 @@
>  
> +    if (StringBeginsWith(fixedSpec, NS_LITERAL_CSTRING("www."))) {
> +      fixedSpec.Rebind(fixedSpec, 4);

It may be more readable as 
return Substring(fixedSpec, 4);
if Substring can be used on nsDependentStrings, I don't recall.

Comment 12

[Marco Bonardo [:mak]]

(In reply to Simon Lindholm from comment #10)
> The idea is to do lazy evaluation: when performing |SELECT
> expensive_function(...) WHERE ...|, the function only gets evaluated when
> the WHERE condition is fulfilled.
> 
> > don't we already have btitle here, since the query includes SQL_BOOKMARK_TAGS_FRAGMENT?
> 
> We do, but if I refer to it, sqlite will eagerly evaluate it (even when
> bookmarked is false).

I see. On the other side though, for bookmarks, we will evaluate it twice :(

Comment 13

[Simon Lindholm]

> To rebind on the same string, there is a constructor taking (start, end)
> that would probably be a better choice (ideally one could optimize the
> functions differently when binding to the same string vs to a different
> string, even if that doesn't currently happen).
> The end value can easily be buffered before the first if and reused.

Hm. I couldn't find a way to use the constructor (or Substring), since nsDependentSubstring's assignment operator is deleted...

> if Substring can be used on nsDependentStrings, I don't recall.

Should be possible. I like the symmetry though.

> I see. On the other side though, for bookmarks, we will evaluate it twice :(

Only if actually SELECTed, which happens for at most 10 items. Non-SELECTed bookmarks will take the additional perf hit of two CASEs, but that shouldn't be very expensive I believe.

Comment 14

[Marco Bonardo [:mak]]

Comment on attachment 8771676 [details] [diff] [review]
0002-Add-mozIStorageValueArray.AsDependentUTF8String-and-.patch

Review of attachment 8771676 [details] [diff] [review]:
-----------------------------------------------------------------

::: storage/mozIStorageValueArray.idl
@@ +5,5 @@
>  
>  #include "nsISupports.idl"
>  %{C++
>  #include "mozilla/DebugOnly.h"
> +#include "nsStringGlue.h"

I'd prefer not to add further string dependencies here, can we do the conversion from AsSharedUTF8String in SQLFunctions.cpp instead?

Comment 15

[Marco Bonardo [:mak]]

(In reply to Simon Lindholm from comment #13)
> > To rebind on the same string, there is a constructor taking (start, end)
> > that would probably be a better choice (ideally one could optimize the
> > functions differently when binding to the same string vs to a different
> > string, even if that doesn't currently happen).
> > The end value can easily be buffered before the first if and reused.
> 
> Hm. I couldn't find a way to use the constructor (or Substring), since
> nsDependentSubstring's assignment operator is deleted...

Sorry I meant Rebind(start, end); instead of Rebind(string, start);

Comment 16

[Marco Bonardo [:mak]]

Comment on attachment 8771679 [details] [diff] [review]
0005-Avoid-querying-bookmark-title-and-tags-for-non-bookm.patch

OK, I need to look into this again and do some testing.

Comment 17

[Simon Lindholm]

> I'd prefer not to add further string dependencies here, can we do the
> conversion from AsSharedUTF8String in SQLFunctions.cpp instead?

Sure.

> Sorry I meant Rebind(start, end); instead of Rebind(string, start);

Can do, but note that it would look like |fixedSpec.Rebind(fixedSpec.BeginReading() + 7, end);| unless I add another Rebind overload taking integer indices.

> OK, I need to look into this again and do some testing.

Great!

Comment 18

[Marco Bonardo [:mak]]

(In reply to Simon Lindholm from comment #17)
> Can do, but note that it would look like
> |fixedSpec.Rebind(fixedSpec.BeginReading() + 7, end);| unless I add another
> Rebind overload taking integer indices.

Sigh, I thought it was taking indices in one overload. Nevermind, let's keep it as-is.

Comment 19

[Marco Bonardo [:mak]]

I had some problems measuring meaningful improvements from the SQL change.
But I see where it may be faster.

Though, I wonder if doing the CASE WHEN but using btitle and tags inside it, will still evaluate them for discarded rows. so basically:
       AND AUTOCOMPLETE_MATCH(:searchString, h.url,

                              CASE WHEN bookmarked THEN IFNULL(btitle}, h.title)
                                   ELSE h.title
                              END,
                              CASE WHEN bookmarked THEN tags
                                   ELSE ''
                              END,

I couldn't measure a difference between this and the one where the expressions are repeated twice.
It would be unfortunate if sqlite would evaluate btitle and tags if the case condition is not satisfied.

Comment 20

[Simon Lindholm]

Ah, you appear to be entirely correct! It's a bit surprising to me to see sqlite perform lazy evaluation on all variables, but I suppose it makes some amount of sense. I'm seeing the following timings ± stdevs:

A: 361896 us ± 11440 (154 data points)
B: 333050 us ± 12844 (150 data points)
C: 335006 us ± 17755 (166 data points)

where A is the original code, B uses your last comment's version, and C is my patch's. I don't have error bars on that, but with 150 data points it should be fairly safe to say that either B or C is a ~8% win over A.

I'll revise the patch to avoid the duplication.

Comment 21

[Simon Lindholm]

Attachment: [DO NOT LAND] Benchmarking code, for reference

Comment 22

[Simon Lindholm]

Attachment: 0001-Bug-1287277-Avoid-repeated-string-reallocations-in-N.patch

Comment 23

[Simon Lindholm]

Attachment: 0002-Bug-1287277-Use-AsSharedUTF8String-in-MatchAutoCompl.patch

Comment 24

[Simon Lindholm]

Attachment: 0003-Bug-1287277-Avoid-unnecessary-string-copies-in-Match.patch

Comment 25

[Simon Lindholm]

Attachment: 0004-Bug-1287277-Silly-micro-optimization.-r-mak.patch

Comment 26

[Simon Lindholm]

Attachment: 0005-Bug-1287277-Avoid-querying-bookmark-title-and-tags-f.patch

Comment 27

[Simon Lindholm]

Try looks quite green: https://treeherder.mozilla.org/#/jobs?repo=try&revision=2eff3a575c10

Comment 28

[Marco Bonardo [:mak]]

Comment on attachment 8775240 [details] [diff] [review]
0002-Bug-1287277-Use-AsSharedUTF8String-in-MatchAutoCompl.patch

Review of attachment 8775240 [details] [diff] [review]:
-----------------------------------------------------------------

::: toolkit/components/places/SQLFunctions.cpp
@@ +181,5 @@
> +  getSharedString(mozIStorageValueArray* aValues, uint32_t aIndex) {
> +    uint32_t len;
> +    const char* str = aValues->AsSharedUTF8String(aIndex, &len);
> +    if (!str) {
> +      return nsDependentCString("", (uint32_t)0);

I was just a little bit worried about dangling pointers, but Sqlite manages the lifetime of most of them and that satisfies our needs.
But for this innocuous looking empty string... who owns it?
Maybe we should create outside an EmptyCString() and pass it to this method, so we can build a dependentString whose lifetime is certain?

Comment 29

[Nathan Froyd [:froydnj]]

(In reply to Marco Bonardo [::mak] (Away 6-20 Aug) from comment #28)
> ::: toolkit/components/places/SQLFunctions.cpp
> @@ +181,5 @@
> > +  getSharedString(mozIStorageValueArray* aValues, uint32_t aIndex) {
> > +    uint32_t len;
> > +    const char* str = aValues->AsSharedUTF8String(aIndex, &len);
> > +    if (!str) {
> > +      return nsDependentCString("", (uint32_t)0);
> 
> I was just a little bit worried about dangling pointers, but Sqlite manages
> the lifetime of most of them and that satisfies our needs.
> But for this innocuous looking empty string... who owns it?

It ought to reside in the static data section of the program binary, so it effectively lives forever.

Comment 30

[Marco Bonardo [:mak]]

Comment on attachment 8775240 [details] [diff] [review]
0002-Bug-1287277-Use-AsSharedUTF8String-in-MatchAutoCompl.patch

Review of attachment 8775240 [details] [diff] [review]:
-----------------------------------------------------------------

You are right. Considered its size, it's likely a price we can pay.

Comment 31

[Simon Lindholm]

Right. In practice it might have been fine also to return an nsDependentCSubstring(nullptr, 0), but that felt a lot iffier.

Setting checkin-needed.

Comment 32

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/fd2b1e87c27e
Avoid repeated string reallocations in NS_UnescapeURL. r=nfroyd
https://hg.mozilla.org/integration/mozilla-inbound/rev/bcfdd291e2f1
Use AsSharedUTF8String in MatchAutoCompleteFunction. r=mak
https://hg.mozilla.org/integration/mozilla-inbound/rev/dcb3c6e5c58b
Avoid unnecessary string copies in MatchAutoCompleteFunction::fixupURISpec. r=mak
https://hg.mozilla.org/integration/mozilla-inbound/rev/ca925530409a
Silly micro-optimization. r=mak
https://hg.mozilla.org/integration/mozilla-inbound/rev/a83df31aa5bd
Avoid querying bookmark title and tags for non-bookmarked items. r=mak

Comment 33

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/fd2b1e87c27e
https://hg.mozilla.org/mozilla-central/rev/bcfdd291e2f1
https://hg.mozilla.org/mozilla-central/rev/dcb3c6e5c58b
https://hg.mozilla.org/mozilla-central/rev/ca925530409a
https://hg.mozilla.org/mozilla-central/rev/a83df31aa5bd

Comment 34

[Marco Bonardo [:mak]]

let's wait some nightlies, then I think we should evaluate uplifting these to 49 early in the cycle, any perf optimization in the location bar is worth it.

Comment 35

[Marco Bonardo [:mak]]

Comment on attachment 8775243 [details] [diff] [review]
0005-Bug-1287277-Avoid-querying-bookmark-title-and-tags-f.patch

To simplify things I'm setting the request only on one patch, but all should land:

Approval Request Comment
[Feature/regressing bug #]: none, this is a performance improvement. We just released a redesign in 48, and some users are suffering perf degrade in certain cases, this may help with that.
[User impact if declined]: awesomebar is slower for some users
[Describe test coverage new/current, TreeHerder]: nightly/aurora
[Risks and why]: the changes are small optimizations that shouldnot have a scary impact, it's also safe to backout in case of problems.
[String/UUID change made/needed]: none

Comment 36

[Gerry Chang [:gchang]]

Comment on attachment 8775243 [details] [diff] [review]
0005-Bug-1287277-Avoid-querying-bookmark-title-and-tags-f.patch

Review of attachment 8775243 [details] [diff] [review]:
-----------------------------------------------------------------

This patch improves the awesomebar performance. Take it in 49 beta. Should be in 49 beta 2.

Comment 37

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/releases/mozilla-beta/rev/c78636aa0841
https://hg.mozilla.org/releases/mozilla-beta/rev/48a8efc2a881
https://hg.mozilla.org/releases/mozilla-beta/rev/cfd61c6384da
https://hg.mozilla.org/releases/mozilla-beta/rev/d4cbfda135b5
https://hg.mozilla.org/releases/mozilla-beta/rev/0750b973794f