War on Christmas

WCF web services and a calculator implementation in one easy snippet!

I wanted to write a calculator that supported parentheses and operator precedence for a while, but never got to sit down and do it. Recently I was poking around WCF (yes, I know I am VERY late for that party!) and wanted something less trivial than "Hello, world" to explore it. Suddenly, it felt like a reasonable opportunity to kill two birds with one stone.

Below is an implementation of a calculator web service. A problem like this is most frequently dealt with using a parse tree, and this solution is no exception. A parse tree is a binary tree representation of an expression which makes the result very easy to calculate by recursive evaluation. Our service exposes two APIs: one takes a string and returns a computed result, the other returns the parse tree for the expression for educational purposes (and to give WCF something non-trivial to marshal).

A parse tree has operators such as +, -, *, and / stored in the nodes with the children of the nodes being the operands. For example, 2 + 2 would generate the following parse tree:

                             +
                2                        2

A more complex example, 3 * 4 + 2 will result in:

                             +
                 *                       2
     3                    4

Once a parse tree is built, the evaluation is trivial: at every node, apply evaluation recursively to the children, then perform the arithmetic operator on the results. The trick here is to build it, as its construction must account for the operator precedence, parentheses, and such.

The  data structure for the node contains an operator, its two children (only would of which will be set for unary operator and in other cases), the parent, and value field used for nodes that represent values. A parenthesized subexpression lives under the separate node rooted in its right child, as illustrated below:

2 * (3 + 5) =>

           *
2                     ()
                                 +
                         3               5

The program moves alongside the expression and adds the nodes corresponding to the tokens it parses to the tree. For example, given the following expression: 2 + 2 + 2 it will:
1) Read 2, create a value node for 2, and remember it as its current node:

                        2 <=

2) Read +, create an operator node for +, set node for 2 as its left child:

                         + <=
               2

3) Read 2, create a value node for 2, and add it to the current (+) node as its right child;


                         +
               2                    2 <=


4) Read +, create an operator node for +, set node for 2 as its left child and hooking it in place of the value node under the earlier +:


                         +
               2                   + <=
                          2

5) Read 2, create a value node for 2, and add it to the current (+) node as its right child;

                         +
               2                   +
                          2                 2 <=

How does the operator precedence work in this scheme? It is encoded in the tree itself. Note that the tree for 3 * 4 + 2 must be built as follows:


                             +
                 *                       2
     3                    4

and not like this:

                 *
     3                    +
                  4                 2

The later would treat the expression as 3 * (4 + 2), which is, of course incorrect. However, this would be the tree that a naive algorithm that just reads the next token and stuffs it into a tree would build.

To account for operator precedence, before adding a new operator node, our algorithm would look at the parent nodes of its current position and if the operator at that node has a higher precedence than the operator we are about to add, it will move up the chain and hook the new node above all the higher-precedence operators, so the tree construction for 3 * 4 * 5 + 2 will proceed like this;

3<=  =>       *<=   =>       *           =>        *             =>       *              =>             +

               3                    3      4<=           3     * <=             3    *                       *        2

                                                                  4                          4   5 <=            3   *

                                                                                                                          4  5

Once this concept is clear, the rest is pure accounting (as is most of the software development :-)). The code below implements it and publishes the results through a template implementation of WCF web service, which takes on the order of 7 functional lines of code (at the very end, in the main function).

//-----------------------------------------------------------------------
//
// Copyright (C) Sergey Solyanik.
//
// This file is subject to the terms and conditions of the Microsoft Public License (MS-PL).
// See http://www.microsoft.com/opensource/licenses.mspx#Ms-PL for more details.
//
//----------------------------------------------------------------------- 
using System;
using System.ServiceModel;
using System.ServiceModel.Description;
using System.Runtime.Serialization;


namespace WCFCalc
{
    [ServiceContract]
    public interface IWCFCalc
    {
        [OperationContract]
        int Calculate(string expr);


        [OperationContract]
        ExprNode Parse(string expr);
    }


    public enum Operator
    {
        PLUS,
        MINUS,
        MUL,
        DIV,
        VAL,
        EXPR,
        OPENPAREN,
        ERROR
    }


    [DataContract]
    public class ExprNode
    {
        [DataMember]
        public ExprNode Left;
        
        [DataMember]
        public ExprNode Right;


        // This is not exported because the
        // serialization would take it as a
        // circular reference.
        public ExprNode Parent;


        [DataMember]
        public Operator Op;


        [DataMember]
        public int Value;
    }


    public class WCFCalcSvc : IWCFCalc
    {
        private void Err(string s)
        {
            Console.WriteLine(s);
            throw new FaultException(
                new InvalidOperationException(s), s);
        }


        private Operator ToOp(char c)
        {
            switch (c)
            {
                case '+': return Operator.PLUS;
                case '-': return Operator.MINUS;
                case '*': return Operator.MUL;
                case '/': return Operator.DIV;
                default: return Operator.ERROR;
            }
        }


        private bool HigherPrecedence(Operator o1, Operator o2)
        {
            if ((o2 == Operator.PLUS || o2 == Operator.MINUS) &&
                (o1 == Operator.MUL || o1 == Operator.DIV))
                return true;


            return false;
        }


        int Calculate(ExprNode expr)
        {
            if (expr.Op == Operator.VAL)
                return expr.Value;


            if (expr.Op == Operator.EXPR)
                return Calculate(expr.Right);


            if (expr.Op == Operator.PLUS)
                return Calculate(expr.Left) + Calculate(expr.Right);


            if (expr.Op == Operator.MINUS)
            {
                if (expr.Left == null)
                    return -Calculate(expr.Right);


                return Calculate(expr.Left) - Calculate(expr.Right);
            }


            if (expr.Op == Operator.MUL)
                return Calculate(expr.Left) * Calculate(expr.Right);


            if (expr.Op == Operator.DIV)
                return Calculate(expr.Left) / Calculate(expr.Right);


            Err("Internal error: unknown operator!");
            return 0;
        }


        public int Calculate(string expr)
        {
            return Calculate(Parse(expr));
        }


        public ExprNode Parse(string expr)
        {
            int x = 0;
            ExprNode current = null;
            while (x < expr.Length)
            {
                if (expr[x] == ' ')
                {
                    ++x;
                    continue;
                }


                if (expr[x] == '(')
                {
                    ++x;


                    ExprNode node = new ExprNode();
                    node.Op = Operator.OPENPAREN;
                    if (current == null)
                    {
                        current = node;
                        continue;
                    }


                    if ((current.Op == Operator.VAL) ||
                        (current.Right != null))
                    {
                        Err("Error @ " + x);
                    }


                    node.Parent = current;
                    current.Right = node;
                    current = node;
                    continue;
                }


                if (expr[x] == ')')
                {
                    ++x;


                    while (current != null && current.Op != Operator.OPENPAREN)
                        current = current.Parent;


                    if (current == null)
                        Err("Error @ " + x);


                    // Close the paren
                    current.Op = Operator.EXPR;
                    continue;
                }


                Operator op = ToOp(expr[x]);
                if (op != Operator.ERROR)
                {
                    ++x;


                    ExprNode node = new ExprNode();
                    node.Op = op;


                    // currently no support for unary ops
                    if (current == null ||
                        (current.Op != Operator.VAL &&
                        current.Op != Operator.EXPR))
                    {
                        if (op == Operator.MINUS)
                        {
                            node.Parent = current;
                            if (current != null)
                                current.Right = node;
                            current = node;
                            continue;
                        }


                        Err("Error @ " + x);
                    }


                    // This ensures that the higher precedence
                    // operators are lower in the expression
                    // tree, and therefore execute before the
                    // lower precedence operators.
                    while (current.Parent != null &&
                        current.Parent.Op != Operator.OPENPAREN &&
                        !HigherPrecedence(op, current.Parent.Op))
                    {
                        current = current.Parent;
                    }


                    node.Parent = current.Parent;
                    if (current.Parent != null)
                        current.Parent.Right = node;
                    current.Parent = node;
                    node.Left = current;
                    current = node;


                    continue;
                }


                // value
                if (expr[x] >= '0' && expr[x] <= '9')
                {
                    int n = 0;
                    while (x < expr.Length && (expr[x] >= '0' && expr[x] <= '9'))
                    {
                        n = n * 10 + (expr[x] - '0');
                        ++x;
                    }


                    ExprNode node = new ExprNode();
                    node.Op = Operator.VAL;
                    node.Value = n;
                    if (current == null)
                    {
                        current = node;
                        continue;
                    }


                    if (current.Op == Operator.VAL)
                        Err("Error @ " + x);


                    if (current.Right != null)
                        Err("Error @ " + x);


                    node.Parent = current;
                    current.Right = node;
                    current = node;
                    continue;
                }
            }


            while (current != null && current.Parent != null)
            {
                if (current.Op == Operator.OPENPAREN)
                    Err("Not enough closed parens!");


                current = current.Parent;
            }


            if (current != null && current.Op == Operator.OPENPAREN)
                Err("Not enough closed parens!");


            return current;
        }
    }


    class Program
    {
        static void Main(string[] args)
        {
            Uri baseAddress = new Uri("http://localhost:8000/Calculator");
            ServiceHost selfHost = new ServiceHost(typeof(WCFCalcSvc), baseAddress);
            try
            {
                selfHost.AddServiceEndpoint(
                    typeof(IWCFCalc),
                    // DANGER! DO NOT CARRY SecurityMode.None
                    // INTO PRODUCTION SERVICE BY DEFAULT!!!
                    new WSHttpBinding(SecurityMode.None),
                    "Calculator");




                ServiceMetadataBehavior smb = new ServiceMetadataBehavior();
                smb.HttpGetEnabled = true;
                selfHost.Description.Behaviors.Add(smb);


                selfHost.Open();
                Console.WriteLine("The service is ready.");
                Console.WriteLine("Press to terminate service.");
                Console.WriteLine();
                Console.ReadLine();


                selfHost.Close();
            }
            catch (CommunicationException ce)
            {
                Console.WriteLine("An exception occurred: {0}", ce.Message);
                selfHost.Abort();
            }
        }
    }
}

To compile the service, create an empty console project, add System.Runtime.Serialization and System.ServiceModel to the list of references, and copy the code into it.

To consume the service, create a client project with the following code:

//-----------------------------------------------------------------------

//

// Copyright (C) Sergey Solyanik.

//

// This file is subject to the terms and conditions of the Microsoft Public License (MS-PL).

// See http://www.microsoft.com/opensource/licenses.mspx#Ms-PL for more details.

//

//----------------------------------------------------------------------- 

using System;

using WCFTestClient.WCFCalc;

namespace WCFTestClient

{

    class Program

    {

        static void Print(ExprNode n)

        {

            Console.Write("(" + n.Op + " ");

            if (n.Left != null && n.Right != null)

            {

                Print(n.Left);

                Console.Write(", ");

                Print(n.Right);

                Console.Write(")");

            }

            else if (n.Left != null || n.Right != null)

            {

                Print(n.Left != null ? n.Left : n.Right);

                Console.Write(")");

            }

            else

            {

                Console.Write(n.Value + ")");

            }

        }

        static void Main(string[] args)

        {

            WCFCalcClient svc = new WCFCalcClient();

            for (; ; )

            {

                Console.Write("> ");

                string s = Console.ReadLine();

                if (s.Equals("exit", StringComparison.OrdinalIgnoreCase))

                    break;

                try

                {

                    if (s.StartsWith("p"))

                    {

                        s = s.Substring(1);

                        ExprNode n = svc.Parse(s);

                        Print(n);

                        Console.WriteLine();

                    }

                    else

                    {

                        Console.WriteLine(s + " = " + svc.Calculate(s));

                    }

                }

                catch (Exception e)

                {

                    Console.WriteLine(e.Message);

                }

            }

        }

    }

}

As you can see, it only takes 1 line of code (!) to connect to our service. The rest constitutes the logic of the program itself.

Now run the service from a command line. Right-click on Service References, select "Add Service Reference", point it to http://localhost:8000/Calculator, set WCFCalc as a namespace, and click import. That's it - you are done. The service importer will create app.config with all the endpoint details, you can now just run the client.

