Immutability in C# Part Eleven: A working double-ended queue

BioSensorAB » Immutability in C# Part Eleven: A working double-ended queue

BioSensorAB » Immutability in C# Part Eleven: A working double-ended queue — Wed, 13 Feb 2008 03:24:32 GMT

PingBack from http://www.biosensorab.org/2008/02/12/immutability-in-c-part-eleven-a-working-double-ended-queue/

re: Immutability in C# Part Eleven: A working double-ended queue

Chris Okasaki — Wed, 13 Feb 2008 07:54:56 GMT

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.

re: Immutability in C# Part Eleven: A working double-ended queue

Eric Lippert — Wed, 13 Feb 2008 10:19:51 GMT

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,

Eric

re: Immutability in C# Part Eleven: A working double-ended queue

Erik — Wed, 13 Feb 2008 20:07:04 GMT

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).

re: Immutability in C# Part Eleven: A working double-ended queue

DRBlaise — Wed, 13 Feb 2008 22:56:53 GMT

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!

Immutability in C#

Wed, 13 Feb 2008 23:41:20 GMT

For some reason, there's been a lot of buzz lately around immutability in C#. If you're interested in

re: Immutability in C# Part Eleven: A working double-ended queue

Franck Jeannin — Thu, 14 Feb 2008 13:57:26 GMT

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,

Franck

re: Immutability in C# Part Eleven: A working double-ended queue

Jay Bazuzi — Thu, 14 Feb 2008 20:35:34 GMT

Cool.

So, why Four, and not Three or Five?

re: Immutability in C# Part Eleven: A working double-ended queue

Eric Lippert — Thu, 14 Feb 2008 21:16:00 GMT

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?

Community Convergence XLI

Charlie Calvert's Community Blog — Wed, 12 Mar 2008 00:35:43 GMT

Welcome to the forty-first Community Convergence. The big news this week is that we have moved Future

re: Immutability in C# Part Eleven: A working double-ended queue

Robin D. — Thu, 10 Apr 2008 00:34:09 GMT

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.

re: Immutability in C# Part Eleven: A working double-ended queue

Eric Lippert — Thu, 10 Apr 2008 00:48:35 GMT

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).