Spinlock de montage en ligne Le plus rapide

Bien qu'il y ait déjà une réponse acceptée, il y a quelques choses qui ont été manquées qui pourraient être utilisées pour améliorer toutes les réponses, tirées de Cet article Intel, tout au-dessus de l'implémentation de verrouillage rapide :

1. tourner sur une lecture volatile, pas une instruction atomique, cela évite le verrouillage inutile du bus, en particulier sur les verrous fortement contestés.
2. Utilisez back-off pour les serrures très contestées
3. Inline le verrou, de préférence avec des intrinsèques pour les compilateurs où inline asm est préjudiciable (essentiellement MSVC).

Wikipedia a un bon article sur les spinlocks, voici l'implémentation x86

Http://en.wikipedia.org/wiki/Spinlock#Example_implementation

Notez que leur implémentation n'utilise pas le préfixe "lock", car elle est redondante sur x86 pour l'instruction "xchg" - elle a implicitement une sémantique de verrouillage, comme discuté dans cette discussion Stackoverflow:

Sur un x86 multicœur, un verrou est-il nécessaire comme préfixe à XCHG?

Le REP: NOP est un alias pour PAUSE instruction, vous pouvez en apprendre plus à ce sujet ici

Comment fonctionne l'instruction de pause x86 dans spinlock *et* peut-elle être utilisée dans d'autres scénarios?

Sur la question des barrières de mémoire, voici tout ce que vous pourriez vouloir savoir

Barrières de mémoire: une vue matérielle pour les pirates logiciels par Paul E. McKenney

Http://irl.cs.ucla.edu/ ~ yingdi / paperreading / whymb. 2010. 06. 07 C. pdf

Je ne suis généralement pas du genre à me plaindre de quelqu'un qui s'efforce d'atteindre un code rapide: c'est généralement un très bon exercice qui se traduit par une meilleure compréhension de la programmation et un code plus rapide.

Je ne vais pas grip ici non plus mais je peux affirmer sans équivoque que la question d'un Spinlock rapide 3 instructions longues ou un peu plus est - au moins sur l'architecture x86-une poursuite futile.

Voici pourquoi:

Invoquer un spinlock avec une séquence de code typique

lock_variable DW 0    ; 0 <=> free

mov ebx,offset lock_variable
mov eax,1
xchg eax,[ebx]

; if eax contains 0 (no one owned it) you own the lock,
; if eax contains 1 (someone already does) you don't

Libérer un spinlock est trivial

mov ebx,offset lock_variable
mov dword ptr [ebx],0

L'instruction xchg soulève la broche de verrouillage sur le processeur, ce qui signifie que je veux le bus pendant les prochains cycles d'horloge. Ce signal se fraye un chemin à travers les caches et jusqu'au périphérique de mastering de bus le plus lent qui est généralement le bus PCI. Lorsque chaque dispositif busmastering est terminé, le signal locka (lock acknowledge) est renvoyé. Ensuite, l'échange a lieu. Le problème est que la séquence lock/locka prend beaucoup de temps. Le bus PCI peut exécuter à 33MHz avec plusieurs cycles de latence. Sur un processeur 3.3 GHz, cela signifie que chaque cycle de bus PCI prend cent cycles CPU.

En règle générale, je suppose qu'un verrou prendra entre 300 et 3000 cycles de CPU à compléter et à la fin, je ne sais pas si je vais même posséder le verrou. Ainsi, les quelques cycles que vous pouvez enregistrer par un spinlock "rapide" seront un mirage car aucun verrou n'est comme le suivant, cela dépendra de votre situation de bus pendant ce court temps.

________________MODIFIER________________

Je viens de lire que le spinlock est un " objet fortement utilisé."Eh bien, vous ne comprenez évidemment pas qu'un spinlock consomme une énorme quantité de cycles CPU chaque fois qu'il est invoqué. Ou, pour le dire autrement, chaque fois que vous l'invoquez, vous perdez une quantité importante de votre capacité de traitement.

L'astuce lors de l'utilisation de spinlocks (ou leur plus grand frère, la section critique) est de les utiliser aussi parcimonieusement que possible tout en restant réaliser la fonction de programme prévue. Les utiliser partout est facile et vous vous retrouverez avec des performances ternes en conséquence.

