Quicksort Random Integers with PLINQ

The first “homework assignment” of Dr. Erik Meijer’s functional programming course on Channel 9 was to write quicksort using C# (or VB) functional comprehensions.  I did it in a very naïve way, then I wondered if I could get a “free” speed up simply by leveraging some of the Parallel Extensions to .NET 4.0. 

 

My results were mixed.  As the number of integers in the unsorted array increases, the parallel implementation begins to pull away, but with smaller numbers the sequential implementation is faster.  I think I’ll try to do something very similar in Erlang this weekend.  It should be an interesting comparison exercise since Erlang terms are immutable.  A naïve implementation should look pretty similar I think.  Neither of them would be true quicksort implementations, since the algorithm was specified by Hoare to work in a mutable fashion with the original array being changed in situ.

 

My dual core machine yielded times of about 80s and 100s when sorting an array of a thousand for the parallel (QsortP) and sequential (Qsort) methods respectively.  So that’s definitely not impressive, but I did it in a very abstract way.  The same function could sort strings or floats or anything else that implements IComparable. 

Code Snippet

1. using System;
2. using System.Collections.Generic;
3. using System.Linq;
4. using System.Threading.Tasks;
5. using System.Diagnostics;
6.  
7. namespace ConsoleApplication3
8. {
9.     class Program
10.     {
11.         static void Main(string[] args)
12.         {
13.             int[] ints = new int[100];
14.             var rand = new Random();
15.             for (int i = 0; i < ints.Length; i++)
16.                 ints[i] = rand.Next(0, Int32.MaxValue);
17.             int[] sortedP;
18.             int[] sorted;
19.             Time(() => sortedP = QsortP(ints).ToArray());
20.             Time(() => sorted = Qsort(ints).ToArray());
21.             Debugger.Break();
22.         }
23.  
24.         public static IEnumerable<T> QsortP<T>(IEnumerable<T> arr) where T : IComparable
25.         {
26.             if (arr.Count() == 0)
27.                 return arr;
28.             T pivot = arr.First();
29.             var sortLess = new Task<IEnumerable<T>>(() => QsortP(arr.Where(v => v.CompareTo(pivot) < 0)));
30.             var sortMore = new Task<IEnumerable<T>>(() => QsortP(arr.Where(v => v.CompareTo(pivot) > 0)));
31.             sortLess.Start(); sortMore.Start();
32.             var equal = arr.AsParallel().Where(v => v.CompareTo(pivot) == 0);
33.             return sortLess.Result.Concat(equal).Concat(sortMore.Result);
34.         }
35.  
36.         public static IEnumerable<T> Qsort<T>(IEnumerable<T> arr) where T : IComparable
37.         {
38.             if (arr.Count() == 0)
39.                 return arr;
40.             T pivot = arr.First();
41.             return Qsort(arr.Where(v => v.CompareTo(pivot) < 0))
42.                 .Concat(arr.Where(v => v.CompareTo(pivot) == 0))
43.                 .Concat(Qsort(arr.Where(v => v.CompareTo(pivot) > 0)));
44.         }
45.  
46.         public static void Time(Action a)
47.         {
48.             var t = new Stopwatch();
49.             t.Start();
50.             a();
51.             t.Stop();
52.             Debug.Write(t.Elapsed.TotalSeconds);
53.         }
54.     }
55. }

Premature Optimization and LINQ to SQL

Don’t count your chickens before they hatch.  Let’s call that adage the “count-no” principle.  I promise that will be funny later.

The common interpretation of this adage is that you should not rely on future results when making decisions in the present.  It is generally an admonishment to not be too cocky about the future.  What might the corollary be?  Perhaps to concern ourselves with the details of the present moment rather than thinking about the future.  We’ll call this corollary “nocount”.  One specific example of this corollary is the programmer’s maxim about premature optimization.  In fact, it was Donald Knuth who said, “"We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil,” in a response to Dijkstra’s “Go to statement considered harmful”.

