To clarify, when I mean use the terms persistent and immutable on a data structure, I mean that:

  1. The state of the data structure remains unchanged for its lifetime. It always holds the same data, and the same operations always produce the same results.
  2. The data structure allows Add, Remove, and similar methods that return new objects of its kind, modified as instructed, that may or may not share some of the data of the original object.

However, while a data structure may seem to the user as persistent, it may do other things under the hood. To be sure, all data structures are, internally, at least somewhere, based on mutable storage.

If I were to base a persistent vector on an array, and copy it whenever Add is invoked, it would still be persistent, as long as I modify only locally created arrays.

However, sometimes, you can greatly increase performance by mutating a data structure under the hood. In more, say, insidious, dangerous, and destructive ways. Ways that might leave the abstraction untouched, not letting the user know anything has changed about the data structure, but being critical in the implementation level.

For example, let's say that we have a class called ArrayVector implemented using an array. Whenever you invoke Add, you get a ArrayVector build on top of a newly allocated array that has an additional item. A sequence of such updates will involve n array copies and allocations.

Here is an illustration: enter image description here However, let's say we implement a lazy mechanism that stores all sorts of updates -- such as Add, Set, and others in a queue. In this case, each update requires constant time (adding an item to a queue), and no array allocation is involved.

When a user tries to get an item in the array, all the queued modifications are applied under the hood, requiring a single array allocation and copy (since we know exactly what data the final array will hold, and how big it will be). Future get operations will be performed on an empty cache, so they will take a single operation. But in order to implement this, we need to 'switch' or mutate the internal array to the new one, and empty the cache -- a very dangerous action.

However, considering that in many circumstances (most updates are going to occur in sequence, after all), this can save a lot of time and memory, it might be worth it -- you will need to ensure exclusive access to the internal state, of course.

This isn't a question about the efficacy of such a data structure. It's a more general question. Is it ever acceptable to mutate the internal state of a supposedly persistent or immutable object in destructive and dangerous ways? Does performance justify it? Would you still be able to call it immutable?

Oh, and could you implement this sort of laziness without mutating the data structure in the specified fashion?

  • 1
    It depends on what guarantees you are making to the clients. If this were to run in a multi-threaded environment, I wouldn't dare call it immutable as it isn't and the assumptions associated with immutability would not hold. – Oded Oct 6 '12 at 19:21
  • It wouldn't be an immutable datastructure, but it would be a confluent persistent datastructure. – dan_waterworth Oct 6 '12 at 19:55

I would be very loath to call a data structure "immutable" unless, once it was exposed to the outside world, unless all changes that are made to its internal state continue at all times to leave the object in the same observable state, and unless the state of the object would be valid with any arbitrary combination of those changes either happening or not happening.

An example of a reasonably-good "immutable" object which obeys this principle is the Java string type. It includes a hash-code field which is initially zero, but which is used to memoize the result of querying the hash code. The state of a string with a zero hash-code field is semantically the same as that of a string where the hash-code field is filled in. If two threads simultaneously attempt to query the hash code, it's possible that both may end up performing the computation and storing the result, but it doesn't matter because neither store will affect the observable state of the object. If a third thread comes along and queries the hash code, it might or might not see the stores from the first two, but the returned hash code will be the same regardless.

(BTW, my one quibble with Java's string-hashing method is that it's possible for the hash function to return zero for a non-null string. I would have thought it better to have the hash function test for zero and substitute something else. For example, if the hashing step is such that adding a single character to a string whose hash is zero will always yield a non-zero hash, simply return the hash of the string minus the last character. Otherwise the worst-case time to hash a long string thousands of times may be much worse than the normal-case time.)

The big things to beware of are (1) sequences of operations which change the state of an object and then change it back, or (2) substitution of objects that appear to have the same state, but don't. Ironically, Microsoft's fixing of what it regarded as bug in its default Struct.Equals method makes #2 harder to protect against. If one has a number of immutable objects which hold references to what appear to be identical immutable objects, replacing all those references with references to one of those immutable objects should be safe. Unfortunately, the Equals overrides for system types Decimal, Double, and Float will sometimes report true even when comparing slightly-different values. It used to be that wrapping one of those types in a struct and calling Equals on that struct would test for true equivalence, but Microsoft changed things so a struct will report Equals if its members do, even if those members hold non-equivalent values of the aforementioned types.

  • Thank you! Your answer is very informative. Basically, using the example above, the object can be totally thread-safe and without any locking, if I can perform the switch in a single, atomic operation. Add, Set, and other operations will either be performed on the non-optimized version -- which means you'll get an non-optimized version back -- or on the optimized version. Gets might optimize the data structure twice, but the result will always be the same. The results will be indistinguishable. Except that if you get a non-optimized version back, it will still need to be optimized. – GregRos Oct 6 '12 at 19:59
  • That's the idea, yes. It's worth noting that the optimal design for a persistent data structure depends how it's used. For example, suppose one designs a data structure so that most items hold a link to an earlier version and a list of changes that have been applied to it. If one wants to change something 1,000 times and be able to access all 1,001 versions of it, such a structure can be very efficient. On the other hand, if one won't anything older than the 100th-latest version, replacing the 100th-latest version's link to older versions with a copy of the data may save time and memory. – supercat Oct 6 '12 at 22:27

