| | | 1 | | using System; |
| | | 2 | | using System.Collections.Generic; |
| | | 3 | | using System.Diagnostics; |
| | | 4 | | using System.Linq; |
| | | 5 | | using Itinero.Data; |
| | | 6 | | using Itinero.Network.Tiles.Standalone.Global; |
| | | 7 | | using Itinero.Network.Writer; |
| | | 8 | | |
| | | 9 | | namespace Itinero.Network.Tiles.Standalone.Writer; |
| | | 10 | | |
| | | 11 | | /// <summary> |
| | | 12 | | /// Extension methods related to writing standalone tiles to a network. |
| | | 13 | | /// </summary> |
| | | 14 | | public static class RoutingNetworkWriterExtensions |
| | | 15 | | { |
| | | 16 | | /// <summary> |
| | | 17 | | /// Per-thread scratch for the global edge ids one insert registers. |
| | | 18 | | /// </summary> |
| | | 19 | | [ThreadStatic] |
| | | 20 | | private static List<GlobalEdgeId>? ArrivedEdges; |
| | | 21 | | |
| | | 22 | | |
| | | 23 | | /// <summary> |
| | | 24 | | /// Adds a tile in the form of a standalone tile to the network. |
| | | 25 | | /// </summary> |
| | | 26 | | /// <param name="writer">The writer to write to.</param> |
| | | 27 | | /// <param name="tile">The tile to add.</param> |
| | | 28 | | /// <param name="globalIdSet">The global id set.</param> |
| | | 29 | | /// <remarks> |
| | | 30 | | /// One lock acquisition for the whole insert, not one per edge. |
| | | 31 | | /// |
| | | 32 | | /// Three phases: |
| | | 33 | | /// |
| | | 34 | | /// <list type="number"> |
| | | 35 | | /// <item><b>Claim, unlocked.</b> Register the tile's internal edges' global ids and claim the |
| | | 36 | | /// boundary crossings whose other half has arrived. A standalone tile arrives with its internal |
| | | 37 | | /// edges already encoded, so nothing here writes tile data — it fills concurrent dictionaries. |
| | | 38 | | /// Doing it before any lock is what makes the next step possible.</item> |
| | | 39 | | /// <item><b>Write, grouped by neighbour.</b> Create the matched boundary edges holding this |
| | | 40 | | /// tile's stripe and one partner's, taken together and ordered, all of that partner's |
| | | 41 | | /// crossings at once. Each edge is created exactly |
| | | 42 | | /// once — only the tile that won the claim in step 1 builds it — and writing it puts an entry |
| | | 43 | | /// in both tiles, which is how a cross-tile edge is represented.</item> |
| | | 44 | | /// <item><b>Restrictions.</b> Separate, and locking themselves, because a restriction names |
| | | 45 | | /// edges in tiles that cannot be predicted from the tile being inserted.</item> |
| | | 46 | | /// </list> |
| | | 47 | | /// </remarks> |
| | | 48 | | public static void AddStandaloneTile(this RoutingNetworkWriter writer, StandaloneNetworkTile tile, |
| | | 49 | | GlobalNetworkManager globalIdSet) |
| | 1928 | 50 | | { |
| | | 51 | | // ---- install first, under this tile's stripe alone ---- |
| | | 52 | | // Before anything is claimable. A crossing this tile records becomes visible to the tile |
| | | 53 | | // on the other side, which will immediately want this tile's vertices to build the edge — |
| | | 54 | | // so the tile has to be in the network before its halves are published. Claiming first and |
| | | 55 | | // installing later fails with "vertex not found" on the other thread. |
| | 1928 | 56 | | using (writer.LockTiles(stackalloc[] { tile.TileId })) |
| | 1928 | 57 | | { |
| | 1928 | 58 | | writer.AddTile(tile.NetworkTile); |
| | 1928 | 59 | | } |
| | | 60 | | |
| | | 61 | | // ---- phase 1: no tile writes, no locks ---- |
| | | 62 | | // Reused per thread rather than allocated per insert: ~346 ids per tile is a 5KB list |
| | | 63 | | // every time, on a path where GC already shows up. Gating the collection on "is anything |
| | | 64 | | // pending" instead looked cheaper and was wrong — a restriction parked by another thread |
| | | 65 | | // mid-insert then waits for the sweep, which made resolution depend on how many tiles |
| | | 66 | | // happen to follow. ConcurrentInsert_ManyTilesWithBoundaryCrossings_MatchesSerialInsert |
| | | 67 | | // fails on that. |
| | | 68 | | // |
| | | 69 | | // Safe to reuse: the list never outlives this call. RetryPendingRestrictionsFor reads it |
| | | 70 | | // synchronously, and nothing here inserts a tile re-entrantly on the same thread. |
| | 1928 | 71 | | var arrived = ArrivedEdges ??= new List<GlobalEdgeId>(512); |
| | 1928 | 72 | | arrived.Clear(); |
| | | 73 | | |
| | | 74 | | // 2.6M map entries per cold block against ~200k reads, and its only consumer is turn |
| | | 75 | | // restriction resolution — routing never reads this map, since the global id a client sees |
| | | 76 | | // comes from the edge's own attributes. Skipping it entirely was measured (+7.1% cold) and |
| | | 77 | | // is NOT an option: it silently drops turn restrictions that name an interior edge. |
| | 1928 | 78 | | RegisterInternalEdges(tile, globalIdSet, arrived); |
| | 1928 | 79 | | var crossings = ClaimBoundaryCrossings(tile, globalIdSet); |
| | | 80 | | // ---- phase 2: every tile this insert writes, locked once ---- |
| | | 81 | | // Grouped by partner tile: one acquisition per NEIGHBOUR, not per crossing and not one |
| | | 82 | | // covering every partner at once. |
| | | 83 | | // |
| | | 84 | | // Both extremes are bad here. Locking this tile plus all of its partners for the whole |
| | | 85 | | // batch holds up to nine stripes at once, and the inserts running concurrently are |
| | | 86 | | // precisely the ones that share boundaries — VertexTouched loads a tile together with its |
| | | 87 | | // eight neighbours, BoxTouched loads a whole box — so every insert collides with every |
| | | 88 | | // other. Locking per crossing keeps holds short but pays an acquisition for each of the |
| | | 89 | | // many ways that cross a single boundary. |
| | | 90 | | // |
| | | 91 | | // A tile has at most eight neighbours and usually fewer, so grouping bounds the |
| | | 92 | | // acquisitions by neighbours while keeping each hold to two stripes. |
| | 2052 | 93 | | crossings.Sort(static (x, y) => x.OtherVertex.TileId.CompareTo(y.OtherVertex.TileId)); |
| | 1928 | 94 | | var start = 0; |
| | 3730 | 95 | | while (start < crossings.Count) |
| | 1802 | 96 | | { |
| | 1802 | 97 | | var partner = crossings[start].OtherVertex.TileId; |
| | 1802 | 98 | | var end = start; |
| | 5406 | 99 | | while (end < crossings.Count && crossings[end].OtherVertex.TileId == partner) end++; |
| | | 100 | | |
| | 1802 | 101 | | using (writer.LockTiles(stackalloc[] { tile.TileId, partner })) |
| | 1802 | 102 | | { |
| | 7208 | 103 | | for (var i = start; i < end; i++) |
| | 1802 | 104 | | { |
| | 1802 | 105 | | CreateBoundaryEdge(writer, globalIdSet, crossings[i]); |
| | 1802 | 106 | | arrived.Add(crossings[i].GlobalEdgeId); |
| | 1802 | 107 | | } |
| | 1802 | 108 | | } |
| | | 109 | | |
| | 1802 | 110 | | start = end; |
| | 1802 | 111 | | } |
| | | 112 | | |
| | | 113 | | // ---- phase 3: restrictions ---- |
| | 1928 | 114 | | ResolveRestrictions(writer, tile, globalIdSet, arrived); |
| | | 115 | | |
| | | 116 | | // Give back the headroom geometric growth took. The growth is what makes the appends above |
| | | 117 | | // linear; the slack is what would otherwise stay resident for the life of the process, and |
| | | 118 | | // that reaches even the hot regime, which does no inserts at all. |
| | 1928 | 119 | | writer.TrimTile(tile.TileId); |
| | 1928 | 120 | | } |
| | | 121 | | |
| | | 122 | | /// <summary> |
| | | 123 | | /// Registers every internal edge's GlobalEdgeId → EdgeId mapping, collecting the ids it wrote. |
| | | 124 | | /// </summary> |
| | | 125 | | /// <remarks> |
| | | 126 | | /// The collected ids are what a pending restriction can be waiting for, so they drive the |
| | | 127 | | /// targeted retry instead of a full pass over the pending list. |
| | | 128 | | /// </remarks> |
| | | 129 | | private static int RegisterInternalEdges(StandaloneNetworkTile tile, GlobalNetworkManager globalIdSet, |
| | | 130 | | List<GlobalEdgeId> arrived) |
| | 1928 | 131 | | { |
| | 1928 | 132 | | var registered = 0; |
| | 1928 | 133 | | var tileEnumerator = new NetworkTileEnumerator(); |
| | 1928 | 134 | | tileEnumerator.MoveTo(tile.NetworkTile); |
| | 1928 | 135 | | var tileId = tile.TileId; |
| | 15108 | 136 | | for (uint v = 0; v < tile.NetworkTile.VertexCount; v++) |
| | 5626 | 137 | | { |
| | 5626 | 138 | | var vertexId = new VertexId(tileId, v); |
| | 5626 | 139 | | if (!tileEnumerator.MoveTo(vertexId)) continue; |
| | | 140 | | |
| | 13022 | 141 | | while (tileEnumerator.MoveNext()) |
| | 7396 | 142 | | { |
| | | 143 | | // only process forward edges to avoid double registration. |
| | 11094 | 144 | | if (!tileEnumerator.Forward) continue; |
| | | 145 | | |
| | 3698 | 146 | | var globalEdgeId = tileEnumerator.GlobalEdgeId; |
| | 3698 | 147 | | if (globalEdgeId != null) |
| | 3698 | 148 | | { |
| | 3698 | 149 | | globalIdSet.EdgeIdSet.Set(globalEdgeId.Value, tileEnumerator.EdgeId); |
| | | 150 | | |
| | 3698 | 151 | | arrived.Add(globalEdgeId.Value); |
| | 3698 | 152 | | registered++; |
| | 3698 | 153 | | } |
| | 3698 | 154 | | } |
| | 5626 | 155 | | } |
| | | 156 | | |
| | 1928 | 157 | | return registered; |
| | 1928 | 158 | | } |
| | | 159 | | |
| | | 160 | | /// One half of a boundary crossing matched with the other, ready to become an edge. |
| | | 161 | | private readonly record struct MatchedCrossing( |
| | 5406 | 162 | | GlobalEdgeId GlobalEdgeId, |
| | 3604 | 163 | | bool IsIncoming, |
| | 1802 | 164 | | VertexId Vertex, |
| | 1802 | 165 | | (string key, string value)[] Attributes, |
| | 1802 | 166 | | uint EdgeTypeId, |
| | 5778 | 167 | | VertexId OtherVertex); |
| | | 168 | | |
| | | 169 | | /// <summary> |
| | | 170 | | /// Claims the crossings whose other half has already arrived, recording the rest. |
| | | 171 | | /// </summary> |
| | | 172 | | /// <remarks> |
| | | 173 | | /// Returns the matches instead of creating the edges here, so that no tile lock is taken |
| | | 174 | | /// while still walking the tile — which is what keeps phase 1 free of any lock ordering. |
| | | 175 | | /// </remarks> |
| | | 176 | | private static List<MatchedCrossing> ClaimBoundaryCrossings(StandaloneNetworkTile tile, |
| | | 177 | | GlobalNetworkManager globalIdSet) |
| | 1928 | 178 | | { |
| | 1928 | 179 | | var matched = new List<MatchedCrossing>(); |
| | 13112 | 180 | | foreach (var (isIncoming, globalEdgeId, vertex, attributes, edgeTypeId) in tile.GetBoundaryCrossings()) |
| | 3664 | 181 | | { |
| | | 182 | | // Materialised before the claim: the stored half outlives this tile's enumerator, and |
| | | 183 | | // the claim may hand it to the other tile's thread at any moment. |
| | 3664 | 184 | | var ownAttributes = attributes.ToArray(); |
| | | 185 | | |
| | | 186 | | // Claim-or-record in one step. Reading, then creating the edge, then removing would |
| | | 187 | | // let two tiles each see the other's half and each create the edge; the claim makes |
| | | 188 | | // exactly one of them the winner. |
| | 3664 | 189 | | if (globalIdSet.TryClaimBoundaryCrossing(globalEdgeId, |
| | 3664 | 190 | | (vertex, ownAttributes, edgeTypeId, isIncoming), out var pending)) |
| | 1802 | 191 | | { |
| | 1802 | 192 | | matched.Add(new MatchedCrossing(globalEdgeId, isIncoming, vertex, ownAttributes, |
| | 1802 | 193 | | edgeTypeId, pending.vertex)); |
| | 1802 | 194 | | } |
| | | 195 | | |
| | | 196 | | // No else: when the claim fails this tile's half has already been recorded by the |
| | | 197 | | // same call, and the other tile will find it. |
| | 3664 | 198 | | } |
| | | 199 | | |
| | 1928 | 200 | | return matched; |
| | 1928 | 201 | | } |
| | | 202 | | |
| | | 203 | | /// <summary> |
| | | 204 | | /// Creates one boundary edge. Caller holds the locks for both tiles. |
| | | 205 | | /// </summary> |
| | | 206 | | private static void CreateBoundaryEdge(RoutingNetworkWriter writer, GlobalNetworkManager globalIdSet, |
| | | 207 | | MatchedCrossing crossing) |
| | 1802 | 208 | | { |
| | | 209 | | // isIncoming=true: vertex is at way tail, other is at way head. |
| | 1802 | 210 | | var tail = crossing.IsIncoming ? crossing.Vertex : crossing.OtherVertex; |
| | 1802 | 211 | | var head = crossing.IsIncoming ? crossing.OtherVertex : crossing.Vertex; |
| | | 212 | | |
| | 1802 | 213 | | var length = writer.ComputeEdgeLength(tail, head); |
| | 1802 | 214 | | var newEdge = writer.AddEdge(tail, head, null, crossing.Attributes, |
| | 1802 | 215 | | crossing.EdgeTypeId, length, crossing.GlobalEdgeId); |
| | | 216 | | |
| | | 217 | | // register boundary edge's GlobalEdgeId → EdgeId mapping. |
| | 1802 | 218 | | globalIdSet.EdgeIdSet.Set(crossing.GlobalEdgeId, newEdge); |
| | 1802 | 219 | | } |
| | | 220 | | |
| | | 221 | | /// Resolves this tile's restrictions, then retries everything still pending. |
| | | 222 | | private static void ResolveRestrictions(RoutingNetworkWriter writer, StandaloneNetworkTile tile, |
| | | 223 | | GlobalNetworkManager globalIdSet, IReadOnlyList<GlobalEdgeId> arrived) |
| | 1928 | 224 | | { |
| | 1928 | 225 | | var seen = 0; |
| | 1928 | 226 | | var parked = 0; |
| | 7644 | 227 | | foreach (var (edges, isProhibitory, turnCostTypeId, restrictionAttributes) in tile.GetGlobalRestrictions()) |
| | 930 | 228 | | { |
| | 930 | 229 | | var globalRestriction = new GlobalRestriction( |
| | 1860 | 230 | | edges.Select(e => e.globalEdgeId), |
| | 930 | 231 | | isProhibitory, |
| | 930 | 232 | | restrictionAttributes.ToArray()); |
| | | 233 | | |
| | 930 | 234 | | seen++; |
| | 930 | 235 | | if (!TryResolveRestriction(globalRestriction, globalIdSet, writer)) |
| | 576 | 236 | | { |
| | 576 | 237 | | parked++; |
| | 576 | 238 | | globalIdSet.AddPendingRestriction(globalRestriction); |
| | 576 | 239 | | } |
| | 930 | 240 | | } |
| | | 241 | | |
| | | 242 | | // Retry only the restrictions waiting for an edge this insert added. A full pass here |
| | | 243 | | // re-examined every pending restriction on every insert - 535,147 examinations for 2,335 |
| | | 244 | | // resolutions over one cold block. |
| | 1928 | 245 | | globalIdSet.RetryPendingRestrictionsFor(arrived, |
| | 3408 | 246 | | r => TryResolveRestriction(r, globalIdSet, writer)); |
| | 1928 | 247 | | } |
| | | 248 | | |
| | | 249 | | private static bool TryResolveRestriction(GlobalRestriction globalRestriction, |
| | | 250 | | GlobalNetworkManager globalIdSet, RoutingNetworkWriter writer) |
| | 2410 | 251 | | { |
| | | 252 | | // try to resolve all GlobalEdgeIds to EdgeIds. |
| | 2410 | 253 | | if (!globalRestriction.TryBuildNetworkRestriction(GetEdge, out var networkRestriction)) |
| | 1480 | 254 | | return false; |
| | | 255 | | |
| | 930 | 256 | | if (networkRestriction!.Count < 2) return true; |
| | | 257 | | |
| | | 258 | | // get last edge and determine turn cost vertex. |
| | 930 | 259 | | var last = networkRestriction[^1]; |
| | 930 | 260 | | var edgeEnumerator = writer.GetEdgeEnumerator(); |
| | 930 | 261 | | if (!edgeEnumerator.MoveTo(last.edge, last.forward)) |
| | 0 | 262 | | return false; |
| | 930 | 263 | | var turnCostVertex = edgeEnumerator.Tail; |
| | | 264 | | |
| | 930 | 265 | | var secondToLast = networkRestriction[^2]; |
| | | 266 | | |
| | 930 | 267 | | if (networkRestriction.IsProhibitory) |
| | 930 | 268 | | { |
| | | 269 | | // prohibitory: add a single cost entry forbidding this specific turn. |
| | 930 | 270 | | var costs = new uint[,] { { 0, 1 }, { 0, 0 } }; |
| | 930 | 271 | | writer.AddTurnCosts(turnCostVertex, networkRestriction.Attributes, |
| | 930 | 272 | | [secondToLast.edge, last.edge], costs, |
| | 930 | 273 | | networkRestriction.Take(networkRestriction.Count - 2).Select(x => x.edge)); |
| | | 274 | | |
| | 930 | 275 | | } |
| | | 276 | | else |
| | 0 | 277 | | { |
| | | 278 | | // mandatory: add cost for every *other* edge at the vertex. |
| | 0 | 279 | | if (!edgeEnumerator.MoveTo(secondToLast.edge, secondToLast.forward)) |
| | 0 | 280 | | return false; |
| | 0 | 281 | | var to = edgeEnumerator.Head; |
| | | 282 | | |
| | 0 | 283 | | edgeEnumerator.MoveTo(to); |
| | 0 | 284 | | while (edgeEnumerator.MoveNext()) |
| | 0 | 285 | | { |
| | 0 | 286 | | if (edgeEnumerator.EdgeId == secondToLast.edge || |
| | 0 | 287 | | edgeEnumerator.EdgeId == last.edge) continue; |
| | | 288 | | |
| | 0 | 289 | | var costs = new uint[,] { { 0, 1 }, { 0, 0 } }; |
| | 0 | 290 | | writer.AddTurnCosts(turnCostVertex, networkRestriction.Attributes, |
| | 0 | 291 | | [secondToLast.edge, edgeEnumerator.EdgeId], costs, |
| | 0 | 292 | | networkRestriction.Take(networkRestriction.Count - 2).Select(x => x.edge)); |
| | 0 | 293 | | } |
| | 0 | 294 | | } |
| | | 295 | | |
| | 930 | 296 | | return true; |
| | | 297 | | |
| | | 298 | | (EdgeId edge, bool forward)? GetEdge(GlobalEdgeId geid, bool isFirst) |
| | 4135 | 299 | | { |
| | | 300 | | // exact match short-circuit (cheap check before walking). |
| | 4135 | 301 | | if (globalIdSet.EdgeIdSet.TryGet(geid, out var edgeId)) |
| | 11 | 302 | | return (edgeId, true); |
| | 4124 | 303 | | if (globalIdSet.EdgeIdSet.TryGet(geid.GetInverted(), out edgeId)) |
| | 13 | 304 | | return (edgeId, false); |
| | | 305 | | |
| | | 306 | | // walk from the chain-anchor end; first edge anchors at Head, every |
| | | 307 | | // subsequent edge anchors at Tail (chain invariant: previous.Head == |
| | | 308 | | // current.Tail). |
| | 4111 | 309 | | return GlobalRestrictionExtensions.WalkFromAnchor(geid, isFirst, |
| | 4111 | 310 | | globalIdSet.EdgeIdSet.TryGet); |
| | 4135 | 311 | | } |
| | 2410 | 312 | | } |
| | | 313 | | } |