Ayende @ Rahien

Ori Folger commented on Concurrency Solutions

Wed, 16 Jan 2008 22:49:33 GMT

"Another issue that you have with concurrency is that you usually have some requirements about in what order you want to deal with operations. You can't really approve an order before it was created, now can you?" If you can undo order approval, maybe you can get started on approving an order before it's created? If you have two processes, say Order Creation and Order Approval, you can start on the Order Approval before Order Creation is really done, by making reasonable assumptions on the missing data. If any of the assumptions turn out wrong you undo the order approval and start over. It's called [speculative execution](http://en.wikipedia.org/wiki/Speculative_execution) and it's at the heart of modern CPUs, which are based around a pipeline design. The trick here is with making reasonable assumptions. It's a game of statistics - if you're very rarely wrong, this is a good way to go. To give an idea of how good you need to be , one of the assumption making components of a CPU is the branch predictor, which is right about 95% of the time. As an example more suitable for high level software, consider the pipeline for an HTTP response. The final response depends on many different processes - user authentication, cache lookup, ad selection, etc. . Instead of just waiting for every bit of these, the pipeline proceeds based on an assumption (i.e. assume the user is an anonymous visitor) and in the rare case the assumption is wrong, the pipeline throws away the work done based on that assumption and starts over. But in the highly common case, the response is generated faster and there is greater resource utilization because there's no need to wait for user authentication to finish before doing any useful work.

Jon Skeet commented on Concurrency Solutions

Wed, 09 Jan 2008 10:06:05 GMT

Indeed - all I was doing was making good on the work stealing references :)

Ayende Rahien commented on Concurrency Solutions

Wed, 09 Jan 2008 09:36:01 GMT

Jon, Note the collaboration technique that I have for the tasks. They can yield and resume without blocking threads. What you are talking about is usually used to maintain the current process cache intact, as well as keeping locks down.

Jon Skeet commented on Concurrency Solutions

Wed, 09 Jan 2008 09:21:46 GMT

It definitely does - I only heard about it in CILK because of PFX :) From http://www.bluebytesoftware.com/blog/2007/11/30/ParallelExtensionsCTPIsAvailable.aspx Not only that, but we’ve expanded the scope of the original project significantly, from PLINQ to Parallel FX, to include new imperative data parallel APIs (for situations where expressing a problem in LINQ is unnatural), powerful task APIs that offer waiting and cancelation, all supported by a common work scheduler based on CILK-style work-stealing techniques developed in collaboration with Microsoft Research. (Side note: Joe Duffy rocks extremely hard. Can't wait for his concurrency book.) --- I'd written the stuff below before your comment came in - included just for extra info: Actually, it looks like that's not terribly helpful as a URL. If you Google for "work stealing" CILK you'll find plenty of hits. I believe the basic idea is that each thread has a queue of work it intends to do - and it can access that work queue very efficiently without locking etc. If it runs out of work, it can steal work from another queue. This is less efficient, but hopefully happens relatively rarely. I don't pretend to understand the details of it, but I think it's meant to be significantly more efficient (particularly for short items?) than a single pool of work which all threads steal from. I suspect it also makes PFX work nicely when the system is heavily loaded with other programs, although that's pretty much a guess! Jon

Ayende Rahien commented on Concurrency Solutions

Wed, 09 Jan 2008 09:14:53 GMT

I was thinking about work stealing for the PFX. This is basically what I am doing in the task scheduling. One interesting thing here is the ability to stop a task in the middle. Clik supports it, and so does the work scheduling, but in my search, PFX doesn't.

Jon Skeet commented on Concurrency Solutions

Wed, 09 Jan 2008 08:24:55 GMT

http://en.wikipedia.org/wiki/Cilk#Work-stealing

Ayende Rahien commented on Concurrency Solutions

Tue, 08 Jan 2008 22:28:46 GMT

Judah, Do you have a reference for "work stealing"? I couldn't find it.

Ayende Rahien commented on Concurrency Solutions

Tue, 08 Jan 2008 22:07:24 GMT

Judah, What the PFX provides is a (much) better thread pool alternative, in terms of the API given. What I am thinking is concurrent tasks, which can pass around control among them without difficulties.

Judah commented on Concurrency Solutions

Tue, 08 Jan 2008 15:54:36 GMT

Oren, you mentioned that PFX is "getting to run things in parallel, that's about it". Last time I looked, PFX had the concepts of tasks and task scheduling, work stealing, some pretty advanced stuff.

Jon Skeet commented on Concurrency Solutions

Tue, 08 Jan 2008 10:33:27 GMT

One thing to note about state: MS is clearly thinking quite hard about immutability and how to deliver it in both languages and libraries. This may well have been accelerated by F#. Just as a few examples: http://www.bluebytesoftware.com/blog/2007/11/11/ImmutableTypesForC.aspx http://www.bluebytesoftware.com/blog/2007/11/17/ImmutableTypesCanCopyTheWorldSafely.aspx http://blogs.msdn.com/lucabol/archive/2007/12/28/creating-an-immutable-value-object-in-c-part-iv-a-class-with-a-special-value.aspx http://blogs.msdn.com/ericlippert/archive/tags/Immutability/default.aspx Of course, now that you've looked at the CCR etc, you should really have a look at... nah, just kidding, I'm done ;) Jon

Darius Damalakas commented on Concurrency Solutions

Tue, 08 Jan 2008 08:14:47 GMT

Nice