Re: [Discuss-gnuradio] fastnoise_source is not thread-safe

[CEL]

Soooo, Markus,

Yep, this works.

As for some background: I build my GNU Radio with
CMAKE_BUILD_TYPE=RelWithDebInfo, which boils down to a reasonable '-g
-O2' using clang. I've built my gr-xoroshiro module with the same
parameters.

It stochastically outperforms the fastnoise_source in Gaussian mode by
orders, up to pool sizes that are roughly equivalent to the sample
size. For more benchmarks refer to [1].

So, I'd argue:

* This is already as least as good as the fastnoise source, but uses
less RAM to achieve the same quality, or is higher-quality when
fastnoise RAM usage is benign
* If I don't use a toy implementation of a normal-shaper, this will
probably perform faster than fastnoise source by orders of magnitude
* This is just demo code; the real RNG is header-only in [2], based on
[3,4] (which is public domain).
* We should fix fastnoise_src by replacing rand() with
xoroshiro128p_next(state), which is threadsafe (if state isn't shared)
* If I'm right and a non-naive normal-shaper performs much better than
averaging, then there's little reason to stick with
boost::random::mt19337 in the (non-fast) noise source, and we can just
replace the algorithm under the hood without API changes, but
increasing the performance enough to deprecate fastnoise source.

To get a feeling for the use case that should be optimized for: What's
your application of the fastnoise source? What is your parameterization
of choice?

Best regards,
Marcus

[1] https://github.com/marcusmueller/gr-xoroshiro/blob/master/examples/
Kolmogorov-Smirnov-Test.ipynb
[2] https://github.com/marcusmueller/gr-xoroshiro/blob/master/include/x
oroshiro/xoroshiro-variates.h
[3] http://vigna.di.unimi.it/xorshift/ 
[4] http://vigna.di.unimi.it/xorshift/xoroshiro128plus.c
On Fri, 2018-01-26 at 16:58 +0000, Müller, Marcus (CEL) wrote:
> Hello Markus,
> 
> just to add to the things said:
> The (non-fast) noise source in GR has experienced a bit of bugfixing
> (but more on a mathematical level: turns out that the built-in random
> function GNU Radio used wasn't all that random if one looked for about
> 10^8 samples)...
> 
> I'm currently reading the fastnoise_source block's code, I'm really not
> all that sure it's *fast*. I mean, neither `rand()` nor `indirectly
> addressing a RAM buffer that's larger than a CPU cache` are really an
> indication for speed. The reason why it's still faster than the noise
> source is that the distribution shaping happens offline (which means
> that probably, our distribution shaping is suboptimal; then again, the
> method used in the generation of normally distributed variables can be
> found all over the internet, probably because it's the method in
> /Numerical Recipes/, and it's a cool method, anyway!).
> 
> That having been said, maybe, instead of just fixing fastnoise source
> (which we must do, I agree!) only, we might simply want to look into
> replacing it by something faster yet threadsafe. I'll whip something up
> for benchmarking purposes; XOROSHIRO128+ has an excellent reputation
> with respect to both speed and statistical properties, and I'd be
> surprised if we couldn't use it to generate both random floats as well
> as random integers. Problem, as usual, is that a good random number
> generator does not make a good source of (pseudo)continuous or even
> just discrete randomness of any given distribution. However, I'm
> willing to test a few reference distributions (mainly, Numpy's, because
> they're easy to use in tests and hopefully well-tested themselves) for
> distributional similarity¹ to the expected distributions, and some
> auto- and crosscorrelation tests.
> 
> So, hm, how do we do this?
> 
> Anyway: Seeing you post on the mailing list lately I'd say it really
> can't hurt letting you sign the FSF CRA; I think you'd greatly benefit
> of having the possibility to quickly upstream a fix, even if it's
> complex. For smaller fixes, a CRA isn't always strictly necessary, but
> your friendly maintainer knows more :)
> 
> Best regards,
> Marcus
> 
> 
> 
> ¹ seriously, I'll have to restrict myself to a Kolmogorov-Smirnov test,
> and maybe Kullback-Leibler divergence considerations. That's all I can
> honestly claim to understand well enough to make qualified statements.
> 
> On Fri, 2018-01-26 at 00:45 +0100, Markus Wirsing wrote:
> > Hello,
> > 
> > I noticed that the fastnoise_source block is not thread safe, as it
> > calls rand(), which keeps global state.
> > This makes it non-reproducable between multiple runs once more than one
> > such source is used.
> > 
> > I also opened an issue about this on github:
> > https://github.com/gnuradio/gnuradio/issues/1542
> > However, there were no reactions to it.
> > 
> > I'm considering to write a fix for it when I find the time.
> > However, I'm not sure about the requirements that need to be met that it
> > can later be included in gnuradio.
> > 
> > Would this already require me to have a CRA?
> > I'm also wondering whether C++11 is allowed in gnuradio.
> > I guess it is not as I found this message on the mailing list:
> > https://lists.gnu.org/archive/html/discuss-gnuradio/2014-06/msg00014.html
> > It might be worth mentioning that on the coding guide in the wiki though:
> > https://wiki.gnuradio.org/index.php/Coding_guide_impl
> > It also might be worth considering to change that rule.
> > C++11 is pretty well supported by now. And it does add some nice features.
> > 
> > I think the easiest fix would be to use random::ran_int() in place of
> > rand() or lrand48(). That way it would also be possible to get rid of
> > the (slightly) biased method of using a linear congruence to reduce the
> > range.
> > 
> > However, while looking at the code in random.cc
> > https://github.com/gnuradio/gnuradio/blob/master/gnuradio-runtime/lib/math/random.cc
> > I noticed that it keeps raw pointers to the different random generators.
> > I don't see why this is done. If I don't misunderstand anything, it
> > would work equally well to have the objects as members in the class.
> > With the added benefit of having them correctly deconstructed in the
> > case of exceptions. Even though that may not be of much relevance in
> > this case.
> > But it at least would make sense to use unique pointers instead of raw
> > pointers.
> > So if I find the time to create a fix for the other problem, would some
> > cleanup in this place be appreciated too?
> > 
> > I have no experience so far with submitting code to open source projects.
> > These issues seem to be a good starting point. However, before investing
> > time, I want to make sure my work can actually be used.
> > 
> > Appreciating any feedback on the proposed changes and on the necessary
> > formalities,
> > Markus
> > 
> > _______________________________________________
> > Discuss-gnuradio mailing list
> > address@hidden
> > https://lists.gnu.org/mailman/listinfo/discuss-gnuradio
> 
> _______________________________________________
> Discuss-gnuradio mailing list
> address@hidden
> https://lists.gnu.org/mailman/listinfo/discuss-gnuradio

smime.p7s
Description: S/MIME cryptographic signature