A strong argument against allowing internal mutable state is that it requires synchronization. If multiple threads access the structure, you need to synchronize on operations that update the state.

I suggest you to read Okasaki's famous book Purely Functional Data Structures (PDF). It's worth it. In particular, he solves the question how to use laziness to make data structures that are persistent and immutable (I mean perfectly immutable, no internal changeable state except lazy evaluation and memoization of evaluated values - just what Haskell does).

Not only he describes structures with efficient amortized costs, he also describes structures that have efficient worst-case costs. The idea is to force a small part of unevaluated computations at each operation.

To give an example how it can work, in Section 4.2 he describes real-time queues. In Haskell, it'd look like

module RTQueue(RTQueue(), empty, add, headQ, tailQ) where

-- Invariant: |schedule| = |front| - |rear|
data RTQueue a = RTQueue { front :: [a], rear :: [a], schedule :: [a] }

empty = RTQueue [] [] []

-- Smart constructor that preserves the invariant.
-- We get |f| - |r| + 1 = |s| and fix it so that
-- the invariant |f| - |r| = |s| holds.
-- Either we force another element of `s` or
-- if `s` is empty we perform a rotation.
queue :: [a] -> [a] -> [a] -> RTQueue a
queue f r (_:s')  = RTQueue f r s'
queue f r []      = let f' = rotate f r []
                    in RTQueue f' [] f'
    -- rotate f r a = f ++ reverse r ++ a
    -- and always |r| = |f| + 1
    rotate :: [a] -> [a] -> [a] -> [a]
    rotate []     [y]    a  = y : a
    rotate (x:f') (y:r') a  = x : rotate f' r' (y : a)

add :: RTQueue a -> a -> RTQueue a
add (RTQueue f r s) x = queue f (x : r) s

headQ :: RTQueue a -> a
headQ (RTQueue (x:_) _ _) = x

tailQ :: RTQueue a -> RTQueue a
tailQ (RTQueue (_:f) r s) = queue f r s

The queue is split into two parts: front from which we take elements and rear which is reversed and to which we prepend elements. From time to time we rotate the queue - we reverse rear and append it to front. The third value schedule holds front after each rotation, but during each add (or tailQ) one of its element is forced (this is done simply by pattern matching on it in queue). The result is that the front list is gradually evaluated and is ready when needed by headQ or a subsequent rotate. This queue has worst-case complexity O(1) for its operations.

There is a functional data structure (not known at the time Okasaki wrote his book) that allows to represent finite sequences with amortized constant access time to both ends and amortized logarithmic access times anywhere, including logarithmic union time. See Data.Sequence.

  • Thank you. I'm actually familiar with the book, the data structure described here, and finger trees (which is how Data.Sequence is implemented). I've implemented these data structures myself. – GregRos Oct 7 '12 at 8:02
  • There's a useful subset of internally-mutable externally-mutable classes in which the internal representation of the object may change, but where none of the changes, singly or in any combination, affect the visible state of the object. For example, Java's strings have a cached hash-code field. Every string has a fixed hash code value, the cached field will always either be zero or that value, and the observable state of the string is the same in either case (beyond the fact that if the value is not faster, requests for the hash code can be processed faster). – supercat Oct 8 '12 at 23:26
  • Classes of that particular kind do not require any sort of inter-thread synchronization for correctness (though in some rare cases adding synchronization may improve efficiency by eliminating redundant work). – supercat Oct 8 '12 at 23:27
  • @supercat I see. But I'm not sure about not requiring synchronization. In the case of hashCode it's likely that saving hashCode to a variable is an atomic operation. But if it were stored in two variables, for example, or in a variable whose update isn't an atomic CPU operation, another thread could read and observe its value in an inconsistent state when only one part of the value is stored and the other still contains zero bits. I cannot imagine how this could be done without synchronization. – Petr Pudlák Oct 9 '12 at 6:26

most uses for immutable copy-on-write stuff like that is for thread safety so you can use a CaS primitive for updates and not need a lock

with the underlying structure being mutable this is no longer thread safe

also for one example that would invalidate the immutability would be: (using D's template syntax) assuming this is under the hood with a pointer and length field

ImmutableArr!int a ={1,2,3,4}
ImmutableArr!int b = a.insert(2,9)

if b gets expanded in place then a would contain {1,2,9,3} after the insert

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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