News for hackers. Stuff that matters.
Re:Algorithms Every Programmer Should Know: Reservoir Sampling by jamiesonbecker on Saturday March 07, 2015 @10:06AM (#9161932)
> Seeding is hard, but once you've done that, generating random numbers is insanely cheap.

Depends on your use case. Generating random numbers is indeed relatively expensive:

    $ time dd if=/dev/zero of=/dev/null bs=1024 count=1M
    1073741824 bytes (1.1 GB) copied, 0.348118 s, 3.1 GB/s
    real    0m0.350s
    user    0m0.092s
    sys     0m0.260s

    $ time dd if=/dev/urandom of=/dev/null bs=1024 count=1M
    1073741824 bytes (1.1 GB) copied, 102.332 s, 10.5 MB/s
    real    1m42.334s
    user    0m0.152s
    sys     1m41.994s
(I7, 3.2.0-4-amd64)
Re:Algorithms Every Programmer Should Know: Reservoir Sampling by IgorPartola on Saturday March 07, 2015 @02:11PM (#9162737)
You are comparing doing nearly nothing vs an PRNG. Presumably, you would spend your computation cycles doing something more useful than generating zeros, at which point I am not certain the difference would be quite so drastic.
Re:Algorithms Every Programmer Should Know: Reservoir Sampling by cperciva on Saturday March 07, 2015 @06:42PM (#9163619)
Your /dev/urandom is astonishingly slow. Is this normal for Linux?
Re:Algorithms Every Programmer Should Know: Reservoir Sampling by SamReidHughes on Sunday March 08, 2015 @10:47AM (#9165711)
Yes. For example, if you choose the encrypted hard drive option when installing Debian, it'll take forever, like, hours and hours, two digit numbers of hours, because it's reading from some /dev/urandom (I presume) to initialize the drive with random data. You can skip that step though. It's way better to do it beforehand using some script that uses something other than /dev/urandom. And maybe, don't put a 1 TB hard drive in a netbook or an older machine.
Re:Algorithms Every Programmer Should Know: Reservoir Sampling by jamiesonbecker on Tuesday March 10, 2015 @02:41PM (#9179703)
btw, your sly remark wasn't lost .. ;)

(fyi, Dr. Colin Percival is an eminent security developer for FreeBSD, author and CEO of the trusted Tarsnap, and developer of the AWS AMI's for FreeBSD; when he takes a whack at Linux's PRNG, he's got some standing to do it from :).)

But, yep, this is normal for Linux.. although, frankly, I'm just glad that we, like FreeBSD, are not taking rdrand at face value (thx Ted T'so!) Perhaps post-seed performance will improve down the road.

Re:Algorithms Every Programmer Should Know: Reservoir Sampling by cperciva on Tuesday March 10, 2015 @06:05PM (#9180993)
I wasn't talking about RDRAND. I can't remember what throughput it gives, and it's a pain to use "live" in that it's allowed to fail and return all zeroes.

The inner loop of a PRNG microbenchmark should be identical to the inner loop of an AES-CTR microbenchmark (or your favourite block cipher or MAC if you prefer a different one) and those are fast these days.