5

What are efficient algorithms for immutable dictionaries/sets? By efficient I mean they either have better or comparable time and/or memory performance compared to their mutable versions. I don't necessarily mean this in the context of functional programming, where I've seen immutability equated to persistent data structures.

A concrete example is Guava, where I have seen memory savings when used with sets that don't need to be modified.

closed as too broad by gnat, Robert Harvey, amon, 8bittree, Thomas Owens Dec 30 '17 at 15:25

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    Look here. – Robert Harvey Dec 15 '17 at 20:02
  • Also, I assume that you're referring to writes, not reads. Reads from an immutable dictionary or data set have the same performance characteristics as their mutable counterparts, give or take the need for thread safety semantics like locking (which immutable collections do not require). – Robert Harvey Dec 15 '17 at 20:05
5

There are data structures that a easy to read and (relatively) slow to build, so they tend to be more suitable for immutable data structures.

Just for example, for a mutable set, you'd typically use some sort of tree structure (e.g., red-black tree or AVL tree). Such a tree has reasonable complexity for both lookups and modifications (typically O(log N) for either). A tree, however, has two (or three) pointers per data item. That reduces the data density, so you get relatively poor cache usage.

If your dictionary is immutable, you can use a sorted array instead. This eliminates the pointers, increasing the data density, so you get (at least somewhat) better cache usage.

In a typical case, using a sorted array will let you go a step further than that though. A tree supports binary searching to find the item of interest. If your keys have a reasonably predictable distribution (most often roughly uniform, but other distributions can be handled as well), you can use an interpolating search instead.

For example, consider looking up a word in a (physical) dictionary. If you're looking for "cab", you know you want to look somewhere close to the beginning; if you're looking for "yes", you know you want to look close to the end.

An interpolating search does roughly the same--uses the key to compute a decent approximation of the starting location for the search, rather than always starting at the middle (and the same on subsequent searches).

Assuming the key distribution is at least somewhat predictable, this will typically improve your lookup complexity to roughly O(log log N), which is often referred to as "pseudo-constant", because it really is essentially constant for almost any size of collection encountered in reality.

For example, let's assume common (base 10) logarithms. Every size from 100 through 109 has log log N = 1. Every size from 1010 through 1099 has log log N = 2.

For any practical purpose, N=2 is already well past the maximum we can ever expect to deal with--to get to N=3, we'd need a collection of at least 10100 items. To put that in perspective, there are about 1057 atoms in the solar system, so if you could store each item using only a single atom, you'd still need the atoms from approximately 1043 solar systems to store a collection of 10100 items.

0

By efficient I mean they either have better or comparable time and/or memory performance compared to their mutable versions.

Strictly speaking I don't believe this can exist, because you can always show me an immutable data structure and I can find ways to make something cheaper if it could be made mutable. For example, I might be able to eliminate the requirement for garbage collection or reference-counting if it was mutable.

There are data structures that are well-suited to become immutable though where the costs are relatively cheap. Most of the non-trivial ones are typically at least partially contiguous. That allows the costs of ref-counting or GC to be trivialized if the nodes are unrolled and store multiple elements each, not one element per node.

There's also often a balancing act between shallow copying more pointers vs. deep copying fewer non-unique elements because any data structure can be made immutable if you just copy the whole freaking thing every time you want to change anything, but that could be explosive in memory and processing requirements. On the flip side, if you shallow reference every single individual element, that could be explosive in memory and processing requirements with all the extra pointers, all the extra indirection and potential memory fragmentation, the cost of ref-counting or GC having to be paid for every single element, etc.

So often I think the most efficient immutable data structures for sets and dictionaries are going to be partially contiguous ones, like a hash table using open addressing but instead of using one giant array for the whole table, it uses unrolled blocks storing, say, 64 keys each. Another example would be an n-ary tree storing many keys in one node.

Of course a hash table using separate chaining is really straightforward to make immutable since making singly-linked LIFO lists immutable just requires storing a different head pointer per immutable list. However, it's straightforward but not very cheap since that implies, again, reference-counting or GC paid on a per-element level.

Also chances are that you'll need something like a "builder" or "transient" to express what you want to do with it, since you don't want to pay the cost of generating a new immutable instance every single time you just insert or remove one key.

A concrete example is Guava, where I have seen memory savings when used with sets that don't need to be modified.

Here perhaps it's not so much about immutability but just a data structure being able to work off the assumption that elements will simply be inserted to it and known in advance and not having to deal with dynamic removal and insertion of elements after it's built.

In that case, for example, you can use a sequential memory allocator as one optimization because you don't have to handle freeing memory for individual elements since elements are never going to be individually removed from the data structure. All you have to be able to do is purge all the memory for all elements when the data structure is destroyed.

Also if the elements are all known in advance, you might be able to avoid having to do reallocations to expand the size of the structure. You can make it perfectly-sized upfront since you know all the elements you're going to be inserting to it upfront so you don't have to reserve any additional memory for future insertions.

Data structures which only need fulfill these types of "static" and not "dynamic" requirements also provide plenty of room for post-processing after they're built. A binary tree might be post-processed to reallocate its nodes in a cache-friendly access pattern, for example. You can afford that with a static kind of data structure that doesn't deal with dynamic insertions and removals since there's a clear build phase which leaves room for post-processing, after which you no longer have to deal with changes to the data structure.

Ex: Mutable "Clear" Method

Any data structure which has fewer functional requirements to deal with will generally have more room to optimize. But here it's not about immutable data structures so much as data structures which can just be built in advance and don't have to deal with dynamic insertions and removals. Such data structures could still be made mutable and stay just as cheap. For example, such a data structure might still provide a mutable clear method to clear the entire contents of the set/dictionary, and providing such a mutable method would not require it to lose those potential optimizations described above. So there's no case as far as I see where immutability makes anything cheaper, since immutability imposes more functional requirements on a data structure, so to speak, not less.

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