Enormous benchmark speedup

Enormous benchmark speedup

[Juhani Viheräkoski]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 987 bytes --]

Hi,

With recent changes in guile vm there are lots on improvements on 
the Gambit benchmarks. In the worst case some test run 10% slower but there
are huge wins in testcases involving vectors offsetting this. Here are 
*some* of the highlights:

triangl:
-15.57user 0.04system 0:15.72elapsed 99%CPU
+6.69user 0.02system 0:06.73elapsed 99%CPU

fft:
-59.16user 0.14system 0:59.89elapsed 99%CPU
+36.50user 0.07system 0:36.68elapsed 99%CPU

nucleic:
-38.99user 0.31system 0:39.30elapsed 99%CPU 
+24.54user 0.27system 0:24.85elapsed 99%CPU

pnpoly:
-85.52user 0.11system 1:25.69elapsed 99%CPU
+38.64user 0.05system 0:38.82elapsed 99%CPU

array1:
-65.91user 0.31system 1:06.51elapsed 99%CPU
+13.66user 0.25system 0:13.95elapsed 99%CPU

However the following testcase does not run when compiled, all the others 
work fine atm (source code attached):

ack:
guile: uncaught throw to vm-error: (vm-run "VM: Stack overflow" ())

Best Regards,
Juhani Viheräkosi

[-- Attachment #2: Type: TEXT/PLAIN, Size: 142 bytes --]

(define (ack m n)
  (cond ((= m 0) (+ n 1))
        ((= n 0) (ack (- m 1) 1))
        (else (ack (- m 1) (ack m (- n 1))))))

(ack 3 9)

Re: Enormous benchmark speedup

[Ludovic Courtès]

Hi!

Juhani Viheräkoski <moonshine@kapsi.fi> writes:

> With recent changes in guile vm there are lots on improvements on the
> Gambit benchmarks.

Improvements compared to what?

> In the worst case some test run 10% slower

Slower than what?

> but there are huge wins in testcases involving vectors offsetting
> this.

Oh, that's cool, but it feels like we're slightly cheating on these.
;-)

> (define (ack m n)
>   (cond ((= m 0) (+ n 1))
>         ((= n 0) (ack (- m 1) 1))
>         (else (ack (- m 1) (ack m (- n 1))))))
>
> (ack 3 9)

This is not tail-recursive (because of the nested `ack' call in the
`else' clause), which is why it can lead to a stack overflow.

I'm too stupid to compute the maximum "depth" of the call graph, but it
looks like this:

  (ack 3 9)
    (ack 3 8) <--- X
      (ack 3 7)
        ...
          (ack 3 0)
            (ack 2 0)
              ...
                (ack 0 0)
    (ack 2 X)
      (ack 2 (- X 1))  <--- Y
        ...
      (ack 1 Y)
        (ack 1 (- Y 1))
          ...

Thanks,
Ludo'.

Re: Enormous benchmark speedup

[Juhani Viheräkoski]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 1291 bytes --]

> > With recent changes in guile vm there are lots on improvements on the
> > Gambit benchmarks.
>
> Improvements compared to what?

I should have been more concise.. I have run these benchmarks against 
guile HEAD for some time (after I reported a few bugs, performance 
regressions included,  affecting the benchmark suite I have done this 
every once in a while to get some additional test coverage) and now I had 
something to report. Guile I compared to is a git version before vector 
instructions were added to VM. Guile is now a little bit slower 
generally, but significantly faster in many real-world benchmarks using 
vectors.

> > but there are huge wins in testcases involving vectors offsetting
> > this.
> 
> Oh, that's cool, but it feels like we're slightly cheating on these.
> ;-)

Well it seems to be a good cheat then :)

