Lately I’ve taken a closer look at Julien’s F# implementations of Chris Okasaki’s Purely Functional Data Structures¹. AltBinaryRandomAccessList² caught my eye because judging from its existing update function it looked pretty simple to implement a remove function. As you may have noticed in all the major collections of F# data structures –FSharp.Core.Collections, FSharpx.core.DataStructures, and PowerPack — remove is pretty rare. And both update and remove seem to be neglected stepchildren in the purely functional data structure world. (By update and remove I am referring to functions updating and removing any element by index.)

Let’s look at Okasaki’s “pseudo-canonical”³ update for list, implemented in F#.

let rec loop i y (l:'a list) = 
    match (i,y,l) with
    | i',y,[] -> raise (System.Exception("subscript"))
    | 0,y',x::xs -> y::xs
    | i',y,x::xs -> x::(loop (i'-1) y xs) 

Do you see the problem? I’ll get back to it below.

How else might we implement update? We could just punt by converting to Array, updating, and back to list.

let punt i y (l:’a list) =
    let a = List.toArray l 
    a.[i] <- y
    List.ofArray a

And our last candidate is a hybrid, in which we progressively take the tail, collecting each head in an Array, until we pass the element for update. Then cons the new element and the elements from the Array.

let hybrid i y (l:'a list) =
    if (i = 0) then List.Cons (y, (List.tail l))
    else 
        let rec loop i' (front:'a array) back =
            match i' with
            | x when x < 0 -> front, (List.tail back)
            | x ->  
                Array.set front x (List.head back)
                loop (x-1) front (List.tail back)

        let front', back' = loop (i - 1) (Array.create i y) l

        let rec loop2 i' frontLen (front'':'a array) back'' =
            match i' with
            | x when x > frontLen -> back''
            | x -> loop2 (x + 1) frontLen front'' (front''.[x]::back'')

        loop2 0 ((Seq.length front') - 1) front' (y::back')

AltBinaryRandomAccessList is a structure with the same basic functions as List, but optimized for update. Here’s the type structure:

type AltBinRndAccList<'a> =
    | Nil
    | Zero of AltBinRndAccList<'a * 'a>
    | One of 'a * AltBinRndAccList<'a * 'a>

The element grouping represents the binary number of the count of elements, with least significant digit to the left⁴. This allows for a member update function which runs in O(log n) time. (The best we have seen so far is O(i), where i is the index of the target element, and punt runs in O(n)).

static member fupdate : ('a -> 'a) * int * AltBinRndAccList<'a> -> AltBinRndAccList<'a> = function
    | f, i, Nil -> raise Subscript
    | f, 0, One(x, ps) -> One(f x, ps)
    | f, i, One (x, ps) -> AltBinRndAccList.cons x (AltBinRndAccList.fupdate (f, i-1, Zero ps))
    | f, i, Zero ps ->
        let f' (x, y) = if i % 2= 0 then f x, y else x, f y
        Zero(AltBinRndAccList.fupdate(f', i/2, ps))

Now lets look at actual performance for our update alternatives⁵.

By way of comparison Array, which is not a purely functional structure, performs 10,000 updates in 0.1 millisecond at all scales, and really has no “worst case” single update. And notice because its function is not tail recursive Pseudo-Canonical eventually took a stack overflow. Also of interest, starting at the scale of 1,000 elements Punt outperforms Pseudo-Canonical in random updates, even though it is O(n) and the latter O(i). Time complexity does not tell the whole performance story.

So where does this leave remove? As it turns out my original idea to modify the update of AltBinaryRandomAccessList resulted with a function that was not tail recursive, but applying the hybrid technique to it resulted in a satisfactory algorithm⁶ and marginally improved performance, but like most every remove implemented in a purely functional list-like structure, the best time complexity you are going to get is O(i). (With a double-ended queue you can achieve ~O(i/2) .)

Here’s the comparative summary of remove performance on list-like structures. This time I include Array, where I copy the retained elements into a new structure one element shorter.

As you can see, remove is a viable function for moderate-sized data structures, but suffers from the limitation of its time complexity as you scale up. You could easily modify remove functions to process an ordered list or range of indexes and still have O(max i) performance.

One remaining question for purists: are the stepchildren still Purely Functional when they use mutation inside a function?

Notes

1 Okasaki, Purely Functional Data Structures, 1998

2 AltBinaryRandomAccessList

3 Okasaki, 1998.

4 See Okasaki, 1998 or Okasaki, Purely Functional Data Structures, 1996 for in depth discussion of numerical representations of data structures.

5 Times were taken on a not particularly fast dual core 64-bit system. Time multiples were calculated at a finer granularity, and so may not perfectly match the timings in milliseconds. AltBinaryRandomAccessList is abbreviated to “RndAcc”.

6 I hope to release it soon in an open source library.

In many disciplines engineers rely on performance characteristic reference tables of the materials and structures they work with. For a host of reasons these aids are lacking in the field of engineering application software. In the previous article in this series I introduced DS_Benchmark, an open source project for benchmarking F# data structure performance. Now I’m rolling out the first performance tables constructed with this tool. At the same time I’m launching the F# Data Structures pages as a centralized source of information on data structures across all available sources.

But won’t performance vary on different systems?

Of course. That has long been a problem with benchmarks represented in terms of how much time operations take. I am using a different approach, which is to compare operations in terms of their relative speed. Running tests on a 32 and 64-bit system I found the performance ratios remarkably consistent despite big differences in absolute performance.

Loading Data Structures

The Initial Data Performance tables rank data structures, originating data source, and data loading action from fastest to slowest for data sizes ranging from 1 to 10⁶. The column “TIME REL TO BEST” reports how many times longer a given combination takes compared to the top ranked.

Naturally you will be interested in specific comparisons. At the scale 10⁵ it is not surprising loading a List from another List of ascending integers is ranked the fastest for the “Init” action (List.ofList), but say your interest is in comparing performance of FSharpx DList to FSharpx PersistentVector when loading from an integer Array? Read down the chart until you find

and

The initial load performance of DList is 96.1 times as long as the top ranked, so divide Persistent Vector’s number by this to learn that it’s performance is 2.1 times slower than DList.

For more information on how the Performance Tables are constructed and how to interpret them see Performance Metric Tables Methodology and Reading the Data Structure Performance Tables.

While the tables comparing performance across data structures will probably be your go to tables, there are also tables comparing performance within a data structure, one for comparing across different methods of loading data (there are some surprising results) as well as actual performance when scaling up data sizes.

Pathologies and other observations

Reasoning about any kind of software performance is notoriously hard. Modern CPU pipelining architectures and instruction and memory caches make it darn near impossible. And there are many considerations to take into account regarding the choice of language. You need to do your own profiling. These performance tables are no substitute, but meant to be a guide. Here are some interesting things that come to light with the performance tables:

• Structures you would expect to display a more or less O(n) data loading performance seldom do. It’s much more common to display better performance up to some threshold (often 10⁴) and then perform worse than O(n).
• The Power Pack library’s HashMultiMap structure loads significantly faster using the AddOne action (a For...do loop) than the new() constructor up to scale 10⁵ where performance becomes roughly the same.
• FSharpx’s RealTimeQueue will stack overflow at scale 10⁵ on both the 32 and 64-bit systems I tested on.
• FSharpx’s BootstrappedQueue scales remarkably well when loading from a List. (Of course if you looked at the code for this structure you would understand why.) And so the AddOne action scales badly in comparison to Init at scale 10⁵.
• Not only is Array generally the fastest structure to initialize at all scales. It is often the fastest structure as the source for loading another structure.

Caveats

It’s important to remember the data load performance charts are the result of the performance interplay of the source and target data structures. If you are loading from I/O or some other “neutral” source consider comparing performance characteristics of Array loads, since Array seems to be consistently fast, and therefore somewhat neutral.

You will also see some strange blips at certain scales and for certain data and ordering characteristics. While I can’t vouch for every one, the oddities I looked at were consistently repeatable. I was still doing some development work while compiling these statistics. There is the possibility of bad data, and I eventually intend to re-compile all these stats. I deemed it more important to publish what I have and move forward with the next phases of my data structure performance survey.

Still to come

Still a lot of data structures to add to the data structure pages, and I still have to compile performance charactistics on common actions, like lookup, update, append, iterate. So I’ll have my head down working on this for a while. Please send comments, suggestions, and requests.

Here are some more .NET related performance benchmarks, also using the ratio comparison method.