Sommario
Introduzione
Il metodo isPrime di default soffre di un grave problema che ne penalizza fortemente le prestazioni:
Nel ciclo for iteriamo da 2 a lim cercando i possibili divisori del numero num fornito come argomento ma ci accorgiamo subito che se il 2 non è un divisore allora è perfettamente inutile tentare il 4 come divisore dal momento che 4 è un multiplo di 2. Lo stesso dicasi per il 6 e anche il 8, e così via. Analogo discorso vale anche per il numero 3 come divisore; se esso non è un divisore di num allora è inutile provare anche: 6, 9, 12, .... e tutti i multipli di 3.
Il crivello di Eratostene è un algoritmo antico sviluppato da Eratostene di Cirene, matematico, filosofo e astronomo greco vissuto tra il terzo ed il secondo secolo a.C. ed è usato ancora oggi per estrarre la lista dei numeri primi compresi tra due estremi. Rispetto al algoritmo "per tentativi di divisione" questo è di gran lunga più veloce: ma quanto?
Brevemente, questo algoritmo si basa sul principio che per estrarre tutti i numeri primi da 2 a n si crea una array di n elementi e si itera su tutti i numeri i da 2 a sqrt(n) cancellando dalla array tutti gli elementi che sono multipli di i. Gli elementi della array "non cancellati" sono numeri primi. L'algoritmo assomiglia quindi ad un setaccio, come quello usato dai cercatori d'oro, dal quale tutti i multipli dei numeri primi cadono dal setaccio ed in esso rimangono solo i numeri primi.
Per questo motivo il crivello di Eratostene è conosciuto anche col nome di setaccio di Eratostene.
L'algoritmo
Per esempio, per trovare i numeri primi da 2 a 20 allochiamo una array di 19 elementi (da 2 a 20, compresi):
1 2 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 | | | | | | | | | | | | | | | | | | | |
e cancelliamo i multipli di 2: 4,6,8,0,12,14,16,18,20
1 2 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 | | |x| |x| |x| |x| |x| |x| |x| |x| |x|
poi i multipli di 3: 6,9,12,15,18
1 2 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 | | |x| |x| |x|x|x| |x| |x|x|x| |x| |x|
E' dimostrato che è sufficente cancellare i multipli da 2 fino a sqrt(n) e poichè:
sqrt(20) = 4.472
l'ultimo numero di cui cancellare i multipli è il 4. Poichè questo numero è già stato cancellato (perchè multiplo di 2), non è necessario cancellare i suoi multipli dal momento che sono già stati cancellati quali multipli del 2. L'algoritmo può dunque fermarsi e, come potete osservare, nella array ci sono elementi "non cancellati": 2,3,5,7,11,13,17 e 19. Questi sono i numeri primi compresi tra da 2 a 20, inclusi.
Nonstante la sua semplicità, il crivello migliora le performance di conteggio ed estrazione dei numeri primi di un fattore di oltre cento volte; soffre però di un importante limite dovuto al enorme consumo di memoria. Cercheremo di minimizzare il consumo di RAM con alcuni accorgimenti.
Le condizioni di overflow
Oltre alla già citata condizione di overflow vista in La condizione di Overflow, dobbiamo introdurne una nuova; dal momento che dobbiamo allocare una array di n elementi e, come sappiamo, il numero massimo di elementi di una array è Integer.MAX_VALUE, ne consegue che, utilizzando questo algoritmo, l'argomento end che rappresenta il limite superiore dell'intervallo da cui estrarre / contare i numeri primi non può essere maggiore di Integer.MAX_VALUE.
Diciamo che questo è il limite superiore massimo del setaccio e scriveremo un metodo apposito per questo limite:
La classe Crivello.java
La classe Crivello.java è la prima implementazione del Crivello di Eratostene. Essa esegue la estrazione e/o il conteggio dei numeri primi in due fasi distinte:
- la prima fase consiste nel allocare ed elaborare il setaccio cancellando tutti i numtipli dei numeri primi partendo da
2fino asqrt(n)dovenè il limite del setaccio - la seconda fase consiste nel estrarre o contare i numeri "non cancellati" dal setaccio: questi sono numeri primi
La prima fase viene eseguita dal metodo protetto setaccia il quale accetta quale argomento il limite superiore del setaccio; lo stesso metodo restituisce il suo limite del setaccio: il limite restituito è, ovviamente, uguale a quello passato come argomento ma potrebbe anche essere superiore (vedi Crivello2: il metodo setaccia).
La seconda fase viene eseguita dal metodo protetto extract (per la estrazione dei numeri primi) e da count (per il conteggio dei numeri primi): il primo restituisce una ArrayList mentre il secondo un long.
Costruttore e membri dati
Non c'è molto da dire a proposito del costruttore e dei membri dati. Essi sono facili da leggere e, comunque, ampiamente commentati nel sorgente. Le due costanti mnemoniche servono ad evitare di allocare un setaccio ed una ArrayList con dimensioni insignificanti.
I due membri dati setaccio e limit vanno di pari passo: il setaccio è la array di elementi "cancellati / non cancellati" mentre limit è la dimensione del setaccio espressa come "quanti elementi cancellati / non cancellati" può contenere.
Benchè appare chiaro che, in questo contesto, il limite del setaccio è anche la sua dimensione, in altri contesti ciò non è vero; nelle prossime sezioni il lettore capirà il perchè.
Perchè si è scelto il tipo di dato byte per la array del setaccio? E non, per esempio, int?
Ebbene, la scelta del tipo di dato deve essere quello che garantisce la piena capienza del valore possibile e il massimo risparmio di memoria. Non dimentichiamo che, potenzialmente, l'argomento end può essere un valore piuttosto grande, circa di 9,2x1018 e che per elaborare il crivello dobbiamo allocare una array di dimensioni pari a end.
Benchè assolutamente impossibile dato il limite fisico delle array in Java che è di Integer.MAX_VALUE (2,1x109), anche questo limite è piuttosto alto e, calcolando che un int è formato da 4 bytes, una array di int della dimensione massima arriverebbe ad allocare 8 gigabytes di memoria, probabilmente superando la dimensione della memoria gestibile dalla JVM.
Pertanto, si è scelto di usare il tipo di dato più piccolo possibile che è il byte in modo da minimizzare al massimo il consumo di RAM considerato che i valori da inserire in ogni elemento della array sono solo due:
- ZERO: elemento non cancellato
- UNO: elemento cancellato
Ma se i valori da inserire negli elementi della array sono solo due perchè non usare il tipo di dato boolean che ha esattamente due soli stati: true e false?
Ebbene, benchè il tipo di dato boolean è di soli due stati esso viene comunque allocato come un byte in memoria almeno nella maggior parte delle implementazioni Java; ne consegue che non abbiamo assolutamente la certezza che quella particolare implementazione Java utilizzi un tipo di dato di dimensione inferiore al byte e, pertanto, troveremo soluzioni migliori per risparmiare memoria; soluzioni che daranno la certezza matematica di utilizzare un solo bit per marcare l'elemento della array.
Il metodo getPrimesCount
Questo metodo è davvero semplice da leggere:
Come prima operazione si verifica che i due estremi dell'intervallo da elaborare siano positivi e che s (=start) sia minore o uguale ad e (=end).
Successivamente, se il setaccio non è stato elaborato o se il suo limite è inferiore a quello necessario ad questa elaborazione, si richiama il metodo setaccia che alloca ed elabora il setaccio.
Questa operazione consente di risparmiare tempo prezioso: supponiamo di usare la classe Crivello per ottenere il conteggio dei numeri primi da 100.000 a 1.0000.000 e che poi vogliamo ottenere il conteggio dei numeri primi da 200.000 a 900.000. Appare chiaro che per la seconda elaborazione NON è assolutamente necessario rielaborare il setaccio: è sufficente eseguire il conteggio e quindi richiamare il metodo protetto count.
Il metodo getPrimesList
Il metodo getPrimesList segue lo stesso schema del metodo visto in precedenza con l'unica differenza che viene allocata anche la lista dei numeri primi da ritornare e che il metodo protetto da richiamare non è count ma extract:
Il metodo setaccia
Passiamo ora a commentare il metodo setaccia che esegue la elaborazione vera e propria del crivello di Eratostene:
Il metodo verifica che il limite superiore del setaccio non sia maggiore del limite massimo ammissibile restituito dal metodo getMaxLimit: di questo abbiamo già discusso in Le condizioni di overflow. Successivamente, determiniamo la dimensione del setaccio, che non può essere minore del minimo stabilito dalla costante mnemonica, e allochiamo la quantità necessaria di bytes che è pari al limite stesso.
Il metodo prosegue elaborando il setaccio vero e proprio:
Per ogni multiplo di i l'elemento della array setaccio corrispondente viene impostato a UNO che è il codice che indica che quel elemento è stato cancellato.
Avrete notato che il primo elemento del setaccio (indice ZERO) corrisponde al numero naturale 2: per questo gli indici vengono diminuiti di 2 unità nella cancellazione dei multipli; in effetti è inutile partire dal numero ZERO o UNO dal momento che nessuno di essi è considerato un numero primo.
I metodi extract e count
Questi due metodi protetti sono quasi identici:
Dopo aver ASSERTato che il setaccio è allocato e che l'argomento end sia minore o uguale al limite del setaccio, il metodo count itera su tutti i numeri i da start a end e, se il numero i NON è stato cancellato dal setaccio incrementa il contatore di una unità; nel metodo getPrimesList, invece, aggiunge il numero alla lista dei numeri primi.
Il cuore di questa seconda fase è, quindi, il metodo isCancelled.
Il metodo isCancelled
Questo metodo verifica se il numero fornito come argomento è stato cancellato dal setaccio confrontando l'elemento ad indice num-2 con il valore 1. Se il valore è uguale a UNO, il numero è stato cancellato e quindi ritorna TRUE:
Il numero da verificare si trova ad indice num-2 perchè, come abbiamo scritto poc'anzi, il primo elemento della array del setaccio rappresenta il numero naturale 2.
Notate anche il cast esplicito dell'indice della array rappresentato dal numero num-2 in un int, dal momento che gli indici degli array non possono essere più grandi di un int.
Il metodo isPrime
Questo metodo ha già una implementazione di default nella interfaccia ListPrimes ma si tratta di un algoritmo poco efficente (vedi ListPrimes.isPrime). In questa classe che implementa il crivello il metodo isPrime viene sovrascritto poichè è possibile avere un netto miglioramento delle performances: se il numero del quale si deve verificare la primalità è minore del limite del setaccio già elaborato in precedenza, allora è sufficente verificare se l'elemento della array setaccio corrispondente al numero è stato cancellato oppure no: se non è stato cancellato, allora è primo.
Tuttavia, se il numero fornito come argomento è maggiore del limite del setaccio elaborato, allora non abbiamo altra scelta che richiamare l'inefficente metodo di default della interfaccia per la verifica. Notate il costrutto da usare per richiamare un metodo di default della interfaccia da una classe che la implementa:
Ci sarebbe anche una seconda possibilità: allocare un nuovo setaccio ma questo non lo farò, preferisco insegnarvi come si richiama un metodo di default di una interfaccia.
Performances del crivello
Proviamo le performances del crivello di Eratostene in confronto al vecchio ed inefficente algoritmo della "divisione per tentativi":
>javac javatutor\primes\crivello\Crivello.java >javac javatutor\primes\Performance.java
Contiamo i numeri primi minori/uguali a dieci-milioni
>java -ea javatutor.primes.Performance DL 10000000 Using implementation: DivisionLoop Time elapsed: 13,8 >java -ea javatutor.primes.Performance C1 10000000 Using implementation: Crivello1 Time elapsed: 0,1
Come peraltro ampliamente prevedibile, il Crivello ha surclassato, in velocità, l'algoritmo della "divisione per tentativi" di un fattore di 138 volte!
Miglioriamo il crivello
Il problema maggiore del crivello di eratostene è che consuma una quantità impressionante di memoria necessaria ad allocare il setaccio cioè la array che cancella i multipli dei numeri. Possiamo migliorare nettamente il consumo di memoria del crivello rendendoci conto che per segnare un elemento del setaccio come cancellato / non cancellato è sufficiente un solo bit (0=non cancellato, 1=cancellato) anzichè un intero byte. Poichè in un byte ci sono 8 bits, il risparmio di memoria è di otto volte: un grande risultato.
Possiamo anche notare che alcuni metodi della classe Crivello non devono nemmeno essere modificati; vanno benissimo così come sono:
getPrimesListegetPrimesCountnon devono essere modificati poichè si basano sui metodiextract,countesetacciaper elaborare il setaccioisPrime, che verifica se un numero è primo, non deve essere modificato perchè si basa sul metodoisCancelledper determinare se il numero è stato cancellato o meno dal setacciogetLimitche restituisce il limite superiore del setaccio attuale; questo limite è memorizzato nel membro dati e restituito dalsetacciaextractecountnon devono essere modificati poichè si basano sul metodoisCancelledper determinare se il numero è stato cancellato o meno
I metodi che dobbiamo modificare perchè la elaborazione di un singolo bit è diversa che quella di un intero byte sono i seguenti:
getMaxLimitche restituisce il limite massimo teorico del setaccio; in questa implementazione il limite è pari a Integer.MAX_VALUE moltiplicato per ottosetacciache esegue il setacciamento dei multipli dei numeri; ora questo metodo deve indirizzare il singolo bit per cancellare un elemento dalla arrayisCancelledche verifica se il numero è stato cancellato dal setaccio; anche questo metodo dovrà indirizzare il singolo bit nella array di bytes che costituisce il setaccio.
Poichè questa seconda versione del crivello condivide molti dei metodi già scritti, non dobbiamo fare altro che derivare una classe specializzata da Crivello e sovrasciverne i metodi suesposti. Chiameremo questa nuova classe: Crivello2
Crivello2: il metodo setaccia
Per marcare un elemento della array di bytes come "cancellato" abbiamo usato il costrutto:
nel quale l'intero byte, quindi l'intero elemento della array, veniva impostato a UNO ma, come accennato in precedenza, per marcare un elemento come cancellato o non_cancellato basterebbe un solo bit: ZERO e UNO. Tuttavia, il tipo di dato boolean, che sembrerebbe il candidato ideale, non lo è affatto poichè la quantità di memoria allocata per esso in molte implementazioni Java è il byte e non il singolo bit. Uno dei motivi di questa scelta sta nella architettura hardware dei calcolatori poichè tutte le istruzioni del microprocessore possono indirizzare la singola cella di memoria (che è il byte) ma non il singolo bit all'interno di essa.
Questo però non significa che non sia possibile impostare/cancellare il singolo bit di un byte; significa solo che non possiamo usare l'operatore di assegnamento come siamo abituati a fare con le variabili, ma ci sono altre possibilità.
Per indirizzare i singoli bits di una qualsiasi variabile numerica si usano gli operatori di bitwise che sono stati descritti in Operatori di bitwise e che abbiamo già usato in precedenza (vedi I flags di disegno).
Prendiamo come esempio il primo byte del setaccio; essendo composto da otto bits, esso è in grado di marcare otto numeri naturali indirizzandone i singoli bits.
Per impostare a UNO (cancellato) il bit numero 4 (che corrisponde al numero naturale quattro) si usa l'operatore di bitwise OR in questo modo:
Quindi è possibile indirizzare tutti i singoli otto bits di un byte, le cui posizioni vanno numerate da 0 a 7, secondo la seguente tabella:
valore del bit ->128 64 32 16 8 4 2 1 posizione del bit -> 7 6 5 4 3 2 1 0
Avrete poi sicuramente notato che il valore del bit da usare nella OR per impostarlo altro non è che la potenza del 2 corrispondete alla sua posizione!
I numeri naturali rappresentati ora nel setaccio vengono indirizzati sul singolo bit e non più sul byte. Possiamo quindi ipotizzare che il setaccio non è più una array di elementi byte ma una array di elementi bit. Schematicamente, l'elemento bit ad indice 29 che rappresenta il numero naturale 29 viene indirizzato nel byte ad indice 3, bit ad indice 5:
1 2 3
numero naturale -> 01234567 89012345 67890123 45678901
^
byte ------------>| 0 | 1 | 2 | 3 |
Quindi, per impostare il 30-esimo elemento della array di bits (che corrisponde al numero naturale 29, devo ottenere due indici:
- l'indice del byte, che ottengo dividendo per otto l'indice dell'elemento
- l'indice del bit, che ottengo come resto della divisione precedente.
In codice, assumendo che num è il numero naturale da cancellare:
Il metodo getMaxLimit
Nella prima versione del crivello, il numero primo più grande (teoricamente) estraibile dal setaccio è pari a Integer.MAX_VALUE dal momento che non è possibile allocare una array di bytes, o meglio, di qualsiasi tipo di elemento, di dimensioni superiori a detto limite.
Assodato che anche in questa versione il limite massimo di bytes allocabili è sempre pari a Integer.MAX_VALUE abbiamo che, però, ognuno di questi bytes può rappresentare otto numeri naturali e quindi il limite massimo teorico del setaccio diventa Integer.MAX_VALUE moltiplicato per otto.
Perchè ho usato un costrutto così strano? Per quale motivo non ho usato il semplice:
Molto probabilmente avete già trovato da soli la risposta dal momento che abbiamo già affrontato la questione overflow almeno due volte.
Quando deve eseguire una operazione aritmetica, il compilatore deve assicurarsi che i tipi di dato da sommare, dividere o moltiplicare siano compatibili: gli interi con gli interi, i long con i long e così via.
Se le due variabili sono di tipo diverso il compilatore promuove la variabile con minore capacità eseguendo un cast implicito. Dopo che le due variabili sono diventate dello stesso tipo, il compilatore esegue la operazione e ritorna il risultato che è dello stesso tipo delle due variabili.
Analizzando la istruzione:
possiamo notare che una costante di tipo int viene moltiplicata con una altra costante di tipo int. Essendo le due costanti dello stesso tipo, il compilatore esegue la moltiplicazione tra due interi e restituisce in m un risultato di tipo int che viene poi convertito in un long.
Ma il risultato della moltiplicazione, che è pari a 17.179.869.176 è troppo grande per un tipo int e viene, pertanto, TRONCATO in -8. E questo sarebbe il valore della variabile m. Come possiamo risolvere? In due modi: separando le due assegnazioni oppure FORZANDO il compilatore a usare un tipo di dato con capienza maggiore nella moltiplicazione eseguendo un cast esplicito di almeno uno dei due argomenti:
il metodo isCancelled
Questo metodo è simile a quello già commentato in precedenza; unica differenza è il calcolo degli indici di byte e di bit che indirizzano l'elemento nella array del setaccio.
Il calcolo di questi due indici è già stato ampiamente commentato nella sezione precedente, a cui rimando:
in questa nuova versione del crivello abbiamo ottenuto un notevole risparmio di memoria ma il codice è più complesso; non solo, mentre nella prima versione l'indice dell'elemento nella array del setaccio era rappresentato dal numero stesso, in questa versione abbiamo dovuto calcolare due indici, introducendo due istruzioni aggiuntive.
Dobbiamo quindi aspettarci un peggioramento delle prestazioni rispetto alla prima implementazione del crivello? Beh, in teoria si ma ... ci aspettano delle sorprese!
Miglioriamo ulteriormente il crivello
Se analizziamo la distribuzione dei numeri primi nell'insieme dei numeri naturali, ci accorgiamo subito di una particolarità:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 ...
sono tutti numeri dispari. Il che è ovvio dal momento che tutti i numeri pari, escluso il 2, sono multipli del due e qundi non possono essere primi.
Possiamo quindi migliorare ulteriormente il crivello sia in termini di memoria consumata che in termini di prestazioni:
- non è necessario sprecare un bit del setaccio per tenere traccia della cancellazione dei numeri pari; essi saranno sicuramente cancellati ad eccezione del numero 2
- non è necessario calcolare i multipli dei numeri pari poichè qualsiasi numero moltiplicato per un numero pari dà un risultato pari;
Il metodo getMaxLimit
Il limite teorico di questa versione è dato dal limite massimo di bytes allocabili per il setaccio che è pari a Integer.MAX_VALUE moltiplicato per sedici (otto numeri dispari + otto numeri pari per ogni byte) meno uno, che equivale a più di 34 miliardi. Tuttavia, come spiegato in Le condizioni di overflow, questo è il limite massimo ammissibile per la applicazione la quale non potrà mai fornire un numero primo maggiore di questo limite.
Ma ci sono limiti più stringenti primo fra tutti la memoria disponibile per allocare sia il setaccio che la lista di numeri primi.
Il metodo setaccia
Il metodo setaccia è molto simile a quelli già visti, ovviamente dal momento che implementa lo stesso algortimo. La differenza si nota nel ciclo for per il calcolo dei multipli da cancellare: il ciclo parte dal numero 3 e non dal 2 (i multipli di due sono sempre numeri pari) ed il passo del ciclo è 2 e non 1:
Il metodo extract
Il metodo che estrae i numeri dal setaccio è sempre un ciclo for che itera dal argomento start (il numero primo più piccolo della lista) al argomento end (il numero primo più grande della lista) e verifica se tutti i numeri compresi tra questi due argomenti sono stati cancellati o meno dal setaccio.
Il metodo è uguale a quello già visto nelle versioni precedenti ad eccezione di alcune particolarità:
- se
startè un numero pari (sicuramente non primo) lo aumenta di uno - se
endè un numero pari (sicuramente non primo) lo diminuisce di uno - il passo del ciclo
forè di 2 unità in modo che, partendo da un numero dispari, solo i numeri dispari vengono verificati
Un piccolo trucchetto
Se avete osservato attentamente i sorgenti della classe Crivello3 avrete notato alcuni costrutti diversi da quelli di Crivello2. Mi riferisco in particolare al metodo isCancelled ed alle due istruzioni che calcolano l'indice del byte del setaccio e l'indice del bit all'interno del byte:
Nella versione precedente (vedi il metodo isCancelled) le due istruzioni eseguivano la divisione per otto per calcolare l'indice del byte mentre l'indice del bit era il resto della divisione per otto (modulo 8). In questa nuova versione del crivello, invece, ho usato istruzioni diverse:
- per dividere per 16 (ora abbiamo 16 numeri per ogni byte) ho usato l'operatore di scorrimento verso destra di quattro posizioni
- per ottenere il resto della divisione per 16 ho usato l'operatore di bitwise
ANDcon operando15e, successivamente, un ulteriore scorrimento verso destra di una posizione
Perchè per dividere per sedici ho eseguito uno scorrimento verso destra di quattro posizioni? Beh, cosa fareste voi per dividere per mille? Semplice, basta scorrere il numero a destra di tre posizioni; per esempio dodicimila diviso mille:
|1|2|0|0|0| --> |0|0|0|1|2|
E perchè lo scorrimento è di tre posizioni? Perchè 1000 = 103. Quindi per dividere per qualsiasi numero che è una potenza del 10 basta scorrere il numero verso destra di tante posizioni quanto è il valore dell'esponente del dieci.
Poichè nel nostro programma num è espresso in binario possiamo applicare lo stesso principio ma tenendo conto che si parla di potenze del due e non del dieci. E poichè 16=24 abbiamo che per dividere per sedici basta scorrere verso destra il numero di quattro posizioni.
Lo stesso principio si applica alla operazione MODULO. Come fate in decimale a trovare il MODULO 100 di un numero (in altre parole il resto della divisione per 100? E' sufficente azzerare tutte le cifre oltre la terza cifra compresa, giusto? Ebbene, in binario si può usare l'operatore di bitwise AND per ottenere lo stesso risultato.
Ma che vantaggio ho ad usare simili sotterfugi? Beh, dobbiamo ammettere che anche per noi umani la divisione è una operazione difficile, che porta via parecchio tempo a meno che il divisore non sia una potenza del dieci: in questo caso è molto più veloce ma solo perchè operiamo uno scorrimento.
Lo stesso principio vale per i microprocessori: la divisione è una operazione che porta via molto più tempo, espresso in clock cycles (=cicli di clock), rispetto allo scorrimento. Al seguente link potete trovare la tabella dei cicli di clock necessari a completare una operazione in codice macchina per diversi processori, dal 8088 al Pentium (lo so, sono arcaici, ma il concetto non cambia).
Di seguito un breve estratto; nella tabella vengono riportati i cicli di clock necessari a completare la operazione tra registro ed operando immediato a 32 bits:
| Opcode | 8088 | 386 | 486 | Pentium | Note |
|---|---|---|---|---|---|
| DIV | 38 | 40 | 41 | Divisione senza segno | |
| IDIV | 43 | 43 | 46 | Divisione con segno | |
| AND | 4 | 2 | 1 | 1 | bitwise AND |
| ROR | 3 | 3 | 2 | 1 | ROtate Right |
Come potete osservare, la divisione è molto più lenta delle altre operazioni e poichè nel setaccio abbiamo bisogno di eseguirne migliaia (se non decine di migliaia) usare lo scorrimento anzichè la divisione può farci risparmiare una quantità di tempo apprezzabile.
Le performances del crivello
Nelle due sezioni successive vengono riepilogati i risultati del test di velocità dei vari algoritmi che abbiamo sviluppato. Ci sono due tabelle: la prima che riguarda il solo conteggio dei numeri primi mentre la seconda riguarda la loro estrazione e memorizzazione in una ArrayList.
I tempi sono stati ottenuti su una macchina Desktop All-In-One equipaggiata con un processore Intel Core i5-6500 e 16 GB di RAM DDR4; non proprio una lepre, in quanto a velocità!
Le performances nel conteggio
In questa tabella vengono riepilogati i risultati del test eseguito con l'argomento start impostato a 2 ed end impostato al limite indicato nella prima colonna; le sigle rappresentano: K=migliaia, M=milioni, G=miliardi. Nella seconda colonna è riportato il conteggio dei numeri primi ritornato dalla app mentre nelle restanti colonne viene riportato il tempo impiegato in secondi per eseguire la elaborazione.
| Limite | Count | DivisionLoop | Crivello | Crivello2 | Crivello3 |
|---|---|---|---|---|---|
| 100K | 9.592 | 0.0 | |||
| 1M | 78.498 | 0.6 | |||
| 5M | 348.513 | 5.2 | |||
| 10M | 664.579 | 13.6 | 0.1 | 0.1 | 0.0 |
| 40M | 2.433.654 | 0.4 | 0.3 | 0.1 | |
| 100M | 5.761.455 | 0.9 | 1.1 | 0.4 | |
| 200M | 11.078.937 | 1.9 | 2.3 | 0.9 | |
| 400M | 21.336.326 | 4.1 | 4.8 | 1.9 | |
| 1G | 50.847.534 | 10.6 | 12.9 | 5.3 | |
| 5G | 234.954.233 | Overflow | 70.5 | 29.5 | |
| 10G | 455.052.511 | 62.4 | |||
| 20G | 882.206.716 | Overflow | 132.5 | ||
| 40G | 1.711.955.433 | Overflow |
Come avrete sicuramente notato, la terza versione del crivello è molto veloce, in grado di contare tutti i numeri primi da 2 a un miliardo in poco più di cinque secondi; e questo su una macchina che, nel 2024, è considerata poco più che un entry-level.
Per un limite di 5 miliardi, invece, la prima versione del crivello termina il programma con una eccezione di overflow: questo perchè non è possibile allocare cinque miliardi di bytes nel setaccio. Il limite massimo è di poco più di due miliardi. Le altre due implementazioni hanno limiti di overflow molto più alti: il Crivello2 arriva a oltre 17 miliardi mentre Crivello3 a circa 34 miliardi (vedi Le condizioni di overflow).
Le performances nella estrazione
Le operazioni di massima sono uguali sia per conteggio dei numeri primi che per la loro estrazione e memorizzazione: se osserviamo il sorgente dei due metodi protetti extract e count ci rendiamo conto che la unica differenza stà nel blocco di codice seguente:
A prima vista non sembrano esserci molte differenze tra i due listati: si tratta pur sempre di una singola istruzione in linguaggio Java. Tuttavia, le differenze sono abissali in termini di tempo impiegato dalla macchina. La istruzione c++ si traduce in linguaggio macchina con una sola istruzione atomica: in linguaggio assembler è la INC (che possiede anche la controparte DEC). Questa singola istruzione viene eseguita da quasi tutti i microprocessori in un unico ciclo di clock.
Invece, la istruzione primes.add() è tutta una altra cosa: sono necessarie diverse decine di istruzione in codice macchina per eseguirla.
E' lecito aspettarsi tempi diversi nei test, tra il conteggio e la estrazione / memorizzazione dei numeri primi? Certo che si. Ecco un raffronto tra i due casi, utilizzando il Crivello3, il più veloce:
| Limite | Count | conteggio | estrazione |
|---|---|---|---|
| 200M | 11.078.937 | 0.9 | 1.2 |
| 400M | 21.336.326 | 1.9 | 2.6 |
| 1G | 50.847.534 | 5.3 | 7.0 |
C'è anche un altro aspetto da tenere in considerazione nella operazione di estrazione e memorizzazione della lista dei numeri primi.
La condizione di Overflow vale sia per il conteggio dei numeri primi che per la loro estrazione ma nel secondo caso si potrebbe avere un altro limite: quello della memoria dedicata alla JVM (il cosidetto Java heap di cui tratterò in dettaglio in Foreign Function and Memory). Se tentiamo la estrazione dei numeri primi da 2 a cinque-miliardi potremmo ottenere un errore di tipo OutOfMemoryError (memoria esaurita):
>java -ea javatutor.primes.Performance -e C3 5000000000 Test performances of ListPrimes implementations Starting number: 2 Ending number: 5000000000 Using implementation: Crivello3 OUT OF MEMORY ERROR Try to increase heap space usign -Xmx JRE option
Il problema, in questo caso, non è il setaccio in quanto esso viene allocato oppure no; l'errore di memoria esaurita avviene nella ArrayList che contiene l'elenco dei numeri primi; come accennato in Arrays e Collections, una ArrayList può crescere in dimensione mano a mano che gli elementi vengono aggiunti ad essa.
Ma se lo spazio in memoria si esaurisce, nessun elemento può essere aggiunto e si ottiene un errore di tipo OutOfMemoryError.
L'errore si può evitare riducendo l'intervallo di elaborazione per esempio potremmo non essere interessati a tutti i numeri primi da 2 a 5-miliardi ma solo ai numeri primi compresi tra 4.999.999.000 e 5.000.000.000:
>java -ea javatutor.primes.Performance -t C3 4999999000 5000000000 Test performances of ListPrimes implementations Starting number: 4999999000 Ending number: 5000000000 Using implementation: Crivello3 4999999007 4999999019 4999999031 4999999057 4999999087 4999999091 4999999177 4999999201 4999999229 4999999237 4999999247 4999999259 4999999267 4999999289 4999999307 4999999313 4999999327 4999999379 4999999391 4999999399 4999999423 4999999447 4999999457 4999999481 4999999547 4999999573 4999999607 4999999621 4999999643 4999999679 4999999717 4999999729 4999999751 4999999759 4999999789 4999999799 4999999801 4999999811 4999999817 4999999859 4999999861 4999999867 4999999883 4999999903 4999999937 count of primes: 45 Time elapsed: 24,8
Noterete anche che il tempo si è abbassato: era di 29.5 secondi nel conteggio: il miglioramento è dovuto al fatto che la seconda fase della elaborazione (quella della estrazione dal setaccio) è partita da un numero prossimo al limite superiore dell'inervallo e non dal 2.
Superare il limite dei 34 miliardi
Voglio attirare la attenzione del lettore sul fatto che il limite di 235 numeri del setaccio in Crivello3 (vedi Il metodo getMaxLimit ) è dato dal numero massimo di elementi allocabili in una Java-array moltiplicato il numero di "numeri naturali" rappresentati in un elemento di tipo byte (16 numeri, otto numeri dispari + otto numeri pari i quali, ovviamente, non vengono setacciati):
limite = Integer.MAX_VALUE * 16 = 231 * 24 = 231+4 - 1
che è pari a circa 34 miliardi. Come possiamo superare questo limite? Ci sono sostanzialmente due soluzioni:
- la prima è la più semplice: invece di allocare un solo byte per elemento possiamo allocare il tipo primitivo più capiente, che è il long: abbiamo pertanto elementi lunghi 8 bytes e questo ci consente di aumentare di otto volte il limite del setaccio
- la seconda soluzione è quella di sganciarci dal linguaggio Java per l'elaborazione del setaccio ed affidarci ai linguaggi nativi (vedi Interfacciamo Java ed i linguaggi nativi)
Se per il setaccio usiamo elementi di tipo long otterremo il vantaggio di poter indirizzare 64 numeri dispari in ogni elemento della array poichè un tipo long è lungo 64 bits. Il limite del setaccio sarà così molto più alto:
limite = Integer.MAX_VALUE * 128 = 231 * 27 = 231+7 - 1
pari a poco meno di 275 miliardi. Ovviamente, si tratta per sempre di un limite teorico perchè la quantità di memoria a disposizione della JVM non è illimitata: per avere un setaccio così grande la JVM sarà costretta ad allocare 16 gigabytes di memoria, una quantità forse troppo grande per il runtime di Java.
Vi anticipo che la classe Crivello4 non è stata ancora scritta: lascio al lettore questo compito salvo dare qualche piccola dritta per facilitare la scrittura. Derivate la classe Crivello4 da Crivello: i metodi della classe base sono per già scritti e funzionanti ed è sufficente sovrascriverne solo due:
- il metodo
setacciadeve allocare una array di tipo long di dimensione pari al numero più alto da setacciare diviso 128, più uno. - il metodo
isCancelleddeve calcolare l'indice del byte e del bit da esaminare tenendo conto che ogni elemento della array contiene 64 numeri dispari e non otto
La documentazione completa in formato javadoc di questo progetto è disponibile al seguente link: Il progetto ListPrimes
Argomento precedente - Argomento successivo - Indice Generale
Generato da
1.12.0