locked
C# vs C++ performance test RRS feed

  • Question

  • I've been toying around with both C# and C++ as a learning experience.  Recently I got involved elsewhere in a discussion regarding in-memory searching.  The discussion got around to wheter or not binary search was a good technique.

    I undertook the tase of doing dome timing the performance of binary search under C# and C++.  My results were a bit astonishing:

    The test consisted doing an "Overhead" run, where using a dummy search routine in order to assess the calling overhead, a "Iterative" algorthm and a "Recursive" algorithm which calls itself in order to search the appropriate segment of the input array.

    Here are the results using an array of 1 million values and doing 10 million  searches, under C# and C++:

    C#

    Overhead 0.0676 sec

    Iterative 1.4688 sec

    Recursive 2.5938 sec

    C++

    Overhead 0.4720 sec

    Iterative 2.0400 sec

    Recursive 6.8290 sec

    C# wins hads-down!

    I was very amazed at the results.  Any comments?


    RussPC

    Sunday, April 1, 2012 1:14 PM

Answers

  • Hi, 

    Few of my words,

    I would say the question should be, at least in this context from your example, why C++ performs array operations faster than C#. In C#, CLR does not guarantees array items will save contiguously in memory. This is the reason on every index access performs bound check, causes significant performance loss, but this is not the case with C++. We can also turnoff bounds check in C# to get performance improvement.

    By using unsafe you can see performance improvement from the same above code.

    Please check what Eric is saying on this from here..

    unchecked array access is likely to be faster than checked array access; a naive C# implementation is therefore likely to be slower. However, there are techniques for turning off safety checks in C# that enable you to regain the lost performance : 

    I hope this helps you...


    If this post answers your question, please click "Mark As Answer". If this post is helpful please click "Mark as Helpful".

    • Marked as answer by RussPC Monday, April 2, 2012 8:50 PM
    Monday, April 2, 2012 6:27 PM

