Skip to content

Routing bake 1/4: one compact copy of the OSM source data #3238

Closed

Description

@timohueser

Status: done

Part of #3228. The words of #3228 apply.

TL;DR

Goal: The routing import keeps each OSM fact once, in flat tables. The Switzerland import then peaks at about 2–3 GB instead of 9.0 GB (target), and the package keeps the same bytes and the same warning counts.
Problem: The import keeps every relation of the file, every referenced node with its tags in hash maps, and up to four copies of the tags and the node list of each highway (see the Facts of #3228).
Decision: source::Tags becomes one packed byte string per object. source::Data becomes three tables sorted by OSM ID, which a builder fills and then sorts. A new column.rs gives two flat containers, Column<T> and Lists<T>, backed by a Vec in this step. The import reads all its files in two passes, and keeps only the relations that can be used.
Systems: routing
Contracts: none
Size: M (one system, about 900 changed lines, many callers of the tag API)

Plan

  1. planner/router-build/src/column.rs (new): Column<T: Copy> (one growable array: push, extend, len, a slice of the values) and Lists<T: Copy> (many variable-length lists in one array: push a list, get(i) a list, len). Both wrap a Vec here. Routing bake 4/4: work tables in files, and sorts on disk #3241 changes only what they store into. Variable-length data, such as tags and roles, is Lists<u8> from the start.

  2. source.rs: Tags stores the pairs of one object as one packed byte string in key order: for each pair, the key length and the value length as u16, then the key bytes, then the value bytes. It has get(key), contains(key, value), iter(), len() and from_pairs. Iteration keeps today's key order, so every output keeps its bytes. A tag can hold any byte, also a NUL.

  3. source.rs: Data holds three tables sorted by OSM ID:

    • Nodes: IDs, points, and tags only for the nodes that have tags.
    • Ways: IDs, node ID lists (Lists<i64>) and tags.
    • Relations: IDs, member IDs (Lists<i64>), member kinds and roles (Lists<u8>: one kind byte and one length-prefixed role for each member), and tags.

    Data::node(id), Data::way(id) and Data::relation(id) find an object by binary search. Data::nodes(), Data::ways() and Data::relations() iterate in ID order, as the BTreeMaps do today. Data::country(way) keeps its rule. A data::Builder takes objects in any order, and Builder::finish sorts them by ID with a stable sort, keeps the first copy of each ID, and returns the number of copies that it dropped. The import and the tests build Data with it; a test that changes a tag builds the object again.

  4. osm.rs import:

    • The first pass reads every file and appends each highway to the way builder, in read order. It also appends every relation of every file, compactly, to the relation builder.
    • After the first pass, the way builder sorts. Its dropped copies give the count "duplicate input ways", as today. Then the import keeps a relation only if it has a member that is a highway of any file, a node member, or a relation member. The rule of preserve_relations then runs on these, so the preserved relations stay the same.
    • One sort of all node references gives the sorted IDs of the needed nodes and their use counts. This replaces the needed map.
    • The second pass reads every node of every file. It keeps a node when its ID is in the sorted needed IDs (binary search) and its point is inside the bounds, and the first copy wins, as today. It stores the point, the crossing modes (from crossing, as today) and the tags of a tagged node. This replaces RawNode. "outside bounds or missing referenced nodes" stays the number of needed IDs minus the kept nodes.
    • Then the import drops the ways that have no node inside the bounds, as preserved.ways.retain does today.
    • build_graph reads the ways and the nodes from Data and copies nothing. RawWay keeps only the attributes of a way.
  5. The callers of the tag and data API use the new methods: cost.rs, suitability.rs, road_bike.rs, traffic.rs, lib.rs, overlays.rs, overlays/access.rs, catalog/mod.rs, and the tests that build Data or Tags (osm.rs, cost.rs, catalog/tests.rs).

  6. New tests: Tags keeps the key order and finds every key, also with a NUL byte; Lists reads back what it took; Builder::finish keeps the first copy of an ID.

Done when

  • obc test -p planner-router-build and obc exec cargo clippy -p planner-router-build --all-targets --all-features -- -D warnings pass.
  • A Switzerland bake gives the same manifest ID as a bake of the same input before the change. The warnings are part of the manifest, so their counts stay too.
  • The pull request records the peak memory of the Switzerland import, before and after.

Generated by Claude Code

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions