Phillip Trelford's Array

Chances are that if you are habitually applying C-style Micro-Optimization tricks when coding C#, like moving variable declarations out of loops, you are probably:

1. Prematurely optimizing
2. Doing it completely wrong

To demonstrate the point lets start by ignoring that there is a perfectly good Array.Reverse function in the framework and write our own:

static void Reverse1<T>(T[] xs)
{
    for (int i = 0; i < xs.Length / 2; i++)
    {
        T x = xs[i];
        xs[i] = xs[xs.Length - 1 - i];
        xs[xs.Length - 1 - i] = x;
    }
}

Now micro-optimize by taking the temp declaration out of the loop:

static void Reverse2<T>(T[] xs)
{
    T x;
    for (int i = 0; i < xs.Length / 2; i++)
    {
        x = xs[i];
        xs[i] = xs[xs.Length - 1 - i];
        xs[xs.Length - 1 - i] = x;
    }
}

The IL (byte code) generated for both implementations is identical in both release and debug builds. If you don’t believe me then check it for yourself by using the ildasm tool.

Another micro-optimization would be to store a copy of the array length in a local variable:

static void Reverse3<T>(T[] xs)
{           
    int len = xs.Length;
    for (int i = 0; i < len / 2; i++)
    {
        T x = xs[i];
        xs[i] = xs[len - 1 - i];
        xs[len - 1 - i] = x;
    }
}

This does actually result in the generation of different IL code, however IL generation is only part of the story. The difference in execution time between these implementations is negligible. The reason is that the IL code is just-in-time (JIT) compiled to machine code before execution and this compilation step will apply further optimizations.

Premature optimization is wrong on so many levels:

• the optimization was probably unnecessary anyway
• code can become less readable for no tangible benefit
• you’re double guessing 2 compilation steps
• you’re probably not even considering high level optimizations

Further reading:

Pareto principle

The Sad Tragedy of Micro-Optimization Theater

Micro-Optimization and Meatballs

Micro-optimization tips to increase performance

Since I first posted an F# solution to Left-Truncatable Primes, C# and Haskell have entered the frame, and although this is not a good problem for a serious comparison of languages, I think it is still interesting.

So lets start at the beginning, Dominic Penfold initially posed the problem and gave an efficient algorithm implemented in C++ (39 lines):

bool IsPrime(int num)
{
    int sqrt = 1 + sqrtf(num);
    for (int i=2; i<sqrt; i++)
    {
        if (num % i == 0)
            return false;
    }
    return true;
}
 
int NthLeftTruncatablePrime(int target)
{
    std::vector<int> PrimeRoots;
    PrimeRoots.push_back(2);
    PrimeRoots.push_back(3);
    PrimeRoots.push_back(5);
    PrimeRoots.push_back(7);
    int start = 0;
    int tens = 10;    
    while(true)
    {
        int end = PrimeRoots.size();
        for (int i=1; i<10; i++)
        {
            for (int pos = start; pos< end; pos++)
            {
                int newprime = tens * i + PrimeRoots[pos];
                if (IsPrime(newprime))
                {
                    PrimeRoots.push_back(newprime);
                    if (PrimeRoots.size()==target)                                      
                        return newprime;                    
                }
            }
        }
        start = end;
        tens *= 10;
    }
}

Performance was considerably faster when 32-bit integers were switched for 64-bit integers.

The C++ code is very easily converted into C# (35 lines):

static bool IsPrime(int num)
{
    int sqrt = 1 + (int ) System.Math.Sqrt(num);
    blue">for (int i = 2; i < sqrt; i++)
    {
        if (num % i == 0)
            return false;
    }
    return true;
}

static int NthLeftTruncatedPrime(int target)
{
    var primeRoots = new List<int>() { 2, 3, 5, 7};               
    int start = 0;
    int tens = 10;
    while (true)
    {
        int end = primeRoots.Count;
        for (int i = 1; i < 10; i++)
        {
            for (int pos = start; pos < end; pos++)
            {
                int newprime = tens * i + primeRoots[pos];
                if (IsPrime(newprime))
                {
                    primeRoots.Add(newprime);
                    if (primeRoots.Count == target)
                        return newprime;
                }
            }
        }
        start = end;
        tens *= 10;
    }
}

Conversion to F# is only slightly trickier as there is no equivalent return statement, but similar behavior can be accomplished using yield (30 lines):

let IsPrime n =
    if n = 1 then false
    else    
        let max = n |> float |> sqrt |> int
        let rec Test = function
            | x when x > max -> true
            | x -> if (n % x) = 0 then false else Test (x+1)
        Test 2

