V8 JavaScript virtual machine compiled

The most interesting part of Google Chrome browser in my apinent it's the new JavaScript virtual machine V8, it's will change the world of the web development the same way server and thick client development was changed by Java and CLR. Now every web developer can build very fast application for a browser.

If you want to explore and learn more here is V8 Virtual machine open source project, you can get source code for this virtual machine , compile it and embed it into your own application. Nice !!

I also made a V8 precompiled package for windows that you can check out if you don't want to setup the build envirement by you self :)

The google chrome is out
http://www.google.com/chrome/index.html?hl=en&brand=CHMG&utm_source=en-hpp&utm_medium=hpp&utm_campaign=en

Our http://lastminutetrave.com site was newer looking beter that in Chrome , it's fantastic.

Fast sets intersect detection in C#

While developing our latest version I encountered a scenario with i think general enough to be interesting for general public. I had two arrays of integers and was needed to find if they overlaps , meaning they intersect is not empty set :). Or in plain English what one array has members what also members of the other array. This operation is going to be performed a couple of millions of times every run of a program so I wanted it to be as fast as possible.

The "Naive" approach for this problem is to just run 2 loops where you take each of the elements of a first array and check it against element of a second array.

bool NaiveIntersect(List<int> setOne, List<int> setTwo)
{      
   for(int i1=0;i1<setOne.Count;i1++)
   {
       for(int i2=0;i2<setTwo.Count;i2++)
       {
           if (setTwo[i2]==setOne[i1])
           {      
               return  true;  
           }
       }  
   }

   return false;
}

Obviously this is a not optimal solution with complexity of O(n*m) .NET framework provide number of build in classes what give ability to test overlap of two arrays.

The list I came up with:

• LINQ intersect extension method
• Hashset collection
• BitArray collection

LINQ don't have Overlap method but it do have Intersect method , so we need just to intersect the two sets and see if intersect is not empty set.

bool LinqOverlap(List<int> setOne, List<int> setTwo)
{
 return setOne.Intersect(setTwo).Any();
}

HashSet it's a hashing data structure similar to HashTable or Dictionary collection, the main difference is what HashSet don't have key and values it has only values ,and hash is performed on them. In hash set you to find an element you just need to compute the hash of this element and get it from appropriate it's much faster that to iterate over a collection. HashSet collection provides a convenient Overlaps method to test this exact scenario so code is very short and obvious.

bool HashSetIntersect(HashSet<int> set1, HashSet<int> set2)
{
   return set1.Overlaps(set2);
}

Another interesting collection is BitArray , underling data structure of BitArray is simple array of integers. The main strange of BitArray is in ability to perform bit operations across two arrays of number, so in our case overlap method will look like this. We perform bitwise AND operation and check if one of the bits in the intersect is set to true.

bool BitArrayOverlap(BitArray set1, BitArray set2)
{
   var intersect=set1.And(set2);

   for(int j=0;j<intersect.Length;j++)
   {
       if(intersect[j])
           return true;
   }

   return false;
}

I took the code above and run it on 2 arrays of integers containing 125 elements each for 100,000 times. So lets se who is the winner

NaiveDoubleLoop - 7995
Linq- 1915
HashSet Overlap - 688
BitArray - 38

As you can see from the table the obvious winner is a BitArray. And it's true for a general case , but in some special case we can get much better performance , lets talk about one more method , it's an optimization of a BitArray method. It suited for cases where sets of integers we going to test for overlap can contain only values we will know in advance and the list of this values is small (couple of hundreds). If we have only 64 possible values we can just assign a bit mask for each of the possible integers values in our sets so a set will be represented by a single long value and testing for overlap is just a binary AND between 2 longs. If we have more that 64 possible values it's possible to extend this method by giving each value in addition to bit mask another parameter that will tell us for what group it belongs so our sets will be a short array of long and we will need to perform AND operation on each pair of values in this arrays.

Here is the code that shows the implementation

bool BinaryOverlap(long[] setOne, long[] setTwo)
{  
 return
  ((setOne[0] & setTwo[0])
  (setOne[1] & setTwo[1])
  (setOne[2] & setTwo[2])) != 0 ;                          
}

So what about performance you say ? For 192 values it's performs 100,000 overlap tests in 1 ms. This approach will not fit every scenario , we can't always control the integers that come to us but if we can it will give us blazingly fast performance.

Why I loving JS ?

JS makes every project an open source project. For example what would you do if you VP of R&D came to you and says , "QA found out what one of MS products you used in development of latest version of you project don't work correctly for 15% of you customers, please fix it" ?

And it's less that one month till release ? And price tag of this version is in 6 to 7 figures area ? Pretty scary if we talking about a C++ dll in mids of .NET framework. But in our case it's just a minor problem.

But let's move closer to the problem. We using a MS virtual earth services for our mapping needs (great service by the way superior to Google maps in many aspects) and as you all of you know recently a Firefox had a new version 3.0 so during QA we noticed what moving a map by mouse in fire fox causes it to jump uncontrollably.

