Tail Recursive Call != Recursive function call

These days I always think about the F# continuation and about the people blame recursive call. Is that true all the recursive call will generate the stack overflow? The answer is NO. The stack-overflow only happens when the parent call is waiting for the return value from the child invoke. If the recursive function does not return anything, there is no stack-overflow at all.

You have to use 64-bit compiler to make this happen; 32-bit does not work.

Pre-Order/In-Order/Post-Order tree transversal

when we use the CSP to transverse a tree, I got confused due to the how to implement the pre-order/in-order/post-order transversal.

when i look at previous post, i realize the keypoint is in the highlighted section.

type Tree = 
    E | T of Tree * value * Tree

let rec f2 tree cont =
    match tree with
        | EmptyTree -> cont([])
        | Tree(l, n, r) ->
            f2 l (fun lSum ->
                    f2 r (fun rSum->cont(lSum@[n]@rSum)))


currently it is in-order. You can change it to [n]@lSum@rSum and this will be pre-order.

Performance - Using Interface

When I asked around, people are always using average to measure if function A is faster than function B. They ran the A and B 100 times and get the average execution time. But it is interesting that nobody really care about if their numbers were telling the truth or not. From the test data, I found the first time execution is much slower (or larger) than those succeeding ones.

1. A=10309 B=689
2. A=83 B=84
3. A=79 B=84
4. A=72 B=91
5. A=76 B=83
6. A=78 B=85
7. A=89 B=83
8. A=74 B=95
9. A=75 B=87
10. A=75 B=89

My functions are listed following:

        public static void A()

        {

            List a = Enumerable.Range(1, 1000).ToList();

            var r = 0;

            var count = a.Count;

            for (int i = 0; i < count; i++)

                r += a[i];

        }

        public static void B()

        {

            IList a = Enumerable.Range(1, 1000).ToList();

            var r = 0;

            var count = a.Count;

            for (int i = 0; i < a.Count; i++)

                r -= a[i];

        }

It seems that List object is kept and reused in A and B. I was expecting the interface one is slower, but the result show the opposite.

Load data template in Silverlight 4

load a data template in Silverlight is painful job. You can always get some error like: The element is already a child of an element [line 0: position 0].

Please do not forget to add your library as the namespace and your assembly, even though your control is in the same assembly.

var template = (DataTemplate)XamlReader.Load(String.Format(@"xmlns:SilverlightControlLibrary=""clr-namespace:SilverlightControlLibrary;assembly=MyAssembly""> ", i++));

0x88000FA8 error

I have encountered several times 0x88000FA8 error in my WP7 application. There is an exception object, but the visual studio just shows the "Evaluation time out" instead of any useful information.

After spending couple of hours on this stupid problem, now I realize that this is because the infinite event loop. For example, you update a control's layout in this control's LayoutUpdated event handler function, the layout updated event will keep firing and finally give this error.

LINQ's performance

The reason I love LINQ is that it can make me think in a  mathematical way. For some reason, I always doubt the FOR loop and IF condition makes a program buggy. I do not have the number to say most of the bug is from FOR loop or IF condition, but at least a world only with sequential statement seems easier for my brain.

For the performance point of view, LINQ is not perfect. When compare LINQ with simple for loop, the loser is always LINQ. Maybe the problem is too simple?

        public static void A()
        {
            var a = Enumerable.Range(1, 1000);
            var b = Enumerable.Range(1, 1000);
            var r = 0;
            var count = a.Count();
            for (int i = 0; i < count; i++)
                r += (a.ElementAt(i) + b.ElementAt(i));
        }

        public static void B()
        {
            var a = Enumerable.Range(1, 1000);
            var b = Enumerable.Range(1, 1000);
            var r = a.Zip(b, (x, y) => x + y).Sum();
        }

A=50109 B=10628

I got two IEnumerable. The for loop is slower than LINQ and not that easy to understand (at least for me). ElementAt()  is the culprit which makes the A 5 times slower than B. I can convert it to a List and without ElementAt(), A is still still faster than B, but it needs more memory to hold the List.


Do I have a conclusion? Unfortunately, NO. For a quick prototype, LINQ is perfect, but for performance critical hot path, I guess a FOR loop is still the inevitable.

String performance II

the previous post discussed the String.Format and concat. It seems that concat is the most efficient way to add strings together. Now I have the following two functions:


        public static void A()
        {
            var s = "1" + "," + "2" + "," + "3" + "," + "4";
        }

        public static void B()
        {
            var s = String.Join(",", "1", "2", "3", "4");
        }

A wins: A=16 B=310

But when we have to pass to non-string type, the winner is differnet:


        public static void A()
        {
            var s = 1.ToString() + "," + 2.ToString() + "," + 3.ToString() + "," + 4.ToString();
        }

        public static void B()
        {
            var s = String.Join(",", 1, 2, 3, 4);
        }


A=1664 B=496

String.Format performance

C# string performance is a tricky problem. I have two functions which generate the same result. Personally I prefer the second one because it is just an elegant representation format. Well, you have to pay for the elegance.

A's performance is much faster than B's.

         public static void A()
        {
            var s = "abc" + "bcd" + "1" + "2" + "3";
        }

        public static void B()
        {
            var s = String.Format("{0}{1}{2}{3}{4}", "abc", "bcd", "1", "2", "3");
        }

the following is the elapsed ticks for function A and B. If I run 100 iterations, A wins 99 times.


A=14 B=344

Let me try something different, maybe my favorite format has some advantages. Most of time, we do not use String.Format to construct a string, we pass in some non-string type.


        public static void A()
        {
            var s = "abc" + "bcd" + 1.ToString() + 2.ToString() + 3.ToString() + 4.ToString() + 5.ToString();
        }

        public static void B()
        {
            var s = String.Format("{0}{1}{2}{3}{4}{5}{6}", "abc", "bcd", 1, 2, 3, 4, 5);
        }

I am so happy that when this time, the String.Format catches up.


A=1609 B=585

I dig into the IL code and find that:

Function A will calls into "77 : Call System.String System.String.Concat(System.String[])".
While B will invoke: "75 : Call System.String System.String.Format(System.String, System.Object[])"

the different is not from these two functions, the difference is because A has to call ToString() several times and convert the result into a string array. A only need to pass the object reference to the Format.