Distances in MLD by ghoshkaj · Pull Request #5019 · Project-OSRM/osrm-backend

ghoshkaj · 2018-04-12T03:48:12Z

Issue

#5013 - Distances in Matrix, MLD

Similar to unpacking in CH, we need to do two things for MLD

From the bidirectional search and the unidirectional search in the table plugin for MLD, we need to recreate the "shortcut" or "packed" path.
We need to unpack the path and calculate the distance of each packed edge while doing so

Details

Finding the packed path

ManyToMany/Bidirectional search: Path finding already happens in the forward routing steps and the backward routing steps in the MLD ManyToManySearch function. The idea is to use the heap from the ForwardRoutingStep and the search space buckets in the BackwardRoutingStep to recreate the packed or shortcutted path.
OneToMany/Unidirectional Search: Path finding already happens during the unidirectional search - however, we need to extract the packed path from the heap and the multi-map that it uses.

We need as the original issue says, to repurpose the unpacking part of the Search function to compute the distances with. We also have to repurpose some of the heaps I believe, as the SearchEngineData heaps aren't manyToMany heaps, but rather, just regular heaps.

Tasklist

CHANGELOG.md entry (How to write a changelog entry)
update relevant Wiki pages
add tests (see testing documentation
review
adjust for comments
cherry pick to release branch

Requirements / Relations

Link any requirements here. Other pull requests this PR is based on?

chaupow · 2018-05-02T13:43:08Z

the changes in profiles/testbot.lua break the test in cucumber features/testbot/traffic_speeds.feature:34

We need to investigate the profile changes and adjust features/testbot/traffic_speeds.feature if we want the change.

cc @TheMarex @ghoshkaj

oxidase · 2018-05-07T07:06:25Z

@ghoshkaj @chaupow I have pushed a commit that contains some fixes for the branch:

phantom nodes selection for unpacking at ecf8016#diff-33262109709646f9865da9ee18f04f50R390 and ecf8016#diff-33262109709646f9865da9ee18f04f50R653
Phantom nodes are used in getNodeQueryLevel functions to compute an overlay level for nodes processed by MLD.
added DIRECTION argument to retrievePackedPathFromSearchSpace and if DIRECTION is REVERSE_DIRECTION edges will be reversed.
simplified logic to compute phantom nodes offsets, by moving checks DIRECTION == REVERSE_DIRECTION before of the conditional branches and swapping source_phantom_index and target_phantom_index
extended Testbot - Multi level routing test case to check also the distances table.

chaupow · 2018-05-07T22:26:11Z

ran current branch and compared with CH numbers:

What	`distances` with MLD	`distances` with CH
100x100 in `us-west`	`30.7s`	`5.6s`
100x100 in la max dist 20km	`5.88s`	`800ms`

chaupow · 2018-05-08T10:21:00Z

ran current branch and measured 25x25 requests

What	`distances` with MLD
25x25 in `us-west`	`2.1s`
25x25 in la max dist 20km	`600ms`

TheMarex

Some cleanup needs to be done.

TheMarex · 2018-05-08T13:03:03Z

features/testbot/distance_matrix.feature

            | a | 0      | 100+-1 |
            | b | 100+-1 | 0      |

+    @ch


We should capture why these tests only work on CH.

TheMarex · 2018-05-08T13:03:09Z

features/testbot/distance_matrix.feature

            | c |        |        | 0      | 100+-1 |
            | d |        |        | 100+-1 | 0      |

+    @ch


TheMarex · 2018-05-08T13:05:17Z

include/engine/routing_algorithms/many_to_many.hpp

 {
    NodeID middle_node;
    NodeID parent_node;
+    bool from_clique_arc;


We cam optimize the size here with bit packing:

unsigned column_index : 31; unsigned from_clique_arc : 1;

TheMarex · 2018-05-08T13:08:19Z

include/engine/routing_algorithms/routing_base_mld.hpp

    // Get packed path as edges {from node ID, to node ID, from_clique_arc}
    auto packed_path = retrievePackedPathFromHeap(forward_heap, reverse_heap, middle);

+    // if (!packed_path.empty())


This is left-over debugging code and needs to be removed.

TheMarex · 2018-05-08T13:08:26Z

include/engine/routing_algorithms/routing_base_mld.hpp

            unpacked_edges.insert(unpacked_edges.end(), subpath_edges.begin(), subpath_edges.end());
        }
    }
+    // std::cout << "unpacked_nodes: ";


TheMarex · 2018-05-08T13:09:03Z

profiles/testbot.lua

     turn.duration = turn.duration + profile.properties.traffic_light_penalty
  end
+
+  io.write("after penalty turn.duration: ", turn.duration, "turn.weight: ", turn.weight, "\n")


This is debug code and needs to be removed.

TheMarex · 2018-05-08T13:09:21Z

