Hierarchical Data Models: Adjacency List Model

In all the possible models of hierarchical data representation, the Adjacency List Model is perhaps the most favoured one among the software developers - for its sheer straight-forwardness and easy implementation. The name Adjacency List is borrowed from the Graph Theory. In its simplest form, each piece of data holds enough information about its parent. Imagine a child's passport wherein her father's name is written. Similarly, in the father's passport, his father's (i.e. the child's grandfather's) name is written. By looking at the girl's passport, we can't determine the grandfather's name without also referring to her father's passport. Please also note, in this case, that this journey is always way up - you can't look at the father's passport and determine his daughter's name.

Let us now play with some real database stuff. The example that we are going to present is that of the list of categories of products sold by a given Departmental Store. The following diagram shows the hierarchy in a tree form:

The top-most node, Product Categories is the root node - it doesn't have any parent. While this example shows one root node, in reality it is possible to have more than one root node, though it is best avoided when designing your data model.

The root node has three children, Consumer Electronics, Computers and Peripherals and Cameras. Each of these children in return, has more than one child, some of which has children one level down the hierarchy. I chose these specifically to show that a hierarchical list need not be a balanced - some branch of the tree can go n-level deep and some may be fewer than that.

This hierarchical information can be very well represented in Xml, as one of the strengths of Xml is to be able to represent hierarchical information at ease. Let's have a look:

<Category CategoryName="Product Categories">
   <Category CategoryName="Consumer Electronics">
      <Category CategoryName="Electronic Gadgets"/>
      <Category CategoryName="Home Appliances"/>
     <Category CategoryName="Office Electronics"/>
   </Category>
   <Category CategoryName="Computers & Peripherals"/>
   <Category CategoryName="Cameras">
      <Category CategoryName="Digital Compact Cameras"/>
      <Category CategoryName="Digital SLR Cameras" />
   </Category>
</Category>

I am just showing the first three levels of the hierarchy in the above xml. Looking at either the diagram or the xml above, you shouldn't have any problem in figuring out what is the grandparent of Digital SLR Cameras.  This xml can of course be extended to include all the levels.

So far so good. The problems start pouring in when we want to represent the same data in a tabular form in SQL Server and most other commonly used RDBMs. The idea borrowed from Adjacency List model comes into rescue at this point. Consider the following diagram:

We have assigned unique numbers to each and every category node to uniquely identify them. Let's call these numbers CategoryId and these would be our primary keys. Now for each node, we have one more attribute called ParentCategoryId and the above diagram shows how we can derive the values for this attribute for each of the nodes. Essentially, we are looking at the tree diagram above, identifying the parent of a given node, and using the CategoryId of the parent node as the ParentCategoryId of the current node. Note that the left-most table doesn't have any ParentCategoryId as that contains the root node and root nodes do not have any parents. A bit of thinking leads us to normalize the above tables into one single table as shown below:

Each row in this table contains three pieces of information: name of the category, the unique id of the category, and the category id of the parent of the current category. With this clarity of understanding, it's time to cook up some SQL scripts to create our table in SQL Server and fill in the values.

--create table first
CREATE TABLE Category( 
   [CategoryId] [int] NOT NULL PRIMARY KEY, 
   [CategoryName] [nvarchar](100) NOT NULL, 
   [ParentCategoryId] [int] NULL ) 
   ON [PRIMARY]
GO
        
-- Insert data for the root level
INSERT INTO Category (CategoryId, CategoryName, ParentCategoryId) VALUES( 0, 'Product Categories', NULL)
INSERT INTO Category (CategoryId, CategoryName, ParentCategoryId) VALUES( 1, 'Consumer Electronics', 0)
INSERT INTO Category (CategoryId, CategoryName, ParentCategoryId) VALUES( 2, 'Computers & Peripherals', 0) 
INSERT INTO Category (CategoryId, CategoryName, ParentCategoryId) VALUES( 3, 'Cameras', 0) 
        
