Nombres premiers: Crible segmenté (B)

Télécharger le projet
Commenter

Description

Bonjour,

La rapidité de l'algorithme du crible segmenté de Kim Wallisch m'épate.
Par exemple, compter explicitement tous les nombres premiers <= NN = 1'000'000'000 = 10⁹ (un milliard) se fait quasiment deux fois plus vite qu'avec le meilleur des algos que j'ai présenté.

En analysant les méthodes utilisées, il me semble que cela devrait être le contraire.
Mais les mesures montrent inexorablement que ce n'est pas le cas !

Pour essayer de trouver une explication, j'ai construit petit à petit le code PrimesToSieve.cpp qui s'approche de plus en plus de celui précité.

A) La première partie consiste à créer une liste de nombres premiers <= N = √NN.
PrimeList (voir CodeS-SourceS: Nombres premiers: PrimeList) fait cela avec N=65535 en moins d'une milliseconde et nous permettra de couvrir tout le domaine des entiers 32 bits.
Wallisch n'utilise pas une liste de nombre premiers, mais il les extrait d'un petit crible précalulé.

B) Le code PrimesToSieve parcourt l'ensemble du "grand crible", en biffant, tous les multiples des nombres premiers de la liste.

PrimesToSieve

A part la gestion des segments, le code contenu dans PrimesToSieve.cpp exécute donc (essentiellement) les mêmes instructions: 
typedef unsigned char uchar;
typedef unsigned int uint;

//  lst doit (au moins) contenir les premiers <= √NN
uchar *PrimesToSieve(uint *lst, uint NN) {
  uchar *usv=(uchar*)malloc(NN+1);
  memset(usv, 1, NN+1); usv[0]=usv[1]=0;
  for (uint k=1, p=3; p*p<=NN; p=lst[++k])
    for (uint p2=2*p, e=p*p; e<=NN; e+=p2) usv[e]=0;
  return usv; // les éléments pairs sont présents, mais ignorés
}

L'exécution de PrimesToSieve.cpp donne: 
PrimesToSieve:

4/10, 0 ms
25/100, 0 ms
168/1000, 0 ms
1229/10000, 0 ms
9592/100000, 0 ms
78498/1000000, 3 ms
664579/10000000, 59 ms
5761455/100000000, 764 ms
50847534/1000000000, 8860 ms

PrimesToOddSieve

En épurant d'avance le crible des nombres pairs (sauf 2), on divise la mémoire utilisée par 2: 
typedef unsigned char uchar;
typedef unsigned int uint;

// Crible impair (OddSieve): nombres pairs absents (sauf 2)
// correspondance:  i=e/2;  e=2*i+1; (sauf si i=0: e=2)
// i: 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 ...
// e: 2  3  5  7  9 11 13 15 17 19 21 23 25 27 29 31 33 35 ...
// p: 2  3  5  7  - 11 13 -- 17 19 -- 23 -- -- 29 31 -- -- ...

uchar *PrimesToOddSieve(uint *lst, uint NN) {
  uint E=(NN+1)/2; //  lst contient (au moins) les premiers <= √NN
  uchar *usv=(uchar*)malloc(E);
  memset(usv, 1, E);
  for (uint k=1, p=3; p*p<=NN; p=lst[++k])
    for (uint e=p*p/2; e<E; e+=p) usv[e]=0;
  return usv; // les éléments pairs ne font pas partie du crible
}


L'exécution de PrimesToOddSieve.cpp donne: 
PrimesToOddSieve:

4/10, 0 ms
25/100, 0 ms
168/1000, 0 ms
1229/10000, 0 ms
9592/100000, 0 ms
78498/1000000, 1 ms
664579/10000000, 30 ms
5761455/100000000, 612 ms
50847534/1000000000, 7108 ms
La rapidité s'améliore d'environ 20 %.

Wallisch: segmented_sieve

Le code peut être obtenu ici: Kim Walisch: segmented_sieve.cpp.

Il est hors de question de le "critiquer", car il est présenté comme "simple implementation of the segmented sieve of Eratosthenes with a few optimizations".
D'ailleurs, leur code super optimisé primesieve: Fast C/C++ prime number generator est inbattable !

Il est simple de "neutraliser" l'effet de la segmentation en forçant la taille du segment à la taille du (grand) crible.

Pour ce faire on remplace brutalement, au début du code, la ligne:
const int L1D_CACHE_SIZE = 32768;
par:
const int L1D_CACHE_SIZE = 1000000000; // = 10⁹

Les résultats sont surprenants:
NN=1000000000 Time= 8860 ms. PrimesToSieve (avec malloc(1000000000);)
NN=1000000000 Time= 7108 ms. PrimesToOddSieve (avec malloc(500000000);)
NN=1000000000 Time= 2005 ms. Wallisch original (avec L1D_CACHE_SIZE = 32768;)
NN=1000000000 Time=19846 ms. Wallisch original (avec L1D_CACHE_SIZE = 1000000000;)

Le coté positif de ce "mauvais" résultat est qu'il laisse entrevoir la possibilité d'améliorer les performances d’autres algorithmes en les "segmentant".

Il apparait que la segmentation n'est pas à proprement parler un algorithme, mais un procédé qui change (dans la mesure du possible) l'ordre des actions.
Principe: une fois qu'on accède à un segment donné, on y effectue le plus d'opérations possibles avant de passer au segment suivant.
Le but est de ménager la gestion de la mémoire virtuelle (voir: WikipédiA: Mémoire virtuelle).

Les prochaines étapes seront de segmenter PrimesToSieve, PrimesToOddSieve et bien d'autres.

Liens:
Nombres premiers
CodeS-SourceS: Le crible d'Eratosthène classique
Kim Walisch: Segmented sieve of Eratosthenes

Bonne lecture ...
Télécharger le projet

Codes Sources

A voir également

S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (William VOIROL)