Nouvel objet : Patch to roughly double the speed of generating pseudo-random inexact numbers.

15 Jan 2009


      A student was trying to use Gambit for a Monte-Carlo simulation, so I
looked at the speed of generating inexact pseudo-random numbers.
This patch adds a procedure
(random-source-make-f64vectors rs #!optional (p (macro-absent-obj))
that returns an f64vector of pseudo-random inexact numbers.  The purpose
of this procedure is to avoid the trampoline in the very common case
when inexact reals are needed in groups by an algorithm.
It also adds the predefined procedure random-f64vector.
There is some amount of duplication in the internal procedure
(make-f64vectors precision)
in order to have an allocation-free path for the generation of the
random reals, so that the only memory allocated is for the f64vector
itself.
In one place I changed
-            (fl/ (fl+ (macro-inexact-+1) (f64vector-ref state 6))
-                 (macro-m1-plus-1-inexact)))))
+            (fl* (fl+ (macro-inexact-+1) (f64vector-ref state 6))
+                 (macro-inv-m1-plus-1-inexact)))))
because the division wasn't necessary to preserve the correctness of the
algorithm.  (The divisions are necessary in advance-state! to preserve
the correctness of the algorithm.)
I changed advance-state! to avoid the final flfloor (it seems that
flfloor, flonum->fixnum, ..., take a relatively long time on my Core 2
Duo compared to the usual addition, multiplication, ...); the new code
still avoids boxing flonums.  I also made state a local variable because
the register allocator kept reloading it into registers, stack slots,
etc., from the closure.
And then I tried to document this stuff.
I noticed that the optional precision parameter wasn't documented; was
that intentional?
Brad
Tests:
With test-random-reals.scm given by
(declare (standard-bindings)(extended-bindings)(block)(not safe))
(define (make-random-f64vector n)
  (let ((result (make-f64vector n)))
    (do ((i (fx- n 1) (fx- i 1)))
    ((fx< i 0) result)
      (f64vector-set! result i (random-real)))))
I get with current head
frying-pan:~/programs/gambc-v4_4_0-devel> gsi
Gambit v4.4.0
...
(load "test-random-reals")
"/home/lucier/programs/gambc-v4_4_0-devel/test-random-reals.o13"
...
(define a (time (make-f64vector 1000000)))
(time (make-f64vector 1000000))
    7 ms real time
    4 ms cpu time (0 user, 4 system)
    1 collection accounting for 1 ms real time (0 user, 0 system)
    8000048 bytes allocated
    1984 minor faults
    no major faults
...
(define a (time (make-random-f64vector 1000000)))
(time (make-random-f64vector 1000000))
    162 ms real time
    160 ms cpu time (144 user, 16 system)
    2 collections accounting for 1 ms real time (0 user, 0 system)
    40000048 bytes allocated
    4981 minor faults
    no major faults
and with the changes I get
frying-pan:~/programs/gambc-v4_4_0-devel> gsi/gsi
Gambit v4.4.0
...
(load "test-random-reals")
"/home/lucier/programs/gambc-v4_4_0-devel/test-random-reals.o13"
...
(define a (time (make-f64vector 1000000)))
(time (make-f64vector 1000000))
    6 ms real time
    4 ms cpu time (0 user, 4 system)
    1 collection accounting for 0 ms real time (0 user, 0 system)
    8000048 bytes allocated
    1982 minor faults
    no major faults
...
(define a (time (make-random-f64vector 1000000)))
(time (make-random-f64vector 1000000))
    132 ms real time
    132 ms cpu time (120 user, 12 system)
    2 collections accounting for 1 ms real time (0 user, 0 system)
    40000048 bytes allocated
    4981 minor faults
    no major faults
...
(define a (time (random-f64vector 1000000)))
(time (random-f64vector 1000000))
    73 ms real time
    72 ms cpu time (64 user, 8 system)
    no collections
    8000048 bytes allocated
    1954 minor faults
    no major faults