-- Insert data for the intermediate (Level 1)
INSERT INTO Category (CategoryId, CategoryName, ParentCategoryId) VALUES( 4, 'Electronic Gadgets', 1)
INSERT INTO Category (CategoryId, CategoryName, ParentCategoryId) VALUES( 5, 'Home Appliances', 1)
INSERT INTO Category (CategoryId, CategoryName, ParentCategoryId) VALUES( 6, 'Office Electronics', 1)
INSERT INTO Category (CategoryId, CategoryName, ParentCategoryId) VALUES( 11, 'Digital Compact Cameras', 3)
INSERT INTO Category (CategoryId, CategoryName, ParentCategoryId) VALUES( 12, 'Digital SLR Cameras', 3)
        
-- Insert data for the leaf level
INSERT INTO Category (CategoryId, CategoryName, ParentCategoryId) VALUES( 7, 'Desktop PCs', 2)
INSERT INTO Category (CategoryId, CategoryName, ParentCategoryId) VALUES( 8, 'Laptops', 2)
INSERT INTO Category (CategoryId, CategoryName, ParentCategoryId) VALUES( 9, 'Printers', 2)
INSERT INTO Category (CategoryId, CategoryName, ParentCategoryId) VALUES( 10, 'Scanners', 2)
INSERT INTO Category (CategoryId, CategoryName, ParentCategoryId) VALUES( 13, '5-6 Megapixels', 11) 
INSERT INTO Category (CategoryId, CategoryName, ParentCategoryId) VALUES( 14, '6-7 Megapixels', 11)
INSERT INTO Category (CategoryId, CategoryName, ParentCategoryId) VALUES( 15, '7-8 Megapixels', 11)
INSERT INTO Category (CategoryId, CategoryName, ParentCategoryId) VALUES( 16, 'Brand XXX SLR Cameras', 11)
INSERT INTO Category (CategoryId, CategoryName, ParentCategoryId) VALUES( 17, 'Brand YYY SLR Cameras', 11)
INSERT INTO Category (CategoryId, CategoryName, ParentCategoryId) VALUES( 18, 'GPS and Navigation', 4)
INSERT INTO Category (CategoryId, CategoryName, ParentCategoryId) VALUES( 19, 'Voice Recorders', 4)
INSERT INTO Category (CategoryId, CategoryName, ParentCategoryId) VALUES( 20, 'Electronic Shavers', 4)
INSERT INTO Category (CategoryId, CategoryName, ParentCategoryId) VALUES( 21, 'DVD Players', 4)
INSERT INTO Category (CategoryId, CategoryName, ParentCategoryId) VALUES( 22, 'MP3 Players', 4)
INSERT INTO Category (CategoryId, CategoryName, ParentCategoryId) VALUES( 23, 'Air Conditioners', 5)
INSERT INTO Category (CategoryId, CategoryName, ParentCategoryId) VALUES( 24, 'Food Processors', 5)
INSERT INTO Category (CategoryId, CategoryName, ParentCategoryId) VALUES( 25, 'Microwaves', 5)
INSERT INTO Category (CategoryId, CategoryName, ParentCategoryId) VALUES( 26, 'Vacuum Cleaners', 5)
INSERT INTO Category (CategoryId, CategoryName, ParentCategoryId) VALUES( 27, 'Calculators', 6)
INSERT INTO Category (CategoryId, CategoryName, ParentCategoryId) VALUES( 28, 'Currency Machines', 6)
INSERT INTO Category (CategoryId, CategoryName, ParentCategoryId) VALUES( 29, 'Paper Shredders', 6)

Run a SELECT query to see how the entire table looks now.

Data thus stored is no good unless we can extract meaningful information out of them. The query to find out all the root nodes (in our case there is only one):

SELECT * FROM Category WHERE ParentCategoryId IS NULL

And the result is:

The query to find out all leaf nodes - the nodes that don't have any children:

SELECT  C1.CategoryId, 
        C1.CategoryName 
FROM    Category C1
LEFT JOIN Category C2 
        ON C1.CategoryId = C2.ParentCategoryId WHERE C2.CategoryId IS NULL

We get all the categories which do not have any children:

As you can see from the query, we have achieved our desired result through what is called as an "Self-Join": the query outer-joins the ParentCategoryId to the CategoryId of the same table and ensures that no ParentCategoryId (through IS NULL check) exists which points to the current CategoryId. Now let's see how we can retrieve a single path for any chosen leaf:

SELECT  C1.CategoryName AS Level1, 
        C2.CategoryName as Level2, 
        C3.CategoryName as Level3, 
        C4.CategoryName as Level4 
