Now here's something amazing. I just added 64-bit integer support to this module, and the speed went way up! I got a 66% speed improvement!

I don't think it has to do with the 64-bit version of the Mersenne Twister algorithm, as it runs through essentially the same code as the 32-bit version (just using different constants). In fact, the 64-bit version has to refresh the random number buffer twice as often, so it's actually doing more work.

One source of improvement may be better utilization of the CPU (Pentium 4) with everything getting done in 64-bit mode to match the CPU registers.

Another may be that since my Perl is compiled with 'use64bitint', it may be using the 64-bit ints from the PRNG directly, and not having to convert them from 32-bits (output of the old PRNG) to 64-bits (Perl's internal representation). (Not sure about this.)

Regardless, it was totally unexpected. Mayhaps this could be a lesson for other Perl XS hackers.