Il ne s'agit pas seulement d'écrire du code rapide, mais aussi d'organiser vos données. Lorsque vous écrivez "copier de petites structures entre les threads", vous devez vous rendre compte que le verrou peut prendre des centaines de fois plus de temps à terminer que la copie réelle.

________________MODIFIER________________

Lorsque vous calculez un temps de verrouillage moyen, il dites probablement très peu car il est mesuré sur votre machine qui peut ne pas être la cible prévue (qui peut avoir des caractéristiques d'utilisation de bus entièrement différentes). Pour votre machine, la moyenne sera composée de temps très rapides individuels (lorsque les activités de maîtrise du bus n'interfèrent pas) jusqu'à des temps très lents (lorsque les interférences de maîtrise du bus étaient importantes).

Vous pouvez introduire du code qui détermine les cas les plus rapides et les plus lents et calculer le quotient pour voir comment grandement les temps de spinlock peuvent varier.

________________MODIFIER________________

Mise à jour de mai 2016.

Peter Cordes a promu l'idée que "régler un verrou dans le cas non soutenu peut avoir un sens" et que les temps de verrouillage de plusieurs centaines de cycles d'horloge ne se produisent pas sur les processeurs modernes, sauf dans les situations où la variable de verrouillage est mal alignée. J'ai commencé à me demander si mon programme de test précédent - écrit en Watcom C 32 bits-pourrait être entravé par WOW64 car il fonctionnait sur un Système d'exploitation 64 bits: Windows 7.

J'ai donc écrit un programme 64 bits et l'ai compilé avec gcc 5.3 DE TDM. Le programme utilise la variante d'instruction de verrouillage implicite du bus "XCHG r, m" pour le verrouillage et une affectation simple "MOV m, r" pour le déverrouillage. Dans certaines variantes de serrure, la variable de verrouillage a été pré-testée pour déterminer s'il était possible de tenter un verrou (en utilisant un simple comparateur "CMP r,m", probablement ne pas s'aventurer à l'extérieur de L3). Ici, il est:

// compiler flags used:

// -O1 -m64 -mthreads -mtune=k8 -march=k8 -fwhole-program -freorder-blocks -fschedule-insns -falign-functions=32 -g3 -Wall -c -fmessage-length=0

#define CLASSIC_BUS_LOCK
#define WHILE_PRETEST
//#define SINGLE_THREAD

typedef unsigned char      u1;
typedef unsigned short     u2;
typedef unsigned long      u4;
typedef unsigned int       ud;
typedef unsigned long long u8;
typedef   signed char      i1;
typedef          short     i2;
typedef          long      i4;
typedef          int       id;
typedef          long long i8;
typedef          float     f4;
typedef          double    f8;

#define usizeof(a) ((ud)sizeof(a))

#define LOOPS 25000000

#include <stdio.h>
#include <windows.h>

#ifndef bool
typedef signed char bool;
#endif

u8 CPU_rdtsc (void)
{
  ud tickl, tickh;
  __asm__ __volatile__("rdtsc":"=a"(tickl),"=d"(tickh));
  return ((u8)tickh << 32)|tickl;
}

volatile u8 bus_lock (volatile u8 * block, u8 value)
{
  __asm__ __volatile__( "xchgq %1,%0" : "=r" (value) : "m" (*block), "0" (value) : "memory");

  return value;
}

void bus_unlock (volatile u8 * block, u8 value)
{
  __asm__ __volatile__( "movq %0,%1" : "=r" (value) : "m" (*block), "0" (value) : "memory");
}

void rfence (void)
{
  __asm__ __volatile__( "lfence" : : : "memory");
}

void rwfence (void)
{
  __asm__ __volatile__( "mfence" : : : "memory");
}

void wfence (void)
{
  __asm__ __volatile__( "sfence" : : : "memory");
}

volatile bool LOCK_spinlockPreTestIfFree (const volatile u8 *lockVariablePointer)
{
  return (bool)(*lockVariablePointer == 0ull);
}

volatile bool LOCK_spinlockFailed (volatile u8 *lockVariablePointer)
{
  return (bool)(bus_lock (lockVariablePointer, 1ull) != 0ull);
}

void LOCK_spinlockLeave (volatile u8 *lockVariablePointer)
{
  *lockVariablePointer = 0ull;
}

static volatile u8 lockVariable = 0ull,
                   lockCounter =  0ull;

static volatile i8 threadHold = 1;

