Line data Source code
1 : /****************************************************************************/
2 : // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.dev/sumo
3 : // Copyright (C) 2001-2026 German Aerospace Center (DLR) and others.
4 : // This program and the accompanying materials are made available under the
5 : // terms of the Eclipse Public License 2.0 which is available at
6 : // https://www.eclipse.org/legal/epl-2.0/
7 : // This Source Code may also be made available under the following Secondary
8 : // Licenses when the conditions for such availability set forth in the Eclipse
9 : // Public License 2.0 are satisfied: GNU General Public License, version 2
10 : // or later which is available at
11 : // https://www.gnu.org/licenses/old-licenses/gpl-2.0-standalone.html
12 : // SPDX-License-Identifier: EPL-2.0 OR GPL-2.0-or-later
13 : /****************************************************************************/
14 : /// @file CCHMetricFamily.h
15 : /// @author Pranav Sateesh
16 : /// @date 2026
17 : ///
18 : // A family of per-vehicle-type CCH metrics over one shared CCHGraph -- the
19 : // MetricProvider machinery behind CCHRouter, shared between the simulation
20 : // and duarouter the same way CCHGraph shares the topology.
21 : //
22 : // Keying by the vehicle TYPE (rather than the class) makes everything the
23 : // effort function reads from the vehicle exact per metric: the type's
24 : // maximum speed, per-class edge speed restrictions, routing preferences,
25 : // the bicycle speed table and one frozen weights.random-factor realization;
26 : // only individual speed-factor draws within one type share a metric (the
27 : // same approximation the CH family makes with its per-class prototype
28 : // vehicles, but at finer granularity).
29 : //
30 : // Two modes:
31 : //
32 : // STATIC -- weights never change while a (type, weight period) pair is in
33 : // use. Metrics are customized lazily on the first query of a pair under a
34 : // mutex and cached (duarouter, marouter and the simulation's free-flow
35 : // routers). When the efforts do change between queries -- a runtime
36 : // permission flip, marouter's travel times after an assignment iteration
37 : // -- the host flags it (flagStale) and every cached metric is refilled
38 : // and re-customized on the next query.
39 : //
40 : // LIVE -- weights track an adaptive speed table (the rerouting device).
41 : // Metrics are double-buffered: worker threads acquire-load the published
42 : // front while the owner refills and customizes the back at its barrier
43 : // and flips, so queries never observe a metric mid-customization. The
44 : // customize is sparse (RoutingKit partial customization over the edges
45 : // whose effort actually moved, behind a configurable deadband) with
46 : // wholesale refills after permission flips. Staleness is bounded to one
47 : // barrier -- CH's weightPeriod semantics: once any metric exists,
48 : // customize(now) must run at every barrier where an effort moved (see
49 : // atBarrier), and an epoch pair guards the bound as an invariant.
50 : //
51 : // The family is intentionally ignorant of WHEN to customize -- only the
52 : // owner knows when no query is in flight (the simulation's adaptation
53 : // barrier, duarouter's mutex) -- and of HOW reference vehicles are built
54 : // (injected factory; V construction is host-specific).
55 : /****************************************************************************/
56 : #pragma once
57 : #include <config.h>
58 :
59 : #include <atomic>
60 : #include <cmath>
61 : #include <limits>
62 : #include <map>
63 : #include <memory>
64 : #include <mutex>
65 : #include <utility>
66 : #include <vector>
67 : #include <utils/common/SUMOTime.h>
68 : #include <utils/common/SUMOVehicleClass.h>
69 : #include <utils/router/CCHGraph.h>
70 :
71 :
72 : // ===========================================================================
73 : // class definitions
74 : // ===========================================================================
75 : /**
76 : * @class CCHMetricFamily
77 : * @brief per-vehicle-type CCH metric store over a shared CCHGraph
78 : *
79 : * @tparam E the edge type (MSEdge / ROEdge)
80 : * @tparam V the vehicle type of the effort callback (SUMOVehicle / ROVehicle)
81 : * @tparam K the vehicle-type key (MSVehicleType / SUMOVTypeParameter); used
82 : * only as a stable map key, never dereferenced
83 : */
84 : template<class E, class V, class K>
85 : class CCHMetricFamily {
86 : public:
87 : typedef CCHGraph<E, V> Graph;
88 : typedef typename Graph::EffortOperation EffortOperation;
89 : typedef const RoutingKit::CustomizableContractionHierarchyMetric* MetricPtr;
90 : /// @brief builds an OWNED effort-reference vehicle for a type: never
91 : /// registered, counted or inserted -- it exists only so every fill of
92 : /// that type's metric evaluates the same reference (deterministic speed
93 : /// factor and frozen random realization are the factory's business).
94 : /// The second argument is the ensemble slot (see the LIVE constructor);
95 : /// slot 0 must reproduce the pre-ensemble reference exactly, further
96 : /// slots give distinct frozen weights.random-factor realizations
97 : /// (typically by varying the reference vehicle's id, which seeds them)
98 : typedef V* (*RefVehicleFactory)(const K*, int);
99 : /// @brief post-fill hook on the input weights (STATIC mode), e.g.
100 : /// duarouter masking the edges that restrict a type to inf_weight
101 : typedef void (*WeightPatch)(const Graph*, const V*, std::vector<unsigned>&);
102 :
103 : /** @brief construct a STATIC family (lazy build per (type, period))
104 : * @param[in] graph the shared topology
105 : * @param[in] fillEffort the effort the weights are computed from
106 : * @param[in] begin begin of the weight-period grid
107 : * @param[in] weightPeriod period length; SUMOTime_MAX = a single period
108 : * @param[in] factory reference-vehicle factory; nullptr = fill with the
109 : * QUERYING vehicle (each pair is customized exactly once, so the first
110 : * vehicle of a type is that type's reference -- duarouter's contract)
111 : * @param[in] patch optional post-fill weight hook */
112 655 : CCHMetricFamily(const Graph* graph, EffortOperation fillEffort,
113 : SUMOTime begin, SUMOTime weightPeriod,
114 : RefVehicleFactory factory, WeightPatch patch) :
115 655 : myGraph(graph), myFillEffort(fillEffort), myGateEffort(nullptr),
116 655 : myFactory(factory), myPatch(patch), myLive(false),
117 655 : myBegin(begin), myWeightPeriod(weightPeriod),
118 4585 : myUpdateFactor(1.), myUpdateConstant(0.) {
119 655 : }
120 :
121 : /** @brief construct a LIVE family (double-buffered, barrier-customized)
122 : * @param[in] graph the shared topology
123 : * @param[in] fillEffort the (possibly per-type) effort the weights are
124 : * computed from, evaluated with the type's reference vehicle
125 : * @param[in] gateEffort the type-INDEPENDENT effort used by the deadband
126 : * (evaluated with a null vehicle: per-type extras are static
127 : * multipliers that cancel out of the moved-or-not decision)
128 : * @param[in] updateFactor / updateConstant the deadband: an edge's arcs
129 : * are only refilled when its gate effort moved by MORE than BOTH the
130 : * relative factor AND the absolute constant (seconds) since this
131 : * buffer last applied it -- the sufficientSaving() analog. The
132 : * moving-average speed filter smears every traffic event into many
133 : * ticks of sub-percent drift; without a deadband that drift marks
134 : * thousands of arcs per barrier and partial re-customization
135 : * degenerates (RoutingKit documents it for the sparse "new traffic
136 : * jam" case). 1/0 = every change propagates. Rejected edges stay
137 : * pending and their drift accumulates against the same applied value,
138 : * so a slow trend eventually passes while filter jitter never does.
139 : * @param[in] factory reference-vehicle factory (required in LIVE mode)
140 : * @param[in] ensembleK how many frozen weights.random-factor
141 : * realizations (= metrics) to keep per type. The exact routers draw a
142 : * fresh perturbation per vehicle; a shared metric freezes ONE
143 : * realization, losing the feature's route diversity. With K > 1 every
144 : * type keeps K metrics -- each filled with its own reference vehicle
145 : * (factory slot k) and therefore its own frozen realization -- and a
146 : * vehicle is assigned its slot by a stable hash of its id, so each
147 : * vehicle persistently routes on one of K perturbed networks:
148 : * K = 1 is exactly the single-realization behavior, growing K
149 : * converges toward the exact routers' per-vehicle diversity at K x
150 : * customization and memory cost. Pointless without
151 : * weights.random-factor (the K references fill identical weights). */
152 231 : CCHMetricFamily(const Graph* graph, EffortOperation fillEffort,
153 : EffortOperation gateEffort, double updateFactor,
154 : double updateConstant, RefVehicleFactory factory,
155 : int ensembleK = 1) :
156 231 : myGraph(graph), myFillEffort(fillEffort), myGateEffort(gateEffort),
157 231 : myFactory(factory), myPatch(nullptr), myLive(true),
158 231 : myBegin(0), myWeightPeriod(SUMOTime_MAX),
159 231 : myUpdateFactor(updateFactor), myUpdateConstant(updateConstant),
160 1617 : myEnsembleK(ensembleK > 1 ? ensembleK : 1) {
161 : const unsigned space = myGraph->edgeIdSpace();
162 693 : for (int i = 0; i < 2; i++) {
163 : // NaN = "never applied": the first pending occurrence always
164 : // passes the deadband and primes the entry
165 462 : myAppliedEffort[i].assign(space, std::numeric_limits<double>::quiet_NaN());
166 462 : myPendingFlag[i].assign(space, 0);
167 : }
168 231 : }
169 :
170 332 : ~CCHMetricFamily() {
171 1793 : for (LiveMetric* c : myLiveMetrics) {
172 1461 : delete c->refVehicle;
173 1461 : delete c;
174 : }
175 436 : for (auto& item : myStaticMetrics) {
176 104 : delete item.second.refVehicle;
177 : }
178 2656 : }
179 :
180 : /// @name STATIC mode
181 : /// @{
182 :
183 : /** @brief the metric for (type key, period of @p time), built on the
184 : * first query of the pair; nullptr before init. Thread-safe: the mutex
185 : * serialises concurrent first queries from parallel routing threads
186 : * (satisfying primeClassMask's synchronization contract); afterwards the
187 : * map is read-only for that key (map references are address-stable).
188 : * A pending flagStale() first refills and re-customizes every cached
189 : * metric from the live efforts and permissions -- in place, so the
190 : * flagging host guarantees that no query is in flight (the simulation's
191 : * main thread, marouter's reset between two iterations). */
192 21273 : MetricPtr get(const K* key, SUMOVehicleClass vClass, SUMOTime time, const V* veh) {
193 21273 : std::lock_guard<std::mutex> lock(myStaticLock);
194 21273 : if (myStale) {
195 102 : for (auto& item : myStaticMetrics) {
196 49 : StaticMetric& sm = item.second;
197 56 : fillStatic(sm, item.first.second, time, sm.refVehicle != nullptr ? sm.refVehicle : veh, veh);
198 49 : sm.metric->customize();
199 : }
200 53 : myStale = false;
201 : }
202 : const int period = periodOf(time);
203 : const std::pair<const K*, int> mapKey(key, period);
204 : auto it = myStaticMetrics.find(mapKey);
205 21273 : if (it == myStaticMetrics.end()) {
206 523 : StaticMetric& sm = myStaticMetrics[mapKey];
207 523 : sm.vClass = vClass;
208 : const V* ref = veh;
209 523 : if (myFactory != nullptr) {
210 104 : sm.refVehicle = myFactory(key, 0);
211 : ref = sm.refVehicle;
212 : }
213 523 : fillStatic(sm, period, time, ref, veh);
214 523 : sm.metric.reset(new RoutingKit::CustomizableContractionHierarchyMetric(
215 523 : myGraph->cch(), sm.weights));
216 523 : sm.metric->customize();
217 523 : return sm.metric.get();
218 : }
219 20750 : return it->second.metric.get();
220 : }
221 :
222 : /// @brief the end of the weight period containing the given time
223 : /// (SUMOTime_MAX when the weights are static); CCHRouter's PeriodEnd hook
224 : SUMOTime periodEnd(SUMOTime time) const {
225 788 : if (myWeightPeriod <= 0 || myWeightPeriod == SUMOTime_MAX) {
226 : return SUMOTime_MAX;
227 : }
228 788 : return myBegin + (periodOf(time) + 1) * myWeightPeriod;
229 : }
230 :
231 : /** @brief the efforts behind the cached metrics changed -- a runtime
232 : * permission change in the simulation (the caller must also invalidate
233 : * the graph's class masks), or marouter's travel times after an
234 : * assignment iteration (CCHRouter::reset): every cached metric is
235 : * refilled and re-customized on the next get(). */
236 : void flagStale() {
237 74 : std::lock_guard<std::mutex> lock(myStaticLock);
238 74 : myStale = true;
239 48 : }
240 :
241 : /// @brief flagStale() under the simulation's name for the permission case
242 : void flagPermissionsStale() {
243 : flagStale();
244 26 : }
245 : /// @}
246 :
247 : /// @name LIVE mode
248 : /// @{
249 :
250 : /// @brief allocate the metric state (all ensemble slots) for one type;
251 : /// call only while no query is in flight (seeding at init, or the
252 : /// customization barrier)
253 1461 : void seedKey(const K* key) {
254 : if (myByKey.count(key) == 0) {
255 1461 : std::vector<LiveMetric*>& slots = myByKey[key];
256 2922 : for (int k = 0; k < myEnsembleK; k++) {
257 1461 : slots.push_back(buildLiveMetric(key, k));
258 : }
259 : }
260 1461 : }
261 :
262 : /// @brief queue an edge whose gate effort changed (both buffers; the
263 : /// deadband applies later, at the customize barrier)
264 1115421 : void markDirty(const E* e) {
265 1115421 : const int id = e->getNumericalID();
266 1115421 : if (id < 0 || id >= (int)myPendingFlag[0].size()) {
267 : return;
268 : }
269 3346263 : for (int i = 0; i < 2; i++) {
270 2230842 : if (!myPendingFlag[i][id]) {
271 1172916 : myPendingFlag[i][id] = 1;
272 1172916 : myPendingList[i].push_back(e);
273 : }
274 : }
275 : }
276 :
277 : /** @brief a runtime permission change (closure / re-opening) hit this
278 : * edge: queue it bypassing the deadband and divert every query to the
279 : * exact fallback until customize() has refilled both buffers wholesale
280 : * (the sparse path cannot repair tail-side arcs of a connection-level
281 : * change). The caller must also invalidate the graph's class masks. */
282 20 : void invalidateEdge(const E* e) {
283 : const int id = e->getNumericalID();
284 20 : if (id < 0 || id >= (int)myPendingFlag[0].size()) {
285 : return;
286 : }
287 20 : markDirty(e);
288 : // NaN sentinel: the deadband always passes, so the flip reaches the
289 : // metric at the next barrier even though the speed table did not move
290 20 : myAppliedEffort[0][id] = std::numeric_limits<double>::quiet_NaN();
291 20 : myAppliedEffort[1][id] = std::numeric_limits<double>::quiet_NaN();
292 20 : myFullFillsPending = 2;
293 : myMetricStale.store(true, std::memory_order_release);
294 : }
295 :
296 : /** @brief the owner's customization barrier: bump the speed epoch when
297 : * an effort moved and re-customize when it matters. Lazy, following the
298 : * CH weightPeriod pattern: metric state is only built for types somebody
299 : * routes on (myLiveMetrics stays empty in a run that never routes, which
300 : * then pays nothing here). Once any metric exists, every barrier where
301 : * an effort moved re-customizes, so a query never sees a metric more
302 : * than one barrier old -- CH's weightPeriod bound. The queried flag only
303 : * bootstraps type creation; a pending permission flip forces the
304 : * customize even without queries. */
305 287851 : void atBarrier(double now, bool effortsMoved) {
306 287851 : if (effortsMoved) {
307 : mySpeedEpoch.fetch_add(1, std::memory_order_release);
308 : }
309 : if (myQueried.exchange(false, std::memory_order_acq_rel)
310 271261 : || myMetricStale.load(std::memory_order_acquire)
311 559104 : || (effortsMoved && !myLiveMetrics.empty())) {
312 211024 : customize(now);
313 : }
314 287851 : }
315 :
316 : /** @brief refill + customize + publish every type's metric from the live
317 : * efforts and permissions. Call only while no query is in flight (the
318 : * publish itself is lock-free: release store here, acquire loads on the
319 : * query hot path). */
320 211255 : void customize(double now) {
321 : // types that queried since the last barrier without a metric
322 : // (streamed route files, TraCI-added types): create their state now
323 : {
324 211255 : std::lock_guard<std::mutex> lock(myWantedLock);
325 211255 : for (const K* key : myWantedKeys) {
326 0 : seedKey(key);
327 : }
328 : myWantedKeys.clear();
329 : }
330 211255 : if (myLiveMetrics.empty()) {
331 0 : return;
332 : }
333 : // buffers flip in lockstep across types (every call processes all)
334 211255 : const int backShared = 1 - myLiveMetrics.front()->frontIndex;
335 : // Permission flip pending: run a FULL refill on this pass's back
336 : // buffer (the other buffer gets its full refill on the next pass --
337 : // myFullFillsPending counts both down). The fills below re-prime the
338 : // graph's connection masks, which the flip's caller invalidated.
339 : bool forceFull = false;
340 211255 : if (myFullFillsPending > 0) {
341 22 : myFullFillsPending--;
342 : forceFull = true;
343 : }
344 : // Deadband pass, once, on the type-shared gate effort: accept edges
345 : // whose effort moved by more than BOTH bounds since this buffer last
346 : // applied them; rejected edges stay pending (see the constructor doc)
347 : std::vector<const E*> accepted;
348 211255 : if (!forceFull && myLiveMetrics.front()->metric[backShared] != nullptr) {
349 : std::vector<const E*> stillPending;
350 3157245 : for (const E* e : myPendingList[backShared]) {
351 : const int id = e->getNumericalID();
352 2946455 : const double effNow = myGateEffort(e, nullptr, now);
353 2946455 : const double effApplied = myAppliedEffort[backShared][id];
354 : bool pass = true;
355 2946455 : if (!std::isnan(effApplied) && effApplied > 0. && effNow > 0.) {
356 : const double hi = MAX2(effNow, effApplied);
357 : const double lo = MIN2(effNow, effApplied);
358 2933724 : pass = (hi / lo > myUpdateFactor) && (hi - lo > myUpdateConstant);
359 : }
360 : if (pass) {
361 1168553 : accepted.push_back(e);
362 1168553 : myAppliedEffort[backShared][id] = effNow;
363 1168553 : myPendingFlag[backShared][id] = 0;
364 : } else {
365 1777902 : stillPending.push_back(e);
366 : }
367 : }
368 : myPendingList[backShared].swap(stillPending);
369 210790 : }
370 1564792 : for (LiveMetric* c : myLiveMetrics) {
371 1353537 : const int back = 1 - c->frontIndex;
372 : // Fill from the live efforts, masking arcs the class is not
373 : // permitted on -- this is where per-class permissions AND active
374 : // closures become inf_weight. The fill reference is the type's
375 : // OWNED refVehicle, so the effort captures the type's extras
376 : // exactly (including each folded via edge inside viaChainEffort)
377 : // and freezes ONE random realization per metric -- the same
378 : // approximation CHRouterWrapper makes per hierarchy; exact
379 : // per-vehicle randomization remains the domain of the exact
380 : // routers.
381 1353537 : if (c->metric[back] == nullptr) {
382 : // first use of this buffer for THIS type only (streamed/late
383 : // vType): no previous state to diff against for this type,
384 : // but every other already-running type's sparse deadband
385 : // state is unaffected, so this branch must NOT trigger the
386 : // shared wipe below (which would reset the type-shared
387 : // myPendingList/myAppliedEffort for everybody just because
388 : // one type is new)
389 2806 : myGraph->fillInputWeights(myFillEffort, c->vClass, c->refVehicle, now, c->weight[back]);
390 2806 : c->metric[back] = std::make_shared<RoutingKit::CustomizableContractionHierarchyMetric>(
391 2806 : myGraph->cch(), c->weight[back]);
392 2806 : c->metric[back]->customize(); // serial; avoids OpenMP oversubscription under FOX
393 1350731 : } else if (forceFull) {
394 : // permission flip: wholesale refill in place from the
395 : // re-primed masks and live permissions (the metric already
396 : // references weight[back]), then a full customize. This is
397 : // the ONLY case that invalidates the type-shared deadband
398 : // state below, since it is the only one that actually
399 : // changes what "applied" means for every type at once.
400 140 : myGraph->fillInputWeights(myFillEffort, c->vClass, c->refVehicle, now, c->weight[back]);
401 140 : c->metric[back]->customize();
402 : } else {
403 : // SPARSE PATH: metric[back] is the customization of the
404 : // current contents of weight[back]. Recompute only the arcs
405 : // of accepted edges (edge->arc reverse image), write the
406 : // ones that moved, and propagate through affected triangles
407 : // only. Cost scales with traffic transitions, not with the
408 : // network.
409 : std::vector<unsigned>& applied = c->weight[back];
410 1350591 : c->partial->reset(myGraph->cch());
411 : unsigned changed = 0;
412 8563503 : for (const E* e : accepted) {
413 24148276 : for (const unsigned a : myGraph->arcsOfEdge(e)) {
414 16935364 : const unsigned newW = myGraph->computeArcWeight(a, myFillEffort, c->vClass, c->refVehicle, now);
415 16935364 : if (newW != applied[a]) {
416 9583256 : applied[a] = newW;
417 9583256 : c->partial->update_arc(a); // takes INPUT arc ids
418 9583256 : ++changed;
419 : }
420 : }
421 : }
422 1350591 : if (changed > 0) {
423 611989 : c->partial->customize(*c->metric[back]);
424 : }
425 : }
426 : // publish lock-free: release store at the barrier, worker
427 : // acquire-loads on the hot path
428 1353537 : c->frontIndex = back;
429 : c->front.store(c->metric[back].get(), std::memory_order_release);
430 : }
431 211255 : if (forceFull) {
432 : // a permission flip's full refill matched every arc to the live
433 : // efforts/masks for this buffer: type-shared deadband entries
434 : // are stale; NaN re-arms the first-change auto-pass. (A plain
435 : // per-type first-fill above does NOT reach here -- it must not
436 : // wipe deadband state that other, already-running types still
437 : // depend on.)
438 97 : for (const E* e : myPendingList[backShared]) {
439 75 : myPendingFlag[backShared][e->getNumericalID()] = 0;
440 : }
441 : myPendingList[backShared].clear();
442 22 : myAppliedEffort[backShared].assign(myAppliedEffort[backShared].size(),
443 22 : std::numeric_limits<double>::quiet_NaN());
444 : }
445 : // every published front now reflects the live permissions (the other
446 : // buffer, if still pending a full refill, is repaired before its
447 : // next publish) and the live efforts as of this barrier (both epoch
448 : // counters only move on the owner's thread at the barrier, so the
449 : // pair cannot tear)
450 : myMetricStale.store(false, std::memory_order_release);
451 : myPublishedEpoch.store(mySpeedEpoch.load(std::memory_order_relaxed),
452 : std::memory_order_release);
453 211255 : }
454 :
455 : /** @brief the published metric for a type key and querying vehicle id
456 : * (the id picks the ensemble slot -- see the LIVE constructor), or
457 : * nullptr if the query must route on the exact fallback. Query hot
458 : * path, any thread. */
459 58844 : MetricPtr published(const K* key, const std::string& vehID) {
460 : const auto it = myByKey.find(key);
461 58844 : if (it == myByKey.end()) {
462 : // streamed-in type without a metric yet: register it for
463 : // creation at the next barrier and fall back
464 : {
465 0 : std::lock_guard<std::mutex> lock(myWantedLock);
466 0 : myWantedKeys.push_back(key);
467 : }
468 : myQueried.store(true, std::memory_order_relaxed);
469 0 : return nullptr;
470 : }
471 : // mark the metric as consumed. Test before set: an unconditional
472 : // store from every query would ping-pong the cache line between
473 : // cores; the read is shared and the store fires once per barrier
474 : // window (relaxed: only gates bootstrap/re-arm, never visibility)
475 58844 : if (!myQueried.load(std::memory_order_relaxed)) {
476 : myQueried.store(true, std::memory_order_relaxed);
477 : }
478 : // A permission flip that is not yet customized in makes every
479 : // published metric unusable: it may still route THROUGH a
480 : // just-closed edge, and CCHRouter's coverage test consults the LIVE
481 : // permissions, which would wrongly bless the query. Route exactly
482 : // until the barrier repairs the metrics.
483 58844 : if (myMetricStale.load(std::memory_order_acquire)) {
484 : return nullptr;
485 : }
486 : // Safety invariant: never serve a metric the efforts have moved away
487 : // from -- the exact routers see live weights and CH is bounded to
488 : // one weightPeriod. atBarrier re-customizes at every moved barrier
489 : // once metrics exist, so this cannot fire in steady state; if a gap
490 : // ever opens, this burst routes on the exact fallback (live weights)
491 : // and the queried flag set above arms the customize that closes it.
492 58808 : if (myPublishedEpoch.load(std::memory_order_acquire)
493 : != mySpeedEpoch.load(std::memory_order_acquire)) {
494 : return nullptr;
495 : }
496 : // stable slot assignment: FNV-1a over the id (std::hash is
497 : // implementation-defined and would break cross-platform test
498 : // reproducibility)
499 58808 : const LiveMetric* c = myEnsembleK == 1 ? it->second.front()
500 0 : : it->second[fnv1a(vehID) % myEnsembleK];
501 58808 : return c->front.load(std::memory_order_acquire);
502 : }
503 :
504 : /// @brief whether any type has live metric state yet
505 : bool empty() const {
506 : return myLiveMetrics.empty();
507 : }
508 : /// @}
509 :
510 : private:
511 : /// @brief per-type LIVE metric state. Heap-owned: the atomic makes it
512 : /// non-movable, so it cannot live in a map by value.
513 4383 : struct LiveMetric {
514 : std::vector<unsigned> weight[2]; // ping-pong input-weight buffers, live whole run
515 : std::shared_ptr<RoutingKit::CustomizableContractionHierarchyMetric> metric[2];
516 : std::atomic<const RoutingKit::CustomizableContractionHierarchyMetric*> front{nullptr};
517 : int frontIndex = 1; // first customize uses back = 0
518 : SUMOVehicleClass vClass = SVC_PASSENGER;
519 : /// @brief OWNED effort-reference vehicle (see RefVehicleFactory)
520 : V* refVehicle = nullptr;
521 : /// @brief partial-customization worker (queue over the shared CCH);
522 : /// one per metric -- its queue is drained by every customize()
523 : std::shared_ptr<RoutingKit::CustomizableContractionHierarchyPartialCustomization> partial;
524 : };
525 :
526 : /// @brief per-(type, period) STATIC metric state. RoutingKit metrics
527 : /// BORROW their input-weight buffer, so buffer and metric live together
528 : /// in the map (std::map nodes are address-stable).
529 523 : struct StaticMetric {
530 : std::vector<unsigned> weights;
531 : std::unique_ptr<RoutingKit::CustomizableContractionHierarchyMetric> metric;
532 : SUMOVehicleClass vClass = SVC_PASSENGER;
533 : /// @brief OWNED reference vehicle (nullptr when filling with the
534 : /// querying vehicle)
535 : V* refVehicle = nullptr;
536 : /// @brief whether the first fill (which runs the patch) is done
537 : bool filled = false;
538 : /// @brief the (arc, weight) pairs the patch wrote on the first fill,
539 : /// re-applied on every refill
540 : std::vector<std::pair<unsigned, unsigned> > patched;
541 : };
542 :
543 : /// @brief the weight period containing @p time: 0 is everything before
544 : /// begin and the whole run when the weights are static
545 : int periodOf(SUMOTime time) const {
546 22061 : if (myWeightPeriod > 0 && myWeightPeriod != SUMOTime_MAX && time > myBegin) {
547 442 : return (int)((time - myBegin) / myWeightPeriod);
548 : }
549 : return 0;
550 : }
551 :
552 : /** @brief (re)fill a STATIC metric's input weights from the live efforts.
553 : * A weight-period grid evaluates at the period's begin, so each pair is
554 : * customized once per fill; a single period evaluates at the query time
555 : * -- free-flow efforts are time-invariant anyway, and marouter's
556 : * per-iteration travel times are exactly what a Dijkstra query at that
557 : * time sees. The patch runs once, on the first fill, and what it wrote is
558 : * re-applied on every refill: the masked set depends only on the
559 : * metric's type, whereas the vehicle triggering a refill may be of
560 : * another type. */
561 572 : void fillStatic(StaticMetric& sm, int period, SUMOTime time, const V* ref, const V* veh) {
562 572 : const double fillTime = myWeightPeriod == SUMOTime_MAX
563 572 : ? STEPS2TIME(time) : STEPS2TIME(myBegin + period * myWeightPeriod);
564 572 : myGraph->fillInputWeights(myFillEffort, sm.vClass, ref, fillTime, sm.weights);
565 572 : if (!sm.filled) {
566 523 : sm.filled = true;
567 523 : if (myPatch != nullptr) {
568 419 : const std::vector<unsigned> unpatched(sm.weights);
569 419 : myPatch(myGraph, veh, sm.weights);
570 8824 : for (unsigned a = 0; a < (unsigned)sm.weights.size(); a++) {
571 8405 : if (sm.weights[a] != unpatched[a]) {
572 3 : sm.patched.emplace_back(a, sm.weights[a]);
573 : }
574 : }
575 419 : }
576 : } else {
577 49 : for (const auto& p : sm.patched) {
578 0 : sm.weights[p.first] = p.second;
579 : }
580 : }
581 572 : }
582 :
583 : /// @brief stable 64-bit FNV-1a for the ensemble slot assignment
584 : static uint64_t fnv1a(const std::string& s) {
585 : uint64_t h = 1469598103934665603ull;
586 0 : for (const char ch : s) {
587 0 : h = (h ^ (unsigned char)ch) * 1099511628211ull;
588 : }
589 : return h;
590 : }
591 :
592 : /// @brief allocate LIVE metric state for one (type, ensemble slot)
593 : /// (owner's thread only)
594 1461 : LiveMetric* buildLiveMetric(const K* key, int slot) {
595 1461 : LiveMetric* c = new LiveMetric();
596 1461 : c->refVehicle = myFactory(key, slot);
597 1461 : c->vClass = c->refVehicle->getVClass();
598 1461 : c->weight[0].resize(myGraph->arcCount());
599 1461 : c->weight[1].resize(myGraph->arcCount());
600 1461 : c->partial = std::make_shared<RoutingKit::CustomizableContractionHierarchyPartialCustomization>(myGraph->cch());
601 1461 : myLiveMetrics.push_back(c);
602 1461 : return c;
603 : }
604 :
605 : /// @brief the immutable shared topology
606 : const Graph* myGraph;
607 : /// @brief the effort the metrics are filled from
608 : EffortOperation myFillEffort;
609 : /// @brief the type-independent effort of the LIVE deadband
610 : EffortOperation myGateEffort;
611 : /// @brief reference-vehicle factory (required LIVE, optional STATIC)
612 : RefVehicleFactory myFactory;
613 : /// @brief post-fill weight hook (STATIC)
614 : WeightPatch myPatch;
615 : /// @brief LIVE or STATIC (fixed at construction)
616 : const bool myLive;
617 :
618 : /// @name STATIC state
619 : /// @{
620 : SUMOTime myBegin;
621 : SUMOTime myWeightPeriod;
622 : std::map<std::pair<const K*, int>, StaticMetric> myStaticMetrics;
623 : std::mutex myStaticLock;
624 : /// @brief the efforts changed behind the cached metrics: refill and
625 : /// re-customize them all on the next get() (see flagStale)
626 : bool myStale = false;
627 : /// @}
628 :
629 : /// @name LIVE state
630 : /// @{
631 : /// @brief the deadband bounds (see the LIVE constructor)
632 : double myUpdateFactor;
633 : double myUpdateConstant;
634 : /// @brief frozen random-factor realizations per type (see the LIVE ctor)
635 : int myEnsembleK = 1;
636 : /// @brief every type's state, in creation order (barrier iteration) and
637 : /// by key (query lookup; only mutated while no query is in flight)
638 : std::vector<LiveMetric*> myLiveMetrics;
639 : std::map<const K*, std::vector<LiveMetric*> > myByKey;
640 : /// @brief types that queried but have no metric yet (demand streams, so
641 : /// types can appear after seeding); queries register them under the lock
642 : /// and route via the fallback until the next barrier builds their state
643 : std::vector<const K*> myWantedKeys;
644 : std::mutex myWantedLock;
645 : /// @brief whether a query arrived since the last barrier (bootstraps
646 : /// type creation and re-arms after resets -- see atBarrier)
647 : std::atomic<bool> myQueried{false};
648 : /// @brief a permission flip has not yet been customized into the
649 : /// published metrics (queries divert to the exact fallback while set)
650 : std::atomic<bool> myMetricStale{false};
651 : /// @brief barrier counter of the tracked efforts and the counter value
652 : /// the published metrics were customized from: the staleness bound's
653 : /// safety invariant (see atBarrier / published). Both only change on the
654 : /// owner's thread at the barrier -- no query is in flight there -- the
655 : /// atomics just publish the values to the query threads.
656 : std::atomic<uint64_t> mySpeedEpoch{0};
657 : std::atomic<uint64_t> myPublishedEpoch{0};
658 : /// @brief how many customize passes must run a FULL refill after a
659 : /// permission flip: 2 = both ping-pong buffers (the sparse path cannot
660 : /// repair connection-level mask changes: arcsOfEdge deliberately omits
661 : /// the tail side)
662 : int myFullFillsPending = 0;
663 : /// @brief per-buffer edge state for the sparse path: the gate effort
664 : /// each edge's arcs were last filled from (NaN = never applied /
665 : /// forced), the pending-dirty flag, and the pending list
666 : std::vector<double> myAppliedEffort[2];
667 : std::vector<char> myPendingFlag[2];
668 : std::vector<const E*> myPendingList[2];
669 : /// @}
670 :
671 : private:
672 : CCHMetricFamily(const CCHMetricFamily&) = delete;
673 : CCHMetricFamily& operator=(const CCHMetricFamily&) = delete;
674 : };
|
