Skip to main content

Purely Functional Collections vs. Mutable Collections

I've been experimenting with some purely functional collections, also known as persistent collections, and began to wonder precisely how much overhead they incur as compared to the standard framework collections on a VM platform such as .NET.

My open source Sasa library has long had a persistent stack type, considered a list in functional languages, and I was considering adding some additional persistent collections. I therefore wanted a better understanding of the various costs involved.

I had also wanted to test an interesting design alternative to standard class-based collections. One of the consistent nuisances on widely deployed VM platforms is the widespread presence of null values. C#'s extension methods somewhat mitigate this problem since you can call extension methods on null values and properly handle it, but calling instance methods on a null value throws a NullReferenceException. Therefore, you cannot invoke ToString or Equals without first checking for null.

This is particularly annoying for data types where null is in fact a valid value, as it is in linked lists, where null denotes the empty list. The idea I had was to make the data type a struct, wrapping an inner reference that would hold the actual collection contents, basically moving the null into a non-nullable type that I control:
public struct Stack<T> : IEnumerable<T> {
Node top;

sealed class Node {
internal T value;
internal Node next;
}
public bool IsEmpty { get { return top == null; } }
public override string ToString() {
return IsEmpty ? "<empty>" : this.Format(" & ");
}
...
}

A struct type can never be null, so I can overload Equals and ToString behaviour, but still handle null as a valid value -- a null inner reference indicates an empty list, for example.

I copied over the Sasa Seq type, implemented a struct-based version of it, and similarly implemented two persistent versions of a queue type. I then ran some quick benchmarks against the system collection classes, List<T>, Stack<T> and Queue<T> using a random sequence of 10,000,000 enqueues and dequeues. This test was repeated 10 times in each run, and the average runtime and memory use was taken.

This process was then repeated 13 times for each collection type, and I threw away the top and bottom two values. The results follow, where all values are in CPU ticks measured by System.Diagnostics.StopWatch. The results are displayed in sorted order, with the fastest at the top, and slowest at the bottom.

Queue Operations


Legend:
  • PQueue<T>: persistent class-based queue.

  • LinkedList<T>: System.Collections.Generic.LinkedList.

  • PQueue2<T>: persistent struct-based queue.

  • Queue<T>: System.Collections.Generic.Queue.

PQueue<T>LinkedList<T>PQueue2<T>Queue<T>
7699324462.557890322380.367679249692.367761780264
7718837154.917983445563.647687912510.557803131562.18
7740207043.648023998067.647703769050.187810452602.91
7828445642.918032055720.737800245839.277811040914.91
8451346377.458201663652.367834188839.277850104080
8589153123.648282536765.097955433135.277935923176
8707905445.828484668378.918178008811.648118527255.27
8764140750.558742958103.278323106361.458348756291.64
8979406774.558752582049.458327369725.098350023904
Averages
8275418530.678266025631.277943253773.97976637783.43

Stack Operations


Legend:
  • Seq<T>: persistent class-based stack.

  • List<T>: System.Collections.Generic.List.

  • Seq2<T>: persistent struct-based stack.

  • Stack<T>: System.Collections.Generic.Stack.

List<T>Seq<T>Stack<T>Seq2<T>
77102630647826307262.557802069434.917690359998.55
7762791045.8278707931847808408813.827770721440.73
7849427981.098035572504.7378400593607989185347.64
7905690538.188099787029.097883823349.098201203589.82
7912993893.828315915441.457907107597.828208994094.55
7947893535.278349995466.187914102997.828239609125.82
7952697770.188396224841.457927640684.368352575028.36
8131449759.278694619845.828155345951.278376635294.55
8388583725.0987382607608294985193.458540294446.55
Averages
7951310145.868258608481.77948171486.958152175374.06

Analysis


The persistent collections perform rather well, generally within 5% of their mutable counterparts given this set of test data. While I didn't calculate it, you can see from the variance in the runs that there's a wider standard deviation from the mean for persistent collections, so their performance is ever so slightly less predictable, though not drastically so.

Interestingly enough, the struct-based persistent collections outperformed the class-based versions. I expected the reverse considering struct operations are not always properly optimized by the JIT. Even though the entire struct would fit into a register, the JIT may still allocate a stack slot for it, which would be more expensive than the guaranteed register-sized operations of a class type. Upon further thought, I suspected that perhaps the struct versions are faster simply because the VM doesn't need to perform a null check on dispatch, but the class-based versions use all-static method calls which don't perform null checks as far as I know.

I don't yet have a good explanation for this, but given the results, I believe I will move all Sasa collections to struct implementations as it simply provides more flexibility, immunity from null errors, and no appreciable runtime overhead.

If I had more time I would make these tests a little more rigourous by varying the test vectors in a more controlled fashion instead of just random, ie. use stepped, random, and other types of enqueue/dequeue sequences, to determine exactly how persistent and mutable collections behave based on inputs. I suspect the performance profiles will differ more drastically in such different scenarios.

This test was enough to demonstrate to me that persistent collections are sufficiently performant to be used in daily code, particularly given their numerous other advantages.

All source code and raw timing/memory tables can be downloaded here.

Comments

Popular posts from this blog

async.h - asynchronous, stackless subroutines in C

The async/await idiom is becoming increasingly popular. The first widely used language to include it was C#, and it has now spread into JavaScript and Rust. Now C/C++ programmers don't have to feel left out, because async.h is a header-only library that brings async/await to C! Features: It's 100% portable C. It requires very little state (2 bytes). It's not dependent on an OS. It's a bit simpler to understand than protothreads because the async state is caller-saved rather than callee-saved. #include "async.h" struct async pt; struct timer timer; async example(struct async *pt) { async_begin(pt); while(1) { if(initiate_io()) { timer_start(&timer); await(io_completed() || timer_expired(&timer)); read_data(); } } async_end; } This library is basically a modified version of the idioms found in the Protothreads library by Adam Dunkels, so it's not truly ground bre

Building a Query DSL in C#

I recently built a REST API prototype where one of the endpoints accepted a string representing a filter to apply to a set of results. For instance, for entities with named properties "Foo" and "Bar", a string like "(Foo = 'some string') or (Bar > 99)" would filter out the results where either Bar is less than or equal to 99, or Foo is not "some string". This would translate pretty straightforwardly into a SQL query, but as a masochist I was set on using Google Datastore as the backend, which unfortunately has a limited filtering API : It does not support disjunctions, ie. "OR" clauses. It does not support filtering using inequalities on more than one property. It does not support a not-equal operation. So in this post, I will describe the design which achieves the following goals: A backend-agnostic querying API supporting arbitrary clauses, conjunctions ("AND"), and disjunctions ("OR"). Implemen

Easy Automatic Differentiation in C#

I've recently been researching optimization and automatic differentiation (AD) , and decided to take a crack at distilling its essence in C#. Note that automatic differentiation (AD) is different than numerical differentiation . Math.NET already provides excellent support for numerical differentiation . C# doesn't seem to have many options for automatic differentiation, consisting mainly of an F# library with an interop layer, or paid libraries . Neither of these are suitable for learning how AD works. So here's a simple C# implementation of AD that relies on only two things: C#'s operator overloading, and arrays to represent the derivatives, which I think makes it pretty easy to understand. It's not particularly efficient, but it's simple! See the "Optimizations" section at the end if you want a very efficient specialization of this technique. What is Automatic Differentiation? Simply put, automatic differentiation is a technique for calcu