Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

When working with an immutable set or map, like the ones found in many functional programming languages, operations that would otherwise modify the container generate a new container instead.

I know that most list operations in functional languages do not result in a copy of the list and just rearrange pointers. This is why working with lists is extremely efficient.

I am curious whether immutable maps are similar or if an entirely new map is created after each operation. I am asking because a library I wrote manipulates a lot of maps and I am curious whether I will see a performance boost if I switch over to immutable maps. Currently, I am just looping over my map adding or throwing away key/value pairs as I go.

share|improve this question
1  
I wouldn't look at immutable collection for performance, they have other benefits. AFAIK it is rather rare for immutable collections to be actually faster than mutable ones, all other things (sophistication of implementation, cleverness of algorithms, performance of relevant primitives such as memory allocation and looping) being equal. That is not to say they are slower, either. –  delnan Mar 9 '13 at 18:19
3  
Okasaki's book is the go-to resource. –  Robert Harvey Mar 10 '13 at 0:14
    
List operations in imperative languages don't copy a list, they just re-arrange pointers - at least for operations where that's appropriate. But changing a pointer in a list item is a mutation. Pure functional list operations tend to copy the part of the list where imperative languages would just fiddle pointers, though the benefit is a greater tendancy to share list tails for multiple lists. –  Steve314 Mar 10 '13 at 22:13
add comment

3 Answers

up vote 5 down vote accepted

As far as I can tell, functional sets are generally implemented as trees, so sharing nodes between concurrent versions makes sense. Some functional languages, notably F# and Clojure, open source their code on github, you can look there for concrete details. F# uses trees.

Some time ago, I have been comparing performance of F# immutable Set (Microsoft.FSharp.Collections) vs mutable .NET HashSet (System.Collections.Generic). I do not have results available to share now, but as far as I remember lookup / union / intersection times were similar for both and when adding large numbers of entries the immutable set performed slower by some low constant factor (something around 3 or 4).

Apart from the book, there's also Okasaki's thesis available, which was the foundation for the book - glimpsed through it and it looks rather hard (well, like a proper thesis should), though you might find it useful.

share|improve this answer
    
+1 for mentioning Okasaki's, his thesis has become the standard starting point for people who want to study pure data structure techniques. It is hard yes, but then working with immutable structures is, you should have at least a cursory understanding of the HM type system and ability to read basic ML to start, after that it's something everyone learning functional programming should wade through. It's a common language among functional programmers. –  Jimmy Hoffa Mar 27 '13 at 14:13
    
Also worth mentioning is many Haskell libraries have been tuned like crazy to have every optimization available while staying pure, and they're all open source on Hackage. The Data.Map, Data.Set, and Data.List libraries are highly optimized and worth looking at if you want to take the approach of reading implementations to see how immutable structures can be tuned. –  Jimmy Hoffa Mar 27 '13 at 14:18
add comment

Sharing — referencing the same data block from several objects, so that several data structures end up with part of their memory in common — is one of the major points of immutable data structures. Immutable data structures automatically share the common pieces that they're built from. (Data structures built independently don't share anything — there are techniques for that, in particular hash consing.)

In many ways, the fundamental mutable data structure is the array, and the fundamental mutation operation is to modify one element of an array. A mutable data structure consists of arrays that contain pointers to (or into) each other.

In an immutable data structure, you have to decide all the elements of a data block when you build that block. That tends to drive towards small data blocks. When you need to store a large amount of data, you pretty much need to apply a divide-and-conquer strategy: unless the data is small enough to store in one lump, you divide it into several pieces, and store a lump of pointers to those pieces — which themselves may be again pointers to smaller pieces, and so on recursively. That makes the resulting data structure a tree. The tree is the basic immutable data stucture.

Any mutable data structure can be represented as an immutable data structure with a logarithmic loss of time and a linear increase in memory. That is, if you have an algorithm that operates in time N and uses M units of memory, you can convert it to use only immutable data structures with O(M) more memory used and operating in time O(N*log(N)). You can do this by encoding every array as a binary tree where the leaves are the elements of the tree. To access or modify an element costs O(1) time in an array and O(log(N)) in a tree with the same number of leaves. This is of course a maximum: often there is a less general but more efficient approach.

This means that there is a bound to the build-up caused by switching to immutable data structures. You'll never experience anything like a quadratic explosion.

In practice, every immutable data structure you'll find in any halfway-decent library will be written around such divide-and-conquer lines, often with copious tricks to compensate the logarithmic build-up. Sharing comes for free: most of the time it would take some work to avoid it. Building short-term data structures that are derived from another data structure, differing only in a few values, is something programmers do all the time; you can be confident that it will result in sharing under the hood. (You can test by checking physical equality of non-modified parts of the data structure, by keeping tracks of your program's memory consumption, or by looking at the program executing in a debugger).

Building a new data structure that differs in only a few places from an old one and discarding the old one is also something programmers do often, and you can often expect to find implementations of immutable data structures that are optimized for that case. Look at indications of amortized complexity.

Chris Okasaki's book Purely Functional Data Structures is a good reference if you need to write your own immutable data structure. Expect the implementers of immutable data structure libraries to have read this book.

share|improve this answer
add comment

When dealing with sets and maps, a lot depends on the specific data structure. Trees are quite common for associative containers, including sets and maps, so I'll deal purely with those.

For unbalanced binary trees, an insert operation operation works in two phases - the top-down part to find the insert point and the bottom-up part to modify (or create) the new tree.

The point here is that for each node, only one of the two subtrees contains the insertion point, and only that one subtree needs to be duplicated for a pure-functional tree insert. So the only new nodes needed are in a chain from the insert point back up to the root.

This means that assuming the tree is (accidentally) balanced, you have O(log n) new nodes for a single insert - the number of new nodes depends on the depth of the tree, not the total size.

A key assumption here is that nodes only store pointers to their children. In imperative languages, it's common for nodes to store pointers back to their parents. This means there are cyclic references, so the data structure must be copied as a whole. There are similar issues with threaded binary trees. The general rule is that when creating a new state, every strongly connected component must be copied as a whole - in practice, these data structures are rarely used in functional programming.

Of course parent links can be stored outside of the tree data structure, and the functional way to handle this is using a zipper. One issue (sometimes advantage, sometimes disadvantage) is that the zippers, like externally-stored parent links generally, refer to the particular state they were created to refer to, not to any newer state.

With balanced binary tree schemes such as AVL trees and red-black trees, there will be more complex changes due to rebalancing, but you still generally get the same O(log n) nodes copied per single item insert - unless you have parent links again.

Digital trees or tries use a tree data structure, but base that on the binary (or digital, at least) representation of the keys, not the ordering. For example, using base 10 digits, you might find the item for key 123 by starting at the root node, following child link 1, then child link 2, then child link 3. The depth of these trees is logarithmic in the maximum possible size because if you have an n-digit number and k distinct digits, you can form k^n digit strings so the maximum possible size is k^n. For example, with three decimal digits, you can only have 1000 different keys, so the maximum size is 1000 - 3 is the base 10 logarithm of 1000.

The story is similar to binary trees, except that you tend to have better constants (the tree branches more ways at each node) and you can often claim O(1) because the keys all have a fixed number of bits. This structure, with hashes for keys, can even be used to give a kind of hash table - with both advantages and disadvantages over the usual array-based hash tables from imperative programming.

There's an in-between structure called a ternary tree - basically a tree of binary trees, so you binary search for the first character of the string, then the next and so on. Again, it's still a tree, and provided there are no parent pointers or other cyclic references each insert should only have to copy O(log n) nodes.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.