All replies

  • may be c++ algo not implemented properly!
    Sunday, April 1, 2012 1:37 PM
  • What happens if you use the library functions in C# and C++ to do this?

    I'd have thought the discussion about binary search was a bit academic - it is known to be optimal. However it depends on just exactly what you are searching and how the items that are searched are compared to the target. I believe Knuth wrote a few words on this topic. :)


    Regards David R
    ---------------------------------------------------------------
    The great thing about Object Oriented code is that it can make small, simple problems look like large, complex ones.
    Object-oriented programming offers a sustainable way to write spaghetti code. - Paul Graham.
    Every program eventually becomes rococo, and then rubble. - Alan Perlis
    The only valid measurement of code quality: WTFs/minute.

    • Proposed as answer by cooler8 Monday, April 2, 2012 4:42 AM
    Sunday, April 1, 2012 8:21 PM
  • Hi,

    Hard to comment without seeing some code to check that this is an exact port. And sometimes it's hard even when seeing the code so if you are really interested you may have to use a profiler to find out where it differs (for example overflow checking or other compiler level optimization could perhaps come into play). Note also that it shows with 10 million of searches so in real world condition there is no visible difference and other parts where C++ would win could get the results closer. So I'm not sure it really have a practical interest.

    An area where I saw mentioned (I don't have tested this myself) that C# is supposed to be more consistently efficient is repeated memory allocation (as it is based on a GC, allocating memory is done in chunks and managed by the GC and releasing can be differed while the C++ code immediately allocates and releases each chunks from/to the OS immediately resulting in slower repeated memory allocations). But once again on the other hand the GC could kick in at unexpected times so it's hard to qualify this as an advantage/disavantage. It is just that different languages are performing differently depending on which area you are testing.


    Please always mark whatever response solved your issue so that the thread is properly marked as "Answered".

    Monday, April 2, 2012 1:40 PM
  • Okay, I'll post the code for both programs here:

    C++

    ===================================

     // BStiming.cpp : Defines the entry point for the console application.

    //


    #include "stdafx.h"
    #include <stdlib.h>
    #include <time.h>


    #define iterations    10000000
    #define num_elements   1000000


    int overhead (int a[], int low, int high, int target)
    {
    while (low <= high)
    {
    return low;
    }
    return -1;
    }


    int binary_search (int a[], int low, int high, int target) 
    {
    int middle;


        while (low <= high) 
    {
            middle = low + (high - low) / 2;


            if (target < a[middle])
    high = middle - 1;

            else if (target > a[middle])
                low = middle + 1;

            else
                return middle;
        }
    }


    int recursive_binary_search (int a[], int low, int high, int target) 
    {
    int middle;


        while (low <= high) 
    {
            middle = low + (high - low) / 2;


            if (target < a[middle])
    return recursive_binary_search (a, low, middle - 1, target);

            else if (target > a[middle])
    return recursive_binary_search (a, middle + 1, high, target);
            else
                return middle;
        }


        return -1;
    }






    int _tmain(int argc, _TCHAR* argv[]) {
        clock_t start, stop;


        int* a = (int*) malloc (num_elements * sizeof(int));
        int i, j, present_val, found_at;

    printf("Initializing...\n");


        for(i=0; i < num_elements; i++) 
    {        
                a[i] = i * 123;
        }



    printf("Timing...\n");


    start = clock();
    j = num_elements;


        for(i=0; i < iterations; i++) {
           present_val = a[--j];


           found_at = overhead (a, j, num_elements - 1, present_val);


    if (j <= 0)
    j = num_elements;


            if (found_at == -1 || a[found_at] != present_val)
                puts("ERROR");
        }


    stop = clock();
        printf("overhead         (%i) time: %f sec\n", iterations,
               ((double)(stop - start))/(CLOCKS_PER_SEC));




        start = clock();
    j = num_elements;


        for(i=0; i < iterations; i++) {
            present_val = a[--j];


    if (j <= 0)
    j = num_elements;
            int found_at = binary_search(a, 0, num_elements - 1, present_val);
            if (found_at == -1 || a[found_at] != present_val)
                puts("ERROR");
        }


    stop = clock();
        printf("iterative search (%i) time: %f sec\n", iterations,
               ((double)(stop - start))/(CLOCKS_PER_SEC));


        start = clock();
    j = num_elements;


        for(i=0; i < iterations; i++) {
            present_val = a[--j];


    if (j <= 0)
    j = num_elements;


            int found_at = recursive_binary_search(a, 0, num_elements - 1, present_val);
            if (found_at == -1 || a[found_at] != present_val)
                puts("ERROR");
        }


    stop = clock();
        printf("recursive search (%i) time: %f sec\n", iterations,
               ((double)(stop - start))/(CLOCKS_PER_SEC));



        return 0;
    }



    RussPC

    Monday, April 2, 2012 3:02 PM
  • Here's the C# code:

    =================

    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;




    namespace nsBSTest
    {
        class BSTest
        {
            static int overhead(int[] a, int low, int high, int target)
            {
                while (low <= high)
                {
                    return low;
                }


                return -1;      // Not found
            }




            static int binary_search (int[] a, int low, int high, int target) 
            {
                while (low <= high) 
           {
                    int middle = low + (high - low) / 2;


                    if (target < a[middle])
            high = middle - 1;
                
                    else if (target > a[middle])
                        low = middle + 1;

                    else
                        return middle;
                }


                return -1;      // Not found
            }


            static int recursive_binary_search (int[] a, int low, int high, int target) 
            {
                while (low <= high) 
           {
                    int middle = low + (high - low) / 2;


                    if (target < a[middle])
           return recursive_binary_search (a, low, middle - 1, target);
                
                    else if (target > a[middle])
           return recursive_binary_search (a, middle + 1, high, target);
                    else
                        return middle;
                }


                return -1;
            }




            static void Main(string[] args)
            {
                int num_elements = 1000000;
                int iterations   = 10000000;


                int[] a = new int[num_elements];          
                int i;


                //Console.WriteLine("Initializing...");


                for (i = 0; i < num_elements; i++)
                {
                    //do
                    //{
                        a[i] = i * 123;     // Create the array in sorted order
                    //} while (a[i] == num_elements / 7);
                }


                 Console.WriteLine("Timing...");


                 DateTime startTime = DateTime.Now;


                 int j = num_elements;


                 for (i = 0; i < iterations; i++)
                 {
                     int present_val = a[--j];
                     int found_at = overhead(a, j, num_elements - 1, present_val);


                     if (j <= 0)
                         j = num_elements;


                     if (found_at == -1 || a[found_at] != present_val)
                         Console.WriteLine("ERROR {0} not found", present_val);
                 }


                 DateTime stopTime = DateTime.Now;


                 Console.WriteLine("Overhead {0}:         {1} sec\n", iterations,
                     stopTime - startTime);




                startTime = DateTime.Now;


                j = num_elements;


                for (i = 0; i < iterations; i++)
                {                      
                    int present_val = a[--j];                
                    int found_at = binary_search(a, 0, num_elements - 1, present_val);
                    if (j <= 0)
                        j = num_elements;
                    
                    if (found_at == -1 || a[found_at] != present_val)
                        Console.WriteLine("ERROR {0} not found", present_val);
                }


                stopTime = DateTime.Now;
     
                Console.WriteLine("iterative search {0}: {1} sec\n", iterations,
                    stopTime - startTime);


                startTime = DateTime.Now;
                j = num_elements;


                for (i = 0; i < iterations; i++)
                {
                    int present_val = a[--j];
                    if (j <= 0)
                        j = num_elements;
                    int found_at = recursive_binary_search(a, 0, num_elements - 1, present_val);
                    if (found_at == -1 || a[found_at] != present_val)
                        Console.WriteLine("ERROR {0} not found", present_val);
                }


                stopTime = DateTime.Now;
                Console.WriteLine("recursive search {0}: {1} sec\n", iterations,
                    stopTime - startTime);


                return;
            }
        }
    }


    RussPC

    Monday, April 2, 2012 3:04 PM
  • I believe you will find the algorithms to be correct.

    As to why I'm doing this, actuall that's my business, and has nothing do do with what I have observed.  

    Why code a binary search algorithm?  Why compare C++ performance to that of C#?  As Einstein would ask, "Why not?"

    Actually, will be teaching a programming class and so I am evaluating the two languages to see some of what a beginner might encounter.  And part of teaching programming, in case anyone has forgotten, is to discuss algorithm design, not just using things "out of the box".

    Someone once remarked, "There are no stupid questions, nor stupid questioners, but ther are pleanty of stupid answers."

    Not that this applies to anyone in these forums. :')


    RussPC

    Monday, April 2, 2012 3:10 PM
  • The inherent problem with comparing C# with C++ is that you're using, more or less, the same code.  C++ has advantages in the performance realm not because it can run a for loop quicker than C# code, but because it can simply do things that can't be done (or can't be done very effectively) in C#.  Often this has to do with either manually managing memory when the paradigm is such that if the GC tried to manage it it wouldn't do a very good job, or times where you can use pointer manipulation to solve a problem that just couldn't be efficiently solved in a world without pointers.  Other times C++ allows closer interaction with the hardware to allow performance gains that you can't effectively get out of a more general purpose program in C#.

    People who say C++ is just generally faster than C# are incorrect, and likewise people who say C# is just generally faster are equally wrong.

    They each have their strengths and purposes, especially in the world of performance, and their success is partly tied in with whether they are used according to their design/purpose.

    C# is designed to be hardware agnostic, and to generally perform the best when run over a range of hardware, such that the overall performance is best.  C++ allows code to be very targeted to a specific machine and set of hardware specs.  Code can be optimized for the size of the cache on the target machine, for example.  The cases where performance really, really matters is in the realm of supercomputing.  In such situations you know when you compile a program exactly what hardware specs it's going to run on.  You know the size of the cache, the exact number of processors (incorporating cores/hyperthreading/etc.), and even the instruction set of the chip.  Because C# abstracts away these 'details' it makes it easier to write the program, port it to other hardware, etc.  And yet you'll never see people writing programs in C# and running them on a supercomputer.

    Monday, April 2, 2012 3:28 PM
  • Sorry if I sounded rude. Even though you are telling it doesn't applies to anyone, it feels like you needed to told it ;-). I just meant that I expect to see differences between different languages and not always in favor of always the same language (keep in mind also that you can have hidden factors such as memory alignment for example). So I don't expect to see either C# always outperforming C++ or even the other way round. Now if you find a particular point is quicker in C#, you'll likely find other points being quicker in C++ and I'm not sure what conclusion could be drawn on this. It is just the real world when you have two different things that are behaving differently (even though I can admit you are surprised to see C# outperforming C++)...

    I'm trying to give this a closer look right now (my approach will be likely to test separately stack allocation, comparison, array access for example to see which one seems to account for the bigger difference)...


    Please always mark whatever response solved your issue so that the thread is properly marked as "Answered".

    Monday, April 2, 2012 5:21 PM
  • In which configuration are you testing ? For now what I see is that for the recursive part the C# debug build outperforms by far the C++ debug built but this is the other way round for the release build (two times faster for C++, close match for the overhead and the iterative parts).


    Please always mark whatever response solved your issue so that the thread is properly marked as "Answered".

    Monday, April 2, 2012 5:49 PM
  • Hi, 

    Few of my words,

    I would say the question should be, at least in this context from your example, why C++ performs array operations faster than C#. In C#, CLR does not guarantees array items will save contiguously in memory. This is the reason on every index access performs bound check, causes significant performance loss, but this is not the case with C++. We can also turnoff bounds check in C# to get performance improvement.

    By using unsafe you can see performance improvement from the same above code.

    Please check what Eric is saying on this from here..

    unchecked array access is likely to be faster than checked array access; a naive C# implementation is therefore likely to be slower. However, there are techniques for turning off safety checks in C# that enable you to regain the lost performance : 

    I hope this helps you...


    If this post answers your question, please click "Mark As Answer". If this post is helpful please click "Mark as Helpful".

    • Marked as answer by RussPC Monday, April 2, 2012 8:50 PM
    Monday, April 2, 2012 6:27 PM
  • Thanks, Kris!  

    I did do a Release buld in C++, and the performance improvement is amazing!  In fact, I'm surprised that the recursive algorithm now slightly outperforms the iterative one.  Not by much, but the improvement is there on repeated runs.

    I'm using the Express version of VS 2010.  Either this edition does not have all of the C# build capabilities, or they are lurkning in some unknown (to me) location.

    By nature, I'm quite interested in "what's under the hood!"

    Thanks again.

    Russ


    RussPC

    Monday, April 2, 2012 8:58 PM