Developer Division Performance Engineering blog

Help Make Visual Studio Faster

David Berg — Fri, 06 May 2011 06:45:55 GMT

One of the most difficult things about our job is trying to decipher why Visual Studio is slow for a customer. Often it starts with a vague complaint (e.g. "Visual Studio is sluggish") which we then have to narrow down to a particular action that's slow, and try and get a profile. Then we have to look through a large profile and figure out which code is running slower than it should be and why. Sometimes the problem is CPU intensive, sometimes it's disk or network, sometimes it's a different program altogether that just happens to be slow. I know the process is just as frustrating for customers, who have to try and figure out just where it is slow and get us a profile. And of course, if VS is just a little bit slow, then it's often much easier to live with it than go through the hassle of trying to help us isolate it.

That's why I'm pleased to announce that we now have a better approach. Visual Studio Perf Watson is now available for download and use with VS2010 SP1. If you download and install Perf Watson it does everything for you (and us). Here's how it works:

Perf Watson monitors VS to make sure it is responsive.
If VS goes unresponsive for more than 2 seconds, Perf Watson grabs a stack frame.
Perf Watson then times how long it takes for VS to become responsive again.
Perf Watson then takes the stack information along with the total time of the hang and sends it to Microsoft.
We take the data and load it into a database.
We analyze the data to see which call stacks are causing the longest hangs that impact the most customers, and then we log bugs on those.
Since we have call stacks, the bugs tend to be very actionable.
Since the data comes from real customers, with hit counts and severity information, we have no trouble prioritizing these performance hangs appropriately - we know exactly what they're costing you.

We've been using Perf Watson internally for a while now, and we've been able to identify and fix a lot of problems just based on our internal product usage. We've also seen some nice correlation between issues raised by Perf Watson and issues found through other analysis. This correlation helps us know that we're on the right track and gives extra weight to getting these issues resolved.

But our usage patterns aren't the same as yours. Everyone uses VS a little bit differently. That's why we're excited to put Perf Watson in your hands so that we can get an accurate picture of the performance issues you're running into, with strong metrics and data to back up the work we need to do.

I hope you'll decide to download and install Perf Watson.

Regards,

David Berg
DDPE

Performance Troubleshooting Article and VS2010 SP1 Change

David Berg — Wed, 02 Mar 2011 00:48:00 GMT

Jason Zander just posted an article on Performance Troubleshooting Article and VS2010 SP1 Change, where he talks about some changes we made in SP1 and links to an article on Visual Studio (Performance) Troubleshooting. Check it out and let us know if it helps, and what other type of information would be useful.

Visual Studio 2010 Survey

David Berg — Sun, 10 Oct 2010 14:18:38 GMT

We'd like to know what you think about Visual Studio 2010.

We are especially interested in hearing about your experience with regards to performance, reliability, and quality. The more details you share with us in this survey, the better we can understand your experience and apply what we learn into future versions.

The survey is very short and should take you no more than a few minutes. You can get started by clicking on Visual Studio 2010 Survey.

It's important that we here from you whether you love us or hate us. The more people who respond, the better we can understand how we're doing and whether or not we're doing the right things to make a difference.

Regards and thanks for your time,

David Berg
Developer Division Performance Engineering Team

VS2010 Performance and Bad Video Drivers/Hardware - Redux

David Berg — Fri, 17 Sep 2010 06:19:00 GMT

Since we shipped Visual Studio 2010 we've continued to have a small but notable series of complaints about performance that we've been able to attribute to bugs in video drivers and GPUs.

The issue first came up back during VS 2010 beta in October of 2009. Since then we've learned that while old, buggy drivers are the usual cause, some newer drivers and GPUs aren't as good at supporting VS's UI as we'd like. (This is also an issue with VMs and VM hosts as Video Virtualization technology isn't very good and requires CPU level TLB virtualization support for decent performance, which most CPUs don't have.)

Fortunately, the software rendering inside WPF is pretty good, so the easy fix here is to force WPF to ignore the GPU and use software rendering (I've tested this on my own system, and I found that WPF's software rendering was actually slightly faster than GPU based rendering on my high end CPU with a mid-range graphics card - your mileage may vary).

But first, if you're seeing slow / broken screen updates you should verify you have the latest display drivers for your system. (See "Guidelines for troubleshooting graphics issues in WPF applications" for more information.)

If that doesn't fix it, then there are three ways to force WPF to use software rendering.

First and preferred, the final RTM version of VS2010 includes a UI for forcing hardware rendering off - for just VS. With VS2010 open, go to Tools | Options, then select Environment | General (as shown below). Then uncheck "Automatically adjust visual experience..." and "Use hardware graphics acceleration..."

That should be sufficient.

However, if you want to force software rendering mode for ALL WPF applications (not just VS), you have a second option. Change (or add) one registry key:

[HKEY_CURRENT_USER\Software\Microsoft\Avalon.Graphics]

"DisableHWAcceleration"=dword:00000001

Note that this key probably won't exist, and you'll probably need to create it. To turn hardware acceleration back on, just change the "1" to a "0".

A third alternative is to adjust the hardware acceleration options from the display control panel. However, we don't recommend this option as it impacts the entire machine, the details vary by manufacturer, and the exact impact of all the different options is untested.

If you try any of these - let us know how it works for you (DevPerf@Microsoft.com). If it does improve performance, be sure to let us know how much and attach a DXDIAG output so we'll know which video driver / hardware configurations aren't working well.

Regards,

David Berg

Developer Division Performance Engineering Team

Visual Studio 2010 runs faster when the Windows Automation API 3.0 is installed

David Berg — Mon, 16 Aug 2010 13:08:34 GMT

If you're running Visual Studio 2010 on XP or Vista you may benefit from installing this upgrade: http://support.microsoft.com/kb/981741

Applications that use Windows Automation APIs can significantly decrease Microsoft Visual Studio IntelliSense performance if Windows Automation API 3.0 is not installed. For example, the Windows pen and touch services can significantly decrease Visual Studio IntelliSense performance if Windows Automation API 3.0 is not installed. This article describes how to install the Windows Automation API 3.0 update. This update is available as a stand-alone download for 32-bit editions of Windows XP and for Windows Server 2003. This update is not available for 64-bit editions of Windows XP. The Windows Automation API is a component of the platform update for Windows Vista and of the platform update for Windows Server 2008.

Note that if you're running Windows XP SP2 you'll be told the patch isn't applicable, that's because you need to upgrade to XP SP3 first. If you're running Vista or Windows Server 2008 you may already have the upgrade, since it's part of the automatic updates. If not you can download the upgrade at the link above. Windows 7 and Windows Server 2008 R2 ships with with Windows Automation API 3.0, so no upgrade is required.

The problem is that earlier versions of the Windows Automation API try to read the entire contents of list boxes that we post to the screen, which blocks us from virualizing them. This is particularly a problem with intellisense as the number of items in an intellisense list is HUGE and it pops up on every character you type.

The API is typically activated when using accessibility devices (such as screen readers), pen / tablet computers, or touch devices, but some software activates it anyway (including iPhone synchronization). Once activated it affects the entire system.

Are you a candidate to run Visual Studio 2010 on a 64-bit OS?

David Berg — Thu, 29 Apr 2010 07:56:00 GMT

Brian Harry's just posted an article on configuring an ideal Visual Studio development machine. You can read about it here: http://blogs.msdn.com/bharry/archive/2010/04/29/your-visual-studio-2010-dream-machine.aspx. By the way, if you scroll down and peruse the comments that customers have posted there, you will see recommendations for several other configuration options. Some of these go well beyond the simpler & less expensive ones Brian discussed. If you rely on Visual Studio in your daily work, you may want to give serious consideration to some of these advanced configuration options.

One of topics Brian addresses in his blog was the benefit of running Visual Studio on a 64-bit OS. We’d like to drill into that topic a little deeper in this post.

Visual Studio’s devenv.exe process still runs as a 32-bit process. Under a 32-bit OS, a 32-bit process can only address up to 2 GB of private virtual memory. (For the sake of simplicity, we are going to ignore the /3 GB boot option for 32-bit Windows machines.) The remaining 2 GB of the 4 GB virtual address space is reserved for system addresses. This 2 GB max is an architectural limit on the size of a 32-bit process. All the code and data that gets loaded has to fit in this 2 GB virtual memory space. This may seem a little strange, but as developers working on Visual Studio, but we consider your code – and forms, XAML, DBML, DGML, PDBs for debugging, TFS Work items, and whatever else your Solution loads – as the data Visual Studio has to load & process. The problem arises when Visual Studio needs to load some combination of our code and your data that exceeds this 2 GB architectural limit.

Actually, memory fragmentation issues prevent a 32-bit process like devenv.exe from ever reaching its 2 GB architectural limit. Due to fragmentation, when a 32-bit process address space starts to grow into the 1.7 – 1.8 GB range, the risk that a virtual memory allocation request will fail starts to increase sharply. When a virtual memory allocation request fails, Visual Studio encounters an End of Memory error and crashes.

Obviously, this is a scenario you want to avoid. The cleanest way to get around the problem is to run Visual Studio on a 64-bit OS. On a 64-bit version of Windows, the private area of a 32-bit process expands to encompass the full 4 GB virtual memory addressing range. Due to fragmentation, you can’t quite get to the 4 GB upper limit either, but the effect of the change is to allow devenv.exe to address twice as much private virtual memory. Please don’t take this as a challenge, but we have yet to see a customer scenario that exhausts the full 4 GB address range.

So, if you think you could be a good candidate for running Visual Studio 2010 under a 64-bit OS, here is what to look for. We will run through a scenario we ran recently on the final RTM version of Visual Studio 2010 Ultimate. The test project is a smallish Web solution with a handful of simple ASP.NET Pages that use LINQ to query the MS SQL Server AdventureWorks demo database. This is a version of an app one of us built last year originally for stress testing some Visual Studio components he was working on. We would characterize this app as “borderline realistic.” For example, the AdventureWorks database has fifty or so inter-related Tables, and its SaleOrderDetail Table contains in excess of 120,000 rows. So it is not a trivial “Hello World” type of app, but the web forms themselves are pretty basic, lacking many of the UI components that you are likely to put into a real-world e-commerce application.

Table 1 shows the main steps in my test scenario and the amount of virtual memory Visual Studio consumed at the end of end of each step. The tool we recommend for measuring virtual memory usage at the process level is VMMap, one of the free Sysinternals utilities. With VMMap, I can see the overall virtual memory usage of the devenv.exe process, broken down according to different types of allocations, which is something we will drill into in a moment.

Here is a summary of the steps of the scenario we ran and the amount of virtual memory allocated by the devenv.exe process at the end of each step.

Step	Scenario	VM Usage
1	Open VS with empty solution	300
2	Open VS with web solution: · Solution Explorer, Team Explorer, and Server Explorer · Connect to TFS · Open one .cs file Opened in the VS Editor · Open one simple web form opened in Split mode · Open one (.dbml) Data Designer · Open one TFS Work Item open	910
3	Step 2, plus F5 to Debug Solution, and run to a breakpoint · Intellitrace is active at its low (default) setting	975
4	Step 3, run to Breakpoint; plus step 10x and then run to 2^nd Breakpoint	1060
5	Step 4, with Resharper installed	> 1300

Table 1. Virtual memory usage of Visual Studio at the end of each scenario step.

In Step 5, we repeated the full scenario, but this time with Resharper, a popular Visual Studio add-in, installed. As Figure 1 shows, at that point, the virtual memory footprint of Visual Studio 2010 exceeds 1.3 GB. Committed bytes exceeds 1.2 GB. While that is not a particularly dangerous amount of virtual memory for Visual Studio to consume, it is still enough to start to make you wary.

Figure 1. VMMAP report on Visual Studio’s virtual memory usage for Step 5 in the scenario. (Click for full size image.)

From the standpoint of Visual Studio responsiveness, it is worth noting that the high water mark for the devenv.exe working set was just under 600 MB in Step 5. So this is a scenario that can still readily fit in a machine with the minimum of 1 GB of RAM, and should perform quite well on a machine with 2 GB of RAM.

Drilling into the virtual memory footprint using the VMMap report shown in Figure 1, we see that the largest single contributor is Images files, code that Visual Studio is loading. For the scenario in step 5, Visual Studio needs to load 775 MB of executable code. we zoomed the VMMap detail report into the Image data and then sorted by Image file size. You can see that many of the image files that Visual Studio loads are quite large, in excess of 10 MB. Meanwhile, private data areas accounted for only about 220 MB of virtual.

One thing about the Image files that get loaded in Visual Studio, the more components of the IDE you use, the more code gets loaded. And once loaded, Visual Studio does not have a mechanism to unload components that you are no longer using. The Image File footprint just keeps on growing throughout your Visual Studio session.

So, take this simple scenario and apply it to a very large project or solution and exercise a few more Visual Studio components like architectural diagrams and performance profiling, and you may quickly be up against the architectural limit of a 2 GB private process virtual address space. As Visual Studio virtual memory usage approaches that limit, the product becomes unstable on a 32-bit OS.

As Brian’s blog discusses, to avoid possible instability problems, the workaround is to install and run Visual Studio on a 64-bit version of the OS. Hopefully, this discussion will help you understand better whether you are a good candidate to run Visual Studio on a 64-bit version of the OS. Running VMMap to gain a more detailed look at Visual Studio’s virtual memory usage in your specific environment can also be useful.

-- David Berg and Mark Friedman

posted May 3, 2010

Measuring Processor Utilization and Queuing Delays in Windows applications

Mark B Friedman — Sun, 04 Apr 2010 18:20:00 GMT

Continuing my answer to the mail I received recently from Uriel Carrasquilla…

Uri’s note, reprinted in the previous post, refers to an "issue" associated with the current technique for measuring processor utilization in Windows. As my reply mentioned, these are documented and well-understood issues. At the core is the methodology used to calculate processor utilization that was originally designed 20 years ago for Windows NT. Since one of the original goals of Windows NT was to be hardware independent, the measurement methodology was also designed so that it was not dependent on any specific set of hardware measurement features. And therein lies a tale.

This methodology was amply documented in my Windows 2003 Server Performance Guide, published in the Windows 2003 Server Resource Kit. As you know, I wrote that book before I came to work at Microsoft as a full-time employee, but the Windows Server performance team that helped me at the time was quite open to documenting the existing facility, warts and all.

Briefly summarizing what I wrote there (and which still applies today), the % Processor Time counters in Windows are measurements derived using a sampling technique. The OS Scheduler samples the state of the CPU once per system clock tick, driven by a high priority timer-based interrupt. Currently, the clock tick interval the OS Scheduler uses is usually 15.6 ms. (The precise value that the OS uses between timer interrupts is available by calling the GetSystemTimeAdjustment() function.) If the processor is running the Idle loop when the quantum interrupt occurs, it is recorded as an Idle Time sample. If the processor is running some application thread, that is recorded as a busy sample. Busy samples are accumulated continuously at both the thread and process level. When a clock interrupt occurs, the Scheduler performs a number of other tasks, including adjusting the dispatching priority of threads that are currently executing, stopping the progress of any thread that has exceeded its time slice, as well as performing its CPU accounting.

The System\Processor Queue Length counter in Perfmon is an instantaneous counter that reflects the current number of Ready threads waiting in the OS Scheduler queue. When a performance monitoring application such as Perfmon requests the Processor Queue counter, there is a measurement function that traverses the Scheduler Ready Queue and counts the number of threads waiting for an available processor. Thus, the System\Processor Queue Length counter represents one sampled observation, and needs to be interpreted with that in mind. (If memory serves, the data collection process that Charles’ analysis relies upon gathers samples of this measurement several times per minute, & his servers are not idle by design. Which basically means I think what he is doing is just fine.)

What I believe Uri is referring to with regard to this processor Queue Length metric not being “correct” is anomalies in this measurement that are due to the kind of phased behavior you can sometimes see on an otherwise idle system. Even on an mostly idle system, a sizable number of threads can be waiting on the same clock interrupt (typically, polling the system state once per second), one of which also happens to be the Perfmon measurement thread, also cycling once per second. These sleeping threads tend to clump together so that they get woken up at the exact same time by the timer interrupt. (As I mentioned, this happens mainly when the machine is idling with little or no real work to do.) These awakened threads then flood the OS dispatching queue at exactly the same time. If one of these threads is the Perfmon measurement thread that gathers the Processor Queue Length measurement, you can see how this “clumping” behavior could distort the measurements. The Perfmon measurement thread executes at an elevated priority level of 15, so it is scheduled for execution ahead of any other User mode threads that were also awakened by the same Scheduler clock tick. The effect is that at the precise time when the Processor ready queue length is measured, there are likely to be a fair number of Ready Threads. Compared to the modeling assumption where processor scheduling is subject to random arrivals, one observes a disproportionate number of Ready Threads waiting for service, even (or especially) when the processor itself is not very busy overall.

