Cosa è più veloce in Ruby, `arr + = [x]` o `arr << x`

Question

Intuitivamente, quest'ultimo dovrebbe essere più veloce del precedente. Tuttavia, sono rimasto molto sorpreso quando ho visto i risultati dei benchmark:

require 'benchmark/ips' 

    b = (0..20).to_a; 
    y = 21; 
    Benchmark.ips do |x| 
    x.report('<<') { a = b.dup; a << y } 
    x.report('+=') { a = b.dup; a += [y] } 
    x.report('push') { a = b.dup; a.push(y) } 
    x.report('[]=') { a = b.dup; a[a.size]=y } 
    x.compare! 
    end 

Il risultato è:

Calculating ------------------------------------- 
        << 24.978k i/100ms 
        += 30.389k i/100ms 
       push 24.858k i/100ms 
       []= 22.306k i/100ms 
------------------------------------------------- 
        << 493.125k (± 3.2%) i/s -  2.473M 
        += 599.830k (± 2.3%) i/s -  3.009M 
       push 476.374k (± 3.3%) i/s -  2.386M 
       []= 470.263k (± 3.8%) i/s -  2.364M 

Comparison: 
        +=: 599830.3 i/s 
        <<: 493125.2 i/s - 1.22x slower 
       push: 476374.0 i/s - 1.26x slower 
       []=: 470262.8 i/s - 1.28x slower 

Tuttavia, quando un mio collega ha creato in modo indipendente il proprio punto di riferimento, il risultato è stato tutto il contrario:

Benchmark.ips do |x| 
    x.report('push') {@a = (0..20).to_a; @a.push(21)} 
    x.report('<<') {@b = (0..20).to_a; @b << 21} 
    x.report('+=') {@c = (0..20).to_a; @c += [21]} 
    x.compare! 
end 

Risultato:

Calculating ------------------------------------- 
       push 17.623k i/100ms 
        << 18.926k i/100ms 
        += 16.079k i/100ms 
------------------------------------------------- 
       push 281.476k (± 4.2%) i/s -  1.410M 
        << 288.341k (± 3.6%) i/s -  1.457M 
        += 219.774k (± 8.3%) i/s -  1.093M 

Comparison: 
        <<: 288341.4 i/s 
       push: 281476.3 i/s - 1.02x slower 
        +=: 219774.1 i/s - 1.31x slower 

Abbiamo anche incrociato i nostri benchmark e su entrambe le nostre macchine il suo benchmark ha mostrato che += è notevolmente più lento di <<, e il mio ha mostrato il contrario.

Perché è quello?

UPD: la mia versione Ruby è Ruby 2.2.3p173 (2015-08-18 revisione 51636) [x86_64-darwin14]; il mio collega è 2.2.2 (non so tutti i dettagli, aggiornerà il post domani).

UPD2: ruby ​​2.2.2p95 (2015-04-13 revisione 50295) [x86_64-darwin12.0] versione Ruby del mio compagno di squadra.

Answer 1

Credo che questo dipenda dal modo in cui l'MRI alloca gli array (tutta questa risposta è molto specifica per la risonanza magnetica). Ruby si sforza davvero di essere efficiente con gli array: i piccoli array (< = 3 elementi) vengono inseriti direttamente nella struttura RARRAY, ad esempio.

Un'altra cosa è che se si prende un array e si inizia ad accodare i valori uno alla volta, ruby ​​non fa crescere il buffer un elemento alla volta, lo fa in blocchi: questo è più efficiente, a scapito di una piccola quantità di memoria.

Uno strumento per vedere tutto questo sta usando memsize_of:

ObjectSpace.memspace_of([]) #=> 40 (on 64 bit platforms 
ObjectSpace.memspace_of([1,2]) #=> 40 (on 64 bit platforms 
ObjectSpace.memsize_of([1,2,3,4]) #=> 72 
ObjectSpace.memsize_of([]<<1<<2<<3<<4) #=> 200 

Nei primi 2 casi, la matrice è confezionato all'interno della struttura RARRAY quindi la dimensione della memoria è solo la dimensione di base di qualsiasi oggetto (40 byte). Nel terzo caso il rubino ha dovuto allocare un array per 4 valori (8 byte ciascuno) quindi la dimensione è 40 + 32 = 72. Nell'ultimo caso il rubino ha aumentato lo spazio di archiviazione a 20 elementi

Questo è rilevante per il secondo caso . Il blocco all'interno del benchmark ha una matrice appena creata che ha ancora una certa capacità di riserva:

ObjectSpace.memsize_of((0..20).to_a) #=> 336, enough for nearly 40 elements. 

