Yet another Racket benchmark comparison

Show & Tell
1

After reading this blog post about a comparison using C and CommonLisp (SBCL) I quickly wrote a Racket version just out of curiosity to make yet another unnecessary comparison :slightly_smiling_face:

I just cloned the directory linked in the post plus adding a .rkt file and the lines in the Makefile to run the benchmark, here is my version. At the end, the resulting Racket code run one order of magnitude slower than C and CL on with 5M parameter, two with 500k as parameter.

My code is surely far from optimal and have space for optimization so I just wanted to share to get some advice on how to possibly improve the code.

1 Like
2

I've only looked at this quickly, but one thing to bear in mind is that set! is generally a red flag in performance-sensitive code. Since set! is rare in idiomatic Racket, the compiler doesn't try to do sophisticated analysis about assignments: in fact, any variable that appears on the left-hand side of a set! expression is effectively turned into a box, which makes the implementation of closures and continuations simple and efficient. It looks like many of your uses of set! could be replaced by changing your for loops to for/fold, perhaps with a #:result clause.

Beyond that, when doing performance-sensitive floating-point math, you generally want to replace generic arithmetic operations like * with specialized variants like fl*. Beyond avoiding unnecessary generic dispatch, the floating-point–specific operators can “unbox” their arguments and intermediate results, keeping them in machine floating-point registers rather than storing them on the heap. One way to get this benefit mostly automatically is to use Typed Racket with floating-point types: Typed Racket can compile * to unsafe-fl*, and the Optimization Coach can warn you about places where you may be missing the optimization.

