Discussion :

[yannoo95170]

Je viens de commencer à développer un petit utilitaire me permettant de tester les différentes fonctions de hachage de Cuckoo

J'y implémenté le filtre de Cuckoo qui utilise 2 fonctions de hachages int h1( int k, int modulo ) et h2( int k, int modulo ) afin de trouver en quasi temps constant si une entrée y est ou pas

J'ai y très légèrement modifié les fonctions de hachage h1() et h2() afin de pouvoir y gérer les nombres négatifs :
(les fonctions originales sont identiques hormis la suppression du if/else et l'inversion de la valeur de k si elle est négative)

Code c :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int cuckoo_hash1( int k, int modulo )
{
	// return k % modulo;
 
	if ( k >= 0 )
		return k % modulo;
	else
		return -k % modulo;
}  
 
int cuckoo_hash2( int k , int modulo )
{
	// return ( k / modulo )  % modulo;
 
	if ( k >= 0 )
		return ( k / modulo) % modulo;
	else
		return ( -k / modulo ) % modulo;
}

J'y ai de plus mis en place un système permettant d'associer différentes fonctions de hachage possibles h1() et h2() entre elles pour en faire un banc de filtres

Code c :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
int cuckoo_hash0( int k, int modulo )
{
	return k & modulo;
}
 
void cuckoo_hash_func( int rang, HashFunc func )
{
	HashFuncs[rang] = func;
}
 
void cuckoo_init_hash_funcs0()
{
	cuckoo_hash_func(1, cuckoo_hash0);
 
	nHashFuncs = 1;
}
 
void cuckoo_init_hash_funcs1()
{
	cuckoo_hash_func(1, cuckoo_hash1);
	cuckoo_hash_func(2, cuckoo_hash2);
 
	nHashFuncs = 2;
}
 
void cuckoo_init_hash_funcs2()
{
	cuckoo_hash_func(1, cuckoo_hash2);
	cuckoo_hash_func(2, cuckoo_hash1);
 
	nHashFuncs = 2;
}
 
void cuckoo_init_hash_funcs()
{
	switch( HashType )
	{
		case HASH_FUNCS_DEFAULT : cuckoo_init_hash_funcs0(); break;
		case HASH_FUNCS_MODULO  : cuckoo_init_hash_funcs1(); break;
		case HASH_FUNCS_DIVIDE  : cuckoo_init_hash_funcs2(); break;
	}
}

=> d'après ce que j'ai trouvé sur le Net, les valeurs de modulo les plus utilisées sont 11 et 31 mais j'ai très agréablement été surpris par la combinaison de la valeur de modulo = 9 et le banc de filtre HASH_FUNCS_DIVIDE :
( HASH_FUNCS_MODULO est le filtre de Cuckoo classique, le filtre HASH_FUNCS_DIVIDE étant tout simplement la permutation des fonctions h1() et h2() dans le banc de 2 fonctions de hachage utilisées par le filtre de Cuckoo)

1) cette combinaison semble bien fonctionner tant avec des valeurs décimales avec des puissances en base 10

Code x :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
yannoo@Thinkoo:~/Dev/Cuckoo$ ./cuckoo 1 10 100 1000 10000 100000

Cuckoo v0.2 by Cylone 

cuckoo_insert(1) 
cuckoo_insert(10) 
cuckoo_insert(100) 
cuckoo_insert(1000) 
cuckoo_insert(10000) 
cuckoo_insert(100000) 

key 	 T1 	      T2 
=== 	 ===       === 
0 	 1 	  
1 	 10 	  
2 	 100 	  
3 	 1000 	  
4 	 10000 	  
5 	 100000 	  
6 	  	  
7 	  	  
8 	  	  

key 	 T3 
=== 	 === 

6 entries cached on T1[] , 0 entries cached on T2[] and 0 entries in T3[] 

6 / 6 = 100% insertions OK :) 

load factor = 6 / 18 = 33% 

extension factor = 0 / 18 = 0% extended

2) qu'avec des valeurs de puissances en base 2 :

Code x :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
yannoo@Thinkoo:~/Dev/Cuckoo$ ./cuckoo 1 2 4 8 16 32 64 128 256 512 1024 2048

Cuckoo v0.2 by Cylone 

cuckoo_insert(1) 
cuckoo_insert(2) 
cuckoo_insert(4) 
cuckoo_insert(8) 
cuckoo_insert(16) 
cuckoo_insert(32) 
cuckoo_insert(64) 
cuckoo_insert(128) 
cuckoo_insert(256) 
cuckoo_insert(512) 
cuckoo_insert(1024) 
cuckoo_insert(2048) 

