Is this string numeric in C# part 2

I heard back from Bill and Jon with some suggestions about improving the algorithm for speed in the IsNumeric(string) function documented at Is this string numeric in C#?

Bill's idea was to use the return value from Int64.TryParse() and Jon's idea was to compare the values of each character to their digital character equivalents and check the greater or less than in the ascii sequence using if (s[i] > '9' || s[i] < '0').

My initial gut-feel reaction was that Jon's would be faster and Bill's slower. The reason that I thought that Jon's would be faster is because I am under the impression that IsDigit() checks other digits outside of the 0 to 9 range to take into account other digit sets such as Thai. Bill's I thought would be slower because I think that TryParse() catches a thrown exception when returning false and so the expense of exception handling would cause it to be slow.

The first problem that I hit was that the original numeric string that I used:

string numericString = "12345678901234567890123456";

was too large for Int64. I didn't pick this up at first and when I ran the first set of tests they completed turned my expectations on their head with Bill's being fastest and then mine and then Jon's. However, these results were invalid as the Int64.TryParse() call was not returning the correct results.

I fixed the test code to look like this and re-ran it all.

static string numericString = "1234567890123456";
static string nonNumericString = "abcdefghijklmnopqrstuvwxyz";
static void DigitTesting()
{
    Func<string, bool> isNumeric_Guy =
        delegate(string s)
        {
            for (int i = 0; i < s.Length; i++)
            {
                if (!Char.IsDigit(s[i]))
                {
                    return false;
                }
            }
            return true;
        };

    Func<string, bool> isNumeric_Jon =
        delegate(string s)
        {
            for (int i = 0; i < s.Length; i++)
            {
                if (s[i] > '9' || s[i] < '0')
                {
                    return false;
                }
            }
            return true;
        };
    Func<string, bool> isNumeric_Bill =
        delegate(string s)
        {
            Int64 number;
            if (Int64.TryParse(s, out number))
            {
                return true;
            }
            return false;
        };

    Func<string, bool>[] functions = {isNumeric_Guy, isNumeric_Jon, isNumeric_Bill };

    foreach (Func<string, bool> function in functions)
    {
        DateTime startTime = DateTime.Now;
        for (int i = 0; i < 100000000; i++)
        {
            function(numericString);
        }
        Console.WriteLine("numberic: {0} time taken: {1}",
            function.Method.Name, DateTime.Now - startTime);
    }
    Console.ReadLine();
}

Against a numeric string IsNumeric_Guy() turned out to be about 15% faster than IsNumeric_Jon() and about 31% faster than IsNumeric_Bill().

When testing against a non-numeric string IsNumeric_Jon() showed up 16% faster than IsNumeric_Guy() and 87% faster than IsNumeric_Bill(). This is how I would have expected the results to be in both cases.

This is an interesting conundrum to end up at with two algorithms both beating each other by the same amount under different data types. Luckily I know that most of the data that this algorithm will be looking at will be non-numeric strings and so I will go with Jon's algorithm.

Thanks Bill and Jon - your ideas and help are much appreciated.

Continued in Is this string numeric in C# part 3.

Is this string numeric in C#?

On a completely unrelated project to my previous post about Optimizing a custom Trim() function in C# where I was stripping non-numeric characters from either end of a string that may have digits in it I found myself battling with a slow running console application that needed profiling.

Someone had recommended EQATEC Profiler to me and so I ran it against this console app to find where the slowness was coming from. It turned out that the bottleneck was in an IsNumeric function:

private readonly static Regex NumericRegex =
    new Regex(@"^[0-9]+$", RegexOptions.Compiled);
bool IsNumeric(string Text)
{
    return NumericRegex.IsMatch(Text);
}

When I discovered how frequently this was being called I went about optimizing it and came up with:

bool IsNumeric(string s)
{
    for (int i = 0; i < s.Length; i++)
    {
        if (!Char.IsDigit(s[i]))
        {
            return false;
        }
    }
    return true;
}

I then tested the two functions on two different strings:

string numericString = "12345678901234567890123456";
string nonNumericString = "abcdefghijklmnopqrstuvwxyz";

To see how they would fare against each other. On the numeric string the new function ran 3 times faster than the old regex one. On the non-numeric string it was a factor of nine. The reason for the huge difference in performance gain between the two types of strings should be fairly obvious. For the non-numeric string the new function bails out of the call immediately after inspection of the first character while the regex would still examine the whole string. For the numeric string both functions would need to examine every single character before returning.

More tests with 2 new algorithms from comment and email: Part 2

Delegates and Lambdas in C#

I was just explaining delegates and lambdas to a friend and thought that I'd write up an example for him.

