PascalTriangle.cs

using System;
using BenchmarkDotNet.Attributes;
using System.Runtime;
using System.Runtime.CompilerServices;
using System.Linq;
using System.Collections.Generic;

namespace SpanVsArray
{
    class Program
    {
        static void Main(string[] args)
        {
            BenchmarkDotNet.Running.BenchmarkRunner.Run<Bench>();
        }
    }

    public class Bench
    {
        [BenchmarkDotNet.Attributes.Params(5, 10, 30)]
        public int N { get; set; }

        [Benchmark]
        public void OP()
        {
            PascalTriangle.Generate(N);
        }

        [Benchmark]
        public void Jodrell()
        {
            JodrellPascal.Triangle(N);
        }
        
        [Benchmark]
        public void JodrellNoSpan()
        {
            JodrellPascalNoSpan.Triangle(N);
        }
        
        [Benchmark]
        public void JodrellNoSpanCache()
        {
            JodrellPascalNoSpanCache.Triangle(N);
        }
        
        [Benchmark]
        public void PeterPerRow()
        {
            Peter.Generate_PerRow_Reflective(N);
        }
        
        [Benchmark]
        public void PeterMelon()
        {
            Peter.Generate_Array_Improved_Reflective(N);
        }
    }

    public static class JodrellPascal
    {
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static ReadOnlySpan<int[]> Triangle(int n)
        {
            if (n < 1)
            {
                return ReadOnlySpan<int[]>.Empty;
            }

            Span<int[]> triangle = new int[n][];

            for (var r = 0; r < n; r++)
            {
                triangle[r] = Line(r).ToArray();
            }

            return triangle;
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static ReadOnlySpan<int> Line(int n)
        {
            if (n < 0)
            {
                return ReadOnlySpan<int>.Empty;
            }

            if (n == 0)
            {
                return (ReadOnlySpan<int>)new int[]
                {
                    1
                };
            }

            Span<int> result = new int[n + 1];

            result[0] = 1;
            for (var k = 0; k < n; k++)
            {
                result[k + 1] = result[k] * (n - k) / (k + 1);
            }

            return result;
        }
    }

    public static class JodrellPascalNoSpan
    {
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static ReadOnlySpan<int[]> Triangle(int n)
        {
            if (n < 1)
            {
                return ReadOnlySpan<int[]>.Empty;
            }

            Span<int[]> triangle = new int[n][];

            for (var r = 0; r < n; r++)
            {
                triangle[r] = Line(r);
            }

            return triangle;
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int[] Line(int n)
        {
            if (n < 0)
            {
                return Array.Empty<int>();
            }

            if (n == 0)
            {
                return new int[]
                {
                    1
                };
            }

            int[] result = new int[n + 1];

            result[0] = 1;
            for (var k = 0; k < n; k++)
            {
                result[k + 1] = result[k] * (n - k) / (k + 1);
            }

            return result;
        }
    }

    public static class JodrellPascalNoSpanCache
    {
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static ReadOnlySpan<int[]> Triangle(int n)
        {
            if (n < 1)
            {
                return ReadOnlySpan<int[]>.Empty;
            }

            Span<int[]> triangle = new int[n][];

            for (var r = 0; r < n; r++)
            {
                triangle[r] = Line(r);
            }

            return triangle;
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int[] Line(int n)
        {
            if (n < 0)
            {
                return Array.Empty<int>();
            }

            if (n == 0)
            {
                return new int[]
                {
                    1
                };
            }

            int[] result = new int[n + 1];

            var last = result[0] = 1;
            for (var k = 0; k < n; k++)
            {
                last = result[k + 1] = last * (n - k) / (k + 1);
            }

            return result;
        }
    }

    public class PascalTriangle
    {
        public static IList<IList<int>> Generate(int numRows)
        {
            IList<IList<int>> result = new List<IList<int>>();
            if (numRows == 0)
            {
                return result;
            }
            List<int> row = new List<int>();
            row.Add(1);
            result.Add(row);
            if (numRows == 1)
            {
                return result;
            }

            for (int i = 1; i < numRows; i++)
            {
                var prevRow = result[i - 1];
                row = new List<int>();
                row.Add(1);
                for (int j = 0; j < prevRow.Count - 1; j++)
                {
                    row.Add(prevRow[j] + prevRow[j + 1]);
                }
                row.Add(1);
                result.Add(row);
            }
            return result;
        }
    }

