1.36.0 boost/random/uniform_01 Infinite[?] Loop
I'm sure everyone will think I'm crazy, but here goes... Background: I came across this problem while developing a proof of concept for my master's project. It entails generating random numbers according to either a uniform or a normal distribution. I wrote a few wrapper classes to simplify dealing with the generators and distributions. Those wrapper classes let me do this: randomGenerator *rg; if(uniformDistribution) rg = new uniformGenerator(); else rg = new normalGenerator(); (I also have constructors that take arguments to alter the range of values, but I'm not using them presently.) Then I can retrieve values like so: (*rg)() uniformGenerator and normalGenerator inherit from randomGenerator, and are wrappers for these: boost::variate_generator<boost::minstd_rand&, boost::uniform_real<> > boost::variate_generator<boost::minstd_rand&, boost::normal_distribution<> > I currently have two programs that use those wrapper classes. One is fairly minimal; it simply parses some command line arguments that affect the distribution and quantity, then retrieves the values and prints them to stdout. The other program is my proof of concept; it does the same argument parsing (with a few more options), then makes use of the values to run my simulation, which is mostly manipulating STL containers. Problem: Now we come to the crazy part. I work mostly on one of two Windows machines, using g++ under Cygwin. On either machine, both of those programs run to completion every time, if I compile with -O1, -O2, or -O3. However, if I use -O0 (or just no -O argument), then the simulation locks up. The other program---that just prints random numbers---never locks up. (Incidentally, this program was my attempt to create a minimal program that replicated the behavior.) By single-stepping with gdb, I determined that it gets stuck in boost/random/uniform_01.hpp: 58 for (;;) { 59 result_type result = result_type(_rng() - (_rng.min)()) * _factor; 60 if (result < result_type(1)) 61 return result; 62 } gdb shows that result is always equal to 1, which of course leads to an infinite loop. Single-stepping through all of the code directly related to the random generators shows the same sequence of instructions for both programs. If I use the uniform distribution, it gets stuck when I try to retrieve the second value. If I use the normal distribution, it gets stuck on the third retrieval. Also worth noting, by default the generators are supplied with a different seed value every time I run either program. Getting back to the programming environment, when I build on the Solaris machines in my school's CS department, the program never gets stuck. For my part, it's exactly the same source, and I still use g++. I have not been able to coerce any warnings or errors from the compiler. So, I'm all out of ideas. I'm open to suggestions for fixing this, but I'm hoping the solution is less extreme than compiling gcc from source.
Dave Steenburgh schrieb:
58 for (;;) { 59 result_type result = result_type(_rng() - (_rng.min)()) * _factor; 60 if (result < result_type(1)) 61 return result; 62 }
Could you show the generated assembler for this as well? Or better, a minimal example to try? Which version of GCC are you using (exactly)? Cheers, Anteru
Could you show the generated assembler for this as well?
I should definitely learn a better method for getting this info, and having unmangled names would be nice, too. This boost code: result_type operator()() { for (;;) { result_type result = result_type(_rng() - (_rng.min)()) * _factor; if (result < result_type(1)) return result; } } Is compiled to this: __ZN5boost10uniform_01INS_6random6detail19pass_through_engineIRNS1_19linear_congruentialIlLl48271ELl0ELl2147483647ELl399268537EEEEEdEclEv: .stabn 68,0,57,LM909-__ZN5boost10uniform_01INS_6random6detail19pass_through_engineIRNS1_19linear_congruentialIlLl48271ELl0ELl2147483647ELl399268537EEEEEdEclEv LM909: pushl %ebp # movl %esp, %ebp #, pushl %ebx # subl $20, %esp #, L840: LBB361: LBB362: LBB363: LBB364: LBB365: .stabn 68,0,59,LM910-__ZN5boost10uniform_01INS_6random6detail19pass_through_engineIRNS1_19linear_congruentialIlLl48271ELl0ELl2147483647ELl399268537EEEEEdEclEv LM910: movl 8(%ebp), %eax # this, this movl %eax, (%esp) # this, call __ZN5boost6random6detail19pass_through_engineIRNS0_19linear_congruentialIlLl48271ELl0ELl2147483647ELl399268537EEEEclEv # movl %eax, %ebx #, tmp60 movl 8(%ebp), %eax # this, this movl %eax, (%esp) # this, call __ZNK5boost6random6detail19pass_through_engineIRNS0_19linear_congruentialIlLl48271ELl0ELl2147483647ELl399268537EEEE3minEv # subl %eax, %ebx # tmp62, movl %ebx, %eax #, tmp63 pushl %eax # tmp63 fildl (%esp) # leal 4(%esp), %esp #, movl 8(%ebp), %eax # this, this fmull 8(%eax) # <variable>._factor fstpl -16(%ebp) # result .stabn 68,0,60,LM911-__ZN5boost10uniform_01INS_6random6detail19pass_through_engineIRNS1_19linear_congruentialIlLl48271ELl0ELl2147483647ELl399268537EEEEEdEclEv LM911: fldl -16(%ebp) # result fld1 fucompp fnstsw %ax # sahf ja L843 #, jmp L840 # L843: .stabn 68,0,61,LM912-__ZN5boost10uniform_01INS_6random6detail19pass_through_engineIRNS1_19linear_congruentialIlLl48271ELl0ELl2147483647ELl399268537EEEEEdEclEv LM912: fldl -16(%ebp) # result LBE365: LBE364: LBE363: LBE362: LBE361: addl $20, %esp #, popl %ebx # popl %ebp # ret
Or better, a minimal example to try?
I wish I had one, because then I might be submitting a bug report instead of asking for help. When I stripped out everything except the retrieval of random numbers, it worked fine, so obviously I went too far. I'll see what I can do...
Which version of GCC are you using (exactly)?
g++ --version reports: g++ (GCC) 3.4.4 (cygming special, gdc 0.12, using dmd 0.125)
Or better, a minimal example to try? I'd like to think I know what the problem is now, but I'm still a little mystified, and I'm not sure how best to correct it. What I think I want is a correction to or replacement for my wrapper class, but I definitely want a second opinion. (Maybe a third and a fourth, too...)
I've got a minimal-ish program that exhibits strange behavior, but it doesn't get stuck. I suspect the same phenomenon is at work here, though, since it still only appears when compiling without optimization. The source is attached, and here are some of my observations: If I use ng instead of vg, there is no problem. (Try it yourself; just move the comment slashes.) If I omit the call to problemFunction, everything works. If I decrease the number of arguments problemFunction requires, everything works. Based on that info, my guess is that something the random generator needs is created on the stack, and later overwritten. However, I think if that were really the problem, it would still be a problem on another platform, or with optimizations enabled. The printHistogram function is mostly unchanged from my original program, and I kept it in this example because it makes the problem quite apparent. It prints data that can be used to create a histogram. Each line contains two numbers; the first represents the minimum value of a histogram "bin," the second is a count of the values that fit in that bin. When everything works correctly, the output should show a normal distribution. When this problem manifests itself, the results always look a lot like this: -1.30211,1 -1.27878,0 -1.25546,0 -1.23213,0 -1.2088,0 -1.18547,0 -1.16215,0 -1.13882,0 -1.11549,0 -1.09216,0 -1.06884,0 -1.04551,0 -1.02218,0 -0.998856,0 -0.975528,0 -0.952201,0 -0.928874,0 -0.905546,0 -0.882219,0 -0.858892,0 -0.835565,0 -0.812237,0 -0.78891,0 -0.765583,0 -0.742255,0 -0.718928,0 -0.695601,0 -0.672274,0 -0.648946,0 -0.625619,0 -0.602292,0 -0.578964,0 -0.555637,0 -0.53231,0 -0.508983,0 -0.485655,0 -0.462328,0 -0.439001,0 -0.415673,0 -0.392346,0 -0.369019,0 -0.345692,0 -0.322364,0 -0.299037,0 -0.27571,0 -0.252382,0 -0.229055,0 -0.205728,0 -0.182401,0 -0.159073,0 -0.135746,0 -0.112419,0 -0.0890915,0 -0.0657642,0 -0.0424369,499 -0.0191097,0 0.00421763,0 0.0275449,0 0.0508722,0 0.0741995,0 0.0975268,0 0.120854,0 0.144181,0 0.167509,0 0.190836,0 0.214163,0 0.23749,0 0.260818,0 0.284145,0 0.307472,0 0.3308,0 0.354127,0 0.377454,0 0.400781,0 0.424109,0 0.447436,0 0.470763,0 0.494091,499 0.517418,0 0.540745,0 0.564072,0 0.5874,0 0.610727,0 0.634054,0 0.657382,0 0.680709,0 0.704036,0 0.727363,0 0.750691,0 0.774018,0 0.797345,0 0.820673,0 0.844,0 0.867327,0 0.890654,0 0.913982,0 0.937309,0 0.960636,0 0.983964,0 1.00729,0 1.03062,1
AMDG Dave Steenburgh wrote:
Or better, a minimal example to try?
I'd like to think I know what the problem is now, but I'm still a little mystified, and I'm not sure how best to correct it. What I think I want is a correction to or replacement for my wrapper class, but I definitely want a second opinion. (Maybe a third and a fourth, too...)
I've got a minimal-ish program that exhibits strange behavior, but it doesn't get stuck. I suspect the same phenomenon is at work here, though, since it still only appears when compiling without optimization. The source is attached, and here are some of my observations: If I use ng instead of vg, there is no problem. (Try it yourself; just move the comment slashes.) If I omit the call to problemFunction, everything works. If I decrease the number of arguments problemFunction requires, everything works. Based on that info, my guess is that something the random generator needs is created on the stack, and later overwritten. However, I think if that were really the problem, it would still be a problem on another platform, or with optimizations enabled.
The error is in this class: class normalGenerator : public randomGenerator { private: typedef boost::normal_distribution<> normalDistribution; boost::variate_generator<baseGenerator&, normalDistribution> _gen; public: explicit normalGenerator(baseGenerator gen = baseGenerator(time(NULL))) : _gen(gen, normalDistribution()) { } inline virtual double operator()() { return _gen(); } }; a) _gen stores a reference to a baseGenerator. b) The constructor takes a baseGenerator by value, which is then destroyed when the constructor returns. In Christ, Steven Watanabe
On Thu, Oct 16, 2008 at 7:39 PM, Steven Watanabe <watanabesj@gmail.com>wrote:
The constructor takes a baseGenerator by value, which is then destroyed when the constructor returns.
Believe it or not, I thought about that when I wrote it, and was amazed that it worked. I promptly forgot about it, and then was severely confused later when I compiled in debug mode, which for me includes turning off optimizations. So, is it just pure luck that it works fine in so many cases? I find it hard to believe that the optimizations would have eliminated enough stack activity so that it worked reliably.
participants (3)
-
Anteru -
Dave Steenburgh -
Steven Watanabe