[gambit-list] Number crunching

Bradley Lucier lucier at math.purdue.edu
Sat Apr 21 15:17:32 EDT 2007


On Apr 19, 2007, at 1:36 PM, Huang Jianshi wrote:

> tutorial/manual/
> examples on showing how to write efficient code on number crunching
> task, especially matrix operations and floating point operations.

Christian gave good advice.  You'll almost need to write C-style code  
and declarations (removing the flexibility that is otherwise built in  
to Scheme).

Start with

(declare
   (standard-bindings)
   (extended-bindings)
   (block)
   (not safe))

These mean

(standard-bindings):  All R4RS/R5RS procedure names point to the  
standard R4RS/R5RS procedures (i.e., you haven't redefined + to  
something different)
(extended-bindings):  The same thing for the Gambit-specific procedures.
(block):  If you haven't set! a variable in the file in which it is  
defined, its value is never changed via set! in any other file.   
(This is why you'll see things like

(define foo ...)
(set! foo foo)

in some of the scheme files in lib; this tells gambit that even  
though the file has (declare (block)), this particular variable can  
be redefined in other files.)
(not safe):  You don't want Gambit to insert checking code to save  
yourself from, e.g., (car 1) crashing gambit.

Then you should use fixnum and/or flonum-specific numeric operations  
as appropriate.  You can put a (declare ...) form anywhere that you  
can put a (define ...) form, so

(let ()
   (declare (flonum))
   ...)

means that all numeric operations in that "let" have flonum arguments  
and results, and tells gambit to just use the usual floating-point  
operations (so (sqrt -1.) is +nan.0 instead of +1.i).  Similarly for  
(declare (fixnum)).  To make it easier to use these declarations in  
simple expressions, I usually define the macros:

(define-macro (FLOAT . rest)
   `(let ()
      (declare (flonum))
      , at rest))

(define-macro (FIX . rest)
   `(let ()
      (declare (fixnum))
      , at rest))

so one can simply say (FIX (+ i 1)), for example.  There's less need  
for this given the fx+, etc., operations, but it does allow you a bit  
more flexibility for testing, etc.  (one can simply redefine (FIX .  
body) as (begin , at body).

The gambit runtime system catches all interrupts and handles them  
itself, and it checks for interrupts at the same time it checks for  
stack overflows.  (See POLL macros in the C code generated by gsc.)   
Sometimes it pays to disable those checks in tight loops with

(declare (not interrupts-enabled))

If you do this in a loop that allocates stuff on the stack, then  
gambit will crash, since there will be a stack overflow that won't be  
caught.  Also, you cannot interrupt a loop that has interrupts  
disabled, and this can be annoying.  In 4.0b22, Marc uses the  
__builtin_expect built-in function in gcc-3.0 and later to tell gcc  
that these POLLs are unlikely to be taken, so maybe POLLs will slow  
down loops less than in previous versions of gambit.

Finally, the Gambit-C compiler generates code that boxes flonums  
across any function call, (if ...) boundary, etc.  And loops are  
function calls in Scheme, so it boxes flonums across loops.   
Sometimes allocating the 12-16 bytes (depending on whether Gambit's  
running on a 32-bit or 64-bit machine) for a boxed flonum takes  
longer that to compute  the value of that flonum.

If this is a real problem, I tend to lesson it for a given loop by  
unrolling the loop a number of times by hand or, if you're  
accumulating a sum into a single flonum result, I may allocate a  
f64vector of length one, read its value at the beginning of the loop,  
and then store back into it at the end of the loop.

All that being said, I tend to write numerical code by identifying  
which loops are computationally intensive, optimize them, and then  
use the late-binding flexibility of normal Scheme semantics to make  
the rest of the code easier to write and maintain.  It's not so easy  
to find out where your code is spending it's time, since 'gcc -pg' is  
pretty useless (each file is compiled to one C function).  If  
necessary, I end up configuring gambit with

env CC='gcc -ftest-coverage -fprofile-arcs' ./configure --enable- 
single-host --enable-gcc-opts

and then run gcov on the output.  The problem with doing this is that  
you need to understand the macros used in the C code generate by  
Gambit, the so-called Gambit Virtual Machine (GVM), and how to  
associate that code with lines in your code. (It's not hard, GVM is a  
simple machine with a few registers, a stack, and the usual abstract  
operations.)  Or, you can compile the scheme file with

gsc -track-scheme file.scm

and then gcov will report the number of times each line of C code is  
executed.  (I just did this for an image-processing program I'm  
writing, and found out that all source files should be in the same  
directory or gcov gets confused.)

You can find code for numerical solution of PDEs at

<http://www.math.purdue.edu/~lucier/615/software/index.html>

that uses all these techniques in one place or another.  Search for  
(FLOAT ...), (FIX ...), and (declare ...).  Understanding this code  
is more complicated because it uses the Meroon object system, but the  
basic numerical tricks are visible.

Brad



More information about the Gambit-list mailing list