Prefix your expression with p to display the parse tree for it, like so: p2+2, or type "exit" to leave.

Pepper spray

"It is becoming more and more fashionable right now, this day and age, to use chemical on people who have an opinion. And that to me is a complete lack of leadership both in the police department and other people who cannot really deal with the root of the problem and they want to spray people to quiet them down. And it’s really not supposed to be that. It’s not a thing that solves any problem nor is it something that quiets people down.”

Kamran Loghman, inventor of modern pepper spray and developer of police procedures for its use

http://boingboing.net/2011/11/30/pepper-spray-inventor-its.html

"War on militancy"

The attack comes as relations between the United States and Pakistan — its ally in the war on militancy — are already strained following the killing of al-Qaida leader Osama bin Laden by U.S. special forces in a secret raid on the Pakistani garrison town of Abbottabad in May.
http://www.msnbc.msn.com/id/45442885/ns/world_news-south_and_central_asia/#.TtDjXPLCcSg

Our ministry of self-censorship is clearly still recovering from a Thanksgiving dinner today...

Economics, as understood by Alan Greenspan

http://cscs.umich.edu/~crshalizi/weblog/841.html

State secrets

"By the way, during seven of the eight George W. Bush years, the IRS report on the top 400 taxpayers was labeled a state secret, a policy that the Obama administration overturned almost instantly after his inauguration."
http://wweek.com/portland/article-17350-9_things_the_rich_dont_want_you_to_know_about_taxes.html

Hiring at elite companies

A friend sent me a pointer to this blog post: http://econlog.econlib.org/archives/2011/11/how_elite_firms.html
The original paper is about hiring practices in financial institutions, but the fact that the best companies prefer applicants from the best universities (much in the same way the top grad schools mostly accept people from the top undergrad schools) is a recurring complaint in software industry as well.

In all cases the preferential treatment is driven by selectivity of the school, not so much by the quality of skills developed there: the idea is that since colleges are highly selective, you can apply them as the first filter to the applicant pool. The system then continues - the resumes from the candidates working at the top companies draw more attention than the resumes from lesser brands, and so it goes.

Which means that if you missed out on a good school early on, you are kinda screwed; while upward mobility is not impossible, it becomes much, much harder.

A long time ago I experienced something similar myself. When I came to the United States, I took the GRE and applied to several top graduate programs in physics. My GRE scores were far, far above the published average scores for all of these programs except MIT, where it was closer to (but still above) average.

In the Soviet Union where I was from, test results were the only allowed criteria for admission. There was no concept of reference letters, legacy status, nor other out-of-band information that would feed into the decision making process. In fact, anything resembling legacy considerations were considered corruption and would earn all involved parties a one-way, all expenses paid, trip to Siberia's finest labor camps (corruption did of course exist, and when discovered it was dealt with harshly; one of the people on my alma mater admission committee ended up in jail for bartering admissions spots for favors from other well-connected people).

Imagine my surprise when I got the rejection letter from UPenn - UPenn! - where the average subject GRE score was in 600s! At the time I did not know what a "safety school" was, but if I did I have thought about it as such at the time. I only applied to UPenn because I lived in Philadelphia at the time, all our relatives lived there, and I needed to show that I was not dismissing the idea of staying "close to the family" outright.

Completely baffled, I wrote them a letter, pointing out the huge discrepancy in the scores and asking them to explain the decision. Soon I befriended another Russian who had emigrated a year earlier and who filled me in on admission practices in the US. According to him, most of the people in the theoretical physics department at Princeton did not even take the GRE - which was listed as a requirement.

Instead, they were being accepted based strictly on references from their undergrad professors. And because people from the top grad schools knew people from the top undergrad schools, their references were trusted far more.

I, on the other hand, was completely unaware of the relative importance of the references, so I got them from random people who were unknown to the admissions committees, and so my application was roundly rejected - the letters from all the other schools arrived a bit later. (UPenn later reversed its decision and accepted me - they must have read my letter and decided that a guy so naive would end up living under a bridge were they not to save me).

But I digress.

