All Your Base Are Belong To Us

DevAcademy4 Session: Parallel Programming in .NET 4 and Visual Studio 2010

Sasha Goldshtein — Sat, 20 Mar 2010 07:43:19 GMT

Sorry for the late announcement, but on Monday I’m going to present a session called Parallel Programming in .NET 4 and Visual Studio 2010 at the Microsoft Developer Academy 4 (Avenue, Airport City).

There are six (!) Sela speakers at the conference: Gil Fink, Alex Golesh, Shai Raiten, Alon Fliess, Noam King, and yours truly—and I’m sure they are going to rock, so take a look at the conference schedule to see which sessions you want to attend.

I wouldn’t want to ruin the fun for the ones who are planning to come to my talk, but here are some of the things we’ll see:

Styles of concurrent applications today
The shift from imperative to declarative parallelism
What’s in the box with .NET 4 and Visual Studio 2010 with regards to parallel programming
Data parallelism, processing parallelism, explicit task management
Migration strategy and integration examples

The sessions will be recorded (AFAIK) so even if you’re unable to attend my talk, I’ll let you know how you can tune in after the conference. I will also upload the presentation, the demos, and any other materials after my talk.

As for the demos—let’s just say that it’s popular to integrate Twitter into every demo at every conference talk, so there will be a Twitter client of some sort but it might have a surprising user interface.

/--------------------\
|                    |
|                    |
|                    |
|                    |
|           **.      |
|          ****      |
|          *****     |
|         *******    |
|      ** ********* |
|     ************* |
|    .***********    |
|      **********    |
|        ********    |
| .    ********     |
|   ***********      |
|    .*******        |
|                    |
|                    |
|                    |
|                    |
\--------------------/

Are We Training Our Customers to Be Dumb?

Sasha Goldshtein — Tue, 16 Feb 2010 20:29:28 GMT

During the past few years at Sela, I’ve authored several courses and participated in the development process of several dozens more. They covered a great deal of topics – ranging from the gory inner workings of Windows and the CLR, through new technologies like LINQ and Windows 7, and all the way to introductory courses to C# programming. I’ve also had the experience of designing and developing courses in a variety of styles – the “Sela style”, which focuses on the brilliance of the instructor delivering the course and slightly deemphasizes the minute details in student handbooks, the “standard international courseware style”, which is all about attention to detail and greatly elaborate lab instructions, and some combinations of the two.

I always preferred concise exercises and labs that emphasize the student’s ability to think and process the material, over exercises that involve straightforward typing or copy-pasting code from the lab manual into Visual Studio and seeing it compile. And I always wondered if it was just some mentality thing here in Israel, or a personal preference I have because I like teaching difficult courses to an audience of highly experienced developers. I also wondered if the reason some customers prefer and training companies encourage the drill-down, copy-paste labs was a matter of dumbing down the lab and making sure everyone in the classroom is capable of finishing it within the allotted time; not to mention that a short and concise lab definition might seem vague and lacking in detail to some audiences.

But one thing just occurred to me. Take a look at this exercise from an introductory mathematical analysis course, one of the first things I found by looking up “mathematical analysis homework” on Google:

Let f be a monotone function on an interval. Prove that f is continuous iff its image is an interval.

Can you see what I’m getting at? OK, here’s an example of an exercise I used a few weeks ago when teaching a concurrent programming course:

The reader-writer lock design shown in class uses two mutexes and an event. Convert this design to use only a single semaphore. Prove that there is a possible deadlock if multiple writers attempt to acquire the lock. Fix the problem by introducing a mutex (additionally to the semaphore).

Compare and contrast to this hypothetical example from today’s typical software industry “courseware”:

In this task, you will implement the IComparable interface so that instances of your class can be sorted by external sort algorithms. Open the MyClass.cs file in Visual Studio, and navigate to the MyClass class definition. (To open a file, click File –> Open.)

Declare that your class is implementing the IComparable interface using the interface implementation syntax, as follows:

internal class MyClass : IComparable {

Implement the CompareTo method. To compare the parameter to your object, cast the parameter to an instance of MyClass. Next, compare the values of the X and Y properties of the parameter to the values of the X and Y properties of your instance (this).

[…several pages later…]

Congratulations! In this exercise, you have implemented the IComparable interface so that users of your class can compare instances of it without being aware of your class’ implementation details. For more information about the IComparable interface, consult the MSDN documentation at […]

It’s mind-numbing to read just this passage, not to mention the 30+ pages of standardized jargon it is usually surrounded by. Are we deliberately dumbing down our training materials and by extension the developer community? What’s the ultimate objective of having every step of the way explained in excruciating detail? How is it possible to learn anything without even trying to perform the task on your own before copy-pasting code from the student manual?

I’ve officially given up trying to understand this phenomenon. But I do know this: Given the choice between short and concise instructions and a 30+ page lab document, I would choose the former over the latter even if it were a million times harder.

I feel that a good litmus test for a properly designed lab exercise would be the following relation:

Lines of Text in Lab Manual / Lines of Code Written by Student < 0.1

Another Happy User of Windows Home Server

Sasha Goldshtein — Thu, 04 Feb 2010 16:59:43 GMT

A couple of months ago I bought an Acer Aspire easyStore home server for my home. It comes preinstalled with Windows Home Server. The configuration I bought has a single 1TB hard drive with the OS itself and plenty of room for backups and data; I also ordered another internal WD Caviar Green 1.5TB hard drive and an external 2TB Seagate hard drive.

The internal hard drive was faulty from the start, so I’m in the process of replacing it, but right now I’m working with 3TB of space, which is enough for my backups and most of my data. It’s really easy to add or remove drives, and you can do it without ever shutting down the server by simply opening the front door, removing one of the bays, inserting your hard drive (screw-less design – another bonus!) and you’re good to go.

One of the neatest things about this server is its form factor – it’s really small. I have a small storage cabinet that’s 30cm (1’) wide and about 70cm (2’4”) tall, and it hosts the home server, the cable modem, the router and the external hard drive without missing a beat.

If you know me personally, you probably know that I’m the (grumpy) system administrator for seven computers (two desktops, two media centers and three laptops), and ensuring the integrity of the data, performing timely backups, restoring them after installation problems and so on – can quickly become annoying if it’s not your day job… One of the primary objectives of buying the server was to stop worrying!

So far I’m very happy with my home server. I’m using it for backups – and because I have Windows 7 on all seven machines, there’s plenty of duplication which Windows Home Server detects – that’s why it’s currently using only 424GB of space for backups. I’m using it for shared storage – photos, videos, music and software installations. The one thing I’m not storing on the home server yet is recorded TV, because it usually doesn’t survive more than a couple of days before being deleted, and my media center’s 1.5TB of storage are more than enough to store plenty of recorded programs.

I’m also using the home server to remotely connect to my computers at home. When you buy a Windows Home Server, you’re automatically entitled to a sub-domain (under .homeserver.com, or other alternatives) that you can use to connect to your server. You can browse all the shared folders and remotely connect to any computer at home using Remote Desktop.

I look back at the last few years and realize that I’ve never been very good with backups. I have backups of the most important personal stuff on DVDs, and some of the work stuff is safely backed up by LiveMesh and SkyDrive. However, if one of my PCs at home suffered a major breakdown, it would take me weeks to restore it to a decent state. With Windows Home Server, restoring over a wireless N connection or a wired Gigabit connection is a matter of hours at most.

This definitely isn’t the freshest piece of advice you’ve ever heard, but if you’re not thinking about backups, it’s better to start sooner than later, and Windows Home Server is a good place to start :-)

