Je suis à la recherche pour obtenir des instructions (machine x86) ou l'optimisation de la ligne de code suivante:Trouver premier bit et mis hors service il atomiquement
lock()
int x = ffs(words); // find first bit that set
long words = unset(x, words); // unset the bit "x" in "words"
unlock()
Je ne sais pas comment faire cela sans verrouillage.
Si words est un type non signé, le calcul non-atomique peut se faire comme suit:
words &= ~-words;
Ou, ce qui revient
words &= words - 1;
Cela fonctionne parce que dans -words (en supposant complément à 2 , que les types non signés doivent utiliser), le moins significatif 1 et tous les 0 à droite de celui-ci sont inchangés, alors que tous les bits à gauche du moins significatif 1 sont inversés. Donc, words & ~-words sera identique à words sauf pour le moins significatif 1.
Cependant, pour faire cela atomiquement, vous devrez soit utiliser un verrou comme indiqué dans la question, soit vous devrez faire un spin-loop autour d'un échange-et-échange atomique.
En fait, j'ai besoin de la mèche, pas simplement de l'annuler. Comment savoir quel bit est défini? Et de plus cela nécessite également un verrou. – w00d
@ w00d: Voulez-vous dire que vous avez besoin du bit, ou vous avez besoin de l'indice du bit? Le bit est 'words & -words', mais pour obtenir l'index du bit, vous devez utiliser quelque chose comme' ffs'. Je sais que cela nécessite un verrou: je l'ai dit dans le dernier paragraphe. Il n'y a aucun moyen de le faire sans une sorte de synchronisation externe, soit un verrou ou un compare-and-swap ou équivalent. – rici
c'est l'indice du bit. – w00d
Je doute que vous puissiez, à moins qu'il y ait une instruction machine permettant ce type d'opération. –
Je crains que vous ayez à vous contenter d'une boucle de spin de comparaison et d'échange pour cela. Quelle est la largeur du bitfield? – doynax
Une recherche binaire ferait au moins une telle boucle O (log). Bien que vous passiez probablement plus de temps sur les décisions que vous économisez théoriquement, surtout quand vous considérez qu'il ne serait pas pratique de se dérouler. – Tommy