FROM Category C1 
LEFT JOIN Category C2 ON C2.ParentCategoryId = C1.CategoryId 
LEFT JOIN Category C3 ON C3.ParentCategoryId = C2.CategoryId 
LEFT JOIN Category C4 ON C4.ParentCategoryId = C3.CategoryId 
WHERE C4.CategoryName = 'MP3 Players'

This produces the result:

The complexity starts here. To reconstruct each single path, we need to know the depth of the node and our query is hard-coded for that level of depth. This indeed is annoying. At the time of design and coding, we may not know the actual hierarchy of product categories that are in use in a given departmental store. Hard-coding SQL in such way actually limits the flexibility of the application. The solution lies in a technique recursion. Back in SQL Server 2000, we would be writing recursive functions and stored procedures to achieve the feat. SQL Server 2005 provides new feature called Common Table Expressions which is just the tool we needed at this juncture. Without going into further details how Common Table Expressions work, as you may always refer to myriads of web-articles on that, let's straight plunge into SQL:

WITH CTE AS ( 
     SELECT  CAST('/' + C1.CategoryName AS NVARCHAR(2000)) AS FullPath,  
             CategoryId  
     FROM    Category C1 
     WHERE   C1.ParentCategoryId IS NULL
                
     UNION ALL 
                
     SELECT  CAST(CTE.FullPath + '/' + C1.CategoryName AS NVARCHAR(2000)), 
             C1.CategoryId 
     FROM    Category C1 
     JOIN    CTE ON C1.ParentCategoryId = CTE.CategoryId
) 
        
SELECT  CTE.FullPath + '/' + C1.CategoryName 
FROM    CTE JOIN Category C1 ON CTE.CategoryId = C1.ParentCategoryId 
ORDER BY 1

The result from this query a proper bread-crumb path for each and every node, not just the child nodes:

To retrieve the data in the above xml format, a bit of work is needed. We will first write a recursive scalar function, and then we fire the function from a SELECT query:

--recurive function to walk through the hierarchy
CREATE FUNCTION dbo.fnCategoryTree(@CategoryId int)
RETURNS XML
BEGIN
    RETURN 
         (SELECT CategoryId AS "@CategoryId", 
                 CategoryName AS "@CategoryName", 
                 ParentCategoryId AS "@ParentCategoryId", 
                 CASE 
                      WHEN ParentCategoryId = @CategoryId THEN dbo.fnCategoryTree(CategoryId) 
                 END 
          FROM   Category 
          WHERE  ParentCategoryId = @CategoryId 
          FOR     XML PATH('Category'), TYPE ) 
END 
        
--retrieve xml data
SELECT  CategoryId AS "@CategoryId", 
        CategoryName AS "@CategoryName", 
        CASE 
             WHEN CategoryId = 0 THEN dbo.fnCategoryTree(CategoryId) 
        END 
FROM Category 
WHERE CategoryId = 0 
FOR XML PATH('Category'), TYPE

DML operations in Adjacency List Model

This model is extremely programmer-friendly when it comes to INSERT, UPDATE and DELETE operations.  The model itself doesn't render any constraint over such operations. Inserting data can simply mean adding one more row at the bottom of the list, with the ParentCategoryId pointing to one existing CategoryId anywhere in the table. The statement can be as simple as:

INSERT INTO Category (CategoryId, CategoryName, ParentCategoryId) VALUES( 30, 'UPS', 2)

Of course the statement would have been a bit simpler if we had marked the CategoryId column as an IDENTITY column. Note that, just by ensuring a correct value for ParentCategoryId, you can not only create leaf nodes, but can create any node at any intermediate level. You may even convert one existing leaf node into an intermediate node by appending one lead below it.

Likewise, update operations are simple too. Assuming you are following the best practice of not modifying the primary key (CategoryId), updating a row merely involves either changing the Category Name of a given node or changing its parent. While changing the node name has no impact on the tree structure, changing the parent changes the physical structure of the tree. In fact, such is the power of the Adjacency List model that you can actually uproot a branch from one position of the tree and graft it below some other branch!

For example, let's try move the entire "Camera" branch, which is directly under the root, under the "Consumer Electronics" node. To achieve this, all we need to do is to change the parent of the "Camera" node from 0 (CategoryId of "Product Categories" node) to 1 (CategoryId of "Consumer Electronics") with this simple SQL:

UPDATE  Category 
SET     ParentCategoryId = 1 
WHERE   CategoryId = 3 -- 3 is the CategoryId of the Camera node

DELETE operations, however, are not as easy. You just cannot delete any intermediate node as that would make the entire children and descendants orphan! Ideally, you should move the descendants first under some other parent (as shown above) before removing a parent.

Improving Adjacency Model

The Adjacency Model we examined so far may be criticized for several drawbacks. For example:

• It is possible to have a child with a phantom parent (i.e. a ParentCategoryId which doesn't exist)
• It is possible to make a child its own parent (ParentCategoryId and the CategoryId being same)
• As mentioned above, you can have a whole branch dangling (without a parent)
• Because the ParentCategoryId column is NULLable, it allows you to have more than one root.

The above table design follows the Adjacency List model, but there is nothing that can stop us from deviating from that as long as we fulfil the requirement of creating a data model capable enough for representing hierarchical data. One immediate thought coming to my mind is to split the ParentCategoryId column to some other table (along with the necessary CategoryId information). Once we do that, we need to set up couple of constraints (Foreign Key, Check etc) to overcome the above problems. I'll leave it you as an exercise:)

Hierarchical Data in SQL Server

What is Hierarchical Data?

Let's try and understand the concept of Hierarchical Data first. Very simply put, when data is organized in a tree like structure it is called hierarchical data. The hierarchical data structure works in a parent/child relationship where each parent can have multiple child whilst a child can have only one parent. Examples are umpteen in the real world. One of the most commonly stated examples is one that of organization hierarchies in a company, where the senior-subordinate relationship is often shown visually in a tree like structure called organization chart.

Just like a family tree, you have the option to call Test Lead an ancestor (or parent) of Tester, and conversely, you may call a Tester a descendant (or child) of the Test Lead. Each such data structure has one top level parent node, often called root node. The root node doesn’t have any parent but it may have one or more children. Each of the intermediate child nodes may have zero or more children, thus they may become parent nodes to its children. At the Leaf level, the nodes do not have any children. Other than the facts that root node doesn’t have a parent node and the leaf nodes do not have child nodes, all the nodes are functionally same, especially when we say that no node can exist in isolation. Well, in some out-of-the-world scenario, we can actually have a root node without any children, but I would hate to call it a tree – a seed would perhaps be a better choice!

Nested Set Model

As I was going to St Ives
I met a man with seven wives
Each wife had seven sacks
Each sack had seven cats
Each cat had seven kits
Kits, cats, sacks, wives
How many were going to St Ives?

No prizes for guessing the answer! Anyone with the mathematical knowledge of Standard III and with a bit of patience can come up with the correct answer in the first try (Not really! There is more to it than some mere calculations. And the whole thing dates back to thousands of years ago. That's a story I'll cover in some other blog - promise!).

This rhyme is considered to be created or gained popularity around 1730 in England. Even though there are more than one place called St. Ives in England, the one mentioned in the rhyme could most probably be St. Ives, Oxfordshire, as this place grew as a prominent market place in the last 1000 years of its history and therefore it makes sense that several people or groups go to that same place in the same day.

Back to the problem. If you try a little, you wouldn't have any problem creating organisation charts like above for this rhyme. You may make the "a man" as the root node, followed by seven intermediate nodes (wives), each wife-node having seven child nodes (sacks) and so on. However, it is also possible to represent the situation in terms of Set Theory. Instead of going into too much of jargons as I find them too much antediluvian way of making a point, let's try and draw a Venn diagram:

In the above nested set representation, the man contains seven wives, each wife contains seven sacks, each sack contains seven cats etc. I didn't draw the whole of the solution because I didn't want to give away the answer :) If you look at it closely, you will notice that either way you look at it (organization chart or nested set diagram), the data itself is hierarchical in nature with that 0-to-Many concept - a parent may have zero or more child and a child must have one and only one parent. Thinking in these lines, you will find that such hierarchical data abounds in our daily life: catalogues in book or movie libraries, departments in an organization, product categories in a departmental store and almost every other taxonomical entities.

Now that we made some progress in understanding what Hierarchical Data is, in my next posts I will discuss different ways of implementing such data structure in databases and how each one fares against the other. Adieu.