This anomaly is best characterized as a low-utilization effect that perturbs the measurement when the machine is loafing. It generally ceases to be an issue when processor utilization climbs or there are more available processors on the machine. But this bunching of timer-based interrupts remains a serious concern, for instance, whenever Windows is running as a guest virtual machine under VMware or Hyper-V. (Please don’t get me started on that topic.) Another interesting side discussion is how this clumping of timer-based interrupts interacts with power management, but I do not intend to go there either.

To summarize, the CPU utilization measurements at the system, process and thread level in Windows are based on a sampling methodology. Similarly, the processor queue length is also sampled. Like any sampling approach, the data gathered is subject to typical sampling errors, including

· accumulating a sufficient number of sample observations to be able to make a reliable statistical inference about the underlying population, and

· ensuring that there aren’t systemic sources of sampling error that causes sub-classes of the underlying population to be under or over-sampled markedly

So, these CPU measurements face familiar issues with sampling size and the potential for systematic sampling bias, as well as the usual difficulty in ensuring that the sample data is representative of the underlying population (something known as non-sampling error). For example, the interpretation of the CPU utilization data that Perfmon gathers at the process and thread level is subject to limitations based on a small sample size for collection intervals less than, for example, 15 seconds. The Performance Guide has a more detailed discussion of these issues, if you are interested.

Event-driven measurement approaches.

What exactly Windows is going to do about this, I couldn't say -- I work in a different part of the company -- but I have consistently lobbied for a more accurate, event-driven approach to gathering CPU measurements. Efficient power management, for example, strongly argues for an event-driven approach. You do not want the OS to wake up periodically on an idle machine that could otherwise be powered down just to perform its CPU usage accounting duties, for example.

It is encouraging that recent versions of Windows have taken major steps in this direction, supporting a more accurate event-driven approach using instrumentation added to the Scheduler to measure CPU utilization. The improvements in this area have not gotten much notice, which is something I will try to rectify a bit here. Windows exploits a machine timing facility that is present in both x86 and x64 hardware, namely, the rdtsc Read TimeStamp Counter instruction. Moreover, these improvements position the Windows OS so it can replace its legacy CPU measurement facility with something more reliable and accurate sometime in the near future. Unfortunately, converting all existing features in Windows, including Perfmon and Task Manager, to support the new measurements is a big job, not without its complications and not always as straightforward as one would hope. (One of the complications is using rdtsc on older hardware where the hardware tick rate changes when there is a power management event. There are also issues of clock drift across multiprocessor cores when they are not re-synchronized periodically. I do not want to take the time to discuss these issues in detail here.)

To see this new processor measurement facility at work, access the new Resource Monitor application (resmon.exe) that is available beginning in Vista and Windows Server 2008. Resource Monitor can be launched directly from the command line, or from either Performance Monitor or Task Manager. In case you are not familiar with it, here is a screen shot that shows Resource Monitor in action on a Windows Server 2008 R2 machine, calculating CPU utilization over the last 60 seconds of operation, breaking out that utilization by process. The CPU utilization measurements that ResMon calculates are based on new OS Scheduler instrumentation. These measurements are very accurate, about as good as it gets from a vantage point inside the OS.

Figure 1. The Windows 7 Resource Manager application. (Click for full size image.)

The Resource Monitor measures CPU busy in real time using event-orient measurement data gathered by the OS Scheduler each time a context switch occurs. A context switch occurs in Windows whenever the processor switches the processor execution context to run a different thread. Context switches also occur as a result of high priority Interrupt Service Routines (ISRs), as well as the Deferred Procedure Calls (DPCs) that ISRs schedule to complete the interrupt processing. Starting in Windows 6, the OS Scheduler began issuing rdtsc instructions to get the internal processor clock each time a context switch occurs. (Note: The Windows OS Scheduler not only orders ready threads in its dispatcher queue by priority, it also lets a higher priority thread preemptively interrupt the execution of a lower priority one. This is known as Preemptive Scheduling with Priority Queuing. Once executing, a thread is also subject to a maximum time-slice interval, sometimes referred to as the quantum. When the Scheduler determines that a thread’s time-slice has expired, the thread is also subject to preemption in favor of another thread from the ready queue of equal priority.) Meanwhile, the hardware manufacturers have improved the performance of the rdtsc instruction, making it considerably more efficient for the Scheduler to gather these processor utilization measurements.

You will notice in the example screen shot shown here in Figure 1 that Resource Manager has calculated that System Interrupts (from ISR and DPC routines) accounts for most of the processor utilization during the last 60 second interval. The machine being monitored is mainly doing file I/O, so this is expected. Although the Resource Monitor display doesn’t say so explicitly, it is worth noting that this is all work being performed in kernel mode.

Conceptually, a context switch event is something like switch(oldThreadId, newThreadId), with an rdtsc time stamp identifying when the context switch occurred. The Context Switch event also provides the old thread’s Wait Reason code, which helps you to understand why the sequence of thread scheduling events occurred. For reference, a Windows context switch is defined here, while the contents of the ETW (Event Tracing for Windows) context switch event record are defined here. Also, see the series of articles by Insung Park and Alex Bendetov that were published in MSDN Magazine entitled “Core OS Events in Windows 7” for additional background and perspective.

(Note: You have to hunt a bit to find the current values of the KWait_Reason enumeration. Officially, the KWait_Reason enumeration is published in the Wdm.h header file available in the Windows Driver Kit (WDK). Unfortunately, in MSDN, ordinarily the most authoritative places to find something like this, the available documentation tends to lag recent releases of Windows. For instance, the version of the enum provided to the .NET developer available here is considerably out of date. The explain text in Perfmon for the Thread\Thread Wait Reason counter is also not current. If you do not have access to the WDK, try either ProcessHacker or NirSoft instead for more up-to-date documentation.)

The same calculation that the Resource Manager in Windows 7 uses can be performed after the fact using event data from ETW. In their article, Insung and Alex write, “In state machine construction, combining Context Switch, DPC and ISR events enables a very accurate accounting of CPU utilization.” This is the technique used in the Windows Performance Toolkit (WPT, which is also known as xperf), for example, to calculate its CPU utilization statistics. (For reference, there is a discussion that illustrates using the WPT to analyze ISR and DPC event data in a previous blog entry entitled “Mainstream NUMA and the TCP/IP stack” posted here.)

The new Concurrency Visualizer, which my colleague Hazim Shafi discusses in a recent MSDN Magazine article entitled “Performance Tuning with the Concurrency Visualizer in Visual Studio 2010 in the Visual Studio 2010 Profiler”, also consumes Context Switch events to calculate processor utilization for the application being profiled. An interesting twist in the Concurrency Visualizer’s CPU Utilization View is that the view pivots based on the application you are profiling, which is likely how a developer engaged in a performance investigation wants to see things. Based on the sequence of context switch trace events, the Concurrency Visualizer calculates processor utilization by the process, aggregates it for the current selection window, and displays it in the CPU Utilization View. In the CPU Utilization View, all other processor activity for processes (other than one being profiled) is lumped together under a category called “Other Processes.” System-processes and the “Idle process,” which is a bookkeeping mechanism, not an actual process that is dispatched, are also broken out separately. See Hazim’s article for more details.

Beyond its CPU utilization calculations, the Concurrency Visualizer’s primary focus is on being able to reconstruct the sequence of events that impact an application’s execution progress. The Concurrency Visualizer’s Threads View is the main display showing an application’s execution path. The view here is of execution progress on a thread by thread basis. For each thread in your application, the Concurrency Visualizer shows the precise sequence of context switch events that occurred. These OS Scheduler events reflect that thread’s execution state. See Figure 2 for an example of this view.

Figure 2 shows the execution path of six application threads, a Main thread, a generic worker thread, and 4 CLR worker threads that the application created by instantiating a ThreadPool object. (There were originally more threads than this, but I have hidden some that were inactive over the entire run.) For each thread, the execution state of the thread – whether it is running or whether it is blocked –is indicated over time. The upper part of the display is a timeline that shows the execution state of each thread over time. The execution progress of each thread display is constructed horizontally from left to right from rectangles that indicate the start and end of a particular thread state. An interval when the thread was running shows as green. An interval where the thread is sleeping is shown in blue. A ready thread that is blocked from executing because a higher priority thread is running is shown in yellow. (This state is labeled “preemption.”) A thread in a synchronization delay waiting on a lock is shown as red.

On the lower left of the display is a Visible Timeline Profile. This summarizes the state of all threads that are visible within the selected time window. In the screen shot in Figure 2, I have zoomed into a window that is approximately 150 milliseconds wide. During that interval, the threads shown were in a state where they were actively executing instruction only 11% of the time. For 25% of the time interval, threads were blocked waiting on a lock. There is a tabbed display at the lower right. If you click on the “Profile Report” tab, a histogram displays that summarizes the execution state of each individual thread over the time window. In the screen shot, I have clicked on the “Current stack,” which displays the call stack associated with the ETW context switch event. If the thread is blocked, the call stack indicates where in the code the thread will resume execution once it unblocks. We will drill into that call stack in a moment.

Note: The Threads View also displays call stacks from processor utilization samples that ETW gathers on a system-wide basis once per millisecond. These are available during any periods when the thread is executing instructions (and ETW execution sampling is active).

One of the other ETW events that the Concurrency Visualizer analyzes is the ReadyThread event. The interval between a ReadyThread event and a subsequent Context Switch that signals that a ready Thread is being dispatched measures CPU queue time delay directly. Using event data, it is possible to measure CPU queuing delays to a degree of precision that far exceeds anything that can be done using performance counters.

The Concurrency Visualizer screen shot in Figure 2 illustrates the calculation of CPU queue time delay. Thread 6920, which happens to be a CLR thread pool worker thread, is shown at a point in time where it was preempted by a higher priority task. The specific delay that I zoomed in on in the screen shot is preemption due to the scheduling of a high priority LPC or ISR – note this category also encompasses assorted APCs and DPCs. In this specific example, execution of Thread 6920 was delayed for 0.7718 milliseconds. According to the trace, that is the amount of time between Thread 6920 being preempted by a high priority system routine and a subsequent context switch where the ready thread was finally re-dispatched.

Figure 2. Screen shot of the Concurrency Visualizer illustrating thread preemption by a higher priority system routine. (Click for full size image.)

The tool also displays the call stack of the preempted thread. The call stack indicates that the CLR’s garbage collector (GC) was running at the time that thread execution was preempted. From the call stack, it looks like the GC is sweeping the Large Object Heap (LOH), trying to free up some previously allocated virtual memory. This is not an opportune time to get preempted. You can see that one of the other CLR worker threads, Thread 6420, is also delayed. Notice from the color coding that Thread 6420 is delayed waiting on a lock. Presumably, one of the other active CLR worker threads in the parent process holds the lock that Thread 6420 is waiting for.

This is one of those “Aha” moments. If you click on the synchronization delay that Thread 6420 is experiencing, as illustrated in Figure 3, you can see that the lock that Thread 6420 is trying to acquire is, in fact, currently held by Thread 6920. Clicking on the tab that says “Current Stack” (not shown) indicates that the duration of the synchronization delay that Thread 6420 suffered in this specific instance of lock contention was about 250 milliseconds.

The scenario here shows one CLR worker thread blocked on a lock that is held by another CLR worker thread, which in turn finds itself being delayed due to preemptions from higher priority Interrupt processing. We can see that whatever high priority work preempted Thread 6920 has the side effect of also delaying Thread 6420, since 6420 was waiting on a lock that Thread 6920 just happened to be holding at the time. The tool in Figure 3 displays the Unblocking stack from Thread 6920 which shows the original memory allocation from the Dictionary.Resize() method call being satisfied, releasing a global GC lock. When Thread 6920 resumed execution following its preemption, the GC operation completes, releasing the global GC lock. Thread 6920 continues to execute for another 25 microseconds or so, before it is preempted because its time slice expired. Even as Thread 6920 blocks, Thread 6420 continues to wait while a different CLR thread pool thread (4664) begins to execute instead. Finally, after another 25 microseconds delay, Thread 6420 resumes execution. For a brief period both 6420 and 4664 execute in parallel from approximately the 7640 to 7650 microsecond milestones. (However, they are subject to frequent preemptions during that period of overlapped execution.) Welcome to the wonderful world of indeterminancy in concurrent programming.

Figure 3. CLR Worker Thread 6420 blocked because it is waiting on a GC lock that happens to be held by Thread 6920, which is subject to preemption by higher priority system routines. (Click for full size image.)

I won’t take the time now to go into what this little concurrent CLR thread pool application is doing. Suffice to say that I wrote it to illustrate some of the performance issues developers can face trying to do parallel programming, which is the other topic I have been blogging about. (I should note that the test program puts the worker threads to sleep periodically to simulate synchronous I/O waits.) As I started to run the test app I developed using the Concurrency Visualizer, I was able to see blocking issues like this one where the Common Language Runtime introduced synchronization and locking considerations that are otherwise opaque to the developer. I eventually tweaked the test app into an especially ghoulish version I call the LockNestMonster program to shine an even brighter light on these issues. (More about this later when I resume blogging about concurrent programming in .NET.)

Time-slicing.

The Concurrency Visualizer also breaks out preemption due to the expiration of a thread’s time-slice, the duration of a time slice being one of the few tuning adjustments available in the OS. For the record, I normally recommend that system administrators not fiddle with this tuning knob, unless they have a whole lot of extra time on their hands. (This older KB article provides some flavor for what is involved.) For those of you that cannot resist the temptation, the Concurrency Visualizer Threads View is the first Windows performance tool that can help you determine if changing the OS default time-slice value is doing your application any good, or harm, for that matter.

In Figure 4, I clicked on the large yellow block on the right hand side of the execution time bar graph for Thread 6920 indicating another long delay. As in Figure 3, I have hidden all but the three active CLR thread pool threads. Using a combination of zooming to a point of interest in the event stream and filtering out extraneous threads, Figure 4 shows that the Concurrency Visualizer computes an execution time profile for just those events that are visible in the current window. Overall, the three active CLR worker threads are only able to execute 18% of the time, while they are delayed by synchronization 9% of the time and subject to preemption 39% of the time. (You can click on the Profile Report tab in the lower right portion of the display and see a profile report by thread.)

Figure 4. Using the Concurrency Visualizer to drill into thread preemption delays. (Click for full size image.)

At the point indicated in the tool, the time-slice quantum for Thread 6920 expired and the Scheduler preempted the executing thread in favor of some other ready thread. Looking at the visualization, it should be apparent that the ready thread the Scheduler chose to execute next was another CLR thread pool worker thread, namely Thread 4664, which then blocked Thread 6920 from continuing. The tool reports that a context switch(6920, 4664) occurred, and that Thread 6920 was delayed for about 275 milliseconds before it resumed execution as a result of being preempted.

As illustrated in this example, the Concurrency Visualizer uses the ETW-based event data from a profiling run to construct a state machine that reflects the precise execution state of each application thread over the time interval being monitored. It goes considerably beyond calculating processor queue time at the thread level. It understands how to weave the sequence of Ready Thread and Context switch events together to create this execution time profile. It summarizes the profiling data, calculating the precise amount time of time each thread is delayed by synchronous IO, page faults (i.e., Memory Management overhead), processor contention, preemption by priority work, and lock contention over the profiling interval. Furthermore, it analyzes the call stacks gathered at each Context Switch event, looking for signatures that identify the specific blocking reason. And, specifically, to help with lock contention issues, which are otherwise often very difficult to identify, it also identifies the thread that ultimately unblocks the thread that was found waiting to acquire a lock.

I will discuss another new facility for capturing CPU time accurately at the thread level as your program executes in the next blog post in this series.

-- Mark Friedman

Statistical Process Control Techniques in Performance Monitoring and Alerting

Mark B Friedman — Wed, 27 Jan 2010 01:31:00 GMT

Being focused on the upcoming release of Visual Studio 2010 for the past six months or so, I, unfortunately, have been neglecting to blog about it. Before I get back to the series of blog posts I started about writing in parallel programming, I thought I’d first answer the mail.

Concerning a recent presentation by Charles Loboz, my colleague at Microsoft, at CMG09 in Texas (DEC 2009), Uriel Carrasquilla, a very knowledgeable and resourceful performance analyst at NCCI in Florida, writes,

“Mr. Loboz indicated that the theoretical calculations were based on Windows reporting of CPU busy and CPU queue length. My results indicate that the CPU queue length reported by Microsoft can't be correct. I found that other CMG researchers came up with the same conclusion.

“I used similar ideas for my Linux, AIX and Sun Solaris data as reported by SAR, and Mr. Loboz ideas work like a charm.

“Question: are you aware of this problem with Microsoft performance reporting? Is anybody working on this issue?”

Uri,

The short answer is,

“The derivation and interpretation of the System\Processor Queue Length performance counter is well-documented in the Windows 2003 Server Performance Guide, published back in the Windows 2003 Server Resource Kit. I believe the Processor Queue Length performance counter continues to be a very useful metric to track, as Charles and his team that is responsible for capacity planning for the many of the Microsoft online properties do.”

n Mark

