Immutability in C# Part Eleven: A working double-ended queue
At long last, let's get to that double-ended queue. Sorry for leaving you in suspense!
Last time we came up with a non-solution -- as commenters immediately discovered, the given algorithm and data structure are deeply inefficient. However, the basic idea is sound. There are a number of ways to solve this problem, but the way I'm going to talk about today is a much more efficient variation on the theme of our previous unsuccessful attempt. That is, have cheap access to the endpoints, and have some kind of more expensive "cold storage" in the middle.
In order to solve this problem I'm first going to introduce some helper classes which solve a much simpler problem. I want to implement a very limited kind of deque, namely one which can only store one, two, three or four items. A "dequelette", if you'll allow the silly name.
Note that there is no "empty" dequelette. Since this class does not actually fulfill the contract for a deque, I'm not going to have it implement IDeque<T>. Rather, I'll just have a base class that these four dequelette types derive from:
public class Deque<T> : IDeque<T>
{
private abstract class Dequelette
{
public abstract int Size { get; }
public virtual bool Full { get { return false; } }
public abstract T PeekLeft();
public abstract T PeekRight();
public abstract Dequelette EnqueueLeft(T t);
public abstract Dequelette EnqueueRight(T t);
public abstract Dequelette DequeueLeft();
public abstract Dequelette DequeueRight();
}
The implementations of dequelette classes One, Two, Three and Four are obvious; rather than take up a lot of space here, I'll put them on a separate page along with the rest of the implementation.
OK. What does this trivial little class hierarchy buy us? We have an immutable deque which can contain one, two, three or four elements, and that's all. Useful? Yes.
Here's my new recursive definition of a deque: a deque of T's is:
- empty, or
- a single element of type T, or
- a left dequelette of T, followed by a middle deque of dequelettes of T, followed by a right dequelette of T.
That bit in boldface is the key. The cold storage in the middle is NOT another deque of items, it is a deque of dequelettes of items. (In particular in this implementation it will furthermore be a deque of dequelettes where every dequelette is of size three. Each item in the cold storage holds three items of the outer deque.)
This use of the type system may be a bit confusing. Let's draw it out. Without loss of generality, let's suppose that we're enqueuing 1, 2, 3, 4, ... onto the right hand side of a deque, starting with the empty deque. The structures we built up go like this:
Deque<int>.Empty
Deque<int>.SingleDeque (1)
Deque<int>( One(1) -- Deque<Deque<int>.Dequelette>.Empty -- One(2) )
Deque<int>( One(1) -- Deque<Deque<int>.Dequelette>.Empty -- Two(2, 3) )
Deque<int>( One(1) -- Deque<Deque<int>.Dequelette>.Empty -- Three(2, 3, 4) )
Deque<int>( One(1) -- Deque<Deque<int>.Dequelette>.Empty -- Four(2, 3, 4, 5) )
Now at this point we are about to enqueue 6, but there is no more room on the cheap storage at the right endpoint. We need to make more room, so let's take three of those out of there, make a dequelette out of them, and stuff them into the right hand side of the cold storage. Notice that the thing in the middle is a single-element deque which contains a dequelette. It is not a three-element deque of integers:
Deque<int>( One(1) -- Deque<Deque<int>.Dequelette>.Single (Three(2, 3, 4) ) -- Two(5, 6))
Deque<int>( One(1) -- Deque<Deque<int>.Dequelette>.Single (Three(2, 3, 4) ) -- Three(5, 6, 7))
Deque<int>( One(1) -- Deque<Deque<int>.Dequelette>.Single (Three(2, 3, 4) ) -- Four(5, 6, 7, 8))
Again, as we are about to enqueue 9, we're out of space in the cheap seats. Move stuff into cold storage. That causes the cold storage to go from a single-element deque to a two-element deque. Note the type of the innermost middle empty element is a deque of dequelettes, where each dequelette contains three dequelettes, each of which contains three ints. So the innermost cold storage will be storing nine items per node when eventually we start pushing stuff into it.
Deque<int>(
One(1)
Deque<Deque<int>.Dequelette>(
One(Three(2, 3, 4))
Deque<Deque<Deque<int>.Dequelette>.Dequelette>.Empty
One(Three(5, 6, 7)))
Two(8, 9))
Our last example was inefficient. Is this efficient?
When enqueueing, most of the time the operation is cheap, just creating a new dequelette. Every third enqueue is expensive; it requires us to do two operations: first, to turn a four-dequelette into a two-dequelette, and second, to create a three dequelette and enqueue it into the cold storage. Every ninth enqueue causes the cold storage to itself have to do an expensive operation on its cold storage. And every twenty-seventh operation requires... and so on. If you sum up that series, you find that the most expensive possible operation costs O(log n), but those are so few and far between that the average cost of enqueueing each element is O(1). Which is awesome.
The other objection that my psychic powers are picking up on is "holy goodness, what horrors must that be wrecking upon the type system?" Relax. The generic type system is plenty buff enough to handle this. Remember, it's a logarithmic thing. A deque with a million integers in it will have a Deque<Deque<Deque<... <int>...> no more than, say, twenty deep. The generic type system is plenty buff enough to handle a recursively defined generic type a mere twenty levels deep.
Also, remember, this is a generic type, not a C++ template. All the code for that crazy generic type is generated once by the jitter, and then the same code is shared for every reference constructed type where the type argument is a reference type -- which in this case, is all of them. That's the great thing about generic types; because they guarantee at compile time that everything in the implementation will work out at runtime, the code can be reused.
What about dequeueing? Same deal. When the cheap storage on the end points gets down to a single element dequelette, just dequeue a three-dequelette from the code storage and use that as the new cheap storage. Again, at least two thirds of all operations are cheap and the price of the expensive ones grows slowly, so the amortized cost of each dequeue is constant.
As a more advanced topic, which I may come back to at some point in the future, we can also implement cheap concatenation of two deques if we allow the cold storage to hold both twos and threes, instead of just threes. I have an implementation but the code for that gets really quite tedious, so I won't show it here. Using twos or threes makes it potentially slightly more expensive than just using threes because you go from a guarantee of two thirds of the operations being cheap to only half being cheap. But on average the amortized cost is still constant per operation whether it is twos or threes.
If you're still having trouble grasping the details of this data structure, try drawing out all the references on a whiteboard. You get a very odd tree-like structure. With most trees, the nodes "in the middle" are the "obvious" ones because they are near the root. In this tree structure (and it is a tree structure in the final analysis!) its the leaf notes near the edges which are the most "shallow" nodes. The middle is where the tree gets "deeper". This is exactly what you want for a structure where the stuff on the edges needs to be cheap to access compared to the stuff in the middle.
Incidentally, this kind of tree is an example of a "finger tree". The "fingers" are the special references to the various special "edge" nodes.
We could keep on going and talking about more and more advanced analysis of immutable structures, but I think I'll stop here. This gives the flavour of this style of programming pretty well I think, so no need to labour the point further.
Acknowledgements:
One of the reasons I write about this stuff is because it forces me to learn about it. I learned a lot, and I hope you did too. For this series, I am indebted to Chris Okasaki's excellent book "Purely Functional Data Structures"; the thesis it was based upon is here. Also to Ralf Hinze and Ross Paterson's excellent paper on finger trees.
Coming up next: I'm not exactly sure. I have a pretty kick-ass implementation of some very fun algorithms which demonstrate the practical advantages of programming in an immutable style. Or perhaps I'll change gears a bit and talk about something else entirely. Either way, it'll be a fabulous adventure I'm sure.
Comments
Anonymous
February 12, 2008
PingBack from http://www.biosensorab.org/2008/02/12/immutability-in-c-part-eleven-a-working-double-ended-queue/Anonymous
February 12, 2008
Thanks for the kind words about my book. I actually just wrote a 10 year retrospective for it on my blog (linked above). As I'm sure you realize, there's a minor problem with this version of deques, which is that the amortized bounds can break down when you take advantage of the immutability to go back and work with old instances. For example, suppose you've just built up a big deque where inserting one more item is going to a cause an O(log n) cascade of inserts into deeper and deeper levels. Call that deque D. Now, if you keep inserting into D, throwing away the new deque, and going back to insert into D again, you'll hit the O(log n) case every time. Of course, this pathological case is unlikely in practice. There are ways around this. For example, when inserting into a deque that has a Four on the right, you could begin by modifying the existing deque, peeling off the Three, adding it to the middle, and leaving a One on the right. Then continue the insert by making a new deque with a Two on the right. Modifying the existing deque goes against the idea of immutability, but can be ok since you're not changing the elements of the existing deque, merely reorganizing them. But of course, this kind of in-place update can interfere with some of the reasons for wanting the immutable deque in the first place, such as thread safety. Even that can be worked around by fiddling with the algorithm even more.Anonymous
February 12, 2008
Hi, how good to hear from you. Indeed, throughout this series I've been concentrating more on just getting across the "flavour" of working with immutable data structures, as it is a coding style which most C# programmers are unfamiliar with, but which we on the compiler team increasingly use ourselves. As my former professor P L Ragde pointed out in a comment a few episodes back, there are all kinds of ways that the simple "two stacks" queue can end up having large costs when you end up with that one "dangerous" structure that is going to be expensive to use, and then you use it over and over again in that state. This deque certainly has the same problem, as you point out. The depth of analysis that you go into in your book on how to measure these costs, track "credits", eliminate dangerous situations, and so on, is fascinating but far beyond the level at which I wanted to pitch this series of articles, so I deliberately held back from mentioning it directly. I shall certainly check out your blog. Thanks again for the note. Cheers, EricAnonymous
February 13, 2008
Excellent series! I like reading about these sorts of structures particularly because I never really thought about it before. That said, at the moment they do seem more like a thought exercise than something that can be used in everyday code. I would like to see some practical uses for these sorts of structures (and this style of coding in general).Anonymous
February 13, 2008
Very nice, great series. I understand Chris Okasaki's comment about being in a dangerous state, but with the Deque structure, the danger is never greater than O(log n). The danger in the Double Stack queue implementation could grow to O(n). I can definitely see benefit in the simple logic of the immutible data structures and the inherent thread safety they provide. Thanks for the mind stimulation!Anonymous
February 13, 2008
For some reason, there's been a lot of buzz lately around immutability in C#. If you're interested inAnonymous
February 13, 2008
Hi Eric, Fantastic work that would really make a great book… I’m sure you have plenty of ideas about what to write about next but I’m going to risk a suggestion: trading CPU for memory and vice versa. Ok, this is not a new concept, this is what caches are all about but with the rise of multi-core on one side and 64 bits addressing (more memory) on the other side, I think it’s about time with find a better way to deal with it. Maybe this is a CLR issue more than a language issue but .NET offers very little support for managing memory pressure. You can have a strong reference to some object or a weak one (which is unlikely to last very long) and nothing in between. So, you end up with selfish applications that take memory and never give it back even if another application could make better use of it. Virtual memory and swapping on disk with a 100 times penalty compared to Ram is clearly not a good solution… So, what if through a language construct or a .NET feature we could say that this object (block of memory) is worth that much to me (in CPU units multiplied by number of accesses maybe). The garbage collector may reclaim that object is someone else would be prepared to pay a higher price for it (to store the result of a more expensive calculation). But in any case, the object would know how to recreate itself (re-running the code associated with it) if the object was needed again after the memory was reclaimed. I hope you find this topic interesting or point me in the direction of another blogger that does… Thanks, FranckAnonymous
February 14, 2008
Cool. So, why Four, and not Three or Five?Anonymous
February 14, 2008
Good question Jay. This question leads to a great many more questions. I will try to break them down and answer them one at a time. The short answer is "because the concatenation algorithm which I did not show requires this". The long answer is:Why not bound the endpoint dequelettes at Three? If we bound them at Three then the inner deque must contain only Twos. We don't want that.
Why does bounding the end points at Three imply that the inner must contain only Twos? Suppose the inner deque contains Threes and the endpoints are bounded at Three. When the endpoint has a Three and you enqueue, that Three has to be moved to the inner deque; the endpoint is replaced with a One. That's an "expensive" operation, potentially O(lg n) in the number of total elements stored in the deque (if the inner deque is also in a "dangerous" condition, we could end up pushing items into inner deques all the way to the bottom.) Now suppose you immediately dequeue it. The One at the end goes away and is replaced with a Three from the inner store. Which is also potentially an O(lg n) operation, to undo all that work we just did. And now we're back in the bad state for enqueueing again. Essentially what we've got here is a deque which is in a state where if you alternate enqueue-dequeue-enqueue-dequeue-enqueue-dequeue, each one might cost O(lg n). My earlier analysis that "at least every other operation is always cheap" just went out the window -- here we have a situation where potentially every operation is maximally expensive. Now suppose that instead, when we enqueue on a "dangerous" deque, we stick a Two in the inner store and replace the endpoint Three with a Two. If you do that then every expensive operation is always followed by at least one cheap operation, so you get back the amortized good performance even for pathological cases. (Leaving aside Chris Okasaki's comments above about reusing a dangerous deque in the same state over and over again. Fixing that requires considerably more advanced analysis.)
OK, so why don't we want to stick only Twos in there? Because of the feature that I mentioned but did not implement. Consider how you would concatenate two deques each with many items in them. You've got (Left1 Middle1 Right1) concatenated with (Left2 Middle2 Right2). Clearly the concatenated deque has the form (Left1 Something Right2), but how to compute the Something? Well, its a deque itself, so use recursion. Somehow stuff the contents of Right1 and Left2 into Middle1, and then recursively concatenate the "new" Middle1 with Middle2. What exactly do we stuff into Middle1? If the endpoints are bounded at Three then Right1 and Left2 have between two and six items amongst them. Suppose they have three or five items. That cannot be broken up into any number of Twos, and therefore we will have to stuff either a Three or a One into Middle1, which then brings back the potential for pathological cases we were in before. However, if we bound endpoints at Four then the middle bit can safely contain Twos or Threes with no pathological cases. We have a Empty and Single deques specifically built for the case where the middle bit contains zero or one element. Every other possible number of elements that can be in the middle can be represented as a deque of some combination of Twos and Threes. (Because 2 = 2, 3 = 3, 4 = 2 + 2, 5 = 2 + 3, 6 = 2 + 2 + 2, 7 = 2 + 2 + 3, ...)
That explains why you want at least Four. Why not Five? With Fours, the concatenation algorithm has to be able to handle sixteen cases for the sizes of Right1 and Left2. With Fives, the concatenation would have to handle 25 cases. Why add nine more complicated cases when the algorithm doesn't need them?
Anonymous
March 11, 2008
Welcome to the forty-first Community Convergence. The big news this week is that we have moved FutureAnonymous
April 09, 2008
ummm. If you occur o(log n) operation speed on every other operation, that's still an o(log n) operation! This algorithm isn't -- strictly speaking -- an improvement.Anonymous
April 09, 2008
Robin, you are not working through the analysis. Suppose there are two operations. The cost of the first is 1. The cost of the second is 1 + 1. Total cost, 3. Suppose there are four operations. The costs are (1) + (1 + 1) + (1) + (1 + 1 + 1). Total cost, 7. Suppose there are 8. (1) + (1 + 1) + (1) + (1 + 1 + 1) + (1) + (1 + 1) + (1) + (1 + 1 + 1 + 1). Total cost, 15. Suppose there are 16... total cost, 31. When the cost is log(n), and only every other calculation is expensive, then the total cost is O(2n), so the amortized cost is O(2n/n) = O(1).Anonymous
May 15, 2011
I wanted to make sure I understood the generic madness of this correctly, so I wrote a simple visualization of your code. If anyone is interested, the code is at github.com/.../Immutable-Deque-visualization.