This system of course leads to very high rate of false negatives - essentially, first strike out. Also, not surprisingly, it results in some amount of false positives as well - once inside, you have a larger than normal share of opportunities to recover from previous failures - regardless of your skills, that degree from Harvard will keep opening doors for you years from now.

The system is obviously sub-optimal, so over the years we tried our best to fix it. Microsoft pioneered the concept of a coding interview - where people are forced to write code on the whiteboard as part of the interview process, a system that is now standard almost everywhere.

http://www.amazon.com/Would-Move-Mount-Microsofts-Puzzle/dp/0316919160
http://www.amazon.com/Cracking-Coding-Interview-Programming-Questions/dp/1466208686

This is infinitely better than hiring people based strictly on their resume and some feel-good conversation during the interview, but it is not entirely fool-proof.

First, it emphasizes a set of skills - specifically, algorithm design - that are not all that frequently required in the actual jobs that people do. Ask yourself, how many times have you had to write quick sort, a hash table, an AVL tree, or a read-write lock implementation at work (and if you did, I would really be interested to know why :-)). The vast majority of people - especially those who work on maintaining very large code bases - like Windows - simply do not get the opportunity to exercise their algorithmic muscle very often.

Yet these are all fair questions during the interview. Don't get me wrong - I BELIEVE that these are fair questions, and I ask them myself: even if you don't need to code hashtables every day, it still helps to know how they work.

For example, I ran into a situation at a hiring committee at Google where an interviewer was unhappy that the interviewee could not find an O(1) solution to a problem that - as far as I was concerned - did not have one. When I asked how exactly could one solve it in O(1) time, the person said - why, by using a hash, of course! Put a person who is convinced that a hash always exhibits O(1) performance on an OS component, and you are in for a number of interesting and intractable performance bugs down the road.
So knowing algorithms and data structures well is very important, but our jobs are not preparing us for that. Which is why I found that often hiring a person from college - especially, an elite college - is easier than hiring a person from the industry - they have not yet had time to forget the theory.

Also, knowing the things that are testable in the coding interview - algorithms, design practices, etc - is necessary, but not sufficient for engineering stardom. I've seen - and hired! - a number of people who were fantastic during the interview, but were very ineffective when they needed to deal with a real engineering problem - such as fixing a complex bug in a large system in a way that does not break existing functionality. To this day I have no idea how to do a practical examination of this skill in an interview setting!

Meanwhile, the candidate pool is huge, and the resumes are mostly BS. I once did an experiment. We needed a contractor for web development - AJAX, Javascript, things like that. So I took every person who claimed to be an expert in Web development on the resume that the contract agencies gave me for a standardized test - about 20 people in all. The test was not very advanced. The questions were "What is a closure in Javascript?", "What is the difference between A.foo = 'bar'; and A.prototype.foo = 'bar';", etc - introductory stuff. The best person on the test scored 25%. The average was below 10%.

Therein lies the cornerstone problem of the software industry, which I will summarize thus:

1) Success of a software company is dependent on hiring great people. A star software engineer is an order of magnitude more productive than an average engineer, but costs only marginally more. Thus there is a huge incentive for companies to hire the best of the best.

2) Many qualities of the best of the best engineers are very hard to measure directly. We can test problem solving, knowledge, and design skills during the interview, but we are forced to rely on a candidate's word when it comes to equally important qualifications such as ability to face ambiguity, passion, leadership, and working with others.

3) There is a huge pool of candidates. The resume databases at the top companies have literally millions of entries. Most of the resumes are "enhanced" for "quality".

4) Vast majority of the candidates are not... well, they are not in the top 10% :-). They may be enough to perform a lot of the jobs adequately, but they are nowhere near the productivity of the best of the best (see #1), and once the job for which they were hired is done, they may not be easily transferable to a different one.

5) Firing someone from a big company requires a lot of work, is a very lengthy process, and so the cost of false positive is very high - both in the company's bottom line as well as in morale of the team.

So... what do we do? How do we even screen the resumes - in a fully meritocratic system that pays no attention to selectivity of the previous places of work or study - given the pure amount of BS in an average sample?

The existing system that relies both on the selectivity of the environment as well as on the interview performance works in the sense that everything else we tried was worse.

