6 ms·

This test isn't actually a great benchmark between languages because, as the author correctly points out, it's mostly a test of random number generation and pre

by btmorex 13y ago

This test isn't actually a great benchmark between languages because, as the author correctly points out, it's mostly a test of random number generation and presumably all of those languages use libc's random number generator. If you run a quick profile on the C code, you'll find the vast majority of time is spent in libc generating random numbers. To get a fair comparison without completely changing the benchmark, you should probably subtract .3-.4 seconds from each runtime as that's the amount of time spent in random number generation (again presumably all languages use libc's).

pcwalton 13y ago
I would be surprised if Go used libc's random number generator; Go libraries tend to reimplement libc functionality in Go. (This is in contrast to Rust, which usually uses libc.) Indeed it is reimplemented: http://golang.org/src/pkg/math/rand/rng.go http://golang.org/src/pkg/math/rand/rng.go Rust uses a cryptographically secure random number generator (ISAAC) by default, to try to protect users from themselves. This means that the RNG is going to be slower than non-cryptographically-secure random number generators. You can get a non-cryptographic random number generator, but you have to ask for it.
- btmorex 13y ago
  Interesting, although I think that makes the benchmark even less useful because the heart of it (generating random numbers) is not using the same algorithm across languages.
- pbsd 13y ago
  I do believe that there's no reason that any modern language should not have a secure random number generator by default. But while ISAAC is likely fine for this purpose, I'd recommend Salsa20/12 instead (Salsa20/8 would be fine too, but let's be conservative). Salsa20 is parallelizable and can skip ahead arbitrarily, has smaller state, and is fast: on recent processors the amortized time per 32-bit integer is around 8 cycles. It was also thoroughly vetted as an eSTREAM cipher.
  - dbaupp 13y ago
    Rust has XorShift (http://en.wikipedia.org/wiki/Xorshift http://en.wikipedia.org/wiki/Xorshift) as a "secondary" RNG in the standard library, for what it's worth.
  - kibwen 13y ago
    What implementations do you suggest? I'd be happy to bring this up to the developers if there's a chance of speeding up our default RNG with one that's just as safe. Note that it must also be compatible with our MIT/Apache 2.0 dual license.
    - pbsd 13y ago
      SUPERCOP [1] has a bunch of public-domain implementations. [2] is a portable one. To get top speed, you need SIMD, though. The available implementations in SUPERCOP are in (x86) assembly, but they really should be converted to intrinsics to be more portable. I don't know if Rust has intrinsics or some other kind of vector register support. I'd even volunteer to implement Salsa20 on it. [1] http://bench.cr.yp.to/supercop.html http://bench.cr.yp.to/supercop.html [2] https://github.com/floodyberry/supercop/blob/master/crypto_stream/salsa2012/e/merged/e/ https://github.com/floodyberry/supercop/blob/master/crypto_s... [3] https://github.com/floodyberry/supercop/tree/master/crypto_stream/salsa2012/amd64_xmm6 https://github.com/floodyberry/supercop/tree/master/crypto_s...
      - pcwalton 13y ago
        There's support for SIMD in Rust, and the compiler intrinsics that LLVM supports. Inline assembler is supported as well. However, note that the SIMD support will quite possibly change to become more first-class.
    - dbaupp 13y ago
      Note that I'm working on this (slowly), and things of interest can/should be put here: https://github.com/mozilla/rust/wiki/Lib-rand https://github.com/mozilla/rust/wiki/Lib-rand
WalterBright 13y ago
D doesn't use libc's random number generator because the C standard one isn't very random. http://dlang.org/phobos/std_random.html http://dlang.org/phobos/std_random.html Of course, a better random number generator takes longer to compute. The blog's author switched the D version to use libc's random number generator, and got some significant speedups. http://www.reddit.com/r/programming/comments/1ixnf6/benchmarking_roguelike_level_generation_go_rust/cb942jo http://www.reddit.com/r/programming/comments/1ixnf6/benchmar...
danieldk 13y ago
Haskell doesn't use the libc standard number generator. The implementation is here: http://hackage.haskell.org/packages/archive/random/1.0.1.1/doc/html/src/System-Random.html http://hackage.haskell.org/packages/archive/random/1.0.1.1/d... Go's implementation is here and doesn't use the libc generator either: http://golang.org/src/pkg/math/rand/rng.go http://golang.org/src/pkg/math/rand/rng.go Walter Bright has already commented on D. it's mostly a test of random number generation and presumably all of those languages use libc's random number generator In fact, that would be better than benchmarking different PRNG methods, as it's done now ;). Anyway, I think the benchmark is still fair, since the programs use whatever the default implementation for a PRNG is in the language's standard library. Sure, the Haskell program will be faster if you'd usea MWC or MT implementation from Hackage. But you'd expect a standard library to come with a sensible default ;).

by btmorex 13y ago

pcwalton 13y ago

I would be surprised if Go used libc's random number generator; Go libraries tend to reimplement libc functionality in Go. (This is in contrast to Rust, which usually uses libc.) Indeed it is reimplemented: http://golang.org/src/pkg/math/rand/rng.go http://golang.org/src/pkg/math/rand/rng.go Rust uses a cryptographically secure random number generator (ISAAC) by default, to try to protect users from themselves. This means that the RNG is going to be slower than non-cryptographically-secure random number generators. You can get a non-cryptographic random number generator, but you have to ask for it.

btmorex 13y ago
Interesting, although I think that makes the benchmark even less useful because the heart of it (generating random numbers) is not using the same algorithm across languages.
pbsd 13y ago
I do believe that there's no reason that any modern language should not have a secure random number generator by default. But while ISAAC is likely fine for this purpose, I'd recommend Salsa20/12 instead (Salsa20/8 would be fine too, but let's be conservative). Salsa20 is parallelizable and can skip ahead arbitrarily, has smaller state, and is fast: on recent processors the amortized time per 32-bit integer is around 8 cycles. It was also thoroughly vetted as an eSTREAM cipher.
- dbaupp 13y ago
  Rust has XorShift (http://en.wikipedia.org/wiki/Xorshift http://en.wikipedia.org/wiki/Xorshift) as a "secondary" RNG in the standard library, for what it's worth.
- kibwen 13y ago
  What implementations do you suggest? I'd be happy to bring this up to the developers if there's a chance of speeding up our default RNG with one that's just as safe. Note that it must also be compatible with our MIT/Apache 2.0 dual license.
  - pbsd 13y ago
    SUPERCOP [1] has a bunch of public-domain implementations. [2] is a portable one. To get top speed, you need SIMD, though. The available implementations in SUPERCOP are in (x86) assembly, but they really should be converted to intrinsics to be more portable. I don't know if Rust has intrinsics or some other kind of vector register support. I'd even volunteer to implement Salsa20 on it. [1] http://bench.cr.yp.to/supercop.html http://bench.cr.yp.to/supercop.html [2] https://github.com/floodyberry/supercop/blob/master/crypto_stream/salsa2012/e/merged/e/ https://github.com/floodyberry/supercop/blob/master/crypto_s... [3] https://github.com/floodyberry/supercop/tree/master/crypto_stream/salsa2012/amd64_xmm6 https://github.com/floodyberry/supercop/tree/master/crypto_s...
    - pcwalton 13y ago
      There's support for SIMD in Rust, and the compiler intrinsics that LLVM supports. Inline assembler is supported as well. However, note that the SIMD support will quite possibly change to become more first-class.
  - dbaupp 13y ago
    Note that I'm working on this (slowly), and things of interest can/should be put here: https://github.com/mozilla/rust/wiki/Lib-rand https://github.com/mozilla/rust/wiki/Lib-rand

WalterBright 13y ago

D doesn't use libc's random number generator because the C standard one isn't very random. http://dlang.org/phobos/std_random.html http://dlang.org/phobos/std_random.html Of course, a better random number generator takes longer to compute. The blog's author switched the D version to use libc's random number generator, and got some significant speedups. http://www.reddit.com/r/programming/comments/1ixnf6/benchmarking_roguelike_level_generation_go_rust/cb942jo http://www.reddit.com/r/programming/comments/1ixnf6/benchmar...

danieldk 13y ago

Haskell doesn't use the libc standard number generator. The implementation is here: http://hackage.haskell.org/packages/archive/random/1.0.1.1/doc/html/src/System-Random.html http://hackage.haskell.org/packages/archive/random/1.0.1.1/d... Go's implementation is here and doesn't use the libc generator either: http://golang.org/src/pkg/math/rand/rng.go http://golang.org/src/pkg/math/rand/rng.go Walter Bright has already commented on D. it's mostly a test of random number generation and presumably all of those languages use libc's random number generator In fact, that would be better than benchmarking different PRNG methods, as it's done now ;). Anyway, I think the benchmark is still fair, since the programs use whatever the default implementation for a PRNG is in the language's standard library. Sure, the Haskell program will be faster if you'd usea MWC or MT implementation from Hackage. But you'd expect a standard library to come with a sensible default ;).