[racket] performance problem in math/matrix

Hi Berthold,

2013/1/20 Berthold Bäuml <berthold.baeuml at dlr.de>:
> I tried a little test with mildly large Flonum matrices using math/matrix in Typed
> Racket. Two 1000x1000 dimensional matrices should be multiplied with (array-
> strictness #t). Running this in DrRacket results in an "out of memory" error (also
> having set the memory limit to 1GB) and running it with racket on the command
> line makes the computer start to heavily swap.

> Where is this high memory consumption coming from?

I consider this a bug in matrix*.

The culprit is inline-matrix-multiply in "untyped-matrix-arithmetic.rkt".
When multiplying an mxp matrix with an pxn  matrix, it builds a
temporary array of size n*p*m with all products needed, then
it computes sums of these products.

Replacing this algorithm with the standard O(n^3) ought to be easy.

Numpy (and Mathematica, I believe) uses BLAS and LAPACK, which use
Strassen's algorithm (or better?) for matrices this large, so there will
still be a performance gap.

If this performance gaps turns out to be too large, we must figure
out a way to integrate BLAS and LAPACK bindings into math/matrix.

For the time being, I have attached an implementation of math/matrix
using supporting matrices over doubles (math/matrix supports
matrices over Racket numbers). The implementation uses Racket
bindings  to BLAS and LAPACK.   All names ought to the same,
just replace "matrix" with "flmatrix".

Your example becomes:

#lang racket
(require "flmatrix.rkt")
(define dim 1000)
(define big1 (build-flmatrix dim dim (lambda (i j) (random))))
(define big2 (build-flmatrix dim dim (lambda (i j) (random))))
(define res (time (flmatrix* big1 big2)))

Note: Disable "Populate "compiled" directories (for faster loading)"
          to run it in DrRacket. To disable: Choose the language menu.
          Choose the menu item "Choose language". Click the button
          "advanced". Then disable.

If it is enabled, I currently get this curious error from the compiler:

../collects/compiler/cm.rkt:438:6: write: cannot marshal value that is
embedded in compiled code
  value: #<ctype:float>

I unsure whether it is a bug in my code, or in cm.rkt.

-- 
Jens Axel Søgaard
-------------- next part --------------
A non-text attachment was scrubbed...
Name: flmatrix.rkt
Type: application/octet-stream
Size: 69193 bytes
Desc: not available
URL: <http://lists.racket-lang.org/users/archive/attachments/20130120/14127529/attachment-0001.obj>