So, I’m debugging a particularly pernicious problem today.  In production (and only production) we were getting a ChangeConflictException when updating a row in the database.  Unfortunately, the logs indicated that there were no MemberChangeConflict objects.  In other words we weren’t violating optimistic concurrency.  So, I profiled the SQL statements and it appeared to be just what I expected, a simple update supporting optimistic concurrency.

Did you know you can eek out an exceedingly miniscule amount of performance by using the “SET NOCOUNT ON” option with SQL Server?  Did you know that you can actually set this option at the server level? Do you know what happens when your LINQ to SQL DataContext uses the row count returned from your optimistically concurrent update statement to determine if one and only one row was updated?

Yes dear reader, premature optimization can cause the most insidious and difficult to discover problems.  Please, don’t ever violate the “nocount princple”!

Website Performance Talk

This is a really enlightening talk from Steve Souders, author of High Performance Websites, and Chief Performance Yahoo!.  Below is a summary of his talk, but they also have a page detailing their rules.

1. Make fewer HTTP requests: combing CSS and Javascript files, CSS sprites*, use image maps instead of multiple images where possible, inline images*
2. Use a Content Distribution Network.  Akamai, Panther Express, Limelight, Mirror Image, SAVVIS.  Distribute your static content before creating a distributed architecture for your dynamic content.
3. Add an Expires header.  If you aren't already, you should be changing the URL of your resources when you version them, to ensure that all users will get updates and fixes.  Since you then won't be updating a given resource, you should give it a far future expires header.
4. Gzip all content: html, css, and javascript.
5. Put stylesheets at the top.  IE will not begin rendering until all CSS files are downloaded.  Use the link HTML tag to pull in stylesheets, not the @import CSS directive, as IE will defer the download of the stylesheet.
6. Put javascripts at the bottom.  HTTP 1.1 allows for two parallel server connections per hostname, but all downloads are blocked until the script is downloaded.  The defer attribute of the script block is not supported in Firefox and doesn't really defer in IE.
7. Avoid CSS expressions.  The speaker doesn't cover this, but I gather from my own experience that this can seriously delay rendering as the expression will not be evaluated until the page is fully loaded.
8. Make CSS and JS external.  This rule can be bent in situations where page views are low and users don't revisit often.  In this situation in-lining is suggested.
9. Reduce DNS lookups.  He didn't cover this either, but it follows from rule #1 that additional network requests negatively impact performance.  He does mention later in the talk that splitting your requests across domains can drastically increase response time.  This is a consequence of the two connections per domain limit in the HTTP 1.1 specification.  It is important to remember that JavaScripts from one domain cannot affect JavaScripts or pages from another domain, due to browser security restrictions.  Also, this is a case of diminishing returns, as beyond four domains causes negative returns from, presumably DNS lookups and resource contention in the browser itself.
10. "Minify" Javascript.  JSMin written by Doug Crockford is the most popular tool.  This is just removing whitespace, generally.  YUI compressor may be preferred and also does CSS.
11. Avoid redirects.
12. Remove duplicate scripts.
13. Configure ETags.  These are used to uniquely identify a resource in space and time, such that if the ETag header received is identical to the cached result from a previous request for that resource, the browser can choose to use the local cache without need to download the remainder of the response stream.  The speaker doesn't go into this subject, so questions about how this improves caching performance over caching headers remain unanswered until you read his book.
14. Make AJAX cacheable.  If you embed a last modified token into the URL of your AJAX request, you can cause the browser to pull from cache when possible.

A great tool to analyze your site's conformance to these rules is YSlow.  It's an add-on for Firebug.  During development your YSlow grade can give you a very good indication of what is happening to the response time of your application.  This metric, the YSlow grade, seems to me to be a much better quality gate for iterative development than does something as variable and volatile measured response time.

Some additional rules from the next version of the book:

• As mentioned in my commentary in rule #9, split dominant content domains.
• Reduce cookie weight.
• Make static content cookie free.
• Minify CSS (see rule #10 comments above).
• Use iframes wisely.  The are a very expensive DOM operation.  Think about it--it's an entirely new page, but linked to another.
• Optimize images.  Should your GIFs be PNGs?  Should your PNGs be JPGs?  Can you shrink your color palette?