Latest Announcemnent
New thread

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

Status
Not open for further replies.
Hyperz

Hyperz

Active Member
Veteran
2,428
2009
575
13,815
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!
 
22 comments
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
PHP: 
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:

2bdc00rng.png


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.
 
Simple single threaded C++ Port:
PHP: 
#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.
 
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 :p i have some tricks yet to be revealed >_>

PHP: 
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());
        }
    }
}
 
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" :D
 
jayfella said:
I am not finished yet :p i have some tricks yet to be revealed >_>
Click to expand...

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:

PHP: 
#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 :whistle:.
 
Just 2 participants ? :P guys plz start from a low level programing n language like c++ so that every can participate :D

thanx y0....n yeah nice idea there by Hyperz n Jay ;) will make people do something more than Css n php shit :P
 
Decided to give this a go :)

The code:
PHP: 
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace WJ_RandomNumberGenerator
{
    class Program
    {
        static Stopwatch sw = new Stopwatch();
        static Random rnd = new Random();


        static void Main(string[] args)
        {
            sw.Start();
            for (int i = 0; i <= 10000000; i++)
            {
                getRand();
            }
            Console.WriteLine(sw.Elapsed.ToString() + " - Whoo");
            Console.ReadLine();
        }

        private static void getRand()
        {
            int lol = ((rnd.Next() * 1103515245) + 12345) & 0x7fffffff;
        }
    }
}

The result:
[slide]http://i47.tinypic.com/167qfsk.png[/slide]
 
well the whole point is to do it over more than one thread - which is in fact riddled with obstacles - but great attempt - also, the reason we arent using static Random is because its slow as hell. Instead we use a known "pseudo random" algorythm.

Hint 1: Using the same object "rnd" over multiple threads will yeild the same random number because it uses TickRate as the seed - and because the calculations are done so fast, the tickrate doesnt even get a chance to change before 50-100 random numbers are generated, and thus you get the same "random number" (assuming you already know PC's can only produce "fake random")

But thanks for joining the challenge - keep going :)
 
jayfella said:
well the whole point is to do it over more than one thread - which is in fact riddled with obstacles - but great attempt - also, the reason we arent using static Random is because its slow as hell. Instead we use a known "pseudo random" algorythm.

Hint 1: Using the same object "rnd" over multiple threads will yeild the same random number because it uses TickRate as the seed - and because the calculations are done so fast, the tickrate doesnt even get a chance to change before 50-100 random numbers are generated, and thus you get the same "random number" (assuming you already know PC's can only produce "fake random")

But thanks for joining the challenge - keep going :)
Click to expand...
Thanks for the hint jaydude =)

I posted it because even though I used the Random class, it still generates them a bit faster than the first results of Hyperz. I printed out a few numbers and they look like this more or less:

1317421276
1968034171
612093081
970587761
1608097552
1713051480
85828884
752998216
Click to expand...

Quite sufficient IMO but as you said it wouldn't be able to spread across different threads.
 
10.000.001 != 100.000.000 Whoo ;).

Btw, what's the logic behind:
Code: 
((rnd.Next() * 1103515245) + 12345) & 0x7fffffff
I mean, is that randomly hitting the keyboard or is there a reason for slowing it down?

Edit:
And also your function doesn't return the result(s) >_>
 
But there is no seed involved >_>. Random uses Environment.TickCount by default. And the output of Next() is already random. Is ((rnd.Next() + 1) ^ 0) more random than random :p?
 
Aaaaaaaahhhhh OMG OMG OMG :o
Visual Studio Ultimate is of 12 THOUSAND DOLLARS :o :O
Is there any software more expensive than this? :))
 
Status
Not open for further replies.
Back
Top