Games people play : 3

Strategy for a Tic-Tac-Toe

At first I thought that I'd explain the strategy in detail but then I thought that 99% of the readers would already know that. For the rest 1%, I'd humbly tell them to google it and they can find many such articles. The game is very simple in the sense that because of its limted moves (only 9 moves), the various combinations for a winning strategy can be easily chalked out. As long as you are playing intelligently, which means that not only you're concentrating on your current move but also on the possible future moves your opponent may play, you can never lose a game. Similarly, the opponent will never lose a game if he knows the game properly and plays it with sufficient intelligence. With two such intelligent players, a game of Tic-Tac-Toe will always result in a draw.

Tic-Tac-Toe problem

Therefore, rather than elaborating on the game and its strategy, let's venture into the world of a puzzle and then we will see how we can use our knowledge of game strategy in solving the puzzle.

Consider the following diagram:

Assume that two intelligent players, both of whom are aware of the game strategies, were playing this game. As is seen from the board, they played up to the sixth move and after that, both of them went out to the garden for a smoke. You enter the room at this time. Looking at the board, can you tell what was the first move in the game? Who played last and what was the last move. In short, can you trace back each moves of the game?

Puzzling? Well...that's the idea :) But because all things are difficult before they are easy, let's try our retrograde logic.

For the sake of convenience, I have watermarked each square with a number.