> This is not tail-recursive (because of the nested `ack' call in the
> `else' clause), which is why it can lead to a stack overflow.

I understand that, but I reported this because interpreter (both 1.8.6 and 
1.9.0) run this test successfully but VM does not. Probably real-world 
programs don't have so deep a recursion, although they might when run with 
complex data..

Thanks for your reply,

Juhani Viheräoski

Re: Enormous benchmark speedup

[Andy Wingo]

Hi Juhani,

On Thu 02 Jul 2009 17:49, Juhani Viheräkoski <moonshine@kapsi.fi> writes:

>> > With recent changes in guile vm there are lots on improvements on the
>> > Gambit benchmarks.
>>
>> Improvements compared to what?
>
> I should have been more concise..

You were concise, but not precise ;-)

So here's a project, should you choose to be interested ;-) Sometimes we
do things that we don't know exactly how they affect performance. We're
working on getting decent measurement into Guile's build itself... I
mean, we want to work on it :) But we're not measuring.

I would really, really love a graph of performance over time on the
various Gambit benchmarks.

So for every git revision, a number (and standard deviation?) for every
Gambit benchmark. Ideally displayed in tables and graphs.

I just mention all of this to you because you said at one point that you
liked systematically testing things ;-)

>> This is not tail-recursive (because of the nested `ack' call in the
>> `else' clause), which is why it can lead to a stack overflow.
>
> I understand that, but I reported this because interpreter (both 1.8.6
> and 1.9.0) run this test successfully but VM does not. Probably
> real-world programs don't have so deep a recursion, although they might
> when run with complex data..

This is a bug in the VM. The default stack is low, and we have no
capacity to enlarge it on demand. We should keep it low and enlarge it
on demand via overflow handlers.

Peace,

Andy
-- 
http://wingolog.org/

Re: Enormous benchmark speedup

[Juhani Viheräkoski]

On Thu, 23 Jul 2009, Andy Wingo wrote:

> So here's a project, should you choose to be interested ;-) Sometimes we
> do things that we don't know exactly how they affect performance. We're
> working on getting decent measurement into Guile's build itself... I
> mean, we want to work on it :) But we're not measuring.
>
> I would really, really love a graph of performance over time on the
> various Gambit benchmarks.
>
> So for every git revision, a number (and standard deviation?) for every
> Gambit benchmark. Ideally displayed in tables and graphs.
>
> I just mention all of this to you because you said at one point that you
> liked systematically testing things ;-)

At least I could easily put raw logs available to my webpage, I run the 
benchmarks by hand anyway. Then I could try to polish my hacked benchmark 
suite and send it upstream. There were some bugs introduced by my porting 
efforts, I *think* I've fixed them all now :) If someone wants to try it 
it's now available at
http://moonshine.kapsi.fi/bench-guile.tar.bz2

I am currently running the benchmarks and I will put the results for 
master (compiled and interpreted) and 1.8.6 in text format to 
http://moonshine.kapsi.fi/guile-results when finished. I'll try to hack 
something neater during the next week or so. BTW, does anyone know if 
there are guile bindings for any graphic library as I couldn't find any? 
If there aren't, I'll do it in perl then, although I don't especially like 
perl.

-- 
Juhani

tfib.scm

[Juhani Viheräkoski]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 1271 bytes --]

> At least I could easily put raw logs available to my webpage, I run the 
> benchmarks by hand anyway. Then I could try to polish my hacked benchmark 
> suite and send it upstream. There were some bugs introduced by my porting 
> efforts, I *think* I've fixed them all now :) If someone wants to try it it's 
> now available at
> http://moonshine.kapsi.fi/bench-guile.tar.bz2
>
> I am currently running the benchmarks and I will put the results for master 
> (compiled and interpreted) and 1.8.6 in text format to 
> http://moonshine.kapsi.fi/guile-results when finished. I'll try to hack 
> something neater during the next week or so. BTW, does anyone know if there 
> are guile bindings for any graphic library as I couldn't find any? If there 
> aren't, I'll do it in perl then, although I don't especially like perl.

Hi,

Results for guile-head are there, however not for 1.8.6 because I think 
there is a problem with threads (at least the same testcase works with git 
version). This program creates lots of threads but should only take some 
milliseconds to run on Linux. It goes into an infinite loop, or at least
takes a very long time to execute as it run for several hours in the 
background while I was doing something else. Testcase attached.