I will post a more expansive answer soon, allowing me to expound a little on a question that gets asked quite frequently, namely, “How are measures of CPU utilization in Windows derived and how can they be interpreted?”

First, though, I’d like to mention some of the work Charles Loboz and his team have been doing in the context of capacity planning to support some of the massive applications Microsoft provisions and supports. Consider an application like Hotmail that supports something in the neighborhood of 500 million mailboxes (give or take a couple hundred million) and a customer base that is global in scale. That is an order of magnitude larger than the largest corporate entity responsible for a single e-mail or messaging infrastructure. (My guess is that the largest corporate entity responsible for a single e-mail infrastructure is the US Department of Defense. Although, it might be the US Army instead since the different service branches probably operate separate infrastructures.) Performance monitoring and capacity planning on the scale of Hotmail or Search is certainly unprecedented. Do you think performance and capacity planning are important in an application the size of Hotmail. The answer is, “You bet.” The investment in hardware and power consumption alone justifies the capacity planning effort.

I had an opportunity to see some of the material that Charles was working on back in the summer & gave him some feedback on measurements and what valid inferences can be drawn from them. I haven’t read the final published version, but, I am certainly in sympathy with the approach he has adopted. (BTW, people like Uri that attended the recent CMG Conference have access to Charles’ paper, but no one else at the moment. As soon as Charles posts it somewhere publicly, I will point this blog entry to it.)

Although the scale Charles has to deal with is something new, the approach isn’t. I remember I also sent Charles a pointer to Igor Trobin's work, which I believe is very complementary. Igor writes an interesting blog called “System Management by Exception.” In addition, Jeff Buzen and Annie Shum published a very influential paper on this subject called “MASF: Multivariate Adaptive Statistical Filtering” back in 1995. (Igor’s papers on the subject and the original Buzen and Shum paper are all available at www.cmg.org.) My colleague Boris Zibitsker has also made a substantial contribution to what I consider a very useful approach, namely applying statistical process control (SPC) techniques to mine for gold within the enormous amounts of performance data that IT organizations routinely gather.

For perspective, Carnegie Mellon’s Software Engineering Institute (SEI) is usually credited with the original application of SPC techniques to software engineering. Len Bass at SEI wrote an excellent book entitled Software Architecture in Practice that embraces a broader perspective on quality in software development that I share. Len’s work on software quality metrics is close to my current interests here in Developer Division, especially around the potential value of scenario-driven development processes. (More on scenarios in the next blog post. Len’s submitted to a brief interview on Channel 9 recently that is posted here.)

Within the application life-cycle, performance, unfortunately, is considered one of the non-functional requirements associated with a system specification, which often means it is relegated to a secondary role during the much of the application life-cycle. In the specification process, getting the business requirements and translating them into system specifications correctly is the most pressing problem for developers of Line of Business applications. Performance is one of those aspects of software quality that often doesn’t get expressed during the software development life cycle until very late in the process when design flaws that lead to scalability problems are very expensive to fix.

Len Bass’s suggestion is that the requirements definition of a scenario should include a response time specification that can then be monitored throughout the development life cycle, just like any other set of requirements. That is the approach that we advocate using here in the Microsoft Developer Division for the software products that we built here. In developing Visual Studio 2010, for example, we made major commitments to performance requirements and regularly conduct automated acceptance testing against those requirements. However, you can also see from the many recent blogs on VS 2010 performance coming from the Microsoft Developer Division that we have not exactly gotten this down to a science yet.

The Len Bass and SEI approach is informed by experience building real-time control systems to fly airplanes, for example, where performance goals absolutely have to be met or the system cannot function as designed. The performance requirements for real-time control systems applications are fundamentally easy to specify. If the computer system doesn’t recognize a condition and respond to it in time, the plane is going to crash. Bass makes the case for that system performance being one of those important Quality Attributes that needs to be addressed at the outset of the development life cycle, beginning with the architectural specification and continuing through the design, development and QA processes, to the delivered software’s operational phase, where it finally becomes the focus of performance analysts and capacity planners like Charles Loboz, Uriel Carrasquilla, and Igor Torbin.

What if you need to specify performance requirements for your LOB application, but don’t know where to start? Consider these two approaches:

· Research in human factors engineering has generated a set of performance requirements for specific types of human-computer interactions in order to promote usability and improve customer satisfaction. Steve Seow, another colleague here in Microsoft, has an excellent, concise book on this topic called “Designing and Engineering Time,” complete with application responsiveness guidelines to help improve customer satisfaction. If you are in a position to design a new application from scratch from First Principles, Steve’s book will be an invaluable guide.

· If the application currently exists in some form or another, measure its current performance. When you deliver the next version of the application, any significant decrease in performance from one release to the next will be perceived as an irritant and received negatively by existing users. In other words, measure the scenario of interest on the current system & use that as a baseline that you won’t regress in a subsequent version.

If you have to start somewhere, measuring current levels of performance around key scenarios and using them as a baseline gives you a place to start, at least. My experience is that the current level of performance sets expectations that the next version of the application must meet if you want your customers to be satisfied. In this context, Steve Seow's book cites psychological research into how much of a response time difference is necessary to be perceived as a difference. (About 20% in either direction makes a difference.) This reminds me of Gregory Bateson’s adage that “information is a difference that makes a difference.”

I do think that over time, humans adapt themselves to the response times they experience, such that, eventually, the response times of the new version become the new baseline. In other words, our positive or negative perception tends to atrophy over time. For example, consider the last time you acquired a new desktop or portable computer that was noticeably faster than its predecessor. How long was it before that rush of enthusiasm for the fast, new machine started to diminish? About 30 days, in my experience.

Twenty-five years ago, I was in a similar position to Charles, responsible for performance and capacity planning at a large telecommunications company for maybe 20 IBM mainframe computers, which was considered a whole lot of machines to keep track of back in those days. We used a product called MICS (full disclosure, I was a developer on MICS for a brief period in the mid-80s) to warehouse the performance data we were gathering from these machines and the SAS language for statistical reporting. Subsequently, at Landmark Systems, I designed a “management by exception” feature for our monitoring products that our customers loved based on very simple statistical process control techniques. Today, for Charles’ team that needs to monitor performance on 100,000s of servers, these statistical techniques are the only viable approach.

But, of course, Uri is correct. You do have to choose the right metrics. I believe Charles has. I will discuss the CPU utilization metrics in Windows in my next post.

-- Mark Friedman

Looking at Virtual Memory Usage

David Berg — Tue, 08 Dec 2009 15:43:00 GMT

Brian Harry is continuing a great series of posts on VS2010 performance, you can read the latest in that series here; where Brian talks about the issues we've been seeing around Virtual Memory Exhaustion and what we're doing to address it.

Improvements in Intellisense post Beta 2

David Berg — Sat, 05 Dec 2009 06:06:00 GMT

Brian Harry has posted a discussion of Intellisense performance improvements in VS2010 that we've made since Beta 2, including bothe before and after videos. He also touches a little on the massive performance effort we're making as a division to address the performance issues identified by our external and internal customers.

Improving the Start-up Performance of the WPF and Silverlight Designer in Visual Studio 2010 Beta 2

David Berg — Mon, 02 Nov 2009 18:34:00 GMT

I wanted to let you know about a last minute change that went into VS 2010 Beta 2 that you can use to improve the startup performance for the WPF and Silverlight Designer. The change went in late and it was a little risky, so we decided to leave it off until we had a chance to do some more testing with it. You can turn the change on yourself via a registry key. We expect the change will be on all the time in the final product, so changing the registry key is strictly a Beta 2 issue.