• Can it be X's move now? If it were so, X will win by acquiring X4. O, being sufficiently intelligent, wouldn't allow that. So, this is not X's move now - it's O's move and X played last..
• There are 3 Xs and 3 Os on the board. We have also proved that X played last. Therefore, we can conclude that O must have played first when the game started.
• O's starting move could have been O2, O3 or O9. From the Game Strategy, we know that X must have played X5 to block the centre had O started with O3 or O9. As the centre square is blank, we conclude that X didn't feel threatened and blocked the centre, which means, O didn't play O3 or O9 and therefore, O played O2. Therefore, the first move of the game was O2.
• dih-dah-dah-dah-dih-dih....What? Surprised? Don't worry...just wanted to find out if you are still reading or not :)
• After O started the game with O2, the following sequences could have led the game to the current position (remember, we are assuming that both sides are intelligent, trying to win and ensuring that the opponent isn't winning):

Sequence 1	O2	X8
	O3	X1
	O9	X6
Sequence 2	O2	X8
	O9	X1
	O3	X6
Sequence 3	O2	X1
	O9	X8
	O3	X6

• Whichever sequence the game is played through, all we needed to know is right there - the last move was X6!!

This concludes my series on Games Theory. The whole idea was not to delve deep into the theories but inculcating enough interest in Roshni (if you don't know who she is, you haven't read my first part of the series!) so that she googles it out in her spare time.

Games people play : 2

If you have missed the first part in the series, click here to read it

Zero-Sum and non-Zero-Sum Games It all started with the concept that a player wins at the expense of other's failure. This type of game is seen more commonly at our daily walk of life and in many instances, between two players only. A game of Ludo or a game of chess can essentially be considered as a zero-sum game because at the end, one player loses (-1) and the other player wins (+1), or it results in a draw (both 0), thereby making the algebraic sum to be zero. When a couple decides to go for a vacation and gets into an argument whether to go by train (husband) or flight (wife), this ensues a zero-sum game. If they go by flight, the husband wins (+1) and the wife loses (-1). If they go by train, the husband loses (-1) and the wife wins (+1). What if they compromise and go by train and return by flight, as would be the most amicable solution? This will result in husband scoring a zero (+0.5 for onward journey, -0.5 for return journey) and the wife scoring a zero too (-0.5 for onward journey, +0.5 for return journey).

However, most of life's practical scenarios cannot be easily rendered in terms of win-lose strategies. For example, in Stock Market if I make lot of money, that wouldn't be essentially at the cost of another share-holder. In Political Science, socialist doctrines believes that a person grows richer because wealth is extracted from some other person making him poorer, hence the national economy is a zero-sum game. The capitalist doctrines, as expected, believes the other way round. To them, the economics is a non-zero sum game because human enterprise actually creates new wealth far out of proportion to any transfers or resource depletion; and voluntary transactions address the preferential desires of both parties.

Strategies

There are so many simple and complex theories about strategies in zero-sum and non-zero sum games. Of course, none of such theories try to establish any rule, which when followed, will ensure a sure win. The reasons for existence of such strategies, and in general, the subject of The Game Theory itself, is to provide a good understanding and knowledge base for identifying games in real life and how to scientifically approach the problems, given all the risk and benefit probabilities that are available during the playing the game.

For example, if a strategy S dominates a strategy T if every outcome in S is at least as good as the corresponding outcome in T, and at least one outcome in S is strictly better than the corresponding outcome in T, the strategy S is considered to be a Dominant Strategy. If player 1 follows a strategy that guarantees that he will win at least N points and player 2 follows a strategy which guarantees player 1 will win no more than N, then N is called the value of the game. The whole game then centres around this value of the game and during the lifetime of the game, different strategies are followed.

A strategy is a comprehensive contingent plan of actions. Contingent – takes into account others’ actions for example. Comprehensive – means that every possible action of the game is considered - not just those that “seem likely” but also includes those that may not be reached.

In general, the Games Theory is not at all a branch of economics or abstract mathematics but a study of our real-world, complex problems trying to explore rational approach in solving them.

In my concluding post, we will explore the game of tic-tac-toe that would be an interesting way of understanding the concepts of strategies and how this could be used for forensic analysis.

Games people play : 1

I was talking to to my friend's daughter, Roshni, or BM as I fondly call her, over the phone and somehow the topic of Games Theory came up in the context. My efforts to explain that over the phone turned out to be futile and hence this post.

Let's first start with a puzzle. Ram and Shyam are two thieves and got caught by the police. The police is separately interrogating them. They have the options to confess their crime and implicate the other thief. If none of them confesses, without having a solid evidence of their theft, will charge them falsely for carrying illegal weapons, and each one of them will be behind bars for two years each. However, if Ram confesses and implicate Shyam, Ram would be freed and Shyam would go to jail for 10 years and same option is available with Shyam. If both of them confesses, then both of them would go to jail for 5 years. Diagrammatically, we can show it like this:

		Shyam
		confesses	doesn't confess
Ram	confesses	Ram: 5 years Shyam: 5 years	Ram: 0 years Shyam: 10 years
	doesn't confess	Ram: 10 years Shyam: 0 years	Ram: 2 years Shyam: 2 years

The question is whether to confess or not so as to minimize the pay-off. If we consider both Ram and Shyam to be rational enough in logical thinking, they might think in the following line: "If I confess, then I would go scot-free and he would go to jail for 10 years. Good for me - hence I will confess." Fair enough. However, if both confess thinking in the same rational manner, both of them would go to the jail each serving 5 years. What if they take the irrational approach - that neither of them confesses. Despite the risk of other confessing, if both them actually end up NOT confessing, that gives them the best pay-off - only two years in prison for each!

This is really amusing and remarkable. Individual rational strategies in the above situation actually resulted the individuals to be in a worse situation! In the parlance of The Games Theory, the dominant strategy is to confess to achieve the most beneficial result to all the people concerned.

The whole idea is to develop a strategy to play a game so as to decide the pay-off. The game, in this context, may not necessarily be a game. The Game Theory applies to economics, social sciences etc. Let me give you one for example:

Two players play this game in a round circular board. There are smaller round pegs and each player takes a turn to place the pegs on the board. The pegs cannot overlap and a player cannot give pass. The last player to place the peg (after which there is no more space left to place a peg) wins the game. All the pegs are of same size.

The question is - can we develop a strategy to win this game? Yes - there is one simple strategy. Player 1 places her peg in the centre. After that for each peg placed by Player 2, Player 1 places is peg a diametrically opposite position. Think a while and you will know that Player 1 always wins in this strategy. Extending it further, we may conclude that (provided both the players are smart enough to devise the strategy), whoever plays first always wins!The following series of images show the first three moves.

Player 1 places her peg at the centre.

Player 2 places at her desired location

Player 1 places her peg at the diametrically opposite position

And this way, the Player 1 wins.
Enough to initiate you with some ideas of Games Theory. There's a lot more to it - which I will continue in some other post.

Why static methods are preferred?

As the books and code analysis tools like FxCop suggests us to use static methods as far as possible, unfortunately, like many other such guidance, there is hardly any explanation why it should be like that. Today while searching for something on my PC, I came across this note of mine – "Explore why static methods are preferred". While I didn't find what I was searching for in the first place (and found something else instead, thus proving one of the Murphie's Laws, QED), I was delighted to be reminded of this puzzle.