static u8 tstr[4][32];    /* 32*8=256 bytes for each thread's parameters should result in them residing in different cache lines */

struct LOCKING_THREAD_STRUCTURE
{
  u8 numberOfFailures, numberOfPreTests;
  f8 clocksPerLock, failuresPerLock, preTestsPerLock;
  u8 threadId;
  HANDLE threadHandle;
  ud idx;
} *lts[4] = {(void *)tstr[0], (void *)tstr[1], (void *)tstr[2], (void *)tstr[3]};

DWORD WINAPI locking_thread (struct LOCKING_THREAD_STRUCTURE *ltsp)
{
  ud n = LOOPS;
  u8 clockCycles;

  SetThreadAffinityMask (ltsp->threadHandle, 1ull<<ltsp->idx);

  while (threadHold) {}

  clockCycles = CPU_rdtsc ();
  while (n)
  {
    Sleep (0);

#ifdef CLASSIC_BUS_LOCK
    while (LOCK_spinlockFailed (&lockVariable)) {++ltsp->numberOfFailures;}
#else
#ifdef WHILE_PRETEST
    while (1)
    {
      do
      {
        ++ltsp->numberOfPreTests;
      } while (!LOCK_spinlockPreTestIfFree (&lockVariable));

      if (!LOCK_spinlockFailed (&lockVariable)) break;
      ++ltsp->numberOfFailures;
    }
#else
    while (1)
    {
      ++ltsp->numberOfPreTests;
      if (LOCK_spinlockPreTestIfFree (&lockVariable))
      {
        if (!LOCK_spinlockFailed (&lockVariable)) break;
        ++ltsp->numberOfFailures;
      }
    }
#endif
#endif
    ++lockCounter;
    LOCK_spinlockLeave (&lockVariable);

#ifdef CLASSIC_BUS_LOCK
    while (LOCK_spinlockFailed (&lockVariable)) {++ltsp->numberOfFailures;}
#else
#ifdef WHILE_PRETEST
    while (1)
    {
      do
      {
        ++ltsp->numberOfPreTests;
      } while (!LOCK_spinlockPreTestIfFree (&lockVariable));

      if (!LOCK_spinlockFailed (&lockVariable)) break;
      ++ltsp->numberOfFailures;
    }
#else
    while (1)
    {
      ++ltsp->numberOfPreTests;
      if (LOCK_spinlockPreTestIfFree (&lockVariable))
      {
        if (!LOCK_spinlockFailed (&lockVariable)) break;
        ++ltsp->numberOfFailures;
      }
    }
#endif
#endif
    --lockCounter;
    LOCK_spinlockLeave (&lockVariable);

    n-=2;
  }
  clockCycles = CPU_rdtsc ()-clockCycles;

  ltsp->clocksPerLock =   (f8)clockCycles/           (f8)LOOPS;
  ltsp->failuresPerLock = (f8)ltsp->numberOfFailures/(f8)LOOPS;
  ltsp->preTestsPerLock = (f8)ltsp->numberOfPreTests/(f8)LOOPS;

//rwfence ();

  ltsp->idx = 4u;

  ExitThread (0);
  return 0;
}

