Comment améliorer cette implémentation de la radix-sort?

J’implémente un sorting Radix de 2 octets. Le concept consiste à utiliser le sorting par comptage pour sortinger les 16 bits inférieurs des nombres entiers, puis les 16 bits supérieurs. Cela me permet d’exécuter le sorting en 2 itérations. Le premier concept que j’avais était d’essayer de comprendre comment gérer les négatifs. Puisque le bit de signe serait inversé pour les nombres négatifs, puis sous forme hexadécimale, les négatifs seraient plus grands que les positifs. Pour lutter contre cela, j’ai inversé le bit de signe quand il était positif, afin de faire [0, 2 bil) = [128 000 000 000, 255 255 …). Et quand c’était négatif j’ai retourné tous les bits, pour le faire aller de (000 000 .., 127 255 ..). Ce site m’a aidé avec cette information. Pour terminer, je scinderais le nombre entier en 16 bits supérieurs ou inférieurs en fonction de la passe. Ce qui suit est le code me permettant de le faire.

static uint32_t position(int number, int pass) { int mask; if (number > 31) | 0x80000000; uint32_t out = number ^ mask; return pass == 0 ? out & 0xffff : (out >> 16) & 0xffff; } 

Pour démarrer le sorting de base réel, je devais former un histogramme de taille 65536 éléments. Le problème que j’ai rencontré était lorsque le nombre d’éléments entrés était très grand. Il faudrait un certain temps pour créer l’histogramme, je l’ai donc implémenté en parallèle, à l’aide de processus et de la mémoire partagée. J’ai partitionné le tableau en sous-sections de taille / 8. Ensuite, sur un tableau de mémoire partagée de 65536 * 8, chaque processus a créé son propre histogramme. Ensuite, j’ai tout résumé pour ne former qu’un seul histogramme. Voici le code pour cela:

 for (i=0;i<8;i++) { pid_t pid = fork(); if (pid > 3; const int stop = i == 7 ? size : ((i + 1) * size) >> 3; const int curr = i << 16; for (j=start;j<stop;++j) hist[curr + position(array[j], pass)]++; _exit(0); } } for (i=0;i<8;i++) wait(NULL); for (i=1;i<8;i++) { const int pos = i << 16; for (j=0;j<65536;j++) hist[j] += hist[pos + j]; } 

La partie suivante était où je passais la plupart de mon temps à parsingr comment le cache affectait les performances de la sum de préfixes. Avec un sorting de base Radix de 8 et 11 bits, tout l’histogramme serait contenu dans le cache L1. Avec 16 bits, il ne tiendrait que dans le cache L2. En fin de compte, l’histogramme 16 bits utilisait la sum le plus rapidement, car je n’avais à exécuter que 2 itérations. J’ai également exécuté la sum de préfixes en parallèle, conformément aux recommandations du site Web CUDA. Avec 250 millions d’éléments, cela a fonctionné environ 1,5 seconde plus lentement que l’entier sur 16 bits. Donc, ma sum de préfixes a fini par ressembler à ceci:

 for (i=1;i<65536;i++) hist[i] += hist[i-1]; 

La seule chose qui restait à faire était de parcourir le tableau en arrière et de placer tous les éléments dans leurs emplacements respectifs dans le tableau temporaire. Étant donné que je n’avais qu’à passer deux fois, au lieu de copier à partir de temp pour aller dans array, et d’exécuter le code à nouveau. J’ai d’abord exécuté le sorting en utilisant array comme entrée et temp comme sortie. Puis il l’a exécuté une deuxième fois en utilisant temp comme entrée et tableau comme sortie. Cela m’a empêché de copier la mémoire dans array les deux fois. Le code ressemble à ceci pour le sorting actuel:

 histogram(array, size, 0, hist); for (i=size-1;i>=0;i--) temp[--hist[position(array[i], 0)]] = array[i]; memset(hist, 0, arrSize); histogram(temp, size, 1, hist); for (i=size-1;i>=0;i--) array[--hist[position(temp[i], 1)]] = temp[i]; 

Ce lien contient le code complet que j’ai jusqu’à présent. J’ai effectué un test contre quicksort, qui a été exécuté 5 à 10 fois plus rapidement avec les entiers et les flottants, et environ 5 fois plus rapide avec les types de données à 8 octets. Y a-t-il un moyen d’améliorer cela?

Je suppose que traiter le signe des nombres entiers pendant le fonctionnement n’en vaut pas la peine. Cela complexifie et ralentit votre code. Je ferais un premier sorting en tant que unsigned , puis un deuxième chemin qui ne ferait que réorganiser les deux moitiés et inverser celui des négatifs.

De plus, votre code n’indique pas comment différents processus fonctionnent ensemble. Comment recueillez-vous l’histogramme chez le parent? vous avez une variable partagée de processus? Dans tous les cas, utiliser ptrhead serait beaucoup plus approprié, ici.