Je recherche une bibliothèque C comprenant des cartes de hachage de style STM (logiciel de la mémoire transactionnelle), mais je n'avais pas de chance jusqu'à présent. Ce serait génial s'il était basé sur Glib / Gobject, mais ce n'est pas si crucial. Il n'a pas non plus besoin de transactions appropriées sur de nombreux objets - un support de hachage immuable unique est tout ce dont j'ai vraiment besoin.
Doit blâmer: instantané immuable lecture, écriture sans verrouillage avec auto-réessaye.
3 Réponses :
Wikipedia a une liste de diverses Mises en œuvre STM .
J'ai regardé à travers celles-ci. Mais ils sont très bas niveau. Le meilleur pour l'intégration est probablement STMMAP: Github.com/skaphan/stmmap . Mais je cherche quelque chose qui inclut déjà la mise en œuvre de HASHMAP. Malheureusement, je ne peux pas être sûr que la bibliothèque de structure de données aléatoire est sûre de simplement utiliser au-dessus de la bibliothèque STM ... Je préférerais quelque chose de travailler sur un niveau supérieur. (Structure de données prête + solution STM)
Eh bien, je pense (et il y a un certain nombre d'études) que la STM actuelle n'est pas plus rapide que le code basé sur le verrouillage et le mutex. Il est évident: STM nécessite une vérification des conflits de données en ligne. Cependant, une telle vérification des conflits dans les logiciels pure nécessite des frais généraux de temps très énormes. Actuellement, seul Sun's Rock Processor prend en charge une forme limitée de STM (HTM de meilleur effort avec STM) par matériel. No x86 cpus ne prend actuellement en charge TM dans le matériel. En bref, la STM est juste lente.
À mon avis, vous feriez mieux d'utiliser une table de hachage simultanée. Par exemple, vous pouvez trouver En outre, je pense que de telles structures de données hautement concurrentes (généralement implémentées comme verrouillées) ne sont pas toujours utiles. Dans certains modèles de charge de travail, l'utilisation de telles structures de données n'est pas bonne. Pour être sûr, je vous recommande d'écrire un petit micro-repère pour deux versions de tables hachées: (1) sans verrouillage et (2) à base de verrouillage. En outre, gardez à l'esprit que les modèles de chargement de la charge de travail pour un tel micro-repère devraient être proches de la réelle. Un exemple pourrait être trouvé dans ici . concurrent_hash_map dans Intel TBB. Voici le lien de manuel TBB . Oh, mais c'est C ++, pas C. Mais je pense que vous pouvez (bien que cela puisse prendre un travail important) Traduire C ++ - basé sur une telle table de hachage au code C. Intel TBB est open source.
Je sais qu'ils sont parfois plus lents. Mais ils sont également plus faciles plus faciles dans une solution spécifique. J'ai un grand hachage qui est souvent lu, rarement écrit à. Écrivez également prendre beaucoup de temps et avez-vous d'abord besoin d'une recherche. Avec une piscine de lecteurs et 1 écrivain, c'est un cas parfait pour la STM. De plus, vous n'avez pas besoin d'une vérification de conflit en ligne. Vous pouvez implémenter de nombreuses solutions de style STM de manière à ce que le lecteur n'attend jamais et que jamais bloque (et aucun écrivain n'attend jamais, bien que cela soit nécessaire de réessayer) en utilisant uniquement la norme CMPXCHG. Pour moi, c'est une synchronisation toutes les 30 sections -vs, en saisissant le verrou de lecture tous les 10 ms.
Je comprends ton problème. Il est préférable d'utiliser la structure de données «sans verrouillage» plutôt que sur le style STM. STM signifie toujours une vérification des conflits. Qu'en est-il de la RCU? en.wikipedia.org/wiki/read-copy-update
Ps. Je sais que Concurrent_hash_map est censé être "LOCK-MOINS", mais ils écrivent: "car avoir accès à un élément peut bloquer d'autres threads, essayer de raccourcir la durée de vie de l'accesseur ou de const_accessor." Pas assez bon pour moi dans ce cas.
Minjang: C'est ce que je voulais dire (plus ou moins;)). D'après ce que je comprends une carte de hachage GC'D immuable basée sur la RCU Trie, répond à peu près à la définition d'une carte de hachage de STM (c'est-à-dire exactement les mêmes propriétés). Ou je manque quelque chose?
STM n'est que la mise en œuvre du niveau logiciel de TM. TM est une approche spéculative pour gérer les serrures efficacement. Par définition, TM est une généralisation de structures de données sans verrouillage. Donc, la carte de hachage de STM n'a pas de sens pour moi et je n'ai jamais entendu ces termes. C'est juste sans attendre / sans verrouillage. Dans l'architecture X86 actuelle, il n'y a pas de magie que vous pouvez faire mieux qu'une structure de données sans verrouillage conventionnelle. Je crois que la structure de données ressemblant à RCU est la meilleure des charges de travail en lecture intensive.
Vouliez-vous dire STL au lieu de STM?
Je pense qu'il désigne la mémoire transactionnelle STM - Software - car il cherche des choses comme des instantanés et une nouvelle rétréct: FR. wikipedia.org/wiki/software_transactional_memory Mais il devrait probablement en faire clairement, puisque STM n'est pas un quartier très bien connu.
Corrigé la description. Michael a raison.