Page MenuHomeSoftware Heritage

in_memory: Fix quadratic run time in snapshot_get_branches.
ClosedPublic

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

Details

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

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.

ardumont accepted this revision.Jul 9 2020, 6:16 PM
ardumont added a subscriber: ardumont.

Looks good.

Thanks.

This revision is now accepted and ready to land.Jul 9 2020, 6:16 PM