retry decorrelation for Polly dotnext 2018

using System;
using System.Collections.Generic;
using System.Linq;
using static System.Math;

namespace dotnext_retry_seq
{
    class Program
    {
        static void Main(string[] args)
        {
            var maxExpRetries = 4;
            var random = new Random(1234);

            var constant = FromFunc(i => 1);

            IEnumerable<double> RandomizedConstant() {
                //var l = Enumerable.Range(0, 32).Select(i => 0.5 + i + random.NextDouble());
                var prev = 0.0;
                for (var i = 0; i < 32; i++) {
                    var next = 0.5 + i + random.NextDouble();
                    yield return next - prev;
                    prev = next;
                }
            }

            IEnumerable<double> SoftExp()
            {
                var n = maxExpRetries;
                var prev = 0.0;
                for (var i = 0; i < n; i++) {
                    var t = (double)i + random.NextDouble();
                    var next = Math.Pow(2, t);
                    yield return next - prev;
                    prev = next;
                }
            }

            IEnumerable<double> SoftExpSoftDelay(double factor)
            {
                var n = maxExpRetries;
                if (factor < 0.1) {
                    throw new ArgumentOutOfRangeException(nameof(factor), factor, "should be >= 0.1");
                }
                var prev = 0.0;
                for (var i = 0; i < n; i++) {
                    var t = (double)i + random.NextDouble();
                    var next = Math.Pow(2, t)* Math.Tanh(Math.Sqrt(factor*t));
                    yield return next - prev;
                    prev = next;
                }
            }

            IEnumerable<TimeSpan> DecorrelatedJitterAWS_Clamped(int maxRetries, TimeSpan seedDelay, TimeSpan maxDelay)
            {
                Random jitterer = random;
                int retries = 0;
                double seed = seedDelay.TotalMilliseconds;
                double max = maxDelay.TotalMilliseconds;
                double current = seed;
                while (++retries <= maxRetries)
                {
                    current = Math.Min(max, Math.Max(seed, current * 3 * jitterer.NextDouble()));
                    // adopting the 'Decorrelated Jitter' formula from https://www.awsarchitectureblog.com/2015/03/backoff.html.  Can be between seed and previous * 3.  Mustn't exceed max.
                    yield return TimeSpan.FromMilliseconds(current);
                }
            }

            IEnumerable<TimeSpan> DecorrelatedJitterAWS(int maxRetries, TimeSpan seedDelay, TimeSpan maxDelay)
            {
                Random jitterer = random;
                int retries = 0;
                double seed = seedDelay.TotalMilliseconds;
                double max = maxDelay.TotalMilliseconds;
                double current = seed;

                while (++retries <= maxRetries)
                {
                    double RandomBetween(Random r, double x, double y) {
                        return x + r.NextDouble() * (y - x);
                    }
                    current = Math.Min(max, RandomBetween(jitterer, seed, current * 3 * jitterer.NextDouble()));
                    // adopting the 'Decorrelated Jitter' formula from https://www.awsarchitectureblog.com/2015/03/backoff.html.  Can be between seed and previous * 3.  Mustn't exceed max.
                    yield return TimeSpan.FromMilliseconds(current);
                }
            }
            
            var exp = FromFunc(i => Math.Pow(2, i));
            var expJittered = FromFunc(i => random.NextDouble() + Math.Pow(2, i));
            var expJitteredShifted = FromFunc(i =>1.5*(random.NextDouble() - 0.5) * (i == 0 ? 1 : i) + Math.Pow(2, i));

            var species = new (IEnumerable<double>, string)[] {
                (RandomizedConstant(), "randomized constant"),
                //(exp, "exp (Polly)"),
                (expJittered, " exp jittered (Polly)"),
                (expJitteredShifted, " exp jittered (Shifted)"),
                (DecorrelatedJitterAWS_Clamped(4, TimeSpan.FromSeconds(1), TimeSpan.FromSeconds(4)).Select(i=> i.TotalSeconds), "decorrelated jitter (AWS with error)"),
                (DecorrelatedJitterAWS(4, TimeSpan.FromSeconds(1), TimeSpan.FromSeconds(4)).Select(i=> i.TotalSeconds), "decorrelated jitter (AWS)"),
                (SoftExp(), "soft exp"),
                (SoftExpSoftDelay(0.1), "soft exp, soft delay 0.1"),
                (SoftExpSoftDelay(1), "soft exp, soft delay 1"),
                (SoftExpSoftDelay(3), "soft exp, soft delay 3"),
                (SoftExpSoftDelay(10), "soft exp, soft delay 10"),
                (SoftExpSoftDelay(50), "soft exp, soft delay 50"),
                };

            Console.WriteLine(string.Join('\t', species.Select(i => i.Item2)));
            foreach (var i in ZipAggregate(species.Select(i => ComputeRetries(i.Item1))))
            {
                Console.WriteLine(string.Join('\t', i));
            }
        }