let NthLeftTruncatablePrime n =
    let oneDigitPrimes = [2;3;5;7]          
    seq {            
        let primes = ref oneDigitPrimes        
        for tens = 1 to 8 do
            let acc = ref []
            for i=1 to 9 do 
                let newPrime = i * pown 10 tens                
                let primes' = ref !primes
                while (!primes').Length > 0 do                            
                    let x = newPrime+(!primes').Head
                    if IsPrime x then 
                        acc := x :: !acc
                        yield x
                    primes' := (!primes').Tail                    
                done                                     
            done         
            primes := !acc |> List.rev    
        done            
    }
    |> Seq.append oneDigitPrimes
    |> Seq.nth (n-1)

The extra overhead of generating a sequence can be avoided using instead recursion (25 lines including IsPrime function):

let NthLeftTruncatablePrime index =
    let rec Find digit factor primes primes' count acc =
        match digit, primes' with
        | 10, _ -> 
            let primes = List.rev acc
            Find 1 (10*factor) primes primes count []
        | _, [] ->
            Find (digit+1) factor primes primes count acc
        | _, prime::tail -> 
            let k = (digit * factor) + prime
            let count, acc =
                if IsPrime k then count+1, k::acc else count, acc 
            if count = index then k
            else Find digit factor primes tail count acc
    let primes = [2;3;5;7]
    if index <= 4 then List.nth primes (index-1)
    else Find 1 10 primes primes 4 []

Later Matt Curran (coincidentally another ex-games developer) got in on the act with a Haskell version (17 lines including a comment – although the lines are a little dense):

isPrime :: Int -> Bool
isPrime 1 = False
isPrime x = null $ take 1 [n | n <- [2..upperBound x], 0 == mod x n]
    where
        upperBound = floor . sqrt . fromIntegral

-- list of all left truncatable primes
ltps :: [Int]
ltps = ps 1 [0]
    where
        ps _ []      = []
        ps m prevMag = thisMag ++ (ps (m*10) thisMag)
            where
                thisMag = primes [x*m | x <- [1..9]] prevMag
                    where
                        primes [] _ = []
                        primes (m:mgs) bases = 
                            (filter isPrime [m+x | x <- bases]) ++ (primes mgs bases)

Results Breakdown by language

Note: the time is to generate the 1000th prime, and the same computer was used for all tests, as was release mode. Haskell time coming soon.

LeftTruncatablePrime.cpp (1.45 kb)

LeftTruncatablePrime.cs (1.58 kb)

LeftTruncatablePrime_seq.fs (1.53 kb)

LeftTruncatablePrime_rec.fs (1.36 kb)

This article has been translated to Serbo-Croatian language by WHGeeks .

The .Net Framework ships with a C# code compiler that lets you generate in-memory assemblies. This can be used to run C# scripts without the need for the installation of a large application like PowerShell. The following code, which targets .Net 2.0, builds into a 7K executable, and is all that is needed to run C# source files from the command line:

using System;
using System.CodeDom.Compiler;
using System.Collections.Specialized;
using System.Diagnostics;
using System.IO;
using System.Text.RegularExpressions;
using Microsoft.CSharp;
using System.Collections.Generic;

static class Program
{
    /// <summary>
    /// Executes specified C# script file
    /// </summary>
    /// <param name="args">Path of C# script file</param>
    static void Main(string[] args)
    {
        // Check parameters
        if (args.Length == 0)
        {
            Console.WriteLine("Please specify a C# script file");
            Environment.Exit(-1);
        }
        // First parameter is source file path
        string path = args[0];
        // Check file exists 
        if (!File.Exists(path))
        {            
            Console.WriteLine("Specified file does not exist");            
            Environment.Exit(-1); 
        }
        // Read source from file
        string source = ReadFile(path);
        // Initialize compiler options
        CompilerParameters compilerParameters = 
            new CompilerParameters();      
        compilerParameters.GenerateExecutable = true;
        compilerParameters.GenerateInMemory = true;
        compilerParameters.TreatWarningsAsErrors = true;
        compilerParameters.CompilerOptions = "/nowarn:1633"; // unrecognized pragmas
        // Prepass source for #pragma reference statements        
        StringReader reader = new StringReader(source);       
        while (true)
        {
            string line = reader.ReadLine();
            if (line == null) break;            
            string pattern = 
                "\\s*#pragma\\s+reference\\s+\"(?<path>[^\"]*)\"\\s*";
            Match match = Regex.Match(line, pattern);                   
            if (match.Success)            
                compilerParameters.ReferencedAssemblies.Add
                    (match.Groups["path"].Value);            
        }
        // Specify .NET version
        Dictionary<string, string> providerOptions =
            new Dictionary<string, string>();
        providerOptions.Add("CompilerVersion", "v3.5");
        CSharpCodeProvider provider = new CSharpCodeProvider(providerOptions); 
        // Compile source           
        CompilerResults results =
                provider.CompileAssemblyFromSource(
                    compilerParameters,
                    new string[] { source });
        // Show errors
        if (results.Errors.HasErrors)
        {
            Console.WriteLine("Errors Building " + path);
            foreach (var err in results.Errors)
                Console.WriteLine(err);
            Environment.Exit(-1);
        }
        // Extract argument tail
        string[] parameters = new string[args.Length - 1];
        Array.Copy(args, 1, parameters, 0, args.Length-1);
        // Invoke compiled assembly's entry point
        results.CompiledAssembly.EntryPoint.Invoke
            (null, new object[1] { parameters });        
    }
    
    private static string ReadFile(string path)
    {
        using (StreamReader reader = File.OpenText(path))
            return reader.ReadToEnd();
    }
}

Script files look just like Console applications:

using System;

public class Class1
{
    static void Main(string[] args)
    {
        Console.WriteLine("Hello World");
    }
}

Finally additional assemblies can be referenced using #pragma directives:

#pragma warning disable 1633 // disable unrecognized pragma directive warning
#pragma reference "System.Windows.Forms.dll"

using System.Windows.Forms;

public class Class1
{
    static void Main(string[] args)
    {
        MessageBox.Show("Hello World");
    }
}