 MSDN Magazine October 2007

MSDN Magazine October 2007

Pooled Threads: Improve Scalability With New Thread Pool APIs

The new threadpool APIs in Windows Vista and in the upcoming Windows Server 2008 provide advances that even native Windows developers can benefit from.

Robert Saccone WPF Threads: Build More Responsive Apps With The Dispatcher

Understanding the Windows Presentation Foundation threading model helps when creating user interfaces that are both compelling and responsive.

Shawn Wildermuth Parallel LINQ: Running Queries On Multi-Core Processors

Use Parallel Language Integrated Query (PLINQ) to take advantage of multi-processor computers and the newer wave of multi-core processors.

Joe Duffy and Ed Essey Parallel Performance: Optimize Managed Code For Multi-Core Machines

While multi-core processors have become increasingly common, most applications still fail to take advantage of multiple cores. Here's an overview of creating multithreaded applications that benefit from these new processors.

Daan Leijen and Judd Hall Mobile Apps: Adjust Your Ring Volume For Ambient Noise

Here's an overview of designing and installing a Windows Mobile app that monitors the noise level in the surrounding environment and adjusts the ring volume of a Pocket PC accordingly.

Chris Mitchell Editor's Note: The Complexity of Complexity

This month our new Editor-in-Chief, Howard Dierking, ponders the convenience of metaphor and abstraction in both software design and magazine production.

Howard Dierking Toolbox: Manage databases, easier FTP, and clustered caching

This month's products include DatabaseSpy, FileZilla, NCache, and more.

Scott Mitchell CLR Inside Out: IronPython and the Dynamic Language Runtime

This column uses the .NET version of the Python programming languages IronPython to demonstrate the value of dynamic languages and the new Dynamic Language Runtime.

Bill Chiles Basic Instincts: Type inference in Visual Basic 2008

Visual Basic 2008 provides type inference to get the language ready to take advantage of LINQ and make your code more robust.

Bill Horst Data Points: Common Table Expressions

In T-SQL, views and derived tables serve similar purposes and have their advantages. But when working with SQL Server 2005,there's a third option--using Common Table Expressions (CTEs). John Papa explains.

John Papa Cutting Edge: AJAX application architecture, Part 2

The second of this two-part series delves into the script services programming model, which is useful if you're looking for a full paradigm shift in building AJAX applications.

Dino Esposito Test Run: Test automation with Windows XP Embedded

This month's column explores how to create lightweight but powerful UI test automation for software systems that run on Windows XP Embedded.

Dr. James McCaffrey and Mike Hall Foundations: 3D text in WPF

This month Charles Petzold explores techniques for generating 3D text in Windows Presentation Foundation.

Charles Petzold Windows with C++: Task Scheduler 2.0

The new Task Scheduler in Windows Vista can do so much more than previous versions. We introduce some basic concepts and building blocks you can put to use in your own scheduled task projects.

Kenny Kerr Netting C++: Describing the EEK!-osystem

This column crafts an XML document to hold the mouse environment simulation data and shows how to incorporate an XML file into the program using a DataSet.

Stanley B. Lippman .NET Matters: Deadlock monitor

This month Stephen Toub discusses deadlocks that can occur when synchronizing threads.

Stephen Toub { End Bracket }: Matrimony mashup

Our site manager Mike Richter leverages Virtual Earth, the Microsoft MapPoint Web service, and Visual Studio to automate the creation of a Web site for his future nuptials and to manage the guest list.

Michael Richter


Pooled Threads: Improve Scalability With New Thread Pool APIs

Pooled Threads

Improve Scalability With New Thread Pool APIs

Robert Saccone
Portions of this article are based on a prerelease version of Windows Server 2008. Details contained herein are subject to change.
Code download available at: VistaThreadPools2007_10.exe (175KB)
This article discusses:
  • Thread pool functionality
  • Legacy thread pool limitations
  • New thread pool APIs
  • Thread pool objects
This article uses the following technologies:
Windows Vista, Windows Server 2008
Contents
Thread Pool Overview
Thread Pool Objects
Callback Environment Objects
Work Objects
Wait Objects
Timer Objects
I/O Completion Objects
Simplifying Cleanup with Cleanup Groups
Callback Instance APIs
Try It Out with the Sample Applications

W
ith the release of Windows Vista® and the upcoming release of Windows Server® 2008, Microsoft has enriched the Windows® platform with so much new technology for developers of managed applications that it's easy to overlook advancements that the native Windows developer can benefit from. The thread pool component that has been part of the platform since the release of Windows 2000, for example, has undergone a complete rearchitecture. The new implementation brings with it a new thread pool API that should make it much easier for developers to write correct code. The legacy APIs are still supported so that legacy applications can continue to run, but, as you'll see, there are many benefits to be gained from moving to the new APIs.

Thread Pool Overview

Before diving into the new APIs, let's review the type of functionality that the thread pool component provides. In a nutshell, the thread pool allows functions to be called at timed intervals, asynchronously, when a kernel object has been signaled, and when asynchronous I/O requests complete. Each time one of these callback functions should be invoked, a request to invoke a callback function is added to the end of a first-in-first-out (FIFO) queue that the thread pool maintains. Worker threads internally managed by the thread pool remove items from the queue and invoke the callback functions. Since the thread pool manages the lifetimes of the worker threads, the application developer does not have to explicitly manage thread lifetimes. This also means that the application should never terminate a thread pool worker thread using the TerminateThread function or by calling the ExitThread function from a function that is executing on a worker thread.

Applications often create dedicated threads that spend a great deal of time waiting for an event or periodically awakening to poll for some state. The thread pool makes this more efficient. For a server class application that is trying to process numerous client requests, the thread pool enables the preferred server concurrency model for the Windows platform, which is to process as many requests concurrently as there are processors in the system. One alternative model I've seen developers try is to dedicate one thread for each client being serviced, but this model does not scale well with a large number of clients. Not only do the large number of threads consume significant resources, but the cost of context switching between them becomes significant and impacts the overall quality of service each client receives.

The new thread pool component addresses a number of limitations of the legacy thread pool. For example, the new thread pool lets you create multiple thread pools per process, while the old model allowed only one. This lets you isolate the tasks the application performs by some chosen criteria. For example, suppose you're writing a distributed server application that is going to use the thread pool to process asynchronous I/O completions on network connections. The network connections are of two types, one from a client application and the second from other instances of the server application running on different computers. Let's further assume that you have to support a large number of simultaneous client connections per server and that the number of client requests is much greater than server-to-server connections, but the server-to-server connections have a higher priority.

When both client and server network connections are processed on a single thread pool, there is a single queue to which all the completion notifications are queued. This means that an I/O completion from a server connection will not be processed until all I/O completions in front of it in the queue are processed, including those from any clients. This can result in significant delays in processing server connections when the system is under heavy client load. Dedicating a thread pool to client connections and another to server connections allows for isolation because each thread pool has its own queue and set of worker threads. The scheduler in the operating system will ensure that the processors are shared fairly between the threads in both pools. However, it's important to use multiple thread pools judiciously as creating too many per process can hurt performance and reduce throughput.

The legacy thread pool used two types of worker threads: I/O and non-I/O, which at times caused confusion. If the developer didn't understand the distinction, the result could be limited performance or incorrect behavior. Moreover, having two distinct thread groupings meant that the thread pool implementation itself was less efficient since it couldn't share threads between callback functions of different types. In the new thread pool, this distinction is removed and all worker threads are the same.

In the legacy API, QueueUserWorkItem was used to queue a function to be called asynchronously on a thread pool worker thread. The legacy API provided no way for the application to determine when the worker thread had finished executing the callback function. If the callback function was located in a DLL, it was virtually impossible to guarantee that it was safe to unload the DLL. This meant that unloading a DLL occasionally caused the hosting process to crash. There was also no way to cancel callbacks that were in the thread pool's queue awaiting execution, so there was no choice but to wait for all requests to drain, which could introduce significant delays.

Finally, the legacy API does not separate resource allocation from resource use. Since these resource allocations can and do fail, the legacy API makes it hard to develop systems that have reliability guarantees. The new thread pool API makes the separation between resource allocation and usage distinct, so that once a resource has been successfully allocated, there is virtually no possibility of failure for well-written code when those resources are put to use.

The new thread pool API is object-based, where each type of object has a set of functions for creation, cleanup, and modifying properties. Figure 1 summarizes the object types exposed by the API. It's important to understand that all the objects created by the thread pool, and all the worker threads managed by it, become part of the application process using them.

Figure 1 Thread Pool Object Types (Close Figure 1)

Object Type | Description
TP_POOL | Pool of threads used to execute callbacks.
TP_TIMER | Invoke a callback function at a due time.
TP_WAIT | Invoke a callback function when a kernel object is signaled or the wait times out.
TP_WORK | Invoke a callback function asynchronously.
TP_IO | Invoke a callback function when an asynchronous I/O completes.
TP_CLEANUP_GROUP | Track one or more thread pool callback objects.
TP_CALLBACK_ENVIRON | Bind a thread pool to its callback objects, and optionally a cleanup group.

Thread Pool Objects

The first step in preparing a thread pool for use is to create one using the CreateThreadpool function, which is shown in Figure 2. The function takes a reserved parameter that must be NULL. If the function succeeds, it returns a PTP_POOL representing the newly allocated thread pool. If the function fails, it returns NULL, and GetLastError can be used to get extended error information.

Figure 2 Thread Pool Object API (Close Figure 2)
PTP_POOL WINAPI CreateThreadpool(PVOID reserved);

BOOL WINAPI SetThreadpoolThreadMinimum(PTP_POOL ptpp,
                      DWORD cthrdMin);

VOID WINAPI SetThreadpoolThreadMaximum(PTP_POOL ptpp,
                      DWORD cthrdMost);

VOID WINAPI CloseThreadpool(PTP_POOL ptpp);

Once the thread pool is created, it is possible to control the minimum and maximum number of threads the pool will manage using two new APIs. By default, the thread pool minimum is 0 and the maximum is 500. These numbers were chosen for backward compatibility with the legacy thread pool as some applications using the legacy thread pool required large numbers of threads. These defaults could change in future versions of Windows as any application that uses such a large number of threads is likely to perform poorly due to excessive context switching.

There are some interesting features to be aware of with these APIs. Notice that SetThreadpoolThreadMinimum returns a BOOL while SetThreadpoolThreadMaximum returns nothing. The reason is that if setting the minimum number of threads requires SetThreadpoolThreadMinimum to increase the number of worker threads in the pool to meet the new minimum, and a failure occurs while allocating the threads, this failure can be reported back to the caller. Setting the maximum number of threads in the pool doesn't cause any resource allocations because all the function does is set an upper bound on how many threads the thread pool can create. The thread pool will vary the number of threads from the minimum to the maximum based upon the actual workload of the thread pool. Unfortunately, SetThreadpoolThreadMinimum has a bug in Windows Vista that manifests when it needs to increase the number of worker threads in the pool: the function returns without immediately creating the additional threads. This bug will be fixed in Windows Vista Service Pack 1 and isn't an issue in Windows Server 2008. For Windows Vista today, however (barring the issue of worker-thread-creation failure), once enough work has been queued to cause the thread pool to create the specified minimum number of threads, the thread pool will honor the minimum and maintain at least that many threads in the pool.

Setting the minimum and the maximum number of threads to the same value creates a pool of persistent threads that will never terminate until the pool is closed. This is handy for using a thread pool with a function, such as RegNotifyChangeKeyValue, that must be called from a persistent thread. For more information on RegNotifyChangeKeyValue see msdn2.microsoft.com/ms724892.

Note that calling SetThreadpoolThreadMinimum with a minimum greater than the current maximum not only causes a new minimum to be set but also causes the maximum to be set to that new minimum. Calling SetThreadpoolThreadMaximum with a maximum that is less than the minimum causes the minimum to be set to the new maximum. The thread count parameter is specified as a DWORD in both of these functions, but the entire range of a DWORD is not available for the thread count. Internally, the value is treated as a LONG and is validated to be greater than or equal to 0.

This is an appropriate time to explain the error-reporting philosophy of the thread pool APIs. If an operation is one that can legitimately be expected to fail, the result is reported by a return code from the function being called. However, errors that are exceptional are reported using structured exceptions. For example, for the functions SetThreadpoolThreadMinimum and SetThreadpoolThreadMaximum, passing an invalid value for the number of worker threads or a NULL thread pool pointer causes a structured exception to be raised. However, a failure to create a new worker thread during a call to SetThreadpoolThreadMinimum is reported to the caller as FALSE because a resource allocation failure is an error that should be expected. It may be tempting to wrap structured exception handlers around calls to the thread pool APIs so that an application will not terminate due to the unhandled exception, but this is a bad idea as catching these exceptions and continuing to execute the program only serves to hide a problem in the application itself. This only makes it harder to diagnose the cause of the problem when the application ultimately fails.

In order to use these APIs properly, it helps to have an understanding of how the concurrency model of the thread pool is implemented. This model is based on the number of available processors in the system. For example, if the system has two physical processors with two cores per processor, optimally you should have only four threads that are runnable most of the time. This eliminates context-switching overhead. However, if the application has only one callback outstanding most of the time, sizing the thread pool to only one thread is perfectly reasonable. Going back to the two-processor, two-core example, assuming that the application has a dozen outstanding callbacks, there should be at least four worker threads in the pool to allow each core to process one item. However, in order to maintain optimal concurrency, it may be necessary for the thread pool to contain more than four worker threads. To understand why, consider a case in which each of the four cores is already busy executing a callback function and there is also a callback pending in the thread pool's queue. What happens if one of those worker threads executing callbacks blocks? There are three possibilities:

  • If the thread pool has an available thread in the pool, it will dispatch another thread to remove the next item from the queue and invoke the pending callback function.
  • If the thread pool has no other available worker threads and the number of worker threads already created is less than the maximum thread count, after a short delay it will create a new worker thread that will be dispatched to execute the pending callback function.
  • If the thread pool has no other available worker threads, and the number of worker threads the thread pool has already created has reached the maximum thread count, no additional threads will be created and the pending callback item will remain in the queue until a previously dispatched worker finishes executing its callback function and returns to the thread pool to determine if there is another item to be executed.

For this reason, if a callback function might block while executing, the maximum size of the thread pool must be larger than the number of available processors in the system in order to realize the maximum concurrency that the hardware supports. Ideally, a callback function should never block. A callback function that blocks not only decreases concurrency but also decreases the level of worker thread reuse. Because of this, it's definitely worth making the effort to eliminate or minimize the length of time a callback function blocks. You can reduce that time if you understand what the callback is blocking on. For example, if the callback is performing synchronous I/O, consider changing it to asynchronous I/O that completes on the thread pool instead. And look to minimize any synchronization that must occur between callback functions because lock contention can cause blocking.

If most of the callback functions don't block, the thread pool can be sized to contain fewer threads in excess of the number of available processors. If most of the callback functions are going to end up blocking, the thread pool should be sized to contain many more worker threads than the number of available processors. In this case, most threads will end up in a wait state. As callback functions complete, in order to maximize overall throughput the thread pool will hold back worker threads, reducing the number of runnable threads to a number that's optimal for the processor configuration. The point is that you want to size the thread pool so that when there are tasks to run and sufficient processor bandwidth available, the pool can create more threads to do work. However, if you find that your application actually uses an inordinately large number of threads, like the 500 in the default setting, or if there is excessive context switching cost, the application is not designed properly and you need to examine your code using the performance monitor and a code profiler to determine where improvements can be made.

Once you're finished with the thread pool, it should be closed using the CloseThreadpool function. The thread pool is closed immediately if there are no outstanding callback objects that are bound to the thread pool. If there are, then the thread pool is released asynchronously when those outstanding objects are freed.

Callback Environment Objects

Now that you understand how to create a thread pool, the next step is to look at what a callback environment object is and how it should be used. A callback environment object is used to bind a thread pool instance to the instances of thread pool callback objects your application creates to actually do work on the thread pool. A callback environment object also allows you to attach a cleanup group object, which makes the cleanup of the thread pool callback objects simpler. Cleanup groups will be fully discussed later on in the article. The callback environment APIs are shown in Figure 3.

Figure 3 Callback Environment APIs (Close Figure 3)
VOID InitializeThreadpoolEnvironment(PTP_CALLBACK_ENVIRON pcbe);
VOID DestroyThreadpoolEnvironment(PTP_CALLBACK_ENVIRON pcbe);
VOID SetThreadpoolCallbackPool(PTP_CALLBACK_ENVIRON pcbe,
                    PTP_POOL ptpp);
VOID SetThreadpoolCallbackLibrary(PTP_CALLBACK_ENVIRON pcbe,
                    PVOID mod);
VOID SetThreadpoolCallbackRunsLong(PTP_CALLBACK_ENVIRON pcbe);

VOID SetThreadpoolCallbackCleanupGroup(PTP_CALLBACK_ENVIRON pcbe,
                    PTP_CLEANUP_GROUP ptpcg,
                    PTP_CLEANUP_GROUP_CANCEL_CALLBACK pfng);

The first step in creating a callback environment is to either declare a TP_CALL_BACK_ENVIRON structure in static storage, on the stack, or allocate one from the heap. The next step is to initialize it using the InitializeThreadpoolEnvironment function, which takes a pointer to TP_CALLBACK_ENVIRON. Finally, to associate a thread pool with the callback environment, use SetThreadpoolCallbackPool. If you don't associate a thread pool with the callback environment or if NULL is specified in the call to SetThreadpoolCallbackPool, the process's default thread pool will be used. As you'll see, the callback environment is eventually used to create the various thread pool callback object instances. Once your application has finished modifying the properties of the callback environment and creating all the instances of the callback objects it needs, the callback environment should be destroyed using the DestroyThreadpoolEnvironment function.

The SetThreadpoolCallbackRunsLong API is used to give a hint to the thread pool that the callback functions associated with this environment may not return quickly. You'll see later how this affects the result returned from calling the API function CallbackMayRunLong.

I mentioned earlier that the legacy thread pool lacked support for an application that needed to determine when it was safe to unload a DLL containing a callback function that was to be executed on the thread pool. The new thread pool API provides the SetThreadpoolCallbackLibrary function to guarantee that a library remains loaded as long as a callback function inside a DLL is still executing. Essentially, what happens is that before the callback function is invoked, the operating system's loader lock (which is always held when a DLL is in the process of being loaded or unloaded) is acquired and the DLL's reference count is incremented; the loader lock is then released. After the callback completes execution, the loader lock is acquired again to decrement the reference count. This makes it impossible for the DLL to be unloaded while a callback function is executing. Note that while callbacks are pending on the thread pool's queue, the reference count on the DLL remains unchanged. This means that a DLL can be unloaded with callbacks pending. However, it is the job of the DllMain function that you write to make sure that you handle the DLL_PROCESS_DETACH event and cancel all pending callbacks. I'll get to this in a bit.

Work Objects

A work object is used to cause the thread pool to invoke a callback function asynchronously on a worker thread. The CreateThreadpoolWork function, shown in Figure 4 along with all the other work object related APIs, is used to create a work object.

Figure 4 Work Object APIs (Close Figure 4)
PTP_WORK WINAPI CreateThreadpoolWork(PTP_WORK_CALLBACK pfnwk,
                    PVOID Context,
                    PTP_CALLBACK_ENVIRON pcbe);
VOID WINAPI SubmitThreadpoolWork(PTP_WORK pwk);
VOID CALLBACK WorkCallback(PTP_CALLBACK_INSTANCE Instance,
                    PVOID Context,
                    PTP_WORK Work);
VOID WINAPI WaitForThreadpoolWorkCallbacks(PTP_WORK pwk,
                    BOOL fCancelPendingCallbacks);
VOID WINAPI CloseThreadpoolWork(PTP_WORK pwk);

BOOL WINAPI TrySubmitThreadpoolCallback(PTP_SIMPLE_CALLBACK pfns,
                    PVOID pv,
                    PTP_CALLBACK_ENVIRON pcbe);
VOID CALLBACK SimpleCallback(PTP_CALLBACK_INSTANCE Instance,
                    PVOID Context);

The first parameter, pfnwk, is a pointer to the callback function to be executed by a worker thread. The second parameter, Context, is typed as PVOID and can be used to supply any application-specific data that the callback function needs. Finally, the last parameter is a pointer to the TP_CALLBACK_ENVIRON. The work object will be bound to the thread pool and, if any, the cleanup group that has been associated with the callback environment.

After the work object has been created, it can be queued to the thread pool using the SubmitThreadpoolWork function. Eventually a worker thread will remove the work object from the queue and invoke its associated callback function. Each call to SubmitThreadpoolWork will generate one call to the work item's callback function.

The WorkCallback function for a work object takes three parameters. The first, Instance, is used to identify the specific instance of the callback function's execution and remains valid only for the execution of the callback function. The Context parameter is the pointer that was supplied as the second parameter to CreateThreadpoolWork. The final parameter, Work, is the instance of the work object for which the callback function is being invoked.

It's important to understand that a callback function can be invoked by any worker thread in the thread pool. The rule of thumb to follow is that the callback function shouldn't make any assumptions about the worker thread on which it will execute and should leave the worker thread in the same state it was in prior to the callback function invocation. For example, if the callback function is going to use COM, then it must call CoInitializeEx each time it is invoked. The callback function should also call CoUninitialize before returning since a worker thread can be reused to dispatch callback functions for a number of different tasks, or it might even be terminated when it is returned to the thread pool. This prevents resources leaks and leaving state information around that could adversely affect the execution of the next callback function, which may have different requirements for the execution environment of the thread. Application Verifier is a runtime verification tool for unmanaged code that assists in finding subtle programming errors that may be difficult to identify in normal application testing. It has been enhanced to assist in finding programming errors related to the thread pool. Among the errors it can detect are unbalanced CoInitializeEx and CoUninitialize calls, thread priority and affinity changes that haven't been reverted before returning the worker thread to the thread pool, impersonation that hasn't been reverted, and orphaned critical sections. For a comprehensive list, consult the documentation installed with Application Verifier, which can be downloaded from microsoft.com/downloads/details.aspx?familyid=bd02c19c-1250-433c-8c1b-2619bd93b3a2.

The WaitForThreadpoolWorkCallbacks function blocks the calling thread until all outstanding callback functions for a work object have completed execution. The second parameter controls whether pending callbacks (callbacks that have been queued to the thread pool's queue but have not yet been dispatched to a worker thread for execution) should be allowed to execute or be canceled. Be careful with this API—using it inside of the work callback function can cause a deadlock.

Rounding out the API set relating to work objects is the CloseThreadpoolWork function. The work object is freed immediately if there are no outstanding callbacks; otherwise the work object will be freed asynchronously once outstanding callbacks complete. This also means that any pending callbacks waiting for execution on the thread pool's queue will be canceled.

The remaining function in Figure 4, TrySubmitThreadpoolCallback, offers the equivalent of creating a work object, submitting it to the thread pool, and ensuring that the work object will be closed once the callback specified by the pfns parameter has completed executing. The signature of the callback function must conform to the signature of the SimpleCallback in Figure 4. It is slightly different from the callback associated with a work object. Since the thread pool takes care of allocating and releasing the work object internally, the callback function is only passed the callback function instance pointer and the application defined context specified in the Context parameter of TrySubmitThreadpoolCallback. Since TrySubmitThreadpoolCallback allocates resources to do its work, there is a possibility it could fail, which is why it returns a BOOL return code.

Wait Objects

Wait objects are used to invoke a callback function once a kernel object has become signaled or when the specified wait period times out. The CreateThreadpoolWait function is used to create a wait object. Its parameters follow the same pattern as CreateThreadpoolWork with the exception that the pointer to the callback function supplied in the first parameter must match the signature of the WaitCallback function, as shown in Figure 5.

Figure 5 Wait Object APIs (Close Figure 5)
PTP_WAIT WINAPI CreateThreadpoolWait(PTP_WAIT_CALLBACK pfnwa,
             PVOID pv,
             PTP_CALLBACK_ENVIRON pcbe);
VOID WINAPI SetThreadpoolWait(PTP_WAIT pwa,
             HANDLE h,
             PFILETIME pftTimeout);
VOID CALLBACK WaitCallback(PTP_CALLBACK_INSTANCE Instance,
             PVOID Context,
             PTP_WAIT Wait,
             TP_WAIT_RESULT WaitResult);
VOID WINAPI WaitForThreadpoolWaitCallbacks(PTP_WAIT pwa,
             BOOL fCancelPendingCallbacks);
VOID WINAPI CloseThreadpoolWait(PTP_WAIT pwa);

After creating a wait object, the next step is to cause the thread pool to wait for a kernel object to become signaled. The SetThreadpoolWait function is used to do just that. The first parameter, pwa, is a pointer to the wait object instance being set. The second parameter is the HANDLE to the kernel object to wait on. The final parameter, pftTimeout, is a pointer to a FILETIME structure that indicates the amount of time the thread pool should wait for the kernel object to be signaled. The amount of time to wait can be expressed in absolute or relative terms and is specified in 100-nanosecond units. Passing a positive value indicates that the timeout is an absolute time since 1/1/1600. Passing a negative value indicates a time relative to the current time at the call of the function. Passing a 0 indicates that the wait times out immediately. Finally, passing NULL indicates an infinite wait that never times out.

Once the kernel object becomes signaled or the wait times out, the thread pool will invoke the wait object's WaitCallback function. The first two parameters are exactly the same as in the WorkCallback function described earlier. The Wait parameter indicates which wait object the callback is being invoked for and the WaitResult is used to indicate the reason for the invocation. WaitResult will be WAIT_ABANDONED_0, WAIT_OBJECT_0, or WAIT_TIMEOUT. If WaitResult is set to WAIT_OBJECT_0, it means that the kernel object became signaled and the wait was satisfied.

If WaitResult is set to WAIT_TIMEOUT, it means the wait is unsatisfied and the timeout interval specified in the call to SetThreadpoolWait has elapsed. A result of WAIT_ABANDONED_0 indicates that the specified object is a mutex and that it was not released by the thread that owned the mutex object before it terminated. However, using a mutex with a wait object should be avoided because the worker thread that invokes the WaitCallback function is not the thread that performed the wait on the mutex. The thread pool uses a different type of thread, called a waiter thread, to actually perform the wait on the kernel object. It is the waiter thread that actually owns the mutex. Waiter threads are not exposed to applications, so there is no way to release the mutex once the waiter thread acquires ownership of it.

After the WaitCallback function has been called for a wait object, SetThreadpoolWait must be called again in order reuse the wait object and have the thread pool wait again for a kernel object to become signaled. Note that when calling SetThreadpoolWait again to reuse a wait object, you have the option to once again specify any kernel object handle to wait on. You don't have to use the handle that was specified in the first call to SetThreadpoolWait if you want to wait on a different kernel object. Finally, the remaining wait object APIs, WaitForThreadpoolWaitCallbacks and CloseThreadpoolWait, behave in exactly the same manner as their work object counterparts.

Timer Objects

Timer objects are used to invoke a callback function when the timer object reaches its due time. They are created using the CreateThreadpoolTimer function, which is shown in Figure 6 along with the other timer object-related APIs. Once again the parameters follow the same pattern as the CreateThreadpoolWork function (in Figure 4), with the exception that the pointer to the callback function supplied in the first parameter must match the signature of the TimerCallback function, as shown in Figure 6.

Figure 6 Timer Object APIs (Close Figure 6)
PTP_TIMER WINAPI CreateThreadpoolTimer(PTP_TIMER_CALLBACK pfnti,
              PVOID pv,
              PTP_CALLBACK_ENVIRON pcbe);
VOID WINAPI SetThreadpoolTimer(PTP_TIMER pti,
              PFILETIME pftDueTime,
              DWORD msPeriod,
              DWORD msWindowLength);
VOID CALLBACK TimerCallback(PTP_CALLBACK_INSTANCE Instance,
              PVOID Context,
              PTP_TIMER Timer);
VOID WINAPI WaitForThreadpoolTimerCallbacks(PTP_TIMER pti,
              BOOL fCancelPendingCallbacks);
BOOL WINAPI IsThreadpoolTimerSet(PTP_TIMER pti);
VOID WINAPI CloseThreadpoolTimer(PTP_TIMER pti);

After creating a timer object, the next step is to set it using the SetThreadpoolTimer function. The pftDueTime parameter is used to set the time when the timer should initially come due. This time is expressed in the same way as the time out used in the SetThreadpoolWait function described above. As its name suggests, the msPeriod parameter sets up a timer, expressed in milliseconds, that fires periodically. Therefore, once the initial time interval expressed by pftDueTime has expired and caused a callback to be queued to the thread pool, each subsequent time interval expiration defined by msPeriod will cause another callback to be queued.

The msWindowLength parameter specifies a time window, expressed in milliseconds, during which the thread pool may delay expiration of the timer. This parameter promotes efficiency when you're using a large number of timers and the expiration time doesn't have to be exact. The window is a fudge factor of sorts that allows the system to coalesce all the timer expirations that fall into the window together so that they can be batched. This is more efficient than waking up a thread, expiring one timer, sleeping, waking up a thread, expiring another timer, sleeping, and so forth. The delay will occur only if there aren't any timers in the window that absolutely must be expired. To better understand how msWindowLength might be used, consider a server app that has a large number of incoming client connections and that in order to reduce resource usage, connections that haven't been active for five minutes should be closed. In this case, specifying a non-zero window length for the inactivity timers, which may result in keeping a connection around slightly past its due time, may be acceptable.

SetThreadpoolTimer can also be used to set a new due time, period, and window length for a timer that was previously set. If the pftDueTime parameter is NULL, it will stop queuing callbacks to the TimerCallback function but callbacks that have already been queued will be executed. Thus you can cancel a timer without having to close the timer object so that it can be reused.

Once the timer object comes due, a request to invoke the callback will be queued to the thread pool. A worker thread will pick up the request and invoke the TimerCallback function supplied in the call to SetThreadpoolTimer. The parameters to the callback function are the same as those described for a work object callback function, with the exception that the third parameter is a PTP_TIMER instead of a PTP_WORK.

Of the remaining timer API functions in Figure 5, the IsThreadpoolTimerSet function, as its name implies, returns TRUE if the timer has been set and FALSE otherwise. The remaining two, WaitForThreadpoolTimerCallbacks and CloseThreadpoolTimer behave exactly as their work object counterparts do.

I/O Completion Objects

The final type of callback object supported by the thread pool is the I/O completion object. Figure 7 lists all the APIs relating to I/O completion objects. An I/O completion object is used to bind a file handle to the thread pool so that asynchronous I/O completion notifications are queued to the thread pool for processing by worker threads. The parameters for the CreateThreadpoolIo function follow a similar pattern to the other create functions with the addition of the HANDLE parameter, which must be opened for overlapped I/O completion.

Figure 7 I/O Completion Object APIs (Close Figure 7)
PTP_IO WINAPI CreateThreadpoolIo(HANDLE fl,
                PTP_WIN32_IO_CALLBACK pfnio,
                PVOID pv,
                PTP_CALLBACK_ENVIRON pcbe);
VOID WINAPI StartThreadpoolIo(PTP_IO pio);
VOID CALLBACK IoCompletionCallback(PTP_CALLBACK_INSTANCE Instance,
                PVOID Context,
                PVOID Overlapped,
                ULONG IoResult,
                ULONG_PTR NumberOfBytesTransferred,
                PTP_IO Io);
VOID WINAPI WaitForThreadpoolIoCallbacks(PTP_IO pio,
                BOOL fCancelPendingCallbacks);
VOID WINAPI CancelThreadpoolIo(PTP_IO pio);
VOID WINAPI WaitForThreadpoolIoCallbacks(PTP_IO pio,
                BOOL fCancelPendingCallbacks);
VOID WINAPI CloseThreadpoolIo(PTP_IO pio);

As shown in Figure 7, the first parameter to CreateThreadpoolIo is the HANDLE to receive completion notifications, while parameters two, three, and four represent respectively the pointer to the callback function to be invoked, an optional application-specific context, and a pointer to the callback environment. CreateThreadpoolIo returns a non-NULL pointer if successful and a NULL pointer otherwise.

In order to cause I/O completion notifications to be processed by the thread pool, the StartThreadpoolIo function must be called prior to issuing each asynchronous I/O request operation on the handle. Forgetting to do this has serious consequences because the thread pool will ignore the I/O completion when it occurs and cause memory corruption. You must call a related function, CancelThreadpoolIo, when the call to initiate an asynchronous I/O operation returns with a failure other than ERROR_IO_PENDING. Accidently omitting the call to CancelThreadpoolIo will cause the thread pool to leak memory.

Once an I/O completion occurs, a worker thread will call the IoCompletionCallback associated with the I/O completion object. The signature for the function follows the same convention as all the other callbacks: the first two parameters to the function are a pointer to the callback instance and the context pointer supplied to the create function. The third parameter, Overlapped, is the pointer to the overlapped structure supplied when initiating the asynchronous I/O operation. The fourth is IoResult, which contains the result of the operation. IoResult will contain NO_ERROR if the operation completed successfully; otherwise it will contain a system error code (see msdn2.microsoft.com/ms681381). The fifth parameter, NumberOfBytesTransferred, contains the number of bytes transferred during the I/O operation while the sixth parameter is a pointer to the I/O completion object itself.

Once again, the remaining functions in Figure 7,WaitForThreadpoolIoCallbacks and CloseThreadpoolIo, behave just like their work object counterparts.

Simplifying Cleanup with Cleanup Groups

Now let's see how cleanup groups can help simplify the process of cleaning up the thread pool callback objects an application creates. By associating a cleanup group with a thread pool callback environment, all thread pool callback objects created using that callback environment will be tracked by the cleanup group. Once your application is finished using callback objects, all it has to do to ensure that each one is closed is to make one function call instead of one close call for each callback object. In fact, if a callback object is associated with a cleanup group, the close API for it shouldn't be called.

The first step in using a cleanup group is to create a cleanup group object using the CreateThreadpoolCleanupGroup function, which is shown in Figure 8.

Figure 8 Cleanup Group APIs (Close Figure 8)
PTP_CLEANUP_GROUP WINAPI CreateThreadpoolCleanupGroup(void);
VOID WINAPI CloseThreadpoolCleanupGroupMembers(PTP_CLEANUP_GROUP ptpcg,
                       BOOL fCancelPendingCallbacks,
                       PVOID pvCleanupContext);
VOID CALLBACK CleanupGroupCancelCallback(PVOID ObjectContext,
                       PVOID CleanupContext);
VOID WINAPI CloseThreadpoolCleanupGroup(PTP_CLEANUP_GROUP ptpcg);

The next step is to associate the cleanup group with the callback environment it is to be used with. The SetThreadpoolCallbackCleanupGroup function from Figure 3 sets up this association.

The first parameter to the function is a pointer to the callback environment. The second parameter is the PTP_CLEANUP_GROUP, and the third parameter is a pointer to a callback function that will be invoked when the CloseThreadpoolCleanupGroupMembers function is called.

Once an application has finished using the thread pool callback objects that are being tracked by the cleanup group, all it has to do is call CloseThreadpoolGroupMembers, which will block until all callback functions currently executing complete. If fCancelPendingCallbacks is TRUE, callbacks that have been queued to the thread pool that have not yet started executing will also be canceled. If fCancelPendingCallbacks is FALSE, CloseThreadpoolCleanupGroupMembers will not return until all the pending callback functions are dispatched to a worker thread and complete execution. The pvCleanupContext parameter is used to pass application data to the optional cancel cleanup callback function that was specified in the call to SetThreadpoolCallbackCleanupGroup. The cancel callback function will be invoked once for each thread pool callback object being cleaned up. The cancel callback's signature must match the CleanupGroupCancelCallback function shown in Figure 3. The first parameter, ObjectContext, is the optional data that was supplied to the creation function for the thread pool callback object that is being cleaned up. The second parameter, CleanupContext, is the optional data that was supplied by the caller to the CloseThreadpoolGroupMembers function. After calling CloseThreadpoolCleanupGroupMembers, the CloseThreadpoolCleanupGroup function is used to close the cleanup group and free any resources associated with it. It's important that CloseThreadpoolCleanupGroup not be called while the cleanup group has members because doing so may cause resources to leak.

Callback Instance APIs

The final set of APIs to examine are shown in Figure 9. They are all meant to be used from the worker thread that is executing the callback object's callback function as they all require that the PTP_CALLBACK_INSTANCE be passed to the callback function. The first function, CallbackMayRunLong, is used to tell the thread pool that the callback function wants to run for an extended period of time. The thread pool tracks the number of worker threads that are executing long-running callbacks. Recall that earlier, we used the SetThreadpoolCallbackRunsLong function to tell the thread pool that callback functions associated with the supplied callback environment are all long-running callbacks.

Figure 9 Callback Instance APIs (Close Figure 9)

BOOL WINAPI CallbackMayRunLong(
                PTP_CALLBACK_INSTANCE Instance);
VOID WINAPI DisassociateCurrentThreadFromCallback(
                PTP_CALLBACK_INSTANCE Instance);
VOID WINAPI SetEventWhenCallbackReturns(
                PTP_CALLBACK_INSTANCE Instance,
                HANDLE evt);
VOID WINAPI ReleaseSemaphoreWhenCallbackReturns(
                PTP_CALLBACK_INSTANCE Instance,
                HANDLE sem,
                DWORD crel);
VOID WINAPI LeaveCriticalSectionWhenCallbackReturns(
                PTP_CALLBACK_INSTANCE Instance,
                PCRITICAL_SECTION pcs);
VOID WINAPI ReleaseMutexWhenCallbackReturns(
                PTP_CALLBACK_INSTANCE Instance,
                HANDLE mut);
VOID WINAPI FreeLibraryWhenCallbackReturns(
                PTP_CALLBACK_INSTANCE Instance,
                HMODULE mod);

A TRUE result from CallbackMayRunLong indicates that the thread pool has worker threads available for processing long-running callbacks. In considering worker thread availability, the thread pool only considers the current set of worker threads that exist at the time the function is called. A FALSE return code indicates that all available worker threads are busy executing long-running callbacks already. In this case, the callback function should return as quickly as possible and delay the long-running work to a later time if it wants to keep a worker thread available to execute short-running callbacks.

The next function in Figure 9, DisassociateCurrentThreadFromCallback, breaks the association between the currently executing callback function and the object that initiated the callback. The current thread will no longer count as executing a callback on behalf of the object. For example, if the callback function for a work object calls DisassociateCurrentThreadFromCallback, it can then call WaitForThreadpoolWorkCallbacks using the pointer to the work object that was passed into the callback function without risking a deadlock. However, DisassociateCurrentThreadFromCallback does retain the association of the currently executing callback to the cleanup group of the callback environments so that if another thread has called CloseThreadpoolCleanupGroupMembers, the function will wait for the thread executing the callback function to return to the thread pool. This ensures that DLLs will not be unloaded while there are still threads executing code within them. One thing to note is that if you call DisassociateCurrentThreadFromCallback, and plan on reusing the object from within the callback function (say for calling a function such as SubmitThreadpoolWork for a work object), this must be synchronized with any calls to CloseThreadPoolCleanupGroupMembers because trying to reuse the object once the CloseThreadPoolCleanupGroupMembers has started to execute can cause an exception to be thrown inside the callback function.

The next set of functions coordinates the completion of the execution of a callback function with a synchronization object. The SetEventWhenCallbackReturns function is used to put an event object into the signaled state when the current callback completes. Similarly the functions ReleaseSemaphoreWhenCallbackReturns, ReleaseMutexWhenCallbackReturns, and LeaveCriticalSectionWhenCallbackReturns are all designed to release different types of lock objects when the current callback function completes. These functions can help reduce programming errors by ensuring that no matter how the callback function returns, the specified lock will be released. Hopefully in a future release of Windows new functions will be added to support Slim Reader/Writer Locks as well.

The FreeLibraryWhenCallbackReturns function can be used to make the thread pool invoke FreeLibrary on the passed module handle when the specified callback instance completes execution. It's up to the application to ensure that all outstanding callbacks have completed execution and that all pending callbacks on the thread pool's queue have been canceled before the callback function returns.

Earlier, the SetThreadpoolCallbackLibrary function was described as a way to prevent a DLL from being unloaded prematurely while a callback function is still executing code inside the DLL. The cost of this insurance is fairly high because of the overhead involved in acquiring and releasing the loader lock before and after the invocation of the callback function. Note also that there is a single loader lock in the process and it may have heavy contention on it, which means that relying on the thread pool's mechanism to ensure a DLL doesn't unload prematurely may have a negative impact on the performance of the application. Depending upon the application scenario, it may be more efficient to build an application-specific mechanism that provides for safe unloading of a DLL using a combination of the functions described in this section and Window's synchronization primitives.

Try It Out with the Sample Applications

As you've seen, the new thread pool component includes many improvements to help you easily write applications that are both highly reliable and scalable. Key among these improvements is the ability to host more than one thread pool per process, where each thread pool has its own separate set of characteristics so you can partition processes by type of work performed.

I hope this overview of the new thread pool has whetted your appetite to explore how using it can benefit your applications. To get you started, I've included two sample applications with this article. The first, ThreadPoolDemo, lets you experiment with work, wait, and timer objects so you can explore how they work. ThreadPoolDemo will run on either the process's default thread pool or on a custom thread pool, allowing the minimum and maximum thread counts to be specified through command line parameters.

The work object demonstration, which is executed by specifying the -Work command-line option, creates a work object. By using the supplied count with the command-line parameter -I, it will submit the work item to the thread pool the number of times specified. You can use the -B option to define how long the callback function should block, and the -E option to specify how long the callback function should execute. By default, the program will run until all the submitted work items have been executed. Specifying either –CC or –CW on the command line causes the application to immediately call CloseThreadpoolCleanupGroupMembers after submitting the work item the specified number of times. The difference between the two options is that –CC cancels all callbacks that have not yet started while –CW waits for them to execute before returning from the CloseThreadpoolCleanupGroupMembers call.

You can also experiment with timer objects. You can configure multiple timer objects where each can have its own due time and an optional period and window. Using multiple timers with different window sizes allows you to see the effect of the system coalescing timer expirations together.

Finally, the wait-object demonstration let's you define one or more event specifications for the thread pool to wait on. Each event specification can include an optional due time to indicate when the event is to be signaled, as well as an optional timeout interval for defining when the wait should expire. These options let you experiment with combinations of events that become signaled, timeout from waits, or never become signaled and never timeout.

For details on command-line parameters for each of the callback object types, type one of the following in a command prompt: "ThreadPoolDemo –Work ?", "ThreadPoolDemo –Timer ?", or "ThreadPoolDemo –Wait ?".

The second sample application included with this article is called CopyFile. Essentially it is an update of the Windows SDK file-copying example that demonstrates how a completion port works. CopyFile will copy a source file to a destination file using the thread pool and demonstrates how I/O Completion Objects work. Typing "CopyFile –Usage" at the command line displays a complete description of the program parameters in the console window.

I'd like to thank Rob Earhart, Eric Li, and Sandeep Ranade for answering my questions and providing insightful feedback; and I'd like to thank Rob Shewan for reviewing the content and providing me with valuable feedback.

Robert Saccone is a Principal Architect in the Forefront Server Security group. His areas of interest are large-scale software design, distributed systems, and operating systems implementations. You can contact him at robsaccone@hotmail.com.

© 2007 Microsoft Corporation and CMP Media, LLC. All rights reserved; reproduction in part or in whole without permission is prohibited.


WPF Threads: Build More Responsive Apps With The Dispatcher

WPF Threads

Build More Responsive Apps With The Dispatcher

Shawn Wildermuth
This article discusses:
  • Threading in WPF
  • Using the Dispatcher
  • Non-UI thread handling
  • Using timers
This article uses the following technologies:
.NET Framework 3.0, WIndows Presentation Foundation
Contents
The Threading Model
DispatcherObject
Using the Dispatcher
BackgroundWorker
DispatcherTimer

I
t would be a shame if you put months of your life into creating an intuitive, natural, and even beautiful interface only to have your users tapping their fingers on their collective desks waiting for it to respond. Watching your application screech to a halt because of a long-running process is just painful. However, creating applications that are responsive takes some careful planning, which usually entails having long-running processes work in other threads so that the UI thread is free to keep up with the user.

My first real experience with responsiveness goes way back to Visual C++® and MFC and the first grid I ever wrote. I was helping write a pharmacy application that had to be able to show every drug in a complex formulary. The problem was that there were 30,000 drugs, so we decided to give the appearance of responsiveness by filling the first screenful of drugs in the UI thread (in about 50 milliseconds), then using a background thread to finish filling the non-visible drugs (in about 10 seconds). The project went well and I learned the valuable lesson that user perception can be more important than reality.

Windows® Presentation Foundation (WPF) is a great technology for creating compelling user interfaces, but that doesn't mean you don't have to take the responsiveness of your application into account. The simple fact is, no matter what type of long-running processes are involved—whether getting large results from a database, making asynchronous Web service calls, or any number of other potentially intensive operations—making your application more responsive is guaranteed to make your users much happier in the long run. But before you can start using an asynchronous programming model in your WPF application, it is important that you understand the WPF threading model. In this article I will not only introduce you to that threading model, but I'll also show you how the Dispatcher-based objects work and explain how to use the BackgroundWorker so that you can create compelling and responsive user interfaces.

The Threading Model

All WPF applications start out with two important threads, one for rendering and one for managing the user interface. The rendering thread is a hidden thread that runs in the background, so the only thread that you ordinarily deal with is the UI thread. WPF requires that most of its objects be tied to the UI thread. This is known as thread affinity, meaning you can only use a WPF object on the thread on which it was created. Using it on other threads will cause a runtime exception to be thrown. Note that the WPF threading model interoperates well with Win32®-based APIs. This means that WPF can host or be hosted by any HWND-based API (Windows Forms, Visual Basic®, MFC, or even Win32).

The thread affinity is handled by the Dispatcher class, a prioritized message loop for WPF applications. Typically your WPF projects have a single Dispatcher object (and therefore a single UI thread) that all user interface work is channeled through.

Unlike typical message loops, each work item that is sent to WPF is sent through the Dispatcher with a specific priority. This allows for both ordering of items by priority and deferring certain types of work until the system has time to handle them. (For example, some work items can be deferred until the system or application is idle.) Supporting item prioritization allows WPF to allow certain types of work to have more access, and therefore more time on a thread, than other work.

Later in this article I will demonstrate that the rendering engine is allowed to update the user interface at a higher priority than the input system. This means that animations will continue to update the user interface no matter what the user is doing with the mouse, keyboard, or ink system. This can make the user interface appear more responsive. For example, let's assume you were writing a music-playing application (like Windows Media® Player). You would most likely want the information about the music playing (including the progress bar and other information) to show up whether the user was using the interface or not. To the user, this can make the interface appear more responsive to what they are most interested in (listening to music, in this case).

In addition to using the Dispatcher's message loop to channel items of work through the user interface thread, every WPF object is aware of the Dispatcher that is responsible for it (and therefore, the UI thread that it lives on). This means that any attempts to update WPF objects from secondary threads will fail. This is the responsibility of the DispatcherObject class.

DispatcherObject

In the hierarchy of classes in WPF, most derive centrally from the DispatcherObject class (through other classes). As shown in Figure 1, you can see that the DispatcherObject virtual class is sandwiched just below Object in the hierarchy of most WPF classes.

Figure 1 DispatcherObject Derivation
Figure 1 DispatcherObject Derivation

The DispatcherObject class has two chief duties: to provide access to the current Dispatcher that an object is tied to and provide methods to check (CheckAccess) and verify (VerifyAccess) that a thread has access to the object (derived from DispatcherObject). The difference between CheckAccess and VerifyAccess is that CheckAccess returns a Boolean value that represents whether the current thread can use the object and VerifyAccess throws an exception if the thread does not have access to the object. By providing this basic functionality, all the WPF objects support being able to determine whether they can be used on a particular thread—specifically, the UI thread. If you are writing your own WPF objects, such as controls, all methods you use should call VerifyAccess before they perform any work. This guarantees that your objects are only used on the UI thread, as shown in Figure 2.

Figure 2 Using VerifyAccess and CheckAccess (Close Figure 2)
public class MyWpfObject : DispatcherObject
{
    public void DoSomething()
    {
        VerifyAccess();

        // Do some work
    }

    public void DoSomethingElse()
    {
        if (CheckAccess())
        {
            // Something, only if called
            // on the right thread
        }
    }
}

With this in mind, be careful to be on the UI thread when calling any DispatcherObject-derived object such as Control, Window, Panel, and so on. If you make a call to a DispatcherObject from a non-UI thread, it will throw an exception. Instead, if you are working on a non-UI thread, you'll need to use the Dispatcher to update DispatcherObjects.

Using the Dispatcher

The Dispatcher class provides a gateway to the message pump in WPF and provides a mechanism to route work for processing by the UI thread. This is necessary to meet the thread affinity demands, but since the UI thread is blocked for each piece of work routed through the Dispatcher, it is important to keep the work that the Dispatcher does small and quick. It is better to break apart larger pieces of work for the user interface into small discrete blocks for the Dispatcher to execute. Any work that doesn't need to be done on the UI thread should instead be moved off onto other threads for processing in the background.

Typically you will use the Dispatcher class to send worker items to the UI thread for processing. For example, if you want to do some work on a separate thread using the Thread class, you could create a ThreadStart delegate with some work to do on a new thread as shown in Figure 3.

Figure 3 Updating UI with Non-UI Thread—The Wrong Way (Close Figure 3)
// The Work to perform on another thread
ThreadStart start = delegate()
{
    // ...

    // This will throw an exception
    // (it's on the wrong thread)
    statusText.Text = "From Other Thread";
};

// Create the thread and kick it started!
new Thread(start).Start();

This code fails because setting the Text property of the statusText control (a TextBlock) is not being called on the UI thread. When the code attempts to set the Text on the TextBlock, the TextBlock class internally calls its VerifyAccess method to ensure that the call is coming from the UI thread. When it determines the call is from a different thread, it throws an exception. So how can you use the Dispatcher to make the call on the UI thread?

The Dispatcher class provides access to invoke code on the UI thread directly. Figure 4 shows the use of the Dispatcher's Invoke method to call a method called SetStatus to change the TextBlock's Text property for you.

Figure 4 Updating the UI (Close Figure 4)
// The Work to perform on another thread
ThreadStart start = delegate()
{
  // ...

  // Sets the Text on a TextBlock Control.
  // This will work as its using the dispatcher
  Dispatcher.Invoke(DispatcherPriority.Normal,
                    new Action<string>(SetStatus),
                    "From Other Thread");
};
// Create the thread and kick it started!
new Thread(start).Start();

The Invoke call takes three pieces of information: the priority of the item to be executed, a delegate that describes what work to perform, and any parameters to pass into the delegate described in the second parameter. By calling Invoke, it queues up the delegate to be called on the UI thread. Using the Invoke method ensures that you are going to block until the work is performed on the UI thread.

As an alternative to using the Dispatcher synchronously, you can use the BeginInvoke method of the Dispatcher to asynchronously queue up a work item for the UI thread. Calling the BeginInvoke method returns an instance of the DispatcherOperation class that contains information about the execution of the work item, including the current status of the work item and the result of the execution (once the work item has completed). The use of the BeginInvoke method and the DispatcherOperation class is shown in Figure 5.

Figure 5 Updating the UI Asynchronously (Close Figure 5)
// The Work to perform on another thread
ThreadStart start = delegate()
{
    // ...

    // This will work as its using the dispatcher
    DispatcherOperation op = Dispatcher.BeginInvoke(
        DispatcherPriority.Normal,
        new Action<string>(SetStatus),
        "From Other Thread (Async)");

    DispatcherOperationStatus status = op.Status;
    while (status != DispatcherOperationStatus.Completed)
    {
        status = op.Wait(TimeSpan.FromMilliseconds(1000));
        if (status == DispatcherOperationStatus.Aborted)
        {
            // Alert Someone
        }
    }
};

// Create the thread and kick it started!
new Thread(start).Start();

Unlike a typical message pump implementation, the Dispatcher is a priority-based queue of work items. This allows for better responsiveness because the more important pieces of work are executed before less important pieces of work. The nature of the prioritization is exemplified by the priorities that are specified in the DispatchPriority enumeration (as shown in Figure 6).

Figure 6 DispatchPriority Prioritization Levels (in Priority Order) (Close Figure 6)

Priority | Description
Inactive | Work items are queued but not processed.
SystemIdle | Work items are only dispatched to the UI thread when the system is idle. This is the lowest priority of items that are actually processed.
ApplicationIdle | Work items are only dispatched to the UI thread when the application itself is idle.
ContextIdle | Work items are only dispatched to the UI thread after higher-priority work items are processed.
Background | Work items are dispatched after all layout, rendering, and input items are processed.
Input | Work items are dispatched to the UI thread at the same priority as user input.
Loaded | Work items are dispatched to the UI thread after all layout and rendering are complete.
Render | Work items are dispatched to the UI thread at the same priority as the rendering engine.
DataBind | Work items are dispatched to the UI thread at the same priority as data binding.
Normal | Work items are dispatched to the UI thread with normal priority. This is the priority at which most application work items should be dispatched.
Send | Work items are dispatched to the UI thread with the highest priority.

Generally you should always use DispatcherPriority.Normal for the priority of work items that update the appearance of the UI (like the example I used earlier). But there are times when you should use different priorities. Of particular interest are the three idle priorities (ContextIdle, ApplicationIdle, and SystemIdle). These priorities allow you to specify work items that are only executed under very low workloads.

BackgroundWorker

Now that you have a sense of how the Dispatcher works, you might be surprised to know that you will not find use for it in most cases. In Windows Forms 2.0, Microsoft introduced a class for non-UI thread handling to simplify the development model for user interface developers. This class is called the BackgroundWorker. Figure 7 shows typical usage of the BackgroundWorker class.

Figure 7 Using a BackgroundWorker in WPF (Close Figure 7)
BackgroundWorker _backgroundWorker = new BackgroundWorker();

...

// Set up the Background Worker Events
_backgroundWorker.DoWork += _backgroundWorker_DoWork;
backgroundWorker.RunWorkerCompleted +=
    _backgroundWorker_RunWorkerCompleted;

// Run the Background Worker
_backgroundWorker.RunWorkerAsync(5000);

...

// Worker Method
void _backgroundWorker_DoWork(object sender, DoWorkEventArgs e)
{
    // Do something
}

// Completed Method
void _backgroundWorker_RunWorkerCompleted(
    object sender,
    RunWorkerCompletedEventArgs e)
{
    if (e.Cancelled)
    {
        statusText.Text = "Cancelled";
    }
    else if (e.Error != null)
    {
        statusText.Text = "Exception Thrown";
    }
    else
    {
        statusText.Text = "Completed";
    }
}

The BackgroundWorker component works well with WPF because underneath the covers it uses the AsyncOperationManager class, which in turn uses the SynchronizationContext class to deal with synchronization. In Windows Forms, the AsyncOperationManager hands off a WindowsFormsSynchronizationContext class that derives from the SynchronizationContext class. Likewise, in ASP.NET it works with a different derivation of SynchronizationContext called AspNetSynchronizationContext. These SynchronizationContext-derived classes know how to handle the cross-thread synchronization of method invocation.

In WPF, this model is extended with a DispatcherSynchronizationContext class. By using BackgroundWorker, the Dispatcher is being employed automatically to invoke cross-thread method calls. The good news is that since you are probably already familiar with this common pattern, you can continue using BackgroundWorker in your new WPF projects.

DispatcherTimer
WPF Threading Resources
  • Windows Presentation Foundation Virtual Labs
  • WPF in the .NET Framework Developer Center
  • WPF Fundamentals: Threading Model, MSDN Library
  • Programming the Windows Presentation Foundation by Chris Sells and Ian Griffiths (O'Reilly, 2005)

Periodic execution of code is a common task in development within the Microsoft® .NET Framework, but using timers in .NET has been, at best, confusing. If you look for a Timer class in the .NET Framework Base Class Library (BCL) you will find no fewer than three Timer classes: System.Threading.Timer, System.Timers.Timer, and System.Windows.Forms.Timer. Each of these timers is different. Alex Calvo's article in MSDN Magazine explains when to use each of these Timer classes (see msdn.microsoft.com/msdnmag/issues/04/02/TimersinNET).

For WPF applications, there is a new type of timer that utilizes the Dispatcher—the DispatcherTimer class. Like other timers, the DispatcherTimer class supports specifying an interval between ticks as well as the code to run when the timer's event fires. You can see a fairly pedestrian use of the DispatcherTimer in Figure 8.

Figure 8 DispatcherTimer Class in Action (Close Figure 8)
// Create a Timer with a Normal Priority
_timer = new DispatcherTimer();

// Set the Interval to 2 seconds
_timer.Interval = TimeSpan.FromMilliseconds(2000);

// Set the callback to just show the time ticking away
// NOTE: We are using a control so this has to run on
// the UI thread
_timer.Tick += new EventHandler(delegate(object s, EventArgs a)
{
    statusText.Text = string.Format(
        "Timer Ticked:  {0}ms", Environment.TickCount);
});

// Start the timer
_timer.Start();

Because the DispatcherTimer class is tied to Dispatcher you can also specify the DispatcherPriority as well as which Dispatcher to use. The DispatcherTimer class uses the Normal priority as the current Dispatcher by default, but you can override these values:

_timer = new DispatcherTimer(
    DispatcherPriority.SystemIdle, form1.Dispatcher);

It is well worth all the effort involved in planning your worker processes to enable more responsive applications. Doing some initial research can make that planning more succesful. I suggest exploring some of the sites mentioned in the "WPF Threading References" sidebar before you begin—along with this article, they should give you a good foundation for developing responsive apps.

Shawn Wildermuth is a Microsoft MVP, MCSD.NET, MCT, and the founder of Wildermuth Consulting Services. Shawn is also the author of Pragmatic ADO.NET (Addison-Wesley, 2002) and the coauthor of four Microsoft Certification Training Kits as well as the upcoming Prescriptive Data Architectures. He can be contacted through his Web site at wildermuthconsulting.com.


Parallel LINQ: Running Queries On Multi-Core Processors

Parallel LINQ

Running Queries On Multi-Core Processors

Joe Duffy and Ed Essey
THis article is based on the Parallel FX library, which is currently in development. All information herein is subject to change.
This article discusses:
  • PLINQ basics
  • The PLINQ programming model
  • Concurrent exceptions
  • Output ordering
This article uses the following technologies:
Parallel FX Library
Contents
From LINQ to PLINQ
PLINQ Programming Model
Processing Query Output
Concurrent Exceptions
Ordering in the Output Results
Side Effects
Putting PLINQ to Work

M
ulti-core processors are here. Once pervasive mainly in servers and desktop PCs, now multi-core processors are being used in mobile phones and PDAs, resulting in great benefits in power consumption. Responding to the increased availability of multi-processor platforms, Parallel Language Integrated Query (PLINQ) offers an easy way to take advantage of parallel hardware, including traditional multi-processor computers and the newer wave of multi-core processors.

PLINQ is a query execution engine that accepts any LINQ-to-Objects or LINQ-to-XML query and automatically utilizes multiple processors or cores for execution when they are available. The change in programming model is tiny, meaning you don't need to be a concurrency guru to use it. In fact, threads and locks won't even come up unless you really want to dive under the hood to understand how it all works. PLINQ is a key component of Parallel FX, the next generation of concurrency support in the Microsoft® .NET Framework.

Using technologies like PLINQ will become increasingly crucial to ensuring the scalability of software on future parallel microprocessor architectures. By utilizing LINQ at choice places throughout your applications today—such as where you have data- or compute-intensive operations that can be expressed as queries—you will ensure that those fragments of your programs continue to perform better when PLINQ becomes available and the machines running your application grow from 2 to 4 to 32 processors and beyond. And even if you only run that code on a single-processor machine, the overhead of PLINQ is typically so small that you won't notice a difference. In addition, the data parallel nature of PLINQ ensures your programs will continue to scale as the size of your data sets increases.

In this article, we review the goals of the PLINQ technology, where it fits into the broader .NET Framework and other concurrency offerings, and what it looks like from the perspective of LINQ developers. We conclude with some example scenarios where PLINQ has already shown tremendous value.

Note that the Parallel FX library, which includes PLINQ, is currently still under development, but the first Community Tech Preview (CTP) will be available from MSDN® in Fall '07. Watch blogs.msdn.com/somasegar for details.

From LINQ to PLINQ

When people first hear about the PLINQ project, they usually ask: why parallelize LINQ? The simple answer is that LINQ's set-at-a-time programming model for expressing computations places an emphasis on specifying what needs to get done instead of how it is to be done. Without LINQ, the how part would typically otherwise be expressed through the use of loops and intermediary data structures, but by encoding so much specific information, the compiler and runtime cannot parallelize as easily. LINQ's declarative nature, on the other hand, leaves the flexibility for a clever implementation like PLINQ to use parallelization to obtain the same results.

The follow-up question is inevitably: if you're going to query enough data for PLINQ to make sense, why not just use a database? And the answer to this question takes the form of a rhetorical question: what code would you have written if you weren't using LINQ? Well, you'd likely be doing the same amount of data- and compute-intensive work, but it would have been captured inside an unstructured series of for loops, function calls, and so forth. So this question implies that all programs should reside in the database, which I'm sure very few people would agree with.

With PLINQ you don't need to move your entire database server processing logic over to in-memory LINQ-to-Objects queries in the client. Rather, PLINQ offers an incremental way of taking advantage of parallelism for existing solutions to existing problems. If your problem is data-intensive enough and would traditionally demand that you pursue a database solution, you should still pursue such a solution. PLINQ changes very little of that. However, if you have several data sources that you'd like to query together—possibly heterogeneous, spanning databases, XML files, and so on—PLINQ can take over and parallelize once data is on the client.

Naturally, people then ask: why doesn't LINQ-to-Objects itself just run queries in parallel? The parallelism would be completely hidden, and developers wouldn't need to change a single line of code to reap the benefits of it. Sadly, there are some subtle gotchas that can arise with the move from LINQ to PLINQ that prohibit us from realizing this vision, at least for PLINQ 1.0. These will be discussed more later in the article.

PLINQ Programming Model

Using PLINQ is almost exactly like using LINQ-to-Objects and LINQ-to-XML. You can use any of the operators available through C# 3.0 and Visual Basic® 9.0 query comprehension syntax or the System.Linq.Enumerable class, including OrderBy, Join, Select, Where, and so on. PLINQ supports all of the LINQ operators, not just those available in language comprehensions. And you can query any in-memory collection such as T[], List<T>, or any other kind of IEnumerable<T> in addition to XML documents loaded using the System.Xml.Linq APIs. If you already have a bunch of LINQ queries, PLINQ is equipped to run them.

LINQ-to-SQL and LINQ-to-Entities queries will still be executed by the respective databases and query providers, so PLINQ does not offer a way to parallelize those queries. If you wish to process the results of those queries in memory, including joining the output of many heterogeneous queries, then PLINQ can be quite useful.

Aside from writing LINQ queries the same way you're used to writing them, there are two extra steps needed to make use of PLINQ:

  1. Reference the System.Concurrency.dll assembly during compilation.
  2. Wrap your data source in an IParallelEnumerable<T> with a call to the System.Linq.ParallelEnumerable.AsParallel extension method.

Calling the AsParallel extension method in Step 2 ensures that the C# or Visual Basic compiler binds to the System.Linq.ParallelEnumerable version of the standard query operators instead of System.Linq.Enumerable. This gives PLINQ a chance to take over control and to execute the query in parallel. AsParallel is defined as taking any IEnumerable<T>:

public static class System.Linq.ParallelEnumerable {
    public static IParallelEnumerable<T> AsParallel<T>(
        this IEnumerable<T> source);
    ... the other standard query operators ...
}

IParallelEnumerable<T> derives from IEnumerable<T> and adds very little to it, being there simply to facilitate binding to PLINQ's ParallelEnumerable query provider, taking advantage of the new extension method support in C# 3.0 and Visual Basic .NET 9.0. The interface derives from IEnumerable<T> so that you can still foreach over instances and pass them to other APIs that expect IEnumerable<T>. The standard query operators defined on ParallelEnumerable mirror those on Enumerable with the only difference being that each takes an IParallelEnumerable<T> as its extension source argument rather than IEnumerable<T>, returns an IParallelEnumerable<T> rather than IEnumerable<T> (except for the aggregations that just return simple types), and of course uses parallelism internally for query evaluation.

For example, take a simple LINQ query defined in C#:

IEnumerable<T> data = ...;
var q = data.Where(x => p(x)).Orderby(x => k(x)).Select(x => f(x));
foreach (var e in q) a(e);

All that is required to use PLINQ in this case is adding a call to AsParallel on data:

IEnumerable<T> data = ...;
var q = data.AsParallel().Where(x => p(x)).Orderby(x => k(x)).Select(x => f(x));
foreach (var e in q) a(e);

This can be written more concisely using the C# query comprehension syntax, in which case the PLINQ version looks like this:

IEnumerable<T> data = ...;
var q = from x in data.AsParallel() where p(x) orderby k(x) select f(x);
foreach (var e in q) a(e);

Once you have made this change, PLINQ will transparently execute the Where, OrderBy, and Select on all of the available processors using classic data parallel evaluation techniques. PLINQ uses deferred execution just like LINQ, meaning the query doesn't begin running until you foreach over it, call GetEnumerator directly, or force the results into a list through some other API such as ToList or ToDictionary. When the query executes, PLINQ will arrange for parts of the query to run on the available processors through the hidden use of multiple threads. You don't even need to understand how all of this is done; you just see better performance and better utilization of the available processors.

Though it's not obvious, the inferred type of q differs between the ordinary LINQ-to-Objects and PLINQ queries shown previously. In the first example, q is typed as IEnumerable<U>, where U is whatever type the f method passed to the Select operator returns. In the second example, however, q is typed as IParallelEnumerable<U>. This usually doesn't matter: if you've declared q to explicitly have type IEnumerable<U>, for instance, the change to AsParallel will still work since IParallelEnumerable<U> derives from IEnumerable<U>. But it does mean that any subsequent use of q will be treated like an IParallelEnumerable<U>. For example, if you subsequently query it, PLINQ will be chosen as the query provider.

Note that some LINQ operators are binary—they take two IEnumerable<T>s as input. Join is a perfect example of such an operator. In these cases, the type of the left-most data source determines whether LINQ or PLINQ is used. Thus you need only call AsParallel on the first data source for your query to run in parallel:

IEnumerable<T> leftData = ..., rightData = ...;
var q = from x in leftData.AsParallel()
        join y in rightData on x.a == y.b
        select f(x, y);

All of this discussion has assumed you're using extension methods to write your queries. If you have chosen instead to call methods on the Enumerable class directly, then you will have a little more work to do to move over to PLINQ. In addition to the call to AsParallel, you must also reference the ParallelEnumerable type. For example, imagine the above query was written by calling Enumerable directly:

IEnumerable<T> data = ...;
var q = Enumerable.Select(
            Enumerable.OrderBy(
                Enumerable.Where(data, (x) => p(x)),
            (x) => k(x)),
        (x) => f(x));
foreach (var e in q) a(e);

To use PLINQ, the query would have to be rewritten like this:

IEnumerable<T> data = ...;
var q = ParallelEnumerable.Select(
            ParallelEnumerable.OrderBy(
                ParallelEnumerable.Where(data.AsParallel(), (x) =>    p(x)),
            (x) => k(x)),
        (x) => f(x));
foreach (var e in q) a(e);

For obvious reasons, using comprehensions and extension methods is a more convenient way of writing your queries and carries the added benefit of making it much easier to move to PLINQ.

And that's it! These are the only changes required to use PLINQ in place of LINQ-to-Objects. Because LINQ-to-XML exposes XML documents as IEnumerable<T> data structures, everything said so far applies to querying XML content, too.

Processing Query Output

As already noted, due to deferred evaluation, parallelism doesn't get introduced until you start processing the output of the query. If you're familiar with IEnumerable<T>, this equates to calling the GetEnumerator method. There are three basic ways that PLINQ queries can be processed, each leading to a slightly different model for parallelism.

The first is pipelined processing, in which case the thread doing the enumeration is separate from the threads devoted to running the query. PLINQ will use many threads for query execution, but will reduce the degree of parallelism by one so that the enumerating thread is not interfered with. For instance, if you have eight processors available, seven of them will run the PLINQ query while the remaining processor runs the foreach loop on the output of the PLINQ query as elements become available. This carries the benefit of allowing more incremental processing of output, thus reducing the memory requirements necessary to hold the results; however, having many producer threads and only a single consumer thread can often lead to uneven work distribution, resulting in processor inefficiency.

The second model is stop-and-go processing. In this model, the thread that starts the enumeration joins all of the other threads to execute the query. Once all threads have finished producing the complete set of output, the thread then proceeds to enumerating the output. This has the benefit that all processing power is devoted to creating the output as quickly as possible. It is also slightly more efficient than pipelined processing because there is less incremental synchronization overhead in the implementation: PLINQ can be more intelligent about these things because it knows exactly where the output data is going and how it will be accessed. If the work distribution is uneven between the consumers and producer, this is usually a more appropriate method of consumption.

Finally, there is inverted enumeration. A lambda function is provided to PLINQ that is run in parallel, once for each element in the output. This is the most efficient mechanism because there is much more parallelism exposed to PLINQ, and the implementation avoids costly operations such as merging output from multiple threads. But it has the drawbacks that you cannot simply use a foreach loop, you must use a special ForAll API, and you must be careful that the lambdas do not rely on shared state. Otherwise, introducing parallelism will render your queries incorrect and can cause unpredictable crashes or data corruption. If you can express your problem in terms of this API, however, it is always the preferred method.

Which of these three models you use depends on what you do with the query results. The default is the first—pipelined processing. As soon as MoveNext is called on the resulting query enumerator, a set of additional worker threads will execute the query, and results are returned from this and all subsequent MoveNext calls as they become available. If a call to MoveNext is made and no output is ready from the query producer threads, the calling thread will block until an element is available. If you just use foreach to process the output of a PLINQ query, this is what you will get:

var q = ... some query ...;
foreach (var e in q) {
    a(e); // this runs in parallel with the execution of 'q'
}

The IParallelEnumerable<T> interface actually offers an overload of GetEnumerator that takes a bool argument called pipelined, allowing you to choose stop-and-go processing instead (true means pipelined and false means stop-and-go). Upon the first subsequent call to MoveNext, the entire query will be executed and the call will only return when all output is available. Subsequent calls to MoveNext just enumerate a buffer containing the output:

var q = ... some query ...;
using (var e = q.GetEnumerator(false)) {
    while (e.MoveNext()) {
        // after the 1st call, the query is finished executing
        // we then just enumerate the results from an in-memory list
        a(e.Current);
    }
}

There are a few special cases where stop-and-go processing is used as the default: if you use the ToArray or ToList methods, these operators will internally force a stop-and-go operation. If you have a sort in your query, stop-and-go will be used instead because pipelining the output of a sort is wasteful. A sort exhibits extremely high latency (because it generally needs to sort the whole input before producing a single output element), and so PLINQ prefers to devote all processing power to completing the sort as quickly as possible.

In order to use inverted enumeration, you must use a different PLINQ-specific API:

public static class System.Linq.ParallelEnumerable {
    public static void ForAll<T>(
        this IParallelEnumerable<T> source, Action<T> action);
    ... the other standard query operators ...
}

Using the ForAll API looks quite a bit like using a foreach loop, as you just saw:

var q = ... some query ...;
q.ForAll(e => a(e));

Concurrent Exceptions
Compelling Scenarios

While reading this article, you have probably already begun to imagine some ways to use PLINQ in your own applications. Perhaps you are already using LINQ today and want to improve your application's scalability on machines with multiple processors or multiple cores. Of course, PLINQ can make your current programs run faster, but it also allows you to do more compute work and operate on larger data sizes in the same amount of time, while processing streams of data at a faster rate. In doing all of this, the new PLINQ technology might open up new application possibilities that you could not previously attempt.

Let's look at a few illustrations of scenarios in which multi-core and PLINQ open up new doors. Consider a music producer working in a sound studio who wants to apply a series of effects on raw instrument sounds to produce a more aesthetically pleasing, production-quality master track. The company that provides his mixing software could apply these effects using PLINQ. These effects are usually composed of filters and projections over large streams of data (the raw music). PLINQ could greatly speed up the production time and utilize more powerful hardware as it becomes available. This approach might even allow music transformations in near real time, instead of doing complete post-production processing.

Likewise, consider a foreign exchange currency trader who looks for arbitrage conditions (inefficiencies in the market) in order to make a profit. Such shifts are minute and disappear as the market is constantly reaching equilibrium, requiring very fast trades. Querying stock trade information using parallelism via PLINQ could enable close to real time decision making, informed by large amounts of data and complicated analysis and computations.

These are just a few samples of the ways in which the speedup provided by PLINQ on multi-core hardware can provide a business advantage. Other domains offer similar opportunities, such as healthcare, economics, geological modeling, scientific computing, traffic control and simulations, gaming, artificial intelligence, machine learning, linguistic analysis, and the list goes on.

Although the statements earlier about PLINQ's parallelization process being entirely transparent were mostly true, there are a small number of places where the use of parallelism can leak through the simple abstractions presented above. These are the gotchas that were alluded to earlier. Happily, most of them are minor, but you should be aware of them anyway.

Any lambdas or query operators that throw an exception stop sequential LINQ queries from executing right away. That's because when only one processor is used to run the query, elements are processed one after the other, sequentially: if an operator fails on one of them, the exception is thrown immediately and the subsequent elements will not even be considered. The same is not true of PLINQ.

As an illustration, take a look at this (contrived) query:

object[] data = new object[] { "foo", null, null, null };
var q = data.Select(x => x.ToString());
foreach (var e in q) Console.WriteLine(e);

Every time you run it with LINQ, it will succeed in running ToString on the first array element, and then it will fail with a NullReferenceException trying to call ToString on the second. You never get to the third or fourth element. When multiple processors are involved, however, as is the case with PLINQ, you have the possibility that multiple exceptions can happen in parallel. Depending on how PLINQ decides to subdivide the problem, you may see failures for 1, 2, and 3, all simultaneously, or any combination of those, including possibly 3, but not 1 or 2.

To deal with this, PLINQ uses a slightly different exception model than LINQ to communicate failures. When an exception occurs on one of the PLINQ threads, the system first tries to stop all other threads from running as quickly as possible. This process happens completely transparently. But this may or may not be accomplished in time to prevent other exceptions from happening concurrently and, indeed, they may have already occurred by the time PLINQ gets involved. Once all threads have shut down, the full set of exceptions that have occurred will be aggregated into a new System.Concurrency.MultipleFailuresException object and that new aggregate exception object will be rethrown. Each exception that occurred is subsequently accessible through the InnerExceptions property, of type Exception[], including unperturbed stack traces.

PLINQ actually always throws a single MultipleFailuresException when an unhandled exception terminates a query's execution, even if only one exception is actually thrown. In the previous example, that means PLINQ always wraps the NullReferenceExceptions in a MultipleFailuresException. If it didn't and you wanted to catch an exception of a particular type, you'd have to write multiple catch clauses. Clearly you usually don't catch certain kinds of exceptions, but if you had wanted to, you would have had to write the following and duplicate a bunch of logic:

try
{
    // query...
}
catch (NullReferenceException)
{ ... }
catch (MultipleFailuresException)
{ ... }

Not only is this clumsy, but developers would be apt to forget about one or the other, leading to bugs that happen only under some circumstances and configurations.

This can unfortunately make debugging more difficult. If an exception goes unhandled and you attach a debugger, you will break into the call to GetEnumerator (if you're calling foreach over the query results) rather than where your exception originated from to begin with. This is similar to what occurs with the asynchronous programming model (BeginXX/EndXX) in the .NET Framework today. Thankfully, PLINQ preserves the original stack traces, so if you expand the MultipleFailuresException object and look at its InnerExceptions property, you will find the full set of exceptions with the complete original stack traces available.

Ordering in the Output Results

Say you've written the following code in LINQ:

int[] data  = new int[] { 0, 1, 2, 3 };
int[] data2 = (from x in data select x * 2).ToArray();

Can you predict the contents of data2? The question seems so simple that it's silly to even consider. Everybody would say: { 0, 2, 4, 6 }. But if you just change the code as shown here, the possible contents of data2 actually differs:

int[] data  = new int[] { 0, 1, 2, 3 };
int[] data2 = (from x in data.AsParallel() select x * 2).ToArray();

In this case, { 0, 2, 4, 6 } is surely possible, but so is { 6, 0, 2, 4 }, or any other permutation of these four numbers.

This is so because PLINQ runs the query in parallel and the results are made available as soon as they become available, no matter whether you are iterating over the query with foreach or marshaling the results into an array with ToArray. The LINQ ordering is simply a byproduct of the fact that its implementation processes input sequentially. Conversely, the PLINQ ordering is determined by the nondeterministic scheduling of parallel units of work, which is apt to change wildly from one execution to the next.

This was an explicit design decision made by the PLINQ team. Historically, queries have not guaranteed anything about ordering. If you take a look at SQL Server™, for example, unless you have specified an order by clause in the query text, the ordering will be dependent on many things: whether an index is used in the query, the layout of records on disk, and so on. In fact, it can also be nondeterministic, because SQL Server can use parallelism in the evaluation of queries too!

Because users frequently need to preserve ordering, and to alleviate some minor challenges for some people trying to migrate from LINQ, PLINQ offers a way of opting in to order preservation. Order preservation simply ensures that, provided there are no intervening sort operations, the relative ordering among output elements is strongly tied to the relative ordering among input elements. If you wanted to ensure that the output of the above query was always {0, 2, 4, 6 }, then you can use the following query instead:

int[] data  = new int[] { 0, 1, 2, 3 };
int[] data2 = (from x in data.AsParallel(QueryOptions.PreserveOrdering)
               select x * 2).ToArray();

Order preservation is not free. In fact, it can substantially impact the performance and scaling of your queries. This is because PLINQ will logically insert a sort operation at the end, and the sort is an operator that does not scale perfectly with an increase in the number of processors. To get an idea of what this means, the previous query is logically equivalent to the following query:

int[] data  = new int[] { 0, 1, 2, 3 };
int[] data2 = data.AsParallel().
                  Select((x, i) => new { x, i }). // remember indices
                  Select((x) => new { x * 2, i }). // (in original)
                  OrderBy((x) => x.i). // ensure order is preserved
                  Select((x) => x.x). // get rid of indices from output
                  ToArray(); // (in original)

The steps introduced by PLINQ to support order preservation are in red. As you can see, it's quite a bit of work! Obviously PLINQ implements this functionality in a much more efficient manner than if you had just written this version of the query, but the steps are logically equivalent.

Side Effects
PLINQ Resources
  • Joe Duffy's blog posts on PLINQ
  • Channel 9 video interview with Anders Hejlsberg on LINQ
  • The LINQ Project at the .NET Framework Developer Center
  • The Evolution of LINQ and Its Impact on the Design of C# by Anson Horton (MSDN Magazine, June 2007)
  • LINQ Discussion in MSDN Forums

PLINQ relies on something called statistical purity: most LINQ queries do not mutate data structures or perform impure operations most of the time. Another way of saying this is that most LINQ queries are strictly functional; they take some data as input, perform some calculations, and create an entirely separate copy of the data, with some changes, as output. But this best practice usage isn't enforced in any way by the compilers or runtime. If people have written queries that break this common usage pattern, then the shift to PLINQ can become quite a bit more complicated.

As an example, consider this LINQ query:

var q = from x in data where (x.f-- > 0) select x;

Notice that the predicate in the where clause actually modifies a field of an object. This means that the query may not be safe to run in parallel without exposing race conditions and concurrency bugs. By default, you must assume that queries like this are not safe and must not be run with PLINQ. But when would it actually be safe? The races occur only if the predicate is run on multiple threads against the same object, which can only happen if data contains duplicate objects. So if data is a set, then it's perfectly OK.

There are other cases, such as where static variables are used, that are always unsafe:

class C { internal static int s_cCounter; }
// elsewhere...
var q = from x in data where (x.f == C.s_cCounter++) select x;

If you run this query in parallel, you're apt to be quite disappointed. You could end up with many objects with duplicate f field values, which only occurs due to the race condition. Be careful: your initial reaction and approach to solving this might be to replace C.s_cCounter++ with Interlocked.Increment(ref C.s_cCounter). While this approach leads to a correct solution, any kind of synchronization will vastly reduce the scalability of your queries. You should strive to eliminate all reliance on mutability and shared state from your queries as a first principle.

The Windows® platform is very thread-centric, and a lot of system state can end up attached to the thread running some piece of code itself. This can take the form of thread-local storage, security information such as impersonation, COM apartments (particularly Single Threaded Apartments), and GUI frameworks such as Windows Forms and Windows Presentation Foundation. All of these can cause trouble when moving from LINQ to PLINQ.

Whereas in the LINQ model all code in the query runs on the same thread that initiated the query, with PLINQ the code in the query is distributed over many threads. Unfortunately, it's not always obvious when you've taken a dependency on thread affinity, since many services in the .NET Framework intrinsically and transparently rely on them internally. The best advice I can give is to be on the lookout for the abovementioned sources of concurrency hazards and avoid them as much as possible from within your queries.

Putting PLINQ to Work

PLINQ allows LINQ developers to take advantage of parallel hardware—including achieving better performance and building more intrinsically scalable software—without needing to understand concurrency or data parallelism. The programming model is simple, enabling a broader number of developers to take advantage of more parallel hardware. The "PLINQ Resources" sidebar lists some references for more information.

For those already using LINQ-to-Objects, LINQ-to-XML, or LINQ to tie together heterogeneous data sources, it is a straightforward process to get your existing queries to use PLINQ. Take a look at the sidebar "Compelling Scenarios" for further possible uses of this technology. For those who have not yet begun adopting LINQ, the parallel speedup gains are another reason for you to consider using it. Even though PLINQ is not available today, using LINQ in your programs is an investment in the future.

Joe Duffy is Development Lead for the Parallel FX team at Microsoft and blogs regularly at www.bluebytesoftware.com/blog. He is writing a book, Concurrent Programming on Windows, to be published by Addison-Wesley.

Ed Essey a five-year veteran Program Manager at Microsoft, works on parallel computing models and infrastructure.


Parallel Performance: Optimize Managed Code For Multi-Core Machines

Parallel Performance

Optimize Managed Code For Multi-Core Machines

Daan Leijen and Judd Hall
This article discusses:
  • Task Parallel Library
  • Parallel.For versus ThreadPool
  • Static Work Distribution
  • Futures
This article uses the following technologies:
Parallel FX Library
Contents
Introducing TPL
Structured Parallelism
Overexposing Parallelism
A Ray Tracer Example
Dynamic Work Distribution
Aggregation
Fork-Join Parallelism
Tasks and Futures
Replicable Tasks
The Task Manager

M
ulti-processor machines are now becoming standard while the speed increases of single processors have slowed down. The key to performance improvements is therefore to run a program on multiple processors in parallel. Unfortunately, it is still very hard to write algorithms that actually take advantage of those multiple processors. In fact, most applications use just a single core and see no speed improvements when run on a multi-core machine. We need to write our programs in a new way.

Introducing TPL

The Task Parallel Library (TPL) is designed to make it much easier to write managed code that can automatically use multiple processors. Using the library, you can conveniently express potential parallelism in existing sequential code, where the exposed parallel tasks will be run concurrently on all available processors. Usually this results in significant speedups.

TPL is being created as a collaborative effort by Microsoft® Research, the Microsoft Common Language Runtime (CLR) team, and the Parallel Computing Platform team. TPL is a major component of the Parallel FX library, the next generation of concurrency support for the Microsoft .NET Framework. Though it has not yet reached version 1.0, the first Parallel FX Community Tech Preview (CTP) will be available from MSDN® in Fall '07. Watch http://blogs.msdn.com/somasegar for details. TPL does not require any language extensions and works with the .NET Framework 3.5 and higher.

Visual Studio® 2008 is fully supported and all parallelism is expressed using normal method calls. For example, suppose you have the following for loop that squares the elements of an array:

for (int i = 0; i < 100; i++) {
  a[i] = a[i]*a[i];
}

Since the iterations are independent of each other, that is, subsequent iterations do not read state updates made by prior iterations, you can use TPL to express the potential parallelism with a call to the parallel for method, like this:

Parallel.For(0, 100, delegate(int i) {
  a[i] = a[i]*a[i];
});

Note that Parallel.For is just a normal static method with three arguments, where the last argument is a delegate expression. This delegate captures the unchanged loop body of the previous example, which makes it particularly easy to experiment with introducing concurrency into a program.

The library contains sophisticated algorithms for dynamic work distribution and automatically adapts to the workload and particular machine. Meanwhile, the primitives of the library only express potential parallelism, but do not guarantee it. For example, on a single-processor machine, parallel for loops are executed sequentially, closely matching the performance of strictly sequential code. On a dual-core machine, however, the library uses two worker threads to execute the loop in parallel, depending on the workload and configuration. This means you can introduce parallelism into your code today and your applications will use multiple processors automatically when they are available. At the same time, the code will still perform well on older single-processor machines.

Unfortunately, the library does not help to correctly synchronize parallel code that uses shared memory. It is still the programmer's responsibility to ensure that certain code can be safely executed in parallel. Other mechanisms, such as locks, are still needed to protect concurrent modifications to shared memory. TPL does offer some abstractions, though, that help with synchronization (as we will show you in a moment).

Structured Parallelism

One of the most important abstractions of the parallel programmer is a parallel loop. For example, consider the following (naïve) matrix multiplication routine:

void SeqMatrixMult(int size, double[,] m1, double[,] m2, double[,] result)
{
  for (int i = 0; i < size; i++) {
    for (int j = 0; j < size; j++) {
      result[i, j] = 0;
      for (int k = 0; k < size; k++) {
        result[i, j] += m1[i, k] * m2[k, j];
      }
    }
  }
}

In this example, the outer iterations are independent of one another and can potentially be done in parallel. Exposing this potential parallelism with TPL is easy. First, we reference the System.Concurrency.dll assembly during compilation. Then we are able to import the library into our code with a using statement:

using System.Concurrency;

Once the namespace is available, we can simply replace the outer for loop of the matrix multiplication with a call to the static Parallel.For method:

void ParMatrixMult(int size, double[,] m1, double[,] m2, double[,] result)
{
  Parallel.For( 0, size, delegate(int i) {
    for (int j = 0; j < size; j++) {
      result[i, j] = 0;
      for (int k = 0; k < size; k++) {
        result[i, j] += m1[i, k] * m2[k, j];
      }
    }
  });
}

The Parallel.For construct is a normal static method with three arguments. The first two arguments specify the iteration limits (between 0 and size). The last argument is a delegate function that is called for each iteration. This delegate takes the iteration index as its first argument and executes the unchanged loop body of the previous example. No changes to the original loop body are necessary since delegates automatically capture the free variables of the loop body (like result and m1). For more information on delegate expressions, see msdn.microsoft.com/msdnmag/issues/06/00/C20.

Finally, if any exception is thrown in any of the iterations, all iterations are canceled and the first thrown exception is rethrown in the calling thread, ensuring that exceptions are properly propagated and never lost.

Without TPL, it is much harder to express the potential parallelism in this loop. Even with the help of the .NET ThreadPool class, we have to consider the cost of synchronization and the division of work. Figure 1 shows the matrix multiplication routine parallelized using the thread pool.

Figure 1 Static Work Distribution and Explicit Synchronization (Close Figure 1)
void ThreadpoolMatrixMult(int size, double[,] m1, double[,] m2,
    double[,] result)
{
  int N = size;
  int P = 2 * Environment.ProcessorCount; // assume twice the procs for
                                          // good work distribution
  int Chunk = N / P;                      // size of a work chunk
  AutoResetEvent signal = new AutoResetEvent(false);
  int counter = P;                        // use a counter to reduce
                                          // kernel transitions
  for (int c = 0; c < P; c++) {           // for each chunk
    ThreadPool.QueueUserWorkItem(delegate(Object o)
    {
      int lc = (int)o;
      for (int i = lc * Chunk;           // iterate through a work chunk
           i < (lc + 1 == P ? N : (lc + 1) * Chunk); // respect upper
                                                     // bound
           i++) {
        // original inner loop body
        for (int j = 0; j < size; j++) {
          result[i, j] = 0;
          for (int k = 0; k < size; k++) {
            result[i, j] += m1[i, k] * m2[k, j];
          }
        }
      }
      if (Interlocked.Decrement(ref counter) == 0) { // use efficient
                                                     // interlocked
                                                     // instructions
        signal.Set();  // and kernel transition only when done
      }
    }, c);
  }
  signal.WaitOne();
}

The example is already quite sophisticated, using the thread pool for work items and using a counter together with a single wait handle to minimize the number of kernel transitions. In addition, it statically divides the loop into chunks based on the number of processors, creating twice as many as necessary to adapt better to dynamic workloads. However, unlike Parallel.For, the approach shown in Figure 1 does not propagate exceptions in the loop body and cannot be canceled.

Obviously, this code is much harder to write and more error-prone than the Parallel.For method. Also, despite being hand-tuned and using a near-optimal division of work, the thread pool approach performs generally worse than the Parallel.For method. Figure 2 shows the results of some anecdotal testing. The results represent the relative speedup when parallelizing the outer loop of a matrix multiplication with 750x750 elements—1 represents the running time with a normal for loop. The tests were conducted on a four-socket dual-core machine with 3GB of memory and running Windows Vista® Ultimate. Notice that on the single-core machine the Parallel.For version performs practically the same as the direct for loop.

Figure 2 Parallel.For vs. ThreadPool Performance
Figure 2 Parallel.For vs. ThreadPool Performance

Overexposing Parallelism

You may have noticed that we can expose even more parallelism by parallelizing the second for loop, as in:

Parallel.For( 0, size, delegate(int i) {
  Parallel.For( 0, size, delegate(int j) {
    result[i, j] = 0;
    for (int k = 0; k < size; k++) {
      result[i, j] += m1[i, k] * m2[k, j];
    }
  });
});

Even though it is fine to nest parallel loops, the performance of this approach is generally worse for two reasons. First, in this particular example, the outer loop already exposes more than enough opportunities for parallelism since we generally have far fewer cores available than the size of the matrix. Second, every delegate expression allocates some memory to hold the free variables. That is why in our initial example, there was just a single allocation whose cost is amortized over the iterations. Unfortunately, in the new code, the inner Parallel.For will perform heap allocation on each iteration of the outer loop. Allocation is very efficient in the CLR, but this is still a noticeable cost compared to the amount of work done in each iteration.

Note that you cannot parallelize the inner loop since those iterations are not independent. In particular, there is a race since every iteration adds to the result[i,j] location. If you parallelize this loop, two iterations could concurrently read the current value into a register, add to it, and write back the result—and one addition would be lost! The only way to parallelize the inner loop is to properly protect the addition with a lock. Of course, actually doing this is not advisable: even if you ignore the extra allocations for the moment, performance is severely impacted since each concurrent iteration competes for the same lock. We'll come back to this in a bit when we discuss aggregation operations. For more information on races and locks, see msdn.microsoft.com/msdnmag/issues/05/08/Concurrency/default.aspx.

A Ray Tracer Example

Ray tracing is a simple but powerful way to generate photorealistic renderings. The technique, however, is very computationally intensive. Ray tracing is actually an excellent candidate for our library since each ray can be computed in parallel. We took an existing ray tracer, written by Luke Hoban (see blogs.msdn.com/lukeh/archive/2007/04/03/a-ray-tracer-in-c-3-0.aspx), and modified it to run in parallel using TPL. The ray tracer generates images as shown in Figure 3 and will be available as a sample in the Parallel FX CTP. The core loop of the original ray tracer iterates through all pixels of the result image:

Figure 3 Parallel Ray Tracer
Figure 3 Parallel Ray Tracer(Click the image for a smaller view)
Figure 3 Parallel Ray Tracer
Figure 3 Parallel Ray Tracer (Click the image for a larger view)

void Render(Scene scene, Color[,] rgb)
{
  for (int y = 0; y < screenHeight; y++)
  {
    for (int x = 0; x < screenWidth; x++) {
      rgb[x,y] = TraceRay(new Ray(scene,x,y));
    }
  }
}

Since each ray can be traced independently, we only needed to make a single line change to the original code to parallelize it:

void Render(Scene scene, Color[,] rgb)
{
  Parallel.For(0, screenHeight, delegate(int y)
  {
    for (int x = 0; x < screenWidth; x++) {
      rgb[x,y] = TraceRay(new Ray(scene,x,y));
    }
  });
}

On an eight-core machine, the original code could generate 1.7 frames every second for an image of 350-by-350 pixels. In comparison, the parallel version, running on the same eight processor machine, generates 12 frames every second. This is a 7 times speedup on an eight processor machine, which is an extremely good result for such a small change. With 12 frames per second, we are just fast enough to produce a smooth animation of the balls bouncing on the floor. And since this is a very simple ray tracer, you may be able to optimize it further to achieve even smoother animation.

Dynamic Work Distribution

When parallelizing loops manually using the thread pool, developers often end up dividing the work statically. For example, in a ray tracer, the image is often divided in even parts where each part is processed by a separate thread. In general, this is not a good idea since the actual work load might be unevenly divided. If the bottom part of the image takes, for example, twice as long to compute due to reflections, then the threads that serve the upper part of the image are left waiting most of the time for the bottom threads to finish. Even if the work is evenly divided, this can still happen due to page faults or other processes on the system that run concurrently.

To scale well on multiple processors, TPL uses work-stealing techniques to dynamically adapt and distribute work items over the worker threads. The library has a task manager that, by default, uses one worker thread per processor. This ensures minimal thread switching by the OS. Each worker thread has its own local task queue of work to be done. Each worker usually just pushes new tasks onto its own queue and pops work whenever a task is done. When its local queue is empty, a worker looks for work itself and tries to "steal" work from the queues of other workers.

The advantage here is that there is almost no synchronization between workers since the work queues are distributed and most operations are local to the worker, which is crucial for scalability. Moreover, work stealing has provably good cache locality and work distribution properties. For example, if the workload is uneven, one worker may take a long time for a specific task, but other workers will now steal work from its queue, keeping all processors busy. Dynamic work distribution is crucial in typical applications since it is hard to predict how long a task will take. This is especially true for desktop systems where processors are shared among many different processes and where we cannot predict the time slices the worker threads will get.

Figure 4 demonstrates the dynamic work distribution in action using four threads. It shows the same ray-traced image as in Figure 3 but this time each worker thread is using a different color to render its pixels. You can see that the library distributed the work evenly among the worker threads, dynamically adapting to the workload.

Figure 4 Distributing Work among Worker Threads
Figure 4 Distributing Work among Worker Threads(Click the image for a smaller view)
Figure 4 Distributing Work among Worker Threads
Figure 4 Distributing Work among Worker Threads (Click the image for a larger view)

Besides performing dynamic work distribution, the library also dynamically adjusts the number of worker threads if workers get blocked. Some examples of blocking operations are file reads, waiting for a key press, and retrieving the user name (since this can access the network on a domain). If a task is unknowingly blocked, performance can degrade as the concurrency level drops (but the program still behaves correctly). To improve performance, the library automatically tracks to see if worker threads are blocked and injects extra worker threads to maintain the concurrency level if necessary. Once operations are unblocked, some workers may be retired to reduce the cost of thread switching.

Aggregation

A for loop is often used to iterate over a domain and aggregate the values into a single result. Take, for example, the following iterations that sum the prime numbers less than 100:

int sum = 0;
for(int i = 0; i < 100; i++) {
  if (isPrime(i)) sum += i;
}

Unfortunately, we cannot parallelize this loop as it is since parallelizing this would lead to a data race. Each iteration modifies the shared sum variable without lock protection. If two concurrent iterations increment the sum at the same time, they can both potentially read the same value in a register, add to it, and write their result back—and we would lose one addition. A correct version would use a lock to protect the addition, like so:

int sum = 0;
Parallel.For(0, 100, delegate(int i) {
  if (isPrime(i)) {
    lock (this) { sum += i; }
  }
});

However, the program now suffers from a performance problem since all parallel iterations contend for both the same lock and the same memory location (sum). It would be better if each worker thread would maintain a thread local sum and only add to the global sum at the end of the loop. This pattern is captured by the Paral- lel.Aggregate operation, and so we can rewrite the example as:

int sum = Parallel.Aggregate(0, 100, // iteration domain
              0,                     // initial value
              delegate(int i) { return (isPrime(i) ? i : 0) }, // apply
                                                      // on each element
              delegate(int x, int y) { return x+y; }  // combine results
          );

The aggregate operation takes five arguments. The first two specify the iteration domain, which can also be an enumerator. The next argument is the initial value for the result. The next two arguments are delegate functions. The first function is applied to each element, and the other is used to combine the element results.

The library automatically uses a thread local variable to compute the thread local results without any locking, only using a lock to combine the final thread local results. Keep in mind that if aggregation is done in parallel, it is possible for elements to be combined in a different order than with a sequential aggregation. Therefore, the combining delegate function must be associative and the initial value must be a unit element.

Fork-Join Parallelism

Another common parallel pattern is fork-join parallelism. As an example, consider the following sequential quicksort implementation:

static void SeqQuickSort<T>(T[] domain, int lo, int hi) where T : IComparable<T>
{
  if (hi - lo <= Threshold) InsertionSort(domain, lo, hi);

  int pivot = Partition(domain, lo, hi);
  SeqQuickSort(domain, lo, pivot - 1);
  SeqQuickSort(domain, pivot + 1, hi);
}

The algorithm is generic in the element type T and only requires that T instances can be compared. Under a certain threshold, the algorithm falls back on insertion sort, which performs better for a small number of elements. Otherwise, we partition the input array in two parts and quicksort each part separately. These two sorts can be performed in parallel since each sort works on a distinct part of the array. We can express this conveniently using the Parallel.Do method:

static void ParQuickSort<T>(T[] domain, int lo, int hi) where T : IComparable<T>
{
  if (hi - lo <= Threshold) InsertionSort(domain, lo, hi);

  int pivot = Partition(domain, lo, hi);
  Parallel.Do(
    delegate { ParQuickSort(domain, lo, pivot - 1); },
    delegate { ParQuickSort(domain, pivot + 1, hi); }
  );
}

The Parallel.Do method is a static method that takes two or more delegates as arguments and potentially executes them in parallel. Since quick sort is recursive, a lot of parallelism is exposed because every invocation introduces more parallel tasks. Again, since the library does not guarantee parallel execution, most of the tasks are actually executed sequentially, which is essential for good performance.

Tasks and Futures

The previous examples all demonstrate structured parallelism where the scope of the parallel code is determined by the lexical scope. But not all parallel algorithms can be expressed this way. Fortunately, the library also provides support for general parallel tasks:

class Task
{
  Task( Action action );

  void Wait();
  void Cancel();
  bool IsCompleted { get; }
  ...
}

A task is created by supplying an associated action that can potentially be executed in parallel. The action is executed somewhere between the creation time of the task and the first call to the Wait method. The associated action may be executed in parallel on another thread, but there is a guarantee that the action will not migrate among threads. This is a useful guarantee since programmers can use thread affine abstractions like Windows critical sections without having to worry, for example, that the LeaveCriticalSection is executed in a different thread than the EnterCriticalSection. If a task is already completed, Wait returns immediately.

Any exception that is raised in the associated action is stored in a task and raised again whenever Wait is called. Similarly, the Parallel.For and Parallel.Do functions accumulate all exceptions thrown and are reraised when all tasks complete. This ensures that exceptions are never lost and are properly propagated to dependents.

Finally, you can cancel the task and all tasks created in its associated actions (child tasks) by calling Cancel. Cancellation is not pre-emptive and a running task must cooperatively quit doing work by calling back into the library. This can be done, for example, by creating new tasks or calling the Wait method. If the parent task has been canceled, these library calls will raise a (synchronous) OperationCanceled exception to stop the action.

You can see tasks as an improved thread pool where work items return a handle that can be canceled or waited upon, and where exceptions are propagated. There is also a variation of tasks, called futures, where the associated action computes a result:

class Task<T> : Task
{
  Task ( Func<T> function );
  T Value { get; }            // does an implicit wait
}

A future, which is a task that computes a result, is constructed not with a normal action but with an action that returns a result. This result is a delegate with the Func<T> type where T is the type of the future value.

The result of the future is retrieved through the Value property. The Value property calls Wait internally to ensure that the task has completed and the result value has been computed. Since Wait is called, calling Value throws any exceptions raised during the computation of the value. One way to look at this is to think of a future as having either a value or an exceptional value, determined by the computation.

Futures are an old concept already implemented in multi-lisp. Note though that our notion of a future is not "safe" in the sense that the programmer is responsible for properly locking shared memory. This is in contrast to approaches where the action of a future is wrapped automatically in a memory transaction.

The future abstraction works well with symbolic code that is less structured than loops. For example, consider the following definition of binary tree nodes and leafs:

class Node : Tree {
  int   depth;  // The depth of the tree
  Tree  left;   // The left sub tree
  Tree  right;  // The right sub tree
  ...
}

class Leaf : Tree {
  int value;  // values are stored in the leafs
  ...
}

Now suppose we define a virtual Sum method on a Tree that sums up all the values of the leaves. A leaf simply returns its value. Nodes add the sums of their sub-trees:

override int Sum() {
   int l = left.Sum();
   int r = right.Sum();
   return (r + l);
}

In this case, each child computation can be done in parallel since they are independent. The parallelism here is lexically scoped and we can use Parallel.Do, but for the sake of demonstration, we use futures:

override int Sum()
{
   Task<int> l = new Task<int>( left.Sum );
   int r       = right.Sum();
   return (r + l.Value);
}

For each left subtree, we create a new future of type int, passing a delegate as the constructor argument. In this sample, we pass the sum method of the left child, left.Sum, without calling it. We continue by calculating the sum of the right subtree. By creating the future, other processors could potentially start evaluating the sum of the left subtree in parallel. In the end, we request the value of the future using the Value property.

If the task has already been calculated by another worker thread, this call immediately returns the result value—great! If the task is still running on another worker thread, we block until the result is available (but another worker thread is scheduled to maintain the concurrency level).

There is another very common scenario where the task has not been started at all. In this case, the call to Value executes the task directly on the calling thread. This is common and very efficient since we just make an indirect method call. In contrast, when we wait on OS-supplied signals, it is not possible to make the signal happen and the only thing that can be done is to block the calling thread, which is generally bad for performance. In our case, it is clear how to calculate the value and the library executes the associated action directly instead of blocking the thread.

Since the amount of work done in the leaves is very small, it might be better to increase the size of work done by each task by doing the summation sequentially at a certain tree depth. For example, if we assume a sequential sum method SeqSum, we can write:

override int Sum()
{
   if (depth < 10) return SeqSum();

   Task<int> l = new Task<int>( left.Sum );
   int r         = right.Sum();
   return (r + l.Value);
}

In general, determining the right threshold limit depends on the amount of work done in the action of a task, compared to the cost of allocating a task object. In our experience, allocation is fairly cheap and the threshold limit is usually around 100 floating point multiplications.

Since futures are true first-class values, you can use futures to introduce parallelism between logically distinct parts of a program. For example, you can store futures in data structures where another distinct phase actually requests the values of these futures. An appropriate venue for this is gaming applications. One phase could calculate, for instance, the new health of all characters as a future, while other phases use the values of those health futures later on. On a multi-core machine, those futures can be calculated in parallel with the work done in each phase.

Replicable Tasks

The library is built upon just two primitive concepts: tasks and replicable tasks. All other abstractions, such as futures and parallel for loops, are expressed in terms of those two primitives. This ensures that operations behave in a regular way with consistent semantics. For example, exceptions are always nicely propagated and all abstractions can be canceled (including parallel for loops).

Note that replicable tasks are really meant for library writers that want to extend the standard abstractions offered by TPL, and they should only be used sparingly (if ever) in normal code. A replicable task derives directly from a normal task, like this:

class ReplicableTask : Task
{
  ReplicableTask( Action action );
}

A replicable task represents a task that can itself be executed by multiple threads at the same time and captures the ubiquitous apply-to-all concurrency pattern while abstracting from the dynamics of work distribution. The constructor takes an action delegate that is potentially executed in parallel on another thread and potentially executed by multiple threads at the same time. If an exception is raised in any of those executions, only one of them is stored and thrown again by Wait.

A replicable task can be used if other threads can potentially participate in doing the work. All the Parallel.For and Parallel.ForEach variations are implemented using replicable tasks. For example, we can naïvely implement the basic Parallel.For as:

static void For( int from, int to, Action<int> body )
{
  int index = from;
  ReplicableTask rtask = new ReplicableTask( delegate {
    int i;
    while ((i = Interlocked.Increment(ref index)-1) < to) {
      body(i);
    }
  });
  rtask.Wait();
}

Since all replicable tasks share the index variable, the actual action delegate that is passed to the replicable task constructor can be executed by as many threads as needed. In the implementation, this can be used to let idling processors participate in the work.

In this implementation, each worker thread claims one index at a time. This corresponds to the dynamic(1) strategy of OpenMP and works generally well when the workload of each index can differ significantly. (For more on this, see msdn.microsoft.com/msdnmag/issues/05/10/OpenMP.) But this strategy can lead to cache contention when the workload per index is small. In that case, it would be better to process a stride of indices at once. Look at this variation of Parallel.For that corresponds to the dynamic(n) strategy of OpenMP and takes a stride as an argument:

static void ForWithStride( int stride, int from, int to, Action<int> body )
{
  int index = from;
  if (stride <= 0) stride = 1;
  ReplicableTask rtask = new ReplicableTask( delegate {
    int i;
    while ((i = Interlocked.Add(ref index,stride)-stride) < to) {
      int end = Math.Min(i+stride, to);
      do {
        body(i);
        i++;
      }
      while (i < end)
    }
  });
  rtask.Wait();
}

Replicable tasks are a powerful abstraction for implementing different parallel iteration strategies. However, in our experience, the standard Parallel.For and Foreach implementations work well in many scenarios and we hope there won't be much need for the extra expressiveness of replicable tasks in practice.

The Task Manager

All tasks belong to a task manager, which, as the name implies, manages the tasks and oversees worker threads to execute tasks. While there is always a default task manager available, an application can also explicitly create a task manager. The task manager interface is defined as:

class TaskManager : IDisposable
{
  TaskManager();
  TaskManager( int maxConcurrentThreads );

  static TaskManager Current     { get; }
  int    MaxConcurrentThreads    { get; }
  ...
}

class Task
{
  Task( TaskManager taskManager, Action action )
  ...
}

A task manager has an associated concurrency level that is returned by the MaxConcurrentThreads property. This specifies to the manager the ideal number of threads executing tasks at any given time. It is a hint, so if the manager needs to use more to make forward progress, it will do so dynamically. When you create a task manager, you can supply this number explicitly; by default it is equal to the number of processors.

In general, you are never required to create a task manager explicitly since a default is always available. However, you might want to use multiple task managers where each has a different concurrency level or each handles a separate set of tasks. In that case, you can create a new task manager and use the special Task constructor that takes a task manager as its first argument and executes that task and all of its children in that task manager. For example, consider the following code:

using (TaskManager tm = new TaskManager(2)) {  // only use 2 worker
                                               // threads for tasks
  new Task( tm, delegate {
    // tasks created in this delegate use the tm task manager by default
    ...
    // finally, show some statistics
    Console.WriteLine( "statistics: " + tm );
  }).Wait();
}

Another important use of the task manager interface is to run all code sequentially using a single worker thread. This means that all tasks and parallel for loops are executed sequentially. This is excellent for debugging purposes where you can verify whether the code functions correctly when executed sequentially before running it in parallel on a multi-processor machine.

Daan Leijen is a Researcher at Microsoft Research. His current interests are declarative and functional programming, type inference systems, and parallel computing.

Judd Hall is a Program Manager II at Microsoft.


Mobile Apps: Adjust Your Ring Volume For Ambient Noise

Mobile Apps

Adjust Your Ring Volume For Ambient Noise

Chris Mitchell
This article discusses:
  • Pocket PC development
  • Measuring loudness
  • Custom installers
  • Using P/Invoke
This article uses the following technologies:
.NET Compact Framework
Code download available at: NoiseDetection2007_10.exe (193KB)
Contents
The Approach
Reference Values
The Implementation
How to Handle Installation
Results

Y
ou're sitting in the local coffee shop on a sunny afternoon, peacefully enjoying a quiet moment, when your phone starts to ring. It's set, of course, to full volume and the ring is so loud you nearly spill your coffee. So you turn it down.

Later that day, you're waiting at a bar for a friend, but he's nowhere to be seen. He'd forgotten which bar you were meeting at and called to see where you were. Unfortunately, you missed the call because you didn't hear your phone ring. The problem: the ring volume was still turned down and wasn't loud enough to hear in the noisy bar.

This is fairly ridiculous when you consider that current mobile phones have as much processing power as the first PC I used for multi-channel audio recording. It would seem that with today's intelligent mobile devices, which are capable of doing so many things and accessing so much information, this problem should not exist. However, everyone who has a mobile phone has experienced this problem in one form or another.

The obvious way to solve the problem is to remember to change your volume settings. The option to change the ring volume is presumably to deal with the acoustic differences in various environments, but the functionality does not really do that. Devices should be able to act with a little more common sense. It's simple: I just want my mobile phone not to ring too loudly in a quiet environment and to ring audibly in a loud place.

This article addresses the possibilities and practicality of a Windows Mobile® application that automatically adjusts the Pocket PC's ring level based on the ambient noise in its current environment. The functionality of this app prevents the phone from ringing too loudly or softly, saving me from embarrassment and missed calls. In this article, I'll use this problem as an introduction to Windows Mobile development using Visual Studio® 2005 and C#.

Embarrassed by your phone ringing too loudly?
Embarrassed by your phone ringing too loudly?

The Approach

The plan is to use the sensors of a mobile phone to obtain a better understanding of the current environment. I want to use the microphone to measure environmental noise and then adjust the ring level accordingly.

I need to address a series of specific problems to make this work, as Figure 1 indicates. How do I obtain audio samples from the microphone that is built into the device? What measure should I use to define loudness? How do I change the ring level of the mobile device in response to this information? I'll discuss the first part of the system, collecting environmental information from a microphone, in a moment. First, however, I need to define a measure of loudness.

Figure 1 High-Level Steps to Adjusting Ring Volume
Figure 1 High-Level Steps to Adjusting Ring Volume

Loudness is subjective and is typically represented with an equal-loudness chart. (For more information on the subjective perception of sound, I recommend you look up some articles on the study of psychoacoustics.) These plots have frequency on one axis and a measure of sound pressure on another, normally in decibels (dB). The charts display the relationship between frequency and our perception of equal loudness.

To determine the relationship values, studies presented individuals with tones that increased in 10dB increments at various frequencies. Study participants were asked to judge when the sounds were of equal loudness compared to a 1KHz reference signal. These relationships were then used to construct tables and plot the equal-loudness chart, which could be used, together with frequency information obtained from the phone's microphone, to create a measure of loudness.

Another approach is to compare a measure of the sound pressure level to reference values and adjust the ring level if a substantial change occurs. What constitutes a change can then be defined by the profile of the phone. This overcomes problems with variations among microphones and speakers on different phones. Simply changing reference values enables the software to operate effectively with various phone models. This also means the system doesn't have to obtain frequency information from the microphone, saving valuable battery power.

Design complexity in the system is simplified through the redundancy of frequency decomposition and dB measurement. However, a measure of relative loudness is required for my application. In audio signal processing, root-mean-square (RMS) can be used as a rudimentary measure of loudness. (I'll explain RMS in more detail when I describe the implementation stage.) Although the frequency attributes still affect the perceived loudness, the RMS values should be sufficient for accuracy needs—this is especially true considering Pocket PCs have only five volume settings. The RMS function can be used to obtain values necessary to adjust ringing volume.

Reference Values

Once the samples are obtained from the microphone and fed into the RMS function, the output needs to be mapped to one of five volume states. What is the mapping function and how do the settings relate to reference values discussed earlier? The values are specific to each device and define when the ringing volume of the mobile phone changes. For example, the ring level should adjust appropriately when the RMS function indicates the environment is similar to a coffee shop or a noisy bar.

If I were going to scale this application up to support multiple device profiles, I would provide an interface for setting up the application. For this article, however, I am not going to implement such an interface; I will leave that up to someone else.

The process for generating reference values for a device profile is not very complicated. First, you use the RMS reporting capabilities of the application to obtain values in multiple reference situations suited to your needs. I used four common environments: a residential area at night (45dB); a quiet indoor restaurant or office (55dB); a typical indoor restaurant (65dB); and busy traffic about 16 feet away (75dB). These values will be the references for mapping to the five states of volume on a Pocket PC. (Obviously, a tool that can be used to obtain the various RMS values in these locations is needed.)

Then, once you have obtained an average value for all of your locations, you will use these values as upper and lower limits in the application's code.

The Implementation

I chose to build my solution in Visual C#® 2005, due to the integrated mobile development platform. This has made Pocket PC development a lot easier, although there is still no built-in wizard to create a desktop installer that can deploy your Pocket PC application via the desktop. There are some good free tools that fill the installer and there are methods for creating your own custom installer. (I'll discuss building a custom installer later in this article.)

For now, I want to get back to the application, which I'll name TooLoud. There are three parts to creating my application:

  1. To capture and process audio, I'll use the P/Invoke service of the Microsoft® .NET Compact Framework.
  2. I'll write a function to calculate RMS values.
  3. I'll write a function to access and set the volume using the registry on the Pocket PC, given an average RMS value.

You can use a number of libraries and ActiveX® controls to access the microphone to record the audio from a Pocket PC device. My example builds on the P/Invoke library (see msdn2.microsoft.com/aa446550.aspx), which includes a WaveIn class for accessing a device's microphone. This class contains a structure capable of storing samples at a set rate and bit resolution. The P/Invoke library also provides a helper class named Wave, which is a common interface to the .wav audio format. The above link provides a list of all implemented classes and functions in the original WaveIn and Wave classes.

The version of the P/Invoke library included in my solution only contains the WaveIn, Memory, and Registry classes. All other classes have been removed for the sake of brevity. The library shown in Figure 2 has been extended by providing extra functions: one in WaveIn (TooLoud)—AutoSetVolume—and the other in Wave—CalcRMS.

Figure 2 Part of the P/Invoke Library Displayed with TooLoud's Class Diagram
Figure 2 Part of the P/Invoke Library Displayed with TooLoud's Class Diagram(Click the image for a smaller view)
Figure 2 Part of the P/Invoke Library Displayed with TooLoud's Class Diagram
Figure 2 Part of the P/Invoke Library Displayed with TooLoud's Class Diagram (Click the image for a larger view)

The application runs AutoSetVolume, which calls CalcRMS as part of its procedure to set the volume. TestProc can be called repeatedly or just once depending on the mode selected in the user interface. TestProc calls six functions:

  • AutoSetVolume is used to achieve the end goal.
  • NumDevices gets the number of input devices.
  • GetDeviceName gets the name of the specified recording device.
  • Preload preloads the buffers for a given size and maximum amount of audio in milliseconds. (Start initiates the recording time, currently set to one second, and Stop ends the current recording.)
  • AutoSetVolume calculates the new volume setting.
  • Dispose clears the buffers.

Preload sets up an instance of a waveformatex, a header to describe the data, with a Pulse Code Modulation (PCM) format tag, 8-bit sample resolution, a single channel, and a sampling rate of 11025 Hz.

Now that I can obtain blocks of audio data for a period of time, I can use this data to calculate an RMS value. The calculation for root mean square is defined in Figure 3.

Figure 3 Part of the Loudness Calculation
Figure 3 Part of the Loudness Calculation(Click the image for a smaller view)
Figure 3 Part of the Loudness Calculation
Figure 3 Part of the Loudness Calculation (Click the image for a larger view)

The corresponding code, shown in Figure 4, can now be presented to define the method of calculating the RMS values using the sample values from the microphone. Due to the sample values being stored in byte format (0-255), the midpoint of 127.5 is subtracted to provide -127.5 to +127.5 normalized audio signals.

Figure 4 RMS Calculation (Close Figure 4)
public double CalcRMS(MainTest.DisplayLineDelegate ShowLine)
{
    byte[] data = new byte[dwBytesRecorded];
    Marshal.Copy(lpData, data, 0, data.Length);
    double temp = 0, sum = 0;
    int j = 0;

    ShowLine(data.Length.ToString());

    for (int i = 0; i < data.Length; i++)
    {
        temp = (double)data[i] - 127.50;
        sum = sum + (temp * temp);
        j++;
    }
    return Math.Sqrt(sum / j);
 }

The mapping function takes the RMS value and defines the value that will be used to set the Pocket PC's current ring level. Although this could be done more empirically, a simple profile of a mobile phone's capabilities will do for the demonstration.

As I discussed, the disadvantage of this technique is that a profile will probably be needed for each model of phone that has significantly different speaker and microphone capabilities. You can solve this problem by creating a configuration interface that lets the user set reference values for various locations, or you could provide a Web site that serves up the various profiles. Here, I will only include the means to input one set of reference values. With this in mind, however, I'll show you how to obtain the mapping values so they can be reproduced for any phone's profile.

The RMS values were generated by recording a number of common sound environments associated with certain dB levels. Ideally, this should be done over a substantial period of time (in case, say, somebody drops a plate in the coffee shop at the exact moment you're sampling), and it should include the typical environments where you expect your phone to be. The average reading from each environment can then be used as the upper and lower limits for volume setting.

Once the reference values have been calculated, an adaptive profile must be constructed. This simply defines how the mobile phone will adapt its ring level according to the values. There are many different strategies you can consider. You could, for example, even have vibrate turn on if the phone is in a very noisy environment. For my implementation, I will simply have the reference values map the microphone input onto the five volumes.

The ring level of a Pocket PC can be set using the registry. The registry value is in HKEY_CURRENT_USER under ControlPanel\SoundCategories\Ring, and the value to change is InitVol, which has a range from 0 to 5.

The code in Figure 5 can be used to set the ring volume values using the standard registry write functions. The mapping decides on the right value for the ringer given an upper and lower limit, implemented as several conditional statements.

Figure 5 Setting the Current Ring Level (Close Figure 5)
public Wave.MMSYSERR AutoSetVolume(MainTest.DisplayLineDelegate ShowLine)
{
    double AverageRMS = 0.00;
    if (!m_inited)xreturn Wave.MMSYSERR.ERROR;

    if (m_recording) Stop();

    try
    {
        // Write the data recorded to each buffer.
        // Get RMS value for each block and take the average
        // across all blocks.
        for (int i = 0; i < m_numBlocks; i++)
        {
            if (m_whdr[i] != null)
            {
                AverageRMS = AverageRMS + m_whdr[i].CalcRMS(ShowLine);
            }
        }

        AverageRMS = AverageRMS / m_numBlocks;
        ShowLine("Average RMS: " + AverageRMS);

        // Select volume based on reference values.
        uint Volume = 0;
        if (AverageRMS > 35.00)
        {
            //Range of this value for the volume control is from
            //0x0000 (min) non to 0x0005 (max).
            Volume = 5;
        }
        else if ((AverageRMS <= 35.00) && (AverageRMS > 30.00))
        {
            //Range of this value for the volume control is from
            //0x0000 (min) non to 0x0005 (max).
            Volume = 4;
        }
        else if ((AverageRMS <= 30.00) && (AverageRMS > 20.00))
        {
            //Range of this value for the volume control is from
            //0x0000 (min) non to 0x0005 (max).
            Volume = 3;
        }
        else if ((AverageRMS <= 20.00) && (AverageRMS > 10.00))
        {
            //Range of this value for the volume control is from
            //0x0000 (min) non to 0x0005 (max).
            Volume = 2;
        }
        else
        {
           //Range of this value for the volume control is from
           //0x0000 (min) non to 0x0005 (max).
            Volume = 1;
        }

        ShowLine("Set Volume to: " + Volume.ToString());
        PInvokeLibrary.Registry.CreateValueDWORD(
            "ControlPanel\\SoundCategories\\Ring", "InitVol",
            Volume);

        return Wave.MMSYSERR.NOERROR;
    }
    catch { return Wave.MMSYSERR.ERROR; }
    finally { FreeWaveBuffers(); }
}

How to Handle Installation

Now that I've created the TooLoud application code, I must pick from among several different options to create installers for the Pocket PC. You can transfer the application using the Windows Vista® Mobile Device Center if you're impatient and want to play with this right away—which is what I did. However, this is less than ideal for the end user. Another approach is to create a CAB file and then create a Microsoft Installer (MSI) installer that can be run from the PC to set up the application on the Pocket PC. Once the CAB file has been generated, you can use a program that allows you to quickly generate a setup file complete with end-user license. But you may prefer to build a custom installer to handle the deployment to the mobile phone from the desktop, offering more sophisticated techniques. The end of this section looks at how to create a custom installer, a smart device CAB file, and a deployment project using Visual C# 2005. If you have Visual Studio 2003, you can find a guide for implementing similar functionality at msdn2.micro- soft.com/ms838273.

The complete project, which is available for you to download from the MSDN® Magazine Web site, contains four main components: the TooLoud application, SmartDeviceCab builder, CustomInstaller, and Setup installer.

In Visual Studio 2005, creating a smart device CAB is straightforward. To add a smart device CAB project to the solution, simply click on the solution in the Solution Explorer, select Add | New Project, select Other Project Types | Setup and Deployment, select the Smart Device CAB Project template, and click OK. Now in Solution Explorer, select the smart device Cab project you just added and add the primary project output from the TooLoud application.

There are several properties you can set for the SmartDeviceCab project; Figure 6 shows the properties page in Visual Studio 2005. While some of the properties are straightforward, a few are not. For instance, the OSversionMin property defines whether the application supports screen orientation awareness if set to 4.21. However, this value will prevent the application from installing on Pocket PCs based on Windows Mobile 2003 and earlier. For Pocket PC solutions based on Windows® 2003SE and earlier, the Compress property and NoUninstall device deployment property must be false. (Note that if you have the .NET Compact Framework 2.0 installed, this latter property can be set to True.)

Figure 6 SmartDeviceCab Properties
Figure 6 SmartDeviceCab Properties(Click the image for a smaller view)
Figure 6 SmartDeviceCab Properties
Figure 6 SmartDeviceCab Properties (Click the image for a larger view)

The CE Setup DLL specifies the file that will run postinstall operations, such as configuring registry settings or installing the application as a service. This latter case is useful if, for example, you want the application to run in the background as a service making intelligent decisions about when the application runs.

Once the CAB file is built, it is capable of deploying the application to a mobile phone, but there is still the problem of how to trigger the CAB file to be copied and installed onto a mobile phone. So I will create a deployment project that will install the CAB file onto the system desktop and then trigger the application manager (see Figure 7). The application manager, which runs under the Windows Mobile Device Center, is the program on your desktop that controls the applications that are installed onto your mobile phone.

Figure 7 Mobile Device Center and Application Manager
Figure 7 Mobile Device Center and Application Manager(Click the image for a smaller view)
Figure 7 Mobile Device Center and Application Manager
Figure 7 Mobile Device Center and Application Manager (Click the image for a larger view)

My deployment project is the same as the desktop deployment project contained within the Visual Studio templates. However, I must extend the functionality to include the task of launching the application manager to install the CAB file. I do this by creating a custom installer class to extend the normal installer. The custom installer class overrides two of the base class's methods, AfterInstall and AfterUninstall, and adds a method to launch the application manager. You can find the location of the application manager by accessing a registry value on the desktop machine.

Figure 7 shows the application manager (the foreground Window), which has been launched by my custom installer. The code for my custom installer is shown in Figure 8.

Figure 8 Custom Installer Code (Close Figure 8)
private void Installer_AfterInstall(
    object sender, System.Configuration.Install.InstallEventArgs e)
{
    // Get fullpath to .ini file.
    string arg = Path.Combine(
        Path.GetDirectoryName(Assembly.GetExecutingAssembly().Location),
        "Setup.ini");

    // Run WinCE App Manager to install .cab file on device.
    RunAppManager(arg);
}

private void Installer_AfterUninstall(
    object sender, System.Configuration.Install.InstallEventArgs e)
{
    // Run app manager in uninstall mode (without any arguments).
    RunAppManager(null);
}

private void RunAppManager(string arg)
{
    // Get path to the application manager.
    const string RegPath = @"Software\Microsoft\Windows\" +
        @"CurrentVersion\App Paths\CEAppMgr.exe";
    RegistryKey key = Registry.LocalMachine.OpenSubKey(RegPath);
    string appManager = key.GetValue("") as string;

    if (appManager != null)
    {
        // Launch the application manager.
        Process.Start(string.Format("\"{0}\"", appManager),
            (arg == null) ? "" : string.Format("\"{0}\"", arg));
    }
    else
    {
        // Could not locate application manager.
      MessageBox.Show(
          "Could not launch the WinCE Application Manager :-(");
    }
}
Figure 9 The Entire Solution
Figure 9 The Entire Solution

Now the deployment project is created in the usual way, by adding a standard desktop setup project to the solution. After the deployment template has been added, I then add the custominstaller.dll and the smartdevicecab.cab to the setup project. To reference the custom installer, I right-click the setup project and select View | Custom Actions. Then I add the custominstaller.dll to the Install and Uninstall custom actions of the deployment project.

My deployment project needs one last file—the setup.ini file:

[CEAppManager]
Version      = 1.0
Component    = App

[App]
Description  = TooLoud Pocket PC
    application.
CabFiles     = SmartDeviceCab.cab

This tells the application manager which CAB to load. Figure 9 shows the layout of my solution. (The build order should be set to TooLoud—SmartDeviceCab—CustomInstall—Setup.) My project can now be built and deployed using a desktop machine that has application manager on it.

Results

This article outlines a specific example I wrote for Visual Studio 2005 using version 1.x of the .NET Compact Framework. It demonstrates the underlying principles and general techniques involved in designing an application that will use the hardware on a Windows Mobile device to monitor the surrounding environment and automatically adjust the ring volume accordingly. Of course, this code can be refactored to use the latest technologies, such as version 2.0 of the .NET Compact Framework.

To see how well my app was working, I did both lab-based testing and environmental testing. The lab-based test was to ensure the phone would only ring 2-5dB louder than the environment (6dB is roughly twice as loud). The dB values were measured with a dB meter with a tone as the test signal. Environmental testing was done in two locations—in a coffee shop and in an airport in Los Angeles. I used a very scientific form of measurement for this test—I counted the number of people who turned around when my phone rang.

The application provides a sound approach (sorry, this pun is intended) to monitoring and adapting the ring level of a mobile phone. Like all applications, it does have its limitations, such as the need to configure the reference values for each model of mobile phone. Although this is not an unmanageable task, the current user interface doesn't support it. The other major limitation is that this approach consumes a lot of power. However, this can be easily solved by, say, having the process activate only when the phone is about to ring.

These issues aside, the application makes a lot of sense—more so, in my opinion, than the current approach of having a ring level that only changes when you manually alter the settings. There are still some improvements to be made, so feel free to start adapting the code and adding any functionality you think would be useful. I'm sure you can think of a lot of features and capabilities that I haven't discussed here.

I would like to thank Brian Richardson for the artwork at the opening of the article.

Chris Mitchell finished his PhD in machine learning and music/sound signal processing, and is currently a Kauffman/NCGE fellow. He was a part-time lecturer at Anglia Ruskin University, Cambridge, UK, which, along with some network consulting, helped finance his studies. You can contact Chris at c.mitchell at anglia.ac.uk. A passion for music technology led him to explore some of the fundamentals of audio programming, and he is always happy to hear about anything in this area.


Editor's Note: The Complexity of Complexity

Editor's Note
The Complexity of Complexity
Howard Dierking

As developers, it seems as though we are under ever increasing pressure to manage new dimensions of complexity. We are asked to author and maintain systems that support progressively more complicated business rules and processes. We are asked to create dynamic, interactive, and integrated user experiences over a variety of media. And, always, we face pressure to understand and leverage nuances of the latest and greatest hardware designs.

What is the solution to this escalating complexity? If history is any teacher, the solution is to create new metaphors and new abstractions. Metaphors let us use existing language and experience to communicate about specialized subjects in a general way. Similarly, abstraction facilitates better design by hiding details that would otherwise cloud our ability to effectively separate different elements from one another. Ultimately, abstraction lets technology specialists create software elements with minimal dependencies on other elements, while metaphor enables generalists or specialists in different areas to intelligently discuss and apply those elements to create elegant solutions.

I recently joined MSDN® Magazine after spending the majority of my career designing and developing software for a variety of different industries. As I'm sure you can imagine, there are many moving parts in the process of publishing a magazine—and for a newcomer, it is easy to feel overwhelmed by the complexity.

However, just as in my developer days, I have found abstraction and metaphor invaluable in giving me a structured way by which to learn the business. For example, details of the editorial and production processes are effectively abstracted from one another—editors don't have to know all the mechanics of creating a layout, and the production folks needn't care how the manuscripts were acquired and massaged. Metaphors such as "pouring" describe the process of transferring edited text into the layout. All in all, it's nice to know that some of the skills I built up as a developer are not completely useless in the magazine business!

In this issue of MSDN Magazine, we explore how the complexity you might be facing in your daily software development tasks is being addressed through new tools and metaphors. For supporting increasingly complex business requirements and demands, Bill Horst discusses how type inference raises the level of abstraction in code from the CLR type system closer to the business domain. Bill Chiles takes this notion of intentionality in programming a step further in his discussion of the dynamic language runtime (DLR). For enabling richer user experiences, Dino Esposito extends the service metaphor to patterns of Web presentation with Part 2 of his column on ASP.NET AJAX. Daan Leijen and Judd Hall describe how the Parallel FX library abstracts away specific low-level details surrounding how to take advantage of new hardware innovations such as multiple processors and multi-core processors. Joe Duffy and Ed Essey then describe how the existing language metaphors are being extended to support these abstractions in Parallel LINQ.

In the end, the successful creation of new metaphors and abstractions will undoubtedly lead to new degrees of complexity and the need for new metaphors and abstractions. However, with each new layer of abstraction, the size of problems we are able to solve through software grows in proportion. So in that light, what metaphor should we create for the vision of MSDN Magazine? Here are a few thoughts: rock concert, hammer, mirror, disco ball.

What about you? E-mail us your thoughts and ideas—who knows? Your idea could help to shape the very vision of the magazine for the next several years! —Howard

Thanks to Thanks to the following Microsoft technical experts for their help with this issue: Mahesh Prakriya, Kit George, Umachandar Jayachandran, Rob Earhart, Eric Li, Sandeep Ranade, Rob Shewan, Judd Hall, Ed Essey, Vance Morrison, JJ Johnston, Daniel Moth, Mike Hall, Jordan Parker, David Aiken, Joe Duffy, and Stephen Toub.


Toolbox: Manage databases, easier FTP, and clustered caching

Toolbox
Manage databases, easier FTP, and clustered caching
Scott Mitchell

Contents
Effectively Manage Your Database Projects
FTP Made Easy
Take Caching to the Next Level

Effectively Manage Your Database Projects

There are many tools available for managing databases, exploring and modifying schemas, and writing and executing queries. One such off-the-shelf tool worth investigating is DatabaseSpy 2007 by Altova. DatabaseSpy can connect to a wide variety of different data stores—Microsoft® Access®, Microsoft SQL Server™, Oracle, MySQL, Sybase, and so on—and provides a uniform user experience regardless of the database.

When first connecting to a database through DatabaseSpy, a new project is automatically created. Projects serve as repositories for connection details, credentials, commonly used queries, and so forth. The contents of a project can be quickly searched, and frequently used elements can be stored in the Favorites folder. Moreover, the project manager's menus and toolbars can be customized and configured to launch external tools.

DatabaseSpy's SQL Editor also offers a modern query editor. For starters, the Autocomplete feature gives the editor IntelliSense®-like behavior. When typing in a query, a drop-down list of possible SQL keywords, functions, and table names appear. When executing a query, the results are displayed in a grid. Unlike the result grid in SQL Server Management Studio, however, DatabaseSpy's grid can be sorted by clicking on a column header. The SQL Editor also includes tools for exporting data to a variety of formats, including XML, CSV, HTML, and Excel®.

In addition, DatabaseSpy includes a rich graphical Design Editor that enables developers to create and modify tables with a few points and clicks. As the table is being created or modified, DatabaseSpy maintains a database structure change script and displays it on-screen. This information is handy to verify what specific changes have been made and for applying the same changes to another database.

If you are looking for top-of-the-line tools for managing databases and executing queries, take the time to explore alternative, third-party options such as DatabaseSpy 2007.

Price: $129

www.altova.com/DatabaseSpy

DatabaseSpy's Design Editor Helps You Create and Modify Tables
DatabaseSpy's Design Editor Helps You Create and Modify Tables (Click the image for a smaller view)
DatabaseSpy's Design Editor Helps You Create and Modify Tables
DatabaseSpy's Design Editor Helps You Create and Modify Tables (Click the image for a larger view)

FTP Made Easy

The File Transfer Protocol (FTP) is an open and well-known protocol for exchanging files between a server and a client over a network. Web browsers are one of the most popular and ubiquitous FTP client applications available, but the FTP features and user experience—while straightforward—typically lack the more advanced features that are found in most stand-alone FTP client applications.

One such stand-alone FTP client application is FileZilla (version 2.2), an open-source project started by Tim Kosse. Launching FileZilla displays the Site Manager, which stores FTP server account information. Here you can add and categorize the FTP servers you commonly access, storing authentication credentials, connection options, and other configuration information. FileZilla supports both the native FTP implementation—which is not secure as it sends credentials over the network in plain text—as well as the two standardized secure implementations: FTP over SSL and SFTP.

Once connected to an FTP site, the FileZilla user interface consists of four panes. The first one lists the FTP commands sent to the FTP server and the corresponding response. This low-level information is quite helpful for developers and other savvy users when troubleshooting. The second pane lists the files and folders on the local computer while the third pane lists those on the FTP server. To upload files or folders from one location to the other, simply select the items from one pane and drag them over to the other pane. The current activity and pending list of actions are listed in the transfer queue, which is displayed in the bottom pane.

In addition to the client application, the FileZilla project includes a free, open-source FTP server implementation.

Price: Free; source code available (Visual C++)

sourceforge.net/projects/filezilla

As a Diagnostic Tool, FileZilla Lists FTP Commands and Responses
As a Diagnostic Tool, FileZilla Lists FTP Commands and Responses (Click the image for a smaller view)
As a Diagnostic Tool, FileZilla Lists FTP Commands and Responses
As a Diagnostic Tool, FileZilla Lists FTP Commands and Responses (Click the image for a larger view)

Take Caching to the Next Level

Caching is a commonly used technique for improving application performance by copying frequently used data from a slow data source to a faster one. For data-driven applications, this usually entails caching data retrieved from databases or Web services into the local computer's memory.

Caching is easiest to implement when the cache is specific to each application, but becomes much more challenging if multiple applications need to work with a common cache. For example, large Web sites typically use a server farm that consists of several computers all serving the same content. As each request arrives, it is assigned to one of the computers in the farm. However, if information is cached in the memory of one computer in the farm, it is not accessible to the cache in another, thereby reducing the effectiveness of the cache. One solution to this problem is to move the cache to a centralized data store, such as a database, or to designate one of the servers in the farm as the cache server, which stores the only copy of the cache. The problem with centralized cache stores is that they introduce a single point of failure and can serve as a bottleneck.

To overcome the limitations of a single, centralized cache store, consider using NCache 3.1 from Alachisoft. NCache is a clustered caching framework that seamlessly manages a cache distributed across multiple computers. An administrator starts by specifying the cluster topologies and cache policies through the NCacheManager tool. The administrator can specify whether the cache is stored in memory or on disk, the eviction policies, and the maximum cache size, among other settings; these settings, as well as the topology, can be modified at runtime. In addition, NCacheManager includes an array of statistics that can be used to monitor the cache's health and as metrics to fine-tune the cache's settings for optimal performance.

When defining a caching cluster, you can specify whether the cache should be replicated or partitioned across the cluster. A replicated cache cluster has the same cache contents on each of the machines in the cluster. Since there is no single point of failure, a replicated cache improves reliability; however, any updates to the cache must be replicated to all of the clusters. Therefore, replicated clusters are ideal for read-dominated caches or small clusters. A partitioned cache, on the other hand, divides the cache contents among the computers in the cluster and boasts better performance for updates and large clusters.

When evaluating frameworks like NCache, I am always interested in the learning curve and ease of integration. Mastering the NCacheManager tool and fully understanding the variety of configuration settings will undoubtedly take time, but plugging in the NCache API into your applications is a painless process. The classes in the NCache API closely match those of the caching API classes in the Microsoft .NET Framework and include HTTP Modules that make upgrading an ASP.NET application as simple as updating its configuration file. NCache also includes a provider for integration into Microsoft's Caching Application Block (CAB).

In short, enhancing caching for your applications is a relatively straightforward process: existing code can be upgraded to using NCache with little or no changes to the code.

Price: $995 per CPU for the Standard Edition

www.alachisoft.com

Specify Cache Policies with NCacheManager
Specify Cache Policies with NCacheManager (Click the image for a smaller view)
Specify Cache Policies with NCacheManager
Specify Cache Policies with NCacheManager (Click the image for a larger view)

Send your questions and comments for Scott to toolsmm@microsoft.com.

Scott Mitchell author of numerous books and founder of 4GuysFromRolla.com, is an MVP who has been working with Microsoft Web technologies since 1998. Scott is an independent consultant, trainer, and writer. You can reach him at Mitchell@4guysfromrolla.com or via his blog at ScottOnWriting.NET.

All prices were confirmed at press time and are subject to change. The opinions expressed in this column are solely those of the author and do not necessarily reflect the opinions of Microsoft.

MSDN Magazine does not make any representation or warranty, express or implied with respect to any code or other information herein. MSDN Magazine disclaims any liability whatsoever for any use of such code or other information.


CLR Inside Out: IronPython and the Dynamic Language Runtime

CLR Inside Out
IronPython and the Dynamic Language Runtime
Bill Chiles

Contents
IronPython Hello World
Launching Ipy.exe
Introduction to the ASTs
Looking at the IronPython AST
Looking at the DLR AST
Looking at Generated Code
Understanding Dynamic Sites
How DynamicSite Objects Work
The Big Payoff

T
he Microsoft® .NET Framework was designed to support a broad range of programming languages on a single runtime—the common language runtime (CLR). The CLR provides shared services to these languages, including garbage collection, just-in-time (JIT) compilation, a sandboxed security model, and support for tools integration. Sharing these features has two huge benefits for language implementers. It is easier to implement a language because much of the lower-level engineering work is already done. And languages running on the CLR can integrate seamlessly. Sharing libraries and frameworks allows languages new to the CLR to build on the work of others.

The CLR also includes support for dynamic languages, as IronPython 1.0 demonstrates (www.codeplex.com/ironpython). Dynamic programming languages deliver a powerful and productive experience for programmers, as James Schementi explained in the October 2006 installment of "CLR Inside Out" (msdn.microsoft.com/msdnmag/issues/06/10/CLRInsideOut). Now Microsoft is building the Dynamic Language Runtime (DLR), which adds to the CLR a set of services designed specifically to meet the needs of dynamic languages. The DLR adds functionality such as a shared dynamic type system, a standard hosting model, and support to make it easy to generate fast dynamic code and fast symbol tables. With these additional features, it is much easier to build high-quality dynamic language implementations for .NET. Furthermore, these features enable dynamic languages built on the DLR to share libraries written in other dynamic languages or in CLR-based static languages.

The DLR lets you build the best experience for your favorite dynamic language. This means your experience coding in your language should feel like it always does. You should also benefit from excellent tools, great performance, and shared libraries. Because using the DLR means you can share standard functionality, you have more time to focus on the features that make a language unique. For example, you can avoid having to implement garbage collection, code generation, and method caching.

The DLR uses adaptive method caching to produce fast dynamic programs, and all language implementations on the DLR benefit from this shared work. Code runs faster by avoiding repeated searching of class precedence lists. It also avoids resolving overloads on .NET methods each time you call on an object (for example, call a method, foo, on some object, o).

The source code for IronPython and the DLR is available on Codeplex under the Berkeley Software Distribution (BSD)-style Microsoft Permissive License (see the 2.0 alpha release). This is a very early release, and there is still significant work to be done. There are low-level mechanisms to design, performance enhancements to implement, and documentation to write. By the time you read this, there will be Codeplex projects available for the DLR code itself and for IronRuby, in addition to IronPython. Though we are working on DLR JScript® and VBX implementations, these may be available only in binary form.

IronPython Hello World

I'll walk through a simple Python program (a twist on Hello World) and discuss what happens when it executes in ipy.exe. The program I'll examine is msdnmag.py:

def yo(yourname):
   text = "hello, "
   return text + yourname

print yo("bill")

I've added something a little beyond the classic "print hello" functionality, so I can discuss more interesting aspects of the IronPython implementation. For instance, I'll be able to demonstrate name binding for identifier references and caching the meaning of "+" in the yo function.

I'm using IronPython 2.0 alpha, so take a few minutes now to download it so you can walk through it with me.

To begin, open the ironpython.sln file in Visual Studio® 2005 and build the solution with the Debug solution configuration. Then right-click on the IronPythonConsole project and select the Debug tab in the left navigation bar. Set this project as the start project (first set of radio buttons under Start Action). Next, under Start Options, enter msdnmag.py as the command-line argument. Finally, copy the msdnmag.py Python code listed above into a file called msdnmag.py in the \bin\debug\ directory that was created when you built the solution.

Launching Ipy.exe

Now let's see how ipy.exe starts up. The DLR provides some default console classes so that language implementers can easily get an interpreter running (the implementer still needs to write parsers and a runtime implementation for his language). The console classes handle input and output, command-line switches, and some shared diagnostic switches the DLR implements. This saves language implementers work in getting some first code running on the DLR, and it provides a testing tool.

To get started, open <installdir>\Src\IronPython\Compiler\Generation\PythonScriptCompiler.cs. Then set a breakpoint in the ParseFile function on the line "using (Parser parser = ...."

Use F5 (Debug | Start Debugging) to run the program. You'll first hit the breakpoint while parsing a code snippet that will initialize the Python execution engine. The code snippet loads the Python site.py file for machine-specific initialization. So, how did you get here? If you look at the call stack, you will see that ipy.exe starts in PythonConsoleHost's Main function, which calls into shared DLR convenience code. Execution comes back into IronPython-specific code to process the command line, which causes the msdnmag.py file to run.

The PythonConsoleHost class is very small. It has a very short Initialize method that sets the LanguageProvider (and therefore the execution engine) to be the IronPython implementation. PythonConsoleHost's Main method simply calls into the default ConsoleHost class provided by the DLR.

ConsoleHost is a helper class that allows language implementers to quickly build a cmd.exe-style interaction shell. The ConsoleHost class gets the CommandLine helper object from the LanguageProvider. When the ConsoleHost runs the CommandLine object, which calls the CommandLine object's Initialize method, the code starts executing in the PythonCommandLine object.

In its Initialize method, the PythonCommandLine object sets up the Python path for loading modules, sets up some built-in modules, and imports IronPython's site.py file. This is all standard Python behavior. PythonCommandLine imports the site.py file by calling IScriptEngine.Execute on the code snippet string, "import site.py".

You will first hit the breakpoint in the call to PythonScriptCompiler.ParseFile due to parsing "import site.py", but let's move on because msdnmag.py is not running yet.

Introduction to the ASTs

When ipy.exe executes msdnmag.py, the IronPython implementation and the DLR work together to compile the code in the file. At a basic level, compilers are pipelines that start with a parser that produces a data structure representing the code. This data structure is an abstract syntax tree, or AST in compiler-speak. The compiler transforms the AST or creates new data structures as it goes through stages analyzing the code. Then, based on the resulting structures, the compiler generates machine code or intermediate language (IL) code for a virtual machine like the CLR.

IronPython code first generates an AST particular to IronPython, and then it maps this tree to a DLR AST. Some languages have their own intermediate tree so that they can perform analysis or support tools (code editors) over their ASTs. Tools need a tree that is close to source code that users have typed in an editor. Many languages may have ASTs that will be similar to the DLR's, but the DLR ASTs will have more information about semantics explicitly represented. You might think of the DLR AST as one of the various transformations that later stages of a compiler need.

It is interesting to note that the DLR lazily compiles portions of the ASTs when the code runs. This is similar to the way the CLR uses JIT compilation only when code runs. You pay a little more in performance the first time the code runs, but subsequent executions are fast. Later on, you'll see that pieces of the AST are not compiled until specific lines of code execute.

Looking at the IronPython AST

Let's get back to running the program so we can look at the IronPython AST. First, hit F5 (Debug | Continue) to stop at the breakpoint again when the IronPython engine starts parsing the contents of site.py to execute it. If you look in the Visual Studio Locals window, you can expand "cc", then "SourceUnit", and then look at either Name or DisplayName to see what ParseFile is processing.

Hit F5 again. We stopped the last time at this breakpoint. If you look in Locals now, you'll see that cc.SourceUnit.DisplayName is msdnmag.py. This is the file I added as a command-line argument to ipy.exe. In the Locals window, cc.SourceUnit.Name is "__main__" because Python names the primary executing module this way.

Now, hit F10 (Debug | Step Over) three times to step over the line

ast = parser.ParseFileInput()

Now you can look at the IronPython AST in the debugger, as shown in Figure 1.

Figure 1 IronPython AST in the Debugger
Figure 1 IronPython AST in the Debugger

You can see the AST root node is a SuiteStatement, representing a series of statements, and it has a Statements member. Expanding the first statement (index zero), you see it holds a FunctionDefinition node. It has a Body member that is a SuiteStatement for the statements of the function's definition, and it has a Name member which is the name that will be bound to the resulting function object.

Pictorially, with some details elided, the IronPython AST for the entire msdnmag.py file looks like Figure 2.

Figure 2 IronPython Abstract Syntax Tree for msdnmag.py
Figure 2 IronPython Abstract Syntax Tree for msdnmag.py(Click the image for a smaller view)
Figure 2 IronPython Abstract Syntax Tree for msdnmag.py
Figure 2 IronPython Abstract Syntax Tree for msdnmag.py (Click the image for a larger view)

There is a mixture of visual representation in the tree. For the most part, if an AST node has a member that points to another AST node, the picture shows an arrow pointing to the subnode. Usually the subnode is named as the type of a member in the parent node. For example, the FunctionDefinition node has a member of type SuiteStatement, and the next node is a SuiteStatement. Sometimes a node contains a description of the subnodes using indentation and curly braces. I chose to show these nodes that way to simplify the diagram.

Looking at the DLR AST

IronPython is now ready to build the DLR AST so that the final stages of compilation can run. Below our breakpoint in ParseFile you can see the call to BindAndTransform, which transforms the IronPython AST into a DLR tree. During that process, IronPython resolves all identifiers so that their representation in the DLR tree points to the declaration/allocation information for the variables they represent. Of course, for some identifiers, they need to compile to an AST node that represents searching for the value at run time; for example, the identifier could resolve to a module member added at runtime or to a late-bound value supplied by a host via the module's dictionary.

There is a lot of detail in this section, perhaps of interest only if you're looking to port a language to the DLR. If you only look at the picture of the DLR tree, note there are MethodCallExpression nodes and ActionExpression nodes. MethodCallExpression nodes compile to calls to an IronPython runtime function that performs an operation. Every time this function gets called, it performs the same work given the arguments passed to it.

The ActionExpression node is particularly interesting because it represents an abstract operation or action. Abstract actions, for example, include fetching a member, indexing an object, calling an object, performing addition on objects, and so on. The DLR compiles ActionExpression nodes into dynamic call sites. Dynamic sites are a runtime mechanism that caches methods appropriate to specific combinations of action and argument types. These allow dynamic code to run faster with little or no static type information at compile time. I'll explain dynamic sites in more detail later.

Let's get back to stepping through the program's execution. Hit Shift+F11 (Debug | Step Out) twice to stop in SourceUnit.Compile, then use F10 (Step Over) to perform the assignment to the variable "block", which will hold the root of the DLR AST for the entire file.

Now we can look at the DLR AST. In the Visual Studio Locals window, expand the node called block, which is a CodeBlock AST node. This is the root node for the file of Python code. Part of translating a language's specific syntax tree to the DLR's AST is clearly designating where variables are declared (explicitly or implicitly) and which variables identifiers refer to. If you expand block's variables member, you'll see two variables declared in the module's scope, "__name__" and "yo". (Expand elements 0 and 1 to see the Variable object's name members.) The first variable is a bound name that Python requires and creates for modules. The second is the module variable that holds our function definition.

Before drilling into the body, take a quick look at a partial expansion of the DLR AST in Figure 3, which reflects a similar representation to the IronPython AST you saw earlier.

Figure 3 The DLR AST
Figure 3 The DLR AST(Click the image for a smaller view)
Figure 3 The DLR AST
Figure 3 The DLR AST (Click the image for a larger view)

Expand the Body property under the block local. Due to the Visual Studio debugger's display characteristics, you need to expand the first node under the body node to actually see the BlockStatement's contents. This DLR BlockStatement AST node corresponds to the IronPython AST's SuiteStatement node, and each represents a series of statements. Expand the statements property.

The first statement (index 0) is an EmptyStatement, which is an artifact of IronPython's translation to the DLR tree. IronPython allocates two statements in case there's a module documentation string, which would cause the creation of an assignment to __doc__. In this case the first statement remains as a placeholder EmptyStatement since there's no documentation string.

The second statement (index 1) is what's interesting because it is the BlockStatement for the rest of the file, which is the code I wrote. This BlockStatement contains an ExpressionStatement followed by a BlockStatement (discussed later). The ExpressionStatement node wraps a BoundAssignment node so that the resulting value of the assignment gets popped off the stack; Python assignments do not return values. The BoundAssignment has name and value members. They represent setting the local variable yo (local to the module the Python code executes in) to the result of a function call. The function call, represented by a MethodCallExpression, calls a runtime helper function that creates an IronPython function object. MethodCallExpression has members indicating that the call is to a method named MakeFunction and what arguments the call gets. One argument is a CodeBlockExpression AST node for the function's body, and another is an array of parameters the created function will take.

Expand the MethodCallExpression AST node, which is the value member of the BoundAssignment. Look at the third element (index 2) of the Arguments property, you'll see the CodeBlockExpression for the body of yo. It has a Block property that is a CodeBlock. The CodeBlockExpression causes the CodeBlock it wraps to turn into a callable value that can be assigned to a module variable. Before we go into the body of the yo function's AST, look at Figure 4, which is a diagram of the entire DLR AST for msdnmag.py.

Figure 4 Entire DLR AST for msdnmag.py
Figure 4 Entire DLR AST for msdnmag.py(Click the image for a smaller view)
Figure 4 Entire DLR AST for msdnmag.py
Figure 4 Entire DLR AST for msdnmag.py (Click the image for a larger view)

There are a couple of notes about the diagram. As with the previous diagram, there is a mixture of visual representation in the tree. For the most part, if an AST node has a member that points to another AST node, the picture shows an arrow pointing to the subnode. Sometimes a node contains a description of the subnodes using indentation and curly braces instead of more arrows and boxes. The snapshot of the Locals window in Visual Studio shows the AST down to the MethodCallExpression node on the left side of the diagram. The first arrow is dotted because the picture skips the BlockStatement with the EmptyExpression. You can expand the data structures in the Locals windows further to see the full structure of the tree, as shown in the diagram.

The CodeBlock node representing the body of the yo function has members for variables, parameters, and the body AST. This is similar to the CodeBlock that represented the entire msdnmag.py file. As you will see later, the CodeBlock for the file turns into an Initialize method for the module. The yo function has one local variable, text, that you can see if you expand the variables member, expand element 0, and then expand the Variable object. Following a similar expansion, you can see the yo function has one parameter, yourname.

The body of the CodeBlock is a BlockStatement, which has two statements: an assignment and a return. As you saw above with the assignment to yo, the BlockStatement first has an ExpressionStatement that holds a BoundAssignment. This assignment represents setting text to "hello, ". The BoundAssignment object has a ConstantExpression value member and a Variable member. The Variable object describes text as a local variable and has a block member that points back to the CodeBlock as the scope of the local variable.

The second statement in BlockStatement is a ReturnStatement whose expression member is an ActionExpression. This AST node is particularly interesting as I explained earlier. This ActionExpression node has an action member that is a DoOperationAction, which represents an Add operation in this case. The ActionExpression has an arguments member with two elements that are BoundExpression objects. The first BoundExpression has a variable member that represents the local text, which was set to "hello, ". The second has a variable member that represents the parameter yourname.

Now let's go back up the tree to the BlockStatement that contains two ExpressionStatments. One is for the BoundAssignment of yo to a function object. The second ExpressionStatement also exists so that the compiler emits code to pop its expression's value off the stack. The ExpressionStatement has an expression member that is a MethodCallExpression.

The MethodCallExpression represents the call to IronPython's runtime function that implements the print statement. It has a method member that is a .NET RuntimeMethodInfo describing print. The MethodCallExpression has an arguments member that is an ActionExpression. As discussed above, this compiles to a dynamic site for fast calls. The ActionExpression has an action member that is a CallAction for the call to yo. This node also has an arguments member with two elements. One is a BoundExpression with a variable member representing that the expression is the value of the local yo (yo is local to the module in which it is defined). The other argument is a ConstantExpression with a value member that holds the string "bill".

That concludes our walk through the DLR AST. You can see how the IronPython tree directly represents the Python code you see. The DLR AST has more explicit information in it. It contains identifier binding information and explicit blocks to represent scopes. It contains explicit representation of runtime method invocations (the call to Print) rather than actions that compile to dynamic sites (the node for "text + yourname"). The DLR AST also contains nodes that force results of expressions to pop off the stack so that the code adheres to Python semantics.

Looking at Generated Code

Now that you've seen how the process starts up and performs the parsing, let's look at some generated code. The easiest way to do this is to use switches for ipy.exe and Lutz Roeder's Reflector program. The switches cause ipy.exe to generate static code (as opposed to Lightweight Code Generation or dynamic methods) and save it to disk. Download Reflector from aisto.com/roeder/dotnet/ and then invoke the following command line while in the bin debug directory where you built ironpython.sln:

ipy.exe -D -X:SaveAssemblies -X:StaticMethods msdnmag.py

You'll find two files in the directory afterwards, snippets1.dll and msdnmag.exe. Now launch Reflector on these files with this command line (filling in the absolute path as necessary):

C:\where\you\put\reflector.exe snippets1.dll, msdnmag.py

You can look down the list of DLLs and EXEs to find msdn and snippets1. Expand msdnmag, msdnmag.exe, "{} -", and finally "__main__$mod_2". Now double-click the Initialize method. This is the body of the msdnmag.py file. You should see the disassembled source code from the IL that the DLR generated. If you have used Reflector before, you know that it is a great tool, but it also has a few flaws. It can generate extra temporary variables for example, so you need to take the C# code you see with a grain of salt.

I won't dwell on the Initialize function, but you can see that yo is being set to the result of the call to MakeFunction, as you saw in the AST. You can see that Initialize then calls the runtime helper PythonOps.Print on the result of invoking yo. Notice the fragment "Call-Simple-1.Invoke". The Call-Simple-1 object is part of the method caching mechanism. I will explain the method caching further by exploring how it shows up in the yo function.

Let's look at the yo function. Double-click yo$1 in the left pane. You can see where it sets text to be "hello," and where it returns the result of "DoOperation-Add-0.Invoke(text, yourname)". That is the essence of the code I wrote in Python. In a moment I will focus on DoOperation-Add-0, which is the object that caches method lookup results. I'll also look at some of the runtime-generated functions in snippets1, as I drill into DoOperation-Add-0.

Understanding Dynamic Sites

Dynamic sites allow dynamic language code to run fast. They manage the method caching for performing specific operations on specific types of objects. The dynamic sites mechanism the DLR uses is based on research and experience with tried-and-true dynamic language implementations. You can see objects in the generated code such as Call-Simple-1 and DoOperation-Add-0, which are instances of derived types from DynamicSite<Targ1, Targ2, Tresult>. I'll briefly explain the caching theory here, but you can search the Web for "dynamic language method caching" or "polymorphic inline method caching" for more information.

Dynamic language performance is hindered by the extra checks and searches that occur at each call site. Straightforward implementations have to repeatedly search class precedence lists for members and potentially resolve overloads on method argument types each time you execute a particular line of code. In an expression such as o.m(x, y) or x + y, dynamic languages need to check exactly what kind of object o is, what is m bound to for o, what type x is, what type y is, or what "+" means for the actual runtime type of x and y. In a statically typed language (or with enough type hints in the code and type inferencing), you can emit exactly the instructions or runtime function calls that are appropriate at each call site. You can do this because you know from the static types what is needed at compile time.

Dynamic languages provide great productivity enhancements and powerful terse expressions due to their dynamic capabilities. However, in practice code tends to execute on the same types of objects each time. This means you can improve performance by remembering the results of method searches the first time a section of code executes. For example, with x + y, if x and y are integers the first time that expression executes, we can remember a code sequence or exactly what runtime function performs addition given two integers. Then each time that expression executes, there is no search involved. The code just checks that x and y are integers again, and dispatches to the right code with no searching. The result can literally be reduced to inlined code generation with a couple of type checks and an add instruction, depending on the semantics of an operation and method caching mechanisms used.

How DynamicSite Objects Work

Static language compilers can select methods or emit specific code at compile time to perform operations such as addition, member fetching, and indexing. Since the DLR cannot always know at compile time what to emit, it emits code to call an Invoke method on a DynamicSite object. This object captures the operation and a delegate (called by Invoke) that contains the caching logic. This caching logic is updated each time the delegate sees a new combination of argument types at run time. (Note that delegates actually wrap pointers to functions, but, for brevity, I use delegate as if it is the function.) That's the simple story; next up is a more detailed look.

The delegate starts out with one call in it to UpdateBindingAndInvoke. The first time a call site executes (let's just consider x + y), UpdateBindingAndInvoke queries the arguments for an Add operation implementation for the type of x and the type of y. If it gets one, it generates a new delegate that encodes a check for x and y having the same types you just saw. In a later call, if x and y have the same types, the new delegate code calls the implementation that we got. If x or y have a different type in a later call, the delegate falls through all the cache checks and calls UpdateBindingAndInvoke again, which generates a new delegate. The newest delegate's code will capture the first tests of x and y as well as the new tests, calling whichever target implementation matches the types.

It's time to take a look at the DoOperation-Add-0 delegate that the DLR generated from running the code in msdnmag.py. Go back to Reflector, and this time expand the snippets1, snippets.dll, "{} -", and "Type$_stub_$4" nodes in the left pane. Click on the Handle method, and in the right pane you'll see the code in Figure 5.

Figure 5 Disassembled "+" Cache (Close Figure 5)
public static object Handle(object[],
    FastDynamicSite<object, object, object> site1,
    object obj1, object obj2)
{
    if (((obj1 != null) && (obj1.GetType() == typeof(string)))
        && ((obj2 != null) && (obj2.GetType() == typeof(string))))
    {
        string text;
        string text1 = text =
            StringOps.Add(Converter.ConvertToString(obj1),
                          Converter.ConvertToString(obj2));
        return text;
     }
     return site1.UpdateBindingAndInvoke(obj1, obj2);
 }

This is the disassembled code from the IL that the DLR generated for the DoOperation-Add-0 delegate after executing "text + yourname". If we called the yo function again, this delegate would execute. This code has some performance issues you might spot, but more on that later. You can see that the code tests whether the two arguments are strings and calls the IronPython runtime implementation of addition given two strings.

If one of the arguments is not a string, then the delegate calls UpdateBindingAndInvoke to generate a new delegate. The new delegate would replace the current one (above) so that the next time DoOperation-Add-0.Invoke runs, it will call the updated delegate. I changed the msdnmag.py code so that the "text + yourname" executes on two integers for a second call to yo. I then found the second delegate that the DLR generated after the second call. It looked like Figure 6.

Figure 6 Disassembled "+" Cache Two (Close Figure 6)
      public static object Handle(object[]
    FastDynamicSite<object, object, object> site1,
    object obj1, object obj2)
{
    if (((obj1 != null) && (obj1.GetType() == typeof(int)))
        && ((obj2 != null) && (obj2.GetType() == typeof(int))))
    {
        return Int32Ops.Add(Converter.ConvertToInt32(obj1),
                            Converter.ConvertToInt32(obj3));
    }
    if (((obj1 != null) && (obj1.GetType() == typeof(string)))
        && ((obj2 != null) && (obj2.GetType() == typeof(string))))
    {
        return = StringOps.Add(Converter.ConvertToString(obj1),
                               Converter.ConvertToString(obj2));
    }
    return site1.UpdateBindingAndInvoke(obj1, obj3);
  }

I cleaned up the bogus temporary variables that Reflector inserted. If you do the extra experiment I did, you'll get slightly different code. You'll see that now the code tests if the arguments are integers. If they are, it calls the runtime helper function that implements Add on integers. The same code that I had before follows the integer test and target code. I chose to order the tests with the most recent types tested first. With profiled runs of the program, you could imagine generating all the right arguments' tests in the optimal order. Of course, the delegate falls back to calling UpdateBindingAndInvoke in case the arguments have a new type combination that has not been seen before.

You will probably notice performance issues with the code. The DLR could generate better code today, but as with any alpha release, the DLR makes trade-offs on functionality and code generation. You may notice that the code tests for a type, string, and then converts the argument to a string. There are two problems with this. The first is that the .NET Framework 2.0 JIT does not propagate type information from "if" tests to the consequent code block. Since the Add implementation is a statically typed method, the arguments need to show up as strings to it. The second problem is the DLR-generated code does a slow call to a runtime conversion function. The DLR could have emitted a cast operation here.

The last performance issue to mention is that the DLR today does not structure tests to avoid repeating the same one. In my updated delegate that knows how to quickly add two integers or two strings, I test the arguments for null. I do this multiple times as I move through the tests when I don't have to do that. When UpdateBindingAndInvoke searches for operation implementations, it actually asks the objects how to do the operation. It calls on the objects to provide a rule for how to perform the operation represented by the DynamicSite. The rule contains an AST for the test to perform and an AST for the target code to execute if the test is true. The DLR could perform tree transformations across the tests to optimize the delegate's code even more.

As a final point, because I used dynamic sites for fetching members of objects, I have to handle changes to instances and dynamic types. The DLR cannot assume for o.m() that if o points to the same object, then it knows exactly which m to invoke. Some languages allow types to change at run time, and they can replace members, essentially overriding a member in an instance. The DLR uses a global version counter that it increments for new types and changes to types. There are various trip wires that cause a type's version to change, such as changing members. Any DynamicSite caches that refer to objects where their type's version has changed will fail the cache. Then the DynamicSite will search again and update the delegate.

The Big Payoff

The generated DynamicSite types are generic types. Using generic types doesn't help very much in the example Python code in msdnmag.py. However, in an expression such as "if x < 1:" you can generate a DynamicSite<Object, Int, Bool>. The site's Invoke method will be statically typed to take one argument as an integer and return a Boolean. The delegate inside the dynamic site is also statically typed in this way, which makes the resulting code faster. The delegate only has to test one argument in its caching, and as the stack unwinds, the JIT knows a Boolean value is flowing to the right location. This eliminates any casts or checks surrounding the if test.

Some dynamic languages have optional explicit typing. Even if they don't, implementations can infer types from calls to .NET static methods, from literal constants, and so on. They can propagate this type information over lifetimes of variables, branches of conditionals, and the like. When languages have type information, they can generate DLR AST that in turn compiles to DynamicSite types with full type information. That can result in inline code generation for the Invoke method call and target code call in the cache.

Today, the DLR generates generic DynamicSite types with six or fewer generic type parameters. The first N-1 parameters represent the types of arguments, and the Nth represents the result type of the operation. After six types, you have to generate AST that just performs method calls to runtime helper functions. Those functions have to do the slow work to compute everything at run time. In the future, the DLR will allow you to use generic tuples to provide large numbers of statically typed arguments. We might also increase the number from six as we figure out the sweet spot for most programs.

You should have a pretty good idea now how explore both language-specific ASTs and DLR ASTs. With some basic information on simple trees, you can examine the way certain languages have been built on the DLR. If you are trying to implement a language on the DLR yourself, you can use this technique. If you're not, it might be fun to just look at what is happening under the covers.

You also got to see some of the shared infrastructure the DLR offers to language implementers. There is a lot to leverage from the CLR and the DLR—garbage collection, JIT compilation, dynamic sites, common dynamic type model, and so forth. Implementing languages on the .NET runtime produces pretty good results now—and it will just keep getting better. Version 1 of the DLR will be great. Soon implementing dynamic languages on .NET will be amazingly easy and the results will be excellent.

Send you questions and comments to clrinout@microsoft.com.

Bill Chiles is a Senior Program Manager at Microsoft who has worked on dynamic language projects (CMU Common Lisp, Dylan) and tools for most of his career. Bill spent nine years on the Visual Studio Core Technologies team and now works on IronPython and the Dynamic Language Runtime.


Basic Instincts: Type inference in Visual Basic 2008

Basic Instincts
Type inference in Visual Basic 2008
Bill Horst

Contents
Why Is Type Inference Necessary?
Type Inference and Lambda Expressions
Other Implications
Go To Type Definition
Enabling and Disabling Type Inference

I
n order to support Language Integrated Query (LINQ), a suite of new technologies was added to the upcoming release of Visual Basic® 2008 that includes type inference. In earlier versions of Visual Basic, a member's type was assumed to be Object unless a different type was explicitly declared in code, as shown in Figure 1. A drawback to declaring a variable this way is that the compiler is only able to assume that the value of the variable will be of type Object. The experience for the developer is that IntelliSense® is only able to display information for the members that are common to all Objects, though there may be other members available on the actual instance at run time. With late binding, the other members are bound at run time, which means they will not be verified in any way until it is time for the line to be executed. So, nonexistent members (such as cust.Name in Figure 1) can be referenced in code, and the problem will not be caught by the compiler. This can easily result in a MissingMemberException and generally requires you to keep track of more information on your own.

Figure 1 Lack of Type Inference in Visual Basic 2005 (Close Figure 1)
Class Form1
    Sub Main()
        Dim a = 3                   ' Type: Object    Value: 3 {Integer}
        Dim b = DateTime.Now        ' Type: Object    Value: Current Time

        Dim cust = GetCustomer(someID)
        MsgBox(cust.Name) ' Customers have FirstName and LastName fields.
                          ' This code generates an exception at Run-Time.

        Dim procs = Process.GetProcesses
        For Each g In procs   ' Compile Error: 'g' is not declared
            Console.WriteLine(g.Id)
        Next
    End Sub
End Class

However, with type inference in Visual Basic 2008, the types of method-level members are inferred based on the right-hand side of any assignments in the declaration statements. You can find several examples in Figure 2. Here, the compiler will catch the reference to the nonexistent member cust.Name shown in Figure 1, and IntelliSense information will be provided for all available members, as if the type were specified explicitly. In the For loop shown in Figure 2, the variable g is recognized as a declaration, with the type of the "procs" expression.

Figure 2 Type Inference in Visual Basic 2008 (Close Figure 2)
Class Form1
    Sub Main()
        Dim a = 3                   ' Type: Integer   Value: 3
        Dim b = DateTime.Now        ' Type: Date      Value: Current Time

        Dim cust = GetCustomer(someID)
        MsgBox(cust.Name) ' Here we get a compiler error, catching the
                          ' problem quickly

        Dim procs = Process.GetProcesses
        For Each g In procs         ' Type: Process
            Console.WriteLine(g.Id) ' No compile errors
        Next
    End Sub
End Class

However, there are times when type inference doesn't happen. For local Dim statements, type inference only occurs when there is an assignment on the declaration line. So, assignments made outside the declaration of the variable will cause the compiler to assume that Object is the type. Object is also still inferred as the type for class-level members, so type inference does not apply to functions, subs, properties, class/structure fields, and so on. Some specific examples are shown in Figure 3.

Figure 3 Cases with No Type Inference (Close Figure 3)
Class Form1
    Sub Main()
        Dim d         ' Assignment not on the declaration line
        d = 3         ' Type: Object    Value: 3 {Integer}
    End Sub
                      ' Class-level
    Dim e             ' Type: Object    Value: Nothing
    Dim f = 3         ' Type: Object    Value: 3 {Integer}

    Function Func1()  ' Type: Object    Value: 3 {Integer}
        Return 3
    End Function
End Class

Why Is Type Inference Necessary?

Type inference is necessary in Visual Basic 2008 because of new language constructs that enable the creation of a type that is not explicitly defined anywhere. In order to assign a variable to an expression with a non-explicitly defined type, it is necessary to infer the type, since it would be impossible to specify it in code.

These non-explicitly defined types are called anonymous types. An object can be created and certain members initialized without being previously defined. This enables LINQ statements to specify a varying number of fields (and in different orders) without having to define objects for every possible variant in advance. Because the object does not necessarily match an already-defined type, the compiler generates a type implicitly (because the name of this type is inconsequential and is not exposed to the developer for use in code, it's called an anonymous type). Using the type inference functionality, the compiler is able to treat this object of an anonymous type just as it would treat an object of an explicitly defined type. Anonymous types will be most useful to LINQ users who write SQL-style queries in Visual Basic.

Here's an example of how anonymous types can help in your LINQ development. Suppose you have a database that includes records of your company's orders, and you want to view certain information for all the orders that have shipped to the state of Washington. The following SQL code assumes a table called Orders whose records contain various fields, including ID, Date, Address, City, State, Zip, and Shipped. The query would return all records in the table where the Shipped field has the value True and the State field has the value Washington:

SELECT Orders.ID, Orders.Date AS OrderDate, Orders.Address,
       Orders.City, Orders.State, Orders.Zip
FROM Orders
WHERE Shipped = 'True' AND State = 'Washington'

With the development of LINQ, a similar operation can be performed in Visual Basic. The following code performs this same query on Orders and assigns the result to the variable OrdersShippedToWA. Orders could be a database table, an in-memory array or collection, or any type that implements the IEnumerable interface:

Dim OrdersShippedToWA = From Ord In Orders _
                        Where Ord.Shipped _
                            And Ord.State = "Washington" _
                                Select Ord.ID, OrderDate = Ord.Date, _
                                Ord.Address, Ord.City, _
                                Ord.State, Ord.Zip

The type that will be inferred for OrdersShippedToWA is IEnumerable(Of <anonymous type>). Each element in the IEnumerable will then have the members that were selected in the query—ID, OrderDate, Address, City, State, and Zip. As you can probably imagine, LINQ is much easier to use and more agile if you don't need to define a type for each combination of members you'd like to use in the Select portion of your query expressions. For this reason, the Visual Basic compiler generates an anonymous type containing the appropriate members and infers that type if an element is referred to later in code. In the following For loop, the type of the variable Ord is inferred as the same anonymous type I discussed for OrdersShippedToWA:

For Each Ord In OrdersShippedToWA
    Dim City As String = Ord.City
Next

In this example, the variable Ord is of a type that has not been explicitly declared, but whose member names are known. The background compiler is able to infer the type, and you get the same IntelliSense support to which you are accustomed. This is the primary reason type inference has been added to Visual Basic 2008.

Imagine another scenario where you want to deal with the entire Order object. If only one expression is being selected by the query, the specific type is inferred. If there are methods or other members defined for the type used in the collection, they can be called through type inference, as well:

Dim SortedWAOrders = From Ord In Orders _
                     Select Ord _
                     Order By Ord.ID Ascending

Dim FirstShipTime = SortedWAOrders(0).CalculateShipTime()

In fact, thanks to type inference, you could use your methods in the query itself. Consider the following example, in which the results are returned in order of the ship time calculated by a method:

Dim SortedShipTimes = From Ord In Orders _
                      Select Ord _
                      Order By Ord.CalculateShipTime() Ascending

There may be occasions where it is convenient for you to initialize an anonymous type in code, so this is also supported in Visual Basic. In Figure 4, Part A shows the NewCustomer variable created without an explicit type. Note that the types of the members in the definition are being inferred as well, since they are not defined anywhere. Part B shows another assignment, where a member of the anonymous type is recognized by the compiler. IntelliSense functionality is supported on the variable when it is referred to in the NewCustomerCity assignment. In Part C, a query called SeattleCustomers, which selects members that match the members of the anonymous type, is initialized. In this case, the compiler recognizes that an anonymous type already exists that matches the one needed for this statement. Instead of creating a new anonymous type, the same type is inferred for SeattleCustomers as for NewCustomer. In Part E, the object assigned to NewCustomer can be added to the data from the SeattleCustomers query because type inference recognized the same anonymous type could be used in both places.

Figure 4 Anonymous Types Matched from Query and Variable (Close Figure 4)
'[Part A] Anonymous Type variable declared
Dim NewCustomer = New With {.Name = "Bill Horst", _
                            .Age = 25, _
                            .City = "Seattle"}

'[Part B] Member recognized by Compiler/IntelliSense
Dim NewCustomerCity = NewCustomer.City

'[Part C] Name, Age and City selected from records in
'         Customers database table
Dim SeattleCustomers = From cust In db.Customers _
                       Where cust.City = "Seattle" _
                       Select cust.Name, cust.Age, cust.City

'[Part D] Seattle Customers stored in a variable with
'         type List(Of <anonymous type>)
Dim SCList = SeattleCustomers.ToList()

'[Part E] Variable Type and Query Result Type match
SCList.Add(NewCustomer)

Type Inference and Lambda Expressions

Type inference is also helpful in accommodating Lambda expressions. A Lambda expression is a new Visual Basic language feature that allows the use of delegates for simple functions in an inline fashion. This is particularly useful for passing simple delegates as parameters. Without having to even name a function, a Lambda expression can be passed, declaring parameters and the expression to return. In the following example, a function is declared that accepts a Customer and a String and returns a Boolean representing whether or not the Customer's city matches the String. That function is then passed as a delegate to the Filter method, presumably to filter based on this Boolean value:

Orders.Filter( _
    Function(cust As Customer, city As String) cust.City = city)

Since this is basically a function definition without a return type, it becomes clear how type inference can be useful in determining the expression's type to declare the proper delegate and verify that type is valid.

Other Implications

When Option Explicit is turned off, a local variable can be used in code without an explicit declaration. As with the case described previously, the variable is assumed to be of type Object and all calls are late-bound. It is worth noting that type inference does not occur on implicitly defined variables, so the behavior has not changed at all. The following code shows an example:

Sub SwapTwoInts(ByVal x As Integer, ByVal y As Integer)
    z = x
    x = y
    y = z
End Sub

Using Visual Basic 2005, it was possible to declare a temporary variable implicitly in the Immediate Window while debugging by assigning some expression to an identifier not defined in the current scope. The result was that a variable of type Object was created and assigned the value specified, much as if this assignment was made in code with Option Explicit Off. In Visual Basic 2008, the behavior I described for the Immediate Window and the behavior I described with Option Explicit Off will be the same as they were with Visual Basic 2005, thus type inference will not take place. If I enter the following two commands into the Immediate Window, the following result will be displayed, showing an Object variable given the Integer value 12:

intVar = 12
?intVar
12 {Integer}

Go To Type Definition

When types are explicitly given in a variable definition, the Visual Studio® "Go To Definition" action can easily be invoked from the context menu of the type identifier to determine where the type is defined. In the following case, the user can click on IEnumerable and the result will be IEnumerable(Of T) in the Object Browser:

Dim customers As IEnumerable(Of Customer) = GetCustomers()

With the new language features discussed here, I expect that it will more frequently be the case that the type is difficult to discern at a glance. Because of type inference, types need not be explicit, and with the new language constructs supporting LINQ, it can be quite obscure. The following variable is of type IEnumerable(Of T) as well, but it's much less obvious here, and there is no place to call Go To Definition to navigate to its type:

Dim customers = From cust In _
                    (From c In db.Customers Select c) _
                Where cust.FirstName = "Danae" _
                Select cust.LastName, cust.Address

For Each c In customers
...

This issue motivated the introduction of the Go To Type Definition command in Visual Studio 2008. You can also call the command from the context menu, so you can find the definition of a variable's type even if only the variable identifier exists in code. You can execute the Go To Type Definition command on the definition of a variable or a reference. In the previous code snippet, you could simply call Go To Type Definition on the customers variable in the definition or in the For loop, and you would be brought to the Object Browser with IEnumerable(Of T) selected (see Figure 5). Were the type explicitly defined in code, you would instead navigate to that location.

Figure 5 Go To Type Definition Command in a For Loop
Figure 5 Go To Type Definition Command in a For Loop

Enabling and Disabling Type Inference

One of the major implications of type inference support is that some code compiled in a previous version of Visual Basic may not compile in a project where type inference is enabled. This is why upgraded projects will have type inference turned off by default. The main area where such build errors could occur is in code that uses late binding.

Using earlier versions of Visual Basic, late binding occurs when Option Strict is turned off, and a variable with no explicit type is initialized to an expression. The variable is given type Object, and any member or method calls on that variable will be bound at run time:

' Late Binding with Visual Basic 2005
Dim x = 5
x = New List(Of Integer)
x.Sort()
x = New Queue(Of Integer)
x.Enqueue(6)

With type inference, such calls would result in compiler errors. Instead of giving the variable type Object, the compiler gives the variable a type to match the expression to which it is initialized. Late binding is still possible with type inference enabled, but Object must be given explicitly as the type:

' Late Binding with Visual Basic 2008
Dim x As Object = 5
x = New List(Of Integer)
x.Sort()
x = New Queue(Of Integer)
x.Enqueue(6)

There are other times you'll want to turn type inference off as well. Fortunately there is a compiler option not unlike Option Strict or Option Explicit, called Option Infer, that lets you turn type inference on or off. It's placed at the beginning of a code file like all compiler options in Visual Basic:

Option Infer On    ' This enables type inference for the file

Option Infer Off   ' This disables type inference, so declarations
                   ' with no type specified will use Object

If Option Infer is not specified for a particular code file, the project-level setting is used. The project-level default setting for Option Infer can be set on the Compile tab of the Project Designer. The Project Designer can be accessed from the Project menu or My Project node of Solution Explorer.

Option Infer is On by default in new Visual Basic 2008 projects and Off by default for upgraded projects in order to avoid breaking pre-existing code. File-level settings override this option for specific files.

While there are plenty of advantages to using type inference, as you will see when you begin using LINQ and other technologies that benefit from it, you have the ability to specify when it will be invoked and when it will not, providing you with maximum flexibility.

Send your questions and comments for Bill to instinct@microsoft.com.

Bill Horst is a Software Design Engineer in Test with the Microsoft Visual Basic Team. He has done much of the testing for LINQ Queries and also tests Visual Basic debugging.


Data Points: Common Table Expressions

Data Points
Common Table Expressions
John Papa

Code download available at: DataPoints2007_10.exe (150KB)
Contents
Views, Derived Tables, and CTEs
Structure of a CTE
Understanding CTEs
Rules of Recursion
Recursion Excursion
Wrapping Up

M
any projects that developers work on involve writing complex SQL statements that deviate from basic SELECT/FROM/WHERE types of statements. One such scenario involves writing Transact-SQL (T-SQL) queries that use derived tables (also known as inline views) inside a FROM clause. This common practice allows a developer to grab a rowset and immediately join that rowset to other tables, views, and user-defined functions in a SELECT statement. Another option is to use a view instead of a derived table. Both of these options have their advantages and disadvantages.

When working with SQL Server™ 2005, I prefer a third option of using Common Table Expressions (CTEs). CTEs can help improve the readability (and thus the maintainability) of the code without compromising performance. They also make writing recursive code in T-SQL significantly easier than it was in previous versions of SQL Server.

In this month's column, I am focusing on using CTEs to address common development scenarios. I will begin by describing how CTEs work and what scenarios they can be used to address. Then I will discuss the advantages of using CTEs versus using traditional T-SQL constructs, such as derived tables, views, and custom procedures. Throughout the column, I will give examples and explain how and where they can be used. I will also demonstrate how CTEs handle recursive logic and define how a recursive CTE operates. Note that all the code I discuss in this column is available for download from the MSDN® Magazine Web site and uses the Northwind and the AdventureWorks databases that come with SQL Server 2005.

Views, Derived Tables, and CTEs

CTEs can be useful when queries need to select from a set of data that does not exist as a table within the database. For example, you might want to write a query against a set of aggregated data that calculates values based on customers and their orders. The aggregated data might join the Customers, Orders, and Order Details tables together and calculate the sum and average values of the orders. And you may want to query against that aggregated rowset. One solution is to create a view that gathers the aggregated data first and then write a query against that view. Another option is to query against the aggregated data using a derived table. You can do this by moving the SQL statement into the FROM clause and querying against it.

Views are generally used to break down large queries so they can be queried against in a much more readable manner. For instance, a view can represent a SELECT statement that joins 10 tables together, selects dozens of columns, and filters out rows based on an involved set of logic. The view can then be queried against by other SELECT statements throughout the database. This abstraction provides easier access to the rowset being represented by the view, and there's no need to duplicate the data or store it in a temp table.

The view can also be reused throughout the database, assuming permissions allow this. In Figure 1, for example, a view is created and then used by another T-SQL statement. However, in situations where you want to gather data and only use it a single time, views may not be the best solution. Since a view is a database object that exists and is available throughout the database to all batches, creating a view that is only used in a single T-SQL batch is overkill.

Figure 1 View Being Queried (Close Figure 1)
CREATE VIEW vwMyView AS
SELECT
    EmployeeID, COUNT(*) AS NumOrders,  MAX(OrderDate) AS MaxDate
FROM Orders
GROUP BY EmployeeID
GO

SELECT
    e.EmployeeID, oe.NumOrders, oe.MaxDate, e.ReportsTo AS ManagerID,
    om.NumOrders, om.MaxDate
FROM
    Employees AS e
    INNER JOIN vwMyView AS oe ON e.EmployeeID = oe.EmployeeID
    INNER JOIN vwMyView AS om ON e.ReportsTo = om.EmployeeID

Another option is to create a derived table (also known as an inline view). A derived table can be created by simply moving a SELECT statement inside of a FROM clause surrounded by parenthesis. It can then be queried against or joined to just like a table or view. The code in Figure 2 solves the same query that Figure 1 solves, but instead of using a view it uses derived tables. While derived tables are only accessible within the statement in which they exist, tables generally make a query more difficult to read and thus to maintain. This problem can be multiplied if you want to use the derived table multiple times within the same batch, as you must then copy and paste the derived table to reuse it.

Figure 2 Query Using Derived Tables (Close Figure 2)
SELECT
    e.EmployeeID, oe.NumOrders, oe.MaxDate,  e.ReportsTo AS ManagerID,
    om.NumOrders, om.MaxDate
FROM
    Employees AS e
    INNER JOIN
        (SELECT EmployeeID, COUNT(*), MAX(OrderDate)
         FROM Orders
         GROUP BY EmployeeID) AS oe(EmployeeID, NumOrders, MaxDate)
        ON e.EmployeeID = oe.EmployeeID
    LEFT JOIN
        (SELECT EmployeeID, COUNT(*), MAX(OrderDate)
         FROM Orders
         GROUP BY EmployeeID) AS om(EmployeeID, NumOrders, MaxDate)
        ON e.ReportsTo = om.EmployeeID

A CTE is a nice fit for this type of scenario since it makes the T-SQL much more readable (like a view), yet it can be used more than once in a query that immediately follows in the same batch. Of course, it is not available beyond that scope. Additionally, the CTE is a language-level construct—meaning that SQL Server does not internally create temp or virtual tables. The CTE's underlying query will be called each time it is referenced in the immediately following query.

Therefore, this same scenario can also be written using a CTE, as shown in Figure 3. The EmpOrdersCTE gathers the aggregated data and is then used by the query that immediately follows the CTE. Using the CTE, the code in Figure 3 makes the query very readable (like a view), yet does not create a system object to store the metadata.

Figure 3 Querying with a CTE (Close Figure 3)
;WITH EmpOrdersCTE (EmployeeID, NumOrders, MaxDate) AS
(
  SELECT EmployeeID, COUNT(*), MAX(OrderDate)
  FROM Orders
  GROUP BY EmployeeID
)

SELECT
    e.EmployeeID,  oe.NumOrders, oe.MaxDate,
    e.ReportsTo AS ManagerID,  om.NumOrders, om.MaxDate
FROM
    Employees AS e
    INNER JOIN EmpOrdersCTE oe ON e.EmployeeID = oe.EmployeeID
    LEFT JOIN EmpOrdersCTE om ON e.ReportsTo = om.EmployeeID

Structure of a CTE

Now I'll demonstrate how to construct a CTE using a simple CTE as an example. A CTE begins with the WITH keyword. However, if the CTE is not the first statement in the batch, you must precede the WITH keyword with a semicolon. As a best practice, I prefer to prefix all of my CTEs with a semicolon—I find this consistent approach easier than having to remember whether I need a semicolon or not.

The WITH keyword is followed by the name of the CTE, which is then followed by an optional list of column aliases. The column aliases correspond to the columns that are returned by the SELECT statement inside the CTE. Following the optional column aliases is the AS keyword—this is required. And the AS keyword is then followed by the query expression that defines the CTE enclosed within parenthesis.

Take a look at this example:

;WITH myCTE (CustID, Co) AS
(
  SELECT CustomerID, CompanyName FROM Customers
)
SELECT CustID, Co FROM myCTE

The CustomerID and CompanyName columns are aliased with CustID and Co. Then immediately following the CTE is a SELECT statement that references the CTE using its column aliases.

Understanding CTEs

Before you design a CTE, you must understand how it works and what rules it follows. This section describes where CTEs can be used as well as what can and cannot be used inside a CTE. For starters, CTEs can be created and used inside of a T-SQL batch, a user-defined function, a stored procedure, a trigger, or a view.

A CTE can only be referenced by the statement that immediately follows the CTE. This means that if you want to use a CTE, you must write the query that refers to the CTE immediately after the CTE in the T-SQL batch. For example, the following batch will produce an error:

;WITH myCTE (CustID, Co) AS
(
  SELECT CustomerID, CompanyName FROM Customers
)
SELECT CompanyName FROM Customers WHERE CustomerID = 'ALFKI'
SELECT CustID, Co FROM myCTE

In this code, myCTE is only available for the first query that follows it. When the second query refers to myCTE, the CTE is not in scope and an exception is thrown (Invalid object name 'myCTE').

Also note that since a CTE is intended to be referred to by another query, which may then reprocess the data anyway, a CTE's query cannot contain statements such as ORDER and COMPUTE. However, complex statements such as FOR XML can still be used to define and operate on a CTE. For example, you could query a CTE and return its results using the FOR XML clause, as shown here.

;WITH myCTE AS
(
  SELECT c.CustomerID, c.CompanyName, o.OrderID, o.OrderDate
  FROM Customers c
  INNER JOIN Orders o ON c.CustomerID = o.CustomerID
)

SELECT CustomerID, CompanyName, OrderID, OrderDate
FROM myCTE FOR XML AUTO

Once a CTE is defined, it can be referenced multiple times by the first query that follows it. This is especially useful when a query needs to refer to the CTE more than once. The code sample in Figure 3 demonstrates how the EmpOrdersCTE is referred to twice by the query so it can grab the emplo yees and their supervisors. This is very useful when you need to reference the same rowset more than once; it is simpler to refer to the CTE twice than it is to duplicate the query.

A CTE does not have to be used by a SELECT statement; it is available for use by any statement that refers to the rowset that the CTE generates. This means a CTE can be followed by a SELECT, INSERT, UPDATE, or DELETE statement that uses the CTE. You can also use forward only and snapshot cursors on queries that use CTEs.

Furthermore, a CTE can be followed by another CTE. This technique can be used to build a CTE off of another CTE when you want to gather intermediate results into a rowset. When creating a CTE that builds off another CTE, you separate the CTE definitions with a comma.

The example shown in Figure 4 defines the EmpOrdersCTE, which gathers a list of employees and the total number of orders for each employee. The second CTE, named MinMaxOrdersCTE, queries the first EmpOrdersCTE and performs the aggregate functions on the rowset to determine the average, minimum, and maximum number of orders for the employees.

Figure 4 CTE Referencing Another CTE (Close Figure 4)
;WITH
EmpOrdersCTE (EmployeeID, NumOrders)
AS
(
  SELECT EmployeeID, COUNT(*)
  FROM Orders
  GROUP BY EmployeeID
),
MinMaxOrdersCTE (Mn, Mx, Diff)
AS
(
  SELECT MIN(NumOrders), MAX(NumOrders), AVG(NumOrders)
  FROM EmpOrdersCTE
)
SELECT Mn, Mx,    Diff
FROM MinMaxOrdersCTE

Multiple CTEs can be defined after the WITH keyword by separating them with a comma. Each CTE can be referenced by the CTE that follows it, building off of each other. The data manipulation language (DML) statement that follows the CTE definitions can also refer to any of the CTEs defined within the WITH clause.

Rules of Recursion

CTEs can also be used to implement recursive algorithms. Recursive logic is useful when you need to write an algorithm that calls itself—this is often done to traverse a nested set of data. Writing recursive logic can be complex, especially in a language like T-SQL. However, this is one of the specific problems that CTEs were designed to address. The basic formula for creating a recursive CTE is as follows:

  1. Create the query that returns the top level (this is the anchor member).
  2. Write a recursive query (this is the recursive member).
  3. UNION the first query with the recursive query.
  4. Make sure you have a case where no rows will be returned (this is your termination check).

Your recursive CTE will look something like this:

;WITH myRecursiveCTE(col1, col2, ... coln) AS
(
  -- Anchor Member Query
  UNION ALL
  -- Recursive Member Query that references myRecursiveCTE
)

When writing a custom recursion procedure that does not involve CTEs, you must include an explicit termination clause. The termination clause is responsible for making sure that the recursive algorithm eventually terminates and bubbles back up the recursive call stack. Without this clause, your code could end up in an infinite loop.

CTEs, however, have two aspects that help with handling termination clauses. The first is an implicit termination clause that occurs when the recursive member returns zero records. When this happens, the recursive member query does not invoke the CTE recursively but instead bubbles back up the call stack. The other is that you can explicitly set the MAXRECURSION level.

The MAXRECURSION level can be set explicitly in a batch that contains the CTE or through a server-side setting (the server-wide setting defaults to 100 unless you change it). This setting limits the number of times a CTE can recursively call itself. If the limit is reached, an exception is thrown. The syntax for setting the MAXRECURSION level is to use the OPTION clause in your SELECT statement that follows the CTE, like so:

-- DEFINE YOUR CTE HERE
SELECT * FROM EmpCTE
OPTION (MAXRECURSION 7)

There are some other rules you should also keep in mind when designing recursive CTEs. A recursive CTE must contain both an anchor member and a recursive member. Both members must have the same number of columns and the columns belonging to both members must have matching datatypes. The recursive member can only refer to the CTE once and the members cannot use the following clauses or keywords:

  • SELECT DISTINCT
  • GROUP BY
  • HAVING
  • TOP
  • LEFT/RIGHT OUTER JOIN

Recursion Excursion

In terms of data and rowsets, recursion is used to resolve a problem when you need to perform the same logic repeatedly against the same set of data, under different terms. For example, say you are asked to find all of the salespeople and who they work for and return the data in hierarchical order. Figure 5 demonstrates a solution using a CTE that uses recursion to gather the list of employees that work for the VP of Sales.

Figure 5 Recursively Gathering Salespeople (Close Figure 5)
;WITH EmpCTE(EmployeeID, EmployeeFirstName,
 EmployeeLastName, MgrID, SalesLevel)
AS
(
  -- Anchor Member
  SELECT EmployeeID, FirstName, LastName, ReportsTo, 0
  FROM Employees
  WHERE EmployeeID = 2 -- Start with the VP of Sales

  UNION ALL

  -- Recursive Member
  SELECT
    e.EmployeeID, e.FirstName, e.LastName, e.ReportsTo, m.SalesLevel+1
  FROM
    Employees AS e
    INNER JOIN EmpCTE m ON e.ReportsTo = m.EmployeeID
)

 -- Using the CTE
SELECT EmployeeID, EmployeeFirstName, EmployeeLastName,
       MgrID, SalesLevel
FROM EmpCTE

Except for a few additional aspects, the recursive CTE shown in Figure 5 looks very much like a standard CTE. Where a standard CTE contains a query that defines a rowset, a recursive CTE defines two query definitions. The first query definition, the anchor member, defines a query that will be executed when the CTE is called. The second query definition, the recursive member, defines a query that returns the same columns and datatypes as the anchor member. The recursive member also retrieves the values that will then be used to call back into the CTE recursively. The results of the queries are pulled together using a UNION statement.

The EmpCTE in Figure 5 shows an anchor member that grabs the employee record for the VP of Sales (EmployeeID = 2). The last column of the anchor member's query returns a value of 0, which represents the 0th level of the hierarchy, which is the top. The recursive member's query grabs the list of employees that report to the previous employee. This is accomplished by joining the Employees table to the EmpCTE.

The same columns are retrieved from the recursive member, but the SalesLevel column is calculated by taking the current employee's supervisor, grabbing the supervisor's SalesLevel, and incrementing it by 1. The expression m.SalesLevel+1 assigns a SalesLevel of 1 to all people who report directly to the VP of Sales (retrieved from our anchor member). Any employees that report to those people then have a SalesLevel of 2. The SalesLevel continues to increment in this way for each subsequent level of the sales organization's hierarchy.

Wrapping Up

CTEs provide a way to make writing T-SQL much more readable when compared to scenarios that use complex derived tables within a query or referencing a view whose definition is external to the T-SQL batch. CTEs also provide a much improved tool to address the struggles involved in using recursive algorithms. Whether you are using non-recursive or recursive CTEs, you'll find CTEs can help you address many common development scenarios and improve readability without sacrificing performance.

Send your questions and comments for John to mmdata@microsoft.com.

John Papa is a Senior .NET Consultant with ASPSOFT (aspsoft.com) and a baseball fanatic who spends most of his summer nights rooting for the Yankees with his family and his faithful dog, Kadi. John, a C# MVP, has authored several books on ADO, XML, and SQL Server. He can often be found speaking at industry conferences, such as VSLive, or blogging at codebetter.com/blogs/john.papa.


Cutting Edge: AJAX application architecture, Part 2

Cutting Edge
AJAX application architecture, Part 2
Dino Esposito

Code download available at: CuttingEdge2007_10.exe (151KB)
Contents
Logging In with AJAX
Flavors of Services
What Do AJAX Services Return?
JSON Versus XML
Security Concerns
Services in ASP.NET AJAX
ASP.NET AJAX Services and SOAP
Invoking AJAX Services
Building the User Interface
What It All Means

W
hen using ASP.NET AJAX Extensions to transition your site to an AJAX experience, there are two main programming models to choose from: partial rendering and script services. In last month's column, I discussed partial rendering from a primarily architectural perspective. Simply put, with partial rendering, you don't need to change the underlying architecture of an ASP.NET application—it's an easy route to implementing some of the best elements of AJAX, such as no-flicker updates to pages on your site. This enhanced behavior is achieved by simply adding a few new server controls (specifically, ScriptManager and UpdatePanel) and having them silently perform a few tricks to transform a traditional postback in an asynchronous request run through the XMLHttpRequest object. This approach is pretty easy as it simply applies AJAX functionality to the existing Web development model.

If you're ready for a full paradigm shift in building AJAX applications, then you should be looking at the script services approach. All in all, the typical AJAX architecture is fairly easy to understand. Figure 1 illustrates a high-level view of how it works. There's a back end made of application-specific services, which are usually just an AJAX script-callable façade on top of the middle tier of the system where the business logic lives and works. Services and the front end exchange data via HTTP using a variety of formats to pass parameters and return values. After receiving and processing data, the front end, which is made of JavaScript code running on the client, faces the nontrivial task of building a graphical UI using HTML and JavaScript. The reliance on JavaScript is a structural constraint of the browser and this will only change once the browser can support more powerful programming capabilities.

Figure 1 Typical AJAX Architecture
Figure 1 Typical AJAX Architecture

Logging In with AJAX

Moving away from the classic ASP.NET model has numerous practical repercussions. Consider the login process and see how it would change in a pure AJAX solution.

Currently with ASP.NET, enabling the login process consists of configuring the login page with the Login control, configuring protected pages with the LoginView control, and setting up the ASP.NET membership provider. Protected pages will use either logged-in or anonymous templates to reflect the result of the authentication process graphically. In ASP.NET 2.0, you can do most of this work without writing any code. For a successful login to take place, though, there is a redirection (HTTP 302) when the user hits a protected page, a postback from the login page to authenticate credentials, and then another redirection back to the originally requested page.

This isn't necessarily the case with AJAX pages. If the user requests a protected page from the address bar, there's not much you can do other than repeating the ASP.NET experience. If, however, you have links in your page that point to protected pages, you can add some script to the onclick event of the link to check whether the user is authenticated. If not, you can then pop up an alert box to warn the user, like this:

function checkFirst()
{
    var loggedIn = Sys.Services.AuthenticationService.get_isLoggedIn();
    if (!loggedIn)
    {
        alert("You must be logged in to follow this link");
        return false;
    }
    return true;
}

As you can see, this approach uses a client framework that, among other things, allows you to check whether the current user is logged in. With ASP.NET AJAX Extensions, you do that through the Sys.Services.AuthenticationService class.

The same service can be used to authenticate a user after she specifies valid credentials. In this case, there is no redirection and no postback. Everything happens in the context of the same page, as the following code snippet demonstrates:

function OnLogin()
{
   Sys.Services.AuthenticationService.login(
      $get("UserName").value,
      $get("Password").value,
      false,
      null,
      null,
      OnLoginCompleted,
      OnLoginFailed);
}

Checking credentials becomes a standard script operation that uses a script service to authenticate. It's up to the developer to update the client page's UI to reflect that the user is logged in once authentication succeeds. Unless the framework you use provides an object model to wrap HTML in controls, you have to take the much longer route of Document Object Model (DOM) scripting. Note that ASP.NET AJAX Extensions does not currently provide an object model for representing chunks of markup as controls.

Flavors of Services

In AJAX, a service indicates a piece of code that is resident on the domain of the application and exposes functionality to client script code. A service used in AJAX requires some designing to create an implementation that shields the real application's back end and middle tier from direct interaction with the end user. Is such a service a WS-* Web service? Can it be a service-oriented architecture (SOA) service?

The ideal service for AJAX applications is primarily concerned with exposing data and resources to Web clients. It is reachable over HTTP and requires that clients use URLs (and optionally HTTP headers) to access data and command operations. Clients interact with the service using HTTP verbs such as GET, POST, PUT, and DELETE. In other words, the URL represents a resource and the HTTP verb describes the action you want to take on the resource. Data exchanged in those interactions is represented in simple formats, such as JSON and plain XML, as well as in syndication formats such as RSS and ATOM.

A service with these characteristics is a Representational State Transfer (REST) service. For more information on the definition of REST, you should read the original paper that describes the vision behind REST (available at ics.uci.edu/~fielding/pubs/dissertation/top.htm).

In the end, services used by AJAX applications tend not to use SOAP to communicate and are not necessarily autonomous services in the SOA sense. Instead, they are bound to the platform and the domain where they're hosted. Based on this, they can hardly be called WS-* Web services or SOA services.

In addition, these services make a point of not having public documentation or a discovery schema—unlike, for example, Web Services Description Language (WSDL) for WS-* Web services. This reduces the number of dependencies on the service and allows for more rapid evolution of the service code. All in all, the paradigm recommended for AJAX services is less ambitious than the paradigm behind Web and SOA services, but it's still effective for the context in which it is intended to be used.

Note that in the remainder of this column, I'll use the expression "AJAX services" to indicate services used to implement the back end of an AJAX application using the script services approach.

What Do AJAX Services Return?

Since AJAX services are exposed exclusively through HTTP, you can use virtually any text format to pack the body of requests and responses. JavaScript Object Notation (JSON) is the most commonly used format, but others, such as plain XML and raw text, can also be used.

JSON is a text-based format designed to move the state of an object across the tiers of an application. A JSON string can easily be evaluated to a JavaScript object through the familiar eval function. The JSON format describes the object, as shown here:

{"ID":"ALFKI", "Company":"Alfred Futterkiste"}

The string indicates an object with two properties, ID and Company, and their respective, text-serialized values. If a property is assigned a non-primitive value, say a custom object, the value is recursively serialized to JSON, like so:

 "ID":"ALFKI",
 "Company":"Alfreds Futterkiste",
 "Location":
      "{"City":"Berlin", "Country":"Germany"}",
}

When processed with the eval function, JSON strings become an associative array—a sort of name/value collection—where each entry has a name and a value. If the JSON string is meant to represent the state of a custom object, say Customer, it's your responsibility to ensure that the definition of the corresponding class is available on the client. In other words, the JavaScript's eval function alone extracts information out of the JSON string to a generic container. If you need such information to be exposed as a custom object, say a Customer object, the task of providing the class definition and loading data into it is entirely up to you or the framework you use. For more information on the syntax and purposes of JSON, have a look at www.json.org.

JSON Versus XML

For years, XML has been touted as the lingua franca of the Web. Now that AJAX is changing the Web as we know it, XML is being pushed to the corner in favor of JSON, as far as data representation is concerned.

JSON is slightly simpler and more appropriate for use with the JavaScript language. While you can argue over which is easier to understand for humans, JSON is certainly easier than XML for a Web browser to process. With JSON, you don't need anything like an XML parser. Everything you need in order to parse the text is built right into the JavaScript language. Because JSON is much less ambitious than XML, it is also less verbose. That's not to say JSON is perfect; the vast quantity of commas and quotes JSON requires makes it a rather quirky format.

With JSON you also gain a key architectural benefit at a relatively low cost. You reason in terms of objects everywhere. On the server, you define your entities and implement them as classes in your favorite managed language. When a service method needs to return an instance of any class, the state of the object is serialized to JSON and travels over the wire. On the client, the JSON string is received and processed and its contents are loaded into an array or a kind of mirror JavaScript object with the same interface as the server class. The interface of the class is inferred from the JSON stream. In this way, both the service and the client page code use the same logical definition of an entity.

From a purely technical standpoint, AJAX services don't strictly require JSON to be implemented as the data representation format. You could achieve the same result using XML, but then you would need an XML parser that can be used from JavaScript. Parsing some simple XML text in JavaScript may not be an issue, but using a full-blown parser is a different story. Performance and functionality-related issues will likely lead to the existence of numerous seemingly similar components that have little in common. And then there's the question of whether the JavaScript XML parser will support things like namespaces, schemas, white spaces, comments, processing instructions, and so on.

As I see it, for the sake of compatibility you would end up with a subset of XML limited to nodes and attributes. At that point, it is merely a matter of choosing between the angle brackets of XML and the curly brackets of JSON.

Security Concerns

AJAX allows for a more dynamic, interactive browsing experience. This, however, increases the surface area for common types of attacks such as cross-site scripting (XSS) and cross-site request forgery (CSRF). These types of attacks are caused by an attacker injecting script code into a Web page, generally via a URL, thereby allowing the attacker to control the Web browser— performing actions such as stealing user names and passwords or executing HTTP requests without the user's knowledge.

An attacker could, for instance, inject malicious script into the client using a dynamically created <script> tag, allowing data to then be imported into the attacker's Web site. In the case of a CSRF attack, the attacker could inject a script into the client, allowing the attacker to execute unauthorized service methods on another Web site by using saved authentication information (such as cookies) on the client.

JSON is a powerful way to pack data and deliver it to the client. However, because JSON is considered a safe subset of the JavaScript language (it excludes assignment and invocation operations), many AJAX applications simply pass JSON strings directly to the JavaScript eval function in order to create JavaScript objects. As a result, a malformed JSON string provides a new means for an attacker to execute unauthorized script on the client.

Most of these attack types rely on exploiting the GET verb on an HTTP request. Fortunately, ASP.NET AJAX Services have the GET verb disabled by default on remote services. Additionally, you can require that a special content type be set in the request: in any other case, an ASP.NET AJAX service will refuse the call. By design, any direct call made from a <script> tag to an ASP.NET AJAX service has the wrong content type and fails.

Services in ASP.NET AJAX

With ASP.NET AJAX Extensions, you can implement script services in two ways—using a special type of ASP.NET Web services and via page methods. In the former case, you just design and build a class linked to an ASMX resource:

<%@ WebService Language="C#"
    CodeBehind="~/App_Code/TimeService.cs"
    Class="IntroAjax.WebServices.TimeService" %>

The class may optionally inherit from the WebService class and must be decorated with the new ScriptService attribute:

[ScriptService]
public class TimeService : System.Web.Services.WebService
{
   ...
}

Each script-callable method is declared public and tagged with the usual WebMethod attribute.

Page methods are simply public, static methods—each marked as WebMethod—defined in the context of a single ASP.NET page. They can only be called from within the host page. Aside from storage differences, a call to a Web service or page method is processed in the same way by the ASP.NET AJAX environment.

You have to understand that AJAX services represent a part of your back end. They're not public Web services in the sense of a WS-* Web service, which are fully documented by a WSDL script and accessed via POST commands carrying SOAP data. AJAX services are really local services, usually defined in the same application that calls them. However, they can also be on a different Web app or even Web site, provided that they live in the same domain.

The ScriptService attribute plays a key role by enabling the ASP.NET AJAX runtime to accept calls to the service. Without the ScriptService attribute, an exception is thrown on the server when you attempt to place calls. Figure 2 shows the message that is returned when an AJAX page links to service not flagged with the attribute. Note that the page shown in the figure is never displayed to any user. You do receive all that markup when you connect to an ASP.NET AJAX page that declares to use such a service. The markup returns an HTTP 500 error code because the internal ASP.NET machinery refuses to process script calls directed at ASP.NET Web services that lack the attribute.

Figure 2 Page Referencing a Non-Scriptable Service
Figure 2 Page Referencing a Non-Scriptable Service(Click the image for a smaller view)
Figure 2 Page Referencing a Non-Scriptable Service
Figure 2 Page Referencing a Non-Scriptable Service (Click the image for a larger view)

By default, AJAX service methods are invoked only using the POST verb and return JSON formatted data. However, by using the optional ScriptMethod attribute on individual service methods, you can change these settings. Figure 3 details the parameters supported by the ScriptMethod attribute. The data returned to the client can be changed to XML and you can even add support for GET requests. But as I mentioned, this apparently innocent change may open up new possibilities for attackers and expose the potential for cross-site calls to the method. The following code snippet shows the definition of a Web service method:

Figure 3 Parameters of the ScriptMethod Attribute (Close Figure 3)

Parameter | Description
ResponseFormat | Specifies whether the response will be serialized as JSON or as XML. The default is JSON, but the XML format can be handy when the return value of the method is XmlDocument.
UseHttpGet | Indicates whether an HTTP GET verb can be used to invoke the Web service method. For security reasons, this is set to false by default.
XmlSerializeString | Indicates whether all return types, including strings, are serialized as XML. The default is false. The value of the property is ignored when the response format is set to JSON.

[WebMethod]
[ScriptMethod]
public DateTime GetTime()
{
   ...
}

If you're not going to change any default settings (which is what I recommend for most cases), then the ScriptMethod attribute can be omitted. The WebMethod attribute is mandatory, though.

ASP.NET AJAX Services and SOAP

Once created, an AJAX Web service is published as an ASMX resource. By default, it's a public URL and can be consumed by AJAX clients, as well as discovered and consumed by SOAP clients and tools. But you can opt to disable SOAP clients and tools altogether. Just enter the following configuration settings to the web.config file of the ASP.NET application that hosts the service:

<webServices>
   <protocols>
      <clear />
   </protocols>
</webServices>

This simple setting disables any protocols defined for ASP.NET 2.0 Web services (in particular, SOAP) and lets the service reply only to JSON requests. Note that with these settings on, you can no longer call the Web service through the browser's address bar for a quick test. Likewise, you can't ask for the WSDL adding the ?wsdl suffix to the URL.

In order to enable ASP.NET AJAX in a Web application, you must include the following settings in the web.config file:

<httpHandlers>
  <remove verb="*" path="*.asmx"/>
  <add verb="*" path="*.asmx" validate="false"
       type="System.Web.Script.ScriptHandlerFactory, System.Web.Extensions" />
</httpHandlers>

The <remove> node drops the default HTTP handler for ASMX resources—the one handling requests via SOAP. The <add> node adds a new HTTP handler that basically checks the content type of each incoming ASMX request and serves it via JSON if the content-type header is set to application/json. Otherwise, the HTTP handler assumes the request is SOAP-based and forwards the request to the standard ASP.NET 2.0 Web service handler. The request will be rejected if the SOAP protocol is disabled.

In the end, and despite appearances, there is no SOAP necessarily involved with an ASP.NET AJAX service. But the support for SOAP clients is guaranteed, unless it is explicitly disabled in the web.config file.

For an ASP.NET AJAX service to work as expected, the incoming request must have the content-type HTTP header set to application/json. This is also an excellent remedy against cross-site attacks conducted through the <script> tag.

Invoking AJAX Services

To invoke an AJAX service, an AJAX client follows the same pattern used to reference Web services in Windows and classic ASP.NET applications. A proxy class provides the same interface locally as the remote service. In ASP.NET AJAX applications, this proxy is a JavaScript class that the runtime generates when the page is downloaded.

The JavaScript proxy class has the same name as the script service and a number of additional properties. It features the same set of methods, although with a slightly extended signature. In general, there's no need for you to snoop into the source code of the proxy class. But if you want to take a look at its structure, try invoking the following URL from the browser's address bar:

http://.../service.asmx/js

The browser will download a JavaScript file that you can save to your local disk for later perusal.

The JavaScript proxy class inherits from a base class named Sys.Net.WebServiceProxy. This provides the basic capabilities for placing JSON calls. The code download for this column provides a proxy class for a Web service with the following interface:

interface ITimeService
{
    DateTime GetTime();
    string GetTimeFormat(string format);
}

The JavaScript proxy class features the properties listed in Figure 4. Each method mirrored has three parameters in addition to its regular set of arguments. They are the callback function to call if the method is successful, the callback function to call if the method fails or times out, and the context object to pass to both callbacks. The three default-related properties shown in Figure 4 allow you to reuse the same function for multiple calls—a unique JavaScript function to handle errors, for instance. Here's some sample code that invokes a remote AJAX service from an ASP.NET AJAX page:

Figure 4 Properties of the JavaScript Proxy Class (Close Figure 4)

Property | Description
Path | Indicates the URL of the underlying Web service.
Timeout | Indicates for how many milliseconds the method is allowed to run before a timeout is called.
defaultSucceededCallback | Indicates the default JavaScript callback function to invoke for a successful call.
defaultFailedCallback | Indicates the default JavaScript callback function, if any, to invoke for a failed or timed-out call.
defaultUserContext | Indicates the default JavaScript object, if any, to be passed to success and failure callbacks.

function getTime()
{
    IntroAjax.WebServices.TimeService.GetTimeFormat(
        "ddd, dd MMMM yyyy [hh:mm:ss]", onMethodComplete);
}

function onMethodComplete(results)
{
    $get("Label1").innerHTML = results;
}

The callbacks invoked at the end of a method call (regardless of the result) have the following prototype:

function method(results, context, methodName)

The context parameter represents the context object specified when the call was made. The methodName parameter is a string set to the name of the service method. Finally, for a callback invoked for a successful call, the results parameter is an object that contains the JavaScript version of the method's return value. For the failure callback, instead, this represents a Sys.Net.WebServiceError object.

Building the User Interface

AJAX is all about the user's experience in the broadest sense—continuous feel, flicker-free updates, interface facilities, mashups, live data, and so on. But you can only utilize the browser and its set of programmability features—primarily, the browser's object model, DOM implementation, support for DHTML extensions, CSS, JavaScript, and plug-ins.

JavaScript is the main tool for building and manipulating the UI. The typical pattern for user interface tasks entails the client using JavaScript to invoke remote services, receiving JSON or perhaps XML data, and then rearranging the page to show changes.

Such a simple model is not necessarily effective when projected to the size and complexity of a real application. Rearranging the page to incorporate fresh data following a remote call poses non-trivial issues as the structure of the UI gets increasingly sophisticated. The point is, where's the threshold at which a sophisticated UI becomes a problem?

There are essentially three user interface features that each realistic application, especially line-of-business applications, depend upon: layout, data binding, and styling. The JavaScript environment has no support for any of them, except for some styling support through CSS. In addition, JavaScript is an interpreted language where, for example, intensive programming often results in memory issues due to subtle browser bugs and poor programming.

Consider a relatively common and simple scenario—paging a grid of data. A grid is ultimately a rather complex table that the browser has to parse and render for each request. It's hard for a user to measure the cost of this rendering operation the first time the page is served since it is incorporated in the overall page download. But once an AJAX postback request is made for a new grid page, the cost of updating the browser's window is immediately evident. The browser receives a JSON string that contains a collection of objects and must turn that collection into a new table. A big HTML string has to be built on the client, composing text in some memory buffer. The same string, if correct, then has to be rendered graphically.

When such intensive operations are performed, you may notice a less than ideal response time. For scenarios like this, above average JavaScript and DHTML skills are required in order to come up with effective solutions.

An alternative approach is to pre-generate some of the markup on the server. In this way, the remote service doesn't just return data but also incorporates markup information. On the server, the markup is built through compiled code, it can be more easily debugged and tested, and you have access to more powerful programming tools for adding accessibility features. On the other hand, more data travels over the wire (but keep in mind that the amount of data is still much less than with regular ASP.NET postbacks).

The bottom line is that more powerful tools are needed on the client in order to make creating realistic user interfaces effective from both the performance and development perspective. Good, thorough libraries of widgets and controls are essential to any developer. But even the best, most optimized libraries can't do much to counter the inherent limitation of an interpreted language, such as JavaScript. Perhaps Silverlight, a Microsoft cross-platform browser plug-in that incorporates a subset of the Windows® Presentation Foundation (WPF) framework, will eventually offer the client-side environment that Web developers will desire for their next generation of Web and AJAX applications. But Silverlight is an external plug-in; it requires a separate download, and it is still maturing. Version 1.0 has just been released, but more sophisticated features are needed in order to use it to build the presentation layer of real-world Web applications.

What It All Means

Partial rendering is the easiest approach to AJAX. It is particularly well suited for adding AJAX capabilities to legacy applications that you don't have the time, budget, or desire to redesign. From an architectural standpoint, partial rendering is a smart extension to today's ASP.NET that preserves the same application model and underlying engine.

A pure AJAX architecture is based on client and server being loosely coupled—essentially two separate worlds connected over the HTTP wire with JSON exchanging messages. In a pure AJAX architecture, you have a service-based back end and a JavaScript-powered front end. The burden of building an effective HTML UI is entirely up to you or the control library you choose. This decoupling, however, will allow for emerging technologies, such as Silverlight, to continue enabling Web developers to create more interactive user interfaces without being constrained by the server platform.

Send your questions and comments for Dinto to cutting@microsoft.com.

Dino Esposito is a mentor at Solid Quality Learning and the author of the upcoming Programming ASP.NET 3.5 Core Reference (Microsoft Press, 2007). Based in Italy, Dino is a frequent speaker at industry events worldwide. You can visit his blog at weblogs.asp.net/despos.


Test Run: Test automation with Windows XP Embedded

Test Run
Test automation with Windows XP Embedded
Dr. James McCaffrey and Mike Hall

Code download available at: TestRun2007_10.exe (1402KB)
Contents
The Application under Test
The Test Automation
Porting UI Test Automation to a Windows XP Embedded System
Creating Components
OS Components
Build Your Image
Deploy Your Image
A Quick Recap

H
ave you ever worked with the Windows® XP Embedded operating system? This is essentially a developer-customized, slimmed-down version of the Windows XP operating system intended for use on PC-like devices—game consoles, information kiosks, network appliances, and the like. With the rapid growth in the use of mobile and embedded devices, this platform is increasingly important.

I've discovered that there is a sort of knowledge gap between software test engineers and developers who work with the Windows XP Embedded-based software systems. To help bridge that gap, in this month's column I'm joined by Mike Hall, a Senior Product Manager in the Microsoft® Mobile and Embedded Devices group and an expert on Windows XP Embedded. Together we will explain how you can create lightweight but powerful UI test automation for software systems that run on Windows XP Embedded.

The best way for us to show you where we are headed is by providing you with a screenshot. Figure 1 shows some lightweight UI test automation in action. But what is not immediately apparent from the screenshot is that the automation is executing on a device that is running Windows XP Embedded.

Figure 1 UI Automation on Windows XP Embedded
Figure 1 UI Automation on Windows XP Embedded(Click the image for a smaller view)
Figure 1 UI Automation on Windows XP Embedded
Figure 1 UI Automation on Windows XP Embedded (Click the image for a larger view)

If you look closely at Figure 1, you'll see that the UI test automation is exercising a simplistic but representative Windows form-based application similar to one you might find on a kiosk device running Windows XP Embedded. The test automation is a console application that:

  • launches the form-based application under test and manipulates the app
  • simulates a search for a product with text "idg" in the product name
  • examines the resulting app state for "111" in the results
  • determines a test scenario result

Behind the scenes, the test automation is manipulating the application under test by using the Microsoft .NET Framework P/Invoke mechanism to call Win32® API functions, such as FindWindow, SendMessage, and GetMenu.

In this month's column, we will briefly discuss the application under test, then look at the test automation, which produced the results shown in Figure 1. Next, we will describe in detail how to use the tools in Windows Embedded Studio to create a Windows XP Embedded system that contains the application and test automation in a relatively simple way. We will also examine a more sophisticated technique that creates the test automation as a custom Windows XP Embedded shell. We will conclude with a brief discussion of how you can adapt and extend the ideas presented here to meet your own needs.

If you are not familiar with Windows XP Embedded, you'll find this column a great introduction to an interesting technology. And if you're not familiar with Win32-based UI automation using a .NET Framework interface, you'll find this column a good introduction to the technique.

The Application under Test

Let's take a look at the key code for the Windows form-based application under test—the heart of a typical Windows XP Embedded software system. All the code for the application and the test automation is included in the code download that accompanies this article. As you can see in Figure 1, the dummy application has basic user controls, including a TextBox control, a ComboBox control, a Button control, and a ListBox control. In a realistic scenario, a Windows XP Embedded search application would likely retrieve search results from a database server or perhaps a Web service. Here the application maintains a local data store in the form of a simple Product class:

public class Product
{
    public string id, name, price;

    public Product(string id, string name, string price)
    {
        this.id = id; this.name = name; this.price = price;
    }
}

The data for Product instances are stored in an ArrayList collection and are supplied when the main Form object loads:

private ArrayList al = new ArrayList();
private void Form1_Load(object sender, System.EventArgs e)
{
    Product p1 = new Product("111", "Widget", "$11.11");
    Product p2 = new Product("222", "Gadget", "$22.22");
    Product p3 = new Product("333", "Thingy", "$33.33");
    al.Add(p1); al.Add(p2); al.Add(p3);
}

Because we are performing UI automation, it doesn't really matter to us where or how the search application retrieves its data—no matter where the result data comes from, it will be reflected in the application's UI, which can be examined to determine a test scenario pass/fail result. All the application logic occurs in the search Button control's click method. The application begins by crudely checking to see if the user has specified a search criterion—by product ID or by product description. If not, the app fires off a MessageBox window with an error message:

if (comboBox1.Text == "" || textBox1.Text == "") {
    MessageBox.Show("You must enter search criteria and term",
                    "Error");
}
listBox1.Items.Clear();

After clearing the ListBox control, which holds the search results, the application retrieves the search criteria/target string and traverses through the ArrayList data store, looking for matches:

string filter = textBox1.Text;
if (comboBox1.Text == "Product ID") {
    foreach (Product p in al) {
        if (p.id.IndexOf(filter) >= 0) {
            listBox1.Items.Add(p.id + " " + p.name + " " + p.price);
        }
    }
}
else if (comboBox1.Text == "Product Name") {
    // search by Name similarly
}

Let us emphasize that we are deliberately not using good coding style or practices in order to keep the code short and understandable, and also to simulate the relatively unrefined nature of an application in the early stages of development. In fact, the sample code has several significant logic flaws you might enjoy hunting for.

If you are new to Windows XP Embedded, you may be asking yourself, "What does this application have to do with Windows XP Embedded? It looks like a perfectly ordinary Windows Forms-based application." Your observation would be correct—and this is an important point. Because Windows XP Embedded is essentially a componentized version of Windows XP, all your development skills transfer directly over. This gives Windows XP Embedded a huge advantage over alternative development platforms for embedded devices. It's not necessary for you to learn an entirely new platform and tool set, you have access to a large support community, you can use the power of the .NET Framework library, and, as this column explains, you can make use of powerful test automation techniques.

The Test Automation

There are several ways to create UI test automation. The technique we use here is to write a C# console application test harness that manipulates the form-based application under test by calling native Win32 API functions using the P/Invoke mechanism. The September 2005 Test Run column, "Low-Level UI Test Automation" (available at msdn.microsoft.com/msdnmag/issues/05/09/testrun), discusses this topic in detail.

We begin the test automation by launching the application under test using the static Start method of the Process class in the System.Diagnostics namespace:

Console.WriteLine("\nLaunching Windows application");
Process p = Process.Start(".\\TheAppToTest.exe");

Notice that the sample code assumes the application under test executable is in the same directory as our test harness executable. As you'll see shortly, this design is especially convenient for test automation on Windows XP Embedded systems. After launching the application under test, we use the Win32 FindWindow function to obtain a handle to the Form object of the application under test as shown in Figure 2.

Figure 2 Obtaining a Handle (Close Figure 2)
Console.WriteLine("\nLooking for Form1");
IntPtr ptrToForm;
bool formFound = false;
int numTries = 0;
while (!formFound && numTries < 100) {
    ++numTries;
    ptrToForm = FindWindow(null, "Form1");
    if (ptrToForm == IntPtr.Zero) {
        Console.WriteLine("Form1 not found yet. . . ");
        Thread.Sleep(100);
    }
    else {
        formFound = true;
        Console.WriteLine("Form1 found with ptr = " +
            ptrToForm.ToString());
    }
}
if (numTries >= 100) throw new Exception("Form was not found");

The heart of the P/Invoke technique is to import the Win32 FindWindow function. We do this by placing a DllImport attribute in the test harness:

[DllImport("user32.dll", EntryPoint = "FindWindow",
           CharSet = CharSet.Auto)]
static extern IntPtr FindWindow(
    string lpClassName, string lpWindowName);

You can loosely interpret this attribute to mean: "Import a Win32 function from the user32.dll library. The Win32 function is named FindWindow (though the system should also check for the same name ending with 'A' or 'W'). And automatically deal with ASCII and Unicode character encoding issues. The C# alias is a static method that returns a .NET IntPtr type, which represents the handle to a window. The C# alias is named FindWindow and accepts two string arguments—the window control class name and the control friendly name."

The code in Figure 2 attempts to find the Form window; if the Form window is not found (typically because the Form object has not yet initialized), the code waits 100 milliseconds and then tries again. If the Form object is not found after 100 attempts, the test automation throws an exception. After the automation harness launches the application under test, the harness manipulates the Form object by resizing and moving the Form. For example:

Console.WriteLine("\nMoving Form1 around");
SetWindowPos(ptrToForm, IntPtr.Zero, 100, 200, 336, 404, 0);

This uses the Win32 SetWindowPos function to position the upper left-hand corner of the Form object at screen coordinates (100,200) with a width of 336 pixels and a height of 404 pixels.

The associated DllImport attribute for our C# alias is:

[DllImport("user32.dll", EntryPoint = "SetWindowPos")]
static extern bool SetWindowPos(IntPtr hWnd, IntPtr hWndInsertAfter,
    int x, int y, int cx, int cy, uint uFlags);

After manipulating the Form object, we obtain handles to the child window controls on the Form. For example, the test harness code used to get a handle to the button1 control is:

Console.WriteLine("Looking for button1");
IntPtr btn = FindWindowEx(ptrToForm, IntPtr.Zero, null, "Search");
if (btn == IntPtr.Zero)
    throw new Exception("Could not find search button");
else
    Console.WriteLine("button1 found with ptr = " + butt.ToString());

This uses the Win32 FindWindowEx function to obtain a handle of a child control with Name attribute "Search".

The code used to get a handle to the TextBox control is a bit trickier:

Console.WriteLine("\nLooking for textBox1");
IntPtr tb = FindWindowByIndex(ptrToForm, 3);
if (tb == IntPtr.Zero)
    throw new Exception("Could not find textBox");
else
    Console.WriteLine("textBox1 found with ptr = " + tb.ToString());

Here we are using an extremely handy program-defined method named FindWindowByIndex.

Although some window controls have Name attributes (such as Form1), many do not. To obtain a handle to a non-named window control you can use FindWindowByIndex, defined as:

static IntPtr FindWindowByIndex(IntPtr hwndParent, int index)
{
    int ct = 0;
    IntPtr result = IntPtr.Zero;
    do {
        result = FindWindowEx(hwndParent, result, null, null);
        if (result != IntPtr.Zero) ++ct;
    } while (ct < index && result != IntPtr.Zero);
    return result;
}

The idea is that even though some window controls do not have Name attributes, all window controls have an implied index number. You can use the Win32 function FindWindowEx and the implied index number of a control to get a handle to the control. The implied index number of a window control is not the same as the tab control order. The implied index number is determined by the order in which the window control is added to a parent window. So, in our example, we specify FindWindowByIndex(ptrToForm, 3) because the application under test code contains:

this.label1 = new System.Windows.Forms.Label();       // index 0
this.label2 = new System.Windows.Forms.Label();       // 1
this.comboBox1 = new System.Windows.Forms.ComboBox(); // 2
this.textBox1 = new System.Windows.Forms.TextBox();   // 3 <-
this.button1 = new System.Windows.Forms.Button();
// etc.

The remaining code in the test harness manipulates the application under test by sending characters to the TextBox control, clicking on the Button control, waiting for an error MessageBox to appear, clicking on its OK button, and so on. The test harness finishes by examining the contents of the ListBox control to determine a pass or fail scenario result.

Porting UI Test Automation to a Windows XP Embedded System

A key concept in Windows XP Embedded systems is the notion of the operating system shell, as opposed to a shell application running on an operating system. Every Windows-based operating system must have exactly one, and only one, primary shell interface. For example, on the standard Windows XP operating system, the Explorer Shell is typically the primary shell, though you can also have several application shells, such as the cmd.exe command shell, the Windows PowerShell® shell, and so on. Since Windows XP Embedded is a customizable, componentized version of Windows XP, you are not limited to using the Explorer Shell as your primary shell—you can choose any of several shells to use as your primary shell and you can even create a custom primary shell.

In the sidebar, "Test Automation as a Custom Shell," we demonstrate how to port UI test automation to a Windows XP Embedded system when you've decided to use a non-custom primary shell. In the next section, we will present a more sophisticated approach for porting test automation when using a custom primary shell.

In documentation terminology, "device" can refer either to the set of equipment on which Windows XP Embedded will be running (such as an information kiosk) or to an individual hardware item (such as a mouse, keyboard, or display adapter). In this example, the target device is a laptop PC. In a more realistic scenario, the target device would probably be something less PC-like—perhaps something with a reduced keyboard or a small video display. But the Windows XP Embedded development principles are exactly the same.

The target device for our example has a single physical hard drive with a C: partition and a D: partition. Our intention is to copy the Windows XP Embedded system onto the D: partition. In order to create a Windows XP Embedded system, you can use the Windows Embedded Studio, which provides a collection of tools and a back-end database of software components. You do not typically install the Windows XP Embedded tools onto the target device; you install them on a development machine (usually running Windows XP), create a system image for your custom Windows XP Embedded OS and application on your development machine, and then deploy the image to the target device.

Creating a Windows XP Embedded image can seem confusing at first, but after a few iterations the process becomes easy to understand. Before we walk you through the details of a specific example, here's a high-level overview of the process. The first step of the image creation process is to analyze the individual hardware devices on your target device using a utility called the Target Analyzer Probe, contained in the Windows XP Embedded toolset. The next step is to create Windows XP Embedded components using a tool called Component Designer (more about this in a minute). Step three is to combine components and build them into a Windows XP Embedded image. The fourth step is to deploy the image to the target device. As you can see, the process is simple in principle.

Now we'll walk you through the details of creating Windows XP Embedded UI test automation. You begin by analyzing the hardware items on the target device using the Target Analyzer Probe (tap.exe; there is also a ta.exe program for use on 16-bit systems). Just copy the tap.exe utility onto the target device. How that copy is performed depends on what I/O devices the target device has available. (Note that the tap.exe utility requires Windows 2000 or Windows XP; alternatively you can use the Windows XP Embedded installation disk, which is bootable for this purpose.)

Once tap.exe is copied onto the target device, you can simply execute it. The result is a file named devices.pmq (often called a "pumpkin file" by insiders), which is stored in the same directory as tap.exe. This file contains a list of all the hardware items found on the target device. And since the file is in XML format, you can read it with any text editor to verify that all the hardware devices were found. Furthermore, you can manually create or edit the file if necessary. After devices.pmq has been created, copy it from the target device to the development machine.

Creating Components

The next few steps involve creating Components using a GUI-based tool called Component Designer. You can think of a Windows XP Embedded component as a package of related software. Note that in this article we use "Component" (uppercase C) when referring to a Windows XP Embedded package and "component" (lowercase) when making a general reference to a collection of items.

Windows Embedded tools work with Components rather than with individual files because the large number of files involved in a Windows XP Embedded image make managing individual files awkward. You need to create two custom Windows XP Embedded Components—one that encapsulates our form-based application and its console-based test automation, and one that encapsulates the appropriate hardware device drivers.

Prepare by creating a C:\Automation directory on the development machine and placing TheAppToTest.exe (the application) and Demo.exe (the automation) in this directory. This is not strictly necessary, but as we will show you shortly, it is a convenient approach when creating a test automation Component.

First we'll step you through making the test automation component, then we'll go through creation of the device driver component. Start by launching the Component Designer tool from the desktop Start menu, then select File | New from the main menu. You can save your configuration (using File | Save) as AutoTestAutomationComponent.sld (this is typically called a slide file) in any convenient directory. However, if you save your .sld configuration files in the same directory as the Component resource files, the entire Component will be portable since all the files are located in the same directory.

In the Component Designer left-hand navigation pane, expand the Windows XP Embedded Client (x86) item. Now create the Repository object for your test automation Component. You can think of a Repository as representing physical storage for the files which make up a Component. Simply right-click on the Repositories item and select Add Repository. In the right-hand data pane, name your Repository AutoTestAutomationRepository and modify the Source Path property to C:\Automation to indicate the location of the automation files on your development machine (as opposed to the final location on the target device). There are a number of other Repository attributes you can set at this point, but to keep things simple we won't get into those right now.

Now go back to the left-hand navigation pane in Component Designer and right-click on Components and select Add Component. At this point, the left-hand pane of Component Designer should look like the screen shown in Figure 3 and the right-hand pane should look like the screen shown in Figure 4. In the Component Properties area in the right-hand pane, you'll see that the Name attribute of the component has been set to AutoTestAutomationComponent.

Figure 3 Component Designer Left-Hand Pane
Figure 3 Component Designer Left-Hand Pane
Figure 4 Component Designer Right-Hand Pane
Figure 4 Component Designer Right-Hand Pane(Click the image for a smaller view)
Figure 4 Component Designer Right-Hand Pane
Figure 4 Component Designer Right-Hand Pane (Click the image for a larger view)

Next, to associate the Repository you just created with the Component, click on the "Repositories ..." button and select the AutoTestAutomationRepository entry from the Select Repository dialog box, and then click OK. You'll notice that most Windows XP Embedded objects, including Repositories, have a revision number that is automatically appended to the object name—this is a big help in keeping your objects organized. Now, in the left-hand pane, add references to the physical files by right-clicking on the Files item and then selecting Add | Multiple Files. In the Add Component File Resources dialog box, navigate to your app and automation files on the development machine (C:\Automation in this case), select TheAppToTest.exe and Demo.exe files using the <Ctrl> key, and click Open.

Now you will add a Component Dependency. Because both the form-based application and the console-based test automation in this example are built upon the .NET Framework 2.0, the final Windows XP Embedded image must include a .NET Framework 2.0 Component. By explicitly specifying this dependency, you can implicitly instruct the Target Designer tool (which, as you recall, combines all the Components into a final, working, Windows XP Embedded image) to include the .NET Framework 2.0 Component. Right-click on the Component or Group Dependency item and then select Add | Component Dependency. (We will explain what a Group Dependency is in the next section of this column.) At this point, Component Designer will connect to a back end database of Components, which was installed as part of the Windows XP Embedded Studio tools.

In the Add Component Dependency dialog, navigate to Software | System | System Services | Other, select the .NET Framework 2.0 Component (as shown in Figure 5), and click OK. Depending on which version of the Windows XP Embedded toolset you are using, you may have to install the .NET Framework 2.0 Component separately. The list of Components is dynamic and growing—Windows XP Embedded has a big support community that includes third-party engineers and companies as well as Microsoft itself.

Figure 5 Add Component Dependency
Figure 5 Add Component Dependency(Click the image for a smaller view)
Figure 5 Add Component Dependency
Figure 5 Add Component Dependency (Click the image for a larger view)

At this point, the test automation Component is complete, so save your .sld configuration and close the Component Designer tool. Now you need to transfer the custom Component into the back-end database via the Component Database Manager tool, which you launch from the Start menu on your desktop. After the tool connects to the back end database, click the Import button on the main Database tab. In the Import SLD dialog box, browse to the .sld file (in this case AutoTestAutomationComponent.sld) and then click Import. The process is very quick and after reviewing the log messages, just click Close and Close. The test automation Component is now available to the Target Designer tool.

Now you need to create the second Component, one that encapsulates all your device drivers and other software required to support the individual hardware items on the target device. This is a very easy process thanks to the devices.pmq file, which lists all the target device hardware. Launch the Component Designer tool again, but this time click File | Import. On the Choose File for Import dialog, navigate to the devices.pmq file and click Open. This causes an Import File dialog box to appear—just click the Start button. The import process takes several minutes because Component Designer is not merely importing the XML data in devices.pmq; it is actually parsing the file, determining which software files are needed to support the hardware devices and creating a Component from that information. In other words, most of the work you would have to do manually when creating a one-off test automation Component is done automatically for the hardware component. You should get an "Import session completed successfully" message and then you can close the Import File dialog.

If you expand the Components item and select the devices item, you can rename the Component to AutoHardwareComponent. Now save your configuration as AutoHardwareComponent.sld and close the Component Designer tool. After that you can use the Component Database Manager tool to import the hardware Component into the back-end database, just as you did for the test automation Component.

OS Components

Now that the test automation and hardware Components have been created, you are ready to combine them with operating system Components to create a Windows XP Embedded image. This is where you use the Target Designer tool.

Launch Target Designer from the Start menu and click File | New. In the resulting New Configuration dialog, name the configuration, AutoTestAutomation for this example, and click OK. The Target Designer UI has three main panes. The left-hand pane lists Components that are available to add to your Windows XP Embedded image. The center pane lists Components that are currently in your image. The right-hand pane displays information about any item that is selected in the left-hand or center pane.

The left-hand pane will automatically read the back-end database and list any Components you have created—in this case AutoHardwareComponent and AutoTestAutomationComponent. Add the hardware Component by right-clicking on AutoHardwareComponent and selecting Add, and then add the AutoTestAutomationComponent in the same way (the order in which you do this doesn't make a difference).

After adding the two custom Components, you need to add core OS Components. While you could examine the thousands of Components available (typically over 10,000), a much easier approach is to use a prebuilt meta-Component. In the left-hand Target Designer pane, expand the Design Templates item to reveal several options. For this example, select the Windows-based Terminal Professional template, then right-click, and select Add. This adds a large number of individual software Components that are commonly used in a PC-like device. There are several templates available, including Retail Point of Sale Terminal, Home Gateway, Network Attached Storage, and so on. The downside to using a Component template is that you are very likely to get Components that you don't actually need. A good approach is to use a template simply as a starting point and then remove any unneeded Components.

In the center pane, select Settings and then in the right-hand pane click Target Device Settings | Show. These entries refer to the target device, not the development machine. So, in this case, you should leave the boot drive as C: but change C: to D: in the Windows folder, Program Files folder, and Documents and Settings folder entries. This is because, as we mentioned earlier, the plan is to copy the Windows XP Embedded image onto the D: partition of the device's single hard drive.

Edit the Boot ARC path entry from multi(0)disk(0)rdisk(0)partition(1) to multi(0)disk(0)rdisk(0)partition(2). The rdisk (physical drives) items are 0-based but partition items are 1-based. And change the boot partition size to 5000 (MB). This is a magic value for any boot partition that is 5GB or larger. If you specify a value of, say, 700MB, then you can potentially create a bootable CD. For this example, just leave the Partition cluster size as 4096 bytes. This is a good time to save the configuration, saving as AutoTestAutomation.slx.

Build Your Image
Test Automation as a Custom Shell

In some cases, developers using Windows XP Embedded want to implement a custom primary shell. For example, imagine the form-based application shown in Figure 1 acting as the entire UI. This approach forces user activity strictly onto the application and generally prevents interaction with such programs as Windows Explorer and Internet Explorer®. In a custom shell scenario, normal test automation techniques don't generally work because you do not launch an OS shell as you would an app.

One test automation solution in a Windows XP Embedded custom shell scenario is to create a test automation Component using the Windows Embedded Studio tools and configure that Component as the primary shell. Here's a quick overview of the process. (For a detailed description of creating custom Windows XP Embedded Shells, check out Mike Hall's article "Creating a Windows XP Embedded Shell" at msdn2.microsoft.com/ms838335.)

To create a custom test automation primary shell, you first create a test automation Component using the Component Designer tool exactly as I've described in this column. After that, when in the Component Designer, you must configure four settings to turn the Component into a special primary shell Component.

  1. Set the Component Prototype property to Software | System | User Interface | Shells | Windows Shells | Shell Prototype Component.
  2. Add an Advanced Property with these settings: Name = cmiShellPath (case sensitive), Format = String, and Value = \Automation\Demo.exe (for example, the path to the test automation).
  3. Set a group membership to Group Memberships | Add Group Membership | Dependencies | Shell.
  4. Set a second group membership to Group Memberships | Add Group Membership | Software | System | User Interface | Shells.

After you have configured these four settings to create your special primary shell Component, the Component will be listed in the Target Designer tool as a UI shell along with the Explorer Shell, the Command Shell, and so on. Then, if you add the custom automation shell Component to the Windows XP Embedded image, you'll find that the result will be an operating system that boots immediately into the test automation, exercising the associated form-based application.

You're almost ready to combine your Components into an image. But before attempting a build, you should check the Component dependencies to determine if you have accidentally left any required Components out of the configuration. This is an important step. An operating system is a complex piece of software and without a tool such as Target Designer, manually determining all the component dependencies would be very difficult.

On the main menu bar, click Configuration | Check Dependencies. A dialog opens and displays progress messages. The dependency check automatically imports any required Components into the configuration. After the dependency check finishes, you can close the dialog box. In most cases, there will be some errors displayed in a task list in the bottom pane of Target Designer. If you right-click on an error, you'll get an Action option that offers recommended fixes. For instance, one of the errors on this example says "Regional and Language Options requires at least one additional enabled component not in the configuration." If you right-click and select Action, you'll get a Resolve Dependency dialog box where you can select English from a list of languages and then click Add. For this sample, you should also add an NT Loader Component, an NTFS Format Component, and an Explorer shell Component to resolve the other errors.

Now you can click Configuration | Build Target Image. When you do this you get a build dialog with the name of your configuration (AutoTestAutomation.slx). You should then click the Build button and Target Designer will warn you that you've made changes to the configuration—because you added four new Components to resolve the errors found by the dependency check—and ask whether you want to rerun the dependency check. Click Yes and a second dependency check runs, but this one is much quicker. After the second dependency check is complete, presumably with no errors, you can close the Dependency Check dialog and the build process will begin.

In Target Designer, selecting Tools | Options | Build lets you configure the default location where Windows XP Embedded images will be stored on your system. You can also specify a location for a particular build in the Build dialog box. It's important to note that if a Windows XP Embedded image already exists, a warning message will alert you that the existing image will be overwritten—this is usually fine.

After the build finishes, don't be surprised if you get a few warnings. You can review these to make sure they are only minor issues (such as a warning that you are using evaluation software) that can be safely ignored.

Deploy Your Image

Now you're ready to deploy your Windows XP Embedded image to the target device. The new image consists of four files and one directory that contains four subdirectories. Three of the files—boot.ini, ntdetect.com, and ntldr—are the key files needed to start a Windows XP-based operating system. The fourth file—weruntime.ini—is essentially a special Windows XP Embedded key that enables Windows XP Embedded.

Copy these four files from the development machine to the boot drive on the target device. Exactly how you copy these files will depend on what types of I/O devices the target device has. In this case, because the target device is a laptop with a regular Windows XP installation on the C: drive, you can simply boot the target device and copy the files using the CD/DVD drive. The main Windows XP Embedded image is located in a directory named DriveD (because the destination on the target device is the D: drive). This directory contains three directories: Documents and Setting, Program Files, and Windows. In addition, there's also an Automation directory, which holds the form-based application (TheAppToTest.exe) and console-based automation (Demo.exe). Copy these four directories to the D: partition on the target device.

Before you attempt to boot up the target device, you'll want to make one small edit to make the device multi-bootable. Simply edit the Windows XP Embedded image's boot.ini file, adding the following line to the [operating systems] section:

multi(0)disk(0)rdisk(0)partition(1)\WINDOWS="Microsoft Windows XP Professional" /fastdetect

This allows you to easily boot your target device into a regular Windows XP session on the C: drive in case something goes wrong with the Windows XP Embedded image on the D: partition. An alternative approach, if your target device has a floppy disk drive, is to create a bootable floppy disk for recovery. Or you can just keep your original Windows XP installation CD handy and use it to boot into Recovery Mode if necessary.

Now comes the moment of truth. Power up your target device and if your Windows XP Embedded image is correct, the target device will boot into the customized system. A special set of programs collectively called First Boot Agent (FBA) will initialize the system on first boot (FBA does not run on subsequent boots).

At this point, you can execute the test automation. Because this example uses an Explorer Shell component, the system has a GUI interface. You can use the Windows-E keyboard combination to launch Windows Explorer, navigate to D:\Automation, and double-click on the file Demo.exe to launch the test automation. The result will resemble the screenshot in Figure 1. Another approach is to include the CMD - Windows Command Processor Component in your Windows XP Embedded image. This will give you a cmd.exe command shell you can use to launch the test automation.

A Quick Recap

Let us recap what we've seen so far and explain the advantages of this technique. Because Windows XP Embedded is essentially a version of the Windows XP operating system, you can create powerful UI test automation for it using standard programming techniques.

One approach to creating UI automation for Windows XP Embedded systems is to create a Component that includes the primary application and its associated test automation contained in a Windows XP Embedded image. Another approach is to create a normal image, without the test automation Component, and then port the automation over to the target device separately.

The test automation Component approach has three significant advantages. First, creating a test automation Component modularizes your test effort, making it easier to maintain and manage. Second, because the back-end Windows XP Embedded Component database can be located on a remote server, a test automation Component can be easily shared by a team of developers and testers. Third, creating a test automation Component allows the Component's possibly complex software dependencies to be automatically checked by the Target Designer tool.

Send your questions and comments to testrun@microsoft.com.

Dr. James McCaffrey works for Volt Information Sciences, Inc., where he manages technical training for software engineers working at Microsoft's Redmond, Washington campus. He has worked on several Microsoft products including Internet Explorer and MSN Search. James is the author of .NET Test Automation Recipes (Apress, 2006). James can be reached at jmccaffrey@volt.com or v-jammc@microsoft.com.

Mike Hall is a Senior Technical Product Manager in the Mobile and Embedded Devices Group at Microsoft. Mike has been working at Microsoft for more than 10 years and currently works with Windows CE, Windows XP Embedded, and Windows Embedded for Point of Service. Mike presents at a number of Microsoft and third-party events and writes a blog discussing embedded technologies.


Foundations: 3D text in WPF

Foundations
3D text in WPF
Charles Petzold

Code download available at: Foundations2007_10.exe (171KB)
Contents
FormattedText and BuildGeometry
Outlines and Meshes
The Text3D Hierarchy
RibbonText and SliverText
The SolidText Breakthrough
Plumping It Up

O
utline font technologies such as TrueType primarily provide us with typographical flexibility and accuracy, but they can also serve as graphical playthings. Programmers can get access to the actual outlines that define each text character and treat them as vector graphics objects. The outlines can be stroked, filled, used for clipping, or subjected to transforms. A popular feature in Microsoft® Word known as WordArt is based on this concept.

It's important to recognize the nature and limitations of these character outlines: they are strictly geometrical and are missing the "hints" that the operating system normally uses to render fonts on the screen. These hints allow the characters to be rasterized intelligently based on the available pixel grid. Consequently, the unhinted character outlines look best in big font sizes or on high-resolution devices. They are usually not adequate for rendering text at normal font sizes on the screen. (However, as printer resolution gets higher and as antialiasing is used more for screen graphics, the value of hinting has decreased.)

Whenever I encounter a new Windows® API, I make a special effort to locate the provision for getting access to these character outlines. In Windows Forms, it's part of the GraphicsPath class. Four overloads of an AddString method lets you add character outlines to a path. Chapter 19 of my books Programming Microsoft Windows with C# (Microsoft Press, 2002) and Programming Microsoft Windows with Microsoft Visual Basic® .NET (Microsoft Press, 2003) show how this is done.

In Windows Presentation Foundation (WPF), the classes and methods that provide access to character outlines are better hidden, but they do exist. The FormattedText and GlyphRun classes from the System.Windows.Media namespace both have methods named BuildGeometry that return a Geometry object for a particular font and text string. In this article I'll use FormattedText exclusively because it's the easier of the two classes. Chapters 28 and 30 of my book Applications = Code + Markup (Microsoft Press, 2006) have some examples of using FormattedText and BuildGeometry with two-dimensional graphics.

When I began working with 3D graphics in WPF, I naturally pondered the possibility of turning these character outlines into blocks of three-dimensional text such as seen in printed media and flying logo effects on television (see the example given in Figure 1). I knew that the job would involve converting a two-dimensional outline into a three-dimensional triangle mesh, but beyond that, I was sure of only one thing: some non-trivial programming was going to be involved.

Figure 1 Solid 3D Text
Figure 1 Solid 3D Text

FormattedText and BuildGeometry

I suspect that most WPF programmers haven't had much contact with the FormattedText class. As the documentation indicates, you use this class for "low-level control for drawing text."

The FormattedText constructors require a TypeFace object, which defines the font family, a style (such as italic), possible boldfacing, and any stretching or compression associated with the font. In addition, the FormattedText constructors require an em size (the font height), a brush for coloring the font characters, and the text string itself.

Once a FormattedText object is created, you can call various methods to set different fonts, styling, or formatting to subsets of the text string. Properties let you set line spacing and other characteristics of the text.

FormattedText objects are used most commonly with the DrawText method of the DrawingContext class. Generally you encounter the DrawingContext class when you override the OnRender method defined by UIElement. This is the lowest level of graphics output your application can do and still be considered a pure WPF application. The DrawText method requires only a FormattedText object and a coordinate point where the text is to begin.

In the context of everything else in FormattedText, the BuildGeometry method seems like an oddity. The method has one argument—an origin of type Point—and returns a Geometry object.

Geometry is an important class in WPF, and it's clearly related to the traditional graphics path. A Geometry object is a collection of straight lines and curves specified as coordinate points. Some of these lines and curves might be connected; some connected lines and curves might be closed to describe enclosed areas. No concept of rendering is included in a Geometry object. In two-dimensional graphics programming, you can render a Geometry object by passing it to the handy Path class, which is part of the high-level Shapes library. An alternative is GeometryDrawing, which is based on a Geometry object, a Brush, and a Pen.

Generally when programming two-dimensional graphics, there's little reason to go digging inside a particular Geometry object. But converting a Geometry object into three-dimensional text is quite a different job. So what exactly is the Geometry object that FormattedText.BuildGeometry returns?

Geometry is an abstract class from which seven other classes derive. My experience is this: the Geometry object returned from FormattedText.BuildGeometry is actually one or more nested GeometryGroup objects containing multiple PathGeometry objects, one for each character in the text string. Each PathGeometry object consists of one or more PathFigure objects defining a closed path. Some characters (such as l, t, or x) require only one PathFigure. Other characters require two. A lowercase i, for example, requires a second PathFigure for the dot. An O requires one PathFigure for the outline of the outside circle and another for the inner circle. An uppercase B requires three PathFigure objects. A percent sign requires five.

Each PathFigure is a collection of objects of type PathSegment, which is another abstract class. My experience reveals that the PathFigure objects that are associated with text outlines contain multiple objects of type LineSegment, PolyLineSegment, BezierSegment, and PolyBezierSegment that contribute to the definition of a single closed path.

WPF 3D has no concept of polylines or Bezier curves, but triangle meshes are based on collections of points, so a first step requires converting a Geometry object from FormattedText.BuildGeometry into a series of enclosed polylines. That would be the easy part. But it soon became obvious to me that coming up with an algorithm to convert those polylines into a triangle mesh was clearly a complex mathematical exercise, and very likely beyond my abilities.

Outlines and Meshes

In the April 2007 issue of this magazine, I discussed the mechanics of generating MeshGeometry3D objects for use with the WPF 3D graphics (see msdn.microsoft.com/msdnmag/issues/07/04/Foundations). At the very least, you need to set the Positions and TriangleIndices properties of a MeshGeometry3D object. The Positions property is a collection of points in 3D space. The TriangleIndices collection describes how to construct triangles from these points. Every three integers in TriangleIndices reference three points in the Positions collection to form a triangle.

I figured that the polylines I generated from the text outlines would form members of the Positions collection of MeshGeometry3D. Figure 2 shows a capital A from a sans-serif font consisting of two enclosed polylines with a total of eleven points. The second image shows how the letter might be divided into seven triangles. For an easy character like this, it's trivial to do it by hand, but describing the process in code wasn't clear to me at all.

Figure 2 Letter Defined by Points and Triangles
Figure 2 Letter Defined by Points and Triangles

Obviously you want to make sure that the sides of each triangle don't stray beyond the confines of the character, and you need to make sure the entire face of the character is accounted for by the triangle collection. And keep in mind that the example I used here is a simple character from an easy sans-serif font. Consider a capital S from a serifed font, and the job becomes truly baffling. A technique known as Delaunay Triangulation exists that might be of help, but the mathematics are rather complex.

Fortunately, all was not lost. While contemplating this problem, I saw some text in an advertisement that took a different approach to 3D text involving only the outlines and leaving the body of each character hollow. This, I realized, was something I knew I could do. First I needed a class name and I came up with RibbonText.

The Text3D Hierarchy

The downloadable code for this article contains a single Visual Studio® solution named Text3D. It consists of a DLL project named Petzold.Text3D and several small demo programs in XAML that use the DLL. Note that the files in the DLL have the namespace Petzold.Text3D.

The class hierarchy in the Petzold.Text3D.dll library begins with ModelVisualBase, an abstract class that derives from the WPF 3D class ModelVisual3D, a technique I discussed in the April 2007 issue of this magazine. This ModelVisualBase class, however, is not exactly the same ModelVisualBase from the previous column because it needed a little more flexibility. But it's important to note that the concept is the same: ModelVisualBase internally stores a GeometryModel3D object and a MeshGeometry3D object, and defines public Material and BackMaterial properties that it transfers to the GeometryModel3D object.

Most of the properties in the Petzold.Text3D classes are backed by dependency properties. The ModelVisualBase class defines two PropertyChanged event handlers (one static, one instance) that descendent classes can use when defining dependency properties. The instance version properly prepares the various properties of the internal MeshGeometry3D object for changes (a process I discussed in my April column), and then calls an abstract method named Triangulate. Descendent classes can override Triangulate to define the various collections of the MeshGeometry3D.

In the Petzold.Text3D library, the abstract Text3DBase class derives from ModelVisualBase. This class defines a bunch of text-related properties named Text, FontFamily, FontStyle, FontWeight, FontStretch, and FontSize, all required by the FormattedText constructor. The class also defines an Origin property that the BuildGeometry method requires. Whenever any of these properties change, the class creates a new FormattedText object and sets an eighth property of Text3DBase named TextGeometry from the Geometry object returned from BuildGeometry:

FormattedText formtxt =
    new FormattedText(Text, CultureInfo.CurrentCulture,
        FlowDirection.LeftToRight,
        new Typeface(FontFamily, FontStyle,
            FontWeight, FontStretch),
            FontSize, Brushes.Transparent);

TextGeometry = formtxt.BuildGeometry(Origin);

This TextGeometry object is available to all descendent classes.

The Text3DBase class cannot create a new TextGeometry object without heap allocations taking place. The class needs to allocate a new FormattedText object, and BuildGeometry undoubtedly makes a lot of its own memory allocations. These heap allocations imply that properties defined by the Text3DBase class should probably not be animated. I've used the IsAnimationProhibited property defined by UIPropertyMetadata to flag those properties that might otherwise be prime candidates for animation.

Throughout the classes I've written that create 3D text, the Origin property defined by Text3DBase is the only property that indicates where the text is positioned in 3D space, and the property is of type Point, which indicates a location in two dimensions. I considered defining an extensive set of properties to precisely position text in 3D space. These properties must include not only a 3D text origin, but also a 3D vector indicating the direction of the baseline, and another 3D vector indicating the upright direction. I instead decided to use the Origin property to position the text on the XY plane in 3D space, and then perform all other positioning with transforms. The big advantage of this approach is that it simplifies the math.

The FontSize property defined by the Text3DBase indicates the em size of the font, which is roughly related to the total height of the font characters. In three dimensions, fonts also have a depth. The DeepTextBase class derives from Text3DBase and exists solely to define a Depth property. (You'll eventually see the reason for this extended class hierarchy; a considerable amount of refactoring took place during the programming of these classes and led to the current structure.) Because the text is positioned on the XY plane, I conceived the Depth property as describing how deep the text extends along the negative Z axis.

So far none of these classes have done any real work. The abstract GeometryTextBase class shown in Figure 3 derives from DeepTextBase and overrides the Triangulate method defined by ModelVisualBase. With the assistance of the GetFlattenedPathGeometry method in the Geometry class, the GeometryTextBase class converts the Geometry object available as the TextGeometry property into multiple connected polylines corresponding to the closed figures that make up the text outlines. For each closed figure, the GeometryTextBase class makes a call to an abstract method, like so:

Figure 3 GeometryTExtBase Class (Close Figure 3)
public abstract class GeometryTextBase : DeepTextBase
{
    // Field prevent re-allocations during mesh generation.
    CircularList<Point> list = new CircularList<Point>();

    protected override void Triangulate(
        DependencyPropertyChangedEventArgs args,
        Point3DCollection vertices, Vector3DCollection normals,
        Int32Collection indices, PointCollection textures)
    {
        // Clear all four collections.
        vertices.Clear();
        normals.Clear();
        indices.Clear();
        textures.Clear();

        // Convert TextGeometry to series of closed polylines.
        PathGeometry path =
            TextGeometry.GetFlattenedPathGeometry(0.001,
            ToleranceType.Relative);

        foreach (PathFigure fig in path.Figures)
        {
            list.Clear();
            list.Add(fig.StartPoint);

            foreach (PathSegment seg in fig.Segments)
            {
                if (seg is LineSegment)
                {
                    LineSegment lineseg = seg as LineSegment;
                    list.Add(lineseg.Point);
                }
                else if (seg is PolyLineSegment)
                {
                    PolyLineSegment polyline = seg as PolyLineSegment;

                    for (int i = 0; i < polyline.Points.Count; i++)
                        list.Add(polyline.Points[i]);
                }
            }

            // Figure is complete. Post-processing follows.
            if (list.Count > 0)
            {
                // Remove last point if it's the same as the first.
                if (list[0] == list[list.Count - 1])
                    list.RemoveAt(list.Count - 1);

                // Convert points to Y increasing up.
                for (int i = 0; i < list.Count; i++)
                {
                    Point pt = list[i];
                    pt.Y = 2 * Origin.Y - pt.Y;
                    list[i] = pt;
                }

                // For each figure, process the points.
                ProcessFigure(list, vertices, normals,
                    indices, textures);
            }
        }
    }

    // Abstract method to convert figure to mesh geometry.
    protected abstract void ProcessFigure(CircularList<Point> list,
        Point3DCollection vertices, Vector3DCollection normals,
        Int32Collection indices, PointCollection textures);
}

protected abstract void ProcessFigure(
    CircularList<Point> list, Point3DCollection vertices,
    Vector3DCollection normals, Int32Collection indices,
    PointCollection textures);

The first argument is a collection of the two-dimensional points in the figure. CircularList is a collection class I defined that functions like a circular buffer. Whenever a member is accessed by an index, the object normalizes the index to the proper range. In other words, an index of -1 accesses the last member of the collection and an index of list.Count accesses the first member of the collection. The collection contains all the points in the closed polyline.

The other arguments to ProcessFigure correspond to the Positions, Normals, TriangleIndices, and TextureCoordinates collections of the MeshGeometry3D object. A class that implements the ProcessFigure method is required to fill at least the vertices and indices collections based on the points in the CircularList collection.

RibbonText and SliverText

The first class I wrote that actually generates three-dimensional text is called RibbonText and is shown in Figure 4. As you can see, the class derives from GeometryTextBase and consists solely of an implementation of the ProcessFigure method. The Point3D objects it generates are based solely on the 2D points in the CircularList collection and the Depth property. The points alternate between those on the XY plane (where Z equals zero) and those Depth units behind the XY plane. The indices collection connects these two sets of points to define a series of triangles.

Figure 4 RibbonText Class (Close Figure 4)
public class RibbonText : GeometryTextBase
{
    protected override void ProcessFigure(CircularList<Point> list,
        Point3DCollection vertices, Vector3DCollection normals,
        Int32Collection indices, PointCollection textures)
    {
        int offset = vertices.Count;

        for (int i = 0; i <= list.Count; i++)
        {
            Point pt = list[i];

            // Set vertices.
            vertices.Add(new Point3D(pt.X, pt.Y, 0));
            vertices.Add(new Point3D(pt.X, pt.Y, -Depth));

            // Set texture coordinates.
            textures.Add(new Point((double)i / list.Count, 0));
            textures.Add(new Point((double)i / list.Count, 1));

            // Set triangle indices.
            if (i < list.Count)
            {
                indices.Add(offset + i * 2 + 0);
                indices.Add(offset + i * 2 + 2);
                indices.Add(offset + i * 2 + 1);

                indices.Add(offset + i * 2 + 1);
                indices.Add(offset + i * 2 + 2);
                indices.Add(offset + i * 2 + 3);
            }
        }
    }
}

Keep in mind that the ProcessFigure method is called multiple times for a particular text string. The Triangulate method in GeometryTextBase is responsible for initially clearing the MeshGeometry3D collections; the ProcessFigure class uses an integer named offset for determining the indices of new points it adds to the vertices collection.

Figure 5 shows a small XAML file that makes use of the RibbonText class, and Figure 6 shows what it looks like. In a sense, it looks somewhat "fancier" than normal 3D block text, perhaps because it's rather unusual. But algorithmically speaking, this is about the simplest form of 3D text conceivable.

Figure 5 RibbonTextDemo.xaml (Close Figure 5)
<!-- RibbonTextDemo.xaml by Charles Petzold, June 2007 -->
<Page xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
      xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
      xmlns:src="clr-namespace:Petzold.Text3D;assembly=Petzold.Text3D"
      WindowTitle="RibbonText Demo"
      Title="RibbonText Demo">

    <Viewport3D>
        <src:RibbonText Text="Ribbon"
                FontFamily="Times New Roman" Depth="2">
            <src:RibbonText.Material>
                <DiffuseMaterial Brush="Cyan" />
            </src:RibbonText.Material>

            <src:RibbonText.BackMaterial>
                <DiffuseMaterial Brush="Pink" />
            </src:RibbonText.BackMaterial>
        </src:RibbonText>

        <!-- Lights. -->
        <ModelVisual3D>
            <ModelVisual3D.Content>
                <Model3DGroup>
                    <AmbientLight Color="#404040" />
                    <DirectionalLight Color="#C0C0C0"
                        Direction="2 -3 -1" />
                </Model3DGroup>
            </ModelVisual3D.Content>
        </ModelVisual3D>

        <!-- Camera. -->
        <Viewport3D.Camera>
            <PerspectiveCamera Position="-3 0 8" UpDirection="0 1 0"
                               LookDirection="1 0 -2" FieldOfView="45" />
        </Viewport3D.Camera>
    </Viewport3D>
</Page>
Figure 6 RibbonTextDemo Display
Figure 6 RibbonTextDemo Display

The characters are actually hollow. If you viewed the text head on, you'd see right through it. Only because it's viewed at an angle can you see that the outside and inside are colored differently. The Material brush (set to Cyan in RibbonTextDemo.xaml) colors the outside of the characters and the BackMaterial brush (set to Pink) colors the inside. For some fonts, however, these colors could be reversed. It depends on the direction of the points defining the character outlines. Conceivably, this direction could even be different for different characters within the same font.

The RibbonText class defines points for the TextureCoordinates collection, so you're not restricted to solid color brushes. The points in the TextureCoordinates collection have Y coordinates of 0 for the foreground part of the ribbon and 1 for the background part, and X coordinates based on the index of the point in the CircularList collection. Any non-solid brush you use with this text will apply to each ribbon separately. The most predictable results occur when you use a LinearGradientBrush with starting and ending coordinates of (0, 0) and (0, 1). Other brushes might reveal a visible seam at unpredictable places in the text characters.

Rather more difficult than RibbonText was a class I called SliverText. This class also focuses solely on the outlines of the text characters, but it gives those outlines a non-zero width that I defined as the SliverWidth property. Figure 7 shows the SliverTextDemo program running with a default FontSize of 1, a default Depth of 1, and a default SliverWidth of 0.05. I defined the TextureCoordinates of SliverText based on the X and Y coordinates of the points, allowing a brush to be varied over the front of the text. The example shows a gradient brush. The tops of the characters appear a little rounded because the coordinates at the edges are shared between the top triangles and the side triangles. WPF 3D calculates normals (which govern the reflection of light) based on the average.

Figure 7 SliverTextDemo Display
Figure 7 SliverTextDemo Display

If you set the SliverWidth to too high a value relative to FontSize, characters will begin to merge into each other. If the text is then animated by a transform, there may be some ugly chatter as surfaces fight for foreground dominance. (The technical term for this effect is "Z fighting.")

The SliverText class involved a little excursion into some two-dimensional analytic geometry. Each character outline is a two-dimensional polyline, but SliverText requires two sets of parallel polylines. I was tempted to use the GetWidenedPathGeometry method defined by Geometry, but my experience with widened paths is that they often produce artifacts I was eager to avoid.

Instead, I widened the path myself. This job requires calculating lines that are parallel to each of the individual lines of the polylines. However, these parallel lines often need to be shortened or lengthened to achieve the same continuity and shape as the underlying path. Helping me out was a little structure named Line2D that I wrote. This structure defines the addition of a Line2D object and a vector as a shift of the line. The multiplication of two Line2D objects returns a Point object indicating the intersection.

The SolidText Breakthrough

Many months passed after I originally wrote RibbonText and SliverText, and I truly feared that was as far as I could go with 3D text. Occasionally I returned to the problem of triangulating the face of the text characters, but I never saw a way to do it without descending into some truly scary mathematics.

Of course, I knew perfectly well how to put a text string on a flat surface in 3D. All you need is a VisualBrush based on a TextBlock element. It certainly occurred to me that I could overlay that flat surface on top of the RibbonText object and create the illusion of solid text. But I knew from experience the problems involved in mixing rasterized text (which is what TextBlock displays) and text constructed from geometrical outlines. The two different algorithms just don't match visually.

The breakthrough came when I realized I could instead cover a flat surface in 3D space with a DrawingBrush based on the same geometry used in RibbonText. The concept was clear; the implementation was not.

The class that generates this DrawingBrush I named PlanarText, which derives from Text3DBase. PlanarText needs the TextGeometry property that Text3DBase generates, but it doesn't need the Depth property defined by DeepTextBase because (as the class name indicates) PlanarText displays text on a plane. However, the PlanarText class does define a property named Z that indicates where the plane of text is located parallel to the XY plane.

PlanarText implements the Triangulate method by simply defining a flat rectangle based on two triangles. The coordinates of the four corners of this rectangle come from the Bounds property associated with the Geometry object obtained from the TextGeometry property.

Where PlanarText is obviously different from the other classes that derive from ModelVisualBase is in its treatment of the Material and BackMaterial properties.

What I find really funny is that when ModelVisualBase was originally conceived, these Material and BackMaterial properties were considered a nuisance more than anything else. ModelVisualBase derives from ModelVisual3D, but ModelVisual3D does not define Material and BackMaterial properties. The WPF 3D class that defines the Material and BackMaterial properties is actually GeometryModel3D, an instance of which ModelVisualBase stores internally as its Content property.

ModelVisualBase needs to define Material and BackMaterial properties so you can set them in derived classes in markup, like so:

<src:RibbonText Text="Ribbon">
    <src:RibbonText.Material>
        <DiffuseMaterial Brush="Cyan" />
    </src:RibbonText.Material>

    <src:RibbonText.BackMaterial>
        <DiffuseMaterial Brush="Pink" />
    </src:RibbonText.BackMaterial>
</src:RibbonText>

Associated with the Material and BackMaterial properties that ModelVisualBase defines is a property-changed handler called MaterialPropertyChanged that simply transfers any objects assigned to these properties to the identical properties of the internal GeometryModel3D object.

But PlanarText needs to do something different. When the Material property of PlanarText is set to a DiffuseMaterial object (for example), PlanarText needs to extract the Brush object associated with that DiffuseMaterial and then create a new DrawingBrush object based on this existing brush and the TextGeometry property:

new DrawingBrush(new GeometryDrawing(brush, null, TextGeometry))

This DrawingBrush becomes the basis of a new DiffuseMaterial object that PlanarText then sets to the Material property of the internal GeometryModel3D object.

This process sounds reasonably easy if the object being assigned to the Material property of PlanarText is a DiffuseMaterial. But the Material property could be assigned a MaterialGroup object, and this MaterialGroup object could have children of type DiffuseMaterial, SpecularMaterial, EmissiveMaterial, or even another nested MaterialGroup. In the general case, the PlanarText class needs to construct a parallel structure of Material objects to assign to its internal GeometryModel3D object, and each DrawingBrush associated with these Material objects needs to be calculated from the Brush object from the Material objects associated with PlanarText.

Simply because of this Material transfer logic, PlanarText.cs turned out to be the longest file in the Text3D library, even though the result doesn't look like much, as Figure 8 demonstrates.

Figure 8 PlanarTextDemo Display
Figure 8 PlanarTextDemo Display

I'm still not entirely happy with the PlanarText class. If the size of the text changes, for example, PlanarText needs to recreate the brushes. The class avoids recreating a bunch of Material objects if the structure of its public Material and BackMaterial properties is the same as the structure of the same properties of the internal GeometryModel3D object. But if one of the brushes associated with these Material objects is animated—perhaps through a ColorAnimation—then PlanarText is forced to recreate GeometryDrawing and DrawingBrush objects on each pass, and that could be costly.

PlanarText is not very important on its own, but it's instrumental in making the SolidText class possible. SolidText, shown in Figure 9, derives from DeepTextBase, which means that it has all the text-related properties defined by Text3DBase as well as the Depth property. But SolidText isn't interested in generating any triangle meshes on its own. It overrides the Triangulate method, but just returns from it.

Figure 9 SolidText Class (Close Figure 9)
public class SolidText : DeepTextBase
{
    public SolidText()
    {
        // Create RibbonText and two PlanarText children.
        RibbonText ribbon = new RibbonText();
        ribbon.Depth = Depth;
        Children.Add(ribbon);

        PlanarText planar = new PlanarText();
        Children.Add(planar);

        planar = new PlanarText();
        planar.Z = -Depth;
        Children.Add(planar);
    }

    // SideMaterial dependency property and property.
    public static readonly DependencyProperty SideMaterialProperty =
        DependencyProperty.Register("SideMaterial",
            typeof(Material), typeof(SolidText),
            new PropertyMetadata(SideMaterialChanged));

    public Material SideMaterial
    {
        set { SetValue(SideMaterialProperty, value); }
        get { return (Material)GetValue(SideMaterialProperty); }
    }

    // SideMaterialChanged handlers.
    static void SideMaterialChanged(DependencyObject obj,
        DependencyPropertyChangedEventArgs args)
    {
        ((SolidText)obj).SideMaterialChanged(args);
    }

    void SideMaterialChanged(DependencyPropertyChangedEventArgs args)
    {
        // Transfer SideMaterial to RibbonText.
        Text3DBase txtbase = Children[0] as Text3DBase;
        txtbase.Material = args.NewValue as Material;
        txtbase.BackMaterial = args.NewValue as Material;
    }

    // MaterialChanged override.
    protected override void MaterialPropertyChanged(
        DependencyPropertyChangedEventArgs args)
    {
        // Transfer Material and BackMaterial properties to PlanarText.
        if (args.Property == MaterialProperty)
            ((PlanarText )Children[1] ).Material =
                                    args.NewValue as Material;

        else if (args.Property == BackMaterialProperty)
            ((PlanarText)Children[2]).BackMaterial =
                                   args.NewValue as Material;
    }

    // TextPropertyChanged override.
    protected override void TextPropertyChanged(
        DependencyPropertyChangedEventArgs args)
    {
        base.TextPropertyChanged(args);

        // Transfer text-related property to all three children.
        for (int i = 0; i < 3; i++)
        {
            Text3DBase txtbase = Children[i] as Text3DBase;
            txtbase.SetValue(args.Property, args.NewValue);
        }
    }

    // PropertyChanged override.
    protected override void PropertyChanged(
        DependencyPropertyChangedEventArgs args)
    {
        if (args.Property == DepthProperty)
        {
            // Set Depth property to RibbonText and PlanarText children.
            double depth = (double)args.NewValue;
            ((DeepTextBase )Children[0]).Depth = depth;
            ((PlanarText)Children[2]).Z = -depth;
        }

        base.PropertyChanged(args);
    }

    // Move on, move on. Nothing to see here.
    protected override void Triangulate(
        DependencyPropertyChangedEventArgs args,
        Point3DCollection vertices, Vector3DCollection normals,
        Int32Collection indices, PointCollection textures)
    {}
}

Instead, SolidText takes advantage of a property it inherits from ModelVisual3D, the Children property. SolidText can have children of type ModelVisual3D and hence of type RibbonText and PlanarText. Any transform applied to SolidText will be applied to all its children. In addition, SolidText defines a SideMaterial property to be applied to the RibbonText child. The primary job of SolidText is distributing the properties set on itself to all its children.

The SolidTextDemo program rotates a SolidText object, which you saw back in Figure 1. To test out the Material-transfer logic in PlanarText, I gave the Figure a gradient brush and specular material that catches the light during its rotation.

Plumping It Up

Once I solved the basic problem of combining the RibbonText and PlanarText figures into one unified block of text, I decided to try to round out the surfaces a bit. The EllipticalText class is similar to SliverText except that each point on the outline of the text character becomes an ellipse rather than a rectangle. The EllipticalText class actually turned out to be a bit shorter than SliverText.

RoundedText derives from SolidText and uses its constructor to replace the RibbonText child that SolidText created with an EllipticalText object. This combination gives the text a somewhat rounded appearance at the edges of the PlanarText object, and also bulks up the middle of the block a bit, as you can clearly see in Figure 10.

Figure 10 Solid 3D Text
Figure 10 Solid 3D Text

The degree of rounding is controlled by a property of both EllipticalText and RoundedText named EllipseWidth, which has a default value of 0.05. Setting this property too large as a fraction of the TextSize property will cause characters to merge with one another and result in Z fighting occuring during animation.

Someday I hope to crack that algorithm that lets me triangulate outline fonts with more flexibility. Meanwhile, these classes will have to suffice. I know that the world is suffering from a dearth of flying logos that incorporate 3D text effects, so I can only hope my modest contribution here will help relieve that dreadful shortage.

Send your questions and comments for Charles to cp@charlespetzold.com.

Charles Petzold is a Contributing Editor to MSDN Magazine. His most recent book is 3D Programming for Windows (Microsoft Press, 2007).


Windows with C++: Task Scheduler 2.0

Windows with C++
Task Scheduler 2.0
Kenny Kerr

Code download available at: WindowsWithC++2007_10.exe (156KB)
Contents
Task Service and Storage
Using the Task Service
Task Definitions
Task Actions
Task Triggers
What's Next?

T
ask Scheduler received a complete overhaul in Windows Vista®. Although there are some similarities, the new Task Scheduler (dubbed Task Scheduler 2.0) is far more powerful than the original, which has been around since Windows® 98. It is no longer just a simple tool for end users, but a powerful platform for designing and managing complex background operations—so much so that it can remove the need for Windows service development in many cases.

Imagine your project needs to check for updates automatically. You might think to write a Windows service that runs in the background and checks for updates every few days. Instead of a service that has to run all the time, you can design a scheduled task that only runs every few days, checks for updates, and then stops. Even better, you can ensure that it runs only when a user is logged in so that resources aren't needlessly consumed when no one is around to perform an update.

It is evident that Microsoft developers consider the new Task Scheduler ready for prime time by the simple fact that it is used by many parts of Windows Vista to manage background tasks. This has the added benefit of reducing the number of new services that would inevitably have been created to handle all those tasks. It also simplifies Windows administration and diagnostics since it is far simpler to interrogate a task to see what it's doing than it is to figure out what a black-box Window service is up to. For tasks that form part of Windows itself, the Task Scheduler also acts as a task host, consolidating many task-specific processes into one and thereby further reducing the resources that are required to host those operations.

In this column I am going to explore the main concepts and building blocks that make up the Task Scheduler so you can get up to speed as quickly as possible and start benefiting from this great new service right away.

Task Service and Storage

The story begins with the Task Scheduler service, the service responsible for the actual scheduling of tasks. Since Task Scheduler uses the file system to store task information, it is possible to enumerate and prepare tasks without the help of the service, but you won't get very far without it. Indeed, future versions of the Task Scheduler may well change the storage format and location, so relying on this is not advised. In fact, it is critical that you not rely on accessing the storage directly as the Task Scheduler may not recognize tasks that are written directly to the file system and will likely refuse to run tasks that have been tampered with. Since Task Scheduler is such an integral part of Windows Vista, it is no longer possible for administrators to simply disable it. This is good news for developers because it means you can safely rely on it to perform your background operations and abstract the task storage.

By convention, tasks are grouped by company, product, and component name. For example, the Windows Disk Defragmenter stores its tasks in the \Microsoft\Windows\Defrag subfolder. Each task is stored as an XML document defined by the Task Scheduler schema. You can then create tasks directly with an XML parser like XmlLite (see my previous MSDN® Magazine article at msdn.microsoft.com/msdnmag/issues/07/04/Xml/), or use the extensive COM interfaces provided by the Task Scheduler API. The COM interfaces also allow you to provide and query the XML definitions for tasks directly. In that way you get the benefit of using XML to author and query tasks while being shielded from their actual storage. Task Scheduler is also accessible remotely.

Using the Task Service

The ITaskService interface is the gateway into the Task Scheduler API. All of the definitions you will need are located within the taskschd.h header file. Of course, you will need the latest Windows SDK that includes support for Windows Vista. Start by creating a local, in-process instance as follows:

CComPtr<ITaskService> service;
HR(service.CoCreateInstance(__uuidof(TaskScheduler)));

(I use the HR macro in these samples to clearly identify where methods return an HRESULT that needs to be checked; you can replace this with appropriate error handling—whether that is throwing an exception or returning the HRESULT yourself.)

Next, call the Connect method to establish a connection to the task scheduler on the computer of your choice. The Connect method is defined as follows:

HRESULT Connect(
    VARIANT computer, VARIANT user,
    VARIANT domain, VARIANT password);

The use of the VARIANT type is unfortunate, but easy enough to deal with using the handy Active Template Library (ATL) CComVariant derived class. To connect to the local computer, simply omit the computer name. To connect using the caller's identity or effective token, don't specify a user name. To use the current domain for the local computer, don't specify a domain name. Finally, only specify a password if you also specified a user name. So, in its simplest form, you might call the Connect method as follows to connect to the local computer's Task Scheduler service:

HR(service->Connect(
    CComVariant(),   // local computer
    CComVariant(),   // current user
    CComVariant(),   // current domain
    CComVariant())); // no password

You can now perform various operations, such as creating tasks and enumerating preexisting folders and tasks. The first step is to get to know the ITaskFolder interface since tasks cannot be used until they have been stored in a folder. ITaskService's GetFolder method returns an ITaskFolder interface pointer for a given folder. A backslash represents the root task folder as illustrated here:

CComPtr<ITaskFolder> folder;
HR(service->GetFolder(CComBSTR(L"\\"), &folder));

You can then create a folder for your application as follows:

CComPtr<ITaskFolder> newFolder;
HR(folder->CreateFolder(
    CComBSTR(L"Company\\Product"),
    CComVariant(), &newFolder));

The optional second parameter to CreateFolder specifies the security descriptor for the newly created file system folder. If omitted, the folder will simply inherit the security descriptor from its parent. You can override the default access control using the security descriptor definition language (SDDL). For example, to allow administrators, as well as the local system, full control, you might use the following SDDL:

HR(folder->CreateFolder(
    CComBSTR(L"Company\\Product"),
    CComVariant(L"D:(A;;FA;;;BA)(A;;FA;;;SY)"),
    &newFolder));

Briefly, D: indicates that the subsequent access control entries (ACE) form part of the discretionary access control list (DACL). The first entry indicates that access is being allowed (A) with file all (FA) being granted to built-in administrators (BA). The second entry indicates the same access is being granted to the local system (SY). Keep in mind that the security descriptor definition is only used in creating the Product folder, while the parent Company folder will still be created with an inherited security descriptor. Also, make sure you don't deny access to the Local System account since that is the identity used by the Task Scheduler service and unexpected behavior is sure to follow when the scheduler cannot access the tasks it is meant to schedule!

Given a preexisting folder, you can use ITaskService's GetFolder method to open a folder relative to the root task folder. Note that ITaskFolder provides the same method for opening folders relative to the folder represented by the interface instance:

CComPtr<ITaskFolder> productFolder;
HR(service->GetFolder(
    CComBSTR(L"Company\\Product"),
    &productFolder));

CComPtr<ITaskFolder> componentFolder;
HR(productFolder->GetFolder(
    CComBSTR(L"Component"),
    &componentFolder));

Figure 1 illustrates the Task Scheduler Explorer sample application included with the download for this column. It provides a handy view of your tasks and is helpful as you start using the task scheduler API.

Figure 1 Task Scheduler Explorer
Figure 1 Task Scheduler Explorer(Click the image for a smaller view)
Figure 1 Task Scheduler Explorer
Figure 1 Task Scheduler Explorer (Click the image for a larger view)

Task Definitions

Before a task can be created, it needs to be modeled by a task definition. Figure 2 describes the components that make up a task definition. Due to the complexity of a task definition and its necessity in creating tasks, I don't recommend jumping right into task creation. It helps to first grasp the fundamental building blocks. Before I dive into the specifics of defining actions and triggers, let's briefly look at how a task definition is composed and created.

Figure 2 Task Definition Components (Close Figure 2)

Task | Definition
Actions | One or more actions define the work the task will perform.
Triggers | One or more triggers indicate when to start the task.
Principal | Authorization and auditing is based on the security context.
Settings | These settings control the runtime behavior and limits of the task.
Data | A string made available to actions.
RegistrationInfo | Administrative bookkeeping information.

Start by asking the Task Scheduler service to create an empty task definition that you can populate:

CComPtr<ITaskDefinition> definition;
HR(service->NewTask(0, // reserved
                    &definition));

Before registering the task definition in a specific folder, you need to populate it with at least one action, and optionally with triggers and other information. Once it's ready you can register it in a folder using the RegisterTaskDefinition method as follows:

CComPtr<IRegisteredTask> registeredTask;
HR(folder->RegisterTaskDefinition(
    CComBSTR(L"Task"),
    definition,
    TASK_CREATE_OR_UPDATE,
    CComVariant(), // user name
    CComVariant(), // password
    TASK_LOGON_INTERACTIVE_TOKEN,
    CComVariant(), // sddl
    &registeredTask));

An IRegisteredTask interface pointer is returned representing the newly registered task. This is the interface used to start or stop tasks as well as to retrieve runtime information about a task.

RegisterTaskDefinition's first parameter specifies the name of the new task. Since this value is also used to name the file saved in the folder, it must comply with the naming conventions of the file system. You can set this parameter to NULL and the method will generate a GUID to use as the name, but this is discouraged since it isn't very meaningful or helpful to administrators of the computer. The second parameter specifies the task definition describing the task to be created. I will dig into that in more detail in the following sections. The third parameter specifies a value from the TASK_CREATION enumeration. The most common values are TASK_ CREATE and TASK_UPDATE, while TASK_CREATE_OR_UPDATE is just a bitwise OR of both.

The next three parameters specify the registration credentials. RegisterTaskDefinition will ensure that the specified user will at least have read access to the registered task even if the DACL you specify in the parameter that follows does not specifically grant it. Task Scheduler supports a number of different logon techniques. The previous example uses TASK_LOGON_INTERACTIVE_TOKEN indicating that the task will only run given an interactive logon session for the specified user. If a user name and password is not provided it will assume the caller's identity. A password is not stored since an interactive logon session is required.

TASK_LOGON_PASSWORD is an alternative that instructs Task Scheduler to create a batch logon session for the task. In this case, both a user name and password must be provided and the account must be granted the "Log on as a batch job" privilege.

TASK_LOGON_S4U is yet another option that provides a more secure alternative. It takes advantage of a service for user (S4U) logon to run the task on behalf of the specified user, but without having to store the password. Since the Task Scheduler runs within the local system account, it can create a S4U logon session and receive a token that can not only be used for identification, but also for impersonation on the local computer. Normally a S4U token is only good for identification.

In addition to the credentials supplied at the time you register a task, the IPrincipal interface offers further control over the security context that will be provided for the task. In particular, IPrincipal provides a convenient way of controlling the execution level for the process hosting the task scheduler engine for your task. Start by querying the task definition for the associated principal object, then set the RunLevel property as needed. This needs to be done before the task definition is registered. Here is an example:

CComPtr<IPrincipal> principal;
HR(definition->get_Principal(&principal));
HR(principal->put_RunLevel(TASK_RUNLEVEL_HIGHEST));

TASK_RUNLEVEL_HIGHEST indicates that the task should be run in the most unrestrictive security context for the particular user. Assuming the user is an administrator, it will provide the process with a token that is not restricted by User Account Control (UAC). The alternative is TASK_RUNLEVEL_LUA, which provides a restricted, or non-elevated, token.

Task Actions
Task Scheduler .NET

Although a Microsoft® .NET Framework wrapper for Task Scheduler is not available, it is not hard to use thanks to a feature of the common language runtime (CLR) known as runtime callable wrappers (RCW).

Since Task Scheduler provides scripting-friendly COM interfaces, it is possible to use the API from managed code with little effort. Simply reference the type library using the Visual Studio® Add Reference dialog. It is a bit misleading since the type library for Task Scheduler 2.0 is named TaskScheduler1.1 Type Library. Nevertheless, Visual Studio will create an interop assembly that provides all of the managed definitions for the COM interfaces so you can construct and reference the various COM objects directly in managed code using RCW.

Here is an example illustrating the C# equivalent of the code samples from the first section of this column, connecting to the Task Scheduler service and creating a folder for your product's tasks:

ITaskService service = new TaskSchedulerClass();
service.Connect(null, // local computer
                null, // current user
                null, // current domain
                null); // no password

ITaskFolder folder = service.GetFolder("\\");
ITaskFolder newFolder = folder.CreateFolder(
    "Company\\Product", "D:(A;;FA;;;BA)(A;;FA;;;SY)");

From here, you can go on to create task definitions, actions, triggers, and much more, all from the comfort of your favorite language that targets the .NET Framework.

With the groundwork out of the way, let's take a look at the variety of action types provided by the task scheduler. Actions are created and added to a task definition using the IActionCollection interface pointer returned by the task definition's Actions property:

CComPtr<ITaskDefinition> definition;
HR(service->NewTask(0, // reserved
                    &definition));

CComPtr<IActionCollection> actions;
HR(definition->get_Actions(&actions));

IActionCollection provides a Create method that creates a new action object and adds it to the collection. The actions themselves are exposed through interfaces deriving from IAction. Here's an example of this:

CComPtr<IAction> action;
HR(actions->Create(TASK_ACTION_EXEC, &action));

TASK_ACTION_EXEC is by far the most common action type as it describes a command-line operation and can be used to launch all kinds of programs. It can even launch documents and other file types registered with the Windows shell. To set the action-specific properties, you need to first query for the type-specific interface and CComQIPtr elegantly takes care of doing just that:

CComQIPtr<IExecAction> execAction(action);

Given an IExecAction interface pointer, you can now configure the action to run the command of your choice. Here's an example that kicks off the Sysinternals Contig tool to defragment my virtual hard drive images:

HR(execAction->put_Path(CComBSTR(L"g:\\Tools\\contig.exe")));
HR(execAction->put_Arguments(CComBSTR(L"-s g:\\VirtualMachines")));

Although running a command is convenient for administrators, it is not always the most appropriate solution for developers since the command doesn't have any awareness of the action it represents within the task or that it is even part of a scheduled task. Fortunately, Task Scheduler provides another action type that is designed specifically to address this issue. The TASK_ACTION_COM_HANDLER action type creates a COM server and queries it for the ITaskHandler interface that you must implement. This establishes a communications channel between the action and the Task Scheduler engine allowing cleaner integration of application-specific operations with Task Scheduler.

Here's how you create a COM action:

CComPtr<IAction> action;
HR(actions->Create(TASK_ACTION_COM_HANDLER, &action));

CComQIPtr<IComHandlerAction> comAction(action);
HR(comAction->put_ClassId(CComBSTR(
    L"{25C6DB11-4ADC-4e89-BA47-04576C7AA46A}")));

You will of course need a COM server that is registered with the specified Class Identifier (CLSID) and that implements the ITaskHandler interface. Figure 3 provides an example of a COM class implementing ITaskHandler with the help of ATL.

Figure 3 COM Action Class (Close Figure 3)
class DECLSPEC_UUID("25C6DB11-4ADC-4e89-BA47-04576C7AA46A")
DECLSPEC_NOVTABLE CoSampleTask :
    public CComObjectRootEx<CComMultiThreadModel>,
    public CComCoClass<CoSampleTask, &__uuidof(CoSampleTask)>,
    public ITaskHandler
{
public:
    DECLARE_REGISTRY_RESOURCEID(IDR_SAMPLETASK)
    BEGIN_COM_MAP(CoSampleTask)
        COM_INTERFACE_ENTRY(ITaskHandler)
    END_COM_MAP()

private:
    STDMETHODIMP Start(IUnknown* taskScheduler, BSTR data);
    STDMETHODIMP Stop(HRESULT* actionResult);
    STDMETHODIMP Pause();
    STDMETHODIMP Resume();
};

There is an additional step you need to perform that, as of this writing, is not documented anywhere but without which your COM action will fail to load. The Task Scheduler engine expects to load your COM server into a separate process using the CLSCTX_LOCAL_SERVER context when it calls the CoCreateInstance function with your CLSID (unless your action is part of Windows itself, in which case it may be loaded in-process). For this to succeed, your COM server needs to be configured to allow activation in a surrogate process. Technically, you could use a traditional out-of-process component, but that is less common and not very practical in most cases. This is easily solved by updating your registration code. Update your ATL registration to include the DllSurrogate value. Here's an example:

HKCR
{
    NoRemove AppID
    {
        '%APPID%' = s 'SampleTask'
        {
            val DllSurrogate = s ''
        }
        'SampleTask.DLL'
        {
            val AppID = s '%APPID%'
        }
    }
}

COM actions are superior in a number of ways to the other action types. Notably, a COM action is the only action type that allows an action to be stopped in a graceful and predictable manner. After the Task Scheduler engine creates an instance of your COM class, it calls the Start method, providing an interface pointer you can use to communicate with the Task Scheduler. The Start method can then query for the ITaskHandlerStatus interface, providing a simple mechanism for the task to notify the task scheduler of its progress and eventual completion. The action can end in two ways. A user may decide to end the task using a variety of methods, all of which result in your COM class's Stop method being called. Alternatively, your COM class may report that it has completed its duties by calling ITaskHandlerStatus's TaskCompleted method.

Another useful action type is provided that allows a task to send e-mail messages. Unlike the previous action types, this one is less useful for performing operations or administrative tasks, but it is ideally suited for use as a notification mechanism. The next section deals with triggers, but for now it is enough to say that tasks can be started by events other than traditional calendar- or time-based triggers. Here's how you create an e-mail action:

CComPtr<IAction> action;
HR(actions->Create(TASK_ACTION_SEND_EMAIL, &action));

CComQIPtr<IEmailAction> emailAction(action);
HR(emailAction->put_From(CComBSTR(L"kenny@example.com")));
HR(emailAction->put_To(CComBSTR(L"karin@example.com")));
HR(emailAction->put_Subject(CComBSTR(L"subject")));
HR(emailAction->put_Body(CComBSTR(L"body")));
HR(emailAction->put_Server(CComBSTR(L"mail.example.com")));

Task Triggers

Task Scheduler provides a variety of triggers that allow you to kick off your tasks without user intervention. There are the usual time- and calendar-based triggers as well as a number of useful event-based triggers.

Tasks are created and added to a task definition using the ITriggerCollection interface pointer returned by the task definition's Triggers property:

CComPtr<ITriggerCollection> triggers;
HR(definition->get_Triggers(&triggers));

ITriggerCollection provides a Create method that creates a new trigger object and adds it to the collection. The triggers themselves are exposed through interfaces deriving from ITrigger. Here's an example of a trigger that might be suitable for the example from the previous section to start a defrag operation:

CComPtr<ITrigger> trigger;
HR(triggers->Create(TASK_TRIGGER_WEEKLY, &trigger));

CComQIPtr<IWeeklyTrigger> weeklyTrigger(trigger);
HR(weeklyTrigger->put_StartBoundary(CComBSTR(
    L"2007-01-01T02:00:00-08:00")));
HR(weeklyTrigger->put_DaysOfWeek(0x01)) // Sunday

TASK_TRIGGER_WEEKLY is one of 11 trigger types that are available in the initial release of the new Task Scheduler. Figure 4 provides a summary of the trigger types that are available to you as well as the associated COM interface for each. The StartBoundary property indicates the earliest date that the task will be triggered as well as the time of day that the task will be started. The DaysOfWeek property specifies the particular days of the week to run the task. It uses a bitmask so that you can combine any days you wish. The trigger in the example above will cause the task to run every Sunday at 2 A.M. PST starting on the first day of 2007.

Figure 4 Trigger Types (Close Figure 4)

Type | Interface | Usage and Options
TASK_TRIGGER_EVENT | IEventTrigger | Events defined by Windows event log.
TASK_TRIGGER_TIME | ITimeTrigger | Time of day; optional random delay.
TASK_TRIGGER_DAILY | IDailyTrigger | Every n days; optional random delay.
TASK_TRIGGER_WEEKLY | IWeeklyTrigger | Specified days of week; every n weeks; optional random delay.
TASK_TRIGGER_MONTHLY | IMonthlyTrigger | Specified days of month; specified months; optional last day of month; optional random delay.
TASK_TRIGGER_MONTHLYDOW | IMonthlyDOWTrigger | Specified days of week; specified weeks of month; specified months of year; optional last week of month; optional random delay.
TASK_TRIGGER_IDLE | IIdleTrigger | When computer is idle.
TASK_TRIGGER_REGISTRATION | IRegistrationTrigger | When task is created or updated; optional delay.
TASK_TRIGGER_BOOT | IBootTrigger | When computer is booted; optional delay.
TASK_TRIGGER_LOGON | ILogonTrigger | When user logs on; optional delay.
TASK_TRIGGER_SESSION_STATE_CHANGE | ISessionStateChangeTrigger | Various session events.

What's Next?

There are many compelling reasons to use the new Task Scheduler in Windows Vista and beyond. If you have relied on Task Scheduler in previous versions of Windows, you will undoubtedly be pleased by all the new features and capabilities.In fact, Task Scheduler may soon replace many custom-built schedulers written for applications today.

I haven't come close to covering all of Task Scheduler's features in this column. Take a moment to explore the documentation in the Windows SDK (msdn2.microsoft.com/en-us/library/aa383614.aspx) and you will discover some additional features, including the ability to author tasks directly in XML, greater control over the security context that tasks are executed in, the ability to enumerate and manage running tasks, and much more!

Send your questions for Kenny to mmwincpp.

Kenny Kerr is a software craftsman specializing in software development for Windows. He has a passion for writing and teaching developers about programming and software design. Reach Kenny at weblogs.asp.net/kennykerr.


Netting C++: Describing the EEK!-osystem

Netting C++
Describing the EEK!-osystem
Stanley B. Lippman

Contents
Hazards and Rewards in the Environment
Laying Out the World
Summing Up

I
n the previous installment of this column, I began building my mouse and mouse environment simulation called EEK! I discussed the two primary methods of parsing the environment XML file: the firehose and Document Object Model (DOM). This month I'll begin by crafting the XML document, then I'll show you another way of incorporating an XML file into the program: using a DataSet, found within the System::Data namespace of the .NET Foundation Class Library. The DataSet leverages the document as a set of relational tables that you can traverse using unique key values.

The first order of business is generating a description of the simulated environment to allow the program to reconstruct and manipulate that world in the course of the application. To do this, I need to determine how best to design the XML document to represent the terrain the mouse will inhabit in the simulation.

The environment I've created (if you're not familiar with it, please read the June 2007 column at msdn.microsoft.com/msdnmag/issues/07/06/NettingC) has a unique constraint. I need to be able to represent it at both macro- and micro-scales and to be able to slide up and down examining the state of each simultaneously—that is, within the Tick of the simulator. For example, at the micro level, I want to track the movement of chemical molecules within the environment (the smell of different entities, such as food or a cat). At the macro level, I need to track the resulting progress and actions of the mouse. A good part of a mouse's behavior is driven by chemical molecules that trigger associated program functions because, unlike humans, it depends on smell, not sight, for exploring its environment. I call this a Scalable Environment Map, or SEM.

Hazards and Rewards in the Environment

The simulated environment itself is just a mapping, although it contains both hazards and rewards. It represents a contiguous area that the mouse moves through, encountering memorable entities such as nesting sites, food, burrs, electrical shocks (e-shocks), scents, and so on (see Figure 1). These encounters between the mouse and the environment literally color the environment.

Figure 1 Neutral World Tile Attributes
Figure 1 Neutral World Tile Attributes(Click the image for a smaller view)
Figure 1 Neutral World Tile Attributes
Figure 1 Neutral World Tile Attributes (Click the image for a larger view)

In the simulation, the experience of the mouse in exploring its environment is "remembered" by maintaining a personal map. In that map, which begins as a blank, a color represents how the mouse experienced that portion of the environment (its interactions with the entities it finds) and allows it to identify and value subsequent areas of the environment by recognizing similar patterns. There are five colors associated with four valuations.

Green and dark blue indicate a rewarding experience—food and drink, a nesting site, and so on. Bright blue denotes fear—some terrifying encounter (in this case represented by simulated electrical shock). Red signifies anger or frustration—some obstruction to the mouse's goal-seeking (embodied in what I call burrs). And orange represents a neutral experience.

One panel of the simulation's display shows the real-time coloring of the environment as it unfolds. Because the environment is deliberate, the resulting maps and ability of the mouse to reach its goals should be predictable based on its configured nature.

In practical terms, this means there is one "truth" map and one subjective map for each moving (sentient) entity in the simulation. The truth map is built from the XML document and represents the physics of the simulated environment. Each subjective map is built up by exploration and colored by personal experience. It is always a subset of the "truth" map. The initial quest driving the mouse is to mark off a personal territory through its subjective map, which contains food and water and a nesting site, and which it can defend. Until I populate the simulation with multiple sentient entities competing for territory, the burrs and e-shocks of the environment will represent hazards and constraints. Figure 1 gives a sense of how a world tile of the environment is populated.

The environment is separated into tiles that are connected by from one to four "doortos" that represent entrances and exits available to the mouse. The simulation begins in an initial chamber that has three doortos representing alternative paths. This chamber is "unpleasant" to a mouse: it is without ground cover, totally exposed with an intense white light. For performance reasons, the simulation only keeps the tile the mouse is currently exploring plus all tiles connected to that tile by a doorto. This becomes the working set (see Figure 2).

Figure 2 World Tiles in Memory
Figure 2 World Tiles in Memory

Laying Out the World

The elements that need to be represented within the XML document consist of the set of titles, the doortos that connect them, and the entities that occur within them:

<element name="tile" ...
<element name="doorto" ...
<element name="burr" ...
<element name="e-shock" ...

The first question is to determine how to relate the elements to each other. Each element of its kind is unique in its attributes, yet echoes aspects of earlier instances the mouse has possibly encountered. (Each time it encounters an element that "reminds" the mouse of an earlier experience, the color of the earlier experience transfers to the new element. This speeds up the mouse's reactions to its environment over time.)

One way to organize the XML is to nest each element description within the tile it occurs in. In Figure 1, this would mean the two burrs, the two scents, the e-shock, the nesting site, and the food and water would all be described within the tile description. This way, by parsing the tile definition, you have a complete description of all the entities within it as well. It also makes the description complicated and the document itself difficult to apprehend by a human reader.

Instead, the document groups each separate entity—first, all the tiles, then doortos, then burrs, and so on. Each entity within the tile is represented as a unique ID, plus a location within the tile. That is, the elements are presented within the document as a set of tables associated by keys.

A second motivation for not defining elements within the tile they occur in is the dual citizenship, so to speak, of doortos. A doorto connects two (and only two) tiles. It does not really belong inside either. It's similar to a design problem that partially motivated the friend mechanism in C++. I create a Matrix class and a Vector class. Now I create a multiplication operator to multiply a Matrix by a Vector. Where do I place it? It doesn't belong in either; however, for performance reasons, I make it a friend to both. That's how I think of doortos; they don't really belong to either of the tiles they connect.

As with most design solutions, this one presents a problem: how to connect a doorto to a tile, or a burr, or scent, or any other entity. I do this by matching uniqueIDs across the two sets of entries. As it happens, this mirrors the representation of a relational database, and I can leverage the database support within the System::Data namespace of the Foundation Class Libraries of the Microsoft® .NET Framework, as I indicated earlier.

A DataSet represents a collection of one or more DataTable instances. In this case, the set of tiles represents the main table. Each environment entity, such as burr or doorto, is stored as an additional DataTable. For each attribute within the tile, I retrieve its uniqueID and cross-reference to the appropriate associated table.

Converting the XML representation into a DataSet is actually quite simple. An XML document and a relational database share a special relationship, in a sense similar to the relationship between water and ice. You can think of them as alternative forms of the exact same data, each suitable for different activities.

A DataSet has a ReadXml method that takes an XML document path name and populates the DataSet object. For example,

DataSet^ ds = gcnew DataSet;
ds->ReadXml( eek_world_xml_path_string );

Although the DataSet object now holds the XML document as a set of DataTables, it does not as yet recognize the relationship between the tables. It needs to have that spelled out. This is done by adding a DataRelation property to the DataSet. The DataRelation defines a relationship between two tables based on a shared column, which represents the element's unique ID, or key.

The Tables property of the DataSet class returns a DataTableCollection object that contains the set of DataTable objects associated with the DataSet. To access a specific instance, you can either index it positionally,

enum class tableIndex {
    tile, doorto, burr, e-shock, ...
};

DataTable^ world_tile = ds->Tables[tile];

or index it associatively using a string representation of the table you want to access:

DataTable^ world_tile = ds->Tables[tile];
world_tile = ds->Tables[ worldTile_table_string ];

There are a number of properties associated with the DataTable, such as the TableName, Rows, Columns, and PrimaryKey:

// returns the name of the table ...
String^ tabName = world_tiles->TableName;
DataRowCollection^    drows = world_tiles->Rows;
DataColumnCollection^ ccols = world_tiles->Columns;
int countRows = drows->Count;
int countCols = ccols->Count;
array< DataColumn^ >^ keys = world_tile->PrimaryKey;

A primary key is a column guaranteed to contain a unique value for each record entry, which also serves as the identity of the record within the table. (A primary key can also be a set of columns. This is why the PrimaryKey property returns an array of DataColumn objects rather than just one.)

In the tile table, for example, the doorto attribute holds the uniqueID of the doorto. In the doorto table, the primary key for organizing the doorto entries is that key.

I identify this relationship by defining a DataRelation class object linking the columns of the two tables that hold key ID value:

DataRelation^ doorto = gcnew DataRelation("UniqueID",
    ds->Tables["worldTile"]->Columns[ doortoID_string ],
    ds->Tables["doorto"]->Columns[ doortoID_key ]);

The first column is referred to as the parent. Its value is used to retrieve the matching entries in the second column, which is referred to as the child. We add the relationship to the DataSet:

ds->Relations->Add(doorto);

In this way, rather than explicitly searching the doorto table for the explicit ID, I instead use the DataRelation object to perform the retrieval.

Summing Up

One of the most productive aspects of .NET is its rich toolset. If I become space-constrained as our environment grows in size, I am best served by the firehose XML support. Otherwise, DOM provides the most data-rich XML representation. In this case, I exploit the relational aspect of the document's layout by reading it into a DataSet. And these solutions work across all .NET-compliant languages. As I've repeatedly said, it's not about languages anymore; it's about libraries. In the next column, I'll begin implementing the mouse.

Send your questions and comments for Stanley to purecpp@microsoft.com.

Stanley B. Lippman is best known for his work on C++ in the 1980s and 1990s with its inventor, Bjarne Stroustrup, at Bell Laboratories, together with his introductory textbook, C++ Primer (Addison-Wesley, 2005), now in its 4th Edition. Stan also worked as Architect with the Visual C++ team at Microsoft in the invention of C++/CLI, which is the focus of this column.


.NET Matters: Deadlock monitor

.NET Matters
Deadlock monitor
Stephen Toub

Code download available at: NETMatters2007_10.exe (156KB)

Q I'm using locks in my application to synchronize work on a bunch of threads. Unfortunately, I'm doing something incorrectly and my threads seem to just stop sometimes. I think I'm running into deadlocks, but I'm not sure how to find them. Is there any way I can do so programmatically? I'd like an exception to be thrown when a deadlock is encountered.

A First, it's important to understand what a deadlock among threads is and the conditions that lead to one. Threads deadlock when waiting on each other to release some resources, but by performing that blocking wait, they're not releasing the resources the other threads need in order to unblock. The threads can't make any progress until the resources are released, but because they're not making progress, the resources will never be released, the threads are locked up, and thus "deadlock." Many OS course textbooks will cite the four conditions necessary for a deadlock to occur:

  • A limited number of a particular resource. In the case of a monitor in C# (what you use when you employ the lock keyword), this limited number is one, since a monitor is a mutual-exclusion lock (meaning only one thread can own a monitor at a time).
  • The ability to hold one resource and request another. In C#, this is akin to locking on one object and then locking on another before releasing the first lock, for example:

lock(a)
{
    lock(b)
    {
        ...
    }
}

  • No preemption capability. In C#, this means that one thread can't force another thread to release a lock.
  • A circular wait condition. This means that there is a cycle of threads, each of which is waiting for the next to release a resource before it can continue.

If any one of these conditions is not met, deadlock is not possible. The first condition is inherent to what a monitor is, so if you're using monitors, this one is set in stone. The second condition could be avoided by ensuring that you only ever lock one object at a time, but that's frequently not a feasible requirement in a large software project. The third condition could possibly be avoided in the Microsoft® .NET Framework by aborting or interrupting the thread holding the resource your thread requires, but a) that would require knowing which thread owned the resource, and b) that's an inherently dangerous operation (for the many reasons why, see msdn.microsoft.com/msdnmag/issues/05/10/Reliability). Thus, the way to avoid deadlocks is to avoid (or thwart) condition four.

In his article in the April 2006 issue (available at msdn.microsoft.com/msdnmag/issues/06/04/Deadlocks), Joe Duffy discusses several techniques for avoiding and detecting deadlocks, including one known as lock leveling. In lock leveling, locks are assigned numerical values, and threads must only acquire locks that have higher numbers than locks they have already acquired. This prevents the possibility of a cycle. It's also frequently difficult to do well in a typical software application today, and a failure to follow lock leveling on every lock acquisition invites deadlock.

Rather than prevent deadlocks wholesale, many systems attempt to detect them and then eliminate them once found. For example, SQL Server® can detect when deadlocks occur and abort one of the tasks involved in the cycle, thereby removing the deadlock. In his article, Joe builds a common language runtime (CLR) host that is capable of this form of deadlock detection in .NET applications that use monitors, a very cool feat. Unfortunately, using a custom CLR host isn't always practical for many .NET apps, including those that already have a custom host, like ASP.NET applications. As such, it would be beneficial to be able to utilize similar deadlock detection capabilities, without the need for a custom CLR host, such that these types of deadlocks could be detected at run time. This would be beneficial during development and testing phases, to identify coding errors where locks are being used incorrectly. It could also be used in production to detect and eliminate deadlocks as they occur (preventing a thread from causing one by blocking it from attempting the critical wait that would complete a cycle), however typical deadlock detection algorithms are costly and may not be appropriate in production systems for performance reasons. (I'll have a few comments on performance at the end of this column.)

To address this need, I've built a sample wrapper for the .NET System.Threading.Monitor class that includes deadlock detection capabilities. As with Monitor, my DdMonitor class provides Enter and Exit methods, and under the covers it delegates to the equivalent methods on Monitor. However, it also tracks monitor usage and throws exceptions when the attempted acquisition of a lock will complete a cycle, which would result in deadlock. For the rest of this column, I'll detail the implementation of this deadlock monitor class and provide additional information on its usage as well as on the advantages and disadvantages of its deployment.

The outline for the DdMonitor class is shown in Figure 1. From the start, note that DdMonitor does not completely mimic the public interface of System.Threading.Monitor. It provides the same public static TryEnter, Enter, and Exit methods, but it does not provide the Wait, Pulse, and PulseAll static public methods of its counterpart.

Figure 1 DdMonitor Class (Close Figure 1)
class DdMonitor
{
    public static IDisposable Lock(object monitor) { ... }

    public static void Enter(object monitor) { ... }

    public static bool TryEnter(object monitor) { ... }
    public static bool TryEnter(
        object monitor, TimeSpan timeout) { ... }
    public static bool TryEnter(
        object monitor, int millisecondsTimeout) { ... }

    public static void Exit(object monitor) { ... }
}

DdMonitor also provides a public static Lock method. Since the C# lock keyword provides a nice abstraction over Monitor, it's beneficial to provide a similar one for DdMonitor. Without the ability to modify the C# language, it's impossible for us to obtain identical syntax, but we can get close:

// with Monitor
lock(obj) { ... }

// with DdMonitor
using(DdMonitor.Lock(obj)) { ... }

This syntactical feat is accomplished by implementing Lock, as shown in Figure 2. The Lock method delegates to DdMonitor.Enter to acquire the lock. However, it also instantiates a DdMonitorCookie object that implements IDisposable. This object's Dispose method will call DdMonitor.Exit to release the lock; this enables the developer to wrap DdMonitor.Lock in a C# using statement (Using in Visual Basic® or stack-allocation in C++/CLI) as shown previously.

Figure 2 Implementing the Lock Method (Close Figure 2)
public static IDisposable Lock(object monitor)
{
    if (monitor == null) throw new ArgumentNullException("monitor");
    IDisposable cookie = new DdMonitorCookie(monitor);
    Enter(monitor);
    return cookie;
}

private class DdMonitorCookie : IDisposable
{
    private object _monitor;

    public DdMonitorCookie(object obj) { _monitor = obj; }

    public void Dispose()
    {
        if (_monitor != null)
        {
            DdMonitor.Exit(_monitor);
            _monitor = null;
        }
    }
}

The Enter method and two of the three TryEnter methods are simple wrappers for the third TryEnter method, as shown in Figure 3. These implementations are meant to follow the same specification as implemented by Monitor's Enter and TryEnter method. Calling Enter will block until the lock is acquired (we differ slightly by design in that our Enter method will throw an exception if a deadlock is detected, rather than blocking forever), and thus delegates to TryEnter with a Timeout.Infinite timeout. Note that Timeout.In- finite equals -1, which is a special value that signals TryEnter to block until lock acquisition, rather than failing out after the specific time. In contrast, the overload of TryEnter that doesn't accept a time value defaults to using a timeout of 0, meaning that it will return false if the lock cannot be acquired immediately (again, our implementation will also throw an exception if acquiring the lock would cause a deadlock; this decision is a debatable point with TryEnter, however, so you may choose to modify the implementation accordingly). Note that TryEnter will return true if the lock was acquired or false otherwise. The second overload of TryEnter simply converts the supplied TimeSpan timeout value into a number of milliseconds, validates the argument, and delegates to the final TryEnter overload, which is where all the real work happens.

Figure 3 Implementing Enter (Close Figure 3)
public static void Enter(object monitor)
{
    TryEnter(monitor, Timeout.Infinite);
}

public static bool TryEnter(object monitor)
{
    return TryEnter(monitor, 0);
}

public static bool TryEnter(object monitor, TimeSpan timeout)
{
    long totalMilliseconds = (long)timeout.TotalMilliseconds;
    if (totalMilliseconds < -1 ||
        totalMilliseconds > Int32.MaxValue)
            throw new ArgumentOutOfRangeException("timeout");
    return TryEnter(monitor, (int)totalMilliseconds);
}

Our design is relatively straightforward, though it does involve a few interesting implementation details. The implementation begins by validating the supplied parameters, ensuring that an object was actually supplied on which to be locked and that a valid timeout was supplied (meaning either -1 or a non-zero number of milliseconds).

At this point, DdMonitor needs to access some shared state. Since there's no supported way for DdMonitor to interrogate the CLR for information about a monitor (including which thread may own it and which threads may be waiting on it), DdMonitor has to track this information manually. It does this by storing a static table of data structures that contain all of the relevant information about acquired monitors in the system, and every time an Enter or Exit operation is performed on a monitor, it updates this shared state.

Note that this has a few implications. First, while we'll see that DdMonitor does end up delegating to Monitor with the same monitor object that was supplied by the user, DdMonitor knows nothing about direct calls to Monitor's methods, and thus it's not able to update its internal state information based on any such calls that are made. This means that deadlock detection will not function properly if you mix usage of DdMonitor and Monitor (or the lock keyword) in your app, causing false negatives and possibly not preventing some deadlocks.

Another implication of this implementation is that this static table is AppDomain-specific. This shouldn't be a problem, since objects you lock on should also only live in one AppDomain. However, there are several special kinds of objects (such as Type and String) that are able to cross AppDomain boundaries, and if you lock on one of these domain-agile objects with DdMonitor from multiple domains, the static table maintained by DdMonitor in each domain will only contain a subset of the relevant information, again possibly leading to false negatives.

A third issue with this approach has to do with reliability. A lock statement in C# expands to a call to Monitor.Enter followed immediately by a try block, whose body is equivalent to the body of the lock statement and whose finally block releases the monitor. The CLR, through a bit of JIT hackery, ensures that the try block is entered if the call to Monitor.Enter succeeds; this ensures that the finally block will also be executed if Monitor.Enter succeeds, which is important in the face of asynchronous exceptions that could otherwise occur between the call to Monitor.Enter and entering the try block (for more information, see msdn.microsoft.com/msdnmag/issues/05/10/Reliability and www.bluebytesoftware.com/blog/2007/01/30/MonitorEnterThreadAbortsAndOrphanedLocks.aspx). As you'll see in our DdMonitor implementation, however, there is code that comes after the actual underlying call to Monitor.Enter and before the try block that comes after the call to DdMonitor.Enter; as such, these reliability guarantees are lost with our implementation.

You should keep all of these issues in mind in case any is dangerous to your scenarios.

Back to our implementation of TryEnter, which is shown in Figure 4; it continues by obtaining its internal lock for this shared state. Once acquired, it accesses the dictionary to find any previous data on the monitor being entered. If no such data exists, that means that no threads currently own or are waiting on the monitor. In such a case, TryEnter initializes a new MonitorState object to track this monitor and puts it back into the table.

Figure 4 Implementing TryEnter (Close Figure 4)
private static Dictionary<object, MonitorState> _monitorStates =
    new Dictionary<object, MonitorState>();

public static bool TryEnter(object monitor, int millisecondsTimeout)
{
    if (monitor == null) throw new ArgumentNullException("monitor");
    if (millisecondsTimeout < 0 &&
        millisecondsTimeout != Timeout.Infinite)
            throw new ArgumentOutOfRangeException("millisecondsTimeout");

    bool thisThreadOwnsMonitor = false;
    MonitorState ms = null;
    try
    {
        lock (_globalLock)
        {
            if (!_monitorStates.TryGetValue(monitor, out ms))
            {
                _monitorStates[monitor] = ms = new MonitorState(monitor);
            }

            if (ms.OwningThread != Thread.CurrentThread)
            {
                ms.WaitingThreads.Add(Thread.CurrentThread);
                ThrowIfDeadlockDetected(ms);
            }
        }

        thisThreadOwnsMonitor = Monitor.TryEnter(
            monitor, millisecondsTimeout);
    }
    finally
    {
        lock (_globalLock)
        {
            if (ms != null)
            {
                ms.WaitingThreads.Remove(Thread.CurrentThread);

                if (thisThreadOwnsMonitor)
                {
                    if (ms.OwningThread != Thread.CurrentThread)
                        ms.OwningThread = Thread.CurrentThread;
                    else ms.ReentranceCount++;
                }
            }
        }
    }

    return thisThreadOwnsMonitor;
}

private class MonitorState
{
    public MonitorState(object monitor) { MonitorObject = monitor; }
    public object MonitorObject;
    public Thread OwningThread;
    public int ReentranceCount;
    public List<Thread> WaitingThreads = new List<Thread>();
}

MonitorState stores several pieces of information about a monitor. First, it stores the monitor itself; the system uses this purely to provide diagnostic information in the event that a deadlock is detected (since it's useful for debugging to know which monitors were involved in a deadlock cycle). MonitorState also stores the Thread object for whichever thread currently owns the monitor (this value is null if it's not currently acquired), a ReentranceCount that indicates the number of times the monitor has been entered (since a thread that owns the monitor can reenter the monitor safely), and a list of waiting threads that indicates what threads are currently trying to acquire this monitor.

With a MonitorState tracking object for this monitor now in hand, TryEnter registers this thread's intent to wait on the object by adding the current Thread to the MonitorState's WaitingThreads list. Once this intent has been registered, TryEnter calls the private ThrowIfDeadlockDetected method, which does exactly what it sounds like (we'll take a look at this method's implementation shortly). If ThrowIfDeadlockDetected detects that this lock acquisition would cause a deadlock cycle, it throws an exception, preventing the lock from being acquired. Note, too, that in doing so, the finally block in which this call is wrapped will remove the current thread from the list of waiting threads.

If no deadlock is detected, it's safe for this thread to attempt to acquire the monitor, and TryEnter simply delegates to Moni- tor.TryEnter to enter the actual monitor. Regardless of whether the lock is acquired, the shared stated lock is then required. Note that I have my own lock leveling scheme here to prevent DdMonitor from causing deadlocks (which would be a really bad thing from a tool meant to prevent them). It's OK for _globalLock to be acquired while holding a lock on a user-supplied monitor, but it's not OK for the reverse to happen. That's why it's OK for me to take the lock on _globalLock in the finally block, where I may potentially already own the user-supplied monitor, but it's not OK to attempt to acquire a lock on the user-supplied monitor while holding _globalLock, which is why I first exit the lock on _globalLock before calling Monitor.TryEnter.

At this point, regardless of whether the user-supplied monitor was successfully acquired, I remove the current thread from the monitor's waiting list (it either owns the monitor or the wait failed, so in either case it's no longer waiting). Then, if the monitor was acquired, the relevant fields are updated in MonitorState.

Exiting the lock is more straightforward, as shown in Figure 5. With the exception of the argument validation, the entire body is wrapped in a lock on the _globalLock monitor. The MonitorState for the user-supplied monitor is retrieved (if it doesn't exist, this monitor was not locked and an exception is thrown), and it's checked to see which thread owns it. If it's unowned or if the owner is not the current thread, the call to Exit was erroneous and an exception is thrown. Otherwise, if the current thread has entered this monitor multiple times, the ReentranceCount is simply reduced, and if not, the OwningThread is set to null to signify the release of this thread's lock on the monitor. Additionally, if there are no threads waiting for this monitor, the MonitorState is removed from the table so that it can be garbage collected (if we failed to do this, the table could grow unbounded over time). Finally, the method delegates to Monitor.Exit to release the actual monitor.

Figure 5 Implementing Exit (Close Figure 5)
public static void Exit(object monitor)
{
    if (monitor == null) throw new ArgumentNullException("monitor");

    lock (_globalLock)
    {
        MonitorState ms;
        if (!_monitorStates.TryGetValue(monitor, out ms))
            throw new SynchronizationLockException();

        if (ms.OwningThread != Thread.CurrentThread)
        {
            throw new SynchronizationLockException();
        }
        else if (ms.ReentranceCount > 0)
        {
            ms.ReentranceCount--;
        }
        else
        {
            ms.OwningThread = null;
            if (ms.WaitingThreads.Count == 0)
                monitorStates.Remove(monitor);
        }

        Monitor.Exit(monitor);
    }
}

Now for the good part. We've seen the whole implementation, except for the actual deadlock detection algorithm, the core of which is implemented in ThrowIfDeadlockDetected (see Figure 6), which we saw called from DdMonitor.Enter earlier.

Figure 6 Detecting Cycles in Wait Chains (Close Figure 6)
private static void ThrowIfDeadlockDetected(MonitorState targetMs)
{
    if (targetMs.OwningThread == null) return;

    Dictionary<Thread, List<MonitorState>> locksHeldByThreads;
    Dictionary<MonitorState, List<Thread>> threadsWaitingOnLocks;
    CreateThreadAndLockTables(
        out locksHeldByThreads, out threadsWaitingOnLocks);

    Queue<CycleComponentNode> threadsToFollow =
        new Queue<CycleComponentNode>(locksHeldByThreads.Count);

    threadsToFollow.Enqueue(new CycleComponentNode(
        Thread.CurrentThread, targetMs, null));

    while (threadsToFollow.Count > 0)
    {
        CycleComponentNode currentChain = threadsToFollow.Dequeue();
        Thread currentThread = currentChain.Thread;

        List<MonitorState> locksHeldByThread;
        if (!locksHeldByThreads.TryGetValue(
            currentThread, out locksHeldByThread)) continue;

        foreach (MonitorState ms in locksHeldByThread)
        {
            List<Thread> nextThreads;
            if (!threadsWaitingOnLocks.TryGetValue(
                ms, out nextThreads)) continue;

            foreach (Thread nextThread in nextThreads)
            {
                if (currentChain.ContainsThread(nextThread))
                    throw new SynchronizationLockException(
                        CreateDeadlockDescription(
                            currentChain, locksHeldByThreads));

                threadsToFollow.Enqueue(new CycleComponentNode(
                    nextThread, ms, currentChain));
            }
        }
    }
}

The ThrowIfDeadlockDetected method accepts as a parameter the MonitorState instance that represents the monitor about to be waited on. For there to be a deadlock, this monitor (which the current thread is about to wait on, and for which we've already registered that intent) needs to be held by a thread that's directly or indirectly holding this monitor and which is waiting on a monitor held by the current thread. By "directly or indirectly holding," I mean that either it acquired a lock on the monitor or that it's waiting on a monitor held by a thread that's directly or indirectly holding this monitor (sorry, I like recursion). In other words, we're looking for a cycle from this monitor, to the thread that owns it, to a monitor that thread is waiting on, to the thread that owns that monitor, and so on, until we come back to the original monitor and thread that owns it. If we can find such a cycle, we throw an exception signaling deadlock.

The implementation follows that approach. First, we check to make sure the target MonitorState is actually owned by a thread; if it's not, there's no problem waiting on it. We then generate lookup tables based on all of the information we currently have about what locks own and are waiting on what monitors (we already have all of this information in the _monitorState table, so we just refactor that information into two Dictionary data structures that will make the rest of the algorithm easier to implement).

At this point, we need to start examining threads. We start with the current thread, which we know to be waiting on the supplied MonitorState. To capture this pairing, I create a simple helper container CycleComponentNode, which, in addition to storing this data, also maintains a reference to the next node in the identified cycle. When we start the algorithm, the only node we know about is the initial thread and MonitorState, so the Next value is null.

Until we have no more threads to be examined, the next thread to be examined (or, rather, the CycleComponentNode storing that thread) is retrieved from the queue. Using the tables we created earlier, we retrieve all of the locks held by this thread; if it doesn't hold any locks, it can't be part of a deadlock (remember the conditions necessary for a deadlock, specifically the one about holding one resource while requesting another). Each of these locks is examined, and again using the tables created earlier, we look up what threads are waiting on these locks. If any of those threads exists in the current wait chain we've built up (represented in list form by the CycleComponentNode), we just found our deadlock! The CreateDeadlockDescription method enumerates all of the CycleComponentNode instances in the chain and generates a description such as the following (which is then thrown in an exception):

Thread 24 waiting on lockP (39C82F0)
    while holding lockH (36BEF47), lockK (3B3D5E3)
Thread 30 waiting on lockH (36BEF47)
    while holding lockB (2CF7029), lockN (349C40A
Thread 29 waiting on lockB (2CF7029)
    while holding lockP (39C82F0)

If the thread doesn't exist in the current wait chain, we still need to examine it. So, we create a CycleComponentNode around it and the MonitorState it's waiting on, and its Next value is set to the current wait chain. That way, when we eventually examine this thread and all of the threads waiting on the monitors it holds, we can search the wait chain properly for those threads.

That's it for the solution. If it doesn't meet all of your needs, you can of course modify it as necessary. For example, when blocking, you could store into the MonitorState the stack trace of the current thread, and then when a deadlock is found, include the stack traces of all relevant threads in the thrown exception's message. Or you could instead augment the solution to support additional synchronization primitives, such as System.Threading.Mutex.

Also, you should note that if you're writing native code and locking on Windows synchronization primitives, you can take advantage of the new Wait Chain Traversal APIs to perform similar and more powerful analysis. For more information regarding this, see John Robbins' Bugslayer column in the July 2007 issue of MSDN® Magazine, available at msdn.microsoft.com/msdnmag/issues/07/07/Bugslayer.

Finally, a few more thoughts on the performance of this implementation. Deadlock detection code as I've implemented here is expensive, plain and simple. As such, you might want to use it in debug builds but not in retail builds. There are a few ways to accomplish this, but one of the simplest is to augment the implementation of DdMonitor with a static property:

private static bool _useDeadlockDetection = false;

public static bool UseDeadlockDetection
{
    get { return _useDeadlockDetection; }
    set { _useDeadlockDetection = value; }
}

With that, you can augment the implementation of Enter, TryEnter, and Exit to check this property and to use it to determine whether to implement the full-blown deadlock detection algorithm or to simply delegate to the corresponding methods on Monitor:

public static void TryEnter(object monitor, int millisecondsTimeout)
{
    if (UseDeadlockDetection)
    {
         ... // existing logic here
    }
    else TryEnter(monitor, millisecondsTimeout);
}

To set UseDeadlockDetection in your code, you could read a value from a configuration file, or if you wanted to set the value based on the build configuration, you could use code like this:

public static void Main(string [] args)
{
    DdMonitor.UseDeadlockDetection =
#if DEBUG
        true;
#else
        false;
#endif

    ... // the rest of your app here
}

Setting UseDeadlockDetection to false and using DdMonitor throughout your code base won't provide identical behavior and performance to just using Monitor, but it should be very close. Just make sure that you don't change the value of UseDeadlockDetection other than at the beginning of your program; if you do change it elsewhere, you may end up using the deadlock detection for some monitor acquisitions and not for others, the dangers of which we already discussed. An alternate approach suggested by Joe Duffy would be to change the implementation of TryEnter to first avoid the deadlock detection code and delegate to Monitor.TryEnter with some configurable timeout, say 500ms (or the user-supplied timeout if it was smaller). If that call succeeds, there's no need to perform deadlock detection as the monitor was successfully acquired. If that call times out and the timeout chosen was less than the user-supplied timeout, then the full-blown deadlock detection algorithm can be run. With this, deadlocks in deployed programs would still be caught, but you wouldn't pay the cost of the detection algorithm until the first Monitor acquisition timed out. And if you pick a reasonable timeout, then it's probably timing out because of a deadlock anyway.

Send your questions and comments for Stephen to netqa@microsoft.com.

Stephen Toub is a Senior Program Manager on the Parallel Computing Platform team at Microsoft. He is also a Contributing Editor for MSDN Magazine.


{ End Bracket }: Matrimony mashup

{ End Bracket }
Matrimony mashup
Michael Richter

Code download available at: WeddingVEAddIn2007_10.exe (338KB)

In my job as Web site manager for MSDN® Magazine and TechNet Magazine, I often have to decide whether to do some mind-numbing manual work that might take several days or try to write an application to do it all for me. Of course, writing that application might take several days in itself, so the time/cost benefit of automation is not always realized. Still, building the application keeps me happy and engaged with my work, whereas repetitive manual tasks can make me hate my job.

I am getting married in October, and I decided to apply my developer skills to automating some of the wedding-planning tasks—which can be equally mind-numbing (but don't tell my fiancée I said that). Luckily for me, she's handling most of the plans, but she did ask me to do two things: create the wedding Web site and manage the guest list.

(Click the image for a smaller view)

(Click the image for a larger view)

Instead of typing in directions and static map links, I created a dynamic page with the Virtual Earth™ API (see msdn.microsoft.com/msdnmag/issues/06/09/EarthlyDelights). I populated two dropdown lists with addresses from an XML file and used one list as a starting route point and the other as the destination route point. Each control has an onchange event that detects if both route points are set and sends the addresses to the GetRoute method of my VEMap object. This updates the map and displays the directions between the points.

This worked fine when I was plotting a route between two addresses, but I also wanted the ability to plot routes between specific longitude and latitude coordinates and between coordinates and addresses. Well, my simple page to automate the maps and directions quickly became complex.

I tried sending coordinates as strings to GetRoute because that is how addresses are sent, but I discovered that coordinates have to be sent as VELatLong objects. I ended up putting a flag in the value for coordinates on the list to clue the JavaScript into creating a new VELatLong for the route point:

<option
   value="821 Stewart Avenue, Garden City, NY">Wingate Hotel</option>
<option value="POSITION,40.729877,-74.038788">Holland Tunnel</option>
<option value="POSITION,40.60294,-74.066305">Verazzano Bridge</option>

My JavaScript code is able to detect if the route point is a set of coordinates by the POSITION flag and send a VELatLong object to GetRoute instead of a string.

I also wanted to see all the guests' addresses on a map. It would be helpful to see which guests would be coming from far away and thus needing a hotel room. It would also be great to see which guests might be able to carpool. And of course, it would be very cool to show the map on our Web site.

I decided to use Virtual Earth pushpins, but I didn't have coordinates for any of the addresses. The VEMap object has a Find method in version 5 of the Virtual Earth control that you can supply with an address and it will return coordinates to a callback function (the name of the callback is passed into the Find method as a parameter). This is great if you need to find one address, but what if you need to find 150? I realized too late that the problem with calling the Find method 150 times is that each call to the callback method overwrites the previous call. So, you cannot use the Find method to get coordinates for many different addresses on one map, at least not in rapid succession.

So I used a geocoding Web service. Microsoft provides the MapPoint® Web service, which offers many features, including one that does exactly what I want (msdn2.microsoft.com/bb545004).

Instead of building this map on a Web page, I chose to build it inside Microsoft® Excel. Inspired by Josh Trupin's Geopegging article (see )msdn.microsoft.com/msdnmag/issues/07/04/EndBracket), I used Visual Studio® Tools for Office 2nd Edition to host a Web-browser control inside an Excel 2007 custom pane. When I select a group of cells, my add-in detects if any addresses are present and, if so, it shows a map of the addresses in the Web browser control. This way, I can add different addresses to Excel or highlight several addresses and see them on a map instantly. You can download the final solution from the MSDN Magazine Web site.

I think most developers will agree that it is fun to automate a job even if performing it manually might be quicker. It's more satisfying to get all the work done by just pushing a button in your custom application. In the case of my wedding, I took some potentially boring tasks and had fun with them. It made me happy, but it made my fiancée happy, too, and that's what's really important.

Michael Richter is the Web Site Manager for MSDN Magazine and TechNet Magazine. He lives in New York City.