<div dir="ltr"><div><div>What is bothering me is the time Racket is spending in garbage collection. <br><br>~/wrk/scm/rkt/matrix$ racket matrix.rkt<br>0.9999999999967226<br>cpu time: 61416 real time: 61214 gc time: 32164<br>
<br>If I am reading the output correctly, Racket is spending 32 seconds out of 61 seconds in garbage collection.<br><br> I am following Junia Magellan's computer language comparison and I cannot understand why Racket needs the garbage collector for doing Gaussian elimination. In a slow Compaq/HP machine, solving a system of 800 linear equations takes 17.3 seconds in Bigloo, but requires 58 seconds in Racket, even after removing the building of the linear system from consideration. Common Lisp is also much faster than Racket in processing arrays. I would like to point out that Racket is very fast in general. The only occasion that it lags badly behind Common Lisp and Bigloo is when one needs to deal with arrays. <br>
<br></div>Basically, Junia is using Rasch method to measure certain latent traits of computer languages, like productivity and coaching time. In any case, she needs to do a lot of matrix calculations to invert the Rasch model. Since Bigloo works with homogeneous vectors, she wrote a few macros to access the elements of a matrix:<br>
<br>(define (mkv n) (make-f64vector n))<br>(define $ f64vector-ref)<br>(define $! f64vector-set!)<br>(define len f64vector-length)<br><br>(define-syntax $$ <br> (syntax-rules () <br> (($$ m i j) (f64vector-ref (vector-ref m i) j))))<br>
<br>(define-syntax $$!<br> (syntax-rules ()<br> (($$! matrix row column value) <br> ($! (vector-ref matrix row) column value)))) <br><br></div><div>I wonder whether homogeneous vectors would speed up Racket. In the same computer that Racket takes 80 seconds to build and invert a system of equations, Bigloo takes 17.3 seconds, as I told before. Common Lisp is even faster. However, if one subtracts the gc time from Racket's total time, the result comes quite close to Common Lisp or Bigloo.<br>
<br>~/wrk/bgl$ bigloo -Obench bigmat.scm -o big<br>~/wrk/bgl$ time ./big<br>0.9999999999965746 1.000000000000774 0.9999999999993039 0.9999999999982576 1.000000000007648 0.999999999996588 <br><br>real 0m17.423s<br>user 0m17.384s<br>
sys 0m0.032s<br>~/wrk/bgl$ <br><br></div><div>Well, bigloo may perform global optimizations, but Common Lisp doesn't. When one is not dealing with matrices, Racket is faster than Common Lisp. I hope you can tell me how to rewrite the program in order to avoid garbage collection.<br>
</div><div><br></div><div>By the way, you may want to know why not use Bigloo or Common Lisp to invert the Rasch model. The problem is that Junia and her co-workers are using hosting services that do not give access to the server or to the jailshell. Since Bigloo requires gcc based compilation, Junia discarded it right away. Not long ago, the hosting service stopped responding to the sbcl Common Lisp compiler for reasons that I cannot fathom. Although Racket 6.0 stopped working too, Racket 6.0.1 is working fine. This left Junia, her co-workers and students with Racket as their sole option. As for myself, I am just curious.<br>
</div></div><div class="gmail_extra"><br><br><div class="gmail_quote">2014-05-11 6:23 GMT-03:00 Jens Axel Søgaard <span dir="ltr"><<a href="mailto:jensaxel@soegaard.net" target="_blank">jensaxel@soegaard.net</a>></span>:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">2014-05-11 6:09 GMT+02:00 Eduardo Costa <<a href="mailto:edu500ac@gmail.com">edu500ac@gmail.com</a>>:<br>
<div class="">> The documentation says that one should expect typed/racket to be faster than<br>
> racket. I tested the math/matrix library and it seems to be almost as slow<br>
> in typed/racket as in racket.<br>
<br>
</div>What was (is?) slow was a call in an untyped module A to a function exported<br>
from a typed module B. The functions in B must check at runtime that<br>
the values coming from A are of the correct type. If the A was written<br>
in Typed Racket, the types would be known at compile time.<br>
<br>
Here math/matrix is written in Typed Racket, so if you are writing an<br>
untyped module, you will in general want to minimize the use of,say,<br>
maxtrix-ref. Instead operations that works on entire matrices or<br>
row/columns are preferred.<br>
<div class=""><br>
> (: sum : Integer Integer -> Flonum)<br>
> (define (sum i n)<br>
> (let loop ((j 0) (acc 0.0))<br>
> (if (>= j mx) acc<br>
> (loop (+ j 1) (+ acc (matrix-ref A i j))) )))<br>
><br>
> (: b : (Matrix Flonum))<br>
> (define b (build-matrix mx 1 sum))<br>
<br>
</div>The matrix b contains the sums of each row in the matrix.<br>
Since matrices are a subset of arrays, you can use array-axis-sum,<br>
which computes sum along a given axis (i.e. a row or a column when<br>
speaking of matrices).<br>
<br>
(define A (matrix [[0. 1. 2.]<br>
[3. 4. 5.]<br>
[6. 7. 8.]]))<br>
<br>
> (array-axis-sum A 1)<br>
- : (Array Flonum)<br>
(array #[3.0 12.0 21.0])<br>
<br>
However as Eric points out, matrix-solve is an O(n^3) algorithm,<br>
so the majority of the time is spent in matrix-solve.<br>
<br>
Apart from finding a way to exploit the relationship between your<br>
matrix A and the column vector b, I see no obvious way of<br>
speeding up the code.<br>
<br>
Note that when you benchmark with<br>
<br>
time racket matrix.rkt<br>
<br>
you will include startup and compilation time.<br>
Therefore if you want to time the matrix code,<br>
insert a literal (time ...) call.<br>
<br>
--<br>
Jens Axel Søgaard<br>
</blockquote></div><br></div>