C# Performance

24 03 2011

I have been working C# for nearly 8 years and never lost sleep over performance. Sure there are times when things run slowly, but the bottleneck is usually a database query or a web service call. I have never really needed to look into C# performance because it was always fast enough.

A couple weeks ago, Danny Tuppeny wrote “Why I’m Close to Giving Up on Windows Phone 7, as a User and a Developer”.  He raised some pretty valid points, but of course this was a call to arms for the “Anything But Microsoft” crowd.  A side thread about C# performance caught my eye.  Here are a couple of the comments:

  • “My favorite feature of .Net, in general, is sluggish performance, but C# is the best language to write sluggish software in by far.”
  • “ObjC performance is also usually much better than even unsafe C# code, since it is essentially C.”

As I said before, I have never had reason to consider C# “sluggish”, but I also hadn’t really looked into its performance either.  Let’s cut to the chase.

The Results

These are the results (in seconds) for a naïve nth prime finder.  11, 101, 1001, 10001, and 1000001 are the “n’s” in nth.  31, 547, 7927, 104743, and 1299721 are the actual values for the nth prime.

  Version Trial 11 101 1001 10001 100001
31 547 7927 104743 1299721
C++ 1 1 0.000 0.000 0.017 2.101 263.429
2 0.000 0.000 0.021 2.100 263.472
3 0.000 0.000 0.016 2.103 264.520
4 0.000 0.000 0.016 2.109 263.482
5 0.000 0.000 0.015 2.098 265.413
Average 0.000 0.000 0.017 2.102 264.063
C# 1 1 0.001 0.001 0.017 2.172 264.570
2 0.001 0.001 0.017 2.133 264.378
3 0.001 0.001 0.017 2.114 264.246
4 0.001 0.001 0.016 2.133 264.401
5 0.001 0.001 0.017 2.128 264.654
Average 0.001 0.001 0.017 2.136 264.450

The difference is negligible.

The Code

I chose the nth prime problem for a couple reasons.  The code could be written nearly identical in C++ and C# removing any ambiguity about language semantics.  It also has a wide range of optimizations that can be applied.  Version 1 is an extremely naïve (i.e. not optimized) approach.

C++

#include "stdafx.h"

#include <time.h>

#include <iostream>

 

const int maxPrimeIndex = 100001;

int _tmain(int argc, _TCHAR* argv[])

{

       clock_t start, finish;

       start = clock();

 

       int currentPrime = 2;

       int primeCount = 1;

 

       while (primeCount < maxPrimeIndex)

       {

              bool isPrime = false;

              int candidate = currentPrime + 1;

              while (!isPrime)

              {

                     isPrime = true;

                     for (int factor = 2; factor< candidate; factor++)

                     {

                           if (candidate % factor == 0)

                           {

                                  isPrime = false;

                                  break;

                           }

                     }

                     if (!isPrime)

                     {

                           candidate++;

                     }

              }

              currentPrime = candidate;

              primeCount++;

       }

 

       finish = clock();

       double elapsed = ((double)(finish – start)) / CLOCKS_PER_SEC;

       std::cout << elapsed << std::endl << currentPrime << std::endl;

       return 0;

}

C#

using System;

 

namespace SpeedTest

{

    class Program

    {

        const int maxPrimeIndex = 100001;

        static void Main(string[] args)

        {

            DateTime start, finish;

            start = DateTime.Now;

 

            int currentPrime = 2;

            int primeCount = 1;

 

            while (primeCount < maxPrimeIndex)

            {

                bool isPrime = false;

                int candidate = currentPrime + 1;

                while (!isPrime)

                {

                    isPrime = true;

                    for (int factor = 2; factor < candidate; factor++)

                    {

                        if (candidate % factor == 0)

                        {

                            isPrime = false;

                            break;

                        }

                    }

                    if (!isPrime)

                    {

                        candidate++;

                    }

                }

                currentPrime = candidate;

                primeCount++;

            }

 

            finish = DateTime.Now;

            TimeSpan elapsed = finish – start;

            Console.WriteLine(elapsed.ToString());

            Console.WriteLine(currentPrime);

        }

    }

}

Why?

Why are the results so similar?  Because both C++ and C# are compiled.  When comparing these programs we are really comparing their compilers.  This program is pretty straight-forward (i.e. no function calls, memory allocation, array checking, etc.) so the compiler optimizations are probably pretty similar.  I used the Microsoft C++ compiler, but I also tested it with g++ and there was negligible difference. 

If you really need to see the C++ compiler “beat” the C# compiler change candidate from an int to a long.  The C++ code will run a little more than twice as fast.  My guess is that the % operator is much less efficient on longs in C#, but that’s just a guess.

