[FFmpeg-devel] [PATCHv3] lavu/lfg: switch to Ziggurat algorithm for normal random number generation (WIP)

[Ganesh Ajjanagadde]

On Sat, Mar 12, 2016 at 12:19 PM, Ganesh Ajjanagadde <gajjanag at gmail.com> wrote:
> Code taken from the Julia project, licensed under MIT:
> https://github.com/JuliaLang/julia/blob/master/base/random.jl, in turn
> derived from: "The Ziggurat Method for generating random variables" - Marsaglia and Tsang.
>
> Paper and reference code: http://www.jstatsoft.org/v05/i08/. This is
> well known to be the fastest method empirically for generating normal random
> variables for a fixed PRNG source.
>
> Note that there are a large number of implementations with
> various tunings, this was one of the simpler ones and also has a friendly
> license.
>
> This results in ~ 3x speedup of random number generation:
> old:
>   15090 decicycles in av_bmg_get,       1 runs,      0 skips
>   13140 decicycles in av_bmg_get,       2 runs,      0 skips
>   10117 decicycles in av_bmg_get,       4 runs,      0 skips
>   [...]
>    2133 decicycles in av_bmg_get,  524268 runs,     20 skips=60.4x
>    2134 decicycles in av_bmg_get, 1048531 runs,     45 skips=61.3x
>    2135 decicycles in av_bmg_get, 2097061 runs,     91 skips=61.9x
>
> new:
>    7650 decicycles in av_gaussian_get,       1 runs,      0 skips
>    5490 decicycles in av_gaussian_get,       2 runs,      0 skips
>    3982 decicycles in av_gaussian_get,       4 runs,      0 skips
>    [...]
>     812 decicycles in av_gaussian_get,  524281 runs,      7 skips
>     813 decicycles in av_gaussian_get, 1048563 runs,     13 skips
>     813 decicycles in av_gaussian_get, 2097131 runs,     21 skips
>
> and accordingly a ~2% speedup in aac encoding (-march=native, Haswell, clang):
>
> old:
> ffmpeg -f lavfi -i anoisesrc -t 300 -y sin_new.aac  5.30s user 0.02s system 99% cpu 5.322 total
> new:
> ffmpeg -f lavfi -i anoisesrc -t 300 -y sin_new.aac  5.16s user 0.03s system 99% cpu 5.198 total
>
> Function added as av_gaussian_get with documentation, minor bumped.
>
> Reviewed-by: Michael Niedermayer <michael at niedermayer.cc>
> Reviewed-by: Reimar Döffinger <Reimar.Doeffinger at gmx.de>
> Signed-off-by: Ganesh Ajjanagadde <gajjanag at gmail.com>

Shelved for now; I would like to get the 64 bit optimized rng in first.
[...]