Projet de Programmation - Assembleur 2016-2017

Objectifs

L'objectif de ce projet est de préparer l'examen final en apprenant à se familiariser avec les instructions assembleur et les concepts liés au langage assembleur.

Rappel : Table de Hashage

Recherche dans une liste

On rappelle que la complexité de la recherche d'un objet dans une liste non triée de $n$ élements est en $O(n/2)$. Cela signifie que si une liste contient 100.000 objets, trouver si un objet est dans la liste prend en moyenne 50.000 comparaisons d'objets de la liste.

Cette complexité théorique est calculée comme la moyenne arithmétique des cas favorable et défavorable.

Soit $O({n + 1}/2)$, lorsque $n$ est grand, 1 est négligeable, on obtient donc une complexité en $O({n}/2)$.

Principe de la table de hashage

Une table de hashage est un conteneur (container en anglais), c'est à dire qu'elle stocke des objets sous forme d'un tableau avec la particularité de pouvoir retrouver un objet avec une complexité en $O(1)$, soit en une opération.

Pour récupérer (s'il existe dans la table) un objet de manière instantanée, on définit pour les objets une fonction de hashage qui calcule pour chaque objet une valeur de hashage (valeur entière) qui correspond à un indice du tableau. Idéalement la fonction de hashage calcule une valeur unique pour chaque objet de manière à ce qu'il y ait une bijection entre les objets et les indices du tableau.

Malheureusement ce n'est pas toujours le cas, il est possible que plusieurs objets aient la même valeur de hashage (fonction surjective). Pour remédier à ce problème, chaque entrée de la table de hashage contient en fait une liste d'objets.

Exemple

Si on traite 100.000 objets et que l'on définit une table de hashage avec 1000 entrées (1000 listes), chaque liste contient en moyenne 100 objets. Pour récupérer un objet il faudra donc :

Au final, par rapport à une liste non triée, le facteur d'amélioration est de :

$$f = {50.000}/{50} = 1000$$

On vérifiera donc qu'un objet est présent ou non dans la table de hashage de 1000 entrées 1000 fois plus rapidement que dans une liste.

Sujet

La solution que l'on vous propose d'implanter ici est une variante de la précédente ou chaque élément de la liste chainée ne contient pas un objet mais 32 objets, ceci dans le but :

On vous demande d'écrire un programme C ou C++ qui permet d'insérer des chaines de caractères d'une longueur de 3 à 8 caractères générées aléatoirement dans une une table de hashage de $k$ entrées.

Comme indiqué, chaque entrée de la table contient une liste chainée de buckets (seaux) qui stockent un maximum de 32 chaines.

Les chaines sont stockées verticalement dans le tableau au format C. Le symbole # dans l'exemple ci-dessous marque la fin de la chaine. La première chaine du bucket est donc EIXLWP.


EULTPZJEUOIVXGXNUBTNDRIBYKNGOQEO
IBXMAAPDDYOTVZUBPRPYQWHNJGCGDLFN
XNEPBVDWOIESQRZPXICERVOBDMURTASC
LPQHNKQTN#AQJ#DZBZRBMVXF#FWLDNU
WF#GUBAKM.SE#..R#RM##L#HA.IFALFY
PJ.GSPIFY.UO...W.UF..G.PH.#VYQZ#
#J.#IMDT#.XW...F.##..V.##..BV#R.
.#..##V#..##...S.....Y.....#E.N.
@@@@@@#@@@@@@@@#@@@@@#@@@@@@#@#@

Les structures de données à utiliser sont les suivantes, vous ne devez pas les modifier :


// maximum length of a string to store
#define STRING_MAX_LENGTH 8

// maximum number of strings in a bucket
#define BUCKET_MAX_STRINGS 32

// default value for number of entries of hash table
int HASH_TABLE_MAX_ENTRIES = 33;

// default value for numbers of words/strings to store
// in the hash table
int WORDS_MAX = 1000000;

/**
 * Data structure for list of BUCKET_MAX_STRINGS strings
 */
typedef struct HashTableBucket {
	// pointer to next element in the list
	struct HashTableBucket *next; 
	// number of strings recorded in this bucket
	int nbr;
	// array of characters to store strings
	char strings[(STRING_MAX_LENGTH+1) * BUCKET_MAX_STRINGS];
} HashTableBucket;


/**
 * Data structure for HashTable: you need to create
 * the entries depending on the value of 
 * HASH_TABLE_MAX_ENTRIES
 */
typedef struct {
	HashTableBucket **entries;
} HashTable;

La fonction de hashage pour les chaines de caractères est

unsigned int hash_value(char *s) {
    unsigned int h = 0;
    
    while (*s != '\0') h = ((h*31) + *s++);
    return h % HASH_TABLE_MAX_ENTRIES;
}

On écrira les fonctions C/C++ :

On écrira une version assembleur (nasm) vectorisée de la fonction de recherche qui permet de comparer les chaines en parallèle dans un bucket:

Questions

Voici la liste des questions auxquelles vous devrez répondre :

  1. Quel est le temps pris pour rechercher les mots insérés dans la table de hashage en utilisant la fonction cpp_HT_find pour 100.000 ou 1.000.000 de chaines ?
  2. Quel est le temps pris pour rechercher des mots non présents dans la table de hashage en utilisant la fonction cpp_HT_find ?
  3. Quel est le temps pris pour rechercher les mots insérés dans la table de hashage en utilisant la fonction asm_HT_find vectorisée ?
  4. Quel est le temps pris pour rechercher des mots non présents dans la table de hashage en utilisant la fonction asm_HT_find vectorisée ?

Pour comparer deux implantations (implantation de REFérence et OPTimisée), on peut définir deux valeurs

Quelques résultats

Voici quelques résultats obtenus pour l'implantation que j'ai développé.

On reporte :

Table de hashage avec liste d'objets

Ici on choisit une implantation classique avec un objet par élément de la liste :

 entrées   #mots   insertion   existants   manquants   CEE   CET   CME   CMT 
 1   10000   0.007659   0.746924   1.50333   49.767.945   50.000.000   100.000.000   100.000.000 
 2   10000   0.005758   0.48038   0.857083   24.886.609   25.000.000   50.000.018   50.000.000 
 4   10000   0.006484   0.238282   0.515179   12.451.542   12.500.000   24.997.537   25.000.000 
 10   10000   0.007585   0.097107   0.272462   4.986.844   5.000.000   10.002.452   10.000.000 
 100   10000   0.008143   0.013805   0.035852   507.162   500.000   1.000.358   1.000.000 
 1000   10000   0.007403   0.003222   0.010648   59.916   50.000   100.502   100.000 
Table 1 - HashTable + liste chainée avec une chaine de caractères par élément de la liste (temps en secondes - 32 bits architecture)
 entrées   #mots   insertion   existants   manquants   CEE   CET   CME   CMT 
 1   50000   0.037332   20.5896   43.8444   1.218.645.875   1.250.000.000   2.500.000.000   2.500.000.000 
 2   50000   0.032498   12.709   28.8501   609.356.374   625.000.000   1.250.049.928   1.250.000.000 
 4   50000   0.037773   9.0131   19.0686   304.699.506   312.500.000   625.027.444   625.000.000 
 10   50000   0.036492   3.89902   9.75821   121.917.537   125.000.000   250.024.169   250.000.000 
 100   50000   0.029826   0.44175   1.18852   12.233.840   12.500.000   24.991.012   25.000.000 
 1000   50000   0.037405   0.059375   0.195421   1.266.674   1.250.000   2.498.551   2.500.000 
Table 2 - HashTable + liste chainée avec une chaine de caractères par élément de la liste (temps en secondes - 32 bits architecture)
 entrées   #mots   insertion   existants   manquants   CEE   CET   CME   CMT 
 1   100000   0.064687   81.5409   174.123   4.774.899.482   5.000.000.000   10.000.000.000   10.000.000.000 
 2   100000   0.054468   52.7931   122.969   2.387.475.923   2.500.000.000   5.000.009.800   5.000.000.000 
 4   100000   0.05772   44.1858   113.326   1.193.761.335   1.250.000.000   2.500.008.620   2.500.000.000 
 10   100000   0.057161   20.2193   55.274   477.575.121   500.000.000   1.000.025.441   1.000.000.000 
 100   100000   0.056147   2.76092   7.482   47.841.451   50.000.000   99.997.194   100.000.000 
 1000   100000   0.053547   0.287672   0.801672   4.866.845   5.000.000   9.999.949   10.000.000 
Table 3 - HashTable + liste chainée avec une chaine de caractères par élément de la liste (temps en secondes - 32 bits architecture)

Remarque 1 : si on considère les cas (Table 2 - 50.000 chaines, 1 entrées) et (Table 3 - 100.000 chaines, 1 entrées), on multiplie le nombre de chaines par 2, mais le temps de calcul de la recherche des mots existants est multiplié par 4 (ici 3.9602). En effet on recherche $N$ éléments et la recherche d'un élément s'effectue en $N/2$ opérations on a donc un algorithme en $O(N^2/2)$

Remarque 2 : En théorie (voir Table 3) quand on passe de 1 à 2 entrées on divise le nombre de comparaisons par 2 (cf. colone CET) . Or le temps lui n'est pas divisé par 2. Le facteur d'amélioration est de 1.54 (81.5409/52.7931).

Table de hashage avec buckets de 32 chaines

architecture 32 bits

 entrées   #mots   insertion   existants   manquants 
 1   50000   0.026215   4.42288   10.0286 
 2   50000   0.025777   2.24490   4.94433 
 4   50000   0.023862   1.15787   2.4954 
 10   50000   0.027885   0.470804   1.00578 
 100   50000   0.028135   0.054073   0.1198 
 1000   50000   0.030065   0.010967   0.031232 
 1   100000   0.048591   17.6342   42.0738 
 2   100000   0.047789   8.99737   20.7294 
 4   100000   0.048941   4.65618   10.5845 
 10   100000   0.046712   1.88282   4.17696 
 100   100000   0.049872   0.204773   0.454415 
 1000   100000   0.052521   0.033698   0.087061 
Table 4 - HashTable + bucket
 entrées   #mots   insertion   existants   manquants 
 1   50000   0.028743   1.0681   2.58122 
 2   50000   0.024331   0.54398   1.26289 
 4   50000   0.025063   0.296426   0.656672 
 10   50000   0.024724   0.122168   0.275197 
 100   50000   0.026144   0.018671   0.04747 
 1000   50000   0.026078   0.006805   0.023926 
 1   100000   0.049946   4.68604   11.8382 
 2   100000   0.051602   2.44821   6.25723 
 4   100000   0.051191   1.33566   3.44339 
 10   100000   0.048893   0.52519   1.30009 
 100   100000   0.05042   0.066423   0.163984 
 1000   100000   0.048843   0.018013   0.054788 
Table 5 -HashTable + bucket + vectorisation

Si on compare les 3 implantations (liste de chaines, liste de buckets, liste de bucket + vectorisation) on obtient le tableau suivant :

 implantation   entrées   #mots   manquants   facteur   pourcentage 
 liste   1   100000   81.5409   ref   ref 
 bucket   1   100000   17.6342   x4.62   -78% 
 bucket+vect   1   100000   4.68604   x17.40   -94% 
 liste   100   100000   2.76092   ref   ref 
 bucket   100   100000   0.204773   x13.48   -92% 
 bucket+vect   100   100000   0.066423   x41.56   -97% 
 liste   1000   100000   0.287672   ref   ref 
 bucket   1000   100000   0.033698   x8.53   -88% 
 bucket+vect   1000   100000   0.018013   x15.97   -93% 
Table 6 - comparaison des implantations

architecture 64 bits

 entrées   #mots   insertion   existants   manquants 
 1   50000   0.022606   4.39365   10.1807 
 2   50000   0.021228   2.27499   5.09816 
 4   50000   0.022594   1.1381   2.49292 
 10   50000   0.018205   0.462285   0.992982 
 100   50000   0.020634   0.052274   0.11342 
 1000   50000   0.021557   0.010721   0.025558 
 1   100000   0.038971   17.5786   47.848 
 2   100000   0.040584   10.328   24.282 
 4   100000   0.058863   5.21676   11.8525 
 10   100000   0.055778   2.14696   4.86756 
 100   100000   0.046063   0.218888   0.519018 
 1000   100000   0.044459   0.037364   0.088299 
Table 7 - HashTable + bucket
 entrées   #mots   insertion   existants   manquants 
 1   50000   0.028794   1.24149   3.19231 
 2   50000   0.029348   0.654452   1.6438 
 4   50000   0.019681   0.344795   0.771084 
 10   50000   0.018343   0.13729   0.311433 
 100   50000   0.026513   0.019422   0.049749 
 1000   50000   0.031378   0.009753   0.031275 
 1   100000   0.043545   5.67649   13.6761 
 2   100000   0.049881   2.975   7.41553 
 4   100000   0.0507   1.50907   3.82663 
 10   100000   0.059147   0.650067   1.47674 
 100   100000   0.040772   0.070523   0.170046 
 1000   100000   0.043286   0.024269   0.058898 
Table 8 -HashTable + bucket + vectorisation

Table de hashage avec buckets de 64 chaines

Architecture 32 bits

 entrées   #mots   insertion   existants   manquants 
 1   50000   0.028719   3.84395   8.7815 
 2   50000   0.028367   1.99244   4.33398 
 4   50000   0.026499   1.01658   2.17348 
 10   50000   0.025701   0.415526   0.884416 
 100   50000   0.025416   0.048332   0.106887 
 1000   50000   0.025243   0.010108   0.028734 
 1   100000   0.049198   15.1814   35.7318 
 2   100000   0.046419   7.86506   18.0387 
 4   100000   0.046187   3.99101   8.89236 
 10   100000   0.050024   1.63098   3.58589 
 100   100000   0.051634   0.180195   0.396152 
 1000   100000   0.054409   0.029185   0.077616 
Table 9 - HashTable + bucket
 entrées   #mots   insertion   existants   manquants 
 1   50000   0.026714   0.671574   1.5649 
 2   50000   0.02715   0.363193   0.811541 
 4   50000   0.026612   0.18735   0.414178 
 10   50000   0.026933   0.080179   0.179334 
 100   50000   0.028959   0.014889   0.036802 
 1000   50000   0.028056   0.006924   0.021394 
 1   100000   0.048759   3.00734   7.99068 
 2   100000   0.051721   1.61464   4.20121 
 4   100000   0.048799   0.784202   1.93244 
 10   100000   0.049083   0.323418   0.780123 
 100   100000   0.051268   0.048121   0.115868 
 1000   100000   0.053954   0.016878   0.047769 
Table 10 -HashTable + bucket + vectorisation

Architecture 64 bits

 entrées   #mots   insertion   existants   manquants 
 1   50000   0.021752   3.90219   8.8711 
 2   50000   0.02075   1.9932   4.34646 
 4   50000   0.019103   1.06476   2.16426 
 10   50000   0.019506   0.413957   0.875613 
 100   50000   0.019847   0.048748   0.102256 
 1000   50000   0.021629   0.009832   0.023343 
 1   100000   0.04019   15.5099   36.2079 
 2   100000   0.03877   7.87803   17.9913 
 4   100000   0.039466   3.99406   8.87796 
 10   100000   0.034783   1.6387   3.58044 
 100   100000   0.040762   0.177261   0.384605 
 1000   100000   0.040787   0.028061   0.066369 
Table 11 - HashTable + bucket
 entrées   #mots   insertion   existants   manquants 
 1   50000   0.017653   0.703368   1.84196 
 2   50000   0.023274   0.345986   0.798993 
 4   50000   0.021172   0.172753   0.388973 
 10   50000   0.019796   0.075506   0.171569 
 100   50000   0.018899   0.015424   0.031684 
 1000   50000   0.022404   0.007383   0.016274 
 1   100000   0.036722   3.23217   8.21048 
 2   100000   0.04001   1.52942   3.92306 
 4   100000   0.040048   0.747169   1.8624 
 10   100000   0.037553   0.314345   0.740921 
 100   100000   0.038227   0.047004   0.102059 
 1000   100000   0.039272   0.016795   0.037262 
Table 12 -HashTable + bucket + vectorisation