Re: [Discuss-gnuradio] New random number generator

[Marcus Müller]

Hi Stefan,

hehe, I thought you might have an idea how to benchmark memory
consumption. So I'm stuck with this myself :)

What I can definitely say is that the -O3 variant of boost definitely
can't allocate much memory, based on the time it needs -- frequent
allocations would probably have caught my eye.
I'm afraid real numbers are impossible to get without the help of tools
like valgrind, which bend/replace libc/syscalls... and hence stretch the
execution duration massively.
However, I think "/usr/bin/time -v" (the ZSH builtin time isn't as
capable) gives some information, too:
For the boost thing, it says, with little difference between -03 and -O0
(O0 gives 783772 kB, so even a bit more)
    Maximum resident set size (kbytes): 783760
For the GNU Radio-random.h based approach:
-O0 = 789352 kB, -O3 = 789380 kB
Considering that 1e8 complex<float> are 781,250 kB

boost O0 = 2522 kB overhead
boost O3 = 2510 kB overhead
gr::random O0 = 8102 kB overhead
gr::random O3 = 8130 kB overhead

The 5.5MB delta might be explained by the fact that I didn't link
statically (that would've been unfair, I thought), and the gr::random
rtloads a lot libraries.

Greetings,
Marcus


On 02.09.2015 17:12, Stefan Wunsch wrote:
> Hi all,
>
> for me, these results don't look that bad. Consider that the quality of
> the random numbers is increased enormously and with an ordinary
> simulation you loop the period length of the current generator (about
> 1e8 samples) multiple times. The results should be highly correlated if
> you use approximately the same periodicity in your simulation! That is a
> bug that you hardly see at first sight.
>
> It is possible to use the mt11213b generator, but this results only in a
> performance increase of 7% (see boost reference page). I don't think
> that it is worth using this one.
>
> Can you benchmark the used memory with your code (don't know how this
> works)? I think this isn't that important, but would be interesting.
>
> Greetings
> Stefan
>
> On 02.09.2015 15:28, Marcus Müller wrote:
>> Hi Stefan,
>>
>> strange, I was looking at the same code just a few days ago, when I
>> needed to find out whether I understood filters well enough by pushing
>> noise through. Here's my small testcases (thankfully I didn't restart my
>> machine since then -- these were still in /tmp).
>>
>> So, in fact, I tested the performance of boost's mt19937 + boost's
>> normal distribution variate, and basically, it's relatively slow,
>> indeed; generating 1e8 complex random numbers (meaning 200e8 random
>> floats) with a single thread takes
>>
>> g++ (GCC) 5.1.1 20150618 (x86_64)
>>      test_rnd (Boost)
>> g++ -OXXX test_rnd.cpp
>>      test_gr (gr::random)
>> g++ $(pkg-config --cflags --libs gnuradio-runtime) -OXXX te_gr.cpp
>> -O3 (optimized for speed)
>>      1.25 s
>>      5.92 s
>> -O0 (explicitly unoptimized) (default)
>>      23.62 s
>>      7.13 s
>>
>>
>> Someone who cares for speed could get a 5x increase of speed by using
>> boost, because that person would be using optimization, anyways.
>> However, I can't really explain what happens with boost and the
>> unoptimized case; it's really three times as bad as the current
>> implementation.
>> However, asking perf about this, the -O3 version spends nearly all of
>> its time in main(), whereas the -O0 spends most of it in some boost
>> functions -- which means that -O3 definitely inlines the calculations,
>> and from the disassembly alone I'd say all the stack operations needed
>> to jump in and out of routines seem to contribute significantly to the
>> problem.
>>
>> Of course, that's not really a benchmark for all systems. What about 32
>> bit? What about ARM? What about clang? Can anyone try to make a Windows
>> build?
>>
>> Best regards,
>> Marcus
>>
>> On 02.09.2015 14:10, Stefan Wunsch wrote:
>>> Hi!
>>>
>>> I have discovered that the implemented random number generator in
>>> gnuradio (see file [0]) is almost older than me. As written in the code,
>>> the implementation is taken from 'Numerical recipes in C' (see version
>>> from 1992). The problem is that this algorithm is really bad compared to
>>> current algorithms. E.g. the period length is 1e8 compared to an
>>> up-to-date algorithm (Mersenne twister) with a period length of about
>>> 1e6000.
>>>
>>> I have fixed this [1] using boost.random and the mentioned Mersenne
>>> twister. Furthermore I have written some test-cases and fixed the
>>> transformation to Laplacian random numbers (the current implementation
>>> is wrong). As well, I have added the random class to swig so that you
>>> can use this in python.
>>>
>>> Now my question: Before doing a pull request, do you have any concerns
>>> regarding memory use or processing load? Obviously the new
>>> implementation isn't that light-weight as the ten lines of code before.
>>> But the current implementation can not be used in any serious simulation
>>> or publication, which is highly dependent on good random numbers. Some
>>> information about the performance is given on this page: [2]. Look for
>>> the generator mt19937 in table 24.5.
>>>
>>> Best regards
>>> Stefan
>>>
>>> [0] gnuradio/gnuradio-runtime/lib/math/random.cc
>>> [1] https://github.com/stwunsch/gnuradio/tree/newRandom
>>> [2]
>>> http://www.boost.org/doc/libs/1_59_0/doc/html/boost_random/reference.html
>>>
>>> _______________________________________________
>>> 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
>>