Differential D3484

in_memory: Fix quadratic run time in snapshot_get_branches.
ClosedPublic
Actions

Authored by vlorentz on Jul 9 2020, 6:00 PM.

Details

Reviewers

ardumont

Group Reviewers

Reviewers

Commits

rDSTOe415488900bd: in_memory: Fix quadratic run time in snapshot_get_branches.

Summary

snapshot.branches is now an ImmutableDict, which is backed by
a tuple of tuples; so random accesses now take a linear time
instead of a constant time.

This commit replaces random accesses with a single scan of all
the items, and does existence checks in a set instead.

Diff Detail

Repository

rDSTO Storage manager

Lint

Automatic diff as part of commit; lint not applicable.

Unit

Automatic diff as part of commit; unit tests not applicable.

Event Timeline

vlorentz created this revision.Jul 9 2020, 6:00 PM

Herald added a reviewer: Reviewers. · View Herald TranscriptJul 9 2020, 6:00 PM

vlorentz added a child revision: D3485: Remove overhead of to_dict/from_dict in test_snapshot_large..Jul 9 2020, 6:02 PM

Build is green

Patch application report for D3484 (id=12322)

Rebasing onto c3803ef8f7...

Current branch diff-target is up to date.

Changes applied before test

commit e415488900bde00db6fe519c76616feca8accd2d
Author: Valentin Lorentz <vlorentz@softwareheritage.org>
Date:   Thu Jul 9 17:58:12 2020 +0200

    in_memory: Fix quadratic run time in snapshot_get_branches.
    
    snapshot.branches is now an ImmutableDict, which is backed by
    a tuple of tuples; so random accesses now take a linear time
    instead of a constant time.
    
    This commit replaces random accesses with a single scan of all
    the items, and does existence checks in a set instead.

See https://jenkins.softwareheritage.org/job/DSTO/job/tests-on-diff/436/ for more details.

Harbormaster completed remote builds in B13543: Diff 12322.Jul 9 2020, 6:06 PM