By examining the behavior it was apparent what in FF3 virtual earth incorrectly calculates mouse position relative to page scroll position. I understood the problem but now I need to find this issue and fix it. How do you do it when all you have it's 800kb (200kb gzipped) of minified JS to look at and it's hosted on external server so you can't modify it?

So first of all I wanted to turn the minified JS into normal JS , http://www.prettyprinter.de/

to the rescue. So I got nice looking script I made a search for scrollposition and found following interesting class with a couple of methods.

Gimme.Screen=new function()
{
    this.getMousePosition=function(a)
    {
        if(!a)
           a=window.event;
        var b= {x:0,y:0};
        if(typeof a.pageX!=="undefined"&&typeof a.x!=="undefined")
        {
            b.x=a.pageX;
            b.y=a.pageY
        }
        else
        {
            var c=this.getScrollPosition();
            b.x=a.clientX+c.x;
            b.y=a.clientY+c.y
        }
        return b
    };

    this.getScrollPosition=function()
    {
        var a = {x:0,y:0};
        if(typeof window.pageYOffset!=="undefined")
        {
            a.x=window.pageXOffset;
            a.y=window.pageYOffset
        }
        else if(typeof document.documentElement.scrollTop!=="undefined")
        {
            a.x=document.documentElement.scrollLeft;
            a.y=document.documentElement.scrollTop
        }
        else if(typeof document.body.scrollTop!=="undefined")
        {
            a.x=document.body.scrollLeft;
            a.y=document.body.scrollTop
        }
        return a
    }
}

From looking at it I saw 2 things

First of all scroll position is calculated correctly but used only for browser what don't support pageX, pageY parameters. I wanted to try and see what happen if I make FF to use this path.
How do you do it if you can't modify script ? Easily because JS is a dynamic language you can modify any object/method at runtime. So I just gave a new implementation for the getMousePosition method by inserting the code bellow into my page.

Gimme.Screen.getMousePosition=function(a)
{
    if(!a)
        a=window.event;
    var b= {x:0,y:0};
    var c=this.getScrollPosition();
    b.x=a.clientX+c.x;
    b.y=a.clientY+c.y
    return b
};

I hit save , reloaded the page and looks like it's works. Issue solved and I can go home :)

For Yonatan

My work room-mate Yonatan will be happy to know what his open source project is actually
used by people outside of our company.
http://www.develop-one.net/blog/2007/11/09/TFSHistoryAcrossBranches.aspx

I suggest for everybody using Team System to try this utility.
It's allows seeing check in history across branches in the team system.

ASP.NET AJAX Extensions

In latest version our system we had 2 pilot projects that where developed using MS Ajax library. Overall project where a success, library can substantially decrease development
time for AJAX applications. But we also encounter number of problems and issues.

I like to list these issues for the general public use :).

ASP.NET AJAX Toolkit

Toolkit is set of additional controls what based on the AJAX extensions library, and was released by MS as open source project.
During development we noticed that controls in this toolkit where not tested as well as core components of AJAX extensions.
We encounter number of issues related to performance then toolkit controls where used inside large repeaters
and we saw functionality bugs in some of the controls.

I recommend using these controls with caution, and double check application performance and behavior during development.
Most of the times we saw what it's better to use our own solutions instead of controls from the toolkit.

Performance

Update panel is not optimal implementation of AJAX from performance perspective; it was developed on top of regular post back model of the ASP.NET
So this causes for information that is usually transferred during post backs to be transferred during async requests as well.
This includes values of all form inputs as well as view state. This additional data causes request to be very bloated even for most simple things

In addition on the server side full page life cycle will be performed.

So from performance point of view:

It's better to make more things on client by using JavaScript instead of making async post back to the server.
Better to use Ajax web services instead of Update Panels, this will post only data that you explicitly wanted to send.
If you using Update Panels try to minimize amount of view state on the page.


Session/ Authentication Time Outs

Another issue with AJAX development, you need to be aware is timeouts in session and authentication.
If user make a regular post back in ASP.NET application and his authentication is timed out he will be redirected to the login page.
It's great but if it's happens inside of asynchronous requests this behavior will cause error on the main page instead of appearance of a login page.
Additional code is needed on client/server to handle such scenarios.

Please be aware of this issue during development and testing.

Usability consideration

When user performs action using regular post backs, he always gets a feedback in the form of flashing status bar
and other visual effects build in the browser, on the other hand Ajax request by default are invisible so it's not clear if something is working
correctly or not when action is performed.

So if request is long we need to give user visual feedback for example in form of "waiting" popup.
AJAX extension provide special Update Progress control to make development of such pop ups simple.


Debugging

If you encounter mysterious problem, instead of making a lot of guesses start investigation is by running Fiddler and look into requests and responses.
It will remove a lot of mystery from the problem :). Another very good tool is Firebug extension for Firebox.
It has a lot of useful tools including performance profiler for JS, very informative debugger, DOM browser and others.

Error handling

AJAX extensions provide facilities to handle errors that came from async requests; you can use them to show friendly messages to the user instead of red exception screens