[Routing] Tools for getting from OSM to a routable network

[Nic Roets]

Hello Geoff,

I agree with Christian that nodes should ordered with the 2D Hilbert curve
(In Gosmore I made the mistake of using a hybrid between Hilbert curve and
hashing). I think the improvement is much more than factor 3 when you're
routing from New York to LA. But it's certainly dependent on the
implementation details.

On Mon, Sep 22, 2014 at 12:16 AM, Geoff Leyland <geoff_leyland at fastmail.fm>
wrote:

>
> Can you expand on where you’ve worked on cache misses?
>
> I store arcs and nodes fairly compactly, and without geometry.  Arcs are a
> large array of:
>
> struct maps_centrelines_arc
> {
>   int32_t end_node;
>   int32_t length_m, time_s;
> };
>
> ordered so that nodes can be:
>
> struct maps_centrelines_node
> {
>   int32_t first_arc;
>   int32_t last_arc;
> };
>

Obviously you should order the nodes according to the Hilbert curve. But
you should also order the arcs according to the Hilbert curve (the
"start_node" field that was optimized away). Then the last_arc of a node
will be the same as first_arc-1 of the next node.

In fact, if you put special delimiting entries in your arc array, you can
get rid of your node array. Then your nodes are subsequences of the arc
array.

That's what I did in Gosmore. But I kept the geometry and calculate the
costs on the fly. So my arc array contains almost everything:

struct doubleArc { // The actual structure has a different name and the
fields are all int32_t
  int32_t lat, lon;
  doubleArc *forward_end_node, *backward_end_node;
  wayType *wayDetails;
}

Each doubleArc encodes the arc that goes forwards along the way and the arc
that goes backwards. If the node is at the end of the way, it's
forward_end_node is NULL.

Note that the array does not contain explicit delimiting entries: If two
arcs have the same lat and lon, Gosmore assumes that they belong to the
same node.

Also note that there a binary(ish) search algorithm to find all the nodes
in a given bbox. So there is no need for quad trees.

To implement Dijkstra, I need some temporary work space. Specifically I
need 2 structs for every doubleArc (resembling the states of arriving at
the node using either of the arcs), which is allocated as an array. This
array is indexed using a direct mapping, so it's entries are also in
Hilbert curve order. The virtual size of this array is several GB, but it's
an mmap() of /dev/zero, so it's physical size is typically much smaller.


> …except that I’ve done no work whatsoever on the heap.  It’s a
> GC-allocated binary heap of non-contiguous objects.  I bet there’s
> improvements to be made there.
>
>
My heaps are arrays of pointers. My experiments showed that the heap stays
quite small for long route. It seldom exceeds 200 entries.



-- 
Regards,
Nic
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/routing/attachments/20140922/0aca22b7/attachment.html>