key 	 T1 	    T2 
=== 	 ===    === 
0 	 4 	  
1 	 16 	    1 
2 	 512     2 
3 	 32 	  
4 	  	   256 
5 	 128    2048 
6 	  	  
7 	 64 	  1024 
8 	  	   8 

key 	 T3 
=== 	 === 

6 entries cached on T1[] , 6 entries cached on T2[] and 0 entries in T3[] 

12 / 12 = 100% insertions OK :) 

load factor = 12 / 18 = 67% 

extension factor = 0 / 18 = 0% extended

=> les entrées sont hyper bien triées dans le cas de l'utilisation puissances de 10 **ET** sont étonnamment toutes présentes les tableaux T1 et T2, bien qu'y étant néanmoins très dispersées

Le tableau T3 permet quand à lui de stocker les valeurs qui ne peuvent être stockées dans les tableaux T1[] ou T2[], du fait de leurs très petite taille qui ne permet pas d'y stocker beaucoup d'entrées, soit 2 x 9 = 18 valeurs au grand maximum avec l'utilisation de modulo 9 et le facteur de remplissage variant entre 0 et 1 tournant aux alentours de 0.5 = 50% en moyenne (de 33% à 72% dans ces exemples) , comme par exemple ici avec 17 premières puissances de 2 :

Code x :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
 yannoo@Thinkoo:~/Dev/Cuckoo$ ./cuckoo 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536

Cuckoo v0.2 by Cylone 

cuckoo_insert(1) 
cuckoo_insert(2) 
cuckoo_insert(4) 
cuckoo_insert(8) 
cuckoo_insert(16) 
cuckoo_insert(32) 
cuckoo_insert(64) 
cuckoo_insert(128) 
cuckoo_insert(256) 
cuckoo_insert(512) 
cuckoo_insert(1024) 
cuckoo_insert(2048) 
cuckoo_insert(4096) 
cuckoo_insert(8192) 
cuckoo_insert(16384) 
cuckoo_insert(32768) 
cuckoo_insert(65536) 

key 	 T1 	          T2 
=== 	 === 	 === 
0 	 65536 	  
1 	 256 	 1 
2 	 16384 	 8192 
3 	 32 	  
4 	 32768 	 4 
5 	 128 	 2048 
6 	  	  
7 	 64 	 16 
8 	  	 512 

key 	 T3 
=== 	 === 
0 	 4096 
1 	 1024 
2 	 8 
3 	 2 

7 entries cached on T1[] , 6 entries cached on T2[] and 4 entries in T3[] 

17 / 17 = 100% insertions OK :) 

load factor = 13 / 18 = 72% 

extension factor = 4 / 18 = 22% extended

=> J'aimerais bien augmenter le nombre de fonctions de hachages utilisables par le banc de filtres, en l'étendant à 3 ou 4 quatres fonctions de hachage distinctes plutôt que les "seulement** 2 fonctions h1() et h2() actuellement utilisées

==> faut-il bien que je regarde du côté des filtres de Bloom ???

[yannoo95170]

Voici ce que celà donne avec l'exemple donné sur la page https://en.wikipedia.org/wiki/Cuckoo_hashing

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
 
yannoo@Thinkoo:~/Dev/Cuckoo$ ./cuckoo 20 50 53 75 100 67 105 3 36 39
 
Cuckoo v0.2 by Cylone 
 
cuckoo_insert(20) 
cuckoo_insert(50) 
cuckoo_insert(53) 
cuckoo_insert(75) 
cuckoo_insert(100) 
cuckoo_insert(67) 
cuckoo_insert(105) 
cuckoo_insert(3) 
cuckoo_insert(36) 
cuckoo_insert(39) 
 
key 	 T1 	 T2 
=== 	 === 	 === 
0 	 3 	        36 
1 	  	        100 
2 	 105 	 20 
3 	  	  
4 	 39 	  
5 	 53 	        50 
6 	  	  
7 	 67 	  
8 	 75 	  
 
key 	 T3 
=== 	 === 
 
6 entries cached on T1[] , 4 entries cached on T2[] and 0 entries in T3[] 
 
10 / 10 = 100% insertions OK :) 
 
load factor = 10 / 18 = 56% 
 
extension factor = 0 / 18 = 0% extended

