Performance impact of top level definitions

Performance impact of top level definitions

[Brian]

Hello,

Today I found that top level defines have a significant performance
impact on Guile (2.2.3). The following program takes about 108 seconds
to complete on my ThinkPad (an i5-5200U with Arch Linux):

(define node cons)
(define node-left car)
(define node-right cdr)

(define (make d)
  (if (= d 0)
      (node #f #f)
      (let ([d2 (1- d)])
        (node (make d2) (make d2)))))

(define (check t)
  (if (node-left t)
      (+ 1 (check (node-left t)) (check (node-right t)))
      1))

(define (main n)
  (define min-depth 4)
  (define max-depth (max (+ min-depth 2) n))
  (define stretch-depth (1+ max-depth))
  (format #t "stretch tree of depth ~a\t check: ~a\n" stretch-depth
(check (make stretch-depth)))
  (let ([long-lived-tree (make max-depth)])
    (do ([d 4 (+ d 2)]) ([not (< d (1+ max-depth))])
      (let ([iterations (ash 1 (+ (- max-depth d) min-depth))])
        (format #t "~a\t trees of depth ~a\t check: ~a\n"
                iterations
                d
                (let sum ([i iterations] [n 0])
                  (if (zero? i)
                      n
                      (sum (1- i) (+ n (check (make d)))))))))
    (format #t "long lived tree of depth ~a\t check: ~a\n"
            max-depth
            (check long-lived-tree))))

(main 21)


By simply wrapping that code in a lambda the program finished in about
47 seconds. Using lets instead of defines is equally effective.

I was quite surprised because I initially thought some optimization
would just substitute those useless nodes symbols away, but it seems
like that's not the case...

Cheers!

Re: Performance impact of top level definitions

[Mark H Weaver]

Hi Brian,

Brian <gomesbascoy@gmail.com> writes:

> Today I found that top level defines have a significant performance
> impact on Guile (2.2.3). The following program takes about 108 seconds
> to complete on my ThinkPad (an i5-5200U with Arch Linux):
[...]
> By simply wrapping that code in a lambda the program finished in about
> 47 seconds. Using lets instead of defines is equally effective.
>
> I was quite surprised because I initially thought some optimization
> would just substitute those useless nodes symbols away, but it seems
> like that's not the case...

Right.  The problem is that toplevel variables can be mutated by
arbitrary code from other modules, e.g. by 'module-set!', so the
compiler cannot make any assumptions about what values those variables
will contain at runtime.

For non-toplevel variables, the situation is quite different.  In
Scheme, non-toplevel variables can be accessed only from within their
lexical scope, so if such a variable is not 'set!' from within its
scope, the compiler knows that it can never be mutated.  In that case,
it can assume that the variable will always contain its initial value,
which enables a great many optimizations including partial evaluation.

       Mark

Re: Performance impact of top level definitions

[Brian]

Hi Mark,

Thanks for that explanation, it makes sense now to me.

Cheers!


On Mon, 2018-05-14 at 22:55 -0400, Mark H Weaver wrote:
> Hi Brian,
> 
> Brian <gomesbascoy@gmail.com> writes:
> 
> > Today I found that top level defines have a significant performance
> > impact on Guile (2.2.3). The following program takes about 108
> > seconds
> > to complete on my ThinkPad (an i5-5200U with Arch Linux):
> 
> [...]
> > By simply wrapping that code in a lambda the program finished in
> > about
> > 47 seconds. Using lets instead of defines is equally effective.
> > 
> > I was quite surprised because I initially thought some optimization
> > would just substitute those useless nodes symbols away, but it
> > seems
> > like that's not the case...
> 
> Right.  The problem is that toplevel variables can be mutated by
> arbitrary code from other modules, e.g. by 'module-set!', so the
> compiler cannot make any assumptions about what values those
> variables
> will contain at runtime.
> 
> For non-toplevel variables, the situation is quite different.  In
> Scheme, non-toplevel variables can be accessed only from within their
> lexical scope, so if such a variable is not 'set!' from within its
> scope, the compiler knows that it can never be mutated.  In that
> case,
> it can assume that the variable will always contain its initial
> value,
> which enables a great many optimizations including partial
> evaluation.
> 
>        Mark