There are some useful additions to the F# tool-belt coming up. Microsoft recently released a preview edition of immutable collections, and if all goes as planned I will release a suite of 6 purely functional linear data structures to FSharpx.Collections in just a couple of days.
Queue is a data structure that needs better representation in the functional world, and both collections make contributions, so this is an opportunity to do some performance comparisons of the queues available to F# programmers. The contenders are two queues from the .NET Framework, System.Collections.Generic.Queue and System.Collections.Concurrent.Queue, the upcoming FSharpx.Collections.Queue, and FSharpx.Datastructures.BatchedQueue, from which FSharpx.Collections.Queue was developed.
The first benchmark exercises something like “real world” usage of the queues with the following steps:
1) enqueue the number of elements indicated
2) peek and dequeue half that number
3) enqueue the same number to the resulting queue
4) peek and dequeue half the resulting size of that queue
5) enqueue one more time the original number
(Milliseconds on a 2.2GHz 4GB dual core 64-bit Windows 7 machine)
| 102 | 103 | 104 | 105 | 106 | |
|---|---|---|---|---|---|
| sys.queue | 0.8 | 0.8 | 1.2 | 5.2 | 45.7 |
| sys.concurrentqueue | 1.9 | 2.1 | 2.8 | 10.9 | 90.3 |
| sys.immutablequeue | 1.4 | 1.5 | 2.7 | 21.2 | 401.4 |
| fsharpx.queue | 1.5 | 1.6 | 2.7 | 20.8 | 404.3 |
| fsharpx.batchedqueue | 2.0 | 2.2 | 4.0 | 32.8 | n/a |
And then the obligatory “not so real world” benchmarks
Enqueue the indicated number of elements
| 102 | 103 | 104 | 105 | 106 | |
|---|---|---|---|---|---|
| sys.queue | 0.3 | 0.3 | 0.4 | 1.1 | 8.8 |
| sys.concurrentqueue | 0.4 | 0.5 | 0.6 | 1.7 | 12.8 |
| sys.immutablequeue | 0.5 | 0.5 | 0.8 | 4.0 | 91.6 |
| fsharpx.queue | 1.1 | 1.2 | 1.4 | 3.7 | 102.4 |
| fsharpx.batchedqueue | 1.2 | 1.2 | 1.5 | 7.8 | n/a |
Peek and Dequeue until the queue is empty
| 102 | 103 | 104 | 105 | 106 | |
|---|---|---|---|---|---|
| sys.queue | 0.2 | 0.2 | 0.2 | 0.7 | 6.2 |
| sys.concurrentqueue | 0.7 | 0.7 | 0.8 | 2.4 | 18.9 |
| sys.immutablequeue | 0.5 | 0.5 | 0.7 | 3.3 | 74.7 |
| fsharpx.queue | 0.6 | 0.6 | 0.7 | 1.3 | 26.8 |
| fsharpx.batchedqueue | 0.7 | 0.7 | 0.9 | 1.8 | n/a |
Initialize from a sequential source (an array unless otherwise indicated)
(The preview Immutable.Queue does not yet implement this capability.)
| 102 | 103 | 104 | 105 | 106 | |
|---|---|---|---|---|---|
| sys.queue | 0.3 | 0.3 | 0.4 | 1.2 | 9.6 |
| sys.concurrentqueue | 0.3 | 0.3 | 0.3 | 0.9 | 6.6 |
| fsharpx.queue ofList | 0.1 | 0.1 | 0.1 | 0.1 | 0.1 |
| fsharpx.queue | 0.7 | 0.7 | 0.7 | 1.2 | 13.1 |
| fsharpx.batchedqueue | 0.8 | 0.8 | 0.8 | 1.3 | n/a |
Use IEnumerable to iterate through each element
(queue of indicated size)
| 102 | 103 | 104 | 105 | 106 | |
|---|---|---|---|---|---|
| sys.queue | 0.1 | 0.1 | 0.2 | 0.7 | 6.9 |
| sys.concurrentqueue | 0.7 | 0.7 | 0.8 | 1.3 | 7.0 |
| sys.immutablequeue | 0.7 | 0.7 | 0.9 | 2.4 | 55.8 |
| fsharpx.queue | 2.1 | 2.1 | 2.4 | 4.7 | 27.6 |
| fsharpx.batchedqueue | 2.1 | 2.2 | 2.4 | 4.7 | n/a |
So which Queue is right for You?
That of course depends on your application. For raw speed the system generic queue is hard to beat. The concurrent queue compares well against generic in all categories in a single-threaded environment, so for raw speed it should be a contender in multi-threaded environments, unless composability and immutability is preferred.
Preview Immutable.Queue seems primarily intended for the C# world, but has adequate composability to make it suitable for F#. FSharpx.Collections.Queue performs just as well (sometimes better), and has a broader range of supporting functions including fold, foldback, reverse (usually O(1), worst case O(n)), ofSeq, and ofList.
Pingback: F# Weekly #3, 2013 « Sergey Tihon's Blog
Very nice summary. This will be a useful post to keep handy. Thanks for compiling it.