Fix generation of inefficient MLD partitions#6085
Merged
mjjbell merged 1 commit intoProject-OSRM:masterfrom Sep 3, 2021
Merged
Fix generation of inefficient MLD partitions#6085mjjbell merged 1 commit intoProject-OSRM:masterfrom
mjjbell merged 1 commit intoProject-OSRM:masterfrom
Conversation
Member
Author
Performance AnalysisPreparationUsing the same set up as the analysis for 5953. Test coordinate sets 1-4 are used to run the following requests via libosrm:
Tests are performed using libosrm versions of Project-OSRM:master at commit f7478ba and mjjbell:mbell/fix_partition Results - RouteAll weights returned by route requests were identical between the two versions, confirming that this is an efficiency issue and not one of correctness. The results below show the difference in request time for the coordinate sets. Coordinate set 1Request Duration
Coordinate set 2Request Duration
Coordinate set 3Request Duration
Coordinate set 4Request Duration
Results - TableWe are not able to compare route weights, as the table response does not contain them. Instead we compare route durations. Coordinate set 1Request Duration
Coordinate set 2Request Duration
Coordinate set 3Request Duration
Coordinate set 4Request Duration
Results - File Size
|
mjjbell
force-pushed
the
mbell/fix_partition
branch
2 times, most recently
from
565aa70 to
3d694b3
Compare
Duplicate restriction nodes in the edge-based-graph are currently not in included in a mapping (.osrm.cnbg_to_ebg) from node-based-graph edges to edge-based-graph nodes. This mapping is used by the MLD partitioner to assign EBG nodes to partitions. The omission from the mapping means all restriction nodes are included in a special 'invalid' partition. This special partition will break the geolocation properties of the multi-level hierarchy. The partition and its super levels will have a large number of border nodes and very few internal paths between them. Given the partitioner is the only consumer of the mapping, we fix the issue by including the duplicate restriction nodes in the mapping, so that they are correctly assigned to a partition. This has measurable improvement on MLD routing. For a country-sized routing network, the fix reduces routing and table request computation time by ~2% and ~6% respectively.
mjjbell
force-pushed
the
mbell/fix_partition
branch
from
3d694b3 to
b4cc11b
Compare
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
2 participants
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Issue
See #6084 for details
Performance
This has measurable improvement on MLD routing.
Will include test results in comments below.
TL;DR
/tableis ~6% faster/routeis ~3% fasterosrm-routeduses 0.2% less memoryTasklist
Requirements / Relations
Closes #6084