Single-instruction randomness

static unsigned long next = 1;int myrand(void) {    next = next * 1103515245 + 12345;    return next;}

This generates 32 bits per call. Tweak the multiplication perhaps to avoid a multiply. It's probably possible to generate 5 bits per cycle or perhaps even more.

But I'm having really hard time imagining a situation where this type of PRNG (especially if poor is acceptable) would be too costly.

A run of MT19937 will generate for you 624 words of 31 bits each. That's around 20k random bits. Every 20k loop iterations, you will have to re-run MT19937 again. Is this too heavy for you?

You could use RDTSC. Not a good source of randomness, but it should be ok.

Regards
elFarto

Depending on the preceding code, the carry flag or data on the stack might actually be somewhat `random'. That would be the very fastest and also least portable/safe method.

> Every 20k loop iterations, you will have to re-run MT19937 again. Is this too heavy for you?
Not only that, but also shift right your bit buffer and load the next word if it's zero. Antheus' LCG is probably less heavyweight.
Incidentally, why mention MT19937 when the newer WELL RNG outperforms it in all respects?

> You could use RDTSC. Not a good source of randomness, but it should be ok.
hm, that's not exactly cheap either; RDTSC reciprocal throughput varies between 50 and 100 clocks.

How about unrolling the loop i=1..N times, each copy of which accesses the i-th bit of a number generated via LCG?

How many numbers do you need in your tight loop?

This was briefly touched with the Twister and WELL routines, but it doesn't have to be specific to any algorithm.

Consider using any different RNG to fill an array of random numbers during a less critical time. You can then simply walk over the array in your tight loop. There will be some data cache effects (both positive and negative) with this approach. Assuming a PC with its huge data cache and simple pointer walking over the data, it may fit your needs.

Quote:

Original post by Jan Wassenberg Incidentally, why mention MT19937 when the newer WELL RNG outperforms it in all respects?

What I remembered from the 2006 article is that WELL was slightly slower than MT, although it was orders of magnitude better in terms of distribution.

I only need a single bit per iteration. Generating 32 at a time might be ok with loop unrolling.

The loop is TINY, only a few instructions, so each additional instruction is an appreciable percentage rise.

Also, I should have mentioned that the generated number must be 0 or 1, not just zero/nonzero, because it will be used as an array index.

OK, I give up. What exactly is the loop for? Good optimization requires context.

Quote:

Original post by Jan Wassenberg > Every 20k loop iterations, you will have to re-run MT19937 again. Is this too heavy for you? Not only that, but also shift right your bit buffer and load the next word if it's zero. Antheus' LCG is probably less heavyweight. Incidentally, why mention MT19937 when the newer WELL RNG outperforms it in all respects?

Aw, great, now I have to Google another thing. :)

Quote:

How about unrolling the loop i=1..N times, each copy of which accesses the i-th bit of a number generated via LCG?

Of course, you could apply the same technique to avoid shifting the bit buffer around with MT19937, etc. :) Incrementing a pointer into the buffer every 32 iterations shouldn't be that much of a hardship.

Quote:

What I remembered from the 2006 article is that WELL was slightly slower than MT, although it was orders of magnitude better in terms of distribution.

Ah. I am given to understand that the reference code that would've been mentioned in that article is rather slow. http://www.lomont.org/Math/Papers/2008/Lomont_PRNG_2008.pdf (which appeared in one of the Game Programming Gems IIRC) presents a better implementation. An advantage of the WELL algorithm is that its state fits in a single cache line, for which one could begrudge a bit of extra computation. However, the WELL implementation is reported to outperform the reference MT code.

> Generating 32 at a time might be ok with loop unrolling.
hm, unrolling 32x is rather excessive, I would worry about icache and ITLB coverage.

Quote:

Of course, you could apply the same technique to avoid shifting the bit buffer around with MT19937, etc.

True, but wasting bits matters much less in the case of the already cheap LCG than with the rather expensive MT19937 regeneration.
(Avoiding such waste leads to either the above or below problem).

Quote:

Incrementing a pointer into the buffer every 32 iterations shouldn't be that much of a hardship.

Doing an increment 1/32 of the time is much less of an issue than checking if the work needs to be done (branch misprediction rate >= 3% isn't great, and branchless increments would add at least two instructions to every iteration).

Quote:

Original post by spraff I only need a single bit per iteration. Generating 32 at a time might be ok with loop unrolling. The loop is TINY, only a few instructions, so each additional instruction is an appreciable percentage rise. Also, I should have mentioned that the generated number must be 0 or 1, not just zero/nonzero, because it will be used as an array index.

unsigned int r = 1;while (true) {  unsigned int r = rand(); // use whichever rand function you want  // or  // r *= 1103515245;  // r += 12345;  for (int i = 0; i < 32; i++) {    foo[ r & 1 ];    r >>= 1;  }}

This is about as simple as it gets simply because fact that you need a single bit doesn't really help. For any non-trivial algorithm that really(?) needs to be this fast, running out of registers is going to be much bigger problem.

Anything else would require rethinking the algorithm in the first place.

You probably have a counter somewhere in your loop, so you can use it. Updating the state variable h takes three operations, and they can probably be done in parallel with your use of the bit b. Of course, you still haven't told use what the loop does...

The context is that this loop traverses a large data structure, "indexing" (sort of) it into a binary tree for later use.

At each node the children can be in either order without affecting the results.

The source data has nodes of higher degree than two and these are represented by splitting nodes as often as is neccessary. The incremental nature of the construction means that if you always split on one side then it degenerates to a linked list.

Thus to make the tree balanced I need to select left/right approximately 50% of the time each.

(You might be wondering why the order of the children doesn't matter, but that's another story :-p )

The loop operation is basically a couple of variable assignments and a trivial custom-made allocator. In this function a PRNG could easily dominate the processing time, and loop unrolling doesn't really fit since it's more a recursive procedure than an iterative one.

Quote:

Original post by spraff In this function a PRNG could easily dominate the processing time

Could?

Does it in my example? I'm curious.

PS. For allocator, you need a separate variable which counts the shifts, but it shouldn't really matter much.

I'd still be surprised if such algorithm would show up in profiles, considering that allocator will likely suffer from cache misses more in the long run.

A LCG should be fine then. If you really don't want to deal with the extra load/stores, then a simple hash of pointer values of the nodes should be random enough.

Quote:

Original post by Jan Wassenberg Incidentally, why mention MT19937 when the newer WELL RNG outperforms it in all respects?

Will it also outperform SIMD Oriented Fast Mersenne Twister?

I don't know, have not tried it. It looks like they only need about half as many instructions, but (SF)MT19937's long period (naturally) comes at the cost of large internal state. The algorithm probably looks better in microbenchmarks than in the real-world, where I'd be rather skeptical of using up to 27K of precious L1 for the RNG. (reminds me of NVidia's "fast" sqrt() with 256K LUTs, heh) If you're doing Monte-Carlo with a tiny working set and actually need such a large period, then it's probably useful.

So, would it be fair to say that the code in question is creating a binary tree from an n-ary tree?
It's a little unclear what "splitting" involves in your code. If an n-ary node has say 5 children, does "splitting it on one side" mean that you divide this into 1 and 4, or 4 and 1? If this is what you're doing, have you considered that it may be better to split into 2 and 3, or 3 and 2 and 3 and perform recursive calls on both halves?
If I'm not understanding right could you elaborate, and if possible give a simple example please?