Algorithmes d'optimisation avec Fast Disk Storage (SSD)?

Question

Étant donné que les disques SSD (Solid State Disks) sont en baisse de prix et vont bientôt devenir plus répandus en tant que disques système, et que leurs taux d'accès sont nettement supérieurs à ceux des supports magnétiques tournants, quels algorithmes standard gagneront en performances grâce à l'utilisation de SSD pour le stockage local? Par exemple, la vitesse de lecture aléatoire élevée des disques SSD confère à une table de hachage sur disque une viabilité pour les grandes tables de hachage; 4 Go d'espace disque sont facilement disponibles, ce qui rend viable le hachage sur un entier entier de 32 bits (davantage pour la recherche que pour la population, ce qui prendrait encore beaucoup de temps); Bien que la taille de la table de hachage ne puisse fonctionner avec des médias en rotation en raison de la vitesse d'accès, cela ne devrait pas être un problème avec les disques SSD.

Existe-t-il d'autres domaines dans lesquels la transition imminente vers les disques SSD générera des gains potentiels en termes de performances algorithmiques? Je préférerais voir comment une chose va fonctionner plutôt que l'opinion; Je ne veux pas que cela devienne litigieux.

Answer 1

Votre exemple de hashtables est en effet la structure de base de données clé qui en bénéficiera. Au lieu d'avoir à charger un fichier entier de 4 Go ou plus en mémoire pour rechercher des valeurs, le disque SSD peut être sondé directement. Le SSD est toujours plus lent que la RAM, par ordre de grandeur, mais il est tout à fait raisonnable d’avoir une table de hachage de 50 Go sur le disque, mais pas dans la RAM, sauf si vous payez beaucoup d’argent pour un gros fer.

Un exemple est celui des bases de données de positions d’échecs. J'ai plus de 50 Go de positions hachées. Il existe un code complexe pour essayer de regrouper les positions liées les unes à côté des autres dans le hachage. Je peux donc parcourir 10 Mo de la table à la fois et espérer en réutiliser une partie pour plusieurs requêtes de position similaires. Il y a une tonne de code et de complexité pour rendre cela efficace.

Remplacé par un SSD, j’ai réussi à abandonner toute la complexité de la mise en cluster et à utiliser des hachages vraiment stupides et randomisés. Les performances ont également augmenté car je ne récupérais que les données dont j'avais besoin sur le disque, pas les gros morceaux de 10 Mo. Le temps de latence est certes plus important, mais la vitesse d’accélération nette est considérable et le code ultra-propre (20 lignes, et non plus de 800) est peut-être encore plus agréable.

Answer 2

Les SSD ne sont significativement plus rapides pour un accès aléatoire. Accès séquentiel au disque, ils ne sont que deux fois plus performants que les lecteurs rotatifs traditionnels. De nombreux disques SSD ont des performances plus médiocres dans de nombreux scénarios, ce qui entraîne une dégradation des performances, comme indiqué ci-après. -state-drives-and.aspx "rel =" nofollow noreferrer "> ici .

Les disques SSD déplacent considérablement l'aiguille, mais ils sont toujours beaucoup plus lents que les opérations du processeur et de la mémoire physique. Pour votre exemple de table de hachage de 4 Go, vous pourrez peut-être utiliser plus de 250 Mo / s d'un disque SSD pour accéder à des compartiments aléatoires de table de hachage. Pour un entraînement en rotation, vous auriez de la chance de casser les Mo / s à un chiffre. Si vous pouvez conserver cette table de hachage de 4 Go en mémoire, vous pourrez y accéder de l'ordre de plusieurs gigaoctets par seconde, bien plus rapidement que même un disque SSD très rapide.

L'article référencé répertorie plusieurs modifications effectuées par MS pour Windows 7 lors de l'exécution sur des disques SSD, ce qui peut vous donner une idée du type de modifications que vous pouvez envisager d'apporter. Premièrement, SuperFetch pour la pré-extraction de données hors du disque est désactivé. Il est conçu pour contourner les temps d’accès aléatoires lents pour les disques qui sont allégés par les disques SSD. La défragmentation est désactivée, car la répartition des fichiers sur le disque ne nuit pas aux performances des disques SSD.

Answer 3

Ipso facto, tout algorithme auquel vous pouvez penser qui nécessite de nombreuses E / S disque aléatoires (random étant le mot clé, ce qui permet de jeter le principe de la localisation aux oiseaux, éliminant ainsi l'utilité de beaucoup continue).

Je pouvais cependant constater que certains systèmes de base de données en tiraient profit. MySQL, par exemple, en utilisant le moteur de stockage MyISAM (où les enregistrements de données sont essentiellement des CSV glorifiés). Cependant, je pense que les très grandes tables de hachage seront votre meilleur choix pour de bons exemples.

Answer 4

Les disques SSD sont beaucoup plus rapides pour les lectures aléatoires, un peu pour les lectures séquentielles et plus lents pour les écritures (aléatoires ou non).

Ainsi, une table de hachage sur disque n'est <<> pas utile avec un SSD, car sa mise à jour prend désormais beaucoup de temps, mais la recherche du disque devient (par rapport à un disque dur normal) très économique.

Answer 5

Ne vous leurrez pas. Les SSD sont encore beaucoup plus lents que la mémoire système. Tout algorithme qui choisit d'utiliser la mémoire système sur le disque dur sera toujours beaucoup plus rapide, toutes choses égales par ailleurs.