[c#] CHALLENGE - Beat the time! #2

[Hyperz]

After our previous challenge me and Jay decided to have another go. This time the challenge is to build a RNG (random number generator) based on a existing algorithm and have it generate 100.000.000 random numbers as fast as possible.

Which algorithm is used doesn't matter. As long as it generates good pseudo random numbers. Since the poll showed that we have a few C# coders here I hope others are gonna give this a try as well .

Note:
This challenge is purely for educational purposes and fun. Keep it clean please . Good luck!

Hyperz Reviewed by Hyperz on 20th Jun 2010. [c#] CHALLENGE - Beat the time! #2 After our previous challenge me and Jay decided to have another go. This time the challenge is to build a RNG (random number generator) based on a existing algorithm and have it generate 100.000.000 random numbers as fast as possible. Which algorithm is used doesn't matter. As long as it generates good pseudo random numbers. Since the poll showed that we have a few C# coders here I hope others are gonna give this a try as well :). Note: This challenge is purely for educational purposes Rating: 5

[Hyperz]

I used the MWC algorithm which is well known for its speed and quality. I slightly modified the original C# implementation to one that uses pointers. This in effect speeds up the algorithm by a factor of 20.

The code

using System;
using System.Collections.Generic;
using System.Threading;
using System.Threading.Tasks;
using System.Text;

namespace Hyperz.RGen
{
    public class Program
    {
        public static RGen random = new RGen(1);
        public static Stopwatch sw = new Stopwatch();

        public static void Main(string[] args)
        {
            int amount = 100000000;

            Console.WriteLine("Running...");
            Console.Title = String.Format(
                "RGen Benchmark | Loops : {0:N0} | CPUs : {1}",
                amount, Environment.ProcessorCount);
            
            sw.Start();
            random.GenerateMultiple(amount);
            sw.Stop();

            GC.Collect();
            Console.WriteLine("RESULT: {0}", sw.Elapsed);
            Console.WriteLine("Done.");
            Console.Read();
        }
    }

    public class RGen
    {
        private UInt32 _seedX;
        private UInt32 _seedY;
        private Object _sync;

        public UInt32 SeedX
        {
            get { lock (_sync) return _seedX; }
            set { lock (_sync) _seedX = value; }
        }

        public UInt32 SeedY
        {
            get { lock (_sync) return _seedY; }
            set { lock (_sync) _seedY = value; }
        }

        public RGen(uint? seed = null)
        {
            this._sync = new Object();
            this._seedX = (seed == null) ? (uint)Environment.TickCount : (uint)seed;
            this._seedY = 362436069;
        }

        // Original C# implementaion of the Multiply With Carry algorithm
        //public UInt32 Generate()
        //{
        //    this.SeedX = 36969 * (this.SeedX & 65535) + (this.SeedX >> 16);
        //    this.SeedY = 18000 * (this.SeedY & 65535) + (this.SeedY >> 16);
        //    return (this.SeedX << 16) + (this.SeedY & 65535);
        //}

        // Pointer based implementaion of the Multiply With Carry algorithm (~ 20x faster)
        public unsafe UInt32 Generate()
        {
            fixed (uint* px = &_seedX)
            fixed (uint* py = &_seedY)
            {
                *px = 36969 * (*px & 65535) + (*px >> 16);
                *py = 18000 * (*py & 65535) + (*py >> 16);

                return (*px << 16) + (*py & 65535);
            }
        }

        public UInt32[] GenerateMultiple(int amount, int threadLimit = 32)
        {
            if (amount < threadLimit) threadLimit = 1;

            int amountPerInstance = amount / threadLimit;
            int addToLast = amount - (amountPerInstance * threadLimit);
            bool addOneToLast = (amount & 1) == 1;

            uint[] results = new uint[amount];

            Parallel.For(0, threadLimit, new ParallelOptions() { MaxDegreeOfParallelism = threadLimit }, num =>
            {
                var r = new RGen(this.Generate());
                int count = (addOneToLast && num == threadLimit - 1) ?
                    amountPerInstance + addToLast : amountPerInstance;

                uint[] numbers = new uint[count];

                for (int i = 0; i < count; i++) numbers[i] = r.Generate();
                lock (results) numbers.CopyTo(results, num * amountPerInstance);
            });

            return results;
        }
    }
} 

Result:



0.435 seconds - 100.000.000 random numbers.

There is still room for improvement here. More specifically, the part that balances the load across the available CPU's.

[Hyperz]

Simple single threaded C++ Port:

#include "stdafx.h"
#include <iostream>
#include <ctime>

using namespace std;


double calc_time(clock_t* start, clock_t* stop);
unsigned int generate();
unsigned int seedx = 1;
unsigned int seedy = 362436069;


int main(int argc, char* argv[])
{
    cout << "Running..." << endl;

    clock_t start, stop;
    int amount = 100000000;
    int i = 0;
    
    start = clock();
    for (; i < amount; i++) generate();
    stop = clock();
    
    cout << "RESULT: " << calc_time(&start, &stop) << " sec" << endl;
    cout << "Done." << endl << endl;

    system("pause");

    return 0;
}

double calc_time(clock_t* start, clock_t* stop)
{
    double result = (*stop - *start);
    return result / CLOCKS_PER_SEC;
}

unsigned int generate()
{
    unsigned int* px = &seedx;
    unsigned int* py = &seedy;

    *px = 36969 * (*px & 65535) + (*px >> 16);
    *py = 18000 * (*py & 65535) + (*py >> 16);

    return (*px << 16) + (*py & 65535);
} 

Results in 0.7 seconds running on 1 hardware thread vs 0.45 seconds of the C# example running on 4 hardware threads. I might add threading to this one. That would make it at least 100% faster.

[BadLuckGuy]

Hmm lol never coded in C#.
Which extension do u use to run that code? exe?
And which software do u use to export it?

[jayfella]

BadLuckGuy - We are using Visual Studio 2010 - which compiles to exe yes.

@Hyp - ill post my results a little later - and must say, im a little apprehensive

[Hyperz]

Don't be . My C++ one doesn't count anyway since its not C# .

[jayfella]

Ok - well ill post my progress so far - its taking like 2 seconds to create 10 million random numbers right now, which is extremely slow as we know, due to that one object being the culprit. I am not finished yet i have some tricks yet to be revealed

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

using System.Diagnostics;
using System.Threading;

namespace ConsoleApplication2
{
    class Program
    {

        static Stopwatch sw = new Stopwatch();
        static void Main(string[] args)
        {
            ThreadPool.SetMinThreads(3, 3);
            ThreadPool.SetMaxThreads(3, 3);
            DoWork();
        }

        private static uint m_w  = 521288629;
        private static uint m_z = 362436069;

        private static uint GetUint()
        {
            m_z = 36969 * (m_z & 65535) + (m_z >> 16);
            m_w = 18000 * (m_w & 65535) + (m_w >> 16);
            return (m_z << 16) + (m_w & 65535);
        }

        static void DoWork()
        {
            sw.Start();
            
            for (int i = 0; i <= 10000000; i++)
            {
                ThreadPool.QueueUserWorkItem(new WaitCallback(GenerateIt), (object)i);

                if (i == 10000000)
                    Console.WriteLine(sw.Elapsed.ToString() + " - DONE");
                
            }
            Console.Read();
        }

        static void GenerateIt(object o)
        {
            uint myRnd = GetUint();
            // Console.WriteLine("Thread: " + Thread.CurrentThread.ManagedThreadId.ToString() + " - " + sw.Elapsed.ToString() + " - " + myRnd.ToString());
        }
    }
} 

[SaBteCh]

how u guys learn coding??
i know only html css and in vb6 i can only make a calculator

[jayfella]

Honestly, its all about determination. You just got to want it enough, and one day it will just click and you'll be like "oh, its easy now"

[Hyperz]

I am not finished yet i have some tricks yet to be revealed

Just let us know when to run for cover .

I just threw the code of the C++ version into a little struct so I don't have to keep initializing those 2 pointers for each random number:

#include "stdafx.h"
#include <Windows.h>
#include <iostream>
#include <ctime>
using namespace std;


struct NGen
{
    private:
        unsigned int* px;
        unsigned int* py;
    public:
        unsigned int seedX;
        unsigned int seedY;

    NGen(int* seed)
    {
        seedX = *seed;
        seedY = 362436069;

        px = &seedX;
        py = &seedY;
    }

    unsigned int generate()
    {
        *px = 36969 * (*px & 65535) + (*px >> 16);
        *py = 18000 * (*py & 65535) + (*py >> 16);

        return (*px << 16) + (*py & 65535);
    }
};

double calc_time(clock_t* start, clock_t* stop)
{
    double dResult = (*stop - *start);
    return dResult / CLOCKS_PER_SEC;
}

int main(int argc, char* argv[])
{
    cout << "Running..." << endl;

    clock_t tStart, tStop;
    const int amount = 100000000;
    int i = 0;
    int seed = 1;
    NGen random = NGen(&seed);
    
    tStart = clock();
    for (; i < amount; i++) random.generate();
    tStop = clock();
    
    cout << "RESULT: " << calc_time(&tStart, &tStop) << " sec" << endl;
    cout << "Done." << endl;

    cin.get();
    return EXIT_SUCCESS;
} 

Result: 0.308 seconds. Now on to the threading part. Of course this is cheating at its finest .