From: <lut...@fr...> - 2012-03-26 19:31:30
|
Hi, I intend to tackle LP #309467 (nonuniform RANDOM distribution if given an integer argument near RANDOM-FIXNUM-MAX that is not a power of two), in fact, as hinted there by using an accept/reject loop instead of RANDOM-EXTRA-BITS. I have working code that shows that apart from the better distribution the random number generation also is often faster and conses less. A DEFTRANSFORM for the case of a compile time constant integer argument is included. Additionally, I worked on making the generation of random bignums have linear instead of quadratic time and space complexity. I'd like to get some feedback before I put more effort into this: Does anyone have plans for RANDOM that conflict with this? Are there additional ways that RANDOM should be improved that I should take care of in connection with this? To not change too much at the same time I would like to keep the 32-bit Mersenne Twister for both the builds with 32 and 64 bit word size. OK? (In the long run one might want to use a 64-bit generator under 64 bit word size, for speed. For example, there exists a 64-bit version of the Mersenne Twister that I would expect to generate twice as many bits per second as the 32-bit version (when both are implemented in Lisp and the word size is 64 bits)). Any comments appreciated, Lutz |
From: Nikodemus S. <nik...@ra...> - 2012-03-27 08:28:42
|
On 26 March 2012 22:29, Lutz Euler <lut...@fr...> wrote: > Does anyone have plans for RANDOM that conflict with this? Are there > additional ways that RANDOM should be improved that I should take care > of in connection with this? *should* is way too strong a word here, but the following items are at least on my "would be neat if" list: - Documentation love. https://bugs.launchpad.net/sbcl/+bug/656839 - SSE2ified mersenne twister on x86-64. - I have a vague recollection that there was something suboptimal about the way we dealt with floating point. There's probably a message or two in the list archives from WHN about it. - Making random generation pluggable, so that it you could eg. do (seed-random-state :type :some-other-generator-type) to get another algorithm. ...but I think only the first item is something that seems even vaguely in scope now. > To not change too much at the same time I would like to keep the 32-bit > Mersenne Twister for both the builds with 32 and 64 bit word size. OK? No objection from me. Cheers, -- Nikodemus |
From: Christophe R. <cs...@ca...> - 2012-03-27 08:42:33
|
Nikodemus Siivola <nik...@ra...> writes: > - Making random generation pluggable, so that it you could eg. do > > (seed-random-state :type :some-other-generator-type) > > to get another algorithm. My (unmerged, where is it?) subclassable structures work was motivated by making subclasses of random-state (and package) possible and useful. It is nowhere near finished, and should absolutely not hold up this work on RANDOM, which I thoroughly support. Cheers, Christophe |
From: Nikodemus S. <nik...@ra...> - 2012-03-27 08:56:39
|
On 27 March 2012 11:42, Christophe Rhodes <cs...@ca...> wrote: > My (unmerged, where is it?) subclassable structures work was motivated > by making subclasses of random-state (and package) possible and useful. ...and thread. :) Cheers, -- nikodemus |
From: <lut...@fr...> - 2012-03-27 15:34:06
|
Hi, thanks to Nikodemus and Christophe for the feedback. Nikodemus wrote (citing out of order): > ...but I think only the first item is something that seems even > vaguely in scope now. I agree. So, below my comments/questions about your first and second item: > - Documentation love. https://bugs.launchpad.net/sbcl/+bug/656839 I plan to do something here, yes; but later. I hope there is an automatic way to get docstrings into the documentation? The docstrings of MAKE-RANDOM-STATE and SEED-RANDOM-STATE would fit nicely, IMO. > - SSE2ified mersenne twister on x86-64. Yes, this is supposed to be faster and even "more random" than the current version, AFAIK. On the other hand, the current code contains a comment from WHN: ;;; Using inline VOP support, only available on the x86 so far. ;;; ;;; FIXME: It would be nice to have some benchmark numbers on this. ;;; My inclination is to get rid of the nonportable implementation ;;; unless the performance difference is just enormous. So his principle seemed to be to prefer portable solutions over machine specific ones? Whatever; I currently don't intend to work on this. It can be done later if desired without causing wasted efforts now. I will upload a patch to LP #309467 for review and then post some more specific questions about it. Greetings, Lutz |
From: Nathan F. <fr...@gm...> - 2012-03-27 15:44:29
|
On Tue, Mar 27, 2012 at 11:31 AM, Lutz Euler <lut...@fr...> wrote: >> - SSE2ified mersenne twister on x86-64. > > Yes, this is supposed to be faster and even "more random" than the > current version, AFAIK. On the other hand, the current code contains > a comment from WHN: > > ;;; Using inline VOP support, only available on the x86 so far. > ;;; > ;;; FIXME: It would be nice to have some benchmark numbers on this. > ;;; My inclination is to get rid of the nonportable implementation > ;;; unless the performance difference is just enormous. > > So his principle seemed to be to prefer portable solutions over machine > specific ones? Yes. At the time, the modular arithmetic bits hadn't been implemented, so doing a portable solution would have been slow. With modular arithmetic, I think the only benefit of the current VOP bits is a clever use or two of flags. So this would be something good to clean up. -Nathan |
From: <lut...@fr...> - 2012-03-28 20:14:35
|
Hi, I just uploaded a patch to LP #309467. It applies on top of sbcl-1.0.55-14-g137b4d0. It would be great if someone could review it as it is easy to break RANDOM in an untestable way. The code passes the test suite under x86 and x86-64 under Linux. I have looked at lots of disassembly to verify that things are inlined and optimised as I expected them to. Some remarks/questions: The first commit in the patch is to fix an old bug that was introduced with a fix for a bug detected by PFD about (RANDOM (IF X 10 20)); Christophe might remember ... Nobody noticed this bug since then (2004). (I hope this means that this code path happened to never be used outside of Paul's tests, and not that users silently got wrong random distributions.) I think the solution to give up the DEFTRANSFORM in this case is OK, but would like getting confirmation about this. Now about the third commit: I have put the parts of the new code dealing with random bignums into a new file "src/code/random-bignum.lisp". It needs both constants and functions from the SB-BIGNUM and the SB-KERNEL package. To put the code into the SB-BIGNUM package meant fewer explicit package markers and fewer additions to exported symbols. It can't be put into "src/code/bignum.lisp" as that comes too early in the build order. Is this OK, or should I use "src/code/target-random.lisp" and switch packages in the middle of that file? I modified the DEFTRANSFORM but left it in "src/compiler/float-tran.lisp". I don't like that very much as the file name obviously doesn't fit an integer-only transform. I am not sure where to put the DEFTRANSFORM: WHN had written in float-tran: ;;; FIXME: It's unpleasant to have RANDOM functionality scattered ;;; through the code this way. It would be nice to move this into the ;;; same file as the other RANDOM definitions. RANDOM definitions at that time were in "src/code/random" and "src/code/target-random". But, currently nearly all transforms are defined in files "compiler/...tran.lisp", and when in 2007 WHN tried to improve integer RANDOM he created "src/compiler/integer-tran.lisp" to put this transform into (which file, by the way, wasn't deleted when WHN retracted his changes, but is now unused). So, where to put this transform? Thanks for any comments, Lutz |
From: Christophe R. <cs...@ca...> - 2012-04-26 10:09:58
|
lut...@fr... (Lutz Euler) writes: > The first commit in the patch is to fix an old bug that was introduced > with a fix for a bug detected by PFD about (RANDOM (IF X 10 20)); > Christophe might remember ... Whoops. > Nobody noticed this bug since then (2004). (I hope this means that this > code path happened to never be used outside of Paul's tests, and not > that users silently got wrong random distributions.) > I think the solution to give up the DEFTRANSFORM in this case is OK, but > would like getting confirmation about this. Yes, I think so. The test cases are good; I might try to implement a uniformity test or two at some point, but the tests in your second commit are clearly better than no tests at all :) > Now about the third commit: > > I have put the parts of the new code dealing with random bignums into > a new file "src/code/random-bignum.lisp". It needs both constants and > functions from the SB-BIGNUM and the SB-KERNEL package. To put the code > into the SB-BIGNUM package meant fewer explicit package markers and > fewer additions to exported symbols. It can't be put into > "src/code/bignum.lisp" as that comes too early in the build order. > Is this OK, or should I use "src/code/target-random.lisp" and switch > packages in the middle of that file? Although slime can cope with switching packages, it is a bit of a pain to the (human) reader, and I think the approach you've taken is much better. Why is src/code/bignum too early, though, what's it using -- do you remember? If that functionality could be used for anything else it might be worth calling the file "late-bignum.lisp" rather than "random-bignum.lisp" -- to make the point that it's code which depends on something earlier. (If there's no conceivable other use for the functionality that random-bignum depends on, then fine :-) > I modified the DEFTRANSFORM but left it in > "src/compiler/float-tran.lisp". I don't like that very much as the file > name obviously doesn't fit an integer-only transform. I am not sure > where to put the DEFTRANSFORM: > > WHN had written in float-tran: > ;;; FIXME: It's unpleasant to have RANDOM functionality scattered > ;;; through the code this way. It would be nice to move this into the > ;;; same file as the other RANDOM definitions. > RANDOM definitions at that time were in "src/code/random" and > "src/code/target-random". But, currently nearly all transforms are > defined in files "compiler/...tran.lisp", and when in 2007 WHN tried to > improve integer RANDOM he created "src/compiler/integer-tran.lisp" to > put this transform into (which file, by the way, wasn't deleted when WHN > retracted his changes, but is now unused). I have several times been confused by integer-tran.lisp; my memory is that it actually was removed from CVS, but the cvs->git conversion didn't pick that up and we've been left with the zombie remains. There's a fair amount of integer-only functionality in srctran.lisp, which could also be moved out into an integer-tran (or inttran to conform to 8.4 file naming restrictions ;-). Initially, modifying the existing transform is fine, and then maybe reviewing srctran and the other transform files for integer-only things to be pulled out would be the way forward. This looks like a very thorough piece of work. Thank you! Best, Christophe |
From: Christophe R. <cs...@ca...> - 2012-04-29 23:04:03
|
lut...@fr... (Lutz Euler) writes: > Regarding a file name: I am mostly interested in something that doesn't > increase the confusingness (?) of build-order.lisp-expr. I am currently > tending towards "target-random-bignum.lisp", but that may be too long. Well. Firstly, apologies for confusing you -- that definitely wasn't my intention. It's probably best to avoid having too long a discussion about this, otherwise we will find out how many angels can dance on the head of a pin. The reasons that "target-random-bignum" may be confusing are: - "target" implies "this stuff is only used by the target". But all of "bignum.lisp" is already only used by the target. - "random" has the unfortunate connotation of "grab-bag of stuff related to" -- as opposed to the very sensible meaning you have here, which is "related to RANDOM". If I had to suggest something for your new file, I might suggest "bignum-random". Best, Christophe |