Почему реализация Racket намного быстрее, чем MIT Scheme? - PullRequest
Новая
       85

Почему реализация Racket намного быстрее, чем MIT Scheme?

2 голосов
/ 02 февраля 2020

В следующем коде используется евклидов алгоритм для вычисления gcd (a, b) и целых чисел s, t, таких что sa + tb = gcd (a, b) (для курса дискретной математики). Я кодировал его в C, и, возможно, это наглядно проиллюстрирует алгоритм.

gcd. c: 

#include <stdio.h>

int gcd_st(int m, int n, int *s, int *t) {
  int a, b, res, tmp;
  a = m>n?m:n;
  b = m>n?n:m;
  if(!b) {
    *s = 1;
    *t = 0;
    return a;
  }
  res = gcd_st(b, a%b, s, t);
  tmp = *t;
  *t = *s - *t*(a/b);
  *s = tmp;
  return res;
}

int main() {
  int st[2];
  for(int i=0; i<100000000; i++)
    gcd_st(42, 56, st, st+1);
  for(int i=0; i<100000000; i++)
    gcd_st(273, 110, st, st+1);

  int res = gcd_st(42, 56, st, st+1);
  printf("%d %d %d\n", res, st[0], st[1]);

  res = gcd_st(273, 110, st, st+1);
  printf("%d %d %d\n", res, st[0], st[1]);
}

Ради интереса я решил закодировать его в Scheme (Lisp) также. Сначала я протестировал его на реализации схемы MIT, а затем с помощью реализации Racket.

gcd.scm (без первых двух строк); gcd.rkt (включая первые две строки): 

#!/usr/bin/racket
#lang racket/base

(define (gcd_st m n)
  (let ((a (max m n)) (b (min m n)))
    (if (= b 0) (list a 1 0)
      (let ((res (gcd_st b (remainder a b))))
        (let ((val (list-ref res 0))
          (s (list-ref res 1))
          (t (list-ref res 2)))
            (list val t (- s (* t (quotient a b)))))))))

(define (loop n fn)
  (if (= n 0) 0
      (loop (- n 1) fn)))

(loop 100000000 (lambda () (gcd_st 42 56)))
(loop 100000000 (lambda () (gcd_st 273 110)))

(display "a b: (gcd s t)\n42 56: ")
(display (gcd_st 42 56))
(display "\n273 110: ")
(display (gcd_st 273 110))
(display "\n")

Обе программы запускают 10 ^ 8 итераций в двух примерах и выдают одинаковый результат. Однако две реализации Схемы (которые используют один и тот же код / ​​алгоритм) сильно отличаются по производительности. Реализация Racket также намного быстрее, чем реализация C, которая, в свою очередь, намного быстрее, чем реализация MIT-схемы.

Разница во времени настолько драматична c Я подумал, что, возможно, Racket оптимизировал из всего l oop, так как результат никогда не используется, но время все еще кажется линейно масштабируемым с l oop итерациями. Возможно ли, что он делает некоторый самоанализ и оптимизирует некоторый код в l oop? 

$ time ./gcd.rkt  # Racket
0
0
a b: (gcd s t)
42 56: (14 1 -1)
273 110: (1 27 -67)

real  0m0.590s
user  0m0.565s
sys 0m0.023s

$ time scheme --quiet <gcd.scm  # MIT-Scheme
a b: (gcd s t)
42 56: (14 1 -1)
273 110: (1 27 -67)

real  0m59.250s
user  0m58.886s
sys 0m0.129s

$ time ./gcd.out  # C 
14 1 -1
1 27 -67

real  0m7.987s
user  0m7.967s
sys 0m0.000s

Почему реализация Racket намного быстрее?

=== ==

Обновление : Если кому-то интересно, вот результаты с использованием исправленной функции l oop с учетом ответа:

loop: 

(define (loop n fn)
    (fn)
    (if (= n 1) 0
        (loop (- n 1) fn)))

Ракетка (все еще немного превосходит C, даже включая время ее установки): 

real    0m7.544s
user    0m7.472s
sys 0m0.050s

Схема MIT 

real    9m59.392s
user    9m57.568s
sys 0m0.113s

Вопрос о большом Разница между реализациями Схемы (все еще большая), однако. Я попрошу об этом отдельно, чтобы игнорировать путаницу с предыдущей ошибкой.

1 Ответ

5 голосов
/ 02 февраля 2020

Вы на самом деле не вызываете ваш thunk, который вызывает вычисления в вашей реализации loop. Вот почему это намного быстрее, чем реализация C. Вы на самом деле ничего не вычисляете.

Я не уверен, почему именно MIT Scheme так медленна для этого. Просто отсчет от 100 миллионов кажется молниеносным, как в Racket.

Чтобы фактически вычислить gcd с избыточностью, выбросить результат и измерить время, реализовать l oop следующим образом: 

(define (loop n fn)
  (if (= n 0) 0
      (begin
        (fn)
        (loop (- n 1) fn))))
...