Here is an IEnumerable<> that we want to interrogate to get all values greater than or equal to 60:
int[] scores = { 45, 55, 59, 65, 66, 67, 68 };

Here is how we could do it using a delegate. We declare a Func<T, TResult> type which is the same as a pointer to a function in C. In our following LINQ statement we pass that function pointer (delegate) as the "predicate" in the Where "clause." The Where() extension method will be passing in each int one at a time and expect a bool true/false result back. That's why we declared the delegate as a Func<int, bool>, the int is what we're passing in and the bool is the return type.
Func<int, bool> predicate = delegate(int score) { return score >= 60; };
IEnumerable<int> passingScores1 = scores.Where(predicate);

LINQ makes the above syntax much easier for us. In the parameter to the Where() extension method we can declare the body of the function so long as it adheres to the prototype of int parameter and bool return.
IEnumerable<int> passingScores2 = scores.Where((int score) => score >= 60);

The compiler can infer the type that's being passed in as the parameter so we can drop the (int score) and replace it with score if you want even more brevity.
IEnumerable<int> passingScores3 = scores.Where(score => score >= 60);

Func<> has 5 overloads:

Func<TResult>
Func<T, TResult>
Func<T1, T2, TResult>
Func<T1, T2, T3, TResult>
Func<T1, T2, T3, T4, TResult>

In best coding practices, what are the maximum number of parameters a function should have? Well the designers of the Func<> delegate believe that it's four and I don't disagree with them. I am guilty of using more than four but that's mostly out of laziness of writing and populating a class to pass instead of the parameters.

JavaScript library management in browsers

Yesterday Google introduced its Closure Tools which includes its Closure Library. Google's AJAX Libraries API page lists a bunch of common JavaScript libraries which include jQuery, Prototype, Scriptaculous, MootTools, Dojo, SWFObject (never heard of this one), and YUI.

One of the advantages of using Google's content distribution network (CDN) for JavaScript libraries is that if someone visiting your site had previously visited another site which used the same JavaScript library from Google's CDN then that library will already be cached and your site will load faster. This is great but I believe that things could be even better. The problem is that you might be using a different CDN to other sites and will not benefit from this caching.

Browsers should be able to manage a library of common JavaScript libraries along with their versions. Your JavaScript code should be able to ask for a particular library and version and the browser should have had it installed when the browser was installed or if released after the initial installation then installed with regular browser updates.

Optimizing a custom Trim() function in C#

I needed to write a Trim() function that removed anything that wasn't a digit from the beginning and end of a string. What usually happens when I write a blog entry like this is that someone posts a comment a few days later saying "hey, you didn't need to write that, it's already in the .NET library." If it is, I haven't been able to find it.

Here is my TrimNonDigits() function first attempt:

protected string TrimNonDigits_v1(string text)
{
    while (text.Length > 0 && !Char.IsDigit(text, 0))
    {
        text = text.Substring(1);
    }
    while (text.Length > 0 && !Char.IsDigit(text, text.Length - 1))
    {
        text = text.Substring(0, text.Length - 1);
    }

    return text;
}

Now this function works and for what I needed it for (trivially short strings) it would do the job. But it is my intention to add it to a string extension library and I had a fear that someone would pass in an enormous string and with all the Substring() operations creating new strings this may become extremely inefficient.

To see how inefficient this function was I wrote another unit test to specifically measure the speed at which the code ran. Here is that unit test:

[TestMethod]
public void trim_non_digits_big_text()
{
    int repeat = 10000;
    UnitTestDerived utd = new UnitTestDerived();
    string lotsOfCharacters = String.Join("", Enumerable.Repeat("abcdef", repeat).ToArray());
    string text = lotsOfCharacters + "1" + lotsOfCharacters;
    string expected = "1";
    string actual = utd.TrimNotDigits(text);
    Assert.AreEqual(expected, actual);
}

The unit test passes but takes 21 seconds to run. Although extremely unlikely that this amount of non-digit-text on either side of a number might appear it's still a valid use case so the code needed reworking so that the Substring() function was only called once. This is the resulting change to the code:

protected string TrimNonDigits(string text)
{
    int start = 0, end = text.Length - 1;
    while (text.Length > start && !Char.IsDigit(text, start))
    {
        start++;
    }
    if (start != end)
    {
        while (end > start && !Char.IsDigit(text, end))
        {
            end--;
        }
    }
    return text.Substring(start, 1 + end - start);
}

The unit test runs against this new function in under 1 second. That's a dramatic difference and good demonstration for the case of not using Substring() repeatedly in a loop if you can help it.

A side note. I also had several other unit tests that checked the validity of the results of the algorithm before I did the optimization. These included the testing of edge cases and extremes. This made the optimization refactor a cinch because I was fairly confident at the end that the algorithm will work in all situations.

