| | | 1 | | using System; |
| | | 2 | | using System.Globalization; |
| | | 3 | | using System.Threading; |
| | | 4 | | |
| | | 5 | | namespace Itinero.Routing; |
| | | 6 | | |
| | | 7 | | /// <summary> |
| | | 8 | | /// Process-wide tallies for <see cref="ReachabilityRouter"/>, so the cost of the optimistic |
| | | 9 | | /// path can be attributed rather than guessed at. |
| | | 10 | | /// </summary> |
| | | 11 | | /// <remarks> |
| | | 12 | | /// Free-running, read by subtracting two snapshots; nothing resets them, which keeps the write |
| | | 13 | | /// path to one uncontended increment. |
| | | 14 | | /// </remarks> |
| | | 15 | | public static class ReachabilityCounters |
| | | 16 | | { |
| | | 17 | | private static long _routes; |
| | | 18 | | private static long _originAdvances; |
| | | 19 | | private static long _destinationAdvances; |
| | | 20 | | private static long _searches; |
| | | 21 | | private static long _settledStates; |
| | | 22 | | |
| | | 23 | | |
| | | 24 | | |
| | | 25 | | // Split by whether the route ever abandoned a candidate: the retried group's share of total |
| | | 26 | | // settled states is the cost of retrying. |
| | | 27 | | private static long _routesRetried; |
| | | 28 | | private static long _settledClean; |
| | | 29 | | private static long _settledRetried; |
| | | 30 | | private static long _wastedStates; |
| | | 31 | | |
| | | 32 | | /// <summary>Route requests entered.</summary> |
| | 0 | 33 | | public static long Routes => Interlocked.Read(ref _routes); |
| | | 34 | | |
| | | 35 | | private static long _pocketsComposed; |
| | | 36 | | private static long _pocketsAbandoned; |
| | | 37 | | |
| | | 38 | | /// <summary> |
| | | 39 | | /// Times a stranded candidate got a pocket composed for it — the local-access fallback. |
| | | 40 | | /// </summary> |
| | | 41 | | /// <remarks> |
| | | 42 | | /// Per route this is how often phase 1 was not enough. Nothing is composed for a candidate |
| | | 43 | | /// that routes straight away, so the common path never pays for it. |
| | | 44 | | /// </remarks> |
| | 0 | 45 | | public static long PocketsComposed => Interlocked.Read(ref _pocketsComposed); |
| | | 46 | | |
| | 3 | 47 | | public static void CountPocketComposed() => Interlocked.Increment(ref _pocketsComposed); |
| | | 48 | | |
| | | 49 | | /// <summary> |
| | | 50 | | /// Pockets that outgrew their budget, so the candidate got no relabelling. |
| | | 51 | | /// </summary> |
| | | 52 | | /// <remarks> |
| | | 53 | | /// Should stay at zero: a local-access region larger than the island threshold means the |
| | | 54 | | /// tagging or the bound is wrong, not that the route is unusual. |
| | | 55 | | /// </remarks> |
| | 0 | 56 | | public static long PocketsAbandoned => Interlocked.Read(ref _pocketsAbandoned); |
| | | 57 | | |
| | 0 | 58 | | public static void CountPocketAbandoned() => Interlocked.Increment(ref _pocketsAbandoned); |
| | | 59 | | |
| | | 60 | | /// <summary>Times the origin gave up on a candidate and took the next one.</summary> |
| | | 61 | | /// <remarks> |
| | | 62 | | /// Counts only candidates abandoned after a failed search. The first snap is not an advance |
| | | 63 | | /// — so zero here means every route was served by the edge nearest its origin. |
| | | 64 | | /// </remarks> |
| | 0 | 65 | | public static long OriginAdvances => Interlocked.Read(ref _originAdvances); |
| | | 66 | | |
| | | 67 | | /// <summary>Times the destination gave up on a candidate and took the next one.</summary> |
| | 0 | 68 | | public static long DestinationAdvances => Interlocked.Read(ref _destinationAdvances); |
| | | 69 | | |
| | | 70 | | /// <summary>Bidirectional searches run, including continuations of a surviving half.</summary> |
| | 0 | 71 | | public static long Searches => Interlocked.Read(ref _searches); |
| | | 72 | | |
| | | 73 | | /// <summary>States settled across both halves, summed over all searches.</summary> |
| | | 74 | | /// <remarks> |
| | | 75 | | /// The per-route figure is what compares against the baseline's A* search: a router paying |
| | | 76 | | /// for goal direction settles far fewer states for the same path, and that difference is |
| | | 77 | | /// CPU rather than I/O, so it shows up most in the hot regime. |
| | | 78 | | /// </remarks> |
| | 0 | 79 | | public static long SettledStates => Interlocked.Read(ref _settledStates); |
| | | 80 | | |
| | | 81 | | /// <summary>Routes that abandoned at least one candidate.</summary> |
| | 0 | 82 | | public static long RoutesRetried => Interlocked.Read(ref _routesRetried); |
| | | 83 | | |
| | | 84 | | /// <summary>Settled states charged to routes that never retried.</summary> |
| | 0 | 85 | | public static long SettledClean => Interlocked.Read(ref _settledClean); |
| | | 86 | | |
| | | 87 | | /// <summary>Settled states charged to routes that retried at least once.</summary> |
| | 0 | 88 | | public static long SettledRetried => Interlocked.Read(ref _settledRetried); |
| | | 89 | | |
| | | 90 | | /// <summary> |
| | | 91 | | /// States settled by halves that were then thrown away — the work a retry actually wastes. |
| | | 92 | | /// </summary> |
| | | 93 | | /// <remarks> |
| | | 94 | | /// Bounded by construction: a half is abandoned only when its heap empties below threshold, |
| | | 95 | | /// so it had already exhausted a component smaller than that. |
| | | 96 | | /// </remarks> |
| | 0 | 97 | | public static long WastedStates => Interlocked.Read(ref _wastedStates); |
| | | 98 | | |
| | 28 | 99 | | internal static void CountRoute() => Interlocked.Increment(ref _routes); |
| | | 100 | | |
| | | 101 | | /// Called once per route, at exit, with what that route cost. |
| | | 102 | | internal static void CountRouteOutcome(bool retried, long settled) |
| | 28 | 103 | | { |
| | 28 | 104 | | if (retried) |
| | 2 | 105 | | { |
| | 2 | 106 | | Interlocked.Increment(ref _routesRetried); |
| | 2 | 107 | | Interlocked.Add(ref _settledRetried, settled); |
| | 2 | 108 | | } |
| | | 109 | | else |
| | 26 | 110 | | { |
| | 26 | 111 | | Interlocked.Add(ref _settledClean, settled); |
| | 26 | 112 | | } |
| | 28 | 113 | | } |
| | | 114 | | |
| | 1 | 115 | | internal static void CountWasted(long states) => Interlocked.Add(ref _wastedStates, states); |
| | | 116 | | |
| | | 117 | | |
| | | 118 | | |
| | | 119 | | |
| | 1 | 120 | | internal static void CountOriginAdvance() => Interlocked.Increment(ref _originAdvances); |
| | | 121 | | |
| | 0 | 122 | | internal static void CountDestinationAdvance() => Interlocked.Increment(ref _destinationAdvances); |
| | | 123 | | |
| | 32 | 124 | | internal static void CountSearch() => Interlocked.Increment(ref _searches); |
| | | 125 | | |
| | 32 | 126 | | internal static void CountSettled(long states) => Interlocked.Add(ref _settledStates, states); |
| | | 127 | | |
| | | 128 | | /// <summary>A one-line summary, for a log heartbeat.</summary> |
| | | 129 | | public static string Describe() |
| | 0 | 130 | | { |
| | 0 | 131 | | var routes = Routes; |
| | 0 | 132 | | if (routes == 0) return "reachability: no routes yet"; |
| | | 133 | | |
| | | 134 | | string Per(long value, string format) => |
| | 0 | 135 | | (value / (double)routes).ToString(format, CultureInfo.InvariantCulture); |
| | | 136 | | |
| | 0 | 137 | | var retried = RoutesRetried; |
| | 0 | 138 | | var clean = routes - retried; |
| | | 139 | | |
| | 0 | 140 | | string Mean(long total, long count, string format) => count == 0 |
| | 0 | 141 | | ? "n/a" |
| | 0 | 142 | | : (total / (double)count).ToString(format, CultureInfo.InvariantCulture); |
| | | 143 | | |
| | 0 | 144 | | string Pct(long part, long whole) => whole == 0 |
| | 0 | 145 | | ? "n/a" |
| | 0 | 146 | | : (part * 100.0 / whole).ToString("0.0", CultureInfo.InvariantCulture) + "%"; |
| | | 147 | | |
| | 0 | 148 | | return "reachability: routes=" + routes.ToString(CultureInfo.InvariantCulture) + |
| | 0 | 149 | | ", searches/route=" + Per(Searches, "0.000") + |
| | 0 | 150 | | ", origin_advances/route=" + Per(OriginAdvances, "0.000") + |
| | 0 | 151 | | ", dest_advances/route=" + Per(DestinationAdvances, "0.000") + |
| | 0 | 152 | | ", settled/route=" + Per(SettledStates, "0.0") + |
| | 0 | 153 | | " | retried=" + Pct(retried, routes) + |
| | 0 | 154 | | " of routes, settled/route clean=" + Mean(SettledClean, clean, "0.0") + |
| | 0 | 155 | | " retried=" + Mean(SettledRetried, retried, "0.0") + |
| | 0 | 156 | | ", wasted_states=" + Pct(WastedStates, SettledStates) + " of all settled" + |
| | 0 | 157 | | " (" + Mean(WastedStates, routes, "0.0") + "/route)" + |
| | 0 | 158 | | " | pockets/route=" + Per(PocketsComposed, "0.000") + |
| | 0 | 159 | | ", pockets_abandoned=" + PocketsAbandoned.ToString(CultureInfo.InvariantCulture); |
| | 0 | 160 | | } |
| | | 161 | | } |