        static IEnumerable<double> FromFunc(Func<int, double> f)
        {
            var maxRetries = int.MaxValue;
            foreach (var i in Enumerable.Range(0, maxRetries))
            {
                yield return f(i);
            }
        }


        static IEnumerable<List<T>> ZipAggregate<T>(IEnumerable<IEnumerable<T>> sequences)
        {
            return sequences.Aggregate(Enumerable.Range(0, int.MaxValue).Select(i => new List<T>()), (a, b) => a.Zip(b, (l, r) => { l.Add(r); return l; }));
        }

        static IEnumerable<double> ComputeRetries(IEnumerable<double> retries)
        {
            var totalSamples = 100_000;
            var totalSlots = 200;
            var slotsPerSec = 10;

            var samples = new double[totalSlots];
            for (var i = 0; i < totalSamples; i++)
            {
                var t = 0.0;
                using (var ie = retries.GetEnumerator())
                {
                    for (var r = 0; r < 30 && ie.MoveNext(); r++)
                    {
                        t += ie.Current;
                        var x = (int)(t * slotsPerSec + 1);
                        if (x >= 0 && x < totalSlots)
                        {
                            samples[x] += 1.0 / totalSamples;
                        }
                    }
                }
            }
            return samples;
        }
    }
}

Posting here very minor modifications to above code made by @reisenberger, to pull out the retry interval distribution for a particular try.

Used to generate the output here: App-vNext/Polly#530 (comment)

