Thread: itsme86's challenge...

  1. #1
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547

    itsme86's challenge...

    Subject of debate: Which language is faster?

    I gave this some thought and decided that rather than presenting source code for some esoteric thing that would slant things in C's favor but would never happen in the real world, I'd like to see the results for something real... sorting a large array of ints.

    itsme86... Play fair, no language specific optimizations... just translations...
    The baseline is this code in C on a given machine, other languages should compare to that.

    On my "I don't care if I fry the CPU" system (AMD64 X2 @2.4ghz, ddr2 800mhz) when compiled in PellesC with full optimizations, this code averages 1030ms for 10 tries... so, just over 10 seconds. Of course the only fair comparison is on the same machine... so...

    Code:
    // create and sort large array
    
    #include <stdio.h>
    #include <windows.h>
    
    #define MAXARRAY 100000
    
    int main( void )
      { int x;                    // loop counter
        int y;                    // loop counter
        int max;                  // maximum value
        int swp;                  // swap pointer
        int Swaps = 0;            // swap counter
        unsigned int Start;       // timing
        unsigned int Finish;
    
        printf( "Benchmark on %d elements\n",MAXARRAY);
    
        // timestamp
        Start = GetTickCount();  // in milliseconds
    
        // create array
        int *Array = malloc(MAXARRAY * sizeof(int));
    
        // fill array
        srand(Start);
        for (x = 0; x < MAXARRAY; x++)
          Array[x] = rand() % MAXARRAY;
    
        // sort
        for (x = MAXARRAY - 1; x > 0; x--)
          { max = Array[x]; 
            swp = x;
            for (y = 0; y < x; y++)
             { if (Array[y] > max)
                 { max = Array[y];
                   swp = y; } }
               if (swp < x )
                  { Array[swp] = Array[x];
                    Array[x] = max;
                    ++Swaps; } }
    
        // timestamp
        Finish = GetTickCount();
     
        // report
        printf("Time = %d milliseconds for %d swaps\n",Finish - Start,Swaps);
        return 0; }

  2. #2
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    BubbleSort? Seriously?

    No thanks.

    Oh, and you have a bug and shouldn't time allocation or initialization because that isn't language bound.

    [Edit]
    Oh, wait. You are the one who is "ignoring me". Does anyone else find that funny?
    [/Edit]

    Soma
    Last edited by phantomotap; 03-05-2011 at 10:35 PM. Reason: none of your business

  3. #3
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,218
    System: Intel Core i7-920 @ 3.96GHz

    I compiled your code as: bin\gcc -Wall -O3 ArraySortChallenge.c -o ArraySortChallenge.exe
    ... and got:
    Code:
    Benchmark on 100000 elements
    Time = 2563 milliseconds for 99963 swaps
    And here's the "equivalent" code I came up with in C#:
    Code:
    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Diagnostics;
    
    namespace ArraySortChallenge
    {
        class Program
        {
            private const int _MaxArray = 100000;
    
            private static Random _Random = new Random();
    
            static void Main(string[] args)
            {
                int x, y;  // Loop counters
                int maxValue;
                int swap;
                int swapCounter = 0;
    
                Console.WriteLine("Benchmark on {0} elements", _MaxArray);
    
                Stopwatch sw = new Stopwatch();
                sw.Start();
    
                int[] array = new int[_MaxArray];
                for (x = 0; x < _MaxArray; ++x)
                    array[x] = _Random.Next(_MaxArray);
    
                for (x = _MaxArray - 1; x > 0; --x)
                {
                    maxValue = array[x];
                    swap = x;
                    for (y = 0; y < x; ++y)
                    {
                        if (array[y] > maxValue)
                        {
                            maxValue = array[y];
                            swap = y;
                        }
                    }
    
                    if (swap < x)
                    {
                        array[swap] = array[x];
                        array[x] = maxValue;
                        swapCounter++;
                    }
                }
    
                sw.Stop();
    
                Console.WriteLine("Time = {0} milliseconds for {1} swaps", sw.ElapsedMilliseconds, swapCounter);
            }
        }
    }
    I turned "Optomize code" on and got:
    Code:
    Benchmark on 100000 elements
    Time = 3834 milliseconds for 99980 swaps
    However, I wouldn't ever bother manually sorting my arrays in C#. So here's (just for fun) a C#-ified version of the program:
    Code:
    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Diagnostics;
    
    namespace ArraySortChallenge
    {
        class Program
        {
            private const int _MaxArray = 100000;
    
            private static Random _Random = new Random();
    
            static void Main(string[] args)
            {
                int i;  // iterator
    
                Console.WriteLine("Benchmark on {0} elements", _MaxArray);
    
                Stopwatch sw = new Stopwatch();
                sw.Start();
    
                int[] array = new int[_MaxArray];
                for (i = 0; i < _MaxArray; ++i)
                    array[i] = _Random.Next(_MaxArray);
    
                array = array.OrderBy(n => n).ToArray();
    
                sw.Stop();
    
                Console.WriteLine("Time = {0} milliseconds", sw.ElapsedMilliseconds);
            }
        }
    }
    I turned "Optomize code" on and got:
    Code:
    Benchmark on 100000 elements
    Time = 32 milliseconds
    I thought at first that I did something wrong, but I had it print out all 100000 elements and, sure enough, it's sorted.

    Anyway, with the "equivalent" code, C came out to be about 35% faster. Now executable size:

    C version:
    Code:
     Directory of C:\Dev-Cpp
    
    03/05/2011  08:35 PM            18,506 ArraySortChallenge.exe
                   1 File(s)         18,506 bytes
                   0 Dir(s)  517,879,136,256 bytes free
    C# version:
    Code:
     Directory of C:\Users\Mike\Documents\Visual Studio 2010\Proj
    enge\ArraySortChallenge\bin\Release
    
    03/05/2011  08:41 PM             5,632 ArraySortChallenge.exe
                   1 File(s)          5,632 bytes
                   0 Dir(s)  517,879,136,256 bytes free
    The C# version is less than 1/3 the size.
    Last edited by itsme86; 03-05-2011 at 10:53 PM.
    If you understand what you're doing, you're not learning anything.

  4. #4
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    I thought at first that I did something wrong, but I had it print out all 100000 elements and, sure enough, it's sorted.
    BubbleSort Versus QuickSort or RadixSort or HeapSort or... much anything other than BubbleSort

    Soma

  5. #5
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Ireland
    Posts
    8,446
    Quote Originally Posted by CommonTater View Post
    Subject of debate: Which language is faster?
    I suppose I could run your code in other languages. istme86 already managed C#, I could do it for erlang. But here's some food for thought:

    - Compilers can affect results. Will the same C code run exactly the same when compiled with Visual C++, gcc, Watcom, Digital Mars, Pelles, etc...? Meaning, results for any language enjoying multiple compilers are immaterial.

    - On interpreted languages, certain languages constructs are highly optimized when moved to intermediary code, giving them an "unfair" advantage. This could be seen as irrelevant, given that it still answers the question of which language is faster. However the intermediary code may have nothing to do with the requirements you set forth.

    - Any answer you might get has to be interpreted this way: For this algorithm, under these conditions, for this system and compiled with these compilers, language X is faster than language Y. The premises are so many and so restrictive that there's hardly anything of use in these results.

    Just saying.
    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  6. #6
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Quote Originally Posted by phantomotap View Post
    BubbleSort Versus QuickSort or RadixSort or HeapSort or... much anything other than BubbleSort

    Soma
    Look again... It's not a bubble sort... Moreover it would not matter if it is or not... The point is to compare identical code on different languages... I guess it's time to put you back in the old ignore list for another couple of weeks. Although I don't really expect you to get any smarter for it...
    Last edited by CommonTater; 03-05-2011 at 11:45 PM.

  7. #7
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Quote Originally Posted by itsme86 View Post
    System: Intel Core i7-920 @ 3.96GHz
    Code:
    Benchmark on 100000 elements
    Time = 2563 milliseconds for 99963 swaps
    Code:
    Benchmark on 100000 elements
    Time = 3834 milliseconds for 99980 swaps
    Impressive system... almost 4 times as fast as my junker. On my main system (AMD X4, 3ghz) I ended up at about 3900.

    That's more or less what I expected from C#... about half again as long... Java would, I think be a little slower.

    However, I wouldn't ever bother manually sorting my arrays in C#.
    Neither would I ... C++, C# and C itself provide far more efficient sort algorythms...
    My time was like 400ms with quicksort...


    Code:
    03/05/2011  08:35 PM            18,506 ArraySortChallenge.exe
                   1 File(s)         18,506 bytes
                   0 Dir(s)  517,879,136,256 bytes free
    Mine came in at about 31k on PellesC... but it static links rather than using the Windows C runtimes so a tiny bit of bloat gets in there as a 1 time blob. By the time our code got beyond 100K we'd still be about 16k different...

    C# version:
    Code:
     Directory of C:\Users\Mike\Documents\Visual Studio 2010\Proj
    enge\ArraySortChallenge\bin\Release
    
    03/05/2011  08:41 PM             5,632 ArraySortChallenge.exe
                   1 File(s)          5,632 bytes
                   0 Dir(s)  517,879,136,256 bytes free
    The C# version is less than 1/3 the size.
    Yes, not including the runtime code... Add that in and it's a little different story.

  8. #8
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    Moreover it would not matter if it is or not
    ^_^

    Awesome.

    I guess it's time to put you back in the old ignore list for another couple of weeks.
    ^_^

    Awesome.

    Soma

  9. #9
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,218
    Quote Originally Posted by CommonTater View Post
    My time was like 400ms with quicksort...
    I find it highly amusing that C# beats out C using C#'s IEnumerable<>.OrderBy() and C's qsort().

    Don't get me wrong. I love C. I just hope the C# bashing can stop now that we've shown what it can do. I think you'll agree that it's more impressive than you were giving it credit.
    If you understand what you're doing, you're not learning anything.

  10. #10
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Quote Originally Posted by itsme86 View Post
    I find it highly amusing that C# beats out C using C#'s IEnumerable<>.OrderBy() and C's qsort().

    Don't get me wrong. I love C. I just hope the C# bashing can stop now that we've shown what it can do. I think you'll agree that it's more impressive than you were giving it credit.
    Yeah... but it's still "baby code".... LOL.

    Seriously though... I am impressed. Especially when you use the optimized sort... There is a hit, but nowhere near as bad as I figured. The last time I did anything like this C# and Java massively sucked by comparison.

    Thanks!

  11. #11
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    python's not bad either, but it appears to be the slowest. I have an Intel P4 CPU though.

    Here's the script:
    Code:
    def foo():
        from random import randrange
        L = [randrange(1,200) for i in range(100000)]
        L.sort()
    
    if __name__ == "__main__":
        foo()
    Here's the profile:
    Code:
    C:\Python27>python -m cProfile "C:\Documents and Settings\Owner\Desktop\sorttest
    .py"
             200052 function calls in 1.136 seconds
    
       Ordered by: standard name
    
       ncalls  tottime  percall  cumtime  percall filename:lineno(function)
            1    0.000    0.000    0.000    0.000 __future__.py:48(<module>)
            1    0.000    0.000    0.000    0.000 __future__.py:74(_Feature)
            7    0.000    0.000    0.000    0.000 __future__.py:75(__init__)
            1    0.002    0.002    0.002    0.002 hashlib.py:55(<module>)
            6    0.000    0.000    0.000    0.000 hashlib.py:91(__get_openssl_constr
    uctor)
            1    0.000    0.000    0.075    0.075 random.py:100(seed)
       100000    0.585    0.000    0.727    0.000 random.py:173(randrange)
            1    0.007    0.007    0.084    0.084 random.py:40(<module>)
            1    0.000    0.000    0.000    0.000 random.py:647(WichmannHill)
            1    0.000    0.000    0.000    0.000 random.py:72(Random)
            1    0.000    0.000    0.000    0.000 random.py:797(SystemRandom)
            1    0.000    0.000    0.075    0.075 random.py:91(__init__)
            1    0.001    0.001    1.136    1.136 sorttest.py:2(<module>)
            1    0.246    0.246    1.135    1.135 sorttest.py:2(foo)
            1    0.000    0.000    0.000    0.000 {_hashlib.openssl_md5}
            1    0.000    0.000    0.000    0.000 {_hashlib.openssl_sha1}
            1    0.000    0.000    0.000    0.000 {_hashlib.openssl_sha224}
            1    0.000    0.000    0.000    0.000 {_hashlib.openssl_sha256}
            1    0.000    0.000    0.000    0.000 {_hashlib.openssl_sha384}
            1    0.000    0.000    0.000    0.000 {_hashlib.openssl_sha512}
            1    0.000    0.000    0.000    0.000 {binascii.hexlify}
            1    0.000    0.000    0.000    0.000 {function seed at 0x00BDB2F0}
            6    0.000    0.000    0.000    0.000 {getattr}
            6    0.000    0.000    0.000    0.000 {globals}
            1    0.000    0.000    0.000    0.000 {math.exp}
            2    0.000    0.000    0.000    0.000 {math.log}
            1    0.000    0.000    0.000    0.000 {math.sqrt}
            1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Prof
    iler' objects}
       100000    0.142    0.000    0.142    0.000 {method 'random' of '_random.Rando
    m' objects}
            1    0.074    0.074    0.074    0.074 {method 'sort' of 'list' objects}
            1    0.075    0.075    0.075    0.075 {nt.urandom}
            1    0.005    0.005    0.005    0.005 {range}
    I guess it does have a space advantage. sorttest.py is a mighty 154 bytes....
    Last edited by whiteflags; 03-06-2011 at 01:47 AM.

  12. #12
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Quote Originally Posted by whiteflags View Post
    python's not bad either, but it appears to be the slowest. I have an Intel P4 CPU though.
    I think you missed the point... We're not comparing optimized sorts, we're comparing languages with exact translations of the C code I provided in the first message...

  13. #13
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Ireland
    Posts
    8,446
    I can see this thread is a followup to some previous debate. It would have been good if that has been mentioned (and where it is). Not everyone necessary follows every single thread on this forums and when replying we may be ignorant of the previous debate and of the whole context for this thread. Seems to have been my case.
    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  14. #14
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,218
    Quote Originally Posted by Mario F. View Post
    I can see this thread is a followup to some previous debate. It would have been good if that has been mentioned (and where it is). Not everyone necessary follows every single thread on this forums and when replying we may be ignorant of the previous debate and of the whole context for this thread. Seems to have been my case.
    You're right. Good point.

    The original post can be found here: New to C : combining lines in text files
    If you understand what you're doing, you're not learning anything.

  15. #15
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Ireland
    Posts
    8,446
    Thanks for the heads up.

    Ah, the old "everything that isn't c or c++ is a toy language" debate.
    Fun... :/

    Did I mention that the London Stock Market uses C# for their entire stock exchange system? Glad I didn't. It could be scary the thought that folks over there were playing with toys. And sure am glad I won't ever mention that I owe Visual Basic my house, my marriage and my general well-being. People could get ideas and think that you don't have to work to make a living, just play around.
    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Challenge Ideas
    By Sedition X in forum General Discussions
    Replies: 4
    Last Post: 01-31-2011, 01:06 AM
  2. AI Challenge
    By unknown_111 in forum General AI Programming
    Replies: 0
    Last Post: 10-02-2007, 12:18 AM
  3. Programming Challenge (for my school)
    By Ezerhorden in forum C++ Programming
    Replies: 2
    Last Post: 01-04-2006, 06:56 AM
  4. Requesting a challenge
    By RealityFusion in forum C++ Programming
    Replies: 8
    Last Post: 08-18-2003, 08:24 PM
  5. Speed Challenge, my solution:
    By RoD in forum C++ Programming
    Replies: 11
    Last Post: 03-17-2003, 09:12 PM