Rails on the road

Oggi su ruby-talk, ho letto un thread chiamato Per elevate prestazioni, programma in C. Mi piacerebbe presentare una risposta a quella tesi. Lasciatemi spiegare.

Tutto è iniziato con una email a lavoro. Qualcuno stava esaminando alcuni programmi per il calcolo dei numeri primi nei vari linguaggi (C, Java, C#, Perl e Python). Tutti utilizzavano lo stesso (terribile) algoritmo e avevano il solo scopo di mostrare quanto fossero performanti i linguaggi. Dato che sono l’evangelista Ruby del posto, mi è stato chiesto di scrivere una versione in Ruby. Questo è il programma (attenzione, l’algoritmo utilizzato è terribile):

    1 #!/usr/bin/ruby
    2 
    3 for num in 1..10_000 do
    4   is_prime = 1
    5   for x in 2..(num - 1) do
    6     if (num % x == 0) 
    7       is_prime = x
    8       break
    9     end
   10   end
   11   if is_prime == 1
   12     puts "#{num} is a prime number"
   13   else
   14     puts "#{num} equals #{is_prime} * #{num/is_prime}"
   15   end
   16 end

Quanto è veloce l’algoritmo? time ci dice:

    1 $ time ./primes.rb > /dev/null
    2 
    3 real    0m2.905s
    4 user    0m2.716s
    5 sys     0m0.004s
    6 $

Certamente, niente di particolare, ma non troppo lontano dalla versione in Perl o quella in Python. Volendo migliorarlo, e non volendo modificare l’algoritmo (vogliamo comparare mele con altre mele, non mele con arance). La cosa da fare è trovare il collo o i colli di bottiglia e riscriverli in C. Il primo passo è quello di utilizzare il profiler di Ruby e vedere quello che dice (in ogni caso riducendo il valore della variabile num a 100 in modo da completare il processo in tempo utile … il profiler è lento).

    1 $ ruby -rprofile primes.rb > /dev/null
    2   %   cumulative   self              self     total
    3  time   seconds   seconds    calls  ms/call  ms/call  name
    4  63.64     0.14      0.14      101     1.39     3.56  Range#each
    5  13.64     0.17      0.03     1133     0.03     0.03  Fixnum#%
    6   9.09     0.19      0.02     1233     0.02     0.02  Fixnum#==
    7   4.55     0.20      0.01      100     0.10     0.20  Kernel.puts
    8   4.55     0.21      0.01      200     0.05     0.05  IO#write
    9   4.55     0.22      0.01      248     0.04     0.04  Fixnum#to_s
   10   0.00     0.22      0.00       74     0.00     0.00  Fixnum#/
   11   0.00     0.22      0.00      100     0.00     0.00  Fixnum#-
   12   0.00     0.22      0.00        1     0.00   220.00  #toplevel
   13 $

Questo significa che la maggior parte del tempo è impiegato nel ciclo each (diciamo che il tempo è impiegato nel blocco di istruzioni passato all’each). Vengono utilizzati 1.39 msec per chiamata, comparato a .0X msec per qualsiasi altra cosa. Cosa succederebbe se riscrivessi solo questo blocco?

Introduciamo RubyInline (Uno stupendo strumento scritto da zenspider e Eric Hodel). Non sono un esperto di C, ma questo passaggio è molto facile da implementare. Il nuovo codice è:

    1 #!/usr/bin/ruby
    2 
    3 require "rubygems"
    4 require "inline"
    5 
    6 class Primes
    7   inline do |builder|
    8     builder.c '
    9     int prime(int num) {
   10       int x; 
   11       for (x = 2; x < (num - 1) ; x++) {
   12         if (num == 2) {
   13           return 1;
   14         }
   15         if (num % x == 0) {
   16           return x;
   17         }
   18       }
   19       return 1;
   20     }'
   21   end
   22 end
   23 
   24 p = Primes.new
   25 
   26 for num in 2..10_000 do
   27   is_prime = p.prime(num)
   28   if is_prime == 1
   29     puts "#{num} is a prime number"
   30   else
   31     puts "#{num} equals #{is_prime} * #{num/is_prime}"
   32   end
   33 end

Non è troppo orribile. Almeno posso vedere cosa sta succedendo. Il ciclo principale aiuta molto (specialmente se questo è parte di un programma più grande). Quanta differenza rispetto a prima? time ci dice:

    1 $ time ./cprimes.rb > /dev/null
    2 
    3 real    0m0.328s
    4 user    0m0.288s
    5 sys     0m0.020s

Abbiamo ottenuto un miglioramento di un ordine di grandezza. Non male. Qual è la lezione che abbiamo imparato? Ottimizza quello di cui hai bisogno (e solo quello) cercandolo con profile (può essere lento, ma è sicuramente indispensabile) e utilizza i giusti strumenti (riscrivendo un po’ di codice con RubyInline è il modo migliore rispetto a scrivere l’intera applicazione in C).

The Rubylation Network