Race Condition When Modifying the HttpRequestMessageProperty in an Outgoing WCF Message

Sasha Goldshtein — Wed, 03 Feb 2010 15:22:25 GMT

I’ve stumbled upon a fairly obscure race condition in WCF’s implementation of the HTTP transport, and just wanted to quickly share it with you should you ever encounter it.

I was using a simple publish/subscribe router similar to the one I’ve blogged about two years ago to automatically publish notifications to a list of subscribers. The router is a WCF service that implements a generic interface that takes a Message and creates multiple copies of it to send to all registered subscribers.

Here’s my original take on the dispatch code: [exception-handling removed for clarity]

foreach (string subscriber in subscribers)
{
    Message toSend = buffer.CreateMessage();
    IGenericOneWayContract proxy =       
        ChannelFactory<IGenericOneWayContract>.CreateChannel(
            Program.Binding, new EndpointAddress(subscriber));
    proxy.Action(toSend);
    ((ICommunicationObject)proxy).Close();
    toSend.Close();
}

…now, seeing that the messages are copied and the send operation is stateless, there’s no reason why I shouldn’t be able to parallelize these operations and make sure subscribers get the notification messages more promptly:

Parallel.ForEach(
  subscribers,
  subscriber =>
      {
          Message toSend = buffer.CreateMessage();
          IGenericOneWayContract proxy =       
             ChannelFactory<IGenericOneWayContract>.CreateChannel(
                Program.Binding, new EndpointAddress(subscriber));
          proxy.Action(toSend);
          ((ICommunicationObject) proxy).Close();
          toSend.Close();
      });

But unfortunately, the latter version of the code fails with the following exception, that only occurs once in several hundreds of messages on my machine: [removed parameters from stack trace for clarity]

System.NullReferenceException: Object reference not set to an instance of an object.

Server stack trace:
   at System.ServiceModel.Channels.HttpRequestMessageProperty.get_Headers()
   at System.ServiceModel.Channels.HttpOutput.WebRequestHttpOutput.PrepareHttpSend…
   at System.ServiceModel.Channels.HttpOutput.Send…
   at System.ServiceModel.Channels.HttpChannelFactory.HttpRequestChannel.HttpChannelRequest.SendRequest…
   at System.ServiceModel.Channels.RequestChannel.Request…
   at System.ServiceModel.Dispatcher.RequestChannelBinder.Send…
   at System.ServiceModel.Channels.ServiceChannel.Call…
   at System.ServiceModel.Channels.ServiceChannelProxy.InvokeService…
   at System.ServiceModel.Channels.ServiceChannelProxy.Invoke…

