Схема размещения Chez: --program vs --script - PullRequest
4 голосов
/ 04 марта 2010

Рассмотрим этот бит Схема Chez код:

(import (chezscheme))

(define (list-enumerate ls val proc)
  (let loop ((ls ls) (return? #f) (val val))
    (if (or (null? ls)
            return?)
        val
        (call-with-values (lambda () (proc val (car ls)))
          (lambda (return? val)
            (loop (cdr ls) return? val))))))

(define (list-index ls proc)
  (list-enumerate ls
                  0
                  (lambda (i elt)
                    (if (proc elt)
                        (values #t i)
                        (values #f (+ i 1))))))

(define n 100000)

(define data (iota n))

(time (list-index data (lambda (elt) (= elt (- n 1)))))

Запустите его:

~ $ scheme --script ~/scratch/_list-enumerate-allocation-test-chez-a.sps 
(time (list-index data ...))
    no collections
    3 ms elapsed cpu time
    4 ms elapsed real time
    8 bytes allocated

Ничего себе, он сообщает, что было выделено только 8 байтов.

Давайте запустим его снова, используя параметр --program вместо --script:

~ $ scheme --program ~/scratch/_list-enumerate-allocation-test-chez-a.sps 
(time (list-index data ...))
    no collections
    3 ms elapsed cpu time
    3 ms elapsed real time
    800000 bytes allocated

Yikes, выделено 800000 байт.

В чем разница?

Ed

1 Ответ

4 голосов
/ 04 марта 2010

Вот записка Кента Дибвига в ответ:


Это интересный вопрос.

При запуске с --script, который использует семантику REPL, переменные определенные в сценарии, такие как list-enumerate и list-index, являются изменяемыми, который препятствует межпроцедурной оптимизации, включая встраивание. когда запустить с --program, однако переменные являются неизменяемыми, что позволяет межпроцедурные оптимизации.

В этом случае --program позволяет компилятору встроить список-перечисление в тело list-index и, в свою очередь, лямбда-выражение в list-index тело в тело списка-перечисления. Конечный результат является условным выражение в выражении производителя вызова со значениями. Это вызывает компилятор для создания замыкания для потребителя, чтобы избежать кода дублирование вдоль тогда и еще ветвей условного. это замыкание создается каждый раз через цикл list-enumerate, что приводит к дополнительные накладные расходы. Так часто идут оптимизации. В основном вы выигрываете, но иногда вы проигрываете. Хорошая новость заключается в том, что Преимущества, превышающие его, он стоит даже в вашей программе. Я позвонил list-index в цикле (модифицированный код ниже) и обнаружил, что это с --программа, код работает примерно на 30% быстрее.

Kent


(import (chezscheme))

(define (list-enumerate ls val proc)
  (let loop ((ls ls) (return? #f) (val val))
    (if (or (null? ls)
            return?)
        val
        (call-with-values (lambda () (proc val (car ls)))
          (lambda (return? val)
            (loop (cdr ls) return? val))))))

(define (list-index ls proc)
  (list-enumerate ls
                  0
                  (lambda (i elt)
                    (if (proc elt)
                        (values #t i)
                        (values #f (+ i 1))))))

(define n 100000)

(define data (time (iota n)))

(let ()
(define runalot
  (lambda (i thunk)
    (let loop ([i i])
      (let ([x (thunk)])
        (if (fx= i 1)
            x
            (loop (fx- i 1)))))))

(time
  (runalot 1000
    (lambda ()
      (list-index data (lambda (elt) (= elt (- n 1))))))))
...