[Haskell-cafe] Generate random UArray in constant memory space.

Vasyl Pasternak vasyl.pasternak at gmail.com
Wed Feb 10 08:29:59 EST 2010


Hi all,

To summarize everything in this thread I've tested mwc-random,
System.Random and mersenne random numbers (mersenne-random-pure64).
Here the score table:

[THIRD PLACE] Generic Random Number Generator. Is the slowest and
allocates too much memory in the heap. The total memory usage is
constant and very low.

[SECOND PLACE] MWC-RANDOM. The fastest random number generator ever.
But it uses O(n) memory for generate random numbers. Thought it isn't
possible to calculate a really large set of random numbers (my PC
stuck with calculating 500 millions random numbers with memory usage
above 3,5Gb). The memory usage for me is more important than time,
because I can easily wait additional 5-10-15 mins, but I cant so
easily put additional memory to my PC. Thus this is only second place.

[FIRST PLACE] Mercenne Random number generator. Approx 10 times faster
than generic and two times slower than mwc. But it works in constant
memory space, so theoretically it could generate infinite list of
numbers. It also uses 6 time less total allocations, than generic RNG.

NOTE: These tests didn't test the quality of the random sequences,
only speed/memory.

Thanks to everyone, who helped me with this code, it seems, that now I
understand optimizations much better, than a day ago.

Best regards,
Vasyl

2010/2/10 Felipe Lessa <felipe.lessa at gmail.com>:
> On Tue, Feb 09, 2010 at 04:27:57PM -0800, Bryan O'Sullivan wrote:
>> It creates and returns a vector, so if you ask it to give you a billion
>> items, it's going to require north of 8 gigabytes of memory. This should not
>> come as a surprise, I'd hope :-)  Assuming that's not what you actually
>> want, you should look at other entry points in the API, which you can use to
>> generate a single value at a time in constant space.
>
> He thought the vector would be fused away by the library, which
> is one of the selling points of uvector.  Sadly the
> implementation of uniformArray wasn't done with this purpose in
> mind.
>
> --
> Felipe.
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>


More information about the Haskell-Cafe mailing list