May 03, 2012 Re: Fixed-size arrays and randomShuffle() | ||||
---|---|---|---|---|
| ||||
Posted in reply to Vidar Wahlberg | OK, I took a look at your example, and I saw the kind of performance you were seeing. I performed an investigation on what could cause such a disparity and came up with a conclusion. The answer is two things: First of all, as noted above, D's default generator is a mersenne twister RNG. You can emulate Java's RNG like so: auto rng = LinearCongruentialEngine!(ulong, 25214903917uL, 11uL, 2uL^^48uL)(); Once I equalized that, I looked into the various methods that are called and settled in on uniform. https://github.com/D-Programming-Language/phobos/blob/master/std/random.d#L1154 As you can see, there's a division at line 1154 and another at line 1158. This means there's a minimum of two division operations every time uniform is called. Now, normally this isn't a big deal, but if we really want maximum performance, we need to eliminate at least one. If you replace lines 1154-1161 (auto bucketSize ... to return...) with: CountType rnum, result; do { rnum = cast(CountType) uniform!CountType(urng); result = rnum % count; } while (rnum > count && (rnum - result + (count - 1)) < (rnum - result - 1)); return cast(typeof(return)) (min + result); Then the time taken shrinks down to roughly the same (within a tenth of a second) as Java. I'll probably clean this up (and write some comments on how this works) and see about submitting it as a patch unless anyone sees anything wrong with this approach. |
May 03, 2012 Re: Fixed-size arrays and randomShuffle() | ||||
---|---|---|---|---|
| ||||
Posted in reply to Vidar Wahlberg | Vidar Wahlberg: > I'm not sure whether this counts as something that should be reported as a bug/improvement, It's a badly written function (with insufficient unit tests): http://d.puremagic.com/issues/show_bug.cgi?id=8026 Bye, bearophile |
Copyright © 1999-2021 by the D Language Foundation