Относительная производительность swap vs lock-and-swap locks на x86

Ответ 1

Я предполагаю, что atomic_swap (lockaddr, 1) переводится в xchg reg, mem инструкция и atomic_compare_and_swap (lockaddr, 0, val) переводится в cmpxchg [8b | 16b].

Некоторые разработчики ядра Linux считают, что cmpxchg ist быстрее, потому что префикс блокировки не подразумевается как с xchg. Поэтому, если вы находитесь в однопроцессорном, многопоточном или можете в противном случае убедиться, что блокировка не нужна, вы, вероятно, лучше с cmpxchg.

Но, скорее всего, ваш компилятор переведет его на "lock cmpxchg", и в этом случае это не имеет большого значения. Также обратите внимание, что в то время как задержки для этих инструкций являются низкими (1 цикл без блокировки и около 20 с блокировкой), если вы используете обычную переменную синхронизации между двумя потоками, что вполне обычное явление, будут выполняться некоторые дополнительные циклы шины, которые в последний раз навсегда по сравнению с задержками команд. Скорее всего, они будут спрятаны с помощью кэширования snoop/sync/mem access/bus lock/whatever/200/500 cpu циклов.

Ответ 2

Я нашел этот документ Intel, заявив, что на практике нет никакой разницы:

http://software.intel.com/en-us/articles/implementing-scalable-atomic-locks-for-multi-core-intel-em64t-and-ia32-architectures/

Один общий миф состоит в том, что блокировка, использующая инструкцию cmpxchg, дешевле, чем блокировка, использующая инструкцию xchg. Это используется потому, что cmpxchg не будет пытаться получить блокировку в эксклюзивном режиме, так как cmp будет проходить первым. На рисунке 9 показано, что cmpxchg так же дорого, как и инструкция xchg.

Ответ 3

В x86 любая команда с префиксом LOCK выполняет все операции с памятью как циклы чтения-модификации-записи. Это означает, что XCHG (с неявным LOCK) и LOCK CMPXCHG (во всех случаях, даже если сравнение не удается), всегда получает исключительную блокировку в строке кэша. В результате практически нет различий в производительности.

Обратите внимание, что многие процессоры, вращающиеся на одной и той же блокировке, могут вызвать много издержек шины в этой модели. Это одна из причин того, что петли спин-блокировки должны содержать инструкции PAUSE. Некоторые другие архитектуры имеют лучшие операции для этого.

Ответ 4