<< può scrivere solo oggetto allo slot appropriato, mentre += deve assegnare un nuovo array (sia l'oggetto e il suo buffer) e copiare tutti i dati.

Se faccio

a = [1,2,3,4,5] 
b = a.dup 
ObjectSpace.memsize_of(b) #=> 40 

Qui b parti suo buffer con a, così viene segnalato come non usando la memoria al di là della dimensione dell'oggetto di base. Nel punto in cui viene scritto b, ruby ​​dovrà copiare i dati (copia su scrittura): nel primo benchmark ENTRAMBI+= e << stanno attualmente allocando un nuovo buffer di dimensioni sufficienti e copiando tutti i dati.

Qui è dove ottengo le mie mani: questo spiegherebbe completamente le cose se << e += sono eseguite in modo identico, ma non è quello che sta succedendo. La mia lettura delle cose è che + è più semplice. Tutto quello che deve fare, indipendentemente da cosa allocare un buffer, e memcpy alcuni dati da 2 posizioni - questo è veloce.

<< d'altra parte sta mutando l'array in modo che stia pagando il sovraccarico di copia su scrittura: sta facendo un lavoro extra confrontare con +=. Ad esempio, ruby ​​deve tenere traccia di chi sta condividendo i buffer in modo che la raccolta dei dati obsoleti dell'array originale sia possibile quando nessuno la condivide più.

Un punto di riferimento che va in qualche modo a convincermi che questa interpretazione è corretta è la seguente:

require 'benchmark/ips' 
b = (0..20).to_a.dup 
y = 21 
Benchmark.ips do |x| 
    x.report('<<') { a = b.dup; a << y } 
    x.report('+=') { a = b.dup; a += [y] } 

    x.report('<<2') { a = b.dup; a << y; a<< y} 
    x.report('+=2') { a = b.dup; a += [y]; a += [y] } 
end 

Questo è fondamentalmente lo stesso punto di riferimento come l'originale, ma ora aggiungendo 2 elementi.Per << la copia sul sovraccarico di scrittura verrà eseguita solo la prima volta. I risultati che ottengo sono

   <<  1.325M (± 7.6%) i/s -  6.639M 
       +=  1.742M (± 9.5%) i/s -  8.677M 
      <<2  1.230M (±10.3%) i/s -  6.079M 
      +=2  1.140M (±10.8%) i/s -  5.656M 

Quindi, l'aggiunta all'array è di nuovo in alto se lo si fa due volte.

Answer 2

A mio parere, per semplificare il confronto tra vari operatori, dovremmo rimuovere il codice non necessario e mantenere il test semplice.

require 'benchmark/ips' 

y = 10 
Benchmark.ips do |x| 
    x.report('<<') { a = [0,1,2,3,4,5,6,7,8,9]; a << y } 
    x.report('+=') { a = [0,1,2,3,4,5,6,7,8,9]; a += [y] } 
    x.report('push') { a = [0,1,2,3,4,5,6,7,8,9]; a.push(y) } 
    x.report('[]=') { a = [0,1,2,3,4,5,6,7,8,9]; a[a.size]=y } 
    x.compare! 
end 

Il risultato del codice sopra riportato è in linea con il secondo snippet di codice condiviso nella domanda.

Calculating ------------------------------------- 
        << 101.735k i/100ms 
        += 104.804k i/100ms 
       push 92.863k i/100ms 
       []= 99.604k i/100ms 
------------------------------------------------- 
        <<  2.134M (± 3.3%) i/s -  10.682M 
        +=  1.786M (±13.2%) i/s -  8.804M 
       push  1.930M (±16.1%) i/s -  9.472M 
       []=  1.948M (± 7.9%) i/s -  9.761M 

Comparison: 
        <<: 2134005.4 i/s 
       []=: 1948256.8 i/s - 1.10x slower 
       push: 1930165.3 i/s - 1.11x slower 
        +=: 1785808.5 i/s - 1.19x slower 

[Finished in 28.3s] 

Perché << è più veloce di +=?

Array#<< è il più veloce dei quattro modi di aggiungere un elemento all'array perché fa proprio questo: aggiunge un elemento all'array. Al contrario, Array#+ aggiunge un elemento ma restituisce una nuova copia dell'array - la creazione di una nuova copia di array lo rende più lento. (Si può usare toogle code opzione nella documentazione per capire il lavoro supplementare svolto da alcuni metodi)

Banco marcatura con dup

Se usiamo qui di seguito il codice per la marcatura panchina,

require 'benchmark/ips' 

y = 10 
Benchmark.ips do |x| 
    x.report('<<') { a = [0,1,2,3,4,5,6,7,8,9].dup; a << y } 
    x.report('+=') { a = [0,1,2,3,4,5,6,7,8,9].dup; a += [y] } 
    x.report('push') { a = [0,1,2,3,4,5,6,7,8,9].dup; a.push(y) } 
    x.report('[]=') { a = [0,1,2,3,4,5,6,7,8,9].dup; a[a.size]=y } 
    x.compare! 
end 

Noi vedere sotto i risultati:

Calculating ------------------------------------- 
        << 65.225k i/100ms 
        += 76.106k i/100ms 
       push 64.864k i/100ms 
       []= 63.582k i/100ms 
------------------------------------------------- 
        <<  1.221M (±14.3%) i/s -  6.001M 
        +=  1.291M (±13.1%) i/s -  6.393M 
       push  1.164M (±14.1%) i/s -  5.773M 
       []=  1.168M (±14.5%) i/s -  5.722M 

Comparison: 
        +=: 1290970.6 i/s 
        <<: 1221029.0 i/s - 1.06x slower 
       []=: 1168219.3 i/s - 1.11x slower 
       push: 1163965.9 i/s - 1.11x slower 

[Finished in 28.3s] 

Se guardiamo attentamente tra due risultati, vediamo solo una differenza. La voce += è diventata la prima, mentre l'ordine di riposo dei metodi è rimasto lo stesso con il risultato originale.

Perché i risultati ruotano quando viene utilizzato lo dup?

Questa è la mia congettura selvaggia, sto indovinando che Ruby interprete ottimizzato il codice e non ha creato un nuovo array come parte di += come si sapeva che si sta lavorando su una copia appena creata di array dup