C# Performance

[lucasart]

'Best' is a slippery word. If I wanted a cryptographically secure PRNG I wouldn't use KISS, I would use something stronger. But, if I wanted to bang out good PRNs as quickly as possible, then KISS would be a good choice. Keep in mind that MersenneTwister would also be a very good choice.

I don't understand the link between cryptography and RNG. All we want is an RNG that is relatively fast and easy to code (that excludes the mersenne twister right away), and that passes all known statistical tests. As far as I know the KISS RNG that I use in DoubleCheck passes all known statistical tests and is very simple. Another example is the KISS generator in Stockfish. Here's what I use in DoubleCheck, I would be glad if you could provide an example of statistical test where this generator fails, and where another one succeeds:

Code: Select all

uint64_t rand64()
// JLKISS 64-bit RNG, by Pr. David Jones, UCL Bioinformatics Lab
{
	// seed variables
	static uint64_t x = 123456789123ULL, y = 987654321987ULL;
	static uint32_t z1 = 43219876, c1 = 6543217, z2 = 21987643, c2 = 1732654;

	x = 1490024343005336237ULL * x + 123456789;
	y ^= y << 21; y ^= y >> 17; y ^= y << 30;	// do not set y=0

	uint64_t t;
	t = 4294584393ULL * z1 + c1; c1 = t >> 32; z1 = t;
	t = 4246477509ULL * z2 + c2; c2 = t >> 32; z2 = t;

	return x + y + z1 + (&#40;uint64_t&#41;z2 << 32&#41;;	// return 64-bit result
&#125;

Note that Mersenne Twister passes all known statistical tests, but fails in some linear complexity tests. This is not an issue for chess programming (as all the RNG are drawn at the start of the program once and for all). But the real issue I have with MT is that it's obfuscated, while KISS generators are much simpler (and faster) and perform just as well (speed aside where they beat MT anytime)

[Richard Allbert]

Hi Lucas,

Do you have some examples of the tests?

I have a C Mersenne twister 64bit number generator, so could also use that. But if there are some tests I could use it would be interesting to compare the different generation schemes.

Richard

[Ron Murawski]

'Best' is a slippery word. If I wanted a cryptographically secure PRNG I wouldn't use KISS, I would use something stronger. But, if I wanted to bang out good PRNs as quickly as possible, then KISS would be a good choice. Keep in mind that MersenneTwister would also be a very good choice.

I don't understand the link between cryptography and RNG. All we want is an RNG that is relatively fast and easy to code (that excludes the mersenne twister right away), and that passes all known statistical tests. As far as I know the KISS RNG that I use in DoubleCheck passes all known statistical tests and is very simple. Another example is the KISS generator in Stockfish. Here's what I use in DoubleCheck, I would be glad if you could provide an example of statistical test where this generator fails, and where another one succeeds:

Code: Select all

uint64_t rand64()
// JLKISS 64-bit RNG, by Pr. David Jones, UCL Bioinformatics Lab
{
	// seed variables
	static uint64_t x = 123456789123ULL, y = 987654321987ULL;
	static uint32_t z1 = 43219876, c1 = 6543217, z2 = 21987643, c2 = 1732654;

	x = 1490024343005336237ULL * x + 123456789;
	y ^= y << 21; y ^= y >> 17; y ^= y << 30;	// do not set y=0

	uint64_t t;
	t = 4294584393ULL * z1 + c1; c1 = t >> 32; z1 = t;
	t = 4246477509ULL * z2 + c2; c2 = t >> 32; z2 = t;

	return x + y + z1 + (&#40;uint64_t&#41;z2 << 32&#41;;	// return 64-bit result
&#125;

Note that Mersenne Twister passes all known statistical tests, but fails in some linear complexity tests. This is not an issue for chess programming (as all the RNG are drawn at the start of the program once and for all). But the real issue I have with MT is that it's obfuscated, while KISS generators are much simpler (and faster) and perform just as well (speed aside where they beat MT anytime)

I was commenting on the KISS generator (from 1993), not the JLKISS generator you are actually using, which is quite different. When you said "KISS" I thought you meant "KISS", not "JLKISS". I have not used JLKISS, so I cannot comment on the quality of the generated numbers. But, I notice that the generator is seeded with constants. Your 'random' series of numbers will always be the same. This repeatability is good for Zobrist keys, but is very bad if you are going to use it to choose moves from the opening book. Your book moves will always be the same!

FYI here is an article about the problem with the original KISS PRNG that I was referring to:
http://eprint.iacr.org/2011/007.pdf

I've used ISAAC PRNG for several projects and it worked quite well for me.
http://burtleburtle.net/bob/rand/isaacafa.html

here's a small, fast PRNG:
http://burtleburtle.net/bob/rand/smallprng.html

I don't actually use MersenneTwister, it's just that I've noticed MT in the source code of two different languages (Python and Vala). Your comment of "whatever you do, never use the random generator of C#" seems very strong to me. I'm sure that the PRNG in C# is much better than you think it is.

My main beef with PRNGs shown on the Internet is that they rarely have any consideration for proper seeding. They are initialized with constants or time-of-day. If you want to avoid repeatability you cannot initialize with constants. If you want to choose seeds with maximum variance (ie: seeds that are truly random), then you will find that time-of-day has many predictable digits (the ones that represent year, month, and day). Instead of time-of-day you will want to use the system entropy functions that are available on Windows and Linux. These functions return an unpredictable series of random bytes suitable for use as seeding values.

[lucasart]

Your 'random' series of numbers will always be the same. This repeatability is good for Zobrist keys, but is very bad if you are going to use it to choose moves from the opening book. Your book moves will always be the same!

Yes, I know, that's my intention, as I only use it for zobrist purposes. I don't have an internal book nor do I plan to ever do it (it's the job of the GUI).

here's a small, fast PRNG:
http://burtleburtle.net/bob/rand/smallprng.html

Yes, a very good one indeed: simple, fast and good enough for all practical purposes. The one used by Stockfish (attributed to Heinz Van Saanen) is basically the same thing but with 64 bit i/o 32. And that's what I use now, because it's so simple and neat. I just rewrote the code in C (was C++) and seeded it with JLKISS64 values. That should be amply sufficient for zobrist keys

Code: Select all

static inline uint64_t rol(uint64_t x, unsigned k)
&#123; return &#40;x << k&#41; | &#40;x >> &#40;64 - k&#41;); &#125;

uint64_t rand64&#40;)
// 64-bit KISS RNG by Heinz Van Saanen
&#123;
	static uint64_t	// seeds
		a = 0x5bc5cd8748be9fe8,
		b = 0x5164ed10aa17c81,
		c = 0x105730377a2a0e9c,
		d = 0xe6b137acae0d8b76;
	
	const uint64_t e = a - rol&#40;b,  7&#41;;
	a = b ^ rol&#40;c, 13&#41;;
	b = c + rol&#40;d, 37&#41;;
	c = d + e;
	return d = e + a;
&#125;

Your comment of "whatever you do, never use the random generator of C#" seems very strong to me. I'm sure that the PRNG in C# is much better than you think it is.

Maybe it is, and maybe it isn't on another implementation of C#. For example I know that MSVC++ uses a 32 bit LCG and returns only 15 bits in C/C++. Many (if not all) programming languages have PRNG with known flaws. Of course some implementations may be good, but you don't know and need to have control over it, which is why I recommend always coding it yourself.

[RoadWarrior]

Apologies for not replying sooner - I've been sick with the flu.

PS: whatever you do, never use the random generator of C#. All known programming languages' random generator are flawed, and some are *severly* flawed. The best RNG these days are the KISS family. Also for portability, as a different implementation of C# will most likely have a different RNG.

C# itself doesn't have a random number generator. Instead it can use several supplied with the .NET base class library. The standard one that everybody uses is System.Random. I don't recommend using this - see this StackOverflow answer for some reasons why.

IMO the best random number generator from a C# perspective is System.Security.Cryptography.RNGCryptoServiceProvider. It passes every statistical test that I've applied.

[Richard Allbert]

Btw, Mark, I meant to tell you - I had a big improvement (iirc +600knps, around 25%) by making the move just an int, and bit shifting the squares, pieces, flags so a move looks like so

Code: Select all

            0000 0000 0000 0000 0000 1111 1111 -> FROM
            0000 0000 0000 1111 1111 0000 0000 -> TO
            0000 0001 1111 0000 0000 0000 0000 -> CAPTURED
            0011 1110 0000 0000 0000 0000 0000 -> PROM
            1100 0000 0000 0000 0000 0000 0000 -> FLAG

Richard

[RoadWarrior]

Btw, Mark, I meant to tell you - I had a big improvement (iirc +600knps, around 25%) by making the move just an int, and bit shifting the squares, pieces, flags so a move looks like so

Code: Select all

            0000 0000 0000 0000 0000 1111 1111 -> FROM
            0000 0000 0000 1111 1111 0000 0000 -> TO
            0000 0001 1111 0000 0000 0000 0000 -> CAPTURED
            0011 1110 0000 0000 0000 0000 0000 -> PROM
            1100 0000 0000 0000 0000 0000 0000 -> FLAG

Richard

I tried that a while ago, but it only gave me a 5% speed-up at the time. I thought it wasn't worth having to do the bit-twiddling. But I have this in an open Mercurial branch, so I can merge it into the default branch at any time in order to see if there's been any change. DVCS is just great for chess programming, where we spend so much time testing and combining dozens of experiments.

BTW, I've started on Zobrist hashing. The random key generation stuff looks something like:

Code: Select all

using System.Security.Cryptography;

RNGCryptoServiceProvider randomGenerator = new RNGCryptoServiceProvider();
byte[] randomBytes = new byte[8];

randomGenerator.GetBytes(randomBytes);
SideToMoveKey = BitConverter.ToUInt64(randomBytes, 0);
............

[diep]

That should also avoid all those "boxing" issues ...
Sven

Well, I learned something new today. Like a lot of developers, I believed that C# values (i.e. instances of a value type like a struct) are stored on the stack unless they're boxed, in which case they're stored on the heap.

It appears my belief was wrong. Eric Lippert (C# compiler guru) says that what actually happens is that values are stored in storage locations, and storage locations are either short-lived or long-lived. If the analysis of a storage location shows that its lifetime is guaranteed to be short, that storage location goes on the stack or in registers. Otherwise it goes on the heap.

Of course, boxing will always create a copy of the value on the heap, regardless of where it was originally stored.

I'm not sure what effect this might have on the "long-lived" approach to storing moves and other information that you described. I'm going to run some tests with Amaia.

Optimization in C# seems more complex than in C.

Not surprisingly. Usually microbenchmarks you can keep speed difference under control. Factor 4 or so slower than well written C.

The real problem comes of course when a program grows a tad bigger.

Yet if i see the struggle here, then i'm glad i program in C

Vincent

[diep]

It looks like I use the same compiler optimisation settings (for a release build) as you.

See my blog entry here [1] for a.NET Framework class that will give you cryptographically-secure pseudo-random numbers in C#. This will be more than adequate, as long as you avoid modulo bias using the technique mentioned in the article.

[1] http://sleeksoft.co.uk/public/techblog/ ... 316_1.html

'cryptographically-secure pseudo-random'
that's a huge sentence, tough to parse for me, especially for Bill Gates toylanguage.

uhhhh?

What's the difference with a RNG?

[diep]

Apologies for not replying sooner - I've been sick with the flu.

PS: whatever you do, never use the random generator of C#. All known programming languages' random generator are flawed, and some are *severly* flawed. The best RNG these days are the KISS family. Also for portability, as a different implementation of C# will most likely have a different RNG.

C# itself doesn't have a random number generator. Instead it can use several supplied with the .NET base class library. The standard one that everybody uses is System.Random. I don't recommend using this - see this StackOverflow answer for some reasons why.

IMO the best random number generator from a C# perspective is System.Security.Cryptography.RNGCryptoServiceProvider. It passes every statistical test that I've applied.

Can it also pass the O (n log n) extra terrestrial test i designed?

Say there that you're a highly intelligent civilization from outer space. You want to communicate with other civilizations - yet only the more developed ones. So you encrypt your communication in a manner that you are sure of that developed civilizations can decrypt. Say a civilization from which you are sure that if they can decrypt it they also already for a while could have nuked their own planet a few times - so you know for sure they're peaceful.

How to detect the difference between true randomness and encrypted data then?

My layman guess there would be the looking whether the spread is too perfect.

Most RNG's are very flawed in one manner - they have a truely perfect spread under theta (n log n)

Say we take a big block of RAM and use all bits there. For example we use it of size 2^n entries with n pretty large (and of course 8 bits per byte), though it would be interesting to use also modulo some large prime, but that's another issue. So we have p = 2^n entries.

Now from the RNG we do this: x = rng() % p;
And we set the bit to 1.

If now entire block within O ( n log n ) is 100% filled with ones, with a rather large block that is an indication of a RNG rather than naturally random primes.

Again this is a heuristic - not an absolute truth

And it's the Diepeveen extra terrestrial test baptized as such by me.

Nearly all the 'reasonable' or 'good' RNG's suffer from this problem. They have a too perfect spread