Stack-Allocated Lists

Don Syme and several others sent tweets to correct my claims about boxing in F#. I made the mistake of assuming that structs cannot be used as interface implementations without being boxed and allocated on the heap. As it turns out, .NET constraints allow structs to implement interfaces without being boxed. Out of sheer curiosity, I attempted to (ab)use this facility to systematically remove heap allocation. I decided to write a simple functional program that would not use the heap at all, performing all computation on the stack.

I went for encoding lists and implementing list reversal:

	type IList<'T> =
	abstract member Tail : #IListConsumer<'T,'R> -> 'R
	abstract member Head : 'T
	abstract member IsEmpty : bool
	and IListConsumer<'T,'R> =
	abstract member Consume : #IList<'T> -> 'R
	[<Struct>]
	type Nil<'T> =
	interface IList<'T> with
	member this.Head = failwith "Empty"
	member this.IsEmpty = true
	member this.Tail k = failwith "Empty"
	[<Struct>]
	type Cons<'T,'L when 'L :> IList<'T>>(head: 'T, tail: 'L) =
	interface IList<'T> with
	member this.Head = head
	member this.IsEmpty = false
	member this.Tail k = k.Consume tail
	let reverse list =
	let rec rev acc list =
	match list with
	| [] -> acc
	| x :: xs -> rev (x :: acc) xs
	rev [] list
	[<Struct>]
	type ListSum(sum: int) =
	member this.Consume(list: #IList<int>) =
	if list.IsEmpty then sum else
	list.Tail (ListSum(sum + list.Head))
	interface IListConsumer<int,int> with
	member this.Consume list = this.Consume list
	[<Struct>]
	type ListPrinter<'T> =
	interface IListConsumer<'T,int> with
	member this.Consume list =
	if list.IsEmpty then 0 else
	stdout.WriteLine list.Head
	list.Tail this
	type Lists =
	static member Reverse<'R,'T,'L1,'L2,'K when 'L1 :> IList<'T>
	and 'L2 :> IList<'T>
	and 'K :> IListConsumer<'T,'R>>
	(acc: 'L1) (list: 'L2) (k: 'K) =
	if list.IsEmpty
	then k.Consume acc
	else list.Tail (ListReverser(list.Head, acc, k))
	static member Sum (list: #IList<int>) =
	ListSum(0).Consume(list)
	static member ReverseSum (list: #IList<int>) =
	Lists.Reverse (Nil ()) list (ListSum(0))
	static member ReversePrint list =
	Lists.Reverse (Nil ()) list (ListPrinter())
	and [<Struct>] ListReverser<'T,'R,'L,'K when 'L :> IList<'T>
	and 'K :> IListConsumer<'T,'R>>
	(head: 'T, acc: 'L, k: 'K) =
	interface IListConsumer<'T,'R> with
	member this.Consume tail = Lists.Reverse (Cons (head, acc)) tail k
	#time
	let r = ref 0
	!r
	for i in 1 .. 10000000 do
	let list = Cons(1, Cons(2, Cons(3, Cons (4, Cons (5, Nil())))))
	r := !r + Lists.ReverseSum list
	for i in 1 .. 10000000 do
	let list = [1; 2; 3; 4; 5]
	r := !r + List.sum (List.rev list)

view raw StackAllocatedLists.fs hosted with ❤ by GitHub

This method for getting rid of heap allocation would not work in C as this particular use of generics implies runtime code generation. As far as I understand, the CLR here generates new code paths for every possible list length.

My little benchmark has stack-allocated lists of 5 elements each being reversed a bit slower than heap-allocated lists. But it is fun to try. FSI reports zero GC usage.