C# is typically JIT compiled, but it doesn’t have to be.  You can use a tool called ngen to compile the image before running it.  You should have a really good reason before doing this though because it can cause headaches when managing updates and the results in many cases will not be dramatic.

Optimization

As I said before, this code was intentionally not optimized.  We are going to apply a very simple but very effective optimization by only checking possible factors up to (and including) the square root of the candidate.  Here are the results:

  Version Trial 11 101 1001 10001 100001
31 547 7927 104743 1299721
C++ 2 1 0.000 0.000 0.000 0.016 0.483
2 0.000 0.000 0.000 0.017 0.479
3 0.000 0.000 0.000 0.015 0.472
4 0.000 0.000 0.000 0.015 0.468
5 0.000 0.000 0.000 0.014 0.481
Average 0.000 0.000 0.000 0.015 0.477
C# 2 1 0.001 0.001 0.002 0.016 0.484
2 0.001 0.001 0.001 0.018 0.474
3 0.001 0.001 0.001 0.016 0.470
4 0.001 0.001 0.002 0.018 0.473
5 0.001 0.001 0.002 0.019 0.470
Average 0.001 0.001 0.002 0.017 0.474

With one simple optimization we have drastically increased our efficiency as n increases.  This raises another question: how fast is fast enough?  For the 100001st it was definitely worth our while.  For the 10001st we save a couple of seconds.  For the 1001st and below it took us more time to write this simple optimization than we’ll ever save.  Context is important.

Conclusion

The point is that people that make blanket statements about performance often have no idea what they are talking about.  Good programmers take the time to understand bottlenecks.  Their gut reaction isn’t “throw more hardware at it” or “should have written it in C”.  A great compiler isn’t going to save your application from a bad coder.

If you disagree, let me know.  Maybe you’re curious how JavaScript or Python compares?  I’d be happy to oblige.  You can find me on Twitter (@azzlsoft) or email (rich@azzlsoft.com).

Advertisements




Project Euler 008 – TSQL

24 03 2011

Problem 8

Find the greatest product of five consecutive digits in the 1000-digit number.

73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450

Solution

declare @digits varchar(MAX)

set @digits =

73167176531330624919225119674426574742355349194934

96983520312774506326239578318016984801869478851843

85861560789112949495459501737958331952853208805511

12540698747158523863050715693290963295227443043557

66896648950445244523161731856403098711121722383113

62229893423380308135336276614282806444486645238749

30358907296290491560440772390713810515859307960866

70172427121883998797908792274921901699720888093776

65727333001053367881220235421809751254540594752243

52584907711670556013604839586446706324415722155397

53697817977846174064955149290862569321978468622482

83972241375657056057490261407972968652414535100474

82166370484403199890008895243450658541227588666881

16427171479924442928230863465674813919123162824586

17866458359124566529476545682848912883142607690042

24219022671055626321111109370544217506941658960408

07198403850962455444362981230987879927244284909188

84580156166097919133875499200524063689912560717606

05886116467109405077541002256983155200055935729725

71636269561882670428252483600823257530420752963450′

 

declare @returnpattern varchar(2);

set @returnpattern = char(13) + char(10)

 

set @digits = replace(@digits, @returnpattern, )

 

declare @currentDigit int

set @currentDigit = 1

declare @sql varchar(max)

 

while(@currentDigit <= len(@digits))

begin

       set @sql = ‘insert into Problem_008 (ordinal, digit) values (‘ + str(@currentdigit) + ‘, ‘ + substring(@digits, @currentDigit, 1) + ‘)’

       exec(@sql)

       set @currentDigit = @currentDigit + 1

end

 

GO

 

select max(product) from

(select

       digit

       * (select digit from Problem_008 a where a.ordinal = Problem_008.ordinal + 1)

       * (select digit from Problem_008 a where a.ordinal = Problem_008.ordinal + 2)

       * (select digit from Problem_008 a where a.ordinal = Problem_008.ordinal + 3)

       * (select digit from Problem_008 a where a.ordinal = Problem_008.ordinal + 4) as product

from Problem_008

where ordinal < (select count(*) from Problem_008) 3) Products

 

 

Discussion

This one is going to take a bit of explanation.  I parse the thousand digit number for it’s component digits and insert them into a database table with their ordinals.  After the digits are in a table it’s a simple query.

Clearly, I didn’t need to insert the digits into a table to get the result, but as with all of the TSQL solutions I want to solve it as if the information exists in the database if possible.

If you have any questions, leave a comment, find me on Twitter (@azzlsoft) or email (rich@azzlsoft.com).