At the moment our nodes are re-numbered sequentially from 0 to number of used nodes. There is no locality in node order at all.

The extractor and especially our guidance code makes use of an immense amount of 1/ coordinate lookups through the node info list (keyed by node id) and 2/ graph traversal via the Dynamic Node Based Graph (nodes sorted by source).

At the moment this is random access as random as it can get (read: bad).

We should establish locality in node ordering by re-using our Hilbert space-filling curve. The reason we're not doing a BFS-based ordering is mainly because we'd need to construct a graph first. A space-filling curve based ordering is good enough for a solid approximation.

Here are some notes:

• For every way we loop over its nodes remembering used node ids in the extractor callbacks

• In the extraction containers we renumber nodes sequentially saving a mapping into the external to internal node id map

• We write the nodes to disk in a contiguous chunk of memory to the beginning of the .osrm file prefixed with the number of nodes

• When building the edge expanded graph the first thing we're doing is reading the nodes from disk again into the this time unzipping them into nodes, barriers, traffic signals. Related: Rename QueryNode to NodeLocation or similar #3238.