[Gcl-devel] Re: several random bugs

[Camm Maguire]

Greetings!

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
the maximum.

> 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
> number.)
> 
> 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
   time.  

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.

Take care,

> Bob
> 
> -------------------------------------------------------------------------------
> 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.
> #p"gcl-bug.o"
> 
> >(load *)
> 
> Loading gcl-bug.o
> start address -T 0x83deea0 Finished loading gcl-bug.o
> 292
> 
> >(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 
> 19061539979441401073668884216553005888015095987208605850362348622463716754383546624711923223377616038019787977433236120789800783643270501079412010576132956599964730611121959415426766496221032596166486661776)
>                                          2))
>                      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