MultiThread testing for speed

I recently wrote this little test program to validate that multi-threading was working the way I expected it to.

class Program
{
    private delegate void funcs();

    static void Main(string[] args)
    {
        funcs[] functions = new funcs[]
        {
            new funcs(MultiThreadTest),
            new funcs(SingleThreadTest)
        };
        foreach (funcs function in functions)
        {
            DateTime startTime = DateTime.Now;
            for (int i = 0; i < 10; i++)
            {
                function();
            }
            while (ThreadWorker.ThreadCount > 0)
            {
                Thread.Sleep(1);
            }
            Console.WriteLine("{0} time taken: {1}",
                function.Method.Name, DateTime.Now - startTime);
        }
        Console.ReadLine();
    }

    private static void MultiThreadTest()
    {
        ThreadWorker threadWorker = new ThreadWorker();
        ThreadStart threadDelegate =
            new ThreadStart(threadWorker.Runner);
        Thread newThread = new Thread(threadDelegate);
        newThread.Start();
    }
    private static void SingleThreadTest()
    {
        ThreadWorker threadWorker = new ThreadWorker();
        threadWorker.Runner();
    }
}

class ThreadWorker
{
    public static int ThreadCount = 0;

    public ThreadWorker()
    {
        ThreadCount++;
    }
    public void Runner()
    {
        IEnumerable<string> strings =
            Enumerable.Repeat(
            @"the not so quick brown fox was
caught by the hen and eaten with eggs", 50);
        string text = String.Join(" ",
            strings.SelectMany(a => a.Split()).ToArray());
        for (int i = 0; i < 1000; i++)
        {
            // Do some random LINQ stuff to occupy the processor
            string[] list = text.Split(' ');
            string[] l2 = list.Distinct().ToArray();
            l2 = list.OrderBy(a => a).ToArray();
            l2 = list.OrderByDescending(a => a).ToArray();
        }
        ThreadCount--;
    }
}

I tested this bit of code by running it four times on each of two machines.

The first was a dual-core and the single-threaded-test took an average of 33.4 seconds and the multi-threaded-test 17.8 seconds. This makes the multi-threaded part 1.9 times faster which is about what you'd expect if you allow two processors to work on the problems in parallel.

The second machine was a quad core with hyper-threading so essentially eight cores. This took an average of 29.3 seconds for the single-threaded-test and 4.6 seconds for the multi-threaded-test. An improvement factor of 6.4, not as close to 8 as I was expecting but not that far off. If anybody knows why the eight cores do not come as close to an eight-times factor as the two cores came to a two-times factor I'd love to hear from you in the comments.

The two processors were:

• Intel Core 2 CPU 6400 @ 2.13 GHz
• Intel Xeon CPU L5410 @ 2.33GHz

Something that I found interesting was that the slower processor ran 1.65 times faster than the fast processor when taking advantage of multi-threading. This has important implications for the software that you write. The single-threaded test ran 1.14 times (14%) faster on the faster processor. However, the multi-threaded code on the slower processor runs 65% faster than the single-threaded code on the faster processor.

If you're looking for a performance boost there may be more performance in multi-threaded code than in a faster processor. In fact, processor speed is probably not what you're looking for. The best combination would be multi-threaded code on multi-core boxes.

 

Using LINQ to join two string lists without repeats

I have a list of members that have to play a game against each other and I want to generate a complete list of all the members against every other member without repeating any games. My list looks like this:

string[] members = {"Alphie", "Jerome", "Silky", "Buzz" };

My first attempt at generating a list using LINQ was this:

IEnumerable<string> q = from one in members
                        from two in members
                        select one + " plays " + two;

which resulted in:

Alphie plays Alphie
Alphie plays Jerome
Alphie plays Silky
Alphie plays Buzz
Jerome plays Alphie
Jerome plays Jerome
Jerome plays Silky
Jerome plays Buzz
Silky plays Alphie
Silky plays Jerome
Silky plays Silky
Silky plays Buzz
Buzz plays Alphie
Buzz plays Jerome
Buzz plays Silky
Buzz plays Buzz

This is not exactly what I was looking for. I wonder who the winner would have been in Buzz versus Buzz?

The secret is to put a where clause before the select statement:

where one.CompareTo(two) < 0

This will eliminate duplicates when CompareTo(two) == 0 and also alphabetically sort the two players eliminating them playing against each other a second time. This is the complete code snippet:

IEnumerable<string> q = from one in members
                        from two in members
                        where one.CompareTo(two) < 0
                        select one + " plays " + two;

and here are the revised results:

Alphie plays Jerome
Alphie plays Silky
Alphie plays Buzz
Jerome plays Silky
Buzz plays Jerome
Buzz plays Silky