2002596 - Improve performance manifestparser.filters.chunk_by_runtime

Status: NEW

(Testing :: General, task)

Description

[[:sergesanspaille]]

Current implementation spends some time handling the case where key are missing. It turns out this case does not currently happen, so it should be guarded.

The algorithm to balance the load is in O(|runtimes| x |chunks| x log |chunks|) because of repetitive use of sort. We can leverage the fact that the list of chunks is always sorted to do a bisect + insertion, which gives a O(|runtimes| x |chunks|) complexity in worst case, and often O(|runtimes| x log |chunks|)

Comment 1

[[:sergesanspaille]]

Attachment: Bug 2002596 - Improve algorithmic complexity of manifestparser.filters.chunk_by_runtime r=jmaher!

Comment 2

[Pulsebot]

Pushed by [e-mail]:
https://github.com/mozilla-firefox/firefox/commit/c2284ad36bf5
https://hg.mozilla.org/integration/autoland/rev/849840e08761
Improve algorithmic complexity of manifestparser.filters.chunk_by_runtime r=jcristau

Comment 3

[Pulsebot]

Pushed by [e-mail]:
https://github.com/mozilla-firefox/firefox/commit/b281825aa31a
https://hg.mozilla.org/integration/autoland/rev/d261486fdca9
Revert "Bug 2002596 - Improve algorithmic complexity of manifestparser.filters.chunk_by_runtime r=jcristau" for causing failures at ChunkByRuntime.

Comment 4

[Atila Butkovits]

Backed out for causing failures at ChunkByRuntime.

Backout link: https://hg-edge.mozilla.org/integration/autoland/rev/d261486fdca9302dbe1bc67dd51094913791446e

Push with failures: https://treeherder.mozilla.org/jobs?repo=autoland&resultStatus=testfailed%2Cbusted%2Cexception%2Cretry%2Cusercancel&revision=849840e0876132f4990dda98659fe2522a9f8c75

Failure log: https://treeherder.mozilla.org/logviewer?job_id=540276201&repo=autoland&task=K866Wqs9QVCS4VwD6Kcuew.0&lineNumber=2265

Comment 5

[[:sergesanspaille]]

The patch was relying on python 3.10 for the key argument of bisect. Postponing the patch.