Concurrency: Aggregating concurrent requests to a heavy function

Standard

I have been dealing with some interesting optimization problems these days, and one of them was a heavy method being called multiple times with the same input in a very short period of time.

The method DownloadCustomersInternal is used to download customer data from a server asynchronously and returns a Task. It resides in a class that is shared across multiple components, and it often gets called by these components almost at the same time. When there’s a lot of data to download, this method can take a while to finish, it makes sense for the callers of this method to wait on the same task if there’s already one. So a wrapper method DownloadCustomers is written:

private Task _downloadTask;
private readonly object _downloadLock = new object();

private Task DownloadCustomers()
{
    lock (_downloadLock)
    {
        // If there is already a download task, just return this one.
        if (_downloadTask != null)
            return _downloadTask;

        // Perform the real download and assign it's task to the download task reference.
        _downloadTask = DownloadCustomersInternal();

        // When the download process is done, clear the download task reference.
        return _downloadTask = _downloadTask.ContinueWith(task =>
        {
            lock (_downloadLock)
                _downloadTask = null;
        });
    }
}

The wrapper method simply checks if there is already a _downloadTask and returns it if there is. This ensures that all calls to this method get the same Task instance before _downloadTask is set to null, which only happens after DownloadCustomersInternal is finished asynchronously. Because the code sets _downloadTask to null uses the same lock, it guarantees thread safety of the variable.

This will resolve the problem by returning the same Task to callers who requests the data while the data is being downloaded, but what if the method is called right after a previous download is finished? Downloading the same data in very close succession can also be considered redundant, so it would be nice to introduce some sort of “cooling period” before the next download can be initiated. Therefore, an updated version of the above method is written:

private Task _downloadTask;
private readonly object _downloadLock = new object();
private DateTime _lastDownloadTime = DateTime.MinValue;
private static readonly TimeSpan MinimumDownloadInterval = TimeSpan.FromSeconds(5);

private Task DownloadCustomers()
{
    lock (_downloadLock)
    {
        // If there is already a download task, just return this one.
        if (_downloadTask != null)
            return _downloadTask;

        // Check if the time between this download request and the previous one is too close.
        var intervalFromLastDownload = DateTime.Now - _lastDownloadTime;
        if (intervalFromLastDownload < MinimumDownloadInterval)
        {
            // If this download request is too close to the previous one,
            // make this request wait until the minimum download interval is passed,
            // then perform the download.
            var waitTaskSource = new TaskCompletionSource<bool>();
            _downloadTask = waitTaskSource.Task.ContinueWith(_=>DownloadCustomersInternal()).Unwrap();

            // Force the wait in a background thread to ensure a non-blocking UI experience.
            ThreadPool.QueueUserWorkItem(_ =>
            {
                Thread.Sleep(MinimumDownloadInterval - intervalFromLastDownload);
                waitTaskSource.SetResult(true);
            });
        }
        else
            // If this download request is far enough from the last one,
            // just perform the normal download.
            _downloadTask = DownloadCustomersInternal();

        // When the download process is done, always clear the download task reference
        // and update the download timestamp.
        return _downloadTask = _downloadTask.ContinueWith(task =>
        {
            lock (_downloadLock)
            {
                _downloadTask = null;
                _lastDownloadTime = DateTime.Now;
            }
        });
    }
}

The key in this update is determining if a call is too close to a previous call when there is no task running. If the call is too close, simply wait in the background until MinimumDownloadInterval elapses. The waiting code in the background is also thread safe because waitTaskSource.Task.ContinueWith (line 22) is assigned to _downloadTask in the same scope of the first lock, and waitTaskSource is only set to finish when the background wait is elapsed.

Search algorithm and the golden ratio

Standard

From time to time, I need to insert an item to the correct index in an already sorted collection. One good example is a list of contacts, where the list is already sorted by the last name, and displayed somewhere in the UI. If the user adds a new contact, the new one needs to appear at the correct position.

So I wrote 2 little helper methods to do just that:

private static int ConditionalIndex<T>(this IList<T> list, T item, Func<T, T, int> comparer)
{
    var length = list.Count;
    for (var i = 0; i < length; i++)
        if (comparer(list[i], item) > 0)
            return i;
    return length;
}

public static void ConditionalInsert<T>(this IList<T> list, T item, Func<T, T, int> comparer)
{
    var index = list.ConditionalIndex(item, comparer);
    if (index >= list.Count) list.Add(item);
    else list.Insert(index, item);
}

And I use them like this:

var newContact = new Contact
{
    FirstName = "David",
    LastName = "Anderson"
};

MyContacts.ConditionalInsert(newContact, (c1,c2) => string.Compare(c1.LastName, c2.LastName));

This has been working fine until one day the list had grown big enough to take quite a few seconds to just add a new contact, and the user experience isn’t that good anymore.

The problem is that the ConditionalIndex method is just using a simple loop to search the index. So if the list has 10,000 items and it happens to be so unlucky that the new item needs to be inserted to the end of the list, it would take the method to go through all 10,000 items and execute that comparer delegate 10,000 times.

Therefore, I decided to optimize it to use a smarter algorithm.

After some digging around, I’ve chosen the Golden Section Search. It is a method that effectively reduces the range to be searched to find the target much faster.

To illustrate this idea in a simple way, let’s say we have a list of numbers from 0 to 9 but missing the number 7, and I want to insert 7 to this list. Golden section search will find the correct index by doing the following:

  1. Determine a split index, using the length of the search range divided by the Golden Ratio. In this case, it would be 10 ÷ 1.618 rounded up to integer, which is 6.
  2. Compare the item at index 6 with the item to be inserted, which is comparing number 6 and 7.
  3. If the item in the list is smaller, take the list before the split index as the new search range and repeat the above 2 steps. If the item is larger, take the list after the split index. If the item is the same, then the correct index is found.
  4. In our example, it would mean to take 8 and 9. The new search range length is 2 so the new split index is 2 ÷ 1.618 ≈ 1.
  5. Compare 9 to 7 means taking 8 as the new search range.
  6. Since there’s only 1 item left in the search range, simply compare 8 to 7 and we get the correct index to insert is the index before 8, which is 7.

My actual implementation of this algorithm is as follow:

public static int ConditionalIndex<T>(this IList<T> list, T item, Func<T, T, int> comparer)
{
    var length = list.Count;
    if (length == 0)
        return 0;

    const double goldenRatio = 1.618;
    var startIndex = 0;
    var endIndex = length - 1;
    while (true)
    {
        // If the start index is larger then the end index,
        // that means the search has already passed all necessary
        // search ranges, just return the start index.
        if (startIndex > endIndex)
            return startIndex;

        // If the start index is the same as the end index,
        // that means there is only 1 item left to compare.
        // Compare this item and return the result.
        if (startIndex == endIndex)
            // If the item in the list is larger than the given item,
            // retrun the index of the item in the list, otherwise return the next index.
            return comparer(list[startIndex], item) > 0 ? startIndex : startIndex + 1;

        // If there are still multiple items in the search range,
        // find the split index of the search range.
        var splitIndex = (int)Math.Round(endIndex - (endIndex - startIndex) / goldenRatio);

        // Compare the item sitting at the spliting point.
        var result = comparer(list[splitIndex], item);
        if (result > 0)
            // If this item is larger than the given item,
            // keep searching the range before the splitting point.
            endIndex = splitIndex - 1;
        else if (result < 0)
            // If this item is smaller than the given item,
            // keep searching the range after it.
            startIndex = splitIndex + 1;
        else
            // Otherwise, return the split index.
            return splitIndex;
    }
}

This has resulted in a huge boost in my stress test on a list that has 500,000 items, almost 100 times faster.

Although the use of the golden ratio is suppose to give you the best split index in general, you need to use Math.Round to round it up to an int for the most accurate result. I found that this is actually a trade off compare to loosing a bit of the precision and just ignore rounding the result casting it directly to and int:

var splitIndex = (int)(endIndex - (endIndex - startIndex) / goldenRatio);

This has given me another 1 to 2% speed boost in my stress test.

These extension methods are part of the EnumerationExtensions class in my open sourced Codify library on GitHub.

Reactive Drag in WPF

Standard

It has been way too long since I last updated my blog. Well I’ve been a bit lazy and busy at the same time, you guys get the excuse😀

So without further ado, let’s get down to the fun stuff: doing a proper drag in WPF by using the Reactive Extensions.

I have covered some RX basics and usages 2 years ago for Silverlight/WP7. This is not only a revisit but more on using RX to solve a more complicated case as an example. Let’s start with the basics again:

var mouseDownEvents = Observable.FromEventPattern<MouseEventArgs>(this, "MouseLeftButtonDown");
var mouseMoveEvents = Observable.FromEventPattern<MouseEventArgs>(this, "MouseMove");
var mouseUpEvents = Observable.FromEventPattern<MouseEventArgs>(this, "MouseLeftButtonUp");

var dragEvents =
    from mouseDownPosition in mouseDownEvents
    from mouseMovePosition in mouseMoveEvents.StartWith(mouseDownPosition)
                                             .TakeUntil(mouseUpEvents)
    select mouseMovePosition;

dragEvents.Subscribe(eventPattern =>
{
    // Move things on UI.
});

This is a very simple drag example using RX, it is basically saying, react to all mouse move events, only after the mouse down event has happened and before any mouse up events have occurred. In the subscribe lambda expression, you can do things like get the current mouse position and use it to move things around on the UI.

However, in WPF a more appropriate way to do drag and drop, is to use the System.Windows.DragDrop.DoDragDrop method, so that you can define the drag source, drag data, allowed effects, etc…

dragEvents.Subscribe(eventPattern =>
{
    DragDrop.DoDragDrop(this, this, DragDropEffects.All);
});

It all looks nice and easy, except that:

  1. The DoDragDrop method is a synchronous method. Your code won’t pass that line until you drop.
  2. The method captures the mouse so no mouse up event will fire.

If no mouse up event is fired, the subscription won’t know when to stop, that means even after you dropped the object, the subscription will still react to mouse movements on the current element – a memory leak.

So it seems it’s reasonable enough to change the MouseLeftButtonUp event query to a Drop event query:

// This is the non-working query:
// var mouseUpEvents = Observable.FromEventPattern<MouseEventArgs>(this, "MouseLeftButtonUp");

// This should work:
var dropEvents = Observable.FromEventPattern<MouseEventArgs>(this,"Drop");

var dragEvents =
    from mouseDownEvent in mouseDownEvents
    from mouseMoveEvent in mouseMoveEvents.StartWith(mouseDownEvent)
                                          .TakeUntil(dropEvents)
    select mouseMoveEvent;

// ...

If you play around with this code for a while, you may realize that there are 2 major catches:

  1. If the current element is part of a complicated UI, you have no idea which element’s “Drop” event you should listen to. The drop could happen at anywhere.
  2. Even if you use VisualTreeHelper or Window.GetWindow to get the root element, if the drop happens on somewhere that does not allow dropping (e.g. the AllowDrop property is not set to true), then no Drop event will be raised.

So it looks like we can’t rely on drop either.

If you look at the code carefully, the drag detection is not a drag detection, it is really a “drag start” detection. As soon as you detect the starting of a drag, you can call DoDragDrop method and the framework can handle it from there. So we can see the problem as: how can I detect the drag start moment and not worry about the rest of the mouse movements?

Well logically the drag start is the one immediate mouse move event right after a mouse down event, so accordingly, we can modify the query to this:

var dragStartEvents =
    from mouseDownEvent in mouseDownEvents
    from mouseMoveEvent in mouseMoveEvents.StartWith(mouseDownEvent)
                                          .TakeUntil(mouseUpEvents)
                                          .Take(1)
    select mouseMoveEvent;

dragStartEvents.Subscribe(eventPattern =&amp;gt;
{
    DragDrop.DoDragDrop(this, this, DragDropEffects.All);
});

Now we are specifying query to only get 1 mouse move event after a mouse down event before any mouse up events. Now you can drag the hell out to anywhere without worrying about detecting where it is dropped.

In fact, the StartWith method includes the mouse down event before the first move event, so the subscription is not really reacting to the first move event, but rather, the mouse down event before that. I know this seems awkward, but I can reproduce this behaviour in .NET 4.0/4.5.

So if this annoys you, we can make the query a little bit error proof:

var dragStartEvents =
    from mouseDownEvent in mouseDownEvents
    from mouseMoveEvent in mouseMoveEvents.StartWith(mouseDownEvent)
                                          .TakeUntil(mouseUpEvents)
                                          .Skip(1)
                                          .Take(1)
    select mouseMoveEvent;

Now, this looks a solid query. It stops at mouse up events, skips the first mouse down event then take the real first mouse move event.

Preventing Accidental Drag

If you are a perfectionist, you may want to consider accidental drag detection. Basically we allow the mouse movement within a very small area around the mouse down position without triggering the drag. To do this, we need to alter the event queries a bit so that instead of getting event sequences, we get mouse position sequences:

var mouseDownEvents = Observable.FromEventPattern<MouseEventArgs>(this, "MouseLeftButtonDown").Select(pattern => pattern.EventArgs.GetPosition(this));
var mouseMoveEvents = Observable.FromEventPattern<MouseEventArgs>(this, "MouseMove").Select(pattern => pattern.EventArgs.GetPosition(this));
var mouseUpEvents = Observable.FromEventPattern<MouseEventArgs>(this, "MouseLeftButtonUp").Select(pattern => pattern.EventArgs.GetPosition(this));

Then we need to incorporate one more “Where” filter in the drag start detection query:

var dragEvents = 
    from mouseDownPosition in mouseDownEvents
    from mouseMovePosition in mouseMoveEvents
                                  .Where(mouseMoveEvent => 
                                             Math.Abs(mouseMovePosition.X - mouseDownPosition.X) > SystemParameters.MinimumHorizontalDragDistance
                                             || Math.Abs(mouseMovePosition.Y - mouseDownPosition.Y) > SystemParameters.MinimumVerticalDragDistance
                                        )
                                  .StartWith(mouseDownPosition)
                                  .TakeUntil(mouseUpEvents)
                                  .Skip(1)
                                  .Take(1)
    select mouseMovePosition;

There you go folks, take the reactive looking functional monad code (or whatever you want to call it) and rock hard out there!

MSMQ: solving access denied errors for private queues

Standard

For the majority cases, it is pretty obvious that you don’t have the required security permission to access a particular message queue if you get the MSMQ “Access to Message Queuing system is denied” exception on accessing a private queue.

Security information for the private queues are managed in the same way as files and folders in Windows:

  • Browse to your private queues in the management console (Start -> type “computer management” and enter -> Services and Applications -> Message Queuing -> Private Queues).
  • Right click on the target queue for it’s Properties, you’ll see the same security tab in the popping up window.
  • Here you can assign property permissions to the user/group that your application runs on.
    • If this is for debugging or testing purpose and you are not who/which group to assign the permission to, you may try giving Full Control to “Everyone”.

If you do not have the permission to modify the security setting of this queue, then this queue was probably not created by you.

The first thing you need to do is to take over the ownership by going to Advanced -> Owner -> select or find your user/group -> OK. This requires that you have permission to take owner ship from another user, and it usually means that you need to be and administrative user first.

Once you have taken the owner ship, you then can modify the security settings for this queue without problems.

What happens if the above did’t work

There’s another trick that you  can try here.

Usually the meta data of these queues are stored at C:\Windows\System32\msmq\storage\lqs. If you use any text editor to open files in this folder, you’ll see the details of the queues. By default, the Administrator group and the MSMQ system account has full control on these files, so if you are an administrative user, you should be able to modify these files (otherwise, try taking ownership of these files see if that works).

  • First, you need to stop the MSMQ service.
  • Then locate the queue file that you are having problem with, the Security attribute is the one we need to modify.
  • If you need a working value for this attribute, you can create a new private queue in the management console and copy the security value in this new queue to your target queue.
  • Now start the MSMQ service and hopefully this works😛

Resurrecting .NET Reflector and its Visual Studio Add-in

Standard

This could be a bit late but I guess it’s better than never. For folks who have missed the latest free version of .NET Reflector, which is NOT publicly downloadable from RedGate, here is your chance to grab it once and for all.

Remember to unblock the archive file before extracting them to avoid running into security issue when integrating with Visual Studio.

Unblock reflector.zip before extracting its contents

Download .NET Reflector 6.8 with Visual Studio Add-in

Activating the Visual Studio add-in

The reflector itself is pretty much a stand alone application which needs no installation. However, if you’d like to activate the included Visual Studio add-in, you’ll need to do the following:

  1. Open the file RedGate.Reflector.Addin in the package using any text editor.
  2. Modify the path in the <Assembly> element so that it points to where the RedGate.Reflector.Addin.dllfile is.
    • Note, this dll file needs to be in the same folder as the Reflector.exe file.
  3. Copy this add-in file to C:\Users\<user name>\Documents\Visual Studio <VS Version>\Addins\.
  4. Activate it in the Add-in Manager in Visual Studio (Top Menu Bar -> Tools -> Add-in Manager…).

Don’t forget that you can also turn on explorer shell integration from within reflector’s tools menu.

Have fun😉

What a bingle mess

Standard

I have to admit that the last 2 Bingle Maps updates were a total mess. Beginning with version 1.5 crashing all around when starting, sleeping, and exiting the app after updating from a previous version, then there’s this not-any-better version 1.6, which silences the crashes but made the app not saving any data at all!

I have to apologise to all of the users out there who’s experiencing these frustrations and am grateful for those who sent in the error reports and the helpful feedbacks.

1.6 was pulled from Market place as soon as I realised the situation, and 1.7 – which is suppose to end all this madness, was submitted to App Hub yesterday. While waiting for Microsoft to test and certify the new version which usually takes a week, I decided to put down some details on what has really happened to the last 2 updates, technically.

It all starts with auto complete

The first new feature I implemented for version 1.5 was auto complete for the search and direction finding boxes. This required some structure changes in one of my data model, which is saved and loaded when the app starts and exits. This is the very culprit for all of those crashes. But how can I not have caught this during my testing?

Turned out that the crashes would only happen if 1.5 tries to load the saved data from a previous version, and this only happens once. This is because I use Silverlight Serializer (SS) to serialise the data to isolated storage, and SS is a binary serialiser, which does not deal with data structure change very well. Therefore, when 1.5 starts for the first time after updating, SS tries to deserialise the old binary data into an updated 1.5 object, which then causes the first exception. This exception stops all other necessary initialisation of the app leaving the app in a half broken state. When you sleep or exit the app however, since there was no data loaded, the app will do a clean up in the isolated storage so that the next time the app starts, it starts anew. This is exactly why the crashes only happens once.

Then there was the new WP7.1 SDK

Half way through 1.5, the WP7.1 SDK beta 2 was released and as a developer I upgraded my phone to a Mango dev build as soon as I can. I was amazed by how far Mango has reached and excited about all of the new features in the SDK. So I quickly wrapped up 1.5 with some extra performance improvements and decided to update the whole project to 7.1.  While I was at it, I figured that it was a good chance to also update all third party libraries that the app uses to their latest version too, such as RestSharp and DropNet, and of course the Silverlight Serializer.

Not long after that, I started getting tons of error reports due to the 1.5 crashing bug. It was till then I realised that it was a huge mistake to rush updating everything to the latest version before making sure that 1.5 was all OK. Because once the project is updated to target the 7.1 runtime, you can’t downgrade back to 7.0. So I had no choice but to revert back in my version control history.

That was a real harsh lesson for me to completely understand how crucially important it is to keep your version control history nicely commented. All of my SVN check-ins were made without comments and there are thousands of them. So after hours of looking at the file diffs in WinMerge, I finally reverted the project back to where I pushed out 1.5, EXCEPT forgetting the updated Silverlight Serializer.

The new Silverlight Serializer is targeting Silverlight 4 framework, which is incompatible with the Silverlight 3.7 CLR running on all of the devices out there. But guess what, I never had a chance to catch this (again) because my phone was running Mango, which has Silverlight 4 CLR. So again, I foolishly thought that I had patched up the 1.5 bug and submitted 1.6 to App Hub. You probably know the rest of the story from here.

One thing surprises me is that the App Hub QA team didn’t run into this bug either. The whole testing and certification process was smooth for 1.6 and it was published to Marketplace within a week. Does it mean that they are using Mango phones to test the new submissions now?

So what’s now

Finding out that 1.6 became a bigger disaster was a nightmare to me. I realised that I really have to clean this up and do it properly from now. So I started re-organising my SVN repo into Git and established proper branches just like an enterprise development project. I then wiped the Mango rom on my phone after that, re-flashed the factory rom, went through the lengthy Zune update process and finally got the phone back to official NoDo environment. From here I could test the re-compiled Silverlight Serializer for 3.7 CLR and made sure every thing works fine on a normal NoDo device.

So 1.7 was submitted and it is running fine on my NoDo phone now. Hopefully this would put an end to the madness. I’d label this as the worst disaster in my development experience so far. But I guess sometimes the most valuable things can only be learnt from the toughest lessons.

Bingle Maps 1.2 with Google Global Business Search

Standard

Bingle Maps 1.2 has been released to the Windows Phone 7 Marketplace today. This version utilizes Google’s “Places” API and “Geocode” API to power search and address lookup feature. Bing’s doing a good job on routing but I’d compare routing data from both side to see if I should also switch routing data over. AFAIK, Google’s Directions V3 API only returns encoded way points and decoding them is not that simple.

Categorized business search would most likely come in next version (aka, the “what’s nearby” feature), and I’m also looking into transit information and compass support.

Also celebrating Bingle Maps passing 20,000 users😀