A general note for benchmarks is that you can consider (#%declare #:unsafe)—but you can decide whether that makes a fair comparison or not, and, anyway, it’s better to start by optimizing your safe code.

1 Like
3

You can let it 6x faster by add more code, comment some old code, without touching the hot loop.

I also added a Julia version (same as C code) for compare, with 500k as parameter.

First version on my computer:

=== C (GCC) ===
-0.169237033
timing: 24 ms

=== Common Lisp (SBCL) ===
-0.169237033
timing: 32 ms

=== Racket ===
-0.169237033
timing: 875 ms

=== Julia ===
-0.169237033
timing: 29 ms

First optimization is, define body as flvector instead of struct, then comment the struct definition:

; (struct body (x y z vx vy vz mass) #:prefab #:mutable)

(define (body x y z vx vy vz mass)
  (flvector (real->double-flonum x)
            (real->double-flonum y)
            (real->double-flonum z)
            (real->double-flonum vx)
            (real->double-flonum vy)
            (real->double-flonum vz)
            (real->double-flonum mass)))

(define (body-x b) (unsafe-flvector-ref b 0))
(define (body-y b) (unsafe-flvector-ref b 1))
(define (body-z b) (unsafe-flvector-ref b 2))
(define (body-vx b) (unsafe-flvector-ref b 3))
(define (body-vy b) (unsafe-flvector-ref b 4))
(define (body-vz b) (unsafe-flvector-ref b 5))
(define (body-mass b) (unsafe-flvector-ref b 6))

(define (set-body-x! b v) (unsafe-flvector-set! b 0 v))
(define (set-body-y! b v) (unsafe-flvector-set! b 1 v))
(define (set-body-z! b v) (unsafe-flvector-set! b 2 v))
(define (set-body-vx! b v) (unsafe-flvector-set! b 3 v))
(define (set-body-vy! b v) (unsafe-flvector-set! b 4 v))
(define (set-body-vz! b v) (unsafe-flvector-set! b 5 v))
(define (set-body-mass! b v) (unsafe-flvector-set! b 6 v))

The result is 666ms, 1.3x faster.

Second optimization is, use flonum operations to replace old arithmetic operations in hot loop. Require racket/flonum, then add these code to advance function, before any other code:

(define + fl+)
(define - fl-)
(define * fl*)
(define / fl/)
(define sqrt flsqrt)

The result is 231ms, 3.78x faster than the first version.

In the first for loop of advance, you used set! to modify dx, dy, dz, dsq, and mag. But you can actually define them in the loop, and get rid of set!. The third optimization is, add an evil macro to advance function:

(define-syntax-rule (set! x val) (define x val))

It replaces set! with define (never do this in real code). The result is 136ms, 6.4x faster than the first version! It still cannot compare to C, Common Lisp or Julia, but not that slow.

My extra experiment is extract many duplicate (vector-ref bod-vec i) to a variable, then use this variable:

(for* ([i (in-range NBODIES)]
       [j (in-range (add1 i) NBODIES)])
  (define bi (vector-ref bod-vec i))
  (define bj (vector-ref bod-vec j))

  (define dx (- (body-x bi) (body-x bj)))
  (define dy (- (body-y bi) (body-y bj)))
  (define dz (- (body-z bi) (body-z bj)))
  (define dsq (+ (* dx dx) (* dy dy) (* dz dz)))
  (define mag (/ dt (* dsq (sqrt dsq))))

  (set-body-vx! bi (- (body-vx bi) (* dx mag (body-mass bj))))
  (set-body-vy! bi (- (body-vy bi) (* dy mag (body-mass bj))))
  (set-body-vz! bi (- (body-vz bi) (* dz mag (body-mass bj))))
  (set-body-vx! bj (+ (body-vx bj) (* dx mag (body-mass bi))))
  (set-body-vy! bj (+ (body-vy bj) (* dy mag (body-mass bi))))
  (set-body-vz! bj (+ (body-vz bj) (* dz mag (body-mass bi))))))

This result is 49ms. Only 2x slower than C.

3 Likes
4

one thing to bear in mind is that set! is generally a red flag ... many of your uses of set! could be replaced by changing your for loops to for/fold, perhaps with a #:result clause

Yeah, this is one of the things I was thinking of implementing since I've read about the set! red flag but Couldn't figure out a immediate conversion from C...

when doing performance-sensitive floating-point math, you generally want to replace generic arithmetic operations like * with specialized variants like fl*.

TIL: I didn't know about the fl* operator, always used *, thanks for letting me discoveer it

5

First optimization is, define body as flvector instead of struct, then comment the struct definition:

Thanks to you too, didn't think of it at all, as I said I was too distracted by the C code and ended up as a code mimicking it, surprised that just that made a significant improvement in speed execution

Second optimization is, use flonum operations to replace old arithmetic operations in hot loop. Require racket/flonum, then add these code to advance function, before any other code:

And thanks for this too, I didn't know about this, always used Racket for personal projects and stuck to the simple usual operators, great discovery

This result is 49ms. Only 2x slower than C.

Cool, wasn't expecting such speed, great result!

1 Like
6

Good catch! Even better, you can replace in-range with in-vector like this, which will minimize bounds checks:

(for* ([bi (in-vector bod-vec)]
       [bj (in-vector bod-vec 1)])

  (define dx (- (body-x bi) (body-x bj)))
  (define dy (- (body-y bi) (body-y bj)))
  (define dz (- (body-z bi) (body-z bj)))
  (define dsq (+ (* dx dx) (* dy dy) (* dz dz)))
  (define mag (/ dt (* dsq (sqrt dsq))))

  (set-body-vx! bi (- (body-vx bi) (* dx mag (body-mass bj))))
  (set-body-vy! bi (- (body-vy bi) (* dy mag (body-mass bj))))
  (set-body-vz! bi (- (body-vz bi) (* dz mag (body-mass bj))))
  (set-body-vx! bj (+ (body-vx bj) (* dx mag (body-mass bi))))
  (set-body-vy! bj (+ (body-vy bj) (* dy mag (body-mass bi))))
  (set-body-vz! bj (+ (body-vz bj) (* dz mag (body-mass bi))))))
1 Like