Quickly, I wrote down this small piece of program:

    class Program
    {
        static void Main(string[] args)
        {
            //call the static method
            Foo.FooStatic();
 
            //create instance of Foo
            Foo instance = new Foo();
 
            //call virtual method
            instance.FooVirtual();
 
            //call non-virtual method
            instance.FooNonVirtual();
        }
 
        //our Foo class
        internal class Foo
        {
            //static method
            public static void FooStatic()
            {
            }
 
            //virtual method
            public virtual void FooVirtual()
            {
            }
 
            //non-virtual method 
            public void FooNonVirtual()
            {
            }
        }
    }

There are three methods in the Foo class, one of them being a static method. The rest are designed to be member methods – virtual and non-virtual. After compilation, I dissected it to find out how CLR would call them. Here's the disassembly:

  IL_0000:  nop
  IL_0001:  call       void Blog20090612.Program/Foo::FooStatic()
  IL_0006:  nop
  IL_0007:  newobj     instance void Blog20090612.Program/Foo::.ctor()
  IL_000c:  stloc.0
  IL_000d:  ldloc.0
  IL_000e:  callvirt   instance void Blog20090612.Program/Foo::FooVirtual()
  IL_0013:  nop
  IL_0014:  ldloc.0
  IL_0015:  callvirt   instance void Blog20090612.Program/Foo: :FooNonVirtual()
  IL_001a:  nop
  IL_001b:  ret

We can see that for a static non-member method, the compiler uses call. One of the differences between a call and a callvirt is that the latter uses a null-check on the class instance. Makes sense. The instance must exist before you can call its method (though strictly speaking, for an object oriented compiler, this is not a must). If the instance is null, it should throw a NullReferenceException. This clearly indicates some performance degradation when calling instance methods when we are sure that the instance is not null. Hence, it is a good idea to make the methods static as far as possible even though the gain is not significantly noticeable.

As is my habit, I never leave a chance to do a what..if check on anything I learn. The question that stormed my mind is now: is there a way for us, the mortal developers, to force the compiler to use call instead of callvirt even for instance methods?

But before I do that, my curious fingers added the following line in the FooNonVirtual() method:

            //non-virtual method 
            public void FooNonVirtual()
            {
                base.ToString();
            }

And the disassembly now looks like:

  IL_0000:  nop
//000041:                 base.ToString();
  IL_0001:  ldarg.0
  IL_0002:  call       instance string [mscorlib]System.Object::ToString()
  IL_0007:  pop
//000042:             }
  IL_0008:  ret

Wo..wo..what's that? ToString() being an instance method, isn't the compiler supposed to generate a callvirt just as we learnt? Well…to think about it, that would have been a silly way. Sitting inside an instance, there is no point in checking if our base class is null or not, right? So the compiler uses call – the one that doesn't check for null instance. Fascinating!

Coming back to my idea of forcing the compiler to skip the null instance check for an instance method, I tried the following:

        static void Main(string[] args)
        {
 
            //create instance of Foo
            Foo instance = new Foo();
 
            //call instance method through instance variable
            instance.FooVirtual();
 
            //call instance method with a trick
            new Foo().FooVirtual();
        }

And the IL emitted by the compiler:

  IL_0000:  nop
  IL_0001:  newobj     instance void Blog20090612.Program/Foo::.ctor()
  IL_0006:  stloc.0
  IL_0007:  ldloc.0
  IL_0008:  callvirt   instance void Blog20090612.Program/Foo::FooNonVirtual()
  IL_000d:  nop
  IL_000e:  newobj     instance void Blog20090612.Program/Foo::.ctor()
  IL_0013:  call       instance void Blog20090612.Program/Foo::FooNonVirtual()
  IL_0018:  nop
  IL_0019:  ret

Bingo! Because a new will never return a null, the compiler now decides to use a call even for an instance method.

Just one point before I finish, this won't be applicable for virtual methods, because callvirt is essentially used for all the hard work before it locates and calls a virtual method. In other words, virtual methods can never be called using call. Or can we? Give me some more time J