Arc Forumnew | comments | leaders | submitlogin
No faster, and call for benchmarks
8 points by conanite 5549 days ago | 4 comments
I tried a tiny little change to the definition of no to see if it would run a little faster. Please excuse the microoptimisation, but no is used everywhere, making it a little faster is probably worth it. These tests were run with arc3.1 on scheme.

with the original (def no (x) (is x nil))

                       avg        min        max       
  arc-code-tokeniser   282.15     269        329       
  find-top-numbers     174.915    172        220       
  generate-primes      67.24      65         107  
  sort-random-numbers  263.365    258        315       
  string-tokeniser     133.84     129        180
with (def no (x) (if x nil t))

                       avg        min        max       
  arc-code-tokeniser   269.97     258        331       
  find-top-numbers     168.415    166        218       
  generate-primes      60.48      58         100  
  sort-random-numbers  248.405    243        290       
  string-tokeniser     112.395    108        158
Admittedly, the faster 'no is one entire token less concise, and it's not quite as intuitively readable, so you might not want this (potential 4% depending on your criteria) gain in speed.

For comparison, this is how rainbow is performing:

                       avg        min        max       
  arc-code-tokeniser   238.45     220        370       
  find-top-numbers     75.625     69         139       
  generate-primes      71.41      68         116       
  sort-random-numbers  103.635    99         239       
  string-tokeniser     103.62     97         122
I'd like to assemble a few more benchmark cases to build a more thorough suite. Please share your ideas on the kinds of things that should be tested. Or even contribute your favourite frustratingly slow function. The "find top numbers" test is an adaptation of the test in the comment at the bottom of arc.arc.

Each test case, for both scheme and java, is run 200 times to warm-up, and then 200 times for the actual measurements. The suite is run in each case from a cold start of the interpreter. If you'd like more details, shout, I'll be happy to be more verbose about it.



2 points by fallintothis 5546 days ago | link

An easy source of ideas is, of course, the Benchmarks Game: http://shootout.alioth.debian.org/. Someone would still need to implement them, but there are plenty of Lisp examples (e.g., http://shootout.alioth.debian.org/u32q/lisp.php).

-----

2 points by fallintothis 5546 days ago | link