Exception rethrown at [0]:
   at System.Runtime.Remoting.Proxies.RealProxy.HandleReturnMessage…
   at System.Runtime.Remoting.Proxies.RealProxy.PrivateInvoke…
   at WCFHttpMessageProperties.IGenericOneWayContract.Action…
   at WCFHttpMessageProperties.PubSubRouter.<>c__DisplayClass1.<Action>b__0…
   at WCFHttpMessageProperties.Parallel.<>c__DisplayClass3`1.<ForEach>b__0…

After looking at the code with Reflector, it seems that during the PrepareHttpSend method that we see in the stack trace, there’s a phase where the message properties (including the HttpRequestMessageProperty) are refreshed, e.g. with HTTP header information. Why, however, should there be a problem with the parallel version of the code if I’m delivering separate copies of the message to my subscribers?

Well, from looking at the implementation of message cloning with Reflector, it appears that message properties are not cloned unless they implement the IMessageProperty interface (see MessageProperties.CreateCopyOfPropertyValue). The HttpRequestMessageProperty class does not implement this interface, and therefore “cloning” it consists of simply returning the original value.

Now the problem should be evident – we have multiple threads that are trying to modify the same HttpRequestMessageProperty instance, with its HTTP header collection and whatnot. There’s a fairly rare race condition because most of the time the operations on the HTTP headers don’t collide, and happen to leave the message property in a consistent state. When they do collide, we get the above exception.

There’s actually another variety of this problem that I’ve seen in the wild, but haven’t been able to reproduce on my machine – it’s when the message is eventually sent, but contains duplicate HTTP headers! This is obviously rather difficult to diagnose because the message is successfully sent with the duplicate headers but the subscriber refuses to receive it! The same fix was sufficient for both of the issues.

So, what’s the fix? In this case, short of writing a manual serialization mechanism for message properties, I didn’t see many options other than a workaround. The workaround I found is to remove the HttpRequestMessageProperty from the message before creating copies – this will cause the transport channel (HttpOutput) to create a new instance of the property and attach this fresh copy to the message.

In other words, the complete and working version of the code is something along the following lines:

message.Properties.Remove(HttpRequestMessageProperty.Name);
MessageBuffer buffer = message.CreateBufferedCopy(int.MaxValue);
string[] subscribers = …;
Parallel.ForEach(
  subscribers,
  subscriber =>
      {
          Message toSend = buffer.CreateMessage();
          IGenericOneWayContract proxy =
             ChannelFactory<IGenericOneWayContract>.CreateChannel(
                Program.Binding, new EndpointAddress(subscriber));
          proxy.Action(toSend);
          ((ICommunicationObject) proxy).Close();
          toSend.Close();
      });
buffer.Close();

I thought it would be interesting to test this behavior with WCF 4.0. On Visual Studio 2010 Beta 2, I was able to reproduce the duplicate HTTP headers problem, with the following exception, although the problem is admittedly rare: [again, edited for clarity; I marked the duplicate header in italic]

System.ServiceModel.ProtocolException: Content Type application/soap+xml; charset=utf-8,application/soap+xml; charset=utf-8 was not supported by service http://localhost:8993/Client_6. The client and service bindings may be mismatched. ---> System.Net.WebException: The remote server returned an error: (415) Cannot process the message because the content type 'application/soap+xml; charset=utf-8,application/soap+xml; charset=utf-8' was not the expected type 'application/soap+xml; charset=utf-8'..
   at System.Net.HttpWebRequest.GetResponse…
   at System.ServiceModel.Channels.HttpChannelFactory.HttpRequestChannel.HttpChannelRequest.WaitForReply…
   --- End of inner exception stack trace ---

Server stack trace:
   at System.ServiceModel.Channels.HttpChannelUtilities.ProcessGetResponseWebException…
   at System.ServiceModel.Channels.HttpChannelFactory.HttpRequestChannel.HttpChannelRequest.WaitForReply…   at System.ServiceModel.Channels.RequestChannel.Request…
   at System.ServiceModel.Dispatcher.RequestChannelBinder.Send…
   at System.ServiceModel.Channels.ServiceChannel.Call…
   at System.ServiceModel.Channels.ServiceChannelProxy.InvokeService…
   at System.ServiceModel.Channels.ServiceChannelProxy.Invoke…

Exception rethrown at [0]:
   at System.Runtime.Remoting.Proxies.RealProxy.HandleReturnMessage…
   at System.Runtime.Remoting.Proxies.RealProxy.PrivateInvoke…
   at WCFHttpMessageProperties.IGenericOneWayContract.Action…
   at WCFHttpMessageProperties.PubSubRouter.<>c__DisplayClass2.<Action>b__1…
   at WCFHttpMessageProperties.Parallel.<>c__DisplayClass4`1.<ForEach>b__1…

Finally, in another test run I encountered a third variety of this exception, that I wasn’t able to see with WCF 3.0. It’s due to an internal implementation change, but the underlying problem is still the same race condition as before: [edited for clarity]

System.ArgumentException: Item has already been added. Key in dictionary: 'Content-Type' Key being added: 'Content-Type'

Server stack trace:
   at System.Collections.Hashtable.Insert…
   at System.Collections.Hashtable.Add…
   at System.Collections.Specialized.NameObjectCollectionBase.BaseAdd…
   at System.Collections.Specialized.NameValueCollection.Add…
   at System.Net.WebHeaderCollection.Add…
   at System.Collections.Specialized.NameValueCollection.Add…
   at System.ServiceModel.Channels.HttpRequestContext.ListenerHttpContext.System.ServiceModel.Channels.HttpRequestMessageProperty.IHttpHeaderProvider.CopyHeaders…
   at System.ServiceModel.Channels.HttpRequestMessageProperty.get_Headers…
   at System.ServiceModel.Channels.HttpOutput.WebRequestHttpOutput.PrepareHttpSend…
   at System.ServiceModel.Channels.HttpOutput.Send…
   at System.ServiceModel.Channels.HttpChannelFactory.HttpRequestChannel.HttpChannelRequest.SendRequest…
   at System.ServiceModel.Channels.RequestChannel.Request…
   at System.ServiceModel.Dispatcher.RequestChannelBinder.Send…
   at System.ServiceModel.Channels.ServiceChannel.Call…
   at System.ServiceModel.Channels.ServiceChannelProxy.InvokeService…
   at System.ServiceModel.Channels.ServiceChannelProxy.Invoke…