    public class Peter
    {
        // Using arrays, calculating each row individually, using row reflection:
        public static IList<IList<int>> Generate_PerRow_Reflective(int numRows)
        {
            var result = new int[numRows][];
            for (int i = 0; i < numRows; i++)
            {
                var row = new int[i + 1];
                row[0] = 1;
                row[i] = 1;
                var mid = i / 2;
                for (int j = 0; j < mid; j++)
                {
                    var value = row[j] * (i - j) / (j + 1);
                    row[j + 1] = value;
                    row[i - j - 1] = value;
                }
                result[i] = row;
            }
            return result;
        }

        // Using arrays instead of lists, caching the previous row's left value, and using row reflection:
        public static IList<IList<int>> Generate_Array_Improved_Reflective(int numRows)
        {
            var result = new int[numRows][];
            if (numRows == 0)
                return result;

            result[0] = new int[] { 1 };
            if (numRows == 1)
                return result;

            for (int i = 1; i < numRows; i++)
            {
                var prevRow = result[i - 1];
                var row = new int[i + 1];

                var left = 0;
                var mid = (i / 2) + 1;
                for (int j = 0; j < mid; j++)
                {
                    int right = prevRow[j];
                    var sum = left + right;
                    row[j] = sum;
                    row[i - j] = sum;
                    left = right;
                }
                result[i] = row;
            }
            return result;
        }
    }
}

BenchmarkDotNet=v0.11.5, OS=Windows 7 SP1 (6.1.7601.0)
Intel Core i7-2670QM CPU 2.20GHz (Sandy Bridge), 1 CPU, 8 logical and 4 physical cores
Frequency=2143603 Hz, Resolution=466.5043 ns, Timer=TSC
.NET Core SDK=3.0.100-preview6-012264
  [Host]     : .NET Core 3.0.0-preview6-27804-01 (CoreCLR 4.700.19.30373, CoreFX 4.700.19.30308), 64bit RyuJIT
  DefaultJob : .NET Core 3.0.0-preview6-27804-01 (CoreCLR 4.700.19.30373, CoreFX 4.700.19.30308), 64bit RyuJIT

Method	N	Mean	Error	StdDev	Median
OP	5	631.2 ns	6.5853 ns	5.8377 ns	630.7 ns
Jodrell	5	327.1 ns	2.0687 ns	1.8338 ns	326.7 ns
JodrellNoSpan	5	216.1 ns	1.5530 ns	1.2968 ns	216.1 ns
JodrellNoSpanCache	5	194.7 ns	1.2954 ns	1.2118 ns	195.0 ns
PeterPerRow	5	192.1 ns	0.7110 ns	0.5937 ns	192.3 ns
PeterMelon	5	215.1 ns	17.2689 ns	50.9178 ns	184.0 ns
OP	10	2,023.4 ns	10.4677 ns	9.7915 ns	2,019.8 ns
Jodrell	10	944.4 ns	8.0694 ns	7.1533 ns	942.1 ns
JodrellNoSpan	10	659.7 ns	4.2389 ns	3.9651 ns	659.7 ns
JodrellNoSpanCache	10	556.9 ns	1.4909 ns	1.3946 ns	556.3 ns
PeterPerRow	10	483.9 ns	2.8657 ns	2.6806 ns	482.7 ns
PeterMelon	10	394.0 ns	2.3752 ns	1.9834 ns	393.6 ns
OP	30	12,464.5 ns	50.7439 ns	47.4659 ns	12,456.3 ns
Jodrell	30	5,925.7 ns	21.8093 ns	19.3334 ns	5,921.6 ns
JodrellNoSpan	30	6,257.4 ns	9.8317 ns	8.2099 ns	6,255.3 ns
JodrellNoSpanCache	30	4,149.0 ns	19.2000 ns	17.0203 ns	4,146.5 ns
PeterPerRow	30	2,777.7 ns	16.9192 ns	14.1283 ns	2,771.8 ns
PeterMelon	30	1,304.9 ns	6.5183 ns	5.4431 ns	1,305.3 ns

Very nice data!