Monday, April 2, 2012

There and back again, again: Any resource's tale

Or, how to generically set and restore state when an exception is raised

I've written twice before (here and here) about making cursor changes more robust with the using statement in C#. These allow states to be reset to correct values regardless of whether or not an exception is raised during some processing. As promised at the end of the last article, today I explain how to use lambdas to easily protect any type of "resource" without having to create a new class or sprinkle your code with try/finally blocks.

To set things up and provide a bit of context, the other day in a code review, I found this:

someFlag = true;
someStartStateMethod();
// Do some work
someResetStateMethod();
someFlag = false;

Over the years, I've seen this pattern repeated, in different domains and different languages and not necessarily limited to setting a flag. Whenever I do, I ask "if an exception happens anywhere in 'do some work,' should the state be reset?" I won't say the answer should always be "yes," but I've not yet found a "no." And this case was no exception.

Since some of the places this was done was nested, I wanted a way to clean all this up that didn't involve adding try/finally blocks. Each try/finally would add another level of indentation; it would get pretty deep pretty fast. Also, it would clutter up the code with noise that didn't really have anything to do with the work needing to be done. In other words, I didn't want this:

someFlag = true;
try
{
   someStartStateMethod();
   try
   {
     // Do some work
   }
   finally
   {
      someResetStateMethod();
   }
}
finally
{
   someFlag = false;
}

In my last article, I separated the code actually handling the protection from the code controlling the invocation of that protection by using inheritance. I created a base abstract class to handle the general IDisposable pattern and descendent classes to handle the actual protection. In that article, I showed a class to handle changing a cursor and then changing it back to the current value.

I quickly realized this code was simply another example of that pattern. I could do the same thing as earlier and put the someStartStateMethod() and someResetStateMethod() in a descendant class. If I followed that pattern, the code under review could be something more along the lines of:

using(new ChangeSomeFlag())
using(new ChangeSomeStateMethod())
{
   // Do some work
}

This is somewhat better.

However, in this case, creating a new class for each thing needing protection didn't seem too appealing. There would be a lot of small special purpose classes, some of which might only be used once. It seemed like a sledgehammer to drive a brad. For this code, I wanted to emphasize composition over inheritance.

Enter lambdas. Because lambdas allow you to treat code as data, they allow easy composition. The LINQ and Rx libraries are great examples. They provide many generic methods (e.g. Where, Select, Any) that have the ability to compose in functionality through the use of lambdas to work on specific types for specialized purposes.

In this particular case, lambdas can be used to contain the code that handles the protection and passed to a class whose sole job is to handle the invocation of that code at the appropriate time. Rewriting the previous example with a new, as yet undefined ResourceProtector class, its use looks like:

using(new ResourceProtector(() => someFlag = true, () => someFlag = false))
using(new ResourceProtector(() => someSetStateMethod(), () => someResetStateMethod()))
{
   // Do some work
}

In this code, two expressions are passed to the constructor of the ResourceProtector class that handle the saving and restoring of state. Here is a single class that can be reused over and over in different situations to protect different types of resources. I think this is a beautiful example of the single responsibility principle combined with the power of lambda expressions to handle composition.

public class ResourceProtector : IDisposable
{
   private bool Disposed { get; set; }
   private Action EndProtection { get; set; }

   public ResourceProtector(Action startProtection, Action endProtection)
   {
      Disposed = false;
      EndProtection = endProtection;
      startProtection();
   }

   public void Dispose()
   {
      DisposeInt();
      GC.SuppressFinalize(this);
   }

   private void DisposeInt()
   {
      if (Disposed)
         return;

      EndProtection();
      Disposed = true;
   }

   ~ResourceProtector()
   {
      DisposeInt();
   }
}

If you have any questions, suggestions or comments, please feel free to leave them below. Until next time, subscribe to the Twitter feed to get notified of future articles and hear about other development related things.

Wednesday, March 21, 2012

7 ways to remove duplicate strings from a list (with timing results)

Recently there was a question on CodeProject about the fastest way to remove duplicate strings from a List. There were a bunch of alternative solutions presented, but no comparison to see what was faster. This post will show each solution and time them in a standard way to determine which actually answers the question.

About the test

Test setup creates a list of 1,000 random strings all 50 characters long. This is the expected result. It then creates duplicates for every other item and then for every 5th item. A list containing duplicates is created from the expected results and the duplicates. Note that for the even 5th items, there are actually two duplicates in the final list.

The core test method takes the list of duplicates, sets up a stopwatch and then calls the method to remove duplicates 1,000 times, each time passing in a new copy of the duplicate list. Since one of the methods under test changes the input list, this causes each iteration to work on the same, pristine input list. The elapsed time from the stopwatch is output and assertions are in place to make sure the method under test does what's expected.

About the methods under test

I've taken the code presented in the original thread and made slight modifications to make them all conform to the same interface. Some of them were code snippets or descriptions so I made my best guess as to the authors' intent.

1. The original poster's solution

public static IList LoadUniqueList1(List doubledList)
{
   var uniqueList = new List();
   foreach (var item in doubledList)
   {
      var x = true;
      foreach (var compare in uniqueList)
      {
         if (item == compare)
         {
            x = false;
         }
         if (!x) break;
      }
      if (x)
         uniqueList.Add(item);
   }
   return uniqueList;
}

2. Same as above, except substituting Contains for the second loop

public static IList LoadUniqueList2(List doubledList)
{
   var uniqueList = new List();
   foreach (var item in doubledList)
   {
      if (!uniqueList.Contains(item))
         uniqueList.Add(item);
   }
   return uniqueList;
}

3. Using a SortedList

public static IList LoadUniqueList3(List doubledList)
{
   var uniqueList = new SortedList();
   foreach (var item in doubledList)
   {
      if (!uniqueList.ContainsKey(item))
         uniqueList.Add(item, item);
   }
   return uniqueList.Values;
}

4. Using a HashSet

public static IList LoadUniqueList4(List doubledList)
{
   return new HashSet(doubledList).ToList();
}

5. Using LINQ Distinct

public static IList LoadUniqueList5(List doubledList)
{
   return doubledList.Distinct().ToList();
}

6. Using LINQ double iteration

public static IList LoadUniqueList6(List doubledList)
{
   var uniqueList = new List();
   uniqueList.Add(
      (from itm in uniqueList
      from compareItem in doubledList
      where itm == compareItem
      select compareItem).ToString());
   return uniqueList;
}

7. Sort and then build filtered list

public static IList LoadUniqueList7(List doubledList)
{
   var uniqueList = new List();
   doubledList.Sort();
   string lastEntry = string.Empty;
   foreach (string str in doubledList)
   {
      if (str != lastEntry)
      {
         uniqueList.Add(str);
         lastEntry = str;
      }
   }
   return uniqueList;
}

Timing results

The table below shows the elapsed time results for three test runs and the average elapsed time. The last column is how the strategy performed.

Before looking at the results, ask yourself "Which are the top two best performers?"


Comments about either the test methodology or results can be left below.

Test project available here.

Monday, March 12, 2012

There and back again, again: Several resource's tale

Or, how to safely change a cursor or other resource

In a previous article, I presented a simple class that utilized the IDisposable pattern to set the cursor to a specific value and then automatically reset it to the initial state when some work was accomplished. This simple class had two limitations: it only worked with WPF and it only worked on cursors.

To overcome these limitations, I refactored this to be more general. I changed the context to a generic type and added an abstract RestoreState method that's called when the class is either destroyed (preferred) or the finalizer is called. This allows all the basic plumbing regarding the IDisposable pattern to be contained in one class.

using System;

namespace ResourceProtection
{
    public abstract class ResourceChangeHandler : IDisposable
    {
        protected TContext Context { get; set; }
        private bool Disposed { get; set; }

        protected ResourceChangeHandler(TContext context)
        {
            Disposed = false;
            Context = context;
        }

        public void Dispose()
        {
            DisposeInt();
            GC.SuppressFinalize(this);
        }

        protected abstract void RestoreState(TContext context);

        private void DisposeInt()
        {
            if (Disposed)
                return;

            RestoreState();
            Disposed = true;
        }

        ~ResourceChangeHandler()
        {
            DisposeInt();
        }
    }
}

The beauty of this is it can be used as the base class for specific needs. The function of actually changing a resource is split out from the framework needed to manage the change. Here are three examples: one each for a WPF cursor changer, a WinForms cursor changer and a TreeView BeginUpdate/EndUpdate handler.

How to change a WPF cursor

public class WpfChangeCursor : ResourceChangeHandler{
    private Cursor OriginalCursor { get; set; }

    public WpfChangeCursor(FrameworkElement element, Cursor newCursor)
            : base(element)
    {
        OriginalCursor = Context.Cursor;
        Context.Cursor = newCursor;
    }

    protected override void RestoreState()
    {
        Context.Cursor = OriginalCursor;
    }
}

To use this, instantiate an instance of WpfChangeCursor in a using block, passing in the element who's cursor should be changed and the new value for the cursor. In this case, the context for the base class is the element containing the cursor to be changed. The descendant class has the responsibility to remember the current value and changing the cursor.

How to change a WinForm cursor

public class WinFormChangeCursor : ResourceChangeHandler{
    private Cursor OriginalCursor { get; set; }

    public WinFormChangeCursor(Cursor newCursor)
            : base(Cusor.Current)
    {
        Cursor.Current = newCursor;
    }

    protected override void RestoreState()
    {
        Cursor.Current = Context;
    }
}

This class is used by instantiating an instance of WinFormChangeCursor in a using block with the new value of the cursor passed to it. This is a little different from the WPF version since there is only one cursor for the application, rather than for each element. In this case, the context passed to the base is the current cursor value which is then used by RestoreState to put things back.

How to call BeginUpdate and EndUpdate safely

public class TreeViewUpdate : ResourceChangeHandler{
    public TreeViewUpdate(TreeView treeview)
            : base(treeview)
    {
        Context.BeginUpdate();
    }

    protected override void RestoreState()
    {
        Context.EndUpdate();
    }
}

And finally, here's a class to make sure EndUpdate is called for every BeginUpate on a TreeView. Like the WPF cursor changer above, the control is passed in as the context for the ancestor class. BeginUpdate is then called on the context. When the using block this class is controlled by finishes, the EndUpdate in RestoreState is called, again on the same context as the BeginUpdate.

This technique provides for a level of separation between the framework needed to safely do and undo things from the actual work of doing and undoing them. It works well for certain classes of problems, specifically fixed things that happen over and over again. The examples above of doing repetitive things on framework level items are good examples.

Sometimes though, one wants this type of functionality without the overhead of creating a new class each time. In the next article, I'll present a method of composing this type of behavior in a more adhoc manner.

Until then, subscribe to the Twitter feed to get notified of future articles and hear about other development related things. And if you have any questions, suggestions or comments, please feel free to leave them below.

Tuesday, September 27, 2011

How to fix Visual Studio C++ Warning: LINK4075

At the beginning of last week's sprint, I picked up a task to reduce our warning count. One of the issues that I scratched my head over a couple minutes was a bunch of warnings with the text warning LNK4075: ignoring '/EDITANDCONTINUE' due to '/SomeOtherSetting' specification. As indicated by the LNK identifier, I knew the linker emitted this warning. However, in my perusal of the linker options, I couldn't find where the EDITANDCONTINUE setting existed. I even glanced through the other property pages looking for it.

Per my wont, I searched the web and eventually found it based on some oblique references on a StackOverflow question. The reason I had trouble finding it? It's a compiler option. And it's not called EDITANDCONTINUE.

This is controlled by the Debug Information Format setting on the C/C++ General page. If the option is Program Database and Edit and Continue, a.k.a. /ZI, then the output obj files apparently have a flag embedded in them that is incompatible with certain settings in the linker. Hence, the linker emits the warnings when it hits these conditions. It would have been nice for the message to have contained the /ZI option (which is what's used in the compiler) rather then than the EDITANDCONTINUE pseudo-option which isn't used anywhere, as near as I can tell.

To fix this warning, either change the linker options that are incompatible with the /ZI option or change the compiler option to something other than /ZI, such as /Zi. As of the time of this writing, the linker options incompatible with EDITANDCONTINUE include setting optimization to /OPT:REF or /OPT:ICF, turning off incremental compilation or setting one of /ORDER, /RELEASE or /FORCE. (These are from this MSDN page.)

Hope this helps someone.

Friday, September 23, 2011

Sharing folders with Windows 8 between VirtualBox machines

Currently Windows 8 runs just fine inside a VirtualBox machine. However, guest additions, the tools to enable certain useful features of VirutalBox, do not yet work with Windows 8. Today I wanted to use some Visual Studio projects from an existing Windows XP virtual machine in my new Windows 8 machine. The obvious first choice was to simply use a shared folder on the host in both virtual machines. However, this requires the guest additions, so I went looking for a work around.

What I found to work was a second virtual hard drive. In VirtualBox, on my primary development machine, I created a new hard drive on the existing IDE controller. I then started the machine and went into Windows' device manager. The disk manager started the new disk wizard. After initialization, I created and formatted an NTFS partition. I then copied the files I wanted to work with to this new disk. Finally I shutdown this machine.

Next, in VirturalBox, I added the same, new hard drive image as a second drive on the Window 8 box's SATA controller. (If you add the drive to the IDE controller, Windows 8 will try to boot to it first and fail with a bad image error.) When I booted Windows 8 and went into Explorer, the second drive showed up with all the data I'd copied to it.

That's it, pretty simple and straight forward, but not the obvious (to me) first solution.

Warning: I don't know what would happen if both virtual machines are run at the same time. I suspect (and hope) the second one started would get some sort of sharing violation and not allow the disk to be mounted. I can't imagine VirtualBox is smart enough to allow two machines to attach to the same vdi file at the same time without corrupting the data. However, it seems to work just fine as long as there is only one machine using the file at any given point of time.

Hope this helps someone.

Monday, September 19, 2011

First Thoughts Regarding Windows 8

With all the hubbub around Microsoft's BUILD conference and the developer preview of Windows 8, I thought I'd grab a copy to check it out. This is what I found; it's going to be pretty short...

Installation

I downloaded a copy of Windows 8,[1] created a new machine in VirtualBox, attached the downloaded ISO to the CD and booted the machine.[2] It started the install OK and then hung part way through. After waiting awhile, I powered off the VM. On restart, it tried to do an install restart but this time give me a failure message. So I powered it down again and then back up. This time during the restart it showed me the partitions on the drive. I deleted all the previously created partitions and it finally ran through the install to the end. When it finished, it did the typical Windows reboot but hung during the reload. I turned the machine off, detached the ISO image from the CD and turned it back on. This time it booted just fine. It asked me a couple of standard questions, like user name and password and took me to a phone/tablet looking screen.

Cursor problems

At this point the cursor pretty much went wonky. Yes, that's a technical term. When moving the cursor from the host OS to the Windows 8 machine, the cursor would jump to an odd place and then jump back off the guest screen back to the host. It was pretty much unusable. I tried installing VirtualBox's guest additions. The installer asked all the startup questions but then stopped when I told it to begin the actual install saying it didn't support that version of Windows. I suppose that's not too surprising. As a last ditch effort, I moved the virtual screen off my large secondary screen to the laptop's smaller main screen and all of a sudden the cursor started working correctly. At this point I'm not sure if it's a problem with VirtualBox on the secondary screen or if it's a Windows 8 incompatibility or perhaps some of each. In any case, the cursor problem doesn't show up on the main screen and the mouse/keyboard capturing works as I'd expect; i.e. once the guest OS has control, you have to hit the Host button to get back out.

Operation

Once the cursor started working correctly, I played around with a bit. IE10 works pretty much like you'd expect a browser to although the UI is somewhat different in keeping with the Metro design. The biggest thing is the address bar is at the bottom of the screen. Other than that, it worked OK. Google returned search results. GMail showed me my mail. However, when I went to YouTube, it needed the Flash plug-in. I knew the Metro version of IE didn't support plug-ins, so I wasn't sure what would happen. But everything worked, sort of: clicking the link took me to Adobe's web site, downloading and installing worked just fine. Yet when I went back to YouTube, it still complained about no plug-in. I went to the desktop (one of the many tiles on the "start page"), clicked on the IE icon there and then navigated to YouTube. It worked. This is one of those differences between the Metro version and the desktop version. However, I had to know that going in, otherwise it would have simply looked like it didn't work. There was no indication saying the Metro version didn't support plug-ins or that the desktop version did.

I tried clicking on some of the other tiles on the start page and didn't get too far. Most of them seem to need features unique to mobile devices. Word Hunt wanted me to "bump" with a friend's device to initiate the connection. I assume that's some sort of bluetooth thing. Labyrinth simply sat there staring at me. No instructions. Clicking, click-dragging and other random character presses yielded no results. I'm guessing it wanted some sort of tilt sensor input. The last thing I tried was BitBox. I had high hopes of getting somewhere since it actually started with a mini-tutorial. My hopes were dashed on about the third step when told to do a pinch operation to continue. Um, how do you do multi-touch with a mouse?

At that point I pretty much gave up and turned the thing off. That was a bit of an adventure itself. First I tried sending the power off signal from VirualBox. This is equivalent to pressing the power button on a typical PC/Laptop. Nothing happened. I looked around a bit for a shutdown option. All I could find was logout. I ended up going to the desktop and pressing Alt-F4. That has worked since at least Windows 3.1, and it still does. I got a familiar "what do you want to do? shutdown, restart" type dialog. (I have subsequently learned there is a power button that's available after you logout.)

Opinions

My first impression after about an hour of playing with it is that it seems fairly comparable to the iPad and Android regarding user experience. (I've played around with both these about as much as I have Windows 8.) Basically there are big squares that slide around and you can click on them. The applications open in full screen mode. Shrug. I guess some people might get excited about it. To me, it seems about the same as everything else on the market.

What I find interesting about these devices is the infrastructure, development environment and community support that grows up around them. The iPad and Android ecosystems both have their strengths and weaknesses. I think it's too early to tell much about what will happen with the ecosystem around Windows 8. Will Microsoft learn from both their previous successes and mistakes, as well as those of Apple and Google, to become a market leader? Will they become another fairly equal player? Or will they become an also ran in this race?

From an internal design perspective, I like the direction Microsoft is going better than Apple or Google. Apple has a split between the desktop/laptop OS X and the mobile device iOS. Google is trying to scale the mobile/browser experience to the desktop in ChromeOS. I think both these are weak strategies.

Apple has two, separate code bases to maintain, much of which could probably be combined. I think long term this is going to cause compatibility problems much like Microsoft has had between the mobile/embedded Windows and the desktop version and more lately between WPF and Silverlight. Very similar systems with differing code bases have made the developer community pretty aggravated at times.

Google has a similar problem with the bifurcation between Android and ChromeOS. Android probably has the potential for making a pretty nice desktop OS. Give some development effort, it'd be pretty comparable, from a design perspective, as Windows 8. The high-level design documents for both would look very similar. However, Google has decided to try to expand the browser into an operating system. I've experimented with ChromeOS and it works acceptably if all you want to do is available on the web. But frequently I want to use my computer off-line and the whole ecosystem is not up to this task. Perhaps in 5 years everything will be a web app. I doubt it though.

Microsoft is pairing down the core of Windows and then placing different layers on top of it. From a design perspective this seems like the best long term solution. It has always appeared that desktop Windows was the first-class citizen and the embedded/phone OS by the same name (which only had passing resemblance to its big brother) was second-class. By putting a desktop UI on the same core as the mobile device UI, they can both become equal products, just for different markets. As a desktop developer, the biggest fear I have is, instead of raising the mobile UI to be equal to the desktop's, they are going to push the desktop down to second-class status. As it stands with this preview, the first and primary experience is the Metro look and feel. It works great on a tablet. I have yet to see it work well on a desktop. Without major changes to the current experience, I predict Windows 8 will work well on mobile devices but will not be adopted in the desktop world. Hmm, will Windows 8 make the year of the Linux desktop finally a reality?

Updates

The above all happened on Friday. Monday morning, I started the Windows 8 virtual machine. It hung during boot. I turned it off and tried again. Again it hung (at a different place) during boot. I deleted the image. Too much hassle at this point.

Monday evening: I created a VirtualBox machine hosted on my MacBook Pro. Pretty much the same configuration as I had on the other one hosted in Windows 7: 50GB hard drive with about 2.5GB of memory. It installed perfectly the first time and so far has worked flawlessly. (Well, other than the weirdnesses of a touch based interface driven by a keyboard/mouse.)


2. This is not intended to be a tutorial. There are already good tutorials to install onto a hard drive and into a virtual machine available.

Thursday, July 14, 2011

LINQ and set notation

So I learned something today.

It's been a long time since I had any classes dealing with sets. I vaguely remember discussions including Venn diagrams and odd notation that didn't have any relevance to any other context that I was familiar with, but they were also pretty cool to study and get to know. However, they're the types of things that have a highly technical, mathematically rigorous side to them and also the day-to-day intuitive side that I use. Not needing it on a regular basis, the finer points of set algebra quickly sink into the background and aren't easily recalled.

Intersection
Today I needed to do some set manipulation. I knew LINQ had some set related methods in it, such as Intersect which gives only the items that are in both lists.

Union
And I knew it had the Union that gives all the items in both lists, without duplicates.

Needing to find the differences between two lists, I suspected there was something to do that easily. I had two string lists and needed the items from both lists that were only in one of the two lists. In other words, I needed the inverse of Intersect. First I looked at the options in the code completion list. Nothing jumped out at me. I couldn't recall the technical name so I did a web search for "LINQ intersect inverse" and found the Except method. The description sounded promising but, when I tried it, I didn't get what I expected. It only gave the things that were in the first list but not in the second list. In other words, it did not include the things in the second list that weren't in the first. Figuring the people who wrote these methods probably knew something about what they were doing, I went digging a little deeper.

The next web search was for "set intersect inverse" that led me to a Wikipedia page on set intersection. Scrolling to the bottom "see also" section, I saw Complement. Ah-ha! That rang a bell from the distant past. Clicking on that link confirmed that Complement was in fact the difference between two sets.

RelativeComplement
And this is where I started to learn something new: there are multiple types of differences in set theory. In general, the Complement refers to things not in a given set. First, there's the relative complement as implemented by LINQ's Except method. This gives the things from one list that are not in the other list. For example, if list1 = new List<string> {"a", "b", "c"} and list2 = new List<string>{"b", "c", "d"} then list1.Except(list2) will return "a".

AbsoluteComplement
Second, there's the absolute complement. This is the universe of all things not in a given set. Hopefully it's obvious that this can't be implemented in software.

SymmetricDifference
Finally, there is the symmetric difference. This is the name of what I needed. It's the list of things that are in only one of two given sets. Thinking in terms of set operations, it's the relative complement between the union of the sets and the intersection of the sets. In LINQ terms it's list1.Union(list2).Except(list1.Intersect(list2)). This got me what I want.

Now that I had a technical term to search on, out of curiosity I tried "symmetric difference LINQ". (It's always easier to find what you're looking for when you know the proper keywords.) This returned a link to a StackOverflow question that not only gave the answer I came up with but also pointed out there's a SymmetricExceptWith method on the HashSet class.

Curiosity now drove me to do a quick benchmark. Knowing LINQ has never been a speed demon, I assumed it probably wouldn't beat out the HashSet implementation. I threw together a quick console app that simply ran both the above LINQ query and HashSet.SymmetricExceptWith call on two short lists a million times and reported the elapsed times. I used three different types of input containers to see if that made much difference. Here's what I found...
Input typeUsing LINQUsing HashSet.SymmetricExceptWith
List<string>2.8 s1.0 s
LinkedList<string>2.9 s1.1 s
HashSet<string>2.7 s0.8 s