Exception rethrown at [0]:
   at System.Runtime.Remoting.Proxies.RealProxy.HandleReturnMessage…
   at System.Runtime.Remoting.Proxies.RealProxy.PrivateInvoke…
   at WCFHttpMessageProperties.IGenericOneWayContract.Action…
   at WCFHttpMessageProperties.PubSubRouter.<>c__DisplayClass2.<Action>b__1…
   at WCFHttpMessageProperties.Parallel.<>c__DisplayClass4`1.<ForEach>b__1…

This last exception even seems to hint that someone at Microsoft introduced an additional sanity check so that messages with duplicate headers do not even leave the HTTP transport, but this sanity check doesn’t work (see the previous exception) and doesn’t fix the root cause of this issue, which is the fact that WCF message properties are not properly cloned when the message is cloned.

Fortunately, the same workaround fixes the problem in WCF 4.0 a well.

IsBadXxxPtr Is Really Harmful – Please Don’t Use These Functions

Sasha Goldshtein — Fri, 15 Jan 2010 17:21:36 GMT

You might have stumbled upon posts like this one that tell you there’s a simple solution for verifying that a memory location is OK for read/write/execution: Just use the “IsBadXxxPtr” family of functions that take a memory address and return a BOOL indicating if you can use the memory.

It turns out (and I’m hardly the first to blog about it) that calling these functions causes more problems than it solves, and causes bugs rather than fixes them. Please heed the collective advice and stay away from these APIs.

Here are some reasons why:

Non-atomicity

If you want to test a page for reading, a standard approach would be to call IsBadReadPtr, get a FALSE result and then try reading from the page, right? Well, what stops some other thread (or even your thread in an APC, for example) from unmapping that page and rendering it invalid for reading just after your checked but before you had a chance to read from it? Guess what, you crash – and this time you crash in a very surprising location. If you try debugging, you’ll see that your app causes a read access violation after testing the address with IsBadReadPtr, and head-scratching is guaranteed.

“Corrupt memory if possible”

IsBadWritePtr is even worse. As Raymond Chen aptly put it, this method should really be called CorruptMemoryIfPossible. What this method does is try to write a single byte to the beginning of every page in the range that you passed to it, and then fix up the old value of that byte if the write succeeded.

Two horrible things come to mind: First, another thread can observe the changed byte before the API had a change to fix it up to the old value. This is clearly very bad. Another horrible thing (which is far less likely though) is that the page becomes read-only after the test byte has been written and before the API had a chance to fix it to the old value. Both of these things are random corruptions that you have no hopes of detecting.

Guard pages

Not many Windows programmers are familiar with guard pages, but they are very important nonetheless. A guard page is a page protected by the PAGE_GUARD page protection flag, which causes a one-shot page guard exception when the page is accessed. After the page is accessed, however, the guard is removed and will not be triggered again unless the page is protected by PAGE_GUARD again.

Guard pages are used by a variety of applications, but they have one very important role: Ensuring that thread stacks are lazily expanded. The way thread stacks work on Windows is that although by default 1MB of stack space is reserved for each thread, the individual pages in that range are committed page-by-page, when the thread attempts to expand the stack by calling a method or allocating stack-based memory. What happens is that the next page that is about to be used for the thread’s stack is a guard page, and there’s an exception handler that catches the page guard exception, properly commits the page and, most importantly, places a guard on the next stack page.

I suppose you can already see the potential for trouble if you touch guard pages using IsBadXxxPtr. The API will swallow the page guard exception like any other, and the exception handler responsible for placing a guard on the next stack page will not run. This means you just created a potential stack overflow where there was previously no reason for one to occur.

There are also other examples of why guard pages can be useful, and in most of these cases the IsBadXxxPtr family of APIs defeats the mechanism behind guard pages in varyingly fatal ways.

Not to mention that bad pointers will crash you anyway

There’s also the more philosophical argument here. If you get a bad pointer (and I’m not talking about a NULL pointer here, which can be easily detected* by other means), what do you think you can do about it? If you have the privilege of returning an error code, do you think the program that gave you an invalid pointer in the first place is going to check the error code?

What you often do by checking for “bad” pointers is turning a fail-fast crash into a subtle bug to be discovered maybe hours later. The worst thing that can happen if you have a memory corruption is that your application continues running. If you check for bad pointers, it’s as if you’re trying to guarantee that your application continues running with a memory corruption.

* By “easily detected” I mean that NULL pointers are not really that hard to identify. Windows guarantees that the first 64KB of memory are a PAGE_NOACCESS region, so there’s absolutely no chance that someone is handing you a valid address that is strictly smaller than 65,536. Corollary: It’s a moot point to try detecting NULL pointers by using IsBadXxxPtr. It’s true that a NULL pointer is not always NULL, e.g. if you’re accidentally obtaining a pointer to a field in a NULL structure pointer or obtaining a pointer to a member using a NULL this pointer. However, in all these cases (unless you have structures bigger than 64KB, which is a whole different problem) you can simply test the address for < 64KB.

Generating Prime Numbers in a Range (Was: LINQ Challenge), Part 4 – More on Sieves

Sasha Goldshtein — Fri, 15 Jan 2010 16:17:57 GMT

As it is often the case with algorithms, there’s a better one yet for the problem at hand. The Sieve of Eratosthenes that we employed in the previous step is significantly faster than naively testing every prime number in the range, but there are additional improvements on this approach.

The Sieve of Atkin is a much smarter algorithm that relies on certain properties of modulo-sixty remainders of prime numbers. The algorithm is based on the following facts (and do feel free to check the Wikipedia entry for more details):

All numbers with a modulo-sixty remainder that is divisible by 2, 3, or 5 are not prime because they are divisible by 2, 3, or 5, respectively. (This leaves only a handful of modulo-sixty remainders to consider.)
All numbers with a modulo-sixty remainder 1, 13, 17, 29, 37, 41, 49, or 53 have a modulo-four remainder of 1 (because these remainders themselves have a modulo-four remainder of 1). These numbers are prime iff the number of solutions to 4x^2 + y^2 = n is odd and the number is not a square of another integer. (The proof to this and the following two claims is here, behind a paywall.)
All numbers with a modulo-sixty remainder 7, 19, 31, or 43 have a modulo-six remainder of 1. These numbers are prime iff the number of solutions to 3x^2 + y^2 = n is odd and the number is not a square of another integer.
All numbers with a modulo-sixty remainder 11, 23, 47, or 59 have a modulo-twelve remainder of 11. These numbers are prime iff the number solutions to 3x^2 - y^2 = n is odd and the number is not a square of another integer.

Hence, a relatively straightforward algorithm can be used to enumerate all solutions to the above quadratic equations in our range {2…N}. Another iteration of refinements will remove all numbers divisible by 2, 3, or 5 – and we have ourselves a sieve, the Sieve of Atkin.

Efficiently implementing the Sieve of Atkin is not trivial – the straightforward algorithm given on the Wikipedia page is in fact slower than the Sieve of Eratosthenes. Daniel J. Bernstein’s primegen is one of the most efficient implementations known, but it’s written in C and comparing its performance with that of a C# Sieve of Eratosthenes is not fair.

Therefore, I embarked on some refinements to the Wikipedia-provided algorithm and obtained the following results: [“Full” refers to the most naive algorithm, “Sqrt” and “SqrtN2” to its optimizations, “Sieve” to the Sieve of Eratosthenes and “Atkin” to the Sieve of Atkin]

N	Full	Sqrt	SqrtN2	Sieve	Atkin
9998	52	2	1	0	0
12998	81	3	1	0	0
16898	139	4	2	0	0
21968	277	7	3	0	0
28559	371	8	4	0	0
37127	603	13	7	1	1
48265	954	17	9	1	1
62745	1554	24	13	2	2
81569	3051	38	21	3	2
106040		55	30	4	3
137852		81	43	5	4
179208		117	62	7	6
232971		173	89	9	7
302862		237	132	12	10
393721		346	182	17	13
511837		482	250	23	17
665388		680	352	31	23
865005		963	506	41	30
1124507		1452	775	74	43
1461859		1943	999	76	52
1900417		2743	1493	133	116
2470542			2008	134	106
3211705				187	124
4175217				349	167
5427782				651	247
7056117				1048	329
9172952				1680	515
11924838				2224	643
15502290					841

In other words, the Sieve of Atkin is a significant improvement over the previous result, especially for very large ranges. A visualization is in place to show just how much better we got with these improvements:

This graph is rather hard to read because the naive algorithm explodes very quickly and looks like a vertical asymptote; there’s also an easily observable difference between the two sieves and the “sqrt”-optimizations.

The same on a log-log scale:

We can learn a few things from this graph. Recall that after plotting a function f(x) in a log-log scale, if we get a straight line with slope M, it means log x = M log y, or equivalently log x = log (y^M), so we get x = y^M. Therefore:

The slopes of the two “sqrt”-optimizations are roughly the same, and therefore there’s no big-O* difference between the two algorithms.
The slope of the naive algorithm is greater than 1, so the naive algorithm is “worse” than O(n).
The slope of the Sieve of Eratosthenes goes up at ~2,000,000 while the slope of the Sieve of Atkin remains constant. Both have a slope < 1 for small ranges, so both are sub-linear.

In the next (and final) post I will summarize some of our findings and point out a couple of other ideas for implementing primality tests in ranges.

* Recall that a function f(n) is big-O of g(n), i.e. f(n) = O(g(n)) if there exists a constant c such that f(n) = c g(n) for all n. (The Wikipedia definition requires this criterion to hold for all n > some constant, but it’s really irrelevant in the big picture.) Therefore, if the slope of two functions f, g is the same on a log-log scale, but their y-intercept is different, then we have: y1 + log f(x) = y2 + log g(x). From this, log f(x) = (y1 – y2) + log g(x) and therefore f(x) = exp (y1 – y2) g(x), but exp (y1 – y2) is a constant and the definition of big-O holds.

Generating Prime Numbers in a Range (Was: LINQ Challenge), Part 3 – Sieve Me One

Sasha Goldshtein — Thu, 14 Jan 2010 10:27:46 GMT

It’s time for the big guns. We’ve already seen simple optimizations to the problem of generating the prime numbers in a range.

A completely different approach, the Sieve of Eratosthenes, is based on a very simple idea. Write down all the numbers in the range {1…N}. Mark 2 as prime. Now strike out every multiple of 2 as composite. Move on to the next number that is not marked as composite yet, and strike out every multiple of it as composite. (The next number, incidentally, is 3; then 5; then 7; and so on.)

After Sqrt[N] steps you have a list of all prime numbers; these are the numbers you did not strike out as composite. An implementation:

static int[] Sieve(IEnumerable<int> range)
{
    int highBound = range.Last();
    bool[] sieve = new bool[highBound];
    int sqrt = (int)Math.Sqrt(highBound);
    for (int i = 2; i <= sqrt; ++i)
    {
        if (sieve[i - 1])//this was already marked as composite
            continue;

        for (int j = 2 * i; j <= sieve.Length; j += i)
            sieve[j - 1] = true;//composite
    }
    sieve[1 - 1] = true;//1 is not prime
    List<int> numbers = new List<int>();
    for (int i = 1; i <= sieve.Length; ++i)
        if (!sieve[i - 1])
            numbers.Add(i);
    return numbers.ToArray();
}

The biggest drawback of using a sieve is its memory utilization. We’re using O(N) bytes of memory to store Boolean variables representing whether the number is prime or composite. [To save initialization costs, I assume that sieve[i] is false if the number is prime; otherwise, we’d have to initialize the sieve to true, which is a costly operation. BTW, it’s possible to use a single bit per integer instead of a whole bool. This is left as an exercise for the reader.]

As for the runtime complexity, well, we’re doing at most Sqrt[N] iterations through the sieve with values {2…Sqrt[N]}. For each value k in this range, we perform (N/k)-1 operations, marking the elements in the sieve as composite. One attempt to arrive to an upper bound is by saying that we have at most Sqrt[N] iterations and each iteration performs at most N/2 operations, hence we have ourselves an O(N^(3/2)) algorithm. However, this upper bound is very far from being tight, and the real upper bound is somewhere between O(N) and O(N(Log[Log[N]])).

Fortunately, the sieve fares very well in comparison to the other alternatives, because the whole purpose of our little exercise is to generate prime numbers in a big range. If we were concerned with primality testing of a small set of numbers, a sieve wouldn’t fit our purposes*; here, however, it scales much better than the iterative alternatives.

Here are some results: [run times in ms, “Full”, “Sqrt” and “SqrtN2” refer to the algorithms presented in the previous posts]

N	Full	Sqrt	SqrtN2	Sieve
9998	52	2	1	0
12998	81	3	1	0
16898	139	4	2	0
21968	277	7	3	0
28559	371	8	4	0
37127	603	13	7	1
48265	954	17	9	1
62745	1554	24	13	2
81569	3051	38	21	3
106040		55	30	4
137852		81	43	5
179208		117	62	7
232971		173	89	9
302862		237	132	12
393721		346	182	17
511837		482	250	23
665388		680	352	31
865005		963	506	41
1124507		1452	775	74
1461859		1943	999	76
1900417		2743	1493	133
2470542			2008	134
3211705				187
4175217				349
5427782				651
7056117				1048
9172952				1680
11924838				2224

Note that the sieve beats the iterative algorithms by a factor of 10 and sometimes more, making it a much more likely option for generating prime numbers in a large range (more than 11,000,000 numbers scanned in just a little more than 2 seconds). In our final installment, we’ll examine the Sieve of Atkin, a final refinement to the idea of generating primes using a sieve.

* The whole idea of a sieve is feasible if you’re testing a very large range of numbers. If the method was called to calculate prime numbers in a range {K…K+100} where K is very large, creating a sieve up to K+100 would be prohibitive. Hence, for the measurements I used 1-based ranges.

Generating Prime Numbers in a Range (Was: LINQ Challenge), Part 2 – Simple Optimizations

Sasha Goldshtein — Tue, 12 Jan 2010 12:27:04 GMT

There are two rather trivial optimizations to the problem of generating prime numbers that we saw in the previous post.

First there’s the observation that it suffices to test all potential divisors in the range {2…Floor[Sqrt[K]]} to ascertain that K is prime. This is not much harder to accomplish and is a significant running time optimization:

static int[] Sqrt(IEnumerable<int> range)
{
    return range.Where(n =>
    {
        if (n == 2) return true;
        int sqrt = (int)Math.Sqrt(n);
        for (int i = 2; i <= sqrt; ++i)
            if (n % i == 0)
                return false;
        return true;
    }).ToArray();
}

The idea is still the same – we iterate over lots of numbers and check if own target is divisible by these numbers. However, this “lots of numbers” is much less than the “lots of numbers” we had earlier.

Specifically, we’re still not using any memory other than a constant amount, but the runtime complexity has improved significantly. This time, for each of the prime numbers in the range K we do at most Sqrt[K] iterations of the inner loop. Assuming as earlier that there are roughly 2Sqrt[N]/Log[N] numbers, the biggest possible number is N, and the amount of work per number is Sqrt[N], we obtain an upper bound of 2N/Log[N] on the amount of work. (This disregards the work needed for the composite numbers; this is an assumption we’ve made before.)

This is a big improvement – the difference between N^2 and N^(3/2)/Log[N] is quite telling, and so is the difference between N^(3/2)/Log[N] and N/Log[N]. Here’s a graph:

Now we can introduce another optimization. It won’t reap us as many fruits as the previous algorithmic improvement, but it’s still worthwhile. Specifically, we note that there’s already a special treatment of the number 2 in our method. Why don’t we automatically discard all even numbers before embarking on the Math.Sqrt call, which is quite expensive?

Furthermore, if we discard all the even numbers in advance, we can start the loop from 3 and advance through only the odd numbers. (Obviously if K is divisible by 2k then K is divisible by 2, hence there’s no need to test even divisors other than 2.)

This brings us to:

static int[] SqrtN2(IEnumerable<int> range)
{
    return range.Where(n =>
    {
        if (n != 2 && n % 2 == 0)
            return false;
        int sqrt = (int)Math.Sqrt(n);
        for (int i = 3; i <= sqrt; i += 2)
            if (n % i == 0)
                return false;
        return true;
    }).ToArray();
}

Not much complicated, but has a potential for running quite faster. For the even numbers, we’re not performing the expensive Math.Sqrt call at all; for prime numbers, we’re going over half as many potential divisors as we did earlier. This is not an improvement if you’re analyzing theoretical runtime complexity, but from a practical standpoint it’s quite an improvement indeed: [times in ms, “Full” stands for the algorithm from the previous post]

N	Full	Sqrt	SqrtN2
9998	52	2	1
12998	81	3	1
16898	139	4	2
21968	277	7	3
28559	371	8	4
37127	603	13	7
48265	954	17	9
62745	1554	24	13
81569	3051	38	21
106040		55	30
137852		81	43
179208		117	62
232971		173	89
302862		237	132
393721		346	182
511837		482	250
665388		680	352
865005		963	506
1124507		1452	775
1461859		1943	999
1900417		2743	1493

Predictably enough, for values of N both small and large, the new version is almost twice as fast as the first one. Still, it takes us 1.5 seconds to generate less than 2,000,000 prime numbers. This scales linearly, but it’s still far from ideal.

The massive breakthrough can be obtained by using the Sieve of Eratosthenes, which is a completely different approach for generating prime numbers in a range. We’ll examine it in the next installment.

Generating Prime Numbers in a Range (Was: LINQ Challenge), Part 1 – Introduction

Sasha Goldshtein — Mon, 11 Jan 2010 21:33:04 GMT

Justin Etheredge posted a nice LINQ challenge – write a LINQ query, using whatever chained lambdas you want, but no custom LINQ methods, to generate the prime numbers in a given range.

Over at his blog, Justin analyzes a couple of possible implementations with real LINQ queries (although the more efficient of them will have fairly complex lambdas in the query). I, on the other hand, would like to focus on the lessons you can learn from this kind of simple exercise, without using LINQ queries for now.

Here are the rules of engagement for this mini-series of posts: We want to implement a method that takes an IEnumerable<int> which is the range of numbers and returns an int[] which is an array of all prime numbers within that range. [It would be unfair to some algorithms if we require that an enumerable is returned, as it would be unfair to return a sieve that specifies which numbers are prime and which aren’t.]

Primality-wise, 1 is not a prime, but it doesn’t matter because no one will pass a range that starts with 1; 2 is a prime, so it 3, and so on.

Without further ado, here’s the most naive thing conceivable:

static int[] Full(IEnumerable<int> range)
{
    return range.Where(n =>
    {
        if (n == 2) return true;
        for (int i = 2; i < n; ++i)
            if (n % i == 0)
                return false;
        return true;
    }).ToArray();
}

This is rather horrible; we iterate over the entire sequence and for each element, check whether it’s prime by going through all possible candidates for a composite divisor and checking them individually. The ToArray() call at the end materializes the query.

Let’s attend to the complexity of this method. It does not use any additional memory (more accurately, it uses only a constant amount of memory that is not a function of the range size), which is a positive characteristic. However, its runtime complexity leaves much to be desired. Here’s a simple upper bound on its runtime, assuming that the range is {1…N} for some N:

For each number k in {1…N}, the algorithm performs k iterations of the loop if the number is prime, and less than k iterations if the number is composite. Therefore, the total number of steps performed by the algorithm is at most N(N+1)/2, or O(N^2). This is not a tight upper bound, because not all numbers in the range are prime (in fact, 50% of the numbers require only one step of the loop; another 33% of the numbers require only two steps; etc.).

Another approach for estimating the runtime complexity is evaluating the number of primes in the range {1…N}, because these are the numbers that are expensive to test. A known result for the number of primes less than X is roughly 2Sqrt[x]/Log[X]. For each of these numbers k we perform roughly k iterations inside the loop; the biggest possible one is N and therefore we perform at most N(2Sqrt[N]/Log[N]) operations, or O(N^(3/2)/Log[N])). This is much better than O(N^2) and is a tighter bound on the runtime complexity of our algorithm. It really grows much slower – here’s a plot of the two functions:

This doesn’t change the fact that it’s really horribly slow. Here are some results for relatively small values of N, times shown in milliseconds: [measured on my machine, of course]

N	Runtime (ms)
9998	52
12998	81
16898	139
21968	277
28559	371
37127	603
48265	954
62745	1554
81569	3051

There are some significant improvements that can be made to this. The most trivial of all is known to any high school student: If you’re checking whether K is prime, you don’t have to test all the factors {2…K} – it’s enough to test all the factors {2…Floor[Sqrt[K]]} and you’re good. We’ll attend to that in the next installment.

Beware of Evil Wizards

Sasha Goldshtein — Sat, 09 Jan 2010 16:18:37 GMT

Ten years ago, Andrew Hunt and David Thomas published the incredible book, “The Pragmatic Programmer: From Journeyman to Master”. It’s not that I like this book because it has taught me so many things; I mainly like this book because of what it has not taught me.

And one thing this book has not taught me is to use Add New Item –> “Some Amazing Technology” Class Template and then just adjust the grid on the control ever so slightly, and bam – there’s your user interface in all its glory.

Here’s what “The Pragmatic Programmer” has to say about it:

[…] Tool makers and infrastructure vendors have come up with a magic bullet, the wizard. Wizards are great. […] But using a wizard designed by a guru does not automatically make Joe developer equally expert. […] Don’t Use Wizard Code You Don’t Fully Understand.

Why is that that we developers should not rely on wizard-generated code, but it’s OK for us to rely on the operating system’s code or on the .NET Framework’s code?

[…] We’d feel the same about wizards if they were simply a set of library calls […] that developers could rely on. But they’re not. Wizards generate code that becomes an integral part of Joe’s application. […] Eventually, it stops being the wizard’s code and starts being Joe’s.

It’s funny how these words never ceased to be true. Despite the ten-year-old warning against Evil Wizards, code generation inside the development environment has become an increasingly popular technique, and not just for spiffy user interface generation. Here are two wizards I use all the time, in Visual Studio:

Adding a WCF service reference generates a whole bunch of proxy code into your project, and not just the bare minimum service contracts and data contracts that you would otherwise write by hand;
Dragging a table across a LINQ to SQL design surface generates a strongly-typed data context, an entity class for each table, relationships between entities, identity constraints and whatnot.

Ten years after “The Pragmatic Programmer”, I’m not saying that you should stop using the Visual Studio wizards to generate code for you. But if you don’t understand the code generated by the wizard even though you’re using and adapting it to your needs, you’re in for some great trouble. (Unfortunately, presenters at conferences and class teachers are often guilty of spreading the trouble.*)

The telling sign is this: If a technology were easy enough so that you didn’t have to thoroughly learn it before applying it, why would there be a wizard for generating code associated with that technology?

* The most unfortunate thing is that sometimes even we, the public speakers who show other people the power of those Evil Wizards, don’t fully understand the code being generated by them. I had the chance to witness, time and again, a presenter showing a bunch of code effected by a simple click of a button, and when something goes wrong the only resort seems to be to regenerate the whole code from scratch. Is this something you would recommend to your fellow developers?

C++ in Visual Studio 2010: Windows Platform Developers User Group

Sasha Goldshtein — Thu, 07 Jan 2010 08:33:03 GMT

Almost two years ago, I wrote about the TR1, a set of additions to the C++ standard that was implemented in a Feature Pack for Visual Studio 2008. Back then, I gave the post a rather provocative title: C++ Developers Just Got Lambdas?

Well, now we’ve got them. The new C++ standard, dubbed C++0x (where the x is going to be a hexadecimal digit, hopefully A) has lambda functions as one of its features. Visual Studio 2010 implements some of the standard (draft), including lambda functions.

Yesterday I had the pleasure of presenting C++0x to a group of Windows C++ developers, at the Windows Platform Developers User Group organized by Alon Fliess and Pavel Yosifovich. I tried my best to touch all aspects of C++0x, including auto variables, the new “for each” statement, lambda functions, static assertions, the “decltype” operator and a brief mention of rvalue references. [I plan to describe at least some of these features in greater detail in the future.]

Here’s a teaser from the session’s code:

template <typename Iterator, typename Combiner>
auto aggregate(
    Iterator begin,
    Iterator end,
    Combiner comb,
    decltype(comb(*begin,*begin)) initial)
        -> decltype(comb(*begin,*begin))
{
    decltype(comb(*begin,*begin)) result = initial;
    for (; begin != end; ++begin)
    {
        result = comb(result,*begin);
    }
    return result;
}

auto add_f = [](int a,int b) { return a+b; };
list<int> numbers = …;
auto something = aggregate(numbers.begin(),numbers.end(),add_f,0);

Confused? Regardless of whether you attended the session, feel free to download the slides and code. The code is very detailed and shows off some really neat things you can do in C++0x, especially with applications of lambda functions. The language becomes much richer, and naturally much more complicated, but I believe that in the course of the next few years we’re all going to ask ourselves how we managed to write any C++ at all without the features of the new standard.

By the way, if you have ideas for future meetings of the Windows Platform UG, or if you would like to deliver a presentation at the UG, I’m sure Alon and Pavel will be more than happy to hear about it. (You can also contact me if you want to, and I will forward your suggestion to them.)

SDP 2009: .NET Debugging Tutorial

Sasha Goldshtein — Sat, 02 Jan 2010 16:09:19 GMT

A few days I delivered a full-day session titled “Debugging .NET Applications” at the Sela Developer Practice. The session was packed and I was really happy to see lots of people interested in .NET debugging – this seems to be an area of incessant popularity.

I only had one day to deliver lots of material – I basically tried to cram the entire .NET Debugging course I teach at Sela into a single day. We started with debugging basics such as dump files and symbols – and considering the dozens of ways to capture a dump these days, even seasoned programmers are in need of a refreshment. Next, we talked about Visual Studio debugging, including Managed Debugging Assistants which are a great but often overlooked feature. Most of the day, however, was dedicated to the WinDbg + SOS duo, which I used to diagnose a couple of memory leaks, a deadlock, a crash, and other scenarios. At the very end I also had a little time to mention other tools, such as Process Explorer, Process Monitor, Application Compatibility Toolkit, Hawkeye, SOSEX, my own Wait Chain Traversal helper and others.

I thoroughly enjoyed the session, as always. If you attended the session (and even if you didn’t), you can download the code samples here. (Unfortunately, the presentations won’t be available online.)

[To view the conference recordings, some of which are already available, with three sessions freely accessible to everyone, including the 3-hour MVPs panel on life, the universe and everything, start here.]

SDP 2009: Parallel Programming with .NET 4.0 and Visual Studio 2010

Sasha Goldshtein — Sat, 02 Jan 2010 15:53:51 GMT

A few days ago, at the Sela Developer Practice, Eran and I delivered a session titled “Parallel Programming with .NET 4.0 and Visual Studio 2010”. In this session we wanted to highlight the new features for parallel programming in .NET 4.0 – the Task Parallel Library and PLINQ – as well as the new Visual Studio 2010 features in the debugging and profiling areas.

We started with what we call explicit parallelism – manually creating tasks and specifying what to do when they execute and when they complete. We used tasks to show some neat design patterns such as a pipeline of tasks and a tree of tasks. Then, we moved to implicit parallelism – using the facilities of the runtime to concurrently schedule a for loop and a foreach loop. At the end of the session we showed the new debugger windows and the new concurrency profiling mode.

The demos and slides that we used can be downloaded from here. If you’re looking for more comprehensive samples, don’t miss the recently updated Microsoft samples for Parallel Programming.

There will be video recordings of the conference available to attendees at the conference website, so don’t forget to check back.

SDP 2009: Building Workflow Services with WF 4.0 and WCF 4.0

Sasha Goldshtein — Sat, 02 Jan 2010 15:44:14 GMT

Eran and I delivered a session titled “Building Workflow Services with WF 4.0 and WCF 4.0” at the Sela Developer Practice on Tuesday. This session was all about integrating the new features of WF 4.0 and WCF 4.0 to create a workflow application that orchestrates the execution of multiple WCF services.

During the session, we showed how to use WCF 4.0’s ad-hoc discovery, how to write declarative workflows and use custom activities, how to take advantage of the built-in messaging activities in WF 4.0 and how to integrate a workflow application into Windows Server AppFabric. It shows off basic and advanced features of WF 4.0 including bookmarking support, variables and arguments, persistence participants, tracking participants and more.

The demos and slides that we used are available here – feel free to use our sample application to learn more about WF 4.0, WCF 4.0 and workflow services.

Video recordings of the sessions will be available to attendees soon at the conference website. Stay tuned.

Fairness is Highly Overrated

Sasha Goldshtein — Thu, 31 Dec 2009 08:22:21 GMT

Fairness with respect to synchronization mechanisms is a highly overrated property. When I talk about concurrency, parallelism, Windows synchronization and similar subjects, I’m often asked whether the specific algorithm, mechanism or feature is fair in some respect.

First, let’s define fairness. I’ll use a simplistic yet rigorous definition to define a fair lock. (Other synchronization mechanisms may have fairness defined in a similar fashion.) To begin with, a lock is exactly what you think it is – a mechanism for specifying mutual exclusion. Given N threads that attempt to acquire the lock concurrently, only one thread may enter the lock at a given time. When that thread releases the lock, one other thread may enter the lock; and so on. We can assume for the sake of the definition that the work protected by the lock is bounded; i.e. no thread acquires the lock with the intention of retaining it indefinitely.

A lock is fair if, given N threads that attempt to acquire the lock, there is an upper bound on the amount of time any one of the N threads will wait before entering the lock.

An alternative definition considers the number of times a thread is skipped before it is allowed to enter the lock, and discards the need to put a bound on the duration of work protected by the lock:

A lock is fair, if given N threads that attempt to acquire the lock, there is an upper bound on the number of times any one of the N threads will be skipped before entering the lock.

This sounds like a fairly trivial property, and one of the most trivial ways to implement this kind of fairness is using a queue (FIFO) to maintain the information about waiting threads. If waiting threads are enqueued into a FIFO, and the work protected by the lock is bounded, then the amount of time any individual thread will wait is also bounded, and the bound is linear in the number of threads that arrived before that thread.

However, FIFO fairness is not always easy to attain. To begin with, some synchronization mechanisms don’t use queues of waiting threads because they are too expensive. For example, a spinlock, which is a purely user-mode synchronization mechanism requiring no system calls, does not use FIFOs of waiting threads at all, and hence is not fair. Extensions of spinlocks, such as queued spinlocks (MCS spinlocks) may provide fairness that is not necessarily linear. Peterson’s algorithm for mutual exclusion provides a quadratic upper bound on fairness, implying that a thread may be skipped O(N^2) times when N threads are completing for the lock.

Even when FIFOs are used, a thread may be forced to leave the queue and be inserted at the back of the queue later on (on Windows, this can happen when an APC is executed on that thread). If this can happen an unbounded number of times, fairness cannot be guaranteed at all – and indeed, no synchronization mechanism on Windows is free from the risk of being interrupted by an APC. If the thread enters an alertable wait state, it can be preempted by a user mode APC; but even if it doesn’t cooperate, kernel mode APCs can still interrupt the thread and effect a reordering of the waiting queues.

The most amazing thing of all about fairness is that it is not always a desired property even if it can be guaranteed with relative ease. Lock convoys are an excellent demonstration of how fairness can be devastating for a group of threads competing for the same synchronization mechanism. In a lock convoy (which I discussed in detail earlier), a group of threads acquires and releases a lock many times in a single quantum; however, when one of the threads is preempted while holding the lock, havoc ensues because any subsequent thread acquires the lock only once and is preempted as soon as it tries to acquire the lock again. This is a direct consequence of fairness, and demonstrates that fairness is not always desirable.

When designing a synchronization mechanism or working with existing synchronization mechanisms, bear in mind that often the progress of a group of threads (measured as throughput, CPU utilization or other metrics) can be shown to be higher if unfair synchronization mechanisms are used. A single thread can “take one for the team” to maintain consistent global progress.