Pro .NET Performance: Optimize Your C# Applications by Sasha Goldshtein & Dima Zurbalev & Ido Flatow

Author:Sasha Goldshtein & Dima Zurbalev & Ido Flatow [Goldshtein, Sasha & Zurbalev, Dima & Flatow, Ido]
Language: eng
Format: epub, pdf
Tags: C#, Computers, Programming, Microsoft Programming, Programming Languages
ISBN: 9781430244585
Publisher: Apress
Published: 2012-09-12T04:00:00+00:00

From Threads to Thread Pool to Tasks

In the beginning there were threads. Threads are the most rudimentary means of parallelizing applications and distributing asynchronous work; they are the most low-level abstraction available to user-mode programs. Threads offer little in the way of structure and control, and programming threads directly resembles strongly the long-gone days of unstructured programming, before subroutines and objects and agents have gained in popularity.

Consider the following simple task: you are given a large range of natural numbers, and are required to find all the prime numbers in the range and store them in a collection. This is a purely CPU-bound job, and has the appearance of an easily parallelizable one. First, let’s write a naïve version of the code that runs on a single CPU thread:

//Returns all the prime numbers in the range [start, end)

public static IEnumerable < uint > PrimesInRange(uint start, uint end) {

List < uint > primes = new List < uint > ();

for (uint number = start; number < end; ++number) {

if (IsPrime(number)) {

primes.Add(number);

}

}

return primes;

}

private static bool IsPrime(uint number) {

//This is a very inefficient O(n) algorithm, but it will do for our expository purposes

if (number == 2) return true;

if (number % 2 == 0) return false;

for (uint divisor = 3; divisor < number; divisor += 2) {

if (number % divisor == 0) return false;

}

return true;

}

Is there anything to improve here? Mayhap the algorithm is so quick that there is nothing to gain by trying to optimize it? Well, for a reasonably large range, such as [100, 200000), the code above runs for several seconds on a modern processor, leaving ample room for optimization.

You may have significant reservations about the efficiency of the algorithm (e.g., there is a trivial optimization that makes it run in O(√n) time instead of linear time), but regardless of algorithmic optimality, it seems very likely to yield well to parallelization. After all, discovering whether 4977 is prime is independent of discovering whether 3221 is prime, so an apparently easy way to parallelize the above code is by dividing the range into a number of chunks and creating a separate thread to deal with each chunk (as illustrated in Figure 6-1). Clearly, we will have to synchronize access to the collection of primes to protect it against corruption by multiple threads. A naïve approach is along the following lines:

public static IEnumerable < uint > PrimesInRange(uint start, uint end) {

List < uint > primes = new List < uint > ();

uint range = end - start;

uint numThreads = (uint)Environment.ProcessorCount; //is this a good idea?

uint chunk = range / numThreads; //hopefully, there is no remainder

Thread[] threads = new Thread[numThreads];

for (uint i = 0; i < numThreads; ++i) {

uint chunkStart = start + i*chunk;

uint chunkEnd = chunkStart + chunk;

threads[i] = new Thread(() = > {

for (uint number = chunkStart; number < chunkEnd; ++number) {

if (IsPrime(number)) {

lock(primes) {

primes.Add(number);

}

}

}

});

threads[i].Start();

}

foreach (Thread thread in threads) {

thread.Join();

}

return primes;

}

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.