Потоки ракетки медленнее, чем пользовательские? - PullRequest
Новая
       13

Потоки ракетки медленнее, чем пользовательские?

6 голосов
/ 13 мая 2019

Я внедрил простое и не очень эффективное сито из эратосфена. Один раз для встроенных ракетных потоков и один раз для самостоятельно определенных потоков. Единственное известное для меня отличие состоит в том, что встроенные потоки оценивают первый элемент по вызову, а не в процессе строительства. При оценке первых 1000 простых чисел в обеих реализациях самоопределяемые потоки работают в 10-20 раз быстрее. Есть ли объяснение? 

(define (integers-starting-from-stream n)
  (stream-cons n (integers-starting-from-stream (+ n 1))))

(define (stream-limit s limit)
    (when (not (= limit 0)) (stream-limit (stream-rest s) (- limit 1))))

(define x (integers-starting-from-stream 2))

(define (divisible? x y)
  (= (remainder x y) 0))

(define (sieve s)
  (stream-cons
   (stream-first s)
   (sieve (stream-filter
           (lambda (x)
             (not (divisible? x (stream-first s))))
           (stream-rest s)))))
(time (stream-limit (sieve x) 1000))

Или я что-то не так влияю на производительность? 

(define-syntax-rule (s-delay exp)
  (λ() exp))

(define (s-force delayedObject)
  (delayedObject))

(define empty-s 'S-EMPTY-STREAM)

(define (s-empty? s)
  (eq? s empty-s))

(define (s-first s)
  (car s))

(define (s-rest s)
  (s-force (cdr s)))

(define-syntax-rule (s-cons a b)
  (cons a (s-delay b)))
(define (s-filter p s)
  (cond ((s-empty? s) empty-s)
        ((p (s-first s))
         (s-cons (s-first s)
                 (s-filter p (s-rest s))))
        (else (s-filter p (s-rest s)))))
;;;;;;;;;;;;;;;;;;;;
(define (divisible? x y)
  (= (remainder x y) 0))

(define (integers-starting-from n)
  (s-cons n (integers-starting-from (+ n 1))))

(define (s-limit s limit)
    (when (not (= limit 0)) (s-limit (s-rest s) (- limit 1))))

(define x (integers-starting-from 2))

(define (sieve s)
  (s-cons (s-first s) (sieve (s-filter (lambda(x) (not (divisible? x (s-first s)))) (s-rest s)))))
(time (s-limit (sieve x) 1000))

1 Ответ

4 голосов
/ 14 мая 2019

Вот наблюдение:

Использование версии integers-starting-from-stream, которая печатает числа по мере их генерации: 

(define (integers-starting-from-stream n)
  (stream-cons n
               (begin
                 (display (~a n " "))
                 (integers-starting-from-stream (+ n 1)))))

И аналогично: 

(define (integers-starting-from n)
  (s-cons n
          (begin (display (~a n " "))
                 (integers-starting-from (+ n 1)))))

Мы можем проверить с помощью: 

(collect-garbage) (collect-garbage) (collect-garbage)
(time (stream-limit (sieve x) 10))
(collect-garbage) (collect-garbage) (collect-garbage)
(time (s-limit (s-sieve s-x) 10))

Мы видим, что потоковая версия печатает числа от 2 до 51, где в s-версии печатаются числа от 2 до 30.

список, создаваемый версией потока, имеет почти двойной размер.

Это первая (и самая важная) причина, по которой версия потока медленнее, чем пользовательская версия.

Вторая причина версии потокамедленнее, то, что потоковая версия кэширует результат stream-first.Кэширование, как правило, будет быстрее, когда вычисление элемента будет медленным. 

(define (integers-starting-from-stream n)
  (stream-cons (begin (sleep 1) n)
               (integers-starting-from-stream (+ n 1))))

и 

(define (integers-starting-from n)
  (s-cons (begin (sleep 1) n)
          (integers-starting-from (+ n 1))))

И затем выполните: 

(collect-garbage) (collect-garbage) (collect-garbage)
(define x (integers-starting-from-stream 2))
(time (stream-limit x 10))
(time (stream-limit x 10))
(collect-garbage) (collect-garbage) (collect-garbage)
(define s-x (integers-starting-from 2))
(time (s-limit s-x 10))
(time (s-limit s-x 10))
...