After all, I do not ever see anything near the stuff people reported on this thread at work: http://www.reddit.com/r/AskReddit/comments/mk7yn/managers_supervisors_and_hr_people_of_reddit_tell/. As a matter of fact, even things worthy of the Daily WTF (http://thedailywtf.com/Default.aspx) almost never come up - at least as long as you are staying inside MSFT product development teams.

This does not mean that the system cannot be improved further - but how? Your ideas are welcome in the comments.

How to clean up the Internet (via Reddit)

"She tells me one day her husband is a really great guy because he spends his free time helping to "clean up the internet."
I ask her what she means and she told me she found a bunch of porn in husbands web browser history. He informed her that he goes to porn sites to download the porn off of the internet servers onto his computer so that he can delete it. Apparently there's a lot of porn on the internet, but he was trying to do what he could to remove as much of it as possible - for the children and all...

She actually believes that he is doing this and uses it as a bragging point to show what a great guy her husband is in conversations."

http://www.reddit.com/r/AskReddit/comments/mk7yn/managers_supervisors_and_hr_people_of_reddit_tell/c31lp65

How to sign device drivers with a test certificate

This: http://msdn.microsoft.com/en-us/library/bb530195.aspx has a long, unwieldy explanation.

Here is a much simpler, step-by-step protocol:
1) Run the following from an elevated CMD window (RunAs Administrator):
    bcdedit /set testsigning on
    bcdedit /set nointegritychecks on
2) Reboot
3) Make a certificate. From a DDK command line window, type:
    makecert -r -pe -ss MyTestCertStore -n "CN=MyTestCert" mytestcert.cer
4) From an elevated CMD window
    certmgr -add mytestcert.cer -s -r localmachine root
    certmgr -add mytestcert.cer -s -r localmachine trustedpublisher
5) From certmgr window that just opened in step one or two (or type certmgr):
  a) Right click on Trusted Root Certification Authorities -> All Tasks -> Import
  b) Navigate to the cert file you have just created in step (3) (mytestcert.cer).
  c) Say "yes"
6) To sign the driver:
    signtool sign /n MyTestCert /s "MyTestCert" yourdrivername.sys

Why can't our documentation people produce something similar???

The new Free Speech protocol

Citizen! It has recently come to our attention that you wish to exercise your first amendment freedoms. In order to ensure compliance with Free Speech Safety standards please obey the following rules to ensure that your protest in conducted properly.

• You can exercise your rights in a designated Free Speech Zone. Anyone who is caught outside specified zones participating in a free speech action will be beaten and jailed.
• You must apply for a permit to designate a Free Speech Zone. To apply for a permit please contact the Board of Permitting and Public Safety. It is expected that you will have your sanitation, safety, education, environmental impact and concessions permits before applying. Anyone found participating in a free speech action without a permit will be beaten and jailed.
• Free Speech Zones operate between the hours of 9am - 5pm, anyone caught participating in a free speech action outside of those times will be beaten and jailed.
• All citizens participating in free speech actions must be properly dressed to identify themselves to authorities, corporate representatives and interested third parties. These uniforms can be purchased at several Free Speech Distribution Authorities located throughout your community. Anyone caught participating in a free speech action without proper attire will be beaten and jailed.
• No items will be allowed to be carried into the Free Speech Zone. Anything that is not attached directly to your person or is out of compliance with the standard Free Speech Zone attire protocol will confiscated before entering the Free Speech Zone. Those caught with foreign items are subject to beatings and possible incarceration at the officers discretion. Any property confiscated will be promptly destroyed.

The first amendment is important to us, and we hope by obeying these simple rules you can make our community a safer and happier place.

Good luck with your free speech action!

http://www.reddit.com/r/politics/comments/mcsy3/occupy_wall_street_being_evicted_calls_all_hands/c2zw30v

How I Stopped Worrying and Learned to Love the OWS Protests

http://www.rollingstone.com/politics/news/how-i-stopped-worrying-and-learned-to-love-the-ows-protests-20111110

"I originally was very uncomfortable with the way the protesters were focusing on the NYPD as symbols of the system. After all, I thought, these are just working-class guys from the Bronx and Staten Island who have never seen the inside of a Wall Street investment firm, much less had anything to do with the corruption of our financial system.