If you have any feedback on how this works (or doesn't work) for you, please let me know. You can contact me at DevPerf@Microsoft.com.

Regards,

Dave

VS2010 Performance and Bad Video Drivers/Hardware

David Berg — Fri, 30 Oct 2009 05:49:00 GMT

[Note, this post is superceeded by a newer post here.]

We’ve received a few performance complaints around Visual Studio 2010 (Beta 2) performance that can be traced to old video drivers or GPU virtualization issues.

If you’re seeing slow / broken screen updates verify you have the latest drivers for your system. If this doesn’t resolve your rendering issues, you may be able to work around the problem by forcing software emulation mode by changing one registry key:

[HKEY_CURRENT_USER\Software\Microsoft\Avalon.Graphics]

"DisableHWAcceleration"=dword:00000001

As you can probably guess, this can be undone with:

[HKEY_CURRENT_USER\Software\Microsoft\Avalon.Graphics]

"DisableHWAcceleration"=dword:00000000

If you have these issues, please, let me know by either posting here or preferably by e-mailing DevPerf@Microsoft.com with details about the problems you are/were seeing. (When you e-mail, please run DXDIAG first and attach the DXDIAG.TXT file. This will give us a lot of information about your system, including what drivers you’re running.)

We’re very interested in finding any hardware/software incompatibilities we might have missed and getting them cleaned up.

If you do find you need to use software emulation, and then get new drivers or hardware later, don’t forget to switch software emulation back off so you can benefit from the improved performance.

Note that this will impact all WPF applications on the system, not just Visual Studio.

Regards,

Dave Berg
Developer Division Performance Team

Tell us about VS2010 Beta2

David Berg — Thu, 29 Oct 2009 21:49:00 GMT

Last week we shipped Beta 2 for broad distribution. Many of you have already sent us comments and improvement suggestions (thanks!)

At this point we are down to our final set of bug fixing, perf tuning, etc. We’re very interested in your feedback so we can take action on it before we ship the final version. To help make it easy, you can take this simple survey.

One thing in particular we are hearing a lot of feedback on is performance. We are working hard on the next round of perf improvements. You can supply your feedback through the survey. When you give us your feedback, the more actionable you can make it the better. We need to know what operations you are doing (like editing, debugging, etc), what kind of hardware you have (CPU, RAM, disk), and your hosting scenario (main machine, running in VM, terminal server, etc).

Thanks in advance for your feedback!

Dave

P.S. If you'd like to talk to me directly about your performance experience, you can reply here or e-mail us at DevPerf@Microsoft.com.

Parallel Scalability Isn’t Child’s Play, Part 3: The Problem with Fine-Grained Parallelism

Mark B Friedman — Tue, 09 Jun 2009 23:17:00 GMT

In the last blog entry in this series, I introduced the model for parallel program scalability proposed by Neil Gunther, which I praised for being a realistic antidote to more optimistic, but better known, formulas. Gunther’s model adds a new parameter to the more familiar Amdahl’s law. The additional parameter k, representing coherence-related delays, enables Gunther’s formula to model behavior where the performance of a parallel program can actually degrade at higher and higher levels of parallelization. Although I don’t know that the coherence delay factor that Gunther’s formula adds fully addresses the range and depth of the performance issues surrounding fine-grained parallelism, it is certainly one of the key factors Gunther’s law expresses that earlier formulations do not.

Developers experienced in building parallel programs recognize that Gunther’s formula echoes an inconvenient truth, namely, that the task of achieving performance gains using parallel programming techniques is often quite arduous. For example, in a recent blog entry entitled “When to Say No to Parallelism,” Sanjiv Shah, a colleague at Intel, expressed similar sentiments. One very good piece of advice Sanjiv gives is that you should not even be thinking about parallelism until you have an efficient single-threaded version of your program debugged and running.

Let’s continue, for a moment, in the same vein as “When to Say No to Parallelism.” Let’s look at the major sources of coherence-related delays in various kinds of parallel programs, how and why they occur, and what, if anything, can be done about them. Ultimately, I will try to tie this discussion into one about tools, especially some great new tools in Visual Studio Team System (see Hazim Shafi’s blog for details) that help you understand contention in your multi-threaded apps. When you use these new tools to gather and analyze the thread contention data for your app, it helps when you understand some of the common patterns to look for.

The first aspect of the coherence delays Gunther is concerned with that we will look at are the bare minimum additional costs that a parallel program running multiple threads must pay, compared to running the same program single threaded. To simplify matters, we will look at the best possible prospect for parallel programming, an algorithm that is both embarrassingly parallel and easy to partition into roughly equal sized subprogram chunks. There are two basic costs to consider: one that is paid up front for initialization of the parallel runtime environment, and one that is paid incrementally each time one of the parallel tasks executes. It is also worth noting that these are unavoidable costs. I will lump both costs into an overhead category associated with Gunther’s coherence delay factor k. The embarrassingly parallel programs we will consider here will incurr these minimum processor overhead penalties when they are transformed to execute in parallel.

Fine grained parallelism.

To frame this part of the discussion, let’s also consider the characterization of workloads and their amenability to parallelization into either fine-grained or coarse-grained ones. This distinction implicitly recognizes the impact of coherency delay factors on scalability. With fine-grained parallelism, the overhead of setting up the parallel runtime & executing the tasks in parallel can easily exceed the benefits. By definition, the initialization overhead of spinning up multiple threads and dispatching them is not nearly so big an issue when the program lends itself to coarse-grained parallelism. Plus, when you are looking at a very long running process with many opportunities to exploit parallelism, it is important to understand you should only have to incur the setup cost once.

Coarse-grained parallelism occurs when each parallel worker thread is assigned to computing a relatively long running function:

Figure 5. Coarse-grained parallelism.

while fine-grained parallelism looks more like this:

Figure 6. Fine-grained parallelism.

The difference, of course, lies in how long, relatively speaking, the worker thread processing the unit of work executes.

The rationale for the fine-grained:coarse-grained distinction is its significance to performance. We identify those parallel algorithms that execute in the worker thread long enough to recover the costs of setting up and running the parallel environment as coarse-grained. The benefits of running such programs in parallel are much easier to realize. On the other hand, the one full proof way to identify fine-grained parallelism is to find embarrassingly parallel programs with very short execution time spans for each parallel task. When executing fine-grained parallel programs, there is a very high risk of slowing down the performance of the program, instead of improving it. (If this sounds like a bit of circular reasoning, it most surely is.)

Now let’s drill into these costs. In the .NET Framework, setting up a parallel execution environment is usually associated with the ThreadPool object. (If you are not very familiar with how to set up and use a ThreadPool in .NET, you might want to read this bit of documentation first that shows some simple C# examples. If you really want to understand all the ins and outs of the .NET ThreadPool, you should considering picking up a copy of Joe Duffy’s very thorough and authoritative book, Concurrent Programming in Windows.)

The thing about using the ThreadPool object in .NET is that you don’t need to write a lot of code on your own to get it up and running. With very little coding effort, you can be running a parallel program. In the .NET Framework, there are newer programming constructs in the Task Parallel Library that are designed to make it easier for developers to express parallelism and exploit multi-core and many-core computers. But underneath the covers, many of the new TPL constructs are still using the CLR ThreadPool. So whatever overheads are associated with this older, less elegant approach still apply to any of the newer parallel programming constructs.

The ThreadPool in .NET

The basic pattern for using the ThreadPool is to call the QueueUserWorkItem() method on the ThreadPool class, passing a delegate that performs the actual processing of the request, along with a set of parameters that are wrapped into a singleton Object. The parameters delineate the unit of work that is being requested. Typically, you also pass to the delegate a ManualResetEvent, what is known as a synchronization primitive. This event is used by the delegate to signal the Main task that the worker thread is finished processing the Work Item request.

Structurally, you have to write:

a class that wraps the Work Item parameter list,
a C# delegate that runs in the worker thread to process the Work Item request,
a dispatcher routine that queues work items for the thread pool delegate to process, and
finally, an event handler to get control when the worker thread completes.

For example, to implement the Fork/Join pattern in .NET using the built-in ThreadPool Object, create (1) a wrapper for the parameter list:

public class WorkerThreadParms

{

private ManualResetEvent _thisevent;

…

public ManualResetEvent thisevent

{

get { return _thisevent;

}

…

public WorkerThreadParms(ManualResetEvent signalwhendone, …,)

{

_thisevent = signalwhendone;

…

}

(2) the ThrealPool delegate that unwraps the parameter list, performs some work, then signals the main thread when it is done:

public void ThreadPoolDelegate(Object parm)

{

WorkerThreadParms p = (WorkerThreadParms) parm;

ManualResetEvent signal = p.thisevent;

… //Do some work here …

signal.Set(); //Signal main task when done

}

(3) a (simple) dispatcher loop:

ManualResetEvent[] thisevent = new ManualResetEvent[tasks];

for (int j = 0; j < tasks; j++)

{

thisevent[j] = new ManualResetEvent(false);

WorkerThreadParms p = new WorkerThreadParms(thisevent[j],…);

WorkerThread worker = new WorkerThread();

ThreadPool.QueueUserWorkItem (worker.ThreadPoolDelegate,p);

}

followed by (4) a WaitForMultipleObjects in the Main thread:

ManualResetEvent.WaitAll(thisevent);

You can see there isn’t very much code for you to write to get up and running in parallel and start taking advantage of all those multi-core processor resources. You should take Sanjiv Khan’s advice and write & debug the delegate code you intend to parallelize by testing it in a single threaded mode first. Once the single threaded program is debugged and optimized, you can easily restructure the program to run in parallel by encapsulating that processing in your worker thread delegate following this simple recipe.

Even though there isn’t very much code for you to write, there are overhead considerations that you need to be aware of. Let’s look at the simplest case where the program is embarrassingly parallel (as discussed in the previous blog entry). This allows us to ignore complications introduced by serialization and locking (which we will get to later). These overheads include

(1) work done in the Common Language Runtime (CLR) on your behalf to spin up the worker threads in the ThreadPool initially, and

(2) the additional cost when running the parallel program associated with queuing work items, dispatching them to a thread pool thread to process, and signaling the main dispatcher thread when done.

In the case of the initialization work, this is something that only needs to be done once. The other costs accrue each time you need to dispatch a worker thread. For parallelism to be an effective scaling strategy, it is necessary to amortize this overhead cost over the life of the parallel threads. The worker thread delegates need to execute long enough that there is a benefit to executing in parallel. And this is for a best case for parallelism where the underlying program is both embarrassingly parallel and easy to partition into roughly equivalent work requests.

A Parallel.For example.

Using the new Parallel.For construct in the Task Parallel Library, by the way, there is even less code you have to write. All you need to code the Parallel.For is write is the worker thread delegate, because the TPL library handles the remaining boilerplate tasks. However, the underlying overhead considerations are almost identical.

The challenge of speeding up programs that have fine-grained parallelism grows in tandem with making it easier for developers to write concurrent programs. Take a look at the following example of parallelization in C# using the new Parallel.For construct taken verbatim from a Microsoft white paper entitled “Taking Parallelism Mainstream.” The white paper describes some of the new language facilities in the Task Parallel Library that make it easier for developers to write parallel programs. These new language facilities include Parallel For loops, Parallel LINQ, Parallel Invoke, Futures and Continuations, and messaging using asynchronous agents. To the extent that these parallel computing initiatives succeed, they will generate the need for better performance analysis tools to understand the performance of concurrent programs because not everyone who implements these new constructs is going to see impressive speed-up of his or her applications. Some developers will even see the retrograde performance predicted by Gunther’s scalability formula.

Here’s the C# program that illustrates one of the new parallel programming constructs:

IEnumerable<StockQuote> Query(IEnumerable<StockQuote> stocks) {

var results = new ConcurrentBag<StockQuote>();

Parallel.ForEach (stocks, stock => {

if (stock.MarketCap > 100000000000.0 &&

stock.ChangePct < 0.025 &&

stock.Volume > 1.05 * stock.VolumeMavg3M) {

results.Add(stock);

}

});

return results;

}

The example uses a Parallel.ForEach enumeration loop, along with one of the new concurrent collection classes, the ConcurrentBag, to evaluate stock prices based on some set of selection criteria. The problem, the white paper author notes, is one that is considered “embarrassingly parallel” because it is easily decomposed into independent sub-problems that can be executed concurrently. The new C# Task Parallel Library language features provide an elegant way to express this parallelism. Underneath the Parallel.For expression is a run-time library that understands how to partition the body of the parallel For loop into multiple work items, and dispatches them to separate worker threads that are then scheduled to execute concurrently.

The .NET Task Parallel Library (TPL) provides the run-time machinery to turn this program into a parallel program. At run-time, it automatically parallelizes the lambda expression that the Parallel.For construct references. In this example, the Task Parallel Library takes the If Statement in the lambda expression and queues it up to run in parallel using the concurrent runtime library in .NET. The concurrent runtime library creates a thread pool and then delegates the processing of the lambda expression to these worker threads. The concurrent runtime attempts to allocate and schedule an optimal number of worker threads to this parallel task.

While TPL makes it easier to express parallelism in your programs and eliminates most of the grunt work in setting up the runtime environment associated with parallel threads, it cannot guarantee that running this program in parallel on a machine with four or eight processors will actually speed up its execution time. That is the essence of the challenge of fine-grained parallelism. There is overhead associated with queuing work items to the thread pool the parallel run-time manages. This is overhead that the serial version of the program does not encounter. Only when the amount of work done inside the lambda expression executes for a long enough time does the benefit of parallelizing the lambda expression exceeds this cost, which must be amortized over each concurrent execution of the inner body of the Parallel.For loop. Note that this particular set of overheads is unavoidable. When you are dealing with fine-grained parallelism, the overhead of setting up the parallel run-time environment alone often exceeds the potential benefit of executing in parallel, notwithstanding other possible sources of contention-related delays that could further slow down execution time.

So, it is important to realize that a code sample like the one I have taken here from the parallel programming white paper was chosen to illustrate the expressive power of the new language constructs. The example was intended to show the pattern that developers should adhere to -- I am certain it wasn't intended to illustrate something specific you would actual do. When you are taking advantage of these new parallel programming language extensions, you need to be aware of the fine-grained:coarse-grained distinction. This is emphatically not an example of a program that you will necessarily speed up by running it in parallel. It will take considerably more anlysis to figure out if parallelism is the right solution here. Speeding up a serial program by running portions of it in parallel isn’t always easy – even when that program has sections that are “embarrassingly parallel.”

What we’d like to be able to do is to estimate the actual performance improvement we can expect of this parallel program, compared to its original serial version. “Embarrassingly parallel” is another way of saying that, once parallelized, the serial portion of this program is expected to be quite small. However, this is also an example of fine-grained parallelism because the amount of code associated with the lambda expression that is passed to worker thread delegate to execute is also quite small. An experienced developer at this point should be asking whether the overhead of creating these working threads and dispatching them might, in fact, be greater than the benefit of executing this task in parallel. This relatively fixed overhead is especially important when the amount of work performed by each delegate is quite small – there is only a limited opportunity to amortize this overhead to initiate and manage the multithreaded operation across the execution time of each of the worker threads. It is extremely important to understand this in the case of fine-grained parallelism.

Next, we will turn to coarse-grained parallelism, where the odds are much better that you may be able to speed up program execution substantially using concurrent programming techniques. In the next blog entry, I will start to tackle more promising examples. The analysis of the performance costs associated with parallel programming tasks will become more complex. I will try to illustrate this analysis using a concrete programming example that will simulate coarse-grained parallelism. As we look at how this simple programming example scales on a multi-core machine, it will bring us face-to-face with the pitfalls even experienced developers can expect to encounter when they attempt to parallelize their existing serial applications.

We will also start to look into the analysis tools that we are available in the next version of the Visual Studio Profiler that greatly help with understanding the performance of your .NET parallel program. In the meantime, if you'd like to get a head start on these new tools in the Visual Studio Profiler , be sure to check out Hazim Shafi’s blog for more details.

Are we taking advantage of Parallelism?

Sunny Egbo — Sun, 03 May 2009 01:38:00 GMT

Recently, a colleague of mine, Mark Friedman, posted a blog titled “Parallel Scalability Isn’t Child’s Play” in which he reviewed the merits of Amdahl Law vs. Gunther’s Law for determining the practical limits to parallelization. I would not argue with the premise of Mark’s blog that Parallelism is not child’s play. However, I do have alternate views of the use of Amdahl Law and Gunther’s Law that I posted on his blog. I think my views and comments on Mark’s blog warrant another blog to fully explain.

Speaking of child’s play: my 10-year old son recently made a two-part movie titled “the Way” and “the Way Back” complete with a full storyline, multiple sound tracks and narrations. He put these movies together with only the help of his eight-year old sister, using sample movie clips and stock photographs he found on his computer hard drive. He asked me for help getting his two masterpieces onto a DVD capable of playing on the average home DVD player. Also, he asked about the length of a typical movie playing in movie theaters around the U.S. (approximately 2 hours) and how much these movies cost at the movie theater (approximately $12 for adults and $8 for children, minus the popcorn). Based on my answers, he determined that he will charge 25 cents for people to watch his movies, because he wanted everyone to attend. I wanted to ask him how much he would charge someone who decided to watch only one of the clips. However, I didn’t because I did not want to lose a price haggling war with a 10-year old. Besides, it would be terrible if you cannot find your way back.

In any case, his movies were quite impressive. The most technologically savvy thing I did as a 10-year old kid was to build a telephone line with tomato soup cans and a string. Movie making was out of reach for me; but now it is child’s play.

Today, parallelism is not child’s play. However, I hold out hope that in the future the typical computer program would be written with parallelism in mind. Is parallelism ever going to be child’s play in the future the way movie making is today?

Parallelism exists everywhere: instruction level, memory level, loop level and task level parallelism, etc. Also, parallelism has been with us for quite some time now. For the past several decades, hardware engineers have quietly been busy solving problems in parallel to improve processor and system level performance. However, for the past four or more years, hardware designers have encountered the twin brick walls created by memory speed and power. These walls have forced CPU architects and hardware designers to go multi-core in a major way. The doubling of the CPU frequency every 18 months, that was true for many decades, are no longer practical and have come to an abrupt end. Although, hardware performance continues to improve as my colleagues and I pointed out in our blog “Investigating a Pleasant Surprise,” the pace of CPU frequency increases has slowed considerably. Instead, hardware designers have been doubling the number of cores available on a single CPU socket every couple of years.

To get the same level of performance that was previously possible, software engineers would now need to step up to the plate—to write software in a parallel and scalable fashion. They would need tools and frameworks that allow them to think about their problems, identify opportunities for parallelism and to analyze their solutions correctly and efficiently.

I am a big fan of Amdahl Law as an analysis framework. However, I do not subscribe to the narrow view that Amdahl’s Law applies only to parallelism, as most people who write about it seem to imply. I prefer the broader treatment of the Law by Hennessy and Patterson in their famous book “Computer Architecture: A Quantitative Approach”—where Amdahl’s Law is used to estimate the opportunities between competing designs. Amdahl’s Law is very powerful for showing the areas that will likely yield the most fruitful performance gains. In my performance design, tuning and optimization work, I use Amdahl Law for prioritizing the areas of opportunities to focus my efforts to gain performance.

Amdahl’s Law is not the limit to either absolute performance or parallelism as many authors seem to suggest. Gunther’s and Gustafson’s Laws are helpful for putting Amdahl’s Law in perspective. However, like Amdahl’s Law, these laws are not fundamental limits. The use of these three laws to estimate the level of parallelism that is possible is very flawed. Specifically, the use of these laws as fundamental limits can obfuscate the level of parallelism and performance inherent in typical computing problems. These laws gloss over a number of important points and practical aspects of obtaining parallelism in general purpose computing, including that:

1. Many user tasks are non-monolithic and can be solved in a distributed fashion. Background tasks (e.g., virus scans) that often block single processor execution can now be done in a way that improves user experiences. The key is to identify unnecessary dependencies that would allow these tasks to proceed in parallel with other tasks in a multi-core computer.

2. Some algorithms that have inefficient sequential solutions surprisingly have efficient parallel solutions. This fact should be comforting to fans of algorithms. For example, many applications require matrix multiplication, which turns out to be easily parallelizable. Although the best sequential algorithm for matrix multiplication has a time complexity of O(n^2.376), a straight-forward parallel solution has an asymptotic time complexity of O(log n) using n^2.376 processor. In other words, we can readily find a parallel solution for matrix multiplication that improves its runtime as more and more processor cores become available. Of course, you might have difficulty conceiving of n^2.376 processors in a system--as a colleague mentioned recently. However, this is just another way of saying that matrix multiplication will benefit with more and more processors.

3. Some poor sequential algorithms can be easily parallelized to execute in less time than their sequential solutions. Also, we know that some algorithms that have the best asymptotic time complexities achieve their speed by introducing data dependencies that make parallelization difficult and that the best asymptotic time complexity does not necessarily translate to the best runtime in real life. Hence, at some point, the benefit of the simpler parallelization of some poor sequential algorithms that have little data dependencies can outweigh the benefit of more efficient sequential counterparts that have data dependencies. Hence, when considering parallel solutions it is not always necessary to start with the sequential solution with the best time complexity [also, see comment about Fortune and Wylie below].

4. The real world performance of applications is not determined exclusively by the asymptotic time complexity of algorithms. Because of the increasing gap between CPU and memory speed, memory accesses are increasingly dominating the performance of applications running on modern CPUs. Although, the gap can be mitigated with large caches, every cache miss takes hundreds of CPU cycles to complete. Even a modest overlap in these memory accesses (Memory Level Parallelism) can improve application performance in noticeable ways.

Over the years, there have been efforts to classify computationally intractable problems. Many decision problems (i.e., Yes/No) and their optimization counterparts have been categorized into NP-complete and NP-Hard sets respectively. The Travelling Salesman (TSP), Online Bin-Packing and 3-Dimensional Matching problems are three famous examples of NP-Complete problems. In a similar fashion, problems that are difficult to parallelize have been categorized into the P-Complete set or the set of problems that are known to be inherently sequential. As you can imagine sorting is not P-Complete. Likewise, Matrix Multiplication is not in the P-Complete set. Processor scheduling can be done in O(log n) time units using n processors—so, it is not P-Complete either. In an ultimate twist of irony, many NP-Hard problems have heuristic solutions that can be executed in parallel to approximate the real solutions. Hence, the natural inclination to think that NP-Complete problems cannot be parallelized is not borne out in practice.

As it turns out, the real limit to parallelism seem not to be defined by Amdahl’s Law, Gunther’s Law, Gustafson’s Law or NP-Completeness, but by the P-Complete set. It appears that parallelizable problems are related to the asymptotic space complexity of their sequential solutions. According to the Fortune and Wylie’s Parallel Processing Thesis, any problem that can be solved with a poly-logarithmic space complexity can be parallelized efficiently. Because of the time space trade-off of algorithms, this implies that the sequential algorithm that achieves this space complexity is not necessarily the algorithm with the best asymptotic time complexity.

In any case, because one can evaluate problems on multiple levels beyond algorithms (e.g., at the instruction, memory and data access, loop and task levels), the set of problems that can be parallelized appears to be quite large. The question is how to identify and take advantage of the parallelization opportunities that may be inherently available and to do so in an efficient and scalable manner. How can we parallelize loops? How do we overlap high latency activities such as accesses to physical memory or I/O to amortize the cost of those activities? How do we minimize synchronizations? How do we partition tasks to eliminate bottlenecks from the critical paths? How do we dispatch work efficiently to improve efficient system utilization, improve throughput and improve latency? What areas of our application can benefit from what sets of efforts? These are some of the questions that allow for scalable designs.

Today, the tools to identify parallelism and scalability opportunities are very limited. The programming languages that allow programmers to express parallelism in a natural way are completely lacking. The tools to analyze and troubleshoot parallel implementations are limited as well. Debugging parallel implementation is particularly hard. However, I suspect that with some industry focus and incremental progress, we could continue to make parallelism accessible to average programmers in a few years. However, we are many years away.

What are some of the fundamental limits preventing such tools to be built? Like Mark said on his blog, achieving improved scalability using parallel programming techniques is certainly very challenging. But, can parallel programming be made less challenging with intuitive tools that expose parallel solutions in a natural way and allow programmers to exploit them? Can programming languages and tools improve to a point where a typical 10-year old will be able to write a parallel program as easily as they can put together a multi-track movie today?

Sunny Egbo

Parallel Scalability Isn’t Child’s Play, Part 2: Amdahl’s Law vs. Gunther’s Law

Mark B Friedman — Wed, 29 Apr 2009 07:51:00 GMT

Part 1 of this series of blog entries discussed results from simulating the performance of a massively parallel SIMD application on several alternative multi-core architectures. These results were reported by researchers at Sandia Labs and publicized in a press release. Neil Gunther, my colleague from the Computer Measurement Group (CMG), referred to the Sandia findings as evidence supporting his universal scalability law. This blog entry investigates Gunther’s model of parallel programming scalability, which, unfortunately, is not as well known as it should be. Gunther’s insight is especially useful in the current computing landscape, which is actively embracing parallel computing using multi-core workstations & servers.

Gunther’s scalability formula for parallel processing is a useful antidote to any overly optimistic expectations developers might have about the gains to be had from applying parallel programming techniques. Where Amdahl’s law can be used to establish a theoretical upper limit to the speed-up that parallel programming techniques can provide, Gunther’s law can also model the retrograde performance that we frequently observe when parallel computing is used. In other words, Gunther’s scalability formula encapsulates the behavior we frequently observe where adding more and more processors to a parallel processing workload can result in degraded performance. It is a more realistic model for people who adopt parallel programming techniques to enhance the scalability of their applications on multi-core hardware. So, without in any way trying to diminish enthusiasm for the entire enterprise, it is crucial to understand that achieving improved scalability using parallel programming techniques can be very challenging.

As I discussed in a review of Gunther’s last book, Gunther’s law adds another parameter to the well-known Amdahl’s Law. Gunther calls this parameter coherence. Parallel programs have additional costs associated with maintaining the “coherence” of shared data structures, memory locations that are accessed and updated by threads executing in parallel. By incorporating these coherence-related delays, Gunther’s formula is able to model the retrograde performance that all too frequently is observed empirically. The blue line marked “Conventional” in the chart Sandia Labs published (Figure 1 in the earlier blog) is a scalability curve that Gunther correctly cites is consistent with his model.

Let’s drill into the mathematics here for a moment. What Gunther’s calls his Universal Scalability law is an extension to the familiar multiprocessor scalability formula first suggested by Gene Amdahl. In Amdahl's law, p is the proportion of a program that can be parallelized, leaving 1 −p to represent the part of the program that cannot be parallelized and remains serial. Amdahl’s insight was that the 1-p amount of time spent in the serial execution portion of the program creates an upper bound on how much its performance can be improved when parallelized.

Consider a sequential program that we want to speed up using parallel programming techniques. An old-fashioned way to think about this is to identify some portion of the program, p, that can be executed in parallel, and then implement a Fork() to spawn parallel tasks, followed by a Join() to unify the processing and carry on sequentially afterwards. Conceptually, something like this:

Figure 3. Parallel processing using a Fork/Join.

Amdahl’s law simply observes that your ability to speed up this program using parallelism is a function of the proportion of the time, p, spent in the parallel portion of the program, compared to s, the time spent in the serial parts of the program. (Note that p + s = 1, in this formulation.) Amdahl’s observation was meant as a direct challenge to hardware architects who were advocating building parallel computing hardware. It was also easy for those advocates of parallel computing approaches to dismiss Amdahl’s remarks since Dr. Amdahl was clearly invested in trying to build faster processors, no matter the cost.

Advocates of parallel computing, of course, are not blind to the hazards of the parallel processing approach. Scalability of the underlying hardware is one challenge. An even bigger challenge is writing multi-threaded programs. For starters, it is often far more difficult to conceptualize a parallel solution than a serial one. (We can speculate that this may simply be a function of the way our minds tend to work.) Parallel programs are also notoriously more difficult to debug. When you are debugging a multi-threaded program running in parallel on parallel hardware, events don’t always occur in the exact same sequence. This is known as non-determinism, and it often leads to huge problems for developers because, for instance, it may be very difficult to reproduce the exact timing sequence that exposes an error in your logic.

Furthermore, once you manage to get your programs to run correctly in a parallel processing mode the performance wins of doing so are not a given. In the course of celebrating the performance wins they do get, developers can sometimes diminish an appreciation for how difficult it was to achieve those gains.

Notwithstanding the difficulties that need to be overcome, compelling reasons to look at parallel computation remain, including trying to solve problems that simply just won’t fit inside the largest computers we can build. Today, there is renewed interest in parallel programming because it is difficult for hardware designers to make processors run at higher and higher clock speeds using current semiconductor fabrication technology without them consuming excessive amounts of power and generating excessive amounts of heat in the process that must be dissipated. Power and cooling considerations are driving parallel computing today for portables, desktops, and servers.

Comparing Gunther’s formula to Amdahl’s law.

Meanwhile, Amdahl’s original insight remains relevant today. From Amdahl’s law, we understand that, no matter what degree of parallelism is achieved, the execution time of a program’s serial portion is a practical upper bound on the performance of its parallel counterpart. As an example, Figure 1 plots the scalability curve using Amdahl’s law where p = 0.9, when just 10% of the program remains serial. Notice that Amdahl’s law predicts the performance of a parallel program will level off as more and more processors are added. As you can, see Amdahl’s law shows diminishing returns from increasing the level of parallelism. You can see how the parallel approach becomes less and less cost-effective as more and more processors are added.

Figure 4. A comparison of Amdahl’s Law to Gunther’s Universal Scalability Model

Given that Amdahl was mainly acting as an advocate for building faster serial CPUs, something that he wanted to do anyway, his is by no means the last word on the subject. Researchers in numerical computing like the ones in Sandia Labs were encouraged a few years later by a paper from one of their own. John Gustafson of Sandia Labs published a well-known paper in 1988 entitled “Reevaluating Amdahl's Law” that adopted a much more optimistic stance to parallel programming. The essence of Gustafson’s argument is that when parallel processing resources become available, programmers will jigger their software to take advantage of them:

One does not take a fixed-size problem and run it on various numbers of processors except when doing academic research; in practice, the problem size scales with the number of processors. When given a more powerful processor, the problem generally expands to make use of the increased facilities. Users have control over such things as grid resolution, number of timesteps, difference operator complexity, and other parameters that are usually adjusted to allow the program to be run in some desired amount of time. Hence, it may be most realistic to assume that run time, not problem size, is constant.

Gustafson’s counter-argument does not refute Amdahl’s law so much as suggest there might be creative ways to work around it. It encouraged parallel programming researchers to keep plugging away, pursuing creative ways to sidestep Amdahl’s law. Microsoft’s Herb Sutter, in his popular Dr. Dobbs Journal column back in January 2008, cited Gustafson’s Law favorably to offer similar encouragement to software developers today that need to re-fashion their code to take advantage of parallel processing in the many-core, multi-core era.

Gunther’s augmentation of Amdahl’s law is grounded empirically, providing a more realistic assessment of scalability using parallel programming technology. Gunther’s formula is similar, but adds another parameter to Amdahl’s law, κ, that represents something called coherency delay:

C(p) = p/(1+s(p-1) + kp(p-1))

To show how the two formulas behave, in Figure 2 above, Amdahl’s law is compared to Gunther’s law for a program with the same 10% serial portion. I set the coherency delay factor in Gunther’s formula to 0.001. When a coherency delay is also modeled, notice that parallel scalability is no longer monotonically increasing as processors are added. When we allow for some amount of coherency delay, there comes a point when overall performance levels off and ultimately begins to decrease. Gunther’s formula not only models the performance of a parallel program that encounters diminishing returns from increased levels of parallelism, it also highlights the performance degradation that can occur when the communication and coordination-related delays introduced by multiple threads needing to synchronize access to shared data structures becomes excessive.

Gunther’s formula lumps all the delays associated with communication and coordination among threads that require access to shared data structures into one factor k that he calls coherence. Unfortunately, Gunther himself provides little help in telling us how to estimate k, the crucial coherency delay factor, beforehand, or measure it after the fact. Presumably, k includes delays associated with accessing critical sections of code that are protected by shared locks, as well as instruction execution delays in the hardware associated with maintaining the “coherence” of shared data kept in processor caches that are accessed and updated by concurrently running threads. There are also additional “overheads” associated with spinning up multiple worker threads, queuing up work items for them to process, controlling their execution, and coordinating their ultimate completion that are new to the parallel processing environment that are all absent from the serial version of the same program.

As a practical developer trying to understand the behavior of my parallel application, personally, I would find Gunther’s formula much more useful if it helped me identify the sources of coherency delays my parallel programs encounter that are impacting its scalability. It would also be useful if Gunther’s insight could help me guided me as I work to try to eliminate or reduce these obstacles to scalability. That is the main subject of the next blog entry in this series.

Parallel Scalability Isn’t Child’s Play

Mark B Friedman — Mon, 16 Mar 2009 20:39:00 GMT

In a recent blog entry, Dr. Neil Gunther, a colleague from the Computer Measurement Group (CMG), warned about unrealistic expectations being raised with regard to the performance of parallel programs on current multi-core hardware. Neil’s blog entry highlighted a dismal parallel programming experience publicized in a recent press release from the Sandia Labs in Albuquerque, New Mexico. Sandia Labs is a research facility operated by the U.S. Department of Energy.

According to the press release, scientists at Sandia Labs

simulated key algorithms for deriving knowledge from large data sets. The simulations show a significant increase in speed going from two to four multicores, but an insignificant increase from four to eight multicores. Exceeding eight multicores causes a decrease in speed. Sixteen multicores perform barely as well as two, and after that, a steep decline is registered as more cores are added.” They concluded that this retrograde speed-up was due to deficiencies in “memory bandwidth as well as contention between processors over the memory bus available to each processor.

Holy cow. The Lab’s scientists, who are heavily invested in parallel programming on supercomputers, simulated running programs on sixteen cores encapsulating “key algorithms for deriving knowledge from large data sets” that gave no better performance than running the same program on two cores.

Please note that these are simulated performance results, because 16-core machines of the type being simulated don’t currently exist. Indeed, I would not expect that 16-core machines of the type being simulated would ever exist. Which leads me to wonder what the point of this Sandia Labs exercise was.

Of course, for developers experienced in parallel programming, this result actually isn’t in itself all that surprising. Quite frequently, experienced developers find that running their multi-threaded application on massively parallel hardware does not scale well with the hardware capabilities. This was apparently the case for the applications the Sandia Labs folks simulated. So what? Should we just give up in our quest for parallel program scalability?

Before drilling into Dr. Gunther’s specific interest in this disclosure, it is worth looking into the Sandia Labs finding in a bit more detail. For instance, did anyone, besides me, wonder what applications were being simulated?

In theory, “deriving knowledge from large data sets” is a category of computing program that readily lends itself to a solution using an SIMD (Single Instruction, Multiple Data) approach. The canonical example of an SIMD approach to “deriving knowledge from large data sets” is a database Search function conducted in parallel where the data set of interest is partitioned across n processing units and their locally attached disks. For example, when the Thinking Machines CM-1 supercomputer publicly debuted in the mid-80s, the company demonstrated its capabilities using a parallel search of a database that was partitioned across all 64K nodes of the machine, which was based on the Connection Machine originally designed by MIT whiz kid Danny Hillis. Parallel search when executed across a partitioned dataset should scale linearly, or close enough for government work (pun intended).

Whenever a problem lends itself to an SIMD approach (also known as “divide and conquer”), linear scalability of the SIMD algorithm does require first partitioning the data being accessed and then proceeding to process that data in parallel. I am sure the point of the Sandia Labs press release was not to disparage the SIMD approach to parallel processing; after all, that is a tried-and-true technique that they have used with great success over the years.

On the contrary, it appears to be a critique of an approach to building parallel processing hardware where you would increase the number of processing cores on the chip (just because you can with the most current semiconductor fabrication technology) without scaling the memory bandwidth proportionally. Since that is not what is happening hardware-wise, it strikes me that this implied criticism of the multi-core hardware strategy Intel and AMD are pursuing is slaying a non-existent dragon. Both Intel and AMD recognize that memory bus bandwidth is a significant potential bottleneck in their multi-core products, and, as a result, both manufacturers are attempting to scale memory bandwidth proportional to the amount of processing power they deliver on a chip.

So then what is all the fuss about? The Sandia Labs “news” starts to look like something the blogosphere is latching onto on an otherwise slow day for tech news, raising an alarm & potentially misleading naïve readers about what the conventional wisdom in multiprocessor chip architecture would be if anyone were actually trying to build multi-core microprocessors that way.

Building a better multicore processor.

The point of the Sandia Labs press release publicizing these simulation results appears to be to suggest what they consider better approaches to packaging multi-core processors on a single socket. They released the following chart that that makes this point (reproduced here in Figure 1):

Figure 1. Sandia Labs simulation showing performance of their application vs. the number of processors.

Exactly what the Sandia Labs folks are reporting here is a little sketchy. Presumably, the simulations are based on observing the behavior of some of their key programs where they were able to measure performance running on “conventional” multi-core processors, perhaps, something like the quad-core machine I recently installed for my desktop that uses a memory bus with bandwidth in the range of 10 GB/sec. The press release seems to imply that the Sandia Labs baseline measurements were taken on current quad-core machines from Intel like mine, not the newer Nehalem processors where the memory architecture has been re-worked extensively. How useful or meaningful the results that Sandia Labs published may turn on this crucial point.

This Sandia Labs simulation then extrapolates out to 16 cores per socket (and beyond), simulating the manufacturer adding more cores to the die, apparently leaving the memory architecture fundamentally unchanged as they moved to more cores. The Sandia Labs chart in Figure 1 is labeled to indicate that the memory bandwidth was held constant at 10 GB/sec.

This is more than a little suspicious. Hardware manufacturers like Intel and AMD understand clearly that the memory bus has to scale with the number of processors. The AMD HyperTransport bus architecture is quite explicit about this, and the latest spec for HyperTransport version 3.1 has an aggregate bandwidth in excess of 50 GB/sec.

Meanwhile, the memory bus capacity on the latest Nehalem-class processors from Intel has been boosted significantly. Alternatively, it is when you cannot scale the memory bus with processor capacity that machines with NUMA architectures become more attractive. The AMD processors use HyperTransport links in a ring topology that implicitly leads to NUMA-characteristics.

In Intel’s approach to NUMA scalability, some small number of processors share a common memory bus, forming a node. Current Nehalem machines (also known as the Core i7 architecture) have four cores sharing the Front-side memory bus (FSB). The physical layout of this chip is photographed in Figure 2, showing four cores, connected to DDR3 DRAM using an integrated memory controller. I wasn’t able to come find a speed rating for the FSB in the Nehalem on Intel’s web site or elsewhere, other than ballpark estimates that puts its speed in the range of 30-40 GB/sec. The QuickConnect technology links that are used to link memory controllers support 25 GB/sec transfers, which is probably a safe lower bound on the capacity of the FSB.

Figure 2. Aerial photograph showing the layout of the 4-way Core i7 (Nehalem) microprocessor chip.

The PIM architecture, whose scalability curves are close to ideal for the Sandia Labs workloads is, probably not coincidentally, a processor architecture championed at Sandia Labs. The idea behind PIM machines (Processor In Memory) is that the processor (or processors) is embedded into the memory chip itself, which is a pretty interest approach to solving the “memory wall” that limits performance in today’s dominant computer architectures. Instead of loading up the microprocessor socket with more and more cores, which is the professed hardware roadmap at Intel & AMD, integrating memory into the socket is an intriguing alternative. Such machines, if anyone were to build them, would obviously have NUMA performance characteristics.

The debate is a bit academic for my taste, however, until these PIM architecture machines are a reality. For PIM architecture machines to ever get traction, either the microprocessor manufacturers would have to start building DRAM chips or the DRAM manufacturers would have to start building microprocessors. The way the semiconductor fabrication business is stratified today, that does not appear to be very likely in the near future.

So, in the end, the point of the Sandia Labs press release appears to be trying to publicize the multiprocessor hardware direction espoused mainly by Sandia Labs’ own researchers. Frankly, there have been lots and lots of different architectural approaches to parallel processing over the years, and it doesn’t look like any one approach is optimal for all computing situations. You ought to be pick another parallel programming workload to simulate in Figure 1 and get an entirely different ranking of the approaches.

Still, the Sandia Labs simulation data are interesting mainly for they say about how difficult it is going to be for developers to write parallel programs that scale well on multi-core machines. No, achieving parallel isn’t child’s play for hardware manufacturers. Nor is it for software developers attempting to take advantage of parallel processing hardware, which is the subject I will start to drill into next time.

Continue to Part 2.....

Visual Studio 2010 Hardware Requirements

David Berg — Wed, 24 Dec 2008 10:56:00 GMT

Soma’s been talking about the upcoming Visual Studio 2010 release on his blog, which means I’m starting to get questions about what type of hardware you’re going to need to run VS2010 on.

Unfortunately, I can’t give you an official answer yet (other than to say, it depends on what you’re doing – obviously building small apps with one of the Express versions of Visual Studio won’t require the same resources as a multi-million line app using full blown Visual Studio Team System with lots of third party add-ins).

What I can do is help put some of the things we’ve said about Visual Studio 2010 into context, to maybe help you make some better hardware decisions today:

1) Memory – we’re trying to make VS2010 as frugal as we can here in order to run in as little memory as possible; however, we’re also adding a lot of functionality, and systems with more memory do tend to perform much better. So the general rule of buying systems still applies – spring for as much memory as you can afford. It’s hard to have too much memory, at a minimum you want to make sure that you’re not paging. That said, there’s very little benefit to making a text editor 64 bit (and lots of reasons not to), so anything over 4GB is likely to be wasted (unless you’re running or writing apps that need more).

2) CPU – modern CPUs with their larger caches and tuned instruction pipelines tend to perform much better than one’s from just a few years ago (see our blog). If you’re going to do multi-threaded programming, you’ll want at least a dual core processor (and with the new Parallel Computing support in VS 2010, you will want to do multi-threaded programming).

3) GPU – VS2010 will leverage WPF heavily to create richer editing and visualizations, so a decent GPU that supports at least DX9 is highly recommended (DX10 is preferred, but requires Vista).

4) Disk – If you’re building a large project or working with a large database, a large high-speed disk is pretty important. For large projects, you can often benefit by spreading your work across multiple disk spindles. At an extreme, putting your tools on one drive, your source code on another, and your object files on a third drive allows the three major sources of disk IO in building a project to be carried out independently of each other. If you have to use a slower disk (e.g. a notebook) then be sure to get lots of memory. Also keep in mind that modern hard drives tend to have more built in caching, so the same speed drive bought recently will likely outperform one bought a few years ago.