=> existe-t-il une méthode pour étendre la gestion des tables de hachage T1[] et T2[], afin d'éviter les collisions, à plus de 2 tables, cf. 3 ou 4 tables par exemples ?

A noter que j'y ai déjà ajouté une table T3[] afin de stocker les valeurs qui rentrent en collisions qui ne peuvent résolues via l'algorithme de hachage de Cuckoo à 2 fonctions de hachage en raison de leur faible taille mais il faut un temps linéaire pour y détecter la présence d'une valeur, et non en temps constant comme possible via les tables T1[] et T2[]
=> est-on obligé de se limiter à 2 fonctions/tables de hachage, plus 1 table de stockage volumineuse pour y mémoriser les valeurs ne pouvant être stockées dans T1[] ou T2[] en raison de la petite taille de ses 2 tables ?
( il est bien sûr possible d'utiliser des tables de hachage de bien plus grande taille mais elles sont vite "saturées" à plus de 50% et la table de recherche "linéaire" T3[] se retrouve alors relativement vite peuplée : les recherches dans cette table s'y font donc en temps linéaire et non en temps constant comme possible par T1[] et T[2] via une fonctions de hachage)

[yannoo95170]

J'ai de plus remarqué que l'algorithme de Cucko est vraiment très sensible à la valeur du modulo utilisé
(je comprend maintenant clairement beaucoup mieux ce que l'on appelle l'effet d'avalanche sur les fonctions de hashage cryptographiques, surtout quand le hash généré est dépendant des précédents)

Pour commencer, j'y ai essayé les valeurs de modulo 11 et 31 qui sont les coefficients qui semblent le plus souvent utilisés avec le hashage de Cuckoo

Puis y est testées différentes valeurs de modulo afin d'essayer de mieux comprendre l'impact de cette valeur sur le peuplage des tableaux
=> la valeur 9 pour le modulo m'a particulièrement plue car elle me permet d'ordonner de manière relativement naturelle les puissances de 10 en entrées en les triant de manière croissante

Par contre, en travaillant sur des puissances de 2, c'est de nouveau redevenu "le bordel" dans les tableaux T1[] et T2[] **mais** bien qu"elles y soient rangées de manière qui semble assez "aléatoire", elle se retrouvent toutes dans les tableaux T1[] et T2[]
=> une idée pourquoi le modulo 9 marche si bien avec les puissances de 10, tout en marchant encore relativement bien avec les puissances de 2 ???

C'est le seul petit modulo que j'ai trouvé qui semble avoir cette propriété
=> peut-être est-ce parce que 9 = 3 au carré ( ou que 9 soit égal à 10 - 1 ?) pour la base 10 et/ou que 9 = une puissance de 2 au cube + 1 pour les puissances de 2 ?
(je connais les nombres de Mersenne = 2 puissance qqchsose - 1 qui ont des propriétés particulières mais rien à propos de de l'équivalent avec +1 à la place de -1 après le calcul de la puissance)

Cf. existe-t-il d'autres valeurs de modulo "magiques" autres que 11, 31 ou 9 ???
(j'en ai essayé quelques unes d'autres mais elles sont relativement petites et ne font pas mieux que 11 ou 31 pour toutes celles que j'ai essayé , la valeur de modulo 9 étant l'exception qui m'a agréablement surpris car fonctionne hyper bien avec les puissances des 10 tout en restant relativement compacte avec des puissances de 2)

[yannoo95170]

Je viens de faire une "découverte perso" en faisant un peu mumuse avec les nombres premiers
=> ils semblent permettre de mapper un immense domaine de valeurs en utilisant la multiplication d'un nombre relativement limité de "bits premiers"
(ici, seulement 14 "bits premiers" permettent de mapper un domaine allant de 1 à plusieurs centaines de milliards de milliards tout de même ...)

Le code que j'ai utilisé :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
 
#include <stdio.h> 
#include <stdlib.h>
#include <math.h> 
 
#define NUM_DIGITS	14
 
int Primes[] = { 1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 31, 37, 43, 47, 53, 59 }; 
 
void PrintFirstPrimes( int nDigits )
{
	int sum = 0;
 
	for ( int i = 0 ; i < nDigits ; i++ )
	{
		sum += Primes[i];
 
		printf("Primes[%d] = %d \n", i, Primes[i] );
	}
 
	printf("The sum of the firsts %d primes number is %d \n\n", nDigits, sum);  
}
 
void PrintSumMultPrimes( int nDigits )
{
	int maxi = (int) pow(2, nDigits);
	long long int sum;
 
	for( int i = 0 ; i < maxi ; i++ )
	{
		sum = 1;
 
		for ( int j = 0 , bit = 1 ; j < nDigits ; j++, bit <<= 1 )
		{
			if( i & bit )
			{
				sum *= Primes[j];
			} 
		}
 
		printf("SumMultPrimes[%d] = %lld \n", i, sum );
	}
}
 
int main( int argc, char *argv[] )
{
	printf("Primes v0.1 by Cyclone \n");
 
	PrintFirstPrimes( NUM_DIGITS );
 
 
	PrintSumMultPrimes( NUM_DIGITS );
 
 
 
	return 0;
}

Et le resultat obtenu, dont j'ai volontairement supprimé un gros morceau des "SumMultPrimes[index] = xxxxxxxxx" afin que ça ne prennent pas trop de place sur ce post

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
 
yannoo@Thinkoo:~/Dev/Primes$ ./primes
Primes v0.1 by Cyclone 
Primes[0] = 1 
Primes[1] = 2 
Primes[2] = 3 
Primes[3] = 5 
Primes[4] = 7 
Primes[5] = 11 
Primes[6] = 13 
Primes[7] = 17 
Primes[8] = 19 
Primes[9] = 23 
Primes[10] = 31 
Primes[11] = 37 
Primes[12] = 43 
Primes[13] = 47 
The sum of the firsts 14 primes number is 259 
 
SumMultPrimes[0] = 1 
SumMultPrimes[1] = 1 
SumMultPrimes[2] = 2 
SumMultPrimes[3] = 2 
SumMultPrimes[4] = 3 
SumMultPrimes[5] = 3 
SumMultPrimes[6] = 6 
SumMultPrimes[7] = 6 
SumMultPrimes[8] = 5 
SumMultPrimes[9] = 5 
SumMultPrimes[10] = 10 
SumMultPrimes[11] = 10 
SumMultPrimes[12] = 15 
SumMultPrimes[13] = 15 
SumMultPrimes[14] = 30 
SumMultPrimes[15] = 30 
SumMultPrimes[16] = 7 
SumMultPrimes[17] = 7 
SumMultPrimes[18] = 14 
SumMultPrimes[19] = 14 
SumMultPrimes[20] = 21 
SumMultPrimes[21] = 21 
SumMultPrimes[22] = 42 
SumMultPrimes[23] = 42 
SumMultPrimes[24] = 35 
SumMultPrimes[25] = 35 
SumMultPrimes[26] = 70 
SumMultPrimes[27] = 70 
SumMultPrimes[28] = 105
... 
SumMultPrimes[1316] = 19437 
SumMultPrimes[1317] = 19437 
SumMultPrimes[1318] = 38874 
SumMultPrimes[1319] = 38874 
SumMultPrimes[1320] = 32395 
SumMultPrimes[1321] = 32395 
SumMultPrimes[1322] = 64790 
SumMultPrimes[1323] = 64790 
SumMultPrimes[1324] = 97185 
SumMultPrimes[1325] = 97185 
SumMultPrimes[1326] = 194370 
SumMultPrimes[1327] = 194370 
SumMultPrimes[1328] = 45353 
SumMultPrimes[1329] = 45353 
SumMultPrimes[1330] = 90706 
SumMultPrimes[1331] = 90706 
...
SumMultPrimes[9615] = 14118330 
SumMultPrimes[9616] = 3294277 
SumMultPrimes[9617] = 3294277 
SumMultPrimes[9618] = 6588554 
SumMultPrimes[9619] = 6588554 
SumMultPrimes[9620] = 9882831 
SumMultPrimes[9621] = 9882831 
SumMultPrimes[9622] = 19765662 
SumMultPrimes[9623] = 19765662 
SumMultPrimes[9624] = 16471385 
SumMultPrimes[9625] = 16471385 
SumMultPrimes[9626] = 32942770 
SumMultPrimes[9627] = 32942770 
SumMultPrimes[9628] = 49414155 
SumMultPrimes[9629] = 49414155 
SumMultPrimes[9630] = 98828310 
SumMultPrimes[9631] = 98828310 
SumMultPrimes[9632] = 5176721 
SumMultPrimes[9633] = 5176721 
SumMultPrimes[9634] = 10353442 
..
SumMultPrimes[12228] = 15619108479 
SumMultPrimes[12229] = 15619108479 
SumMultPrimes[12230] = 31238216958 
SumMultPrimes[12231] = 31238216958 
SumMultPrimes[12232] = 26031847465 
SumMultPrimes[12233] = 26031847465 
SumMultPrimes[12234] = 52063694930 
SumMultPrimes[12235] = 52063694930 
SumMultPrimes[12236] = 78095542395 
SumMultPrimes[12237] = 78095542395 
SumMultPrimes[12238] = 156191084790 
SumMultPrimes[12239] = 156191084790 
SumMultPrimes[12240] = 36444586451 
SumMultPrimes[12241] = 36444586451 
SumMultPrimes[12242] = 72889172902 
SumMultPrimes[12243] = 72889172902 
SumMultPrimes[12244] = 109333759353 
SumMultPrimes[12245] = 109333759353 
SumMultPrimes[12246] = 218667518706 
SumMultPrimes[12247] = 218667518706 
SumMultPrimes[12248] = 182222932255 
SumMultPrimes[12249] = 182222932255 
...
SumMultPrimes[16375] = 103429736347938 
SumMultPrimes[16376] = 86191446956615 
SumMultPrimes[16377] = 86191446956615 
SumMultPrimes[16378] = 172382893913230 
SumMultPrimes[16379] = 172382893913230 
SumMultPrimes[16380] = 258574340869845 
SumMultPrimes[16381] = 258574340869845 
SumMultPrimes[16382] = 517148681739690 
SumMultPrimes[16383] = 517148681739690

=> bon ok, ce n'est pas un mappage linéaire mais il a tout de même tendance à proposer des petits chiffres au début, des moyens après et d'aller de plus en plus vers des valeurs de plus en astronomiques au fur et à mesure que l'on arrive vers la fin
(des centaines de milliards de milliards avec l'utilisation de **SEULEMENT** 14 "bits premiers" tout de même !!!)
==> en y ajoutant un système de virgule fixe (ou "glissante", à voir) , ça permettrait assez sûrement de représenter des valeurs très très petites tout comme des valeurs très très grandes avec un minimum de bits
===> je regarde plus en détail la distribution des valeurs générées via ces "bits premiers" et vous ferais un retour assez prochainement sur les résultats de cette analyse
(à la première vue des valeurs obtenues, je pense que l'utilisation de "bits premiers" à la place des bits classiques, + gestion d'une "virgule fixe ou glissante", pourraient efficacement être utilisés pour remplacer les float par des "petits float" par exemple)
[c'est plus au niveau de la granularité que ça me paraît un peu moins top par contre **MAIS**, avec un peu beaucoup de chance, ça pourrait peut-être passer via l'utilisation d'une virgule fixe ou "glissante" pour passer de valeurs entières à des valeurs à virgule relativement grandes, tout en restant relativement assez précises, et ce avec l'utilisation de pourtant relativement peu de bits => j'ai dû utiliser des "long long int", soit des valeurs entières sur 64 bits, pour faire la somme et le printf de valeurs générées à partir de seulement 14 "bits premiers" tout de même : c'est pas rien car nombre de bits divisés par un peu plus de 4,5 tout de même, soit un passage de 64 bits "classiques/binaires" à seulement 14 bits "premiers" ... ]

[Guesset]

Bonjour yannoo95170,

(les fonctions originales sont identiques hormis la suppression du if/else et l'inversion de la valeur de k si elle est négative)

Code c :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
int cuckoo_hash1( int k, int modulo ) {   // return k % modulo;
   if ( k >= 0 )
      return k % modulo;
   else
     return -k % modulo;
}  
 
int cuckoo_hash2( int k , int modulo ) {   // return ( k / modulo )  % modulo;
   if ( k >= 0 )
      return ( k / modulo) % modulo;
   else
      return ( -k / modulo ) % modulo;
}

Les 2 fonctions ne retournent pas le bon modulo quand k est négatif (par ailleurs il n'est pas vérifié que modulo n'est pas nul ou négatif même si cela n'est peut être pas nécessaire).

Supposons k = 59 et m(odulo) = 7, k = 7*8 + 3 donc k % m = 3 et -k % m = -3 soit 4 [modulo m] alors que la fonction réécrite donner 3. Proposition (peut être que déclarer les fonctions inline aurait de l'effet) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
int cuckoo_hash1( int k , int m) {
   k = k % m;
   return k >= 0 ? k: k + m;              // k = a*m² + b*m + d => return b
}
int cuckoo_hash2( int k , int m) {
   k = (k / m) % m;
   return k >= 0 ? k: k + m;              // k = a*m² + b*m + d => return b
}

Salutations