1356282 - Sync's Utils.arrayUnion and Utils.arraySub should not be O(n^2)

Status: RESOLVED FIXED

(Firefox :: Sync, enhancement, P3)

Description

[Thom Chiovoloni [:tcsc] (ex-moco)]

Currently these are needlessly O(n^2) (indexOf in a loop). They could be O(n) if implemented using Set.

I don't know of any cases where this causes a real performance problem, but I noticed it recently and made a mental note to file a bug for it.

Comment 1

[:Grisha Kruglov]

P3, and also NI myself to investigate as a first bug.

Comment 2

[Santiago Paez [:tiago]]

Attachment: Bug 1356282 - Change Sync's Utils.arraySub to be O(n) using Set.

Sync's Utils.arrayUnion and Utils.arraySub are O(n^2) because Utils.arraySub uses indexOf inside a loop. This patch makes Utils.arraySub use a Set, and by doing so, Utils.arrayUnion and Utils.arraySub become O(n).

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

Comment 3

[Thom Chiovoloni [:tcsc] (ex-moco)]

Comment on attachment 8864747 [details]
Bug 1356282 - Change Sync's Utils.arraySub to be O(n) using Set.

https://reviewboard.mozilla.org/r/136406/#review139718

Looks good and the test pass.

Comment 4

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/afee0d3c7aab
Change Sync's Utils.arraySub to be O(n) using Set. r=tcsc

Comment 5

[Sebastian Hengst [:aryx] (needinfo me if it's about an intermittent or backout)]

https://hg.mozilla.org/mozilla-central/rev/afee0d3c7aab