fastest way to atomically compare two integers in C?

Question

uint64_t n;      // two 32-bit integers

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

What is the fastest way to atomically compare the 32 most-significant bits to the 32 least-significant bits of a uint64_t?

I think one horrible solution is to do: acquire spinlock, read 32 LSB, read 32 MSB, compare to get result, release spinlock, return result. Is there any way to do this without having to take a spinlock?

Answer 1

How about using a compare-exchange operation on the two different addresses?

Something like: CMPXCHG (int*)&n, (((int*)&n)+1) (note - this actually cannot work).

Edit: changed the syntax to more closely resemble the actual x86 syntax.

Edit 2: as Serge has pointed out, using two memory addresses in an assembly instruction is not supported for most assemblies, so this way can't work directly from memory. This means that this approach can't be used for comparing the two 32 bits portions of a 64 bit variable in an atomic fashion.

Some assemblies (PowerPC at least) are able to provide special instructions (for PowerPC, LWARX and STWCX) that can make this work in a multi-threaded safe way, but it is not exactly what the OP asked, nor will it work for x86.

Answer 2

This whole operation (atomic comparison of two values in memory) is meaningless unless you can also ensure that writing them is always atomic. It's also subject to an inherent race condition; by the time you've determined that they're equal they may have changed, or vice versa. Whatever problem you're trying to solve almost surely calls for a lock, not atomic operations.

Answer 3

1. You can do it without lock only if you are able to retrieve 64-bit number atomically on your platform. If it is possible then first - you atomically retrieve 64-bit value in your favorite way (e.g. InterlockedOr64(ptr,0) on 64-bit windows, there is no way if you have 32-bit x86 CPU - unless you have Intel CPU not older than Pentium and you make sure your 64-bit value is 64-bit aligned, not sure about other vendors' x86 CPUs), second - do your compare with the value you retrieved.

2. You obviously cannot do it in portable way. On platforms where you cannot atomically get 64-bit number it is impossible to do it without lock.

EDIT

Since some severely misleading ideas gain serious popularity in this discussion I feel my duty to write some notes about failing to use Compare&Exchange of 32-bit numbers to solve the problem.

Let's assume we have x86 platform then we might write asm code:

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

Obviously this implementation is not atomic - thread may be interrupted between mov and cmpxchg instructions (as always two memory operands not allowed in one instruction).

32-bit based Compare&Exchange functions from different APIs (like InterlockedCompareExchange from Win32 API) does not provide the correct solution either because their semantic allows atomic access to one 32-bit memory address only.

Answer 4

What about using a union? So like this:

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

Then you go do:

uint64_t n;      // two 32-bit integers

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

I don't know if this is the fastest, but if you don't copy the uint64_t into the union but use the union directly, it should be quite fast, since it does not need to do anything for the comparison.

Answer 5

Use inline assembly to load the 64-bit integer into a MMX or SSE register (64-bit reads are atomic) and then compare the halves.