class Program
{
    static void Main(string[] args)
    {
        const char separator = ',';

        var maxExpRetries = 4;
        var random = new Random(1234);

        int? highlightTry = args.Length == 1 ? Int32.Parse(args[0]): (int?)null;

        Console.WriteLine($"Distribution of retry intervals, focusing on try: {(highlightTry == null ? "all tries" : highlightTry.ToString())}.");

        #region Formulae

        IEnumerable<double> RandomizedConstant()
        {
            //var l = Enumerable.Range(0, 32).Select(i => 0.5 + i + random.NextDouble());
            var prev = 0.0;
            for (var i = 0; i < 32; i++)
            {
                var next = 0.5 + i + random.NextDouble();
                yield return next - prev;
                prev = next;
            }
        }

        IEnumerable<double> SoftExp()
        {
            var n = maxExpRetries;
            var prev = 0.0;
            for (var i = 0; i < n; i++)
            {
                var t = (double)i + random.NextDouble();
                var next = Math.Pow(2, t);
                yield return next - prev;
                prev = next;
            }
        }

        IEnumerable<double> SoftExpSoftDelay(double factor)
        {
            var n = maxExpRetries;
            if (factor < 0.1)
            {
                throw new ArgumentOutOfRangeException(nameof(factor), factor, "should be >= 0.1");
            }
            var prev = 0.0;
            for (var i = 0; i < n; i++)
            {
                var t = (double)i + random.NextDouble();
                var next = Math.Pow(2, t) * Math.Tanh(Math.Sqrt(factor * t));
                yield return next - prev;
                prev = next;
            }
        }

        IEnumerable<TimeSpan> DecorrelatedJitterAWS_Clamped(int maxRetries, TimeSpan seedDelay, TimeSpan maxDelay)
        {
            Random jitterer = random;
            int retries = 0;
            double seed = seedDelay.TotalMilliseconds;
            double max = maxDelay.TotalMilliseconds;
            double current = seed;
            while (++retries <= maxRetries)
            {
                current = Math.Min(max, Math.Max(seed, current * 3 * jitterer.NextDouble()));
                // adopting the 'Decorrelated Jitter' formula from https://www.awsarchitectureblog.com/2015/03/backoff.html.  Can be between seed and previous * 3.  Mustn't exceed max.
                yield return TimeSpan.FromMilliseconds(current);
            }
        }

        IEnumerable<TimeSpan> DecorrelatedJitterAWS(int maxRetries, TimeSpan seedDelay, TimeSpan maxDelay)
        {
            Random jitterer = random;
            int retries = 0;
            double seed = seedDelay.TotalMilliseconds;
            double max = maxDelay.TotalMilliseconds;
            double current = seed;

            while (++retries <= maxRetries)
            {
                double RandomBetween(Random r, double x, double y)
                {
                    return x + r.NextDouble() * (y - x);
                }
                current = Math.Min(max, RandomBetween(jitterer, seed, current * 3 * jitterer.NextDouble()));
                // adopting the 'Decorrelated Jitter' formula from https://www.awsarchitectureblog.com/2015/03/backoff.html.  Can be between seed and previous * 3.  Mustn't exceed max.
                yield return TimeSpan.FromMilliseconds(current);
            }
        }

        var exp = FromFunc(i => Math.Pow(2, i));
        var expJittered = FromFunc(i => random.NextDouble() + Math.Pow(2, i));
        var expJitteredShifted = FromFunc(i => 1.5 * (random.NextDouble() - 0.5) * (i == 0 ? 1 : i) + Math.Pow(2, i));

        #endregion

        var species = new (IEnumerable<double>, string)[] {
            (RandomizedConstant(), "randomized constant"),
            (expJittered, " exp jittered (Polly)"),
            (expJitteredShifted, " exp jittered (Shifted)"),
            (DecorrelatedJitterAWS_Clamped(maxExpRetries, TimeSpan.FromSeconds(1), TimeSpan.FromSeconds(4)).Select(i=> i.TotalSeconds), "decorrelated jitter (AWS with error)"),
            (DecorrelatedJitterAWS(maxExpRetries, TimeSpan.FromSeconds(1), TimeSpan.FromSeconds(4)).Select(i=> i.TotalSeconds), "decorrelated jitter (AWS)"),
            (SoftExp(), "soft exp"),
            (SoftExpSoftDelay(0.1), "soft exp, soft delay 0.1"),
            (SoftExpSoftDelay(1), "soft exp, soft delay 1"),
            (SoftExpSoftDelay(3), "soft exp, soft delay 3"),
            (SoftExpSoftDelay(10), "soft exp, soft delay 10"),
            (SoftExpSoftDelay(50), "soft exp, soft delay 50"),
            };

        Console.WriteLine(string.Join(separator, species.Select(i => '"' + i.Item2 + '"')));
        foreach (var i in ZipAggregate(species.Select(i => ComputeRetries(i.Item1, highlightTry))))
        {
            Console.WriteLine(string.Join(separator, i));
        }
    }

    static IEnumerable<double> FromFunc(Func<int, double> f)
    {
        var maxRetries = int.MaxValue;
        foreach (var i in Enumerable.Range(0, maxRetries))
        {
            yield return f(i);
        }
    }


    static IEnumerable<List<T>> ZipAggregate<T>(IEnumerable<IEnumerable<T>> sequences)
    {
        return sequences.Aggregate(Enumerable.Range(0, int.MaxValue).Select(i => new List<T>()), (a, b) => a.Zip(b, (l, r) => { l.Add(r); return l; }));
    }

    static IEnumerable<double> ComputeRetries(IEnumerable<double> retries, int? highlightTry)
    {
        var totalSamples = 100_000;
        var totalSlots = 200;
        var slotsPerSec = 10;

        var samples = new double[totalSlots];
        for (var i = 0; i < totalSamples; i++)
        {
            var t = 0.0;
            using (var ie = retries.GetEnumerator())
            {
                for (var r = 0; r < 30 && ie.MoveNext(); r++)
                {
                    t += ie.Current;
                    var x = (int)(t * slotsPerSec + 1);
                    if (x >= 0 && x < totalSlots && (highlightTry == null || highlightTry == r))
                    {
                        samples[x] += 1.0 / totalSamples;
                    }
                }
            }
        }
        return samples;
    }
}