[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Gcl-devel] Re: several random bugs
[Gcl-devel] Re: several random bugs
30 May 2005 16:09:56 -0400
Gnus/5.09 (Gnus v5.9.0) Emacs/21.2
Robert Boyer <address@hidden> writes:
> The following transcript illustrates several bugs, I think.
> 1. Simply making and discarding a lot of random bignums can fill memory
> until it chokes.
This is a problem in the optimize-maximum-pages algorithm, which can
be worked around by (setq si::*optimize-maximum-pages* nil). I will
fix this by having GCL effectively do this when the heap approaches
> 2. RANDOM is not very random -- it seems to always returns even numbers for
> the case given. But it ought to return odd numbers frequently, or so I
> randomly believe. (I think it was Knuth who asked whether 2 was a random
> 3. It may well be that RANDOM needs a large scale redoing. Currently,
> *RANDOM-STATE* seems to be about the size of a fixnum. In Allegro, it's a
> lot larger than that. Given that RANDOM can get as its argument a very large
> integer, it seems that *RANDOM-STATE* must take on a very large number of
> possible states.
Yes, as you've discovered, our random only makes 32 bits of randomness
at a time. Definitely inadequate.
Your idea separately suggested about using gmp random numbers is quite
useful -- thanks! I was about to put in my own copy of the Mersenne
Twister when I discovered we already have it in gmp.
I've implemented this here (e.g. gmp random), and all tests appear to
be passing, including your #'fap example below. Might be interesting
to benchmark if I can find a good test snippet.
There are a few general issues in our gmp interface that have surfaced
again in implementing this.
1) This change has required gbc support, as the gmp random state has
internal bignum pointers which must be marked. Not a problem, but
it does raise the question of how we synchronize if/when gmp ever
changes this structure, as we dynamically link against an external
libgmp by default. I need a good runtime gmp version check.
2) We don't want to require the user to have gmp headers/development
files installed, so we need to excerpt sections from gmp.h to put
in our cmpinclude.h used by the compiler. Perhaps we could just
dump the entire file, but this cmpinclude.h is already huge. If
excepting is done, it should be done automatically at compile
3) We currently use the 'high level' gmp interface, redirecting gmp's
heap allocation function to our alloc_relblock/alloc_contblock. In
almost all cases, it would certainly appear faster to allocate on
the stack and call the lower level mpn_ functions when possible.
This is quite a bit of work, which I don't think I'll pursue unless
someone can provide evidence of the gains to be had.
4) I'm not sure what to report in the #$ random state reader/printer,
though I think it should be the _mp_seed bignum stored (and
apparently modified) by gmp in its random state struct.
5) There are a few algorithms to choose from -- I've implemented the
default, described in the docs as :
-- Function: void gmp_randinit_default (gmp_randstate_t STATE)
Initialize STATE with a default algorithm. This will be a
compromise between speed and randomness, and is recommended for
applications with no special requirements.
I take it we do not need a lisp interface to choose the alternates
instead? In some alternatives, one can explicitly specify the bit
size of randomeness, currently up to 256 bits. Requests for larger
bit streams than this size are concatenated from multiple calls.
6) Right now all random calls pass through gmp -- would it be better
to implement fixnum randoms inline?
7) Looking at the gmp website, their reports of possible gmp
miscompilation are somewhat alarming. They have a regression
suite, which I am considering pushing up to the lisp user to check
their external gmp library.
8) time(0) is used as the default random state seed as before,
despite deprecations in the gmp docs. We could try to read
/dev/random (non-portably), but then the lisp user can do this with
#'open from within lisp, so this does not seem pressing.
> The transcript.
> % /p/bin/gcl-2.6.6twc
> GCL (GNU Common Lisp) 2.6.6 CLtL1 May 26 2005 21:17:40
> Source License: LGPL(gcl,gmp), GPL(unexec,bfd)
> Binary License: GPL due to GPL'ed components: (BFD UNEXEC)
> Modifications of this banner must retain notice of a compatible license
> Dedicated to the memory of W. Schelter
> Use (help) to get some basic information on how to use GCL.
> >(compile-file "gcl-bug.lisp")
> Compiling gcl-bug.lisp.
> End of Pass 1.
> End of Pass 2.
> OPTIMIZE levels: Safety=0 (No runtime error checking), Space=0, Speed=3
> Finished compiling gcl-bug.lisp.
> >(load *)
> Loading gcl-bug.o
> start address -T 0x83deea0 Finished loading gcl-bug.o
> >(fap 1000000000)
> ....... several minutes later on elgin.cs.utexas.edu ...
> Error: Relocatable blocks exhausted.
> Currently, 48507 pages are allocated.
> Use ALLOCATE-RELOCATABLE-PAGES to expand the space.
> Fast links are on: do (si::use-fast-links nil) for debugging
> Error signalled by EVAL.
> Broken at FAP. Type :H for Help.
> >>(room t)
> 1766/3597 16.2% 8 CONS FIXNUM SHORT-FLOAT CHARACTER RANDOM-STATE
> READTABLE SPICE
> 52/54 72.7% SYMBOL
> 1/2 13.7% PACKAGE
> 2/45 32.4% ARRAY HASH-TABLE VECTOR BIT-VECTOR STREAM
> PATHNAME CCLOSURE CLOSURE
> 13680/23955 13.5% 69 STRUCTURE BIGNUM RATIO LONG-FLOAT COMPLEX CFUN
> 22/37 90.4% SFUN STRING GFUN VFUN AFUN CFDATA
> 321/512 contiguous (96 blocks)
> 13107 hole
> 48507 99.9% 88 relocatable
> 15523 pages for cells
> 77458 total pages
> 0 pages available
> 53614 pages in heap but not gc'd + pages needed for gc marking
> 131072 maximum pages
> The file gcl-bug.lisp
> ; we set *random-state* only for reproducibility
> (setq *random-state* #$-38547439)
> (defun fap (n) (loop for i from 1 to n
> until (equal 1 (mod (random
> do '(nothing) finally (return i)))
> ; calling (fap 1000000000) seems to choke gcl to death within a few minutes.
Camm Maguire address@hidden
"The earth is but one country, and mankind its citizens." -- Baha'u'llah
|[Prev in Thread]
||[Next in Thread]|
- [Gcl-devel] Re: several random bugs,
Camm Maguire <=