[Gcl-devel] Re: strange slowdown with si::allocate-bigger-fixnum-range

[Camm Maguire]

Greetings!

This is a question of data locality, as far as I can see, which was
masked by the inefficiency of earlier incarnations of the gc
algorithm.  Try the same with (setq si::*optimize-maximum-pages* nil),
and you can see the allocation benefits of the bigger fixnum table
readily.  

Attempting to parse the Rosetta Stone of the existing GCL code, the
small fixnum table size appears to have been selected to fit into the
L1 cache of typical x86 machines (2k*8bytes).  Going out of cache
appears to pay a penalty in locality/access-time as compared to
freshly allocated objects on the heap.  We could probe for the l1
cache size at configure time if we were in the mood.  Also, it would
be straightforward to double our current size at no performance
penalty by compressing the static fixnum table along the lines of what
we are doing with cons in the 'twc' experiment.  Lastly, I've
implemented a fixnum_times function in num_arith.c (not yet committed
anywhere) which cuts the time for this benchmark in half (6.5s ->
3.5s) -- don't know how important such types of calculation are.
There is a similar performance fix we need for num_expt -- I'll likely
put these in at the same time.

There are prefetch instructions on most modern machines that can
greatly speedup access times in certain circumstances -- haven't yet
found the right place for them in GCL if anywhere.

Take care,

Robert Boyer <address@hidden> writes:

> I can hardly believe my eyes, but it looks to me like
> si::allocate-bigger-fixnum-range can really slow things down!  The file
> mm.lisp at the end of this message implements a very simple, undeclared array
> multiply.
> 
> Below I compile the file, load it, initialize two arrays, and then time a
> multiply.  Takes 6.340 seconds, including .41 in gc.  Then I
> (si::allocate-bigger-fixnum-range -1000000 1000000) and time a multiply.
> Takes 9.8 seconds!
> 
> I'll never understand Lisp, I'm afraid.
> 
> Bob
> 
> 
> -------------------------------------------------------------------------------
> The transcript:
> 
> GCL (GNU Common Lisp)  2.6.6 CLtL1    Mar  8 2005 22:20:59
> 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 "mm.lisp")
> 
> Compiling mm.lisp.
> End of Pass 1.  
> End of Pass 2.  
> OPTIMIZE levels: Safety=0 (No runtime error checking), Space=0, Speed=3
> Finished compiling mm.lisp.
> #p"mm.o"
> 
> >(load "mm")
> 
> Loading mm.o
> start address -T 0x8537950 Finished loading mm.o
> 1696
> 
> >(in-package "COMMON-LISP-USER")
> 
> #<"COMMON-LISP-USER" package>
> 
> COMMON-LISP-USER>(m-init)
> 
> NIL
> 
> COMMON-LISP-USER>(time (m-mm))
> 
> real time       :      6.340 secs
> run-gbc time    :      5.830 secs
> child run time  :      0.000 secs
> gbc time        :      0.410 secs
> NIL
> 
> COMMON-LISP-USER>(si::allocate-bigger-fixnum-range -1000000 1000000)
> 
> T
> 
> COMMON-LISP-USER>(time (m-mm))
> 
> real time       :      9.800 secs
> run-gbc time    :      9.810 secs
> child run time  :      0.000 secs
> gbc time        :      0.000 secs
> NIL
> 
> 
> -------------------------------------------------------------------------------
> 
> the file mm.lisp:
> 
> (in-package "COMMON-LISP-USER")
> 
> ; very dumb way to multiply two square matrices *a* and *b* and
> ; put the results in *c*.  *l* is the size of one dimension of the
> ; arrays.
> ; Call (m-init) to start.  Then (time (m-mm)) to see the cost of
> ; an array multiplication.
> 
> ; also maybe try (si::allocate-bigger-fixnum-range 0 20000000)
> 
> (defparameter *l*  300) ; dimension of array
> 
> (defparameter *a* (make-array (list *l* *l*)))
> 
> (defparameter *b* (make-array (list *l* *l*)))
> 
> (defparameter *c* (make-array (list *l* *l*)))
> 
> (defparameter *x* 100) ; upper limit on initial values
> 
> (defun m-init ()
>   (sloop::sloop for i below *l* do
>         (sloop::sloop for j below *l* do
>               (setf (aref *a* i j) (random *x*))
>               (setf (aref *b* i j) (random *x*)))))
> 
> (defun m-mm ()
>   (sloop::sloop for i below *l* do
>         (sloop::sloop for j below *l* do
>               (setf (aref *c* i j)
>                     (sloop::sloop for k below *l* sum (* (aref *a* i k)
>                                                          (aref *b* k j)))))))
> 
> 
> 
> 

-- 
Camm Maguire                                            address@hidden
==========================================================================
"The earth is but one country, and mankind its citizens."  --  Baha'u'llah