| | | 1 | | using System; |
| | | 2 | | |
| | | 3 | | namespace AmbientServices.Utilities; |
| | | 4 | | |
| | | 5 | | /// <summary> |
| | | 6 | | /// A static class to hold enhanced functions for performing interlocked operations. |
| | | 7 | | /// </summary> |
| | | 8 | | /// <remarks> |
| | | 9 | | /// <pitch>Lock-free aggregation on shared numeric fields — running min/max, additive accumulation, and an exponential m |
| | | 10 | | /// <pledge>All operations are safe to call from any number of threads, never take a lock, and never throw due to conten |
| | | 11 | | /// <plan>Each operation is an optimistic <see cref="System.Threading.Interlocked.CompareExchange(ref long, long, long)" |
| | | 12 | | /// <priority> |
| | | 13 | | /// 1. Bounded cost under contention over never losing an update: an attempt is abandoned after ten misses, so a caller |
| | | 14 | | /// 2. Keeping contending threads out of lock-step over the cheapest possible backoff: the spins and sleeps are randomly |
| | | 15 | | /// </priority> |
| | | 16 | | /// Note that we could increase the code coverage by making a single function with a delegate to reduce the uncovered li |
| | | 17 | | /// but this would likely have a significant performance impact without affecting the actual testability or reliability |
| | | 18 | | /// </remarks> |
| | | 19 | | public static class InterlockedUtilities |
| | | 20 | | { |
| | | 21 | | /// <summary> |
| | | 22 | | /// Replaces the value with the specified value if the specified value is greater. |
| | | 23 | | /// If there is too much contention on <paramref name="valueReference"/>, the attempt will fail and no exception wil |
| | | 24 | | /// </summary> |
| | | 25 | | /// <param name="valueReference">A reference to the value being manipulated.</param> |
| | | 26 | | /// <param name="possibleNewMin">The value to replace the value with if it is greater.</param> |
| | | 27 | | /// <returns>The new minimum value.</returns> |
| | | 28 | | public static long TryOptimisticMin(ref long valueReference, long possibleNewMin) |
| | | 29 | | { |
| | 2 | 30 | | int attempt = 0; |
| | | 31 | | // loop attempting to put it in until we win the race or timeout |
| | | 32 | | while (true) |
| | | 33 | | { |
| | | 34 | | // get the latest value |
| | 2 | 35 | | long oldValue = valueReference; |
| | | 36 | | // done but not the new min? |
| | 2 | 37 | | if (possibleNewMin >= oldValue) return oldValue; |
| | | 38 | | // try to put in our value--did we win the race? |
| | 2 | 39 | | if (oldValue == System.Threading.Interlocked.CompareExchange(ref valueReference, possibleNewMin, oldValue)) |
| | | 40 | | // we're done and we were the new min |
| | 2 | 41 | | return possibleNewMin; |
| | | 42 | | // note that it's very difficult to test a miss here--you really have to pound it with multiple threads, so |
| | 2 | 43 | | if (!TryAgainAfterOptimisticMissDelay(attempt++)) return oldValue; |
| | | 44 | | } |
| | | 45 | | } |
| | | 46 | | /// <summary> |
| | | 47 | | /// Replaces the value with the specified value if the specified value is greater. |
| | | 48 | | /// If there is too much contention on <paramref name="valueReference"/>, the attempt will fail and no exception wil |
| | | 49 | | /// </summary> |
| | | 50 | | /// <param name="valueReference">A reference to the value being manipulated.</param> |
| | | 51 | | /// <param name="possibleNewMax">The value to replace the value with if it is greater.</param> |
| | | 52 | | /// <returns>The new maximum value.</returns> |
| | | 53 | | public static long TryOptimisticMax(ref long valueReference, long possibleNewMax) |
| | | 54 | | { |
| | 2 | 55 | | int attempt = 0; |
| | | 56 | | // loop attempting to put it in until we win the race or timeout |
| | | 57 | | while (true) |
| | | 58 | | { |
| | | 59 | | // get the latest value |
| | 2 | 60 | | long oldValue = valueReference; |
| | | 61 | | // done but not the new max? |
| | 2 | 62 | | if (possibleNewMax <= oldValue) return oldValue; |
| | | 63 | | // try to put in our value--did we win the race? |
| | 2 | 64 | | if (oldValue == System.Threading.Interlocked.CompareExchange(ref valueReference, possibleNewMax, oldValue)) |
| | | 65 | | // we're done and we were the new max |
| | 2 | 66 | | return possibleNewMax; |
| | | 67 | | // note that it's very difficult to test a miss here--you really have to pound it with multiple threads, so |
| | 2 | 68 | | if (!TryAgainAfterOptimisticMissDelay(attempt++)) return oldValue; |
| | | 69 | | } |
| | | 70 | | } |
| | | 71 | | /// <summary> |
| | | 72 | | /// Replaces the value with the specified value if the specified value is greater. |
| | | 73 | | /// If there is too much contention on <paramref name="valueReference"/>, the attempt will fail and no exception wil |
| | | 74 | | /// </summary> |
| | | 75 | | /// <param name="valueReference">A reference to the value being manipulated.</param> |
| | | 76 | | /// <param name="possibleNewMin">The value to replace the value with if it is greater.</param> |
| | | 77 | | /// <returns>The new minimum value.</returns> |
| | | 78 | | public static double TryOptimisticMin(ref double valueReference, double possibleNewMin) |
| | | 79 | | { |
| | 2 | 80 | | int attempt = 0; |
| | | 81 | | // loop attempting to put it in until we win the race or timeout |
| | | 82 | | while (true) |
| | | 83 | | { |
| | | 84 | | // get the latest value |
| | 2 | 85 | | double oldValue = valueReference; |
| | | 86 | | // done but not the new min? |
| | 2 | 87 | | if (possibleNewMin >= oldValue) return oldValue; |
| | | 88 | | // try to put in our value--did we win the race? |
| | 2 | 89 | | if (oldValue == System.Threading.Interlocked.CompareExchange(ref valueReference, possibleNewMin, oldValue)) |
| | | 90 | | // we're done and we were the new min |
| | 2 | 91 | | return possibleNewMin; |
| | | 92 | | // note that it's very difficult to test a miss here--you really have to pound it with multiple threads, so |
| | 2 | 93 | | if (!TryAgainAfterOptimisticMissDelay(attempt++)) return oldValue; |
| | | 94 | | } |
| | | 95 | | } |
| | | 96 | | /// <summary> |
| | | 97 | | /// Replaces the value with the specified value if the specified value is greater. |
| | | 98 | | /// If there is too much contention on <paramref name="valueReference"/>, the attempt will fail and no exception wil |
| | | 99 | | /// </summary> |
| | | 100 | | /// <param name="valueReference">A reference to the value being manipulated.</param> |
| | | 101 | | /// <param name="possibleNewMax">The value to replace the value with if it is greater.</param> |
| | | 102 | | /// <returns>The new maximum value.</returns> |
| | | 103 | | public static double TryOptimisticMax(ref double valueReference, double possibleNewMax) |
| | | 104 | | { |
| | 2 | 105 | | int attempt = 0; |
| | | 106 | | // loop attempting to put it in until we win the race or timeout |
| | | 107 | | while (true) |
| | | 108 | | { |
| | | 109 | | // get the latest value |
| | 2 | 110 | | double oldValue = valueReference; |
| | | 111 | | // done but not the new max? |
| | 2 | 112 | | if (possibleNewMax <= oldValue) return oldValue; |
| | | 113 | | // try to put in our value--did we win the race? |
| | 2 | 114 | | if (oldValue == System.Threading.Interlocked.CompareExchange(ref valueReference, possibleNewMax, oldValue)) |
| | | 115 | | // we're done and we were the new max |
| | 2 | 116 | | return possibleNewMax; |
| | | 117 | | // note that it's very difficult to test a miss here--you really have to pound it with multiple threads, so |
| | 2 | 118 | | if (!TryAgainAfterOptimisticMissDelay(attempt++)) return oldValue; |
| | | 119 | | } |
| | | 120 | | } |
| | | 121 | | /// <summary> |
| | | 122 | | /// Attempts to add the specified amount to the value using interlocked operations. |
| | | 123 | | /// If there is too much contention on <paramref name="valueReference"/>, the attempt will fail and no exception wil |
| | | 124 | | /// </summary> |
| | | 125 | | /// <param name="valueReference">A reference to the value being manipulated.</param> |
| | | 126 | | /// <param name="toAdd">The value to add to the value.</param> |
| | | 127 | | /// <returns>The new value.</returns> |
| | | 128 | | public static double TryOptimisticAdd(ref double valueReference, double toAdd) |
| | | 129 | | { |
| | 2 | 130 | | int attempt = 0; |
| | | 131 | | // loop attempting to put it in until we win the race or timeout |
| | | 132 | | while (true) |
| | | 133 | | { |
| | | 134 | | // get the latest value |
| | 2 | 135 | | double oldValue = valueReference; |
| | | 136 | | // try to put in our value--did we win the race? |
| | 2 | 137 | | if (oldValue == System.Threading.Interlocked.CompareExchange(ref valueReference, oldValue + toAdd, oldValue) |
| | | 138 | | // return the new value |
| | 2 | 139 | | return oldValue + toAdd; |
| | | 140 | | // note that it's very difficult to test a miss here--you really have to pound it with multiple threads, so |
| | 2 | 141 | | if (!TryAgainAfterOptimisticMissDelay(attempt++)) return oldValue; |
| | | 142 | | } |
| | | 143 | | } |
| | | 144 | | /// <summary> |
| | | 145 | | /// Updates an exponential moving average, which is a type of average where the age of recently added samples affect |
| | | 146 | | /// with the effect of samples decreasing exponentially over time. |
| | | 147 | | /// Whenever a new sample is added, the sum of all old samples are weighted in comparison to the new sample based on |
| | | 148 | | /// If there is too much contention on <paramref name="valueReference"/>, the attempt will fail and no exception wil |
| | | 149 | | /// </summary> |
| | | 150 | | /// <param name="valueReference">A reference to the value being manipulated.</param> |
| | | 151 | | /// <param name="decayHalfLives">The number of half-lives the old value should be discounted due to age.</param> |
| | | 152 | | /// <param name="sampleValue">The sample value to add to the moving average.</param> |
| | | 153 | | /// <returns>The new minimum value.</returns> |
| | | 154 | | public static double TryOptimisticAddExponentialMovingAverageSample(ref double valueReference, double decayHalfLives |
| | | 155 | | { |
| | 2 | 156 | | if (decayHalfLives < 0) throw new ArgumentOutOfRangeException(nameof(decayHalfLives), "The number of half lives |
| | 2 | 157 | | if (decayHalfLives == 0) return valueReference; |
| | 2 | 158 | | int attempt = 0; |
| | | 159 | | // loop attempting to put it in until we win the race or timeout |
| | | 160 | | while (true) |
| | | 161 | | { |
| | | 162 | | // get the old average |
| | 2 | 163 | | double oldAverage = valueReference; |
| | 2 | 164 | | double newAverage = sampleValue + (oldAverage - sampleValue) * (1 / Math.Pow(2.0, decayHalfLives)); |
| | | 165 | | // try to put in our value--did we win the race? |
| | 2 | 166 | | if (oldAverage == System.Threading.Interlocked.CompareExchange(ref valueReference, newAverage, oldAverage)) |
| | | 167 | | // we're done--return the new average |
| | 2 | 168 | | return newAverage; |
| | | 169 | | // note that it's very difficult to test a miss here--you really have to pound it with multiple threads, so |
| | 0 | 170 | | if (!TryAgainAfterOptimisticMissDelay(attempt++)) return oldAverage; |
| | | 171 | | } |
| | | 172 | | } |
| | | 173 | | internal static bool TryAgainAfterOptimisticMissDelay(int attempt) |
| | | 174 | | { |
| | | 175 | | // attempts 0-2 (the first few misses): retry immediately with no delay |
| | 2 | 176 | | if (attempt > 0) |
| | | 177 | | { |
| | | 178 | | // at ten or more misses, bail out and just ignore the attempted operation |
| | 2 | 179 | | if (attempt >= 10) return false; |
| | | 180 | | int delay; |
| | | 181 | | // attempts 5-9: sleep for a random, exponentially-growing amount before continuing |
| | 2 | 182 | | if (attempt >= 5) |
| | | 183 | | { |
| | 2 | 184 | | delay = _Rand.NextInt32 % (int)(50 * Math.Pow(2, attempt - 4)); |
| | 2 | 185 | | System.Threading.Thread.Sleep(delay); |
| | | 186 | | } |
| | | 187 | | // attempts 3-4: spin for a random, exponentially-growing number of iterations before continuing (attempts 1 |
| | 2 | 188 | | else if (attempt >= 3) |
| | | 189 | | { |
| | 2 | 190 | | delay = _Rand.NextInt32 % (int)(500 * Math.Pow(2, attempt - 2)); |
| | 2 | 191 | | for (int spin = 0; spin < delay; ++spin) { } |
| | | 192 | | } |
| | | 193 | | } |
| | 2 | 194 | | return true; |
| | | 195 | | } |
| | 2 | 196 | | private static readonly Pseudorandom _Rand = new(true); |
| | | 197 | | } |