So now that I’ve given you my thoughts on what hardware Visual Studio 2010 will need, what are your thoughts? What kind of hardware are you developing on today, and what do you expect to be using in the next couple years? What are your expectations on how we should be leveraging your hardware to create a productive development environment?

PDC2008 preConference Workshop

Mark B Friedman — Wed, 22 Oct 2008 18:36:00 GMT

Over the past several weeks, I have been working overtime developing a presentation on web application performance to be given at the upcoming Professional Developer’s Conference (PDC), which is next week in Los Angeles. This is partly why I have been remiss about blogging this month. At least, that is my excuse, and I am sticking to it.

The presentation is entitled “Performance by design using the .NET Framework” and I am presenting jointly with two colleagues in the Developer Division, Rico Mariani and Vance Morrison. It is one of ten PreConference sessions that are scheduled to run all day on Sunday. My portion of the session is an extended discussion of optimization & scaling strategies for web applications. The scope encompasses ASP.NET, AJAX, Silverlight, WPF & WCF. Information about the upcoming event is here.

I have attended several PDCs in the past as a customer, and found them to be amazing events. Before the days of widespread blogging, the “Ask the Experts” sessions at the PDC were often the only way to get an authoritative answer to your question. The actual Conference sessions emphasize imminently arriving technology and future directions, aimed at the professional developer who needs to be able to anticipate and plan. The technical sessions run the gamut from Windows 7, the Windows Live Cloud computing initiatives, IE8, Surface and Windows for Workflow. There will be previews of the next version of the .NET Framework, Visual Studio, and the Visual Studio Team System.

