Subject: Re: How to avoid GC in tight numeric test loop? (CMUCL)
From: (Rob Warnock)
Date: Fri, 13 Jun 2008 03:44:42 -0500
Newsgroups: comp.lang.lisp
Message-ID: <>
Robert Maas, <> wrote:
| After seeing your reply, I tried using RANDOM with smaller
| argument, but it didn't help enough:
| (defparameter exp2 21)
| (defparameter arrsiz (expt 2 exp2))
| arrsiz
| => 2097152
| (time (dotimes (k 50000)
|         (declare (type (unsigned-byte 16) k))
|         (the (unsigned-byte 21) (random arrsiz))))
| Compiling LAMBDA NIL:
| Compiling Top-Level Form:
| [GC threshold exceeded with 2,002,376 bytes in use.  Commencing GC.]
|   1945120 bytes consed.

See my parallel reply <>.

The problem isn't the value of the arg to RANDOM per se, it's that unless
the arg is a literal number the #+RANDOM-MT19937 (DEFTRANSFORM RANDOM)
inline expander in "cmucl/src/compiler/float-tran.lisp" isn't seeing
the arg as one which will return an (UNSIGNED-BYTE 32) or smaller, and
thus is punting to the generic function call of RANDOM... which conses
some 80-96 bytes per call [it varies].

There's special code on X86 platforms to allow args up to (EXPT 2 32),
*significantly* larger than KERNEL:RANDOM-FIXNUM-MAX [== 4194303 in 19c,
but see below re 18b!], but unfortunately the COND branch for that check
is in the wrong place!! [Yes, I have already mentioned this to one of
the CMUCL maintainers.]

But how big is KERNEL:RANDOM-FIXNUM-MAX on CMUCL-18b?!? I don't have
version 18b here, but on 18d it was already 4194303 [same as 19c],
and your above code does *NOT* cons anything on either 18d or 19c!!

    cmu> (list (lisp-implementation-type)

    ("CMU Common Lisp" "18d")
    cmu> (defparameter exp2 21)

    cmu> (defparameter arrsiz (expt 2 exp2))

    cmu> arrsiz

    cmu> kernel:random-fixnum-max    ; What is this on your system?!?

    cmu> (time (dotimes (k 50000) ; You don't really need to declare K here
		 (random arrsiz)))
    Compiling LAMBDA NIL: 
    Compiling Top-Level Form: 

    Evaluation took:
      0.0 seconds of real time
      7.26e-4 seconds of user run time
      0.001454 seconds of system run time
      0 page faults and
      0 bytes consed.
    cmu> (time (dotimes (k 2000000000)
		 (random arrsiz)))
    Compiling LAMBDA NIL: 
    Compiling Top-Level Form: 

    Evaluation took:
        87.24 seconds of real time
        86.44366 seconds of user run time
        0.0f0 seconds of system run time
        0 page faults and
        0 bytes consed.

Aha!! A web search shows that in even older versions of CMUCL,
KERNEL:RANDOM-FIXNUM-MAX was only 524287!! So either try an
ARRSIZ < 524287, or (much better!) switch to a newer version
of CMUCL. [You really, *really* need to do that in any case,
since CMUCL-18b is already a *decade* old!!]

| Maybe I need to put the entire loop inside a lexical closure where
| ARRSIZ is defined once as an int32 then referenced locally?

That won't help until the bug in "cmucl/src/compiler/float-tran.lisp"
gets fixed. Until then, either use a literal constant arg [can be as
high as (EXPT 2 32) on X86] or a variable arg whose type is known to
the compiler and whose value is less than KERNEL:RANDOM-FIXNUM-MAX
on whatever version you're running.

| I'll read the rest of the thread before trying that.

Just read my previous [URL above] & this message...  ;-}


p.s. Hmmm... What does (FIND :RANDOM-MT19937 *FEATURES*) give you on 18b?
The larger KERNEL:RANDOM-FIXNUM-MAX comes with the new MT19937 random
number generator, which may have been an optional "extra" in CMUCL-18b.
[It was standard by 18d, at least.] If so, you might be able to load it
at runtime [but *before* compiling code which calls RANDOM] and at least
get a non-consing RANDOM with args up to 4194303 [results in 0..4194302].

Rob Warnock			<>
627 26th Avenue			<URL:>
San Mateo, CA 94403		(650)572-2607