src/engine/routing_algorithms/direct_shortest_path.cpp

    auto &reverse_heap = *engine_working_data.reverse_heap_1;
    insertNodesInHeaps(forward_heap, reverse_heap, phantom_nodes);

+    std::cout << "source_phantom.forward_segment_id.id: "


This is debug code and needs to be removed.

TheMarex · 2018-05-08T13:09:54Z

src/engine/routing_algorithms/many_to_many_ch.cpp

    // Store settled nodes in search space bucket
    search_space_with_buckets.emplace_back(
-        node, parent, column_index, target_weight, target_duration);
+        node, parent, INVALID_CLIQUE_ARC_TYPE, column_index, target_weight, target_duration);


Instead of pushing this to the call-site we can add a second constructor.

TheMarex · 2018-05-08T13:12:29Z

src/engine/routing_algorithms/many_to_many_mld.cpp

-                                                 : facade.IsBackwardEdge(edge))
+            if ((DIRECTION == FORWARD_DIRECTION ? facade.IsForwardEdge(edge)
+                                                : facade.IsBackwardEdge(edge)) &&
+                !query_heap.WasInserted(facade.GetTarget(edge)))


We should pull out facade.GetTarget(edge) in an own variable.

This commit brings feature parity with CH for the `table` pluging.

ghoshkaj added the Experimental - Do not merge label Apr 12, 2018

ghoshkaj force-pushed the mld-distances branch 3 times, most recently from 1beecb1 to 0e2092a Compare April 20, 2018 02:47

chaupow changed the base branch from master to distances April 20, 2018 10:22

ghoshkaj force-pushed the distances branch 3 times, most recently from 649e0af to 5ebc145 Compare April 20, 2018 21:21

ghoshkaj force-pushed the mld-distances branch 5 times, most recently from 1048bd3 to 1ac22d0 Compare April 23, 2018 22:53

TheMarex added this to the distance-matrix milestone Apr 24, 2018

TheMarex added Work In Progress and removed Experimental - Do not merge labels Apr 24, 2018

TheMarex assigned ghoshkaj Apr 24, 2018

ghoshkaj force-pushed the mld-distances branch 6 times, most recently from 181486a to 0470d55 Compare April 30, 2018 11:04

ghoshkaj changed the base branch from distances to master May 1, 2018 01:31

ghoshkaj force-pushed the mld-distances branch from 24aa921 to 80e994f Compare May 2, 2018 03:07

chaupow force-pushed the mld-distances branch from c09c21a to 984b9b9 Compare May 2, 2018 13:41

ghoshkaj force-pushed the mld-distances branch from 8bc9bb8 to 383a6af Compare May 3, 2018 02:21

oxidase force-pushed the mld-distances branch 2 times, most recently from d3d24b1 to 40c025c Compare May 6, 2018 14:33

oxidase force-pushed the mld-distances branch 2 times, most recently from e5598d7 to ecf8016 Compare May 6, 2018 15:41

TheMarex force-pushed the mld-distances branch 2 times, most recently from 2351bdc to 8537df0 Compare May 7, 2018 15:56

TheMarex force-pushed the mld-distances branch from 8537df0 to 8dd510d Compare May 7, 2018 22:54

TheMarex force-pushed the mld-distances branch from 8dd510d to 22acbe4 Compare May 8, 2018 13:02

TheMarex requested changes May 8, 2018

View reviewed changes

Add support for annotations=distances in MLD

37e3777

This commit brings feature parity with CH for the `table` pluging.

TheMarex force-pushed the mld-distances branch from 22acbe4 to 37e3777 Compare May 8, 2018 13:48

Address PR comments

dfb6f8a

TheMarex force-pushed the mld-distances branch from 0f09c28 to dfb6f8a Compare May 8, 2018 13:55

TheMarex added Review - In feedback and removed Work In Progress labels May 8, 2018

Fix excluding nodes for one to all query

4aed184

TheMarex approved these changes May 8, 2018

View reviewed changes

TheMarex merged commit 3b4e2e8 into master May 8, 2018

TheMarex deleted the mld-distances branch May 8, 2018 15:50

danpat mentioned this pull request Sep 5, 2018

Optionally cache CH/MLD edge distances #5197

Closed

6 tasks

danpat mentioned this pull request Oct 29, 2018

Pre-calculate distance values #5251

Merged

6 tasks

Uh oh!

Conversation

ghoshkaj commented Apr 12, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Issue

Tasklist

Requirements / Relations

Uh oh!

chaupow commented May 2, 2018

Uh oh!

oxidase commented May 7, 2018

Uh oh!

chaupow commented May 7, 2018

Uh oh!

chaupow commented May 8, 2018

Uh oh!

TheMarex left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

4 participants

ghoshkaj commented Apr 12, 2018 •

edited

Loading