This is the first time I will be on the other side of the podium for the event. In our preCon session, Rico, Vance and I will focus on facilities available in the Framework today, including the best practices and tools we recommend to help you design & build an application that meets its performance and scalability requirements. The intended audience is experienced .NET developers.

If you are reading this blog & coming to my session, be sure to say hello. I’d like to get the chance to meet you in person.

-- Mark Friedman

Mainstream NUMA and the TCP/IP stack: Final Thoughts

Mark B Friedman — Fri, 19 Sep 2008 00:18:00 GMT

This is a continuation of Part IV of this article posted here.

Note that a final version of a white paper tying this series of five blog entries together (and a Powerpoint presentation on the subject) are attached.

For many years, the effort to improve network performance on Windows and other platforms focused on reducing the host processing requirements associated with the need to service frequent interrupts from the NIC. In the many-core era where the clock speeds of processors are constrained by power considerations, this strategy is inadequate to the growing host processing requirements that accompany high-speed networking. It is necessary to augment technologies like interrupt moderation and TCP Offload Engine that improve the efficiency of network I/O with an approach that allows TCP/IP Receive packets to be processed in parallel across multiple CPUs. Together, MSI-X and RSS are technologies that enable host processing of TCP/IP packets to scale in the many-core world, albeit not without some compromises with the prevailing model of networking using isolated, layered components.

Using MSI-X and RSS, for example, the Intel 82598 10 Gigabit Ethernet Controller mentioned earlier can be mapped to a maximum of 16 processor cores that could then be devoted to networking I/O interrupt handling. Capacity-wise, this is still not sufficient processing capacity to handle the theoretical maximum load equation 3 predicts for a 10 Gb Ethernet card, but it does represent a substantial scalability improvement.

With this understanding of what MSI-X and RSS accomplishes, let’s return for a moment to our NUMA server machine shown in Figure 6 below.

With MSI-X and Receive-Side Scaling, CPU 0 on node A and CPU 1 on node B are both enabled for processing network interrupts. Since RSS schedules the NDIS DPC to run on the same processor as the ISR, even at moderate networking loads, CPU 0 and 1 for all practical purposes become dedicated to the processing of high priority networking interrupts.

Numerous economies of scale accrue using this approach. The same RSS process that sends all Receive packets from a single TCP connection to a specific CPU for processing improves the efficiency of that processing. The instruction execution rate of the TCP/IP protocol stack is enhanced significantly through this scheduling mechanism that enforces localization. Ultimately, TCP/IP application data buffers need to be allocated from local node memory and processed by threads confined to that node. Recently used data and instructions that networking ISRs and DPCs issue tend to reside in the dedicated cache (or caches) associated with the processor devoted to network I/O. Or, at the very least, they migrate to the last level cache that is shared by all the processors on the same NUMA node.

Ultimately, of course, the TCP layer hands data from the network I/O to an application layer that is ready to receive and process it. The implications of RSS for the application threads that process TCP receive packets and build responses for TCP/IP to send back to network clients ought to be obvious, but I will spell them out anyway. For optimal performance, these application processing threads also need to be directed to run on the same NUMA node where the TCP Receive packet was processed. This localization of the application’s threads should, of course, be subject to other load balancing considerations to prevent the ideal node from becoming severely over-committed while other CPUs on other nodes are idling or under-utilized. The performance penalty for an application thread that must run on a different node than the one that processed the original TCP/IP Receive packet is considerable because it must access the data payload of the request remotely. Networked applications need to understand these performance and capacity considerations and schedule their threads accordingly to balance the work across NUMA nodes optimally.

Consider the ASP.NET application threads that process incoming HTTP Requests and generate HTTP Response messages. If the HTTP Request packet is processed by CPU 0 on node A in a NUMA machine, the Request packet payload is allocated in node A local memory. The ASP.NET application thread running in User mode that processes that incoming HTTP Request will run much more efficiently if it is scheduled to run on one of the other processors on node A, where it can access the payload and build the Response message using local node memory.

There is currently no mechanism in Windows today for kernel mode drivers like ndis.sys and http.sys to communicate to the application layers above them and specify the NUMA node on which that packet was originally processed. Communicating that information to the application layer is another grievous violation of the principle of isolation in the network protocol stack, but it is a necessary step to improve the performance of networking applications in the many-core era where even moderately sized server machines have NUMA characteristics.

Links.

Herb Sutter, “The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software.” Dr. Dobb’s Journal, March 1, 2005. http://www.ddj.com/architect/184405990

NTttcp performance testing tool: http://www.microsoft.com/whdc/device/network/TCP_tool.mspx

Windows Performance Toolkit (WPT, aka xperf): http://msdn.microsoft.com/en-us/library/cc305218.aspx

David Kanter, “The Common System Interface: Intel's Future Interconnect,” http://www.realworldtech.com/includes/templates/articles.cfm?ArticleID=RWT082807020032&mode=print

Windows NUMA support: http://msdn.microsoft.com/en-us/library/aa363804.aspx

Intel white paper: Accelerating High-Speed Networking with Intel® I/O Acceleration Technology

Mark B. Friedman, “An Introduction to SAN Capacity Planning,” Proceedings, Computer Measurement Group, Dec. 2001.

Jeffrey Mogul’s “TCP offload is a dumb idea whose time has come,” Proceedings of the 9th conference on Hot Topics in Operating Systems - Volume 9, 2003. http://portal.acm.org/citation.cfm?id=1251059&dl=ACM&coll=portal&CFID=71988909&CFTOKEN=98964748

Dell Computer Corporation, “Boosting Data Transfer with TCP Offload Engine Technology.”

Microsoft Corporation, KB 951037, http://support.microsoft.com/kb/951037

Microsoft Corporation, Windows Driver Development Kit (DDK) documentation, http://msdn.microsoft.com/en-us/library/cc264906.aspx

Microsoft Corporation, KB 927168, http://support.microsoft.com/kb/927168

Microsoft Corporation, NDIS 6.0 Receive-Side Scaling documentation, http://msdn.microsoft.com/en-us/library/ms795609.aspx

Mainstream NUMA and the TCP/IP stack, Part IV: Parallelizing TCP/IP

Mark B Friedman — Tue, 09 Sep 2008 02:35:00 GMT

This is a continuation of Part III of this article posted here.

In the many-core era, the host processor overhead associated with processing TCP/IP interrupts is not a capacity problem, since CPU cycles on the host computer are plentiful and becoming more plentiful all the time. The problem is that the individual processors themselves are not fast enough, nor are they growing much faster. To craft a solution that works in the many-core era, there is a clear need to enhance the hardware and software in the TCP/IP protocol stack to run in parallel across multiple processors and take advantage of the available capacity. There are two hardware and software technologies that are associated with that capability today:

· Extended Message-Signaled Interrupts (MSI-X): a hardware technology that allows the NIC to support multiple interrupt vectors, enabling multiple processor cores to handle interrupts from the NIC simultaneously.

· Receive-Side Scaling (RSS): the protocol used in the NDIS driver software to manage multiple interrupt vectors and communicate to the hardware to ensure that session-oriented TCP packets are delivered in sequence to a processor-specific interrupt queue.

MSI-X and RSS work together to allow the processing of TCP/IP Receive packets to scale in parallel across multiple processor cores

Message Signaled Interrupts (MSI-X). MSI-X is an architectural change that allows a device to send interrupts to be processed on multiple CPUs. Historically, on the Intel architecture, devices were limited to sending interrupts to a single target. Concentrating all hardware interrupts on a single processor boosts the instruction execution rate of the Interrupt Service Routine (ISR) by increasing the chances of a processor cache warm start. In the many-core era, limiting the device to one processor that it can interrupt is a severe capacity constraint. MSI-X capabilities allow the NICs to scale on many-core processors.

One key feature of Windows’ support for MSI-X devices is the ability to specify a policy that automatically assigns MSI-X interrupts to CPUs based on the OS’s understanding of the underlying NUMA topology of the machine. An NDIS-driver that supports MSI-X devices can specify an IrqPolicySpreadMessagesAcrossAllProcessors policy that automatically distributes interrupts across an optimal set of eligible processors. On some NUMA machines, the performance of the device connection is affected by the underlying topology of the multi-node connections. For instance, certain device-to-processor node connections may be low latency local ones, while others are higher latency remote connections. For performance reasons, you want NIC interrupts to be processed on nodes that are connected locally and access local memory on that node exclusively. For optimal scalability, you then want to balance device interrupts across all the NUMA nodes that are interconnected. The IrqPolicySpreadMessagesAcrossAllProcessors policy understands these performance considerations, and distributes the device interrupts to the right set of processors automatically.

Figure 6 illustrates one way the IrqPolicySpreadMessagesAcrossAllProcessors policy could be used to distribute interrupts from the NIC across nodes in a simple NUMA machine. A server with two quad-core sockets is shown, with each socket connected to a block of local RAM. Memory accesses from a processor core to local RAM are considerably faster than an access to remote memory attached via a bridge to the other multi-core socket. An optimal configuration is to process TCP/IP interrupts on CPU 0 on the first node and on CPU 1 on the second node, as depicted, balancing the networking I/O load across nodes.

Figure 6. Two NUMA nodes in a Windows Server machine configured to use MSI-X and RSS to process TCP/IP Receive packets across multiple processors.

While Receive-Side Scaling (RSS) does not require MSI-X, the two technologies normally go hand-in-hand. We restrict the RSS discussion here to the manner in which MSI-X devices are supported, which is both the simplest and most common case.

Receive-Side Scaling (RSS). RSS complements the Windows support for MSI-X. It allows the workload associated with processing network interrupts to be spread across multiple CPUs. With RSS, the DPC routine that we have seen is responsible for performing the bulk of the host processing is also scheduled to run on the same CPU where the interrupt service routine (ISR) just ran. Concentrating all the work associated with network interrupt processing on the same CPU improves instruction execution rates because data associated with the packet is likely to remain in the processor caches. It also dramatically reduces delays spent in unproductive spin lock code associated with serialization. Optimistic, non-blocking per processor locking strategies are effective under these circumstances. By default under RSS, even the Send processing associated with an ACK message is also processed on the same CPU where the Receive was processed to take advantage of the same performance considerations.

There is one complication, however, that arises when network interrupts are distributed across multiple CPUs that RSS is forced to address. If packets are distributed randomly across multiple CPUs, this can conflict with the important function of the TCP protocol that guarantees delivery of data in sequence to the application. Suppose packets for a group of TCP connections are processed across two CPUs and one CPU in the bunch is lightly loaded while the other is heavily loaded. Older packets received on the lightly loaded CPU could easily be processed first. Receiving packets out of order in TCP triggers Fast Retransmits, for example, that could degrade both the network and delay the application, not to mention serialization delays before TCP can safely notify the application layer that Request data is available for processing.

Given this complication, RSS distributes connections, not individual packets. RSS has a mechanism that sends all the packets associated with any one TCP connection to the same processor. This preserves the order of delivery of received data packets, which avoids needless requests for TCP retransmits. Crucially, the processor associated with the specific connection must be communicated to the NIC, which must arrange Received packets into the correct message queues accordingly, prior to signaling the host processor by raising an interrupt. This coordination, of course, is another violation of the isolation principle of the layered networking stack. It is worth noting that nasty side effects can arise as a result of this willful violation of the layered networking architecture; see, for example, KB927168 documenting a conflict between RSS and Internet Connection Sharing on Vista that was later fixed in WS2008 and Vista SP1.

To achieve good performance, however, it is absolutely necessary for the NIC to schedule all the packets for the same TCP session to same host processor. It can only do that by peeking into the TCP header and finding the port indicator, which it then uses to calculate the right CPU to deliver the packet to. This calculation is based on a hash table that is passed to the NIC by the NDIS driver software. RSS even includes a capability to adjust the load across the CPUs that are enabled for processing NIC interrupts dynamically. The protocol stack in Windows can re-balance the interrupt load by modifying the hashing table passed to the NIC that is used in determining the proper CPU. This mechanism can be used in case some CPUs remain overloaded for an extended period of time because, for example, some TCP connections are more chatty and persistent than others.

Speaking of maintaining a balanced system, long-running tasks such as large file copies associated with a single ftp, SMB or media server session present inherent difficulties under RSS. The general problem is that the throughput of any one session is ultimately limited by host processor speed. With many-core processors, it is important to figure out how to use parallel data divide-and-conquer techniques to break long serial operations into smaller sub-tasks that can be executed concurrently. Providing the capability to spread long, data-intensive operations across multiple TCP sessions is one possible approach.

For further technical details on RSS, see http://msdn.microsoft.com/en-us/library/ms795609.aspx. One interesting aspect of the RSS specification is that the DPC, not the ISR, is responsible for re-enabling the processor for more interrupts from the NIC. This prevents the NIC from sending any more Receive packets to the processor until the previous set has been completely processed. This effectively acts as both a serialization mechanism and a form of interrupt moderation that adaptively adjusts the delay between interrupts based on the specific processing load at the CPU.

This blog entry is continued here.

Performance improvements in Service Pack 1 for VS 2008 and .NET FX 3.5

David Berg — Wed, 13 Aug 2008 14:31:00 GMT

We just announced the release of Service Pack 1 for VS 2008 and .NET FX 3.5. A major push for this release was continuing to enhance performance and reliability, as Soma noted in his most recent blog entry. I want to take a minute to drill into the major performance improvements you will find in this release of Visual Studio.

Framework Performance Enhancements

NET FX (CLR):

· New .NET Framework Client Profile - a smaller .NET Framework redist optimized for .NET client applications. The new redist weighs in at around 28 MB, enabling a smaller, faster, more reliable installation experience for .NET client applications on machines that do not already have the .NET Framework installed. The framework was refactored so that it now includes system core libraries and components (including LINQ), language support, XML, Windows Forms, WPF, Deployment, Web Services remoting and serialization, data access, and a few others. See the BCL Team blog for the full list and more details.

· Client applications should also see an improvement in cold startup scenarios especially for rich graphics WPF-based apps.We also made improvements to the working set of Ngen’d images, which also helps cold startup scenarios .

· Support for Address Space Layout Randomization (ASLR) on Vista and WS 2008. ASLR uses fast kernel mode virtual base address relocation to improve both memory layout and security.

WPF:

· Cold startup up to 40% faster, depending on the scenario and application size, without the need to modify any of your code.

· Additional support for text and graphics to deliver better performance. For example, effects like DropShadow and Blur were initially implemented using software rendering; with SP1 these are now implemented using hardware acceleration.

· Faster text rendering, mostly when used in specific scenarios such as VisualBrushes, DrawingBrushes, and Viewport2DVisual3D.

· Scrolling improvements with Container Recycling.

· Improved working set using TreeView virtualization

· A much improved WriteableBitmap that enables real-time bitmap updates from a software surface.

Jossef Goldberg’s blog is a great source of information on WPF performance tips and tricks. His detailed list of SP1 performance improvements is posted here.

WCF:

· Support for asynchronous HTTP module/handlers on IIS 7.0. Supports better thread management and improved throughput for systems with heavy backend processing requirements. (See Wenlong’s blog for the technical details.)

Windows Forms:

· General performance improvements, mostly due to underlying improvements in the CLR.

Data handling:

· Improved throughput in ADO.NET scenarios (2x+ requests/second for some scenarios).

· Performance improvements in XLINQ over XML containing many small elements.

Visual Studio Performance Enhancements

Visual Web Developer:

· Improved typing performance in the designer in complex pages (especially with MutiView control) 100x

· Fixed the issues with Switching to Design View.

· Opening Web Sites is up to 10x faster!

· Building Web Sites is up to 3x faster!

· Opening Web Forms is up to 2x faster!

· General performance improvements in startup and shutdown.

· Plus lots of new features and fixes (see the team blog).

Visual Basic .NET:

· Performance improvements in Intellisense and listing errors.

