Reflective Code

We know that .NET performs optimizations when accessing rectangular arrays, but for sequential access should the inner loop be on the first or second index? Is there even a difference?

The Code

using System;

class Program

{

    static void Main(string[] args)

    {

        int size = 512;

        int count = 1000;

        int[,] array = new int[size, size];

        int total = 0;

        var watch = System.Diagnostics.Stopwatch.StartNew();

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

            for (int x = 0; x < size; x++)

                for (int y = 0; y < size; y++)

                    total += array[x, y];

        watch.Stop();

        Console.WriteLine(String.Format("Sequential access by [x,y]: {0}ms", watch.ElapsedMilliseconds));

        watch = System.Diagnostics.Stopwatch.StartNew();

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

            for (int x = 0; x < size; x++)

                for (int y = 0; y < size; y++)

                    total += array[y, x];

        watch.Stop();

        Console.WriteLine(String.Format("Sequential access by [y,x]: {0}ms", watch.ElapsedMilliseconds));

        Console.WriteLine(total);

        Console.Read();

    }

}

The Output

Sequential access by [x,y]: 825ms
Sequential access by [y,x]: 2414ms
0

What a difference! Incrementing the first index in the inner loop takes almost 3 times longer, probably because there are so many more cache misses.

The Verdict

For best performance, process your rectangular arrays by incrementing the first index in an outer loop, and the second index in an inner loop.

One of my projects is a perfect candidate for concurrency. There is a collection of entities that each need to be processed, and each can be processed independently. For the sake of Separation of Concerns, I developed a WorkManager class dedicated to performing an action on the elements of an enumeration. Before I spill the code, here is how it is used:

Entity[] myCollection = LoadEntities();

WorkManager manager = new WorkManager();

manager.ForEach(myCollection, e => e.Process());

Note the lambda expression above. It means that for each Entity in myCollection, the code will execute its Process method. The program will create a separate thread for each processor, and evenly distribute the workload across the threads.

And without further delay, the WorkManager class:

One thing I love about WSUS is the ability to monitor the presence of clients. It gives me a good approximation of the last time a computer was on the network. I often use this information to help me clean missing computers out of Active Directory.

But what about when a computer is removed from the domain before it is removed from WSUS? Rather than manually checking, I wrote an IronPython script that compares the list of computers in Active Directory with the computers on WSUS. When I run this script, it lists computers that should be removed from WSUS, and deletes them for me (after prompting).

In my current programming project, I've embedded IronPython in a C# program. I thought I would share the basics of embedding a scripting engine. I imagine the process would be the same for any language that uses the DLR (Dynamic Language Runtime), like IronRuby. Here is a sample using IronPython 2.0 Beta 5.

using System;

using IronPython.Hosting;

using Microsoft.Scripting;

using Microsoft.Scripting.Hosting;

public class Program

{

    // Delegate matching the signature of the factorial function

    delegate int FactorialDelegate(int n);

    static void Main(string[] args)

    {

        // Our factorial function

        string[] lines = {"def factorial(n):",

                          "  for i in range(1, n):",

                          "    n = n * i",

                          "  return n"};

        string code = String.Join("\r", lines);

        // Instantiate the IronPython environment

        ScriptEngine engine = Python.CreateEngine();

        // Create a scope/module to work in

        ScriptScope scope = engine.CreateScope();

        // A little preparation

        ScriptSource source = engine.CreateScriptSourceFromString(code, SourceCodeKind.Statements);

        // Compile the code

        CompiledCode compiled = source.Compile();

        // Execute the code in the scope

        compiled.Execute(scope);

        //Now the factorial function exists in the IronPython environment. Let's use it.

        // Set x = 5

        scope.SetVariable("x", 5);

        // print factorial(x)

        ScriptSource print = engine.CreateScriptSourceFromString("print factorial(x)", SourceCodeKind.SingleStatement);

        print.Execute(scope);       //outputs 120

        // Get the result from IronPython

        int result1 = scope.Execute<int>("factorial(6)");

        Console.WriteLine(result1); //outputs 720

        // We can also call the function directly from C#

        FactorialDelegate factorial = scope.GetVariable<FactorialDelegate>("factorial");

        int result2 = factorial(7);

        Console.WriteLine(result2); //outputs 5040

        Console.Read();

    }

}

Today a friend and I were reflecting through System.Math (courtesy of IronPython) and we noticed the BigMul method:

Math.BigMul(Int32, Int32) : Int64

Why have a method just for multiplication? It seems to be a trivial reason to add a method to the .NET framework. After all, multiplication with casting does the same thing:

(long)a * (long)b

Being optimistic, I suggested that perhaps Microsoft's BigMul is implementing a faster and more efficient multiplication algorithm. Maybe there is a clever way to multiply two 32 bit numbers without explicit casting to 64 bit. Naturally, I wrote a simple speed test.

static void Main(string[] args)

{

    int a = 40993;

    int b = 69872;

    long c = 0;

    DateTime start;

    TimeSpan length;

    Console.WriteLine("Inline multiplication");

    start = DateTime.Now;

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

        c = (long)a * (long)b;

    length = DateTime.Now - start;

    Console.WriteLine(c);

    Console.WriteLine(length.ToString());

    Console.WriteLine();

    Console.WriteLine("Math.BigMul");

    start = DateTime.Now;

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

        c = Math.BigMul(a, b);

    length = DateTime.Now - start;

    Console.WriteLine(c);

    Console.WriteLine(length.ToString());

    Console.WriteLine();

    Console.Read();

}

The results were not encouraging.

The following is a report I wrote for my Artificial Intelligence course in November 2006. It discusses Franklin Chang's article entitled "Symbolically speaking: A connectionist model of sentence production."

F. Chang developed neural networks to produce proper sentences from basic messages. His networks were implemented on LENS neural network software. This research was performed around the year 2000 and a paper detailing his research and findings was published as an article in Cognitive Science in 2002. In this paper, I will explain, summarize, and analyze his article.

Background

Because Chang's models are neural networks mimicking human linguistic abilities, comprehension of his work relies on familiarity with linguistics and connectionist models. Linguistics will be addressed as necessary throughout this paper. A neural network is a computing model comprised of nodes (also called units) grouped into layers. The nodes between two layers are connected by weights. As nodes are activated, the activations of each layer are passed forward to the next layer by the connecting weights. Layers are connected in a forward-feeding fashion so that there are no loops. The value of a weight determines how much of the activation from the sending node is transferred to the receiving node. The total of all the activations received by a node determines its activation value. The result is a network of nodes that pass activations forward through the network. Activations originate from the input layers, which serve as the input for the network. These activations feed-forward to the output layers, whose activations serve as the output of the network. Learning occurs as weights are adjusted to correct the actual output values to match the desired output values.