Another benchmark ported from an SBCL version (http://shootout.alioth.debian.org/u32q/benchmark.php?test=pi...), pidigits:

  (= digits-per-line*     10
     default-stop-digits* 1000)

  (def make-digit-generator ()
    (with (zq 1 zr 0 zt 1 k 0 4k+2 2 2k+1 1)
      (with (extract [trunc:/ (+ (* zq _) zr) zt]
             comp    (fn (aq ar at bq br bt)
                       (= zq (* aq bq)
                          zr (+ (* aq br) (* ar bt))
                          zt (* at bt))))
        (fn ()
          (let y (extract 3)
            (until (is y (extract 4))
              (comp zq zr zt (++ k) (++ 4k+2 4) (++ 2k+1 2))
              (= y (extract 3)))
            (comp 10 (* -10 y) 1 zq zr zt)
            y)))))

  (def spigot ((o digits default-stop-digits*))
    (with (digits-printed 0
           next-digit     (make-digit-generator))
      (while (> digits 0)
        (if (>= digits digits-per-line*)
            (do (repeat digits-per-line* (pr (next-digit)))
                (++ digits-printed digits-per-line*))
            (do (repeat digits (pr (next-digit)))
                (sp (- digits-per-line* digits))
                (++ digits-printed digits)))
        (prn "\t:" digits-printed)
        (-- digits digits-per-line*))))

  (= benchmark time:spigot)
Then

  Use (quit) to quit, (tl) to return here after an interrupt.
  arc> (load "pidigits.arc")
  nil
  arc> (benchmark)
  3141592653      :10
  5897932384      :20
  6264338327      :30
  9502884197      :40
  1693993751      :50
  0582097494      :60
  4592307816      :70
  4062862089      :80
  9862803482      :90
  5342117067      :100
  9821480865      :110
  1328230664      :120
  7093844609      :130
  5505822317      :140
  2535940812      :150
  8481117450      :160
  2841027019      :170
  3852110555      :180
  9644622948      :190
  9549303819      :200
  6442881097      :210
  5665933446      :220
  1284756482      :230
  3378678316      :240
  5271201909      :250
  1456485669      :260
  2346034861      :270
  0454326648      :280
  2133936072      :290
  6024914127      :300
  3724587006      :310
  6063155881      :320
  7488152092      :330
  0962829254      :340
  0917153643      :350
  6789259036      :360
  0011330530      :370
  5488204665      :380
  2138414695      :390
  1941511609      :400
  4330572703      :410
  6575959195      :420
  3092186117      :430
  3819326117      :440
  9310511854      :450
  8074462379      :460
  9627495673      :470
  5188575272      :480
  4891227938      :490
  1830119491      :500
  2983367336      :510
  2440656643      :520
  0860213949      :530
  4639522473      :540
  7190702179      :550
  8609437027      :560
  7053921717      :570
  6293176752      :580
  3846748184      :590
  6766940513      :600
  2000568127      :610
  1452635608      :620
  2778577134      :630
  2757789609      :640
  1736371787      :650
  2146844090      :660
  1224953430      :670
  1465495853      :680
  7105079227      :690
  9689258923      :700
  5420199561      :710
  1212902196      :720
  0864034418      :730
  1598136297      :740
  7477130996      :750
  0518707211      :760
  3499999983      :770
  7297804995      :780
  1059731732      :790
  8160963185      :800
  9502445945      :810
  5346908302      :820
  6425223082      :830
  5334468503      :840
  5261931188      :850
  1710100031      :860
  3783875288      :870
  6587533208      :880
  3814206171      :890
  7766914730      :900
  3598253490      :910
  4287554687      :920
  3115956286      :930
  3882353787      :940
  5937519577      :950
  8185778053      :960
  2171226806      :970
  6130019278      :980
  7661119590      :990
  9216420198      :1000
  time: 94562 msec.
  nil
Versus the same run in GNU clisp with the Shootout's SBCL code:

  > (time (spigot 1000))

  [OUTPUT ELIDED]

  Real time: 1.022299 sec.
  Run time: 0.888055 sec.
  Space: 104310256 Bytes
  GC: 133, GC time: 0.420025 sec.
  NIL
Their outputs were the same, so the Arc program seems to be working (to say nothing of its optimality; I basically did a straight port). This benchmark's fun if only because you get to watch pi being calculated before your eyes. Nifty algorithm.

-----

2 points by conanite 5539 days ago | link

This is an awesome reference, thanks. I'll be using a few of these. The pi calculation uncovered a rainbow weakness: rainbow relies on java "long" integers for 'int types; but these are 64-bit signed integers and the algorithm fails at the 5th digit. So I'll need to think of a way to incorporate arbitrary-precision maths before I can run this benchmark. One thing is certain: using java's BigXXX family of numeric types is going to hurt.

-----

1 point by fallintothis 5546 days ago | link

For instance, here's a (pretty direct) port of the SBCL nbody benchmark (http://shootout.alioth.debian.org/u32q/benchmark.php?test=nb...):

  (= pi             (* 4 (atan 1))
     days-per-year* 365.24d0
     solar-mass*    (* 4d0 pi pi))

  (def make-body (x y z vx vy vz mass)
    (obj x x y y z z vx vx vy vy vz vz mass mass))

  (= jupiter* (make-body 4.84143144246472090d0
                         -1.16032004402742839d0
                         -1.03622044471123109d-1
                         (* 1.66007664274403694d-3 days-per-year*)
                         (* 7.69901118419740425d-3 days-per-year*)
                         (* -6.90460016972063023d-5  days-per-year*)
                         (* 9.54791938424326609d-4 solar-mass*)))

  (= saturn* (make-body 8.34336671824457987d0
                        4.12479856412430479d0
                        -4.03523417114321381d-1
                        (* -2.76742510726862411d-3 days-per-year*)
                        (* 4.99852801234917238d-3 days-per-year*)
                        (* 2.30417297573763929d-5 days-per-year*)
                        (* 2.85885980666130812d-4 solar-mass*)))

  (= uranus* (make-body 1.28943695621391310d1
                        -1.51111514016986312d1
                        -2.23307578892655734d-1
                        (* 2.96460137564761618d-03 days-per-year*)
                        (* 2.37847173959480950d-03 days-per-year*)
                        (* -2.96589568540237556d-05 days-per-year*)
                        (* 4.36624404335156298d-05 solar-mass*)))

  (= neptune* (make-body 1.53796971148509165d+01
                         -2.59193146099879641d+01
                         1.79258772950371181d-01
                         (* 2.68067772490389322d-03 days-per-year*)
                         (* 1.62824170038242295d-03 days-per-year*)
                         (* -9.51592254519715870d-05 days-per-year*)
                         (* 5.15138902046611451d-05 solar-mass*)))

  (= sun* (make-body 0.0d0 0.0d0 0.0d0 0.0d0 0.0d0 0.0d0 solar-mass*))

  (def apply-forces (a b dt)
    (withs (dx    (- (a 'x) (b 'x))
            dy    (- (a 'y) (b 'y))
            dz    (- (a 'z) (b 'z))
            d     (sqrt (+ (expt dx 2) (expt dy 2) (expt dz 2)))
            mag   (/ dt (expt d 3))
            dxmag (* dx mag)
            dymag (* dy mag)
            dzmag (* dz mag))
      (-- (a 'vx) (* dxmag (b 'mass)))
      (-- (a 'vy) (* dymag (b 'mass)))
      (-- (a 'vz) (* dzmag (b 'mass)))
      (++ (b 'vx) (* dxmag (a 'mass)))
      (++ (b 'vy) (* dymag (a 'mass)))
      (++ (b 'vz) (* dzmag (a 'mass)))))

  (def advance (solar-system dt)
    (on a solar-system
      (for i (+ index 1) (- (len solar-system) 1)
        (apply-forces a (solar-system i) dt)))
    (each b solar-system
      (++ (b 'x) (* dt (b 'vx)))
      (++ (b 'y) (* dt (b 'vy)))
      (++ (b 'z) (* dt (b 'vz)))))

  (def energy (solar-system)
    (let e 0.0d0
      (on a solar-system
        (++ e (* 0.5d0
                 (a 'mass)
                 (+ (expt (a 'vx) 2)
                    (expt (a 'vy) 2)
                    (expt (a 'vz) 2))))
        (for i (+ index 1) (- (len solar-system) 1)
          (withs (b  (solar-system i)
                  dx (- (a 'x) (b 'x))
                  dy (- (a 'y) (b 'y))
                  dz (- (a 'z) (b 'z))
                  d  (sqrt (+ (expt dx 2) (expt dy 2) (expt dz 2))))
            (-- e (/ (* (a 'mass) (b 'mass)) d)))))
      e))

  (def offset-momentum (solar-system)
    (with (px 0.0d0
           py 0.0d0
           pz 0.0d0)
      (each p solar-system
        (++ px (* (p 'vx) (p 'mass)))
        (++ py (* (p 'vy) (p 'mass)))
        (++ pz (* (p 'vz) (p 'mass))))
      (= ((car solar-system) 'vx) (/ (- px) solar-mass*)
         ((car solar-system) 'vy) (/ (- py) solar-mass*)
         ((car solar-system) 'vz) (/ (- pz) solar-mass*))))

  (def nbody (n)
    (let solar-system (list sun* jupiter* saturn* uranus* neptune*)
      (offset-momentum solar-system)
      (prn (energy solar-system))
      (repeat n (advance solar-system 0.01d0))
      (prn (energy solar-system))
      nil))
I didn't have the patience to wait for Arc to finish the benchmark's n = 50,000,000 (gives you an idea of how well it performs!), but on smaller values it seems correct.

  arc> (load "nbody.arc")
  nil
  arc> (time (nbody 50000))
  -0.16907516382852447
  -0.16907807065934496
  time: 30905 msec.
  nil
The reference implementation, run from a GNU clisp REPL (though I suppose I should use SBCL for a fairer time comparison, I'm just interested in the accuracy of the Arc results with this run):

  > (time (nbody 50000))
  -0.169075164
  -0.169078071
  Real time: 37.575706 sec.
  Run time: 32.862053 sec.
  Space: 374412048 Bytes
  GC: 477, GC time: 1.836092 sec.
  NIL

-----