· Improvements in compiler and build throughput (most notably for projects with large amounts of XML comments in a single file)

Visual C#:

· Up to 2x improvements in bringing up Intellisense with a large number of types.

XAML Editing:

· Improved designer startup and form load time.

Debugging:

· Improvements in symbol and source downloading and the ability to cancel out of symbol download from a slow symbol server.

· Fix to a performance problem in the debugger when you are stepping through source code that is downloaded from Microsoft Reference Source Server that was caused by downloading the source files again for each breakpoint. Previously released as KB944899. (Please uninstall this KB before installing the SP.)

XML Editing:

· Loading XML is up to 3x faster!

· Improved editing performance.

Team Foundation Server:

In this Service Pack, a large part of the focus was to improve the performance and scalability of Team Foundation Server. Key changes include faster synchronization with Active Directory, improved check-in concurrency, a faster way to create source tree branches, online index rebuilding for less maintenance downtime and better support for checking very large sets of code.

TFS improved the number of projects a server can support. You should experience better scalability of the server, as well as the client experience when connecting to a server with a large number of projects on it.

· Opening Source Controlled Solutions is up to 2.5x faster!

· Deleting files is up to 2x faster!

· Improved Work Item performance (loading, saving, querying).

· Improved UI navigation performance.

· Improved performance working with TFS work items in Excel and Project

· Improved performance and reliability of the Visual SourceSafe migration tool.

· See Brian Harry’s BLOG for more about the Service Pack Release and Team Foundation Server improvements and scalability.

Other:

And, of course, there are lots of new features including the new Data Entity Framework, ADO.NET data services, support for SQL Server 2008’s new features, updated components for Visual Basic and Visual C++ (including a MFC-based Office 2007 Ribbon), and new designer capabilities that improve performance indirectly by improving developer productivity.

Some of these performance fixes were previously released as hot fixes (see our blog on the beta). If you installed some of those hot fixes you may need to remove them before installing the Service Patch. See the release notes on the download page for more information.

Should you encounter any performance problems we’ve missed, please continue to let us know here on the blog or by e-mail to devperf@Microsoft.com.

Mainstream NUMA and the TCP/IP stack, Part III: A look back at older strategies to scale high-speed networking

Mark B Friedman — Wed, 06 Aug 2008 02:04:00 GMT

This is a continuation of Part II of this article posted here.

By necessity, both the hardware and the software devoted to processing network traffic need to evolve in the many-core era to become multiprocessor-oriented. On servers that have NUMA architectures, that multiprocessing support needs to acquire a NUMA flavoring. The technology that allows network interrupts to be processed concurrently across multiple processors includes support for

· multiple Descriptor Queues in the networking hardware,

· Extended Message Signaled Interrupts (MSI-X) to allow hardware interrupts to be serviced concurrently on more than one processor, and

· the software support in Windows known as Receive-Side Scaling (or RSS).

With ccNUMA architecture machines becoming more mainstream, it is clear that multi-processor support should also include being NUMA-aware.

For an idea of how fast the NICs are getting, a typical 1 Gb Ethernet card supports 4 transmit and 4 receive interrupt queues and can spread interrupts across as many as 4 host processors for load balancing under RSS. A 10 Gb Ethernet card necessarily supports even high levels of parallelism. For example, the dual-ported Intel 82598 10 Gigabit Ethernet Controller provides 32 transmit queues and 64 receive queues per port, which can be mapped to a maximum of 16 processor cores. Note that this increase in parallel processing capacity is only a 4x improvement over recent 1 Gb Ethernet cards, which is probably inadequate to exploit the increased bandwidth fully.

Let’s consider briefly some of the ideas to improve TCP/IP performance that have been implemented in the recent past. The strategies discussed here either increase the efficiency of host computer processing of TCP/IP packets or attempt to off load some of these software functions onto networking hardware. These strategies have proven effective, but they do not offer enough capacity relief to keep pace with the steady advance of networking speeds. The way out of the current mismatch between high speed networks and the host processing requirements they generate is a parallel processing approach where TCP/IP interrupts are distributed across multiple CPUs.

Interestingly, some of the changes outlined here to streamline TCP/IP host processing fly in the face of a major precedent. The layered architecture of the networking stack is widely regarded as one of the storied accomplishments of software engineering. Several of the efforts to improve the performance of host processing of TCP/IP interrupts involve shattering the strict isolation of components that the layered networking model advocates.

In theory, at least, the layered approach simplifies complex software that is designed to function smoothly in diverse environments. Layering also supports development of components that can proceed independently and in parallel. In principle, each layer defines and adheres to a standard set of services, or interfaces, that it provides to the component in the layer immediately above it. An upper layer communicates with a level below it using only this predefined set of abstract interfaces. (The set of services provided and consumed by two adjacent layers, in effect, defines a contract.) Furthermore, in the design of the networking protocol, components are isolated. It is an article of faith among software engineers that layered architectures, when properly defined and implemented, greatly contribute to the robustness and reliability of the software built using those design principles.

TCP/IP Layers
Data unit	Layer	Function	Example
Data	5. Application	Application-specific	HTTP, SMTP, RPC, SOAP, etc.
Segment	4. Transport	End-to-end connections (sessions) and reliable delivery	TCP/ UDP
Packet/Datagram	3. Network	Logical addressing and routing; segmentation & re-assembly	IP
Frame	2. Data link	Physical addressing (MAC)	Ethernet, ATM
Bit	1. Physical	Media, signal and binary transmission	Optical fiber, coax, twisted pair

Table 4. The TCP/IP layered networking model.

Table 4 is a standard representation of the layered networking model used in TCP/IP, which has gained almost universal acceptance in computer-computer communications. Take the ubiquitous IP layer, for instance. IP implements a Best Effort service model to deliver packets from one station to another using routing. By design, it is connectionless, session-less and unreliable. Delivery of packets to the correct destination is not guaranteed, but IP does take a “best effort” approach to accomplish this. For the applications that require these services, the higher-level TCP Host protocol guarantees that packets are delivered reliably and in order to the designated application layer above it. It does this using a session-oriented protocol that preserves the state of the messaging-passing session between packets. TCP has also evolved complicated, performance-oriented flow and congestion control mechanisms that are beyond the scope of the current discussion.

The layering approach to networking introduces one additional and crucial design constraint. When one station is transferring a message to another, only components at the same level in the protocol stack can exchange data and communicate with each other. For example, only the TCP component in the receiver is supposed to be able to understand and process information placed into the TCP packet header by the sender. However, both the TCP Offload Engine and Receive-Side Scaling utilize knowledge of what is going on the upper layer TCP protocol down in the Data Link (or MAC) layer in the receiver, a serious violation of the principle that the layers in the protocol stack remain totally isolated from each other. Apparently, this is a case where the serious performance issues trump the pure design principles, and the evolution of TCP/IP has always been sensitive to practical issues of scaling. It is not that you absolutely cannot violate the contract that governs the ways layers communicate, but it is something that should be done very thoughtfully so that your once clean interfaces don’t start to look like swiss cheese.

A crucial factor that works to encourage breaking with precedent is that the protocols from the TCP layer down to the hardware all adhere very strictly to the standards in order to promote interoperability. This strict compliance has the effect of hardening the services and interfaces between these layers in cement. This rigidity actually reduces the risk of side effects when a lower level component presumptuously usurps a service that architecturally is defined as the responsibility of some higher level.

Another factor is also at work. Within a layer, components that conform to the same contract layer can, in theory, be freely substituted for each other. This principle of the layered approach is supposed to promote development of a profusion of components that implement different sets of services, but still adhere to the strict requirements of the standard. In fact, the need for interoperability severely limits the proliferation of components that can be freely substituted for each other. Ethernet is almost always the hardware used at the bottom of the stack due to its superior cost/performance. Ethernet is always followed by IP, which is then usually followed by TCP. UDP can be freely substituted for TCP at the host processing layer, but only when the TCP services that ensure reliable delivery of packets and flow control can be dispensed with. In practice, there is very little variety among the components you will see operating in every networking protocol stack. TCP/IP over Ethernet, being ubiquitous, achieves the highest possible degree of interconnectivity and interoperability.

With the TCP/IP stack so pervasive and so stable and dominant, it then becomes possible to think the unthinkable. It becomes difficult to resist the temptation to violate the principle of isolation if you can demonstrate a big enough performance win. Having the Ethernet layer peek into the TCP packet headers and optimize their processing is acceptable when the violation of this sacrosanct principle of layering yields sufficient performance or scalability improvements.

Recent performance improvements to TCP/IP host processing.

Before we drill into the current set of architectural changes to the networking stack, let’s explore briefly some of the more successful strategies for reducing the host computer processing requirements associated with TCP/IP interrupt processing that have been explored in the past. Stateless processing associated with the IP layer were some the earliest functions identified that could be performed on the NIC and eliminate some amount of host processing. These offloaded functions include Checksum and segmentation for large Sends, both of which were supported in the Windows 2000 timeframe. Because the IP protocol is stateless and connectionless, there are virtually no side effects to performing these functions on the NIC, even if it does violate the principle of strict isolation between layers in the protocol stack.

Another set of performance improvements that have been implemented recently do potentially generate serious side effects that must be handled rather delicately. These include:

· interrupt moderation

· jumbo frames

· TCP Offload engine (TOE)

We will drill into these three approaches next, discussing some of the potential side effects, performance trade-offs, and other issues they raise. It is probably also worthwhile to mention netDMA, which is the Windows support for Intel’s I/O Acceleration Technology (I/OAT), in this context. I/OAT makes targeted improvements in the processor memory architecture to improve the efficiency of NIC-to-memory transfers.

Each of these approaches has worked to a degree, but none has produced enough of a breakthrough in performance to address the underlying condition, the growing mismatch between host processing requirements and network bandwidth.

As noted earlier, the CPU load associated with the processing Ethernet packets with TCP/IP at a server is a long-standing and persistent performance problem that has escaped a satisfactory solution in the past. For many years, the thrust of conventional solutions to the problem was straightforward – namely, any means possible for reducing the number of interrupts that the host computer needs to process. Two of the more effective approaches to reducing the number of interrupts are to use some form of interrupt moderation or so-called jumbo frames, basically larger packets than the Ethernet standard supports. Both approaches are effective to a degree, but also have serious built-in limitations and drawbacks.

Interrupt moderation on the NIC is widely used today to reduce the host interrupt processing rate. It is successful, but only to the extent of addressing the processing load associated with each interrupt, which, as indicated in the protocol overhead measurements discussed earlier, is relatively minor. A NIC that supports interrupt moderation can delay the host interrupt for up to a specified period of time with the hope that the NIC will receive additional networks packets to process during the delay. Then, instead of each packet causing an interrupt, the host processor can process multiple packets in a single interrupt. In the measurements reported in Part 1, interrupt moderation was used to cut the host processor interrupt rate in half. When you consider as we have earlier, the potential rate of networks interrupts that a 10Gb Ethernet card can drive, some form of interrupt moderation on the NIC becomes essential for the smooth operation of the host processor.

Interrupt moderation helps, but not enough to relieve the bottleneck at the host CPU. The host processing associated with the TCP/IP protocol appears to scale as a function of both the number of interrupts and the amount of data being transferred between the NIC and the host computer. As the average size of data payloads increases, the processing bottleneck shifts to memory latency. See, for example, the bottleneck analysis presented in the Intel white paper “Accelerating High-Speed Networking with Intel® I/O Acceleration Technology.”

Interrupt moderation should be used cautiously in situations where the fastest possible network latency is required, such as two communicating infrastructure servers connected to the same high-speed networking backbone. It also has to be implemented carefully to ensure it does not interfere with the TCP congestion control functions that try to measure round trip time (RTT).

Jumbo frames. Sending data across the wire in so-called jumbo frames also significantly reduces the number of host interrupts. And there is little question that the size of the Ethernet MTU is sub-optimal for many networking transmission workloads. Consider the relatively large data payloads that routinely need to be transferred between a back-end database machine and the clusters of front-end and middle tier machines in a typical clustered, multi-tier web service application today. Using jumbo frames of, say, 9K payloads on the high speed network backbone linking these servers leads to a 6:1 reduction in the number of host processor interrupts required to transfer sizable blocks of data. When servers are connected to a Storage Area Network (SAN) using iSCSI, even larger frames are desirable.

In fact, jumbo frames appears to be such a simple, effective solution within the confines of the data center that it naturally leads to consideration of what other aspects of the TCP/IP protocol that are sub-optimal in that environment could also be modified. For example, when there is frequent high speed communication between very reliable components, the TCP/IP requirement to acknowledge positively the receipt of every packet is overkill, and it very tempting to break with the standard and relax that requirement. The superior cost/performance of high speed Ethernet-based networking makes it very tempting to consider as an alternative interconnect technology to use with both SANs and High Performance Computing (HPC) clusters. In both these cases there are alternatives linkage technologies that outperform TCP/IP that are also considerably more expensive. For a further discussion of this issue in the context of SAN performance, see “An Introduction to SAN Capacity Planning.” And for the HPC flavor of this same discussion, see Jeffrey Mogul’s “TCP offload is a dumb idea whose time has come.”

Unfortunately, using non-standard jumbo frames introduces a significant compatibility problem that severely limits the effectiveness of the solution. The great majority of network clients will reject frames larger than the standard Ethernet MTU of 1500 bytes. In effect, you can send jumbo frames between specific host computers that are equipped to handle them on a dedicated backbone segment readily enough, but you cannot reliably send them to just any machine connected using the IP internetworking layer. So implementing jumbo frames requires more complicated routing schemes. TCP/IP RFC 2923 section 2.1, which is supported in Windows XP SP3, Vista, and Windows Server 2008, allows two TCP peers to negotiate the largest size MTU that can be transmitted between them. But the connectionless and stateless IP routing mechanism means that no single packet transmitted between station A and B need follow the same route twice. Given that the precise route to the destination station is dynamically constructed for each packet, any intermediate router that did not support jumbo frames would reject any non-standard packets it received and prevent successful transmission to the receiver.

TCP Offload Engine. A TCP Offload Engine (or TOE) is another solution that has been implemented to reduce the host processing required for TCP/IP interrupts. As the name suggests, in this approach, certain TCP/IP protocol functions are performed directly on the NIC, either reducing the amount of processing that must be performed in the host machine, or eliminating host interrupts associated with certain TCP/IP housekeeping operations entirely. Areas where significant performance gains are experienced with TOE include the elimination of expensive memory copy operations, offloading segmentation and reassembly (a function of the IP layer), and offloading some of the TCP housekeeping functions that ensure reliable connections (mainly, ACK processing and TCP retransmission timers). Moving these functions onto the NIC results in a reduction of the total number of interrupts that need to be processed by the host machine. Potential performance benefits associated with TOE are quantified here: “Boosting Data Transfer with TCP Offload Engine Technology.” You can see that the potential CPU savings are considerable.

TCP Offload Engine, however, is a grievous violation of the layered architecture of the networking protocol stack. The TCP Chimney Offload feature that provides TOE support in Windows, for example, required an extensive re-architecture of the TCP/IP stack. TOE introduces many breaking changes. See the KnowledgeBase article entitled ”Information about the TCP Chimney Offload feature in Windows Server 2008” detailing the many limitations, reflecting what networking functions can & can’t safely be offloaded in which computing environments. For instance, any networked machine that enforces an IPsec-based security policy where it is necessary to inspect each individual packet cannot use TOE. Neither is TOE currently compatible with either server virtualization technology or common forms of clustering based on virtual IP addresses.

The modest benefits in many environments and the complexities introduced due to explicit violations of the layered model of the network protocol argue against a general TOE solution. Another strong criticism of the TOE approach is that it merely moves the bottleneck from the host processor to the NIC. As RSS penetrates the market for high-speed networking, I believe that interest in the TOE approach will wane. If you do have a processing bottleneck on the host machine as a result of high-speed networking, with an RSS solution, at least, the bottleneck is visible, and there are inexpensive mechanisms to help deal with it. A processing bottleneck on the NIC is opaque and resists any capacity solution other than to swap in a more expensive card, assuming one exists, and hope that the new one is significantly faster and more powerful than the old one.

Intel I/OAT. Intel’s I/OAT introduces memory architecture improvements that give the NIC access to a dedicated DMA (direct memory access) engine for copying data between host memory and the NIC. These architectural changes are known as the Intel QuickData Technology DMA subsystem. With both interrupt moderation and the TCP Offload of IP segmentation and re-assembly, the processor tends to receive fewer interrupts to process, but each interrupt results in larger amounts of data that needs to be processed by the host. The networking protocol stack services the initial interrupt from the NIC and examines the Receive data block while it is running in kernel mode. Most data blocks associated with networking I/O subsequently need to be copied into the networking application’s private address space. A performance analysis showed that, especially with larger blocks of data, this second memory-to-memory copy operation was responsible for a very large portion of the host processor load. An Intel white paper here describes this analysis in some detail.

