A Stack data structure implementation using Span

I am back in Microsoft and today we talk about the code below, which is on github here:

7. public ref struct SpanStack<T>
8. {
9.     private Span memory;
10.     private int index;
11.     private int size;
13.     public SpanStack(Span mem) { memory = mem; index = 0; size = mem.Length; }
15.     public bool IsEmpty() => index < 0;
16.     public bool IsFull() => index > size – 1;
18.     public void Push(T item) => memory[index++] = item;
19.     public T Pop() => memory[–index];
20. }
22. public static class SpanExtensions
23. {
24.     public static SpanStack AsStack<T>(this Span span) => new SpanStack(span);
25. }

This Stack data structure can be used over memory that resides on the stack, heap or unmanaged heap. If you know about Span this should immediately make sense to you.

This has to be a ref struct because it contains a Span. It can’t be used on the heap (i.e. in lambdas, async, class field, …). You have to build it on top of Memory if you need that. Also, you can happily blow the stack with this guy …

Let’s micro-benchmark it with BenchmarkDotNet.  For example, a postfix calculator. Let’s first do it naively using inheritance and the generic Stack class in the framework.

This is the naive object model:

27. abstract class Token {}
29. sealed class Operand: Token
30. {
31.     public int Value { get; }
32.     public Operand(int v) { Value = v; }
33. }
35. abstract class Operator: Token {
36.     abstract public int Calc(int a, int b);
37. }
39. sealed class Add: Operator
40. {
41.     public override int Calc(int a, int b) => a + b;
42. }
44. sealed class Mult : Operator
45. {
46.     public override int Calc(int a, int b) => a * b;
47. }
49. sealed class Minus : Operator
50. {
51.     public override int Calc(int a, int b) => a – b;
52. }

Let’s then do it trying to be a bit more performance aware using a stack friendly representation:

54. public enum TokenType { Operand, Sum, Mult, Minus}
56. readonly struct SToken
57. {
58.     public TokenType Type { get; }
59.     public int Value { get; }
60.     public SToken(TokenType t, int v) { Type = t; Value = v; }
61.     public SToken(TokenType t) { Type = t; Value = 0; }
63.     public int Calc(int a, int b) =>
64.                Type == TokenType.Sum   ? a + b :
65.                Type == TokenType.Minus ? a – b :
66.                Type == TokenType.Minus ? a * b :
67.                throw new Exception(“I don’t know that one”);
69. }

Perhaps not overtly elegant, but not that terrible either. You got to love those expression bodied methods and throw-expression.

We then setup things (I know I could/should parse a string here):

73. static Token[] tokens;
74. static SToken[] stokens;
76. [GlobalSetup]
77. public void Setup()
78. {
79.     tokens = new Token[] { new Operand(2), new Operand(3), new Operand(4), new Add(),
80.                            new Mult(), new Operand(5), new Minus() };
81.     stokens = new SToken[] { new SToken(TokenType.Operand, 2),
82.                              new SToken(TokenType.Operand, 3), new SToken(TokenType.Operand, 4),
83.                              new SToken(TokenType.Sum),  new SToken(TokenType.Mult),
84.                              new SToken(TokenType.Operand, 5), new SToken(TokenType.Minus)};
85. }

And first test the naive object model with the standard Stack from System.Collections.Generic.

133. [Benchmark]
134. public int PostfixEvalStack()
135. {
136.     var stack = new Stack(100);
138.     foreach (var token in tokens)
139.     {
140.         switch (token)
141.         {
142.             case Operand t:
143.                 stack.Push(t);
144.                 break;
145.             case Operator o:
146.                 var a = stack.Pop() as Operand;
147.                 var b = stack.Pop() as Operand;
148.                 var result = o.Calc(a.Value, b.Value);
149.                 stack.Push(new Operand(result));
150.                 break;
151.         }
152.     }
153.     return (stack.Pop() as Operand).Value;
154. }

Then let’s just swap out our own lean-and-mean stack:

109. [Benchmark]
110. public int PostfixEvalSpanStack()
111. {
112.     Span span = new Token[100];
113.     var stack = span.AsStack();
115.     foreach (var token in tokens)
116.     {
117.         switch (token)
118.         {
119.             case Operand t:
120.                 stack.Push(t);
121.                 break;
122.             case Operator o:
123.                 var a = stack.Pop() as Operand;
124.                 var b = stack.Pop() as Operand;
125.                 var result = o.Calc(a.Value, b.Value);
126.                 stack.Push(new Operand(result));
127.                 break;
128.         }
129.     }
130.     return (stack.Pop() as Operand).Value;
131. }

And finally let’s go the whole way, lean object model and lean data structure, everything on the stack:

87. [Benchmark(Baseline = true)]
88. public int PostfixEvalSpanStackStructTypes()
89. {
90.     Span span = stackalloc SToken[100];
91.     var stack = span.AsStack();
93.     foreach (var token in stokens)
94.     {
95.         if (token.Type == TokenType.Operand)
96.         {
97.             stack.Push(token);
98.         } else {
99.             var a = stack.Pop();
100.             var b = stack.Pop();
101.             var result = token.Calc(a.Value, b.Value);
102.             stack.Push(new SToken(TokenType.Operand, result));
103.             break;
104.         }
105.     }
106.     return stack.Pop().Value;
107. }

We also want to check that we didn’t code anything stupid and finally run the benchmark.

156. static void Test()
157. {
158.     var p = new Program();
159.     p.Setup();
160.     Trace.Assert(p.PostfixEvalStack() == p.PostfixEvalSpanStack() &&
161.                  p.PostfixEvalSpanStack() == p.PostfixEvalSpanStackStructTypes());
162. }
163. static void Main(string[] args)
164. {
165.     Test();
166.     var summary = BenchmarkRunner.Run();
167. }

On my machine I get these results:

BenchmarkDotNet=v0.10.14, OS=Windows 10.0.16299.431 (1709/FallCreatorsUpdate/Redstone3)
Intel Core i7-6600U CPU 2.60GHz (Skylake), 1 CPU, 4 logical and 2 physical cores
Frequency=2742185 Hz, Resolution=364.6727 ns, Timer=TSC
.NET Core SDK=2.1.300-rc1-008673
  [Host]     : .NET Core 2.1.0-rc1 (CoreCLR 4.6.26426.02, CoreFX 4.6.26426.04), 64bit RyuJIT
  DefaultJob : .NET Core 2.1.0-rc1 (CoreCLR 4.6.26426.02, CoreFX 4.6.26426.04), 64bit RyuJIT

Method	Mean	Error	StdDev	Scaled	ScaledSD
PostfixEvalSpanStackStructTypes	76.24 ns	1.563 ns	2.857 ns	1.00	0.00
PostfixEvalSpanStack	168.65 ns	5.280 ns	15.319 ns	2.22	0.22
PostfixEvalStack	334.56 ns	7.387 ns	20.593 ns	4.39	0.31

Your mileage might vary. I want to emphasize that I am just playing with things. I haven’t done any deep analysis of this benchmark. There can be flaws, etc… etc…

Still, I find the idea of data structures which are memory-location-independent rather fascinating.