int main (int argc, char *argv[])
{
  u8 processAffinityMask, systemAffinityMask;

  memset (tstr, 0u, usizeof(tstr));

  lts[0]->idx = 3;
  lts[1]->idx = 2;
  lts[2]->idx = 1;
  lts[3]->idx = 0;

  GetProcessAffinityMask (GetCurrentProcess(), &processAffinityMask, &systemAffinityMask);

  SetPriorityClass (GetCurrentProcess(), HIGH_PRIORITY_CLASS);
  SetThreadAffinityMask (GetCurrentThread (), 1ull);

  lts[0]->threadHandle = CreateThread (NULL, 65536u, (void *)locking_thread, (void *)lts[0], 0, (void *)&lts[0]->threadId);
#ifndef SINGLE_THREAD
  lts[1]->threadHandle = CreateThread (NULL, 65536u, (void *)locking_thread, (void *)lts[1], 0, (void *)&lts[1]->threadId);
  lts[2]->threadHandle = CreateThread (NULL, 65536u, (void *)locking_thread, (void *)lts[2], 0, (void *)&lts[2]->threadId);
  lts[3]->threadHandle = CreateThread (NULL, 65536u, (void *)locking_thread, (void *)lts[3], 0, (void *)&lts[3]->threadId);
#endif

  SetThreadAffinityMask (GetCurrentThread (), processAffinityMask);

  threadHold = 0;

#ifdef SINGLE_THREAD
  while (lts[0]->idx<4u) {Sleep (1);}
#else
  while (lts[0]->idx+lts[1]->idx+lts[2]->idx+lts[3]->idx<16u) {Sleep (1);}
#endif

  printf ("T0:%1.1f,%1.1f,%1.1f\n", lts[0]->clocksPerLock, lts[0]->failuresPerLock, lts[0]->preTestsPerLock);
  printf ("T1:%1.1f,%1.1f,%1.1f\n", lts[1]->clocksPerLock, lts[1]->failuresPerLock, lts[1]->preTestsPerLock);
  printf ("T2:%1.1f,%1.1f,%1.1f\n", lts[2]->clocksPerLock, lts[2]->failuresPerLock, lts[2]->preTestsPerLock);
  printf ("T3:%1.1f,%1.1f,%1.1f\n", lts[3]->clocksPerLock, lts[3]->failuresPerLock, lts[3]->preTestsPerLock);

  printf ("T*:%1.1f,%1.1f,%1.1f\n", (lts[0]->clocksPerLock+  lts[1]->clocksPerLock+  lts[2]->clocksPerLock+  lts[3]->clocksPerLock)/  4.,
                                    (lts[0]->failuresPerLock+lts[1]->failuresPerLock+lts[2]->failuresPerLock+lts[3]->failuresPerLock)/4.,
                                    (lts[0]->preTestsPerLock+lts[1]->preTestsPerLock+lts[2]->preTestsPerLock+lts[3]->preTestsPerLock)/4.);

  printf ("LC:%u\n", (ud)lockCounter);

  return 0;
}

Le programme a été exécuté sur un DELL i5-4310U basé ordinateur avec DDR3-800, 2 cœurs / 2 HTs capable de 2,7 GHz et un cache L3 commun.

Pour commencer, il semble que L'impact de WOW64 était négligeable.

Un seul thread effectuant un verrouillage/déverrouillage sans surveillance était capable de le faire une fois tous les 110 cycles. Le réglage du verrou sans surveillance est inutile: tout code ajouté pour améliorer l'instruction XCHG unique ne fera que le ralentir.

Avec quatre HTs bombardant la variable de verrouillage avec des tentatives de verrouillage, la situation change radicalement. Le temps nécessaire pour obtenir un verrou réussi saute à 994 cycles dont une partie importante peut être attribuée aux tentatives de verrouillage échouées 2.2. En d'autres termes, dans une situation à forte contention, il faut tenter en moyenne 3,2 écluses pour obtenir une écluse réussie. Évidemment, les 110 cycles ne sont pas devenus 110 * 3.2 mais plus proches de 110 * 9. Si d'autres mécanismes sont en jeu ici, tout comme avec les tests sur les vieilles machines. En outre, la moyenne 994 cycles englobe une plage comprise entre 716 et 1157

La serrure les variantes implémentant des pré-tests nécessitaient environ 95% des cycles réutilisés par la variante la plus simple (XCHG). En moyenne, ils effectuaient 17 CMPs pour trouver qu'il était possible de tenter 1,75 écluses dont 1 a réussi. Je recommande d'utiliser le pré-test non seulement parce qu'il est plus rapide: il impose moins de pression sur le mécanisme de verrouillage du bus (3,2-1,75=1,45 moins de tentatives de verrouillage) même si cela augmente légèrement la complexité.

Demande juste:

Avant de creuser cela profondément dans les structures de données spinlock et presque sans verrouillage:

Avez - vous-dans vos benchmarks et votre application-fait en sorte que les threads concurrents soient garantis pour fonctionner sur des cœurs différents?

Si ce n'est pas le cas, vous pouvez vous retrouver avec un programme qui fonctionne très bien sur votre machine de développement mais qui suce/échoue dur sur le terrain car un thread doit être à la fois le locker et le unlocker de votre spinlock.

Pour vous donner un chiffre: sous Windows vous avez une tranche de temps standard de 10 millisecondes. Si vous ne vous assurez pas que deux threads physiques sont impliqués dans le verrouillage / déverrouillage, vous finirez avec environ 500 verrous / déverrouillages par seconde, et ce résultat sera très meh