Ultimately, the result of this performance analysis was the set of I/OAT architectural improvements that permit this second memory-to-memory operation to be performed by a DMA provider engine (located on the Northbridge chip set currently) that requires no additional host processor bandwidth. The memory copy operation occupies the memory controller, but does not consume Front Side Bus bandwidth, which also frees up the host processor to perform other CPU tasks. Interestingly, Windows support for this technology, described in the Driver Development Kit (DDK) documentation, is actually very general, but to date the only netDMA client available is the tcpip.sys kernel mode driver that processes networking interrupts. It ought to be possible for disk I/O controllers to also exploit I/OAT architectural improvements sometime in the future. However, data blocks associated with disk I/O, which are cached by default in the system address space in Windows, are not necessarily subject to multiple copy operations, depending on the cache interface used.

Continue to Part IV.

Mainstream NUMA & the TCP/IP stack: Part 2: Programming ccNUMA machines

Mark B Friedman — Sun, 27 Jul 2008 21:02:00 GMT

This is a continuation of Part I of this article posted here.

In Part 1 of this article, we looked at the capacity issues that are driving architectural changes in the TCP/IP networking stack. While network interfaces are increasing in throughput capacity, processor speeds in the multi-core era are not keeping pace. Meanwhile, the TCP/IP protocol has grown in complexity so that host processing requirements are increasing, too. The only way for networked computers to scale in the multi-core era is to begin distributing networking I/O operations across multiple processors. Since bigger server machines rely on NUMA architectures for scalability, high speed networking is also evolving to exploit machines with NUMA architectures in an optimal fashion.

Machines with NUMA (non-uniform memory access speeds) architectures are usually large scale multiprocessors that are assembled using building blocks, or nodes, that each contain some number of CPUs, some amount of RAM, and various other peripheral connections. Nodes are often configured on separate boards, for example, or specific segments of a board. Multiple nodes are then interconnected with high speed links of some sort that permit all the memory that is configured to be available to executing programs. There are many schools of thought on what the best interconnection technology is. Some manufacturers favor tree structures, some favor directory schemes, some favor network-like routing. A key feature of the architecture is that the latency of a memory fetch depends on the physical location of the RAM being accessed. Accessing RAM attached to the local node is faster than a memory fetch to a remote location that is physically located on another node.

Within one of the new Intel Nehalem many-core microprocessor, for example, all the processor cores and their logical processors can access local memory at a uniform speed. Figure 3 is a schematic diagram depicting a 4-way Nehalem multiprocessor chip that is connected to a bank of RAM. The configuration of processors and RAM shown in Figure 3 is a building block that is used in creating a larger scale machine by connecting two or more of such nodes together.

Figure 3. A schematic diagram depicting a NUMA node showing locally-attached RAM and a multi-core socket.

A two-node NUMA server is illustrated in Figure 4, which shows a direct connection between the memory controller on node A and the memory controller on node B. This is the relatively simple case. A thread executing on node A can access any RAM location on either node, but an access to a local memory address is considerably faster. The latency to access to a remote memory location is several times slower. (Definitive timings are not available as of this writing because early versions of the hardware are just starting to become available.)

Figure 4. A two-NUMA server showing a cross-node link that is used when a thread on one node needs to access a remote memory location.

As the number of nodes increases, it is no longer feasible for every node to be directly connected to every other node, nor can each bank of RAM that is installed be accessed in a single hop. The specific technology used to link nodes may introduce additional variation in the cost of accessing remote memory. From any one node, it could take longer to access memory on some nodes than others. For instance, some nodes may be accessed in a single hop across a direct link, while other accesses may require multiple hops. Some manufacturers favor routing through a shared directory service, for example. Your mileage may vary.

Specifically, in the Intel architecture, manufacturers are supplying a cache coherent flavor of NUMA servers (ccNUMA). Cache coherence is implemented using a snooping protocol to ensure that threads executing on each NUMA node have access to the most current copy of the contents of the distributed memory. Details of the snooping protocol used in Intel ccNUMA machines are discussed here.

AMD has taken a somewhat different tack in building its multi-core processors. For communication on chip between processors, AMD uses a technology known as HyperTransport, which is a dedicated, per-processor 2-way high speed link. Multiple processors cores are then linked on the chip in a ring topology as depicted in Figure 5. The ring topology has the effect of scaling the bus bandwidth that is used as an interconnect linearly with the number of the processors. But the architecture leads to NUMA characteristics. A thread executing on CPU 0 can access a local memory location, a remote memory location that is local to CPU 1 at the cost of one hop across the HT link, or a remote memory location that is local to CPU 2 at the cost of two hops across HT links.

Figure 5. The AMD approach to multi-core processors has NUMA characteristics. A program executing on CPU 0 that accesses RAM that is local to CPU 2 requires two hops across the HyperTransport links that connect the processors in a ring.

Historically, application development for NUMA machines meant understanding the performance costs associated with accessing remote memory on a specific hardware platform. Since manufacturers employ different proprietary interconnection schemes in their multi-tiered NUMA machines, application developer are challenged to find the right balance in exploiting a specific proprietary architecture that may then limit the ability to port the application to a different platform in the future. It may be possible to connect nodes in a NUMA machine in an asymmetric configuration, for example, where the performance cost function associated with accessing different memory locations is decidedly irregular.

To scale well, a multi-threaded program running on a NUMA machine needs to be aware of the machine environment and understand which memory references are local to the node and which are remote. A thread that was running on one NUMA node that migrates to another node pays a heavy price every time it has to fetch results from remote memory locations. The difficulty programmers face when trying to develop a scalable, multi-threaded application for a NUMA architecture machine is understanding their memory usage pattern and how it maps to the NUMA topography. When NUMA considerations were confined to expensive, high-end supercomputers, the inherent complexities developers faced in programming them were considered relatively esoteric concerns. However, in the era of many-core processors, NUMA is poised to become a mainstream architecture.

In theory, it is possible to craft an optimal solution when threads and the memory they access are balanced across NUMA processing nodes. In order to achieve an optimal balancing of the machines resources without overloading any of them, programs need to understand the CPU and memory resources that individual tasks executing in parallel require and understand how to best map those resources to the topography of the machine. Then they require a suitable scheduling mechanism to achieve the desired result. Achieving an optimal balance, as a practical matter, is not easy, in the face of variability in the resources required by any of execution threads, a complication that may then require dynamic adjustments to the scheduling policy in effect.

The Windows OS is already NUMA-aware to a degree and, thus, supports a NUMA programming model. For example, once dispatched, threads have node affinity and tend to stay dispatched on an available processor within a node. Windows OS memory management is also NUMA-aware, maintaining per node allocation pools. The OS not only resists migrating threads to another node, it also tries to ensure that most memory allocated are satisfied locally using per node memory management data structures.

Windows also provides a number of NUMA-oriented APIs that applications can use to keep their threads from migrating off-node and also enable them to direct memory allocations to a specific physical processing node. For more information on the NUMA support in Windows, see the MSDN Help topic “NUMA Support.”

To help application developers deal better with the complexities of NUMA architectures in the future, the Windows NUMA support needs to evolve. One potential approach would be for the OS to attempt to calculate a performance cost function at start-up that it would then expose to driver and application programs when they start up and run. Conceivably, the OS might also need to adjust this performance cost function to response to configuration changes that occur dynamically, such as any power management event that affects memory latency. These changes would then have to be communicated to NUMA-aware drivers and applications somehow so they could adapt to changing conditions.

Continue to Part III of this article.

Lessons from the test lab: investigating a pleasant surprise

Jonathan Hardwick — Thu, 19 Jun 2008 00:33:20 GMT

This post describes our recent investigation into an interesting performance problem: benchmarks that we were surprised to find running significantly faster than we expected on new hardware. Along the way we discuss useful benchmarking tools, how to validate results, and why it pays to know exactly what hardware you're running on.

This all started in our performance test lab. During the development of Visual Studio, each new build undergoes a suite of automated performance tests, running in a lab full of identical machines. These performance tests allow us to track Visual Studio's performance over time, and detect performance regressions (when something gets unexpectedly worse). We recently added a batch of new machines in our lab, and that's when the fun started.

Pop Quiz: How Much Faster?

Old machine: dual-core Intel Pentium D 830 processor, running at 3 GHz, with 1 GB of RAM.

New machine: quad-core Intel Xeon 5355 processor, running at 2.66 GHz, with 4 GB of RAM.

Given the differences in the two hardware configurations above, how much faster would you expect the new machine to be when running a Visual Studio performance test? Lower than, same as, twice, three times or four times the performance of the older machine?

One line of reasoning might look at the relative clock frequencies of the processors on the two machines. This might lead you to expect the newer processor cores to perform slower than the older cores, since their clock frequency is 11% lower. By this reasoning you might conclude that single-threaded applications would perform poorly on the new machine.

Another line of reasoning would factor in the number of cores in the two systems. Since the new machine has twice the number of cores, you might expect it to have about twice the performance on multi-threaded applications. (If you also accounted for the lower clock frequency, you'd end up with a figure of 1.78 times the performance of the old machine.)

A third approach might estimate the impact of RAM size. We’ve quadrupled the amount of RAM, so maybe any benchmarks that used to page to disk can now execute entirely in memory and hence will be orders of magnitude faster. [We'll cheat here and tell you that our benchmarks are generally not memory constrained].

So far, all these options seem plausible. What's your guess?

What we naively expected to find lay somewhere between the first two lines of reasoning - that the new machines would be 1-2 times faster than the old machines, depending on the particular benchmark.

What we actually found is that many of our single-threaded CPU-bound benchmarks run about twice as fast on the new machine, while scalable multi-threaded benchmarks run up to four times as fast. This was a pleasant surprise, because it significantly reduces the overall time to run all the benchmarks. But it did leave us wondering why we were getting much greater speedups than our naive explanations would suggest. The rest of this post explores that question.

Using WinSAT and SPEC to Validate Benchmark Results

To make sure this wasn't a fluke result, we used the Windows System Assessment Tool (winsat.exe). This is a built-in tool that can give quickly give a representative view of a machine's performance. It is multi-threaded, taking full advantage of all the cores on a machine. Here are the WinSAT CPU results:

Benchmark	Old Machine	New Machine	Speedup
CPU – Compression (MB/s)	70.5	262.0	3.7
CPU – Encryption (MB/s)	52.3	139.3	2.7

We also wanted to validate our results against other real-world benchmarks. For this we turned to the SPEC website. SPEC produces a series of benchmark suites, plus a very formal process that ensures results are reproducible and can fairly be applied across different manufacturers. More importantly for our purposes, SPEC posts all reported benchmark results on their web site. You won’t always be able to find your exact machine listed, but after using results from a tool like CPU-Z you can generally find results from a machine with the same CPU configuration and clock speed.

We used the "CINT2006" benchmarks – this is a widely-used benchmark suite concentrating on integer performance. We compared results for both CINT2006, which is a good test of single-threaded performance, and CINT2006 Rate, which tests the ability of a system to execute multiple copies of CINT2006, and is therefore a better test of multi-threaded performance. For two representative machines that are similar to our old and new hardware, here are the results:

Benchmark	Old Machine	New Machine	Speedup
CINT2006	9.85	15.5	1.6
CINT2006 Rate	18.0	44.4	2.5

The WinSAT and SPEC results confirm that the new machines are much faster than our naive expectations, even for benchmarks such as CINT2006 that cannot take advantage of the extra cores. So what were we missing?

Using CPU-Z to Examining Machine Configurations

To answer this, we need a deeper understanding of the configurations of the two systems.

Unfortunately, finding detailed configuration information isn't always straightforward. For example, we know that level two (L2) cache size impacts performance, but Windows doesn't report it, and it's not easy to reboot into the BIOS to take a look at cache size when the machine is located in a remote test lab. This is where machine reporting tools like CPU-Z come in. You can run CPU-Z remotely on an unknown machine and get back a nicely formatted HTML report showing exactly what the hardware is. Here's a deeper look at our old and new systems:

Feature	Old Machine	New Machine
CPU name	Pentium D 830 (“Smithfield”)	Xeon X5355 (“Clovertown”)
CPU speed	3.00 GHz	2.66 GHz
Number of cores	2	4
L1 cache (per core)	16 KB	32 KB
L2 cache (total)	2 MB	8 MB
System RAM	1 GB DDR2	4 GB DDR2

Using BCDEdit to Disable Cores

Now we can try to tease out the relative impacts of the many changes from the old configurations the new configurations. The first and easiest step is to disable two out of four cores on a new machine, to enable a fairer "apples to apples" comparison of cores between old and new machines.

To do this we used the Windows BCDEdit tool, which replaces the old method of editing BOOT.INI by hand. Here we were particularly concerned with the order in which cores are disabled. This is important because the 8 MB of L2 cache in the Xeon “Clovertown” processors is divided: two of the four cores share 4 MB, and the other two cores share the other 4 MB. To keep our benchmark comparisons as fair as possible, we wanted to make sure that only one of the L2 caches was in use after disabling two cores. We used CPU-Z again after rebooting to confirm this.

Now we were in a position to do a fairer “cores to cores” comparison between the old and new machines. Here's a summary from WinSAT:

Benchmark	Old Machine	New (2 cores)	Speedup
CPU – Compression (MB/s)	70.5	131.9	1.9
CPU – Encryption (MB/s)	52.3	69.7	1.3
Memory Bandwidth (MB/s)	4,041	3,360	0.8

Now we can really see the advantage of the latest processors – on a core-for-core basis, they are 1.3-1.9x faster on the CPU-intensive WinSAT benchmarks, despite having lower clock frequencies.

Good, now on to the next… wait a second. Look at that memory bandwidth result. Our new machines have less memory bandwidth than the old machines? That doesn't look right: although memory performance hasn't been keeping pace with CPU speeds, it has been improving over time. Compared to a three-year-old machine, we'd expect these new machines to have slightly better memory bandwidth, and definitely not worse. What gives?

Memory Channels

A primary limiting factor to memory bandwidth is the number of memory channels that are in use. And this turns out to be the problem here: although the new machines have four memory channels and eight memory slots, only two of those slots are filled, because the vendor supplied us with two 2 GB memory modules per machine. This maximizes future expansion potential – we can take the machine up to 16 GB without throwing away any of our initial investment in memory. But in the meantime using two memory slots limits us to two memory channels in use. If instead we had four 1 GB memory modules we'd have four memory channels in use, improving memory interleaving from 2:1 to 4:1 and increasing memory bandwidth. To confirm this, we populated four memory slots on one of the new machines (going from 4 GB to 8 GB) and reran WinSAT:

Benchmark	2 channels	4 channels	Speedup
Memory Bandwidth (MB/s)	3,360	4,134	1.2

Conclusions

It's always possible to run more experiments to further isolate and explain benchmark results, but after a while you reach a point of diminishing returns. With the results we have so far, we can already draw some useful conclusions.

The first conclusion is that our naive explanations greatly underestimated just how much better the newer processors are at executing real benchmarks, despite their slower clock speeds. The results from WinSAT and SPEC clearly show this, with core-to-core performance that is 1.3-1.9x faster on the new machines, depending on the benchmark.

This is perhaps the most important lesson for developers to learn: clock speeds are no longer a good indicator of true performance. Although clock speeds have plateaued, processor designers continue to find ways to make each new generation significantly faster than the last. In our case, the old machines have Pentium D processors (“Smithfield”), while the new machines have Xeon 5-series processors (“Clovertown”). And while the newer processors have slightly slower clock speeds, their micro-architecture executes more instructions per clock cycle.

The second conclusion is that it's very hard to perform fair comparisons. The two machines have several configuration differences, including clock frequency, number of cores, core micro-architecture, cache sizes, bus speed, memory size and speed, and so on. We showed an example of isolating the effect of just one of these differences, the number of cores, using the BCDEdit tool. Isolating the effect of every single difference would require much more effort.

Indeed, some of these differences are interrelated, and it is hard to change one without affecting another. For example, CPU architects make their micro-architecture design decisions based on cache sizes. Now imagine a hypothetical experiment that tried to isolate the effect of L2 cache size by giving each core just 1 MB of cache. This would be especially hard on the newer processors, which have been designed on the assumption that they have 2 MB of L2 cache per core[1]. In trying to perform a fairer comparison, we would have actually handicapped one system!

Our final conclusion is that it truly pays to benchmark and compare systems. In our case, the simplest possible benchmark (WinSAT) showed an unexpected memory bandwidth loss, which we then traced back to a machine mis-configuration. So that was the final pleasant surprise: if we hadn't gotten curious about why the new machines were so much faster, we would never have found that they could be faster still!

David Berg
Sunny Egbo
Jonathan Hardwick
Peter Okonski

[1] Because two cores share a single 4 MB L2 cache on the Clovertown processors, the exact size of the cache that is used by each core is not fixed at 2 MB per core; the use will vary during program execution. Cache hungry threads might get more of the cache, while less cache hungry threads get less. Even when two cache hungry threads run on the two cores, their memory hotspots are asynchronous; thus, the net effect is that each thread gets more of the cache when they need it and less when they don’t need it.