самый быстрый способ атомарно сравнить два целых числа в C?

Question

uint64_t n;      // two 32-bit integers

return ( (uint32_t)(n >> 32) == (uint32_t)n );

Какой самый быстрый способ атомарного сравнения 32 старших значащих битов с 32 младшими значащими битами uint64_t?

Я думаю, что одно ужасное решение - сделать: получить спин-блокировку, прочитать 32 LSB, прочитать 32 MSB, сравнить, чтобы получить результат, разблокировать спин-блокировку, вернуть результат. Есть ли способ сделать это без снятия блокировки?

Answer 1

Как насчет использования операции сравнения-обмена на двух разных адресах?

Что-то вроде: CMPXCHG (int*)&n, (((int*)&n)+1) (обратите внимание - это на самом деле не может работать).

Редактировать: изменил синтаксис, чтобы более близко походить на фактический синтаксис x86.

Редактировать 2: , как указал Серж, использование двух адресов памяти в инструкции сборки не поддерживается для большинства сборок,поэтому этот способ не может работать напрямую из памяти.Это означает, что этот подход не может быть использован для сравнения двух 32-битных частей 64-битной переменной атомарным способом.

Некоторые сборки (по крайней мере, PowerPC) могут предоставить специальные инструкции (для PowerPC, LWARX и STWCX), которые могут сделать эту работу многопоточным безопасным способом, но это не совсем то, что запросил OP,и не будет работать для x86.

Answer 2

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

Answer 3

1. Вы можете сделать это без блокировки, только если вы можете атомарно получить 64-битный номер на вашей платформе.Если это возможно, то сначала - вы атомарно извлекаете 64-битное значение вашим любимым способом (например, InterlockedOr64 (ptr, 0) в 64-битных окнах, если у вас есть 32-битный процессор x86, то нет никакого способа - , если только выесли у вас процессор Intel не старше Pentium, и вы убедитесь, что ваше 64-битное значение выровнено по 64-битному алгоритму , не уверены в процессорах x86 других производителей), второе - сравните его со значением, которое вы получили.

2. Вы, очевидно, не можете сделать это портативным способом.На платформах, где вы не можете атомарно получить 64-битное число, это невозможно сделать без блокировки.

РЕДАКТИРОВАТЬ

Так как некоторые идеи вводят в заблуждениенабираю серьезную популярность в этой дискуссии. Я чувствую свою обязанность написать некоторые заметки о том, что не удалось использовать сравнение и обмен 32-разрядными числами для решения проблемы.

Давайте предположим, что у нас есть платформа x86, тогда мы могли бы написать код asm:

    mov eax, [num+4]
    lock cmpxchg [num], eax
    jz  equal_case_code
    ; non-equal case code follows
equal_case_code:
    ; equal case code follows

Очевидно, что эта реализация не является атомарной - поток может быть прерван между mov и cmpxchg инструкциями (как всегда, два операнда памяти не допускаются в одной инструкции).

32-разрядныйФункции сравнения и обмена из разных API (например, InterlockedCompareExchange из Win32 API) также не обеспечивают правильного решения, поскольку их семантика допускает атомарный доступ только к одному 32-битному адресу памяти.

Answer 4

Используйте встроенную сборку для загрузки 64-разрядного целого числа в регистр MMX или SSE (64-разрядные чтения являются атомарными), а затем сравните половинки.

Answer 5

А как насчет использования союза?Так вот так:

typedef union {
    uint32_t small[2];
    uint64_t full;
} bigint_t;

Затем вы делаете:

uint64_t n;      // two 32-bit integers

bigint_t mybigint;
mybigint.full = n;
return mybigint.small[0] == mybigint.small[1];

Я не знаю, самый ли это быстрый, но если вы не скопируете uint64_t в объединениено используйте объединение напрямую, оно должно быть достаточно быстрым, поскольку для сравнения не нужно ничего делать.