1453961 - SyncResultObject.add is janky

Status: RESOLVED FIXED

(WebExtensions :: Storage, enhancement)

Description

[Florian Quèze [:florian]]

Profile where this blocked the main thread for ~330ms on a fast macbook pro: https://perfht.ml/2EI1mb9

The poorly performing code (O(n^2)) is https://searchfox.org/mozilla-central/rev/9f3da81290054c5b8955bb67ff98cae66676f745/services/common/kinto-offline-client.js#909-914

Comment 1

[Mathieu Leplatre [:leplatrem]]

FYI, the problem was fixed upstream:
https://github.com/Kinto/kinto.js/pull/807

We now need to upgrade the vendored kinto.js lib

Comment 2

[Mike Conley (:mconley) (:⚙️)]

Is upgrading the vendored kinto.js something that we can do for 61 before the next uplift? When are Kinto upgrades generally done?

Comment 3

[Ethan Glasser-Camp (:glasserc)]

Attachment: Bug 1453961: bump kinto.js version to 11.1.2

This eliminates a quadratic behavior in SyncResultObject#add.

Review commit: https://reviewboard.mozilla.org/r/238290/diff/#index_header
See other reviews: https://reviewboard.mozilla.org/r/238290/

Comment 4

[Ethan Glasser-Camp (:glasserc)]

Whenever we need them ;). At :leplatrem's request, I have cut a release of kinto.js which includes the relevant fix. I tried to launch a try build too, but I can't promise I got the right tasks.

Comment 5

[Florian Quèze [:florian]]

Comment on attachment 8969527 [details]
Bug 1453961: bump kinto.js version to 11.1.2

https://reviewboard.mozilla.org/r/238290/#review244208

::: services/common/kinto-offline-client.js:915
(Diff revision 1)
> +      entries = [entries];
> +    }
>      // Deduplicate entries by id. If the values don't have `id` attribute, just
>      // keep all.
> -    const deduplicated = this[type].concat(entries).reduce((acc, cur) => {
> -      const existing = acc.filter(r => cur.id && r.id ? cur.id != r.id : true);
> +    const recordsWithoutId = new Set(this[type].filter(record => !record.id));
> +    const recordsById = new Map(this[type].filter(record => record.id).map(record => [record.id, record]));

This seems pretty complicated with 2 filter calls over the whole existing array.

Here is a simpler solution:

const recordWithoutId = new Set();
const recordsById = new Map();
this[type].concat(entries).forEach(record => {
  /* same implemention as in the current patch */

And the .concat works even if entries isn't an array yet.

Comment 6

[Ethan Glasser-Camp (:glasserc)]

Comment on attachment 8969527 [details]
Bug 1453961: bump kinto.js version to 11.1.2

https://reviewboard.mozilla.org/r/238290/#review244208

> This seems pretty complicated with 2 filter calls over the whole existing array.
> 
> Here is a simpler solution:
> 
> const recordWithoutId = new Set();
> const recordsById = new Map();
> this[type].concat(entries).forEach(record => {
>   /* same implemention as in the current patch */
> 
> And the .concat works even if entries isn't an array yet.

Thanks for the feedback. I'm not crazy in love with the current implementation in general because we internally maintain an array for this data, and as a result have to convert to/from Maps, potentially numerous times, to ensure uniqueness by ID. I think we would do much better to maintain Maps internally, and expose Arrays if we need to, but that was a more involved change and I didn't really have the time at the moment.

I'm not crazy at the use of `concat` in your solution; it feels like it creates needless copying/GC. (Maybe you know something I don't about how `concat` returns a lazily-instantiated Array or something.) But I agree that there's a commonality about how we treat each record. Using this insight, I've taken another swing at this; it's at https://github.com/Kinto/kinto.js/pull/809. Please feel free to review that as well.

Comment 7

[Florian Quèze [:florian]]

(In reply to Ethan Glasser-Camp (:glasserc) from comment #6)

> I've taken another swing at this; it's at
> https://github.com/Kinto/kinto.js/pull/809. Please feel free to review that
> as well.

Looks good to me, thanks!

Comment 8

[Ethan Glasser-Camp (:glasserc)]

Comment on attachment 8969527 [details]
Bug 1453961: bump kinto.js version to 11.1.2

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/238290/diff/1-2/

Comment 9

[Ethan Glasser-Camp (:glasserc)]

Comment on attachment 8969527 [details]
Bug 1453961: bump kinto.js version to 11.1.2

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/238290/diff/2-3/

Comment 10

[Florian Quèze [:florian]]

Comment on attachment 8969527 [details]
Bug 1453961: bump kinto.js version to 11.1.2

https://reviewboard.mozilla.org/r/238290/#review245750

Thanks!

Comment 11

[Ryan VanderMeulen [:RyanVM]]

Autoland can't push this until all pending issues in MozReview are marked as resolved.

Comment 12

[Ethan Glasser-Camp (:glasserc)]

I have marked the issue as resolved.

Comment 13

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/0d2ed925b490
bump kinto.js version to 11.1.2 r=florian

Comment 14

[Andreea Pavel [:apavel]]

https://hg.mozilla.org/mozilla-central/rev/0d2ed925b490

Comment 15

[marius.santa]

Yes, the bug status is changed and well as the status for the fixed version and later when it is uplifted you will get notified by email.

Comment 16

[marius.santa]

Please disregard the previous comment.
Is manual testing required on this bug? If Yes, please provide some STR and the proper webextension(if required), if No set the “qe-verify-“ flag.