But I was wrong. The police in their own way are symbols of the problem. All over the country, thousands of armed cops have been deployed to stand around and surveil and even assault the polite crowds of Occupy protesters. This deployment of law-enforcement resources already dwarfs the amount of money and manpower that the government "committed" to fighting crime and corruption during the financial crisis. One OWS protester steps in the wrong place, and she immediately has police roping her off like wayward cattle. But in the skyscrapers above the protests, anything goes."

Puzzling heap performance in CRT under Visual Studio

So I'm running this app which does reasonable amount of allocations using standard CRT functions. It's compiled for release, but I was running it under Visual Studio. Absolutely terrible memory allocator performance, especially the one in free: 89 seconds to free just under a million structures (the app uses just two sizes - around 32000 2056 byte structures and about 900000 36 byte structures).

Generating: 1000000
Adding: 951 ms
Port: 10000, total ip entries: 994937, total memory used: 3673124
    Entries at level 1: 128 (blanket: 0)
    Entries at level 2: 32768 (blanket: 0)
    Entries at level 3: 885384 (blanket: 3975)
Testing the ip ranges... 0
Testing ip ranges: 27378 ms
Total ips allowed across all ports: 2012537
Removing: 71355 ms
Port: 10000, total ip entries: 0, total memory used: 0
    Entries at level 1: 0 (blanket: 0)
    Entries at level 2: 0 (blanket: 0)
    Entries at level 3: 0 (blanket: 0)

