Re: Curiosité

Le 19/06/2024 à 13:05, efji a écrit :

Le 19/06/2024 à 09:45, Dominique a écrit :
 

Cela dit, la rapidité de calcul avec Python est telle qu'un grand nombre d'itérations donne un résulta presque instantané. L'optimisation du code devient accessoire 🤔
>

 :)
Python est le langage le moins rapide qui existe, mais en effet pour ce genre de chose ça ne se voit pas.
 

Un petit essai que j'avais fait pour comparer les temps d'exécution  de quelques langages, en calculant un grand nombre de factorielles.  C'est en anglais, mais Google peut le traduire.  le résultat est que python est au moins 100 fois plus lent
que ce que produit lisp sbcl ou bien sûr, C, en fait sbcl et C donnent une vitesse équivalente.
A small comparison of execution speed of several languages on the same
job, computing a bunch of factorials, and the same machine.  The same
computations are done in each case, but sometimes the factorial is
programmed in tail recursive way. The last factorial is printed to
check that all programs give the same answer. This test is obviously
not a benchmark of general use, but it exercises the arithmetic and
logical units of the processor. There are no floating point
computations, and i think the computation is hold in the cache, so
memory accesses are not dominant like in large floating computations.
Here are the programs:
Scheme: tested with Racket and Chicken
#lang racket         <---- remove that for chicken
(define (myfact n)
   (cond ((< n 0) 0)
((= n 1) 1)
(else (* n (myfact (- n 1))))))
(time
  (let ((q 0))
    (do ((i 1 (+ 1 i)))
        ((> i 20000000)(print q))
      (set! q (myfact (floor (/ i 1000000)))))))
The tail recursive program:
#lang racket
(define (myfact n [acc 1])   <--- This is racket syntax for optional.
   (if (<= n 1)
acc
(myfact (- n 1) (* acc n))))
(time
  (let ((q 0))
    (do ((i 1 (+ 1 i)))
        ((> i 20000000)(print q))
      (set! q (myfact (floor (/ i 1000000)))))))
Common lisp: tested with sbcl gcl and clisp. Programmed with
tail recursion and maximal optimization
(defun myfact (n &optional (acc 1))
(declare ( fixnum n acc)
(optimize (speed 3) (safety 0)))
(if (<= n 1)
     acc
     (myfact (- n 1)  (* acc n))))
(defun myloop()
(declare  (optimize speed))
  (let ((q 0))
    (do ((i 1 (+ 1 i))) ((> i 20000000)(print q))
      (setq q (myfact (floor i 1000000))))))
(time (myloop))
Python: with cpython3
import time
import math
def myfact(n):
if n < 0 :
return 0
elif n == 1 :
return 1
else:
return n * myfact(n-1)
start = time.time()
q = 0
for i in range(20000000):
q = myfact(math.floor(i/1000000))
print(q)
end = time.time()
print(end - start)
and finally C compiled with gcc and clang.
#include<stdio.h>
#include<sys/time.h>
#include<math.h>
long long myfact (int n) {
if (n<0) return 0;
else if (n==0) return 1;
else return n * myfact(n-1);
}
int main() {
long i;
long long q;
struct timeval start;
struct timeval end;
double(diff);
gettimeofday(&start,0);
q=0;
for (i=0;i <= 20000000;i++) {
q = myfact(floor(i/1000000));
}
printf("%lli\n",q);
gettimeofday(&end,0);
diff=(double)(end.tv_sec -start.tv_sec)+
(double)(end.tv_usec - start.tv_usec) / 1000000;
printf("%f\n",diff);
}
Here are the timings. The slowest is uncompiled clisp which takes 207s
and uncompiled gcl which takes 138s.
Then comes python3 at 61s.
After that we have a group around 30s. After compilation clisp takes 33s.
Chicken (compiled by csc -O3 -o fact fact.scm) takes 27s.  The racket
system has, i think, a JIT compiler, and is faster. It runs in 13s, and
surprisingly the tail recursive computation takes the same time. Which
means that the compiler is quite good at optimizing the code.
Using a compiled version of fact.lisp with gcl takes 6s. Then are the fast systems.
Since sbcl compiles on the fly it is fast, it takes 0.509s. By curiosity, for the non
tail recursive version of myfact:
(defun myfact(n) (if (<= n 1) 1 (* n (myfact (- n 1)))))
and without any declaration sbcl takes 4.281 s while in the same situation
gcl using compilation takes 4.090 s  So both are quite equivalent, but sbcl takes the advantage
when using its elaborate optimizer.
Finally directly using a C program, far more boilerplate, non obvious decalarations, etc.
with gcc -O1  gives 1.162638 s while gcc -03 gives 0.256238 s. There is no appreciable
difference between clang -O1 and clang -O3 both run in 0.000220 s which seems
incredibly fast.   In any case we see that sbcl has basically equivalent performance with
the C program compiled with gcc. After having looked at the  assembly produced by gcc and
clang, it appears that the reason of the clang performance is that it has optimized away
the whole for (i=0;i <= 20000000;i++) {q = myfact(floor(i/1000000));} and computed only
the last factorial! Changing fact.c to avoid that (computing the sum of the q) one gets
0.757577 s for clang -O3 and 0.263702 s for gcc -O3, that is sbcl is as fast as clang
and gcc -O3 is much better as i had expected.
--
Michel Talon