Вы уверены, что не имели в виду

 if (!atomic_load(lockaddr)) {
       if (!atomic_swap(lockaddr, val)) /* got the lock */

для второго?

Проверить и установить блокировки (см. Wikipedia https://en.wikipedia.org/wiki/Test_and_test-and-set) - довольно распространенная оптимизация для многих платформ.

В зависимости от того, как реализуется сравнение и обмен, он может быть быстрее или медленнее, чем тест и тест и установить.

Поскольку x86 - это относительно более мощная оптимизация HW платформы, которая может сделать тест и тест и установить блокировки быстрее, может быть менее возможно.

Рисунок 8 из документа, найденного Бо Перссоном http://software.intel.com/en-us/articles/implementing-scalable-atomic-locks-for-multi-core-intel-em64t-and-ia32-architectures/ показывает, что блокировки Test и Test и Set превосходят производительность.

Ответ 5

Что касается производительности на процессорах Intel, то одно и то же, но для простоты, чтобы все было проще понять, я предпочитаю первый путь из приведенных вами примеров. Нет причин использовать cmpxchg для получения блокировки, если вы можете сделать это с помощью xchg.

В соответствии с принципом бритвы Оккама, простые вещи лучше.

Кроме того, блокировка с помощью xchg более мощная - вы также можете проверить правильность логики своего программного обеспечения, то есть, что вы не получаете доступ к байту памяти, который не был явно выделен для блокировки, или что вы не дважды откройте.

Нет консенсуса относительно того, следует ли освобождать блокировку как обычный магазин или хранилище lock -ed. Например, LeaveCriticalSection под Windows 10 использует хранилище lock -ed для блокировки даже в однопроцессорном процессоре; в то время как на нескольких физических процессорах с Non-Uniform-Memory-Access (NUMA) возникает вопрос о том, как освободить блокировку: нормальный магазин и хранилище lock -ed может быть еще более важным.

См. этот пример более безопасных функций блокировки, которые проверяют данные на достоверность, и ловит попытки освободить блокировки, которые не были получены:

const
  cLockAvailable = 107; // arbitrary constant, use any unique values that you like, I've chosen prime numbers
  cLockLocked    = 109;
  cLockFinished  = 113;

function AcquireLock(var Target: LONG): Boolean; 
var
  R: LONG;
begin
  R := InterlockedExchange(Target, cLockByteLocked);
  case R of
    cLockAvailable: Result := True; // we've got a value that indicates that the lock was available, so return True to the caller indicating that we have acquired the lock
    cLockByteLocked: Result := False; // we've got a value that indicates that the lock was already acquire by someone else, so return False to the caller indicating that we have failed to acquire the lock this time
      else
        begin
          raise Exception.Create('Serious application error - tried to acquire lock using a variable that has not been properly initialized');
        end;
    end;
end;

procedure ReleaseLock(var Target: LONG);
var
  R: LONG;
begin
  // As Peter Cordes pointed out (see comments below), releasing the lock doesn't have to be interlocked, just a normal store. Even for debugging we use normal load. However, Windows 10 uses locked release on LeaveCriticalSection.
  R := Target;
  Target := cLockAvailable;
  if R <> cLockByteLocked  then
  begin
    raise Exception.Create('Serious application error - tried to release a  lock that has not been actually locked');
  end;
end;

Ваше основное приложение здесь:

var
  AreaLocked: LONG;
begin
  AreaLocked := cLockAvailable; // on program initialization, fill the default value

  .... 

 if AcquireLock(AreaLocked) then
 try
   // do something critical with the locked area
   ... 

 finally
   ReleaseLock(AreaLocked); 
 end;

....

  AreaLocked := cLockFinished; // on program termination, set the special value to catch probable cases when somebody will try to acquire the lock

end.

Вы также можете использовать следующий код как цикл вращения, он использует обычную нагрузку, вращаясь для экономии ресурсов, как это предложил Питер Кордес. После 5000 циклов он вызывает функцию Windows API SwitchToThread(). Это значение 5000 циклов является моим эмпирическим. Значения от 500 до 50000 также кажутся в порядке, в некоторых сценариях более низкие значения лучше, а в других выше - лучше. Обратите внимание, что этот код можно использовать только для процессоров, поддерживающих SSE2 - вы должны проверить соответствующий бит CPUID перед вызовом инструкции pause, иначе в противном случае будет просто потеря мощности. На процессорах без pause просто используйте другие средства, такие как EnterCriticalSection/LeaveCriticalSection или Sleep (0), а затем Sleep (1) в цикле. Некоторые говорят, что на 64-битных процессорах вы не можете проверить SSE2, чтобы убедиться, что инструкция pause реализована, потому что исходная архитектура AMD64 приняла в качестве основных инструкций Intel SSE и SSE2 и, практически, если вы запускаете 64- битный код, вы уже наверняка имеете SSE2 и, следовательно, инструкцию pause. Тем не менее, Intel отказывается от практики использования специфической функции присутствия и явно заявляет, что в будущих процессорах может исчезнуть определенная функция, и приложения должны всегда проверять функции через CPUID. Однако инструкции SSE стали повсеместными, и многие 64-разрядные компиляторы использовали их без проверки (например, Delphi для Win64), поэтому вероятность того, что в некоторых будущих процессорах не будет SSE2, не говоря уже о pause, очень тонкая.

// on entry rcx = address of the byte-lock
// on exit: al (eax) = old value of the byte at [rcx]
@Init:
   mov  edx, cLockByteLocked
   mov  r9d, 5000
   mov  eax, edx
   jmp  @FirstCompare
@DidntLock:
@NormalLoadLoop:
   dec  r9
   jz   @SwitchToThread // for static branch prediction, jump forward means "unlikely"
   pause
@FirstCompare:
   cmp  [rcx], al       // we are using faster, normal load to not consume the resources and only after it is ready, do once again interlocked exchange
   je   @NormalLoadLoop // for static branch prediction, jump backwards means "likely"
   lock xchg [rcx], al
   cmp  eax, edx        // 32-bit comparison is faster on newer processors like Xeon Phi or Cannonlake.
   je   @DidntLock
   jmp  @Finish
@SwitchToThread:
   push  rcx
   call  SwitchToThreadIfSupported
   pop   rcx
   jmp  @Init
@Finish: