May, 2008

  • Kirill Osenkov

    Testing

    • 10 Comments

    If you're interested in testing or would like to learn more about it, here are a couple of links:

    • MSDN recently announced Tester Center: http://msdn.com/testercenter - this is a centralized resource about testing from Microsoft. Quote:
      "The Microsoft Tester Center showcases the test discipline as an integral part of the application lifecycle, describes test roles and responsibilities, and promotes the test investments required to deliver high-quality software."
    • Our QA team has a blog about testing called CSharpening: http://blogs.msdn.com/csharpening/ Unfortunately, the content there is not being updated very frequently, because we're busy testing the Visual Studio 2008 SP1 and the first new features of Visual Studio "10". Yours truly intends to post testing-related articles there.

    Some common facts about my job as a tester at Microsoft (to clarify some common misconceptions):

    • Officially my position is called SDET - Software Design Engineer in Test.
    • We develop all of our test code using most recent builds of Visual Studio "10" and C# 4.0.
    • We do almost no manual testing - almost all of our tests are automated, which means they can run on a lab machine unattended.
    • We run our tests on a variety of operating systems, languages and VS SKUs (e.g. Visual C# Express 2008 on Japanese Vista or VSTS on Windows Server 2008 with Visual Studio 2005 already installed side-by-side).
    • The Visual Studio Managed Languages Team has about 30000 functional C# and VB tests which run overnight for about 12 hours on 5 to 10 lab machines (paralleled).
    • C# tests are written in C#, VB tests are written in VB, F# tests are written in F#.
    • We have a lot of automated UI tests - where mouse moves automatically and keyboard "types" on its own - its fun to sit and watch a test creating a C# project, opening files, typing, using refactorings, navigating, etc.
    • We prefer testing on the component level, bypassing the UI.
    • Our developers write unit-tests, while we concentrate on the functional testing and end-to-end scenarios.
    • We reach more than 70% code coverage with our tests - this is a required minimum for our team.
    • We use TFS (Team Foundation Server) for source control and work item tracking.
    • Many of our tests use a new data-driven test framework where our test scripts are written in XML and are interpreted by a script-like engine.
    • Most of Visual Studio tests are out-of-process - our tests attach to a Visual Studio process and control it using Remoting.
    • We have a "bug-bash" day about once a month where the entire team just uses Visual Studio and logs bugs.
    • We also have AppWeeks, where we form groups and build applications using our product.

    Please let me know if you'd like to know more. Thanks!

  • Kirill Osenkov

    Algorithms in C#: Connected Component Labeling

    • 11 Comments

    I have to admit, I'm not very good at interviews. For some reason my mind isn't trained well for sorting linked lists or balancing binary trees on the whiteboard. I have no problem designing 600+ type hierarchies and building complex object-oriented frameworks, but typical interview questions were never an area where I was shining. Maybe it's because I like to think slowly and take my time, maybe for some other reasons :) Anyway, just out of the blue I decided to implement an algorithm in C# with the goal to improve my algorithm skills and to enjoy the power and expressiveness of my most favorite language and platform.

    As it usually goes, I first sat down and spent three hours coding the whole thing, and after that I did some online research, which revealed the algorithms official name:

    Connected component labeling

    The goal is, given a 2D-matrix of colors, to find all adjacent areas of the same color, similar to the flood-fill algorithm used in Paint.

    Standard (existing) solution - Union-Find

    Online research had revealed that there is a standard algorithm for this that heavily employs Union-Find. The union-find approach starts with a disjoint matrix, where every element is its own set and then iteratively joins (unions) neighboring sets together. The secret of Union-Find is twofold:

    • Extremely fast (constant-time) union of two sets
    • Extremely fast (almost constant-time) determining whether two points belong to the same set or not

    I remember when I was at the university, I even knew how to prove that the complexity of Union-Find is bounded by the inverse Ackermann function, which, believe me, grows very slowly. The important thing that I carried out for the future is that for all practical purposes you can safely consider this O(1).

    My solution

    I was somewhat proud to have implemented a different approach. If you have seen this anywhere before, I wouldn't be surprised though, so please bear with me. The idea is to split the "image" into horizontal stripes ("spans") of the same color. Then scan all the rows of the image row-by-row, top-to-bottom, and for each row, for each span in a row, attach the span to the neighbor spans of the previous row. If you're "touching" more than one existing component, join them into one. If you're not touching any pixels of the same color, create a new component. This way, we split all horizontal spans into three generations: 0, 1 and 2 (like the .NET Garbage Collector!). Generation 0 is the current row, Generation 1 is the row above it, and Generation 2 are all the rows above these two. As we finish processing a row, Generation 1 is added to Generation 2 and Generation 0 becomes Generation 1.

    MSDN Code Gallery

    I published the source code at http://code.msdn.microsoft.com/ConnectedComponents. MSDN Code Gallery is an awesome new website where you can publish your code samples and source code. I discovered that I'm not the only one to publish algorithms in C#: see for example, A* path finding.

    Performance challenge

    I'd be very curious to measure the performance of my current code. I know it isn't optimal because there is at least one place where I can do considerably better. For the profiling wizards among you, I won't reveal where it is for now. For the tuning wizards, if my algorithm takes 100% time, how many percent can you get? I myself expect (but not guarantee) to be around 5-10% faster. Can anyone do better?

    Also, I'd be curious how my algorithm performs compared to the classical union-find implementation. Anyone interested to implement and see if it does better? (I hope I won't regret posting this when someone shares an implementation which is 100 times faster than mine...)

    Cleaner code challenge

    I dare to hope that my code is more or less clean and more or less well-factored. However I learned one lesson in life - whenever I start thinking that I'm good, life immediately proves otherwise. That's why I welcome any improvement suggestions. I understand that on such Mickey Mouse-size projects it doesn't really matter that much if the code is clean or not, but anyway. The design could be better, the use of .NET and C# could be better, the distribution of responsibilities could be better, my OOP kung-fu could be better. I'd like to use little projects like this to learn to code better.

    Language challenge

    Care to implement it in F# or, say, Nemerle? This is your chance to show the world that C# is not the only .NET language! Of course, non-.NET languages are highly welcome as well. I'd personally be interested in, for example, Haskell, Lisp, Prolog, Scala, Nemerle, Boo, (Iron)Ruby, (Iron)Python, Smalltalk, Comega, SpecSharp, SML.NET and so on.

    Silverlight challenge

    Have you installed Silverlight 2 beta? Need an idea what to implement? ;-)

  • Kirill Osenkov

    How to determine the .NET installation directory and CLR version

    • 0 Comments

    I recently discovered the System.Runtime.InteropServices.RuntimeEnvironment class, especially RuntimeEnvironment.GetRuntimeDirectory().

    Also, RuntimeEnvironment.GetSystemVersion() gets the version of the CLR that is running the current process.

  • Kirill Osenkov

    How to map a Visual Studio macro to a keyboard shortcut?

    • 3 Comments

    The complete answer is here: http://msdn.microsoft.com/en-us/library/a0003t62.aspx

    Excerpt:

    1. Choose Options on the Tools menu to display the Options dialog box.
    2. In the Environment folder, click Keyboard.
    3. In the Show commands containing box, type "macros." Once you do this, all commands beginning with the word "macros" appear in the commands list.
    4. Scroll down the list to your macro.
    5. Click the Press shortcut key(s) box type a key combination, such as CTRL+SHIFT+ALT+A. This will be the keyboard shortcut that executes the macro. You can use a different key sequence if you prefer.
    6. Click Assign and then click OK. Your macro is now bound to that keyboard shortcut.
    kick it on DotNetKicks.com
Page 1 of 1 (4 items)