Fine, I replaced the allocator with my own, using fixed memory blocks (described here: http://1-800-magic.blogspot.com/2007/11/guerilla-guide-to-native-memory.html). The object removal time promptly dropped to just above 200ms. Ok. Then, on a hunch, I run this - with the standard CRT allocator - from the command line:

Generating: 1000000
Adding: 281 ms
Port: 10000, total ip entries: 994937, total memory used: 3673124
    Entries at level 1: 128 (blanket: 0)
    Entries at level 2: 32768 (blanket: 0)
    Entries at level 3: 885384 (blanket: 3975)
Testing the ip ranges... 0
Testing ip ranges: 27831 ms
Total ips allowed across all ports: 2012537
Removing: 249 msPort: 10000, total ip entries: 0, total memory used: 0
    Entries at level 1: 0 (blanket: 0)
    Entries at level 2: 0 (blanket: 0)
    Entries at level 3: 0 (blanket: 0)

Come on, Visual Studio guys. Release should mean RELEASE - not a debug heap!

Interestingly, I ran it under profiler after this, and the profiler does the right thing - it uses the fast heap. Otherwise the results would be really, really screwed. It's a good thing - if you happen to use the profiler or at least run it outside the environment before pursuing the problem that does not even exist!

My daughter releases her first Microsoft product!

http://channel9.msdn.com/Blogs/Charles/Summer-Interns-2011-Parallel-Watch-Visualizers-for-Visual-Studio-11

String-matching automaton

static void Main(string[] args)
{
    if (args.Length < 2)
    {
        Console.WriteLine("Usage: {0} string_pattern string",
            Environment.GetCommandLineArgs()[0]);
        return;
    }

    string pattern = args[0].ToUpper();
    string str = args[1].ToUpper();

    // The automaton. Simple state machine that contains back-links to self-repeating
    // patterns inside the pattern. This takes a long time to compute:
    // O(pattern size cubed times size of the alphabet). This makes this algorithm
    // not very practical in general.
    const int alphabetLen = 'Z' - 'A' + 1;
    int [,] transitionFunc = new int[alphabetLen, pattern.Length];
    for (int stateIndex = 0; stateIndex < pattern.Length; ++stateIndex)
    {
        for (int ch = 0; ch < alphabetLen; ++ch)
        {
            string suffix = pattern.Substring(0, stateIndex) + (char)('A' + ch);
            int stateTransition = Math.Min(pattern.Length + 1, stateIndex + 2);
            string prefix;
            do
            {
                --stateTransition;
                prefix = pattern.Substring(0, stateTransition);
            }
            while (!suffix.EndsWith(prefix));
            transitionFunc[ch, stateIndex] = stateTransition;
        }
    }

    // The match.
    int state = 0;
    for (int i = 0; i < str.Length; ++i)
    {
        state = transitionFunc[str[i] - 'A', state];

        if (state == pattern.Length)
        {
            Console.WriteLine("Substring found at " + (i - pattern.Length + 1));
            break;
        }
    }
}

SleepSort

static void SleepSort(int[] args)
{
    int count = 0;
    TimerCallback t = (object o) =>
    {
        Console.WriteLine(o);
        Interlocked.Increment(ref count);
    };

    foreach (int a in args)
        new Timer(t, a, a * 1000, System.Threading.Timeout.Infinite);

    while (count < args.Length)

        Thread.Sleep(1000);
}

static void Main(string[] args)

{
    SleepSort(new int[] {5, 3, 12, 10, 1, 2});
}

Code snippet: how to use Windows Task Scheduler from .NET

First, make a reference to TaskScheduler 1.1 Type Library in COM components.

Then:

using System;
using System.IO;
using System.Threading;
using TaskScheduler;

namespace TaskScheduleDemo
{
    class Program
    {
        static void Main(string[] args)
        {
            if (args.Length > 0)
            {
                if (args[0].Equals("bing"))
                {
                    for (int i = 0; i < 10; ++i)
                    {
                        Console.WriteLine("Bing!");
                        Thread.Sleep(1000);
                    }
                    return;
                }
                else if (args[0].Equals("install"))
                {
                    Install();
                    return;
                }
                else if (args[0].Equals("remove"))
                {
                    Remove();
                    return;
                }
            }

            Console.Error.WriteLine("Usage: {0} {bing|install|remove}");
        }

        static private void Remove()
        {
            ITaskService service = new TaskSchedulerClass();
            service.Connect(null, null, null, null);
            ITaskFolder folder = service.GetFolder(@"\");
            try
            {
                folder.DeleteTask(@"\Microsoft\Bing\Bing", 0);
                folder.DeleteFolder(@"\Microsoft\Bing", 0);
            }
            catch (FileNotFoundException)
            {
            }
            catch (DirectoryNotFoundException)
            {
            }
            catch (System.Runtime.InteropServices.COMException cex)
            {
                // Something else is still there
                if ((uint)cex.ErrorCode != 0x80070091)
                    Console.Error.WriteLine("Failed to remove task: {0}", cex.ErrorCode);
            }
        }

        static private void Install()
        {
            ITaskService service = new TaskSchedulerClass();
            service.Connect(null, null, null, null);
            ITaskFolder folder = service.GetFolder(@"\");
            ITaskFolder bing = null;
            try
            {
                bing = folder.GetFolder(@"Microsoft\Bing");
            }
            catch (FileNotFoundException)
            {
            }

            if (bing == null)
                bing = folder.CreateFolder(@"Microsoft\Bing",
                    "D:(A;;FA;;;BA)(A;;FA;;;SY)(A;;GR;;;WD)");

            ITaskDefinition td = service.NewTask(0);
            td.RegistrationInfo.Description = "Bing!";
            td.Settings.Enabled = true;
            td.Principal.LogonType = _TASK_LOGON_TYPE.TASK_LOGON_INTERACTIVE_TOKEN;

            IExecAction action = td.Actions.Create(_TASK_ACTION_TYPE.TASK_ACTION_EXEC)
                as IExecAction;
            string executable = System.Reflection.Assembly.GetExecutingAssembly().Location;
            action.Path = executable;
            action.WorkingDirectory = Path.GetDirectoryName(executable);
            action.Arguments = "bing";

            ITrigger trigger = td.Triggers.Create(_TASK_TRIGGER_TYPE2.TASK_TRIGGER_TIME);
            trigger.StartBoundary = DateTime.Now.AddMinutes(1).ToString("o");
            trigger.Enabled = true;

            bing.RegisterTaskDefinition(@"Bing", td, 6, null, null,
                _TASK_LOGON_TYPE.TASK_LOGON_INTERACTIVE_TOKEN, null);
        }
    }
}