-- 
Juhani

[-- Attachment #2: Type: TEXT/PLAIN, Size: 6762 bytes --]



;------------------------------------------------------------------------------

(define (run-bench name count ok? run)
  (let loop ((i count) (result '(undefined)))
    (if (< 0 i)
      (loop (- i 1) (run))
      result)))

(define (run-benchmark name count ok? run-maker . args)
  (newline)
  (let* ((run (apply run-maker args))
         (result (run-bench name count ok? run)))
    (if (not (ok? result))
      (begin
        (display "*** wrong result ***")
        (newline)
        (display "*** got: ")
        (write result)
        (newline)))))

(define (fatal-error . args)
  (for-each display args)
  (newline)
  (exit 1))

 (define (call-with-output-file/truncate filename proc)
   (call-with-output-file filename proc))

;------------------------------------------------------------------------------

; Macros...

; Specialize fixnum and flonum arithmetic.

;; This code should be used when f64vectors are available.
;(def-macro (FLOATvector-const . lst)   `',(list->f64vector lst))
;(def-macro (FLOATvector? x)            `(f64vector? ,x))
;(def-macro (FLOATvector . lst)         `(f64vector ,@lst))
;(def-macro (FLOATmake-vector n . init) `(make-f64vector ,n ,@init))
;(def-macro (FLOATvector-ref v i)       `(f64vector-ref ,v ,i))
;(def-macro (FLOATvector-set! v i x)    `(f64vector-set! ,v ,i ,x))
;(def-macro (FLOATvector-length v)      `(f64vector-length ,v))
;
;(def-macro (nuc-const . lst)
;  `',(list->vector
;       (map (lambda (x)
;              (if (vector? x)
;                (list->f64vector (vector->list x))
;                x))
;            lst)))

(define make-thread call-with-new-thread)
(define thread-join! join-thread)
(define (thread-start! x) #f)
(define-macro (bitwise-or . lst) `(logior ,@lst))
(define-macro (bitwise-and . lst) `(logand ,@lst))
(define-macro (bitwise-not . lst) `(lognot ,@lst))


; Don't specialize fixnum and flonum arithmetic.

(define-macro (FLOATvector-const . lst)   `',(list->vector lst))
(define-macro (FLOATvector? x)            `(vector? ,x))
(define-macro (FLOATvector . lst)         `(vector ,@lst))
(define-macro (FLOATmake-vector n . init) `(make-vector ,n ,@init))
(define-macro (FLOATvector-ref v i)       `(vector-ref ,v ,i))
(define-macro (FLOATvector-set! v i x)    `(vector-set! ,v ,i ,x))
(define-macro (FLOATvector-length v)      `(vector-length ,v))

(define-macro (nuc-const . lst)
  `',(list->vector lst))

(define-macro (FLOAT+ . lst) `(+ ,@lst))
(define-macro (FLOAT- . lst) `(- ,@lst))
(define-macro (FLOAT* . lst) `(* ,@lst))
(define-macro (FLOAT/ . lst) `(/ ,@lst))
(define-macro (FLOAT= . lst)  `(= ,@lst))
(define-macro (FLOAT< . lst)  `(< ,@lst))
(define-macro (FLOAT<= . lst) `(<= ,@lst))
(define-macro (FLOAT> . lst)  `(> ,@lst))
(define-macro (FLOAT>= . lst) `(>= ,@lst))
(define-macro (FLOATnegative? . lst) `(negative? ,@lst))
(define-macro (FLOATpositive? . lst) `(positive? ,@lst))
(define-macro (FLOATzero? . lst)     `(zero? ,@lst))
(define-macro (FLOATabs . lst) `(abs ,@lst))
(define-macro (FLOATsin . lst) `(sin ,@lst))
(define-macro (FLOATcos . lst) `(cos ,@lst))
(define-macro (FLOATatan . lst) `(atan ,@lst))
(define-macro (FLOATsqrt . lst) `(sqrt ,@lst))
(define-macro (FLOATmin . lst) `(min ,@lst))
(define-macro (FLOATmax . lst) `(max ,@lst))
(define-macro (FLOATround . lst) `(round ,@lst))
(define-macro (FLOATinexact->exact . lst) `(inexact->exact ,@lst))

(define-macro (GENERIC+ . lst) `(+ ,@lst))
(define-macro (GENERIC- . lst) `(- ,@lst))
(define-macro (GENERIC* . lst) `(* ,@lst))
(define-macro (GENERIC/ . lst) `(/ ,@lst))
(define-macro (GENERICquotient . lst)  `(quotient ,@lst))
(define-macro (GENERICremainder . lst) `(remainder ,@lst))
(define-macro (GENERICmodulo . lst)    `(modulo ,@lst))
(define-macro (GENERIC= . lst)  `(= ,@lst))
(define-macro (GENERIC< . lst)  `(< ,@lst))
(define-macro (GENERIC<= . lst) `(<= ,@lst))
(define-macro (GENERIC> . lst)  `(> ,@lst))
(define-macro (GENERIC>= . lst) `(>= ,@lst))
(define-macro (GENERICexpt . lst) `(expt ,@lst))


;------------------------------------------------------------------------------
; Gabriel benchmarks
(define boyer-iters         2)
(define browse-iters       60)
(define cpstak-iters      100)
(define ctak-iters         1)
(define dderiv-iters   200000)
(define deriv-iters    200000)
(define destruc-iters      50)
(define diviter-iters  100000)
(define divrec-iters   100000)
(define puzzle-iters       10)
(define tak-iters         200)
(define takl-iters         30)
(define trav1-iters        10)
(define trav2-iters         2)
(define triangl-iters       1)

; Kernighan and Van Wyk benchmarks
(define ack-iters           1)
(define array1-iters        1)
(define cat-iters           1)
(define string-iters        1)
(define sum1-iters          1)
(define sumloop-iters       1)
(define tail-iters          1)
(define wc-iters            1)

; C benchmarks
(define fft-iters        2000)
(define fib-iters           5)
(define fibfp-iters         2)
(define mbrot-iters       100)
(define nucleic-iters       5)
(define pnpoly-iters   100000)
(define sum-iters       10000)
(define sumfp-iters      5000)
(define tfib-iters         20)

; Other benchmarks
(define conform-iters       4)
(define dynamic-iters       2)
(define earley-iters       20)
(define fibc-iters         50)
(define graphs-iters       30)
(define lattice-iters       1)
(define matrix-iters       40)
(define maze-iters        400)
(define mazefun-iters     100)
(define nqueens-iters     200)
(define paraffins-iters   100)
(define peval-iters        20)
(define pi-iters            1)
(define primes-iters    10000)
(define ray-iters           1)
(define scheme-iters     20000)
(define simplex-iters   10000)
(define slatex-iters        2)
(define perm9-iters         1)
(define nboyer-iters       10)
(define sboyer-iters       10)
(define gcbench-iters       1)
(define compiler-iters     30)
;;; TFIB -- Like FIB but using threads.

(define (tfib n)
  (if (< n 2)
      1
      (let ((x (make-thread (lambda () (tfib (- n 2))))))
        (thread-start! x)
        (let ((y (tfib (- n 1))))
          (+ (thread-join! x) y)))))

(define (go n repeat)
  (let loop ((repeat repeat)
             (result '()))
    (if (> repeat 0)
        (let ((x (make-thread (lambda () (tfib n)))))
          (thread-start! x)
          (let ((r (thread-join! x)))
            (loop (- repeat 1) r)))
        result)))

(define (main . args)
  (run-benchmark
   "tfib"
   tfib-iters
   (lambda (result) (equal? result 610))
   (lambda (n repeat) (lambda () (go n repeat)))
   14
   100))
(main)