Jim's Random Notes

Michael Abrash famously said, “The best optimizer is between your ears.” His point is that no amount of machine-specific optimization is going to make a difference in the running time of a bad algorithm. A poorly written Quicksort, for example, will outperform the most highly optimized Bubble sort. Selecting the right algorithm can give you orders of magnitude (or even more!) improvements in performance. Hand optimizing code usually provides small percentage improvements after an efficient algorithm is selected.

In most of what I do, performance is important, but not super-critical. That is, performance is usually “good enough” if I select an efficient algorithm. As such, I don’t worry too much about micro-level optimizations. In this environment, the .NET Framework and the C# language are very nice. I’m incredibly productive with C#. The language and the runtime library give me many tools with which to quickly and (reasonably) efficiently implement my algorithms. I know that I’m paying a performance penalty. C# applications that do a lot of processing are typically around 10% less efficient than programs compiled to native machine code. But that’s okay. Very little of what I do is so performance sensitive that I’m willing to forego the productivity of .NET for the efficiency of native code.

But when performance is critical, I get very annoyed because the C# way of doing things is often very sub-optimal.

I’ve recently been working on a system that finds similar videos based on Web links. That is, if I like a particular video that Alice linked to on her blog, then it’s likely that I’ll also like other videos that Alice linked to. If 10 people linked to the video, then I might be interested in the other videos that those people linked to. So imagine a search facility that, given a search term (say, “bluegrass”), will find all videos that have that term in the title and then does a spreading activation by activating all of the videos that are linked to by people who linked to the videos in the initial result set.

So, searching for “bluegrass” might find 3,000 videos that have the term in their titles. Those 3,000 videos are in turn linked to by a total of, say, 4,000 different people. Combined, those 4,000 people can have many millions of different links, although there will be duplicates (that is, Alice, Bob, and George could all link the same video). We can score a video by relevance and popularity by taking into account the number of links it gets and the relative weight of each referrer’s links. But to do that I have to:

1. Create a referrer activation record for each referrer that links to any of the videos in the initial result set.
2. Group the referrer activation records by referrer, and compute a referrer score.
3. Create a video activation record for each video that the activated referrers link to.
4. Group the video activation records by video, and compute the video’s score.

This isn’t difficult to do, even when the scoring calculation is involved. It’s just creating lists, sorting, and then grouping. It’s what we programmers do all too much of every day. And it shouldn’t take very long, either: sorting and grouping tens of millions of items should be a matter of a second or two on modern hardware, even without taking advantage of muliple cores.

My first working cut of this took about 20 seconds, and a relatively few minutes’ time optimizing cut that in half. And then I was stuck. The first three steps happen in well under a second. But no matter what I did, the sorting and grouping portion (step 4) would take almost 10 seconds on a typical query that had about 10 million video references. And that just seemed like way too much time. I tried lots of different things before I got it into my head to try something extreme.

My video reference record was a simple KeyValuePair<int, double>, where the Key is the video id, and the Value is the score from a particular referrer. Those were being placed into a List that I then sorted by video id (Key). The sort was taking most of the time. And that’s just way too much time to sort 10 million items.

In retrospect, I should have thought of this earlier. But things are always obvious after the fact.

You see, I’ve run into this kind of thing before. My sort was written like this:

VideoReferences.Sort((r1, r2) => r1.Key.CompareTo(r2.Key));

I’ll let you look into the details of what exactly that syntax means, but in a nutshell it ends up creating a comparison function that is called through a delegate for each comparison. And, the structures I’m sorting (KeyValuePair) occupy 16 bytes each, meaning that for each swap that occurs during the sort I’m moving 48 bytes around. Like I said, I don’t normally think about this stuff because performance is usually good enough.

But benchmarking results showed conclusively that the sort was taking way more time than I thought it should. So, I thought, what if I could make a list of a native type and sort that? What, indeed.

I changed my reference structure so that it takes only 8 bytes. It now looks like this:

[StructLayout(LayoutKind.Explicit)]
struct VidVote
{
    [FieldOffset(0)]
    public ulong Combined;
    [FieldOffset(0)]
    public float VoteScore;
    [FieldOffset(4)]
    public int VideoId;
}

For those of you who are unfamiliar with C#, that’s the C# way of declaring a union. It packs the integer video id and the floating point score (float is fine here for individual values) into a single 8-byte structure. The Combined field treats the two values as a single unsigned long integer, with the video id in the high 32 bits.

What’s that do for me? Well, I can then write this:

VideoReferences = new List<ulong>(NumberOfReferences);
// ... populate the list with
var v = new VidVote();
v.VideoId = id;
v.VoteScore = score;
VideoReferences.Add(v.Combined);
// and then sort it.
VideoReferences.Sort();

With this structure, Sort uses the default comparison for ulong, which internally does a native 64-bit integer comparison directly rather than calling a comparison delegate.

The result? Sort time went from almost eight seconds to less than two seconds, and the subsequent grouping code is also faster than in the previous version. I’m a little bit annoyed that I had to resort to these bit twiddling tricks, but I can’t complain too much about a 70% decrease in run time.

And the really nice thing is that given this new structure I can see another improvement that should knock another big chunk off the run time.

The idea behind data format standards is to ensure that disparate tools can communicate using a common “language.”  When the standard includes potential ambiguity, things get messy.

A case in point is JSON (Javascript Object Notation).  The standard for escaping characters in strings looks like this:

In English, that says that the only characters that must be escaped are quote (“), backslash¹ (\), and control characters.  An escaped character starts with backslash and the following character(s) must be one of those identified.  That’s all good except for one item:  the “solidus” (/).  That character can be escaped, but it does not have to be.  So in a string, “/” and “\/” mean the same thing.

Why?  The potential ambiguity here is the exception to the rule.  Somebody implementing a JSON processor might easily interpret that to mean that the slash (I’m sorry, “solidus”) must be escaped.

---

¹”solidus”? Learn something new every day. It’s too bad that they didn’t come up with a unique name for “\”.  ”Reverse solidus” is harder to say than “backslash.”

The HttpListener class in .NET lets you create a lightweight HTTP server without having to go through all the rigmarole¹ of installing and managing IIS. It’s incredibly easy to get a simple HTTP server up and working with HttpListener

But when it comes to handling query parameters, things break in a very strange way. The server I’m working on currently accepts requests to search for strings in video titles. Last night I got a bug report saying that it didn’t work when searching for Kanji (Japanese) characters. David was looking for the string “尺八”², and got no results back even though he knew that there were matching titles in the database.

When a browser sends a query string to the server, it encodes the string using the UTF-8 character encoding. So David’s search for “尺八” resulted in this request to my server: “/?q=%E5%B0%BA%E5%85%AB”. Which is correct.

Then things get weird.

The HttpListenerContext.Request object contains all the information about the request that came to the server. If I look at the relevant properties, I see the following:

Request.RawUrl = "/?q=%E5%B0%BA%E5%85%AB"
Request.Query["q"] = "尺八"
Request.Url = {http://localhost:8080/?q=尺八}

The problem here is that the Request.Query property is apparently interpreting the encoded query string parameter using something other than UTF-8. And, looking at the code for HttpListenerRequest.QueryString (part of the .NET runtime library) confirms that:

public NameValueCollection QueryString
{
    get
    {
        NameValueCollection nvc = new NameValueCollection();
        Helpers.FillFromString(nvc, this.Url.Query, true, this.ContentEncoding);
        return nvc;
    }
}

The problem is the this.ContentEncoding, which says, “use the Request object’s encoding to interpret this string.” That’s pretty strange. It’s hard to be sure, but I think that the current standard (RFC3986) says that query strings should be UTF-8 encoded. If that’s true, then this is a bug in the HttpListenerRequest implementation.

Fortunately, there’s an easy workaround. The Request.Url property is properly formed, so I can use its Query property to construct my own queryString collection and ignore Request.QueryString:

var queryString = HttpUtility.ParseQueryString(context.Request.Url.Query);
string q = queryString["q"];

As far as I know, this is the only way to properly handle encoded query strings in HttpListener. If you know of some way to make Request.QueryString work as expected (or can tell me why the current behavior isn’t a bug), I’d sure like to hear about it.

---

¹I always pronounced that word “rig-a-ma-role.”  But the word is “rig-ma-role”. Learn something new every day.

²WordPress lets you add Unicode characters when adding a new post, but if you pull the post up to edit it afterwards, the Unicode characters get turned into question marks. Also, the “new post” editor accepts Unicode characters directly but any editing done after that requires you to input the characters using HTML Unicode escapes, like <code>&#x5C3A;&#x516B;</code>.

How constant are constants?

I got a rude surprise today when I discovered that constants in C# (.NET programs in general) are a little more constant than I thought. I know that sounds strange, but let me explain.

Here’s a C# class that defines two constants and a method that outputs those constants.

using System;

namespace OtherTest
{
    public static class TestObj
    {
        public const int ConstInt = 42;
        public const string ConstString = "First test";

        public static void ShowConstants()
        {
            Console.WriteLine("TestObj.ShowConstants");
            Console.WriteLine("ConstInt = {0}", ConstInt);
            Console.WriteLine("ConstString = {0}", ConstString);
        }
    }
}

We can compile that into OtherTest.dll with a simple command line:

csc /t:library OtherTest.cs

If you’re having trouble running the compiler, go to your All Programs menu and select Visual Studio|Visual Studio Tools|Visual Studio Command Prompt. Then you should be able to run the command line compiler.

Okay so far. Here’s some code that references the constants in that class:

using System;

using OtherTest;

namespace testo
{
    class Program
    {
        static void Main()
        {
            Console.WriteLine("Inside Program.Main");
            Console.WriteLine("ConstInt = {0}", TestObj.ConstInt);
            Console.WriteLine("ConstString = {0}", TestObj.ConstString);
            TestObj.ShowConstants();
        }
    }
}

Compile that program and link with the OtherTest assembly with this command line:

csc /t:exe /reference:OtherTest.dll ConstTest.cs

That creates ConstTest.exe which, when run, provides this output:

C:\DevWork\ConstTest>ConstTest
Inside Program.Main
ConstInt = 42
ConstString = Firsttest
TestObj.ShowConstants
ConstInt = 42
ConstString = Firsttest

That’s exactly what we expect. Now, change the values of the constants in OtherTest.cs:

        public const int ConstInt = 99604;
        public const string ConstString = "Second test";

And re-compile the assembly:

csc /t:library OtherTest.cs

And run the ConstTest.exe program again:

C:\DevWork\ConstTest>ConstTest.exe
Inside Program.Main
ConstInt = 42
ConstString = Firsttest
TestObj.ShowConstants
ConstInt = 99604
ConstString = Second test

If you’re as surprised as I am, raise your hand. The constant that the main program sees is different from the constant that is defined in the external assembly.

I understand what’s going on, but I’m pretty surprised by it. The compiler, when it compiled ConstTest.cs, reached into OtherTest.cs, got the values of the constants, and included them as constants in the compiled code. So when the code references TestObj.ConstInt at runtime, it’s really just getting the constant 42. That all makes sense. Except, of course, when you change the constant in the OtherTest.cs assembly, re-compile, and the values don’t match.

What surprises me is that the C# compiler (CSC) hoists the constants from the assembly. After all, the compiler is just creating MSIL (intermediate code) that is later compiled to native code by the JIT compiler at runtime. I would have expected CSC to write MSIL that says, in effect, “Use the constant value defined in that other assembly here,” and let the JIT compiler figure out how to optimize everything. That would eliminate the confusion you see above, and I don’t understand why it’s not done that way.

The thing to remember here is that constants are evaluated at compile time. I don’t know all the ramifications of this, but one thing is for certain: if your program references constants that are defined in an external assembly, then your program is at risk any time that assembly is changed. Unless you make the rule that a publicly visible constant never changes value throughout the life of the source code, you’re running the risk of encountering a very difficult to find bug that will “go away” when you re-compile the project. And there’s nothing worse than bugs that just “go away.”

I’m developing a generic Range class in C# so that I can create comparison ranges.  The idea is that I can replace code like this:

int MinValue = 22;
int MaxValue = 42;
...
if (val >= 22 && val < 42)
{
}

with this:

Range<int> MyRange = new BoundedRange(
    22, RangeBoundType.Inclusive,
    42, RangeBoundType.Exclusive);
...
if (MyRange.Contains(val))
{
}

In isolation it doesn’t look like a win but if you’re doing that range comparison in multiple places or working with multiple ranges, some of which can have an open-ended upper or lower bound, or  bounds that can be inclusive or exclusive, working with a Range type can save a lot of trouble.

Before we go on, let me introduce a little bit of notation.

First, the characters ‘[' and ']‘ mean “inclusive”, and the characters ‘(‘ and ‘)’ mean “exclusive.”  So, assuming we’re working with integral values, the range [1,30) means that the numbers 1 through 29 are in the range.  Similarly, (1, 30] means that the numbers 2 through 30 are in the range.

To specify “unboundedness,” I use the character ‘*’.  So the range [*,255] means all numbers less than or equal to 255.  And, of course, the range [*,*] encompasses the entire range of values for a particular type.  By the way, inclusive and exclusive are irrelevant when unboundedness is specified.  That is, [*,255] and (*,255] are identical ranges.

A Range type also allows me to do things like compare ranges to see if they overlap, if one contains the other, etc. And therein lies a problem. Consider the two byte ranges [0,*] and [*,255].

It should be clear that, since the range of a byte is 0 through 255 (inclusive), the two ranges are identical. The first range has a lower bound of 0, inclusive, and is unbounded on the upper end.  The second range has defined bounds of 0 and 255.  As programmers, we can tell by inspection that the two ranges are identical.

Unfortunately, there’s no way to write generic code that can determine that the ranges are equivalent.  Although the primitive types available in C# all have defined maximum and minimum values (Int32.MaxValue and Int32.MinValue, for example), not all types do.   And since I might want to have ranges of strings or other types that don’t have defined bounds, there’s no general way to tell the difference between a range that has no defined upper bound and a range whose upper bound is the maximum possible value for that type.  If I wanted that ability, the only way would be to pass maximum and minimum possible values for each type to the Range constructor–something that I’m not willing to do and might not even be possible.  What’s the maximum value for a string?

The inability to determine that an unbounded range is equivalent to a bounded range makes for some interesting problems. For example, consider the two byte ranges [1,*] and [0,255].  It’s obvious to programmers that the second range contains the first range. But how would you write a function to determine that?

public bool Contains(Range<T> other)
{
    // returns true if the current range contains the other range
}

Since there’s no way to convert that unbounded value into a number, the code can only assume that the upper bound of the first range is larger than the upper bound of the second range. Therefore, Contains will return false.

Whether that’s an error is a matter of opinion.  Logically, having Contains return false in this case is the correct thing to do because “unbounded” is larger than any number.  But it seems like an error in the context of types like byte that have limited ranges, because there’s really no such thing as an unbounded byte.  Rather, byte has a maximum value of 255 and one would expect the code to know that.

As I said, it’d be possible to extend the Range class so that it knows the minimum and maximum values for the primitive types, and give clients the ability to add that information for their own types if they want.  That way, an unbounded upper value for an integer would get  Int32.MaxValue.   That way, the code would “do the right thing” for the built-in types, and clients could define minimum and maximum values for their own types if they wanted to.

But I wonder if it’s worth going to all that trouble.  Is it more sensible to explain the rules to programmers and expect them to define specific bounds (i.e. not use unbounded) if they think they’ll be working with ranges (as opposed to comparing values against ranges) of primitive types?