Interlocked.Increment and return of incremented value

Question

We have a method which maintains global sequence index of all events in our application. As it is website, it is expected to have such method thread safe. Thread-safe implementation was following:

private static long lastUsedIndex = -1;

public static long GetNextIndex()
{
    Interlocked.Increment(ref lastUsedIndex);
    return lastUsedIndex;
}

However we noticed that under some not heavy load duplicated indexes appeared in system. Simple test shown that there are about of 1500 duplicates for 100000 iterations.

internal class Program
{
    private static void Main(string[] args)
    {
        TestInterlockedIncrement.Run();
    }
}

internal class TestInterlockedIncrement
{
    private static long lastUsedIndex = -1;

    public static long GetNextIndex()
    {
        Interlocked.Increment(ref lastUsedIndex);
        return lastUsedIndex;
    }

    public static void Run()
    {
        var indexes = Enumerable
            .Range(0, 100000)
            .AsParallel()
            .WithDegreeOfParallelism(32)
            .WithExecutionMode(ParallelExecutionMode.ForceParallelism)
            .Select(_ => GetNextIndex())
            .ToList();

        Console.WriteLine($"Total values: {indexes.Count}");
        Console.WriteLine($"Duplicate values: {indexes.GroupBy(i => i).Count(g => g.Count() > 1)}");
    }
}

This can be fixed with following implementation:

public static long GetNextIndex()
{
    return Interlocked.Increment(ref lastUsedIndex);
}

However, I do not clearly understand, why first implementation did not work. Can anybody help me describing what is happening in that case?

Answer 1

If it worked the way in your original example, you could also say that it would work for a general case of

Interlocked.Increment(ref someValue);

// Any number of operations

return someValue;

For this to be true, you would have to eliminate all concurrency (including both parallelism, reëntrancy, preëmptive code execution...) between the Increment and the return. Worse, you'd need to ensure that even if someValue is used between the return and the Increment, it wouldn't in any way affect the return. In other words - someValue must be impossible to change (immutable) between the two statements.

You can clearly see that if this were the case, you wouldn't need Interlocked.Increment in the first place - you'd just do someValue++. The whole purpose of Interlocked and other atomic operations is to ensure that the operation either happens at once (atomically) or not at all. In particular, it defends you against any kind of instruction reordering (either through CPU optimisations or through multiple threads running in parallel on two logical CPUs, or being preëmpted on a single CPU). But only within the atomic operation. The subsequent read of someValue is not part of the same atomic operation (it is atomic itself, but two atomic operations don't make the sum atomic as well).

But you aren't trying to do "Any number of operations", are you? Actually, you are. Because there's other threads running asynchronously with respect to your thread - your thread might be preëmpted by one of those threads, or the threads might truly be running in parallel on multiple logical CPUs.

In a real environment, your example provides an ever-increasing field (so it is a bit better than someValue++), but it doesn't provide you with unique ids, because all you're reading is someValue at some uncertain moment in time. If two threads try to do the increment at the same time, both will succeed (Interlocked.Increment is atomic), but they will also read the same value from someValue.

This doesn't mean that you always want to use the return value of Interlocked.Increment - if you are more interested in the increment itself, and not the incremented value. A typical example might be a cheap profiling method - each method call might increment a shared field, and then the value is read once in a while for e.g. an average of calls per second.

Answer 2

According to comments the following is happening.

Assume we have lastUsedIndex == 5 and 2 parallel threads.

First thread will execute Interlocked.Increment(ref lastUsedIndex); and lastUsedIndex will become 6. Then second thread will execute Interlocked.Increment(ref lastUsedIndex); and lastUsedIndex will become 7.

Then both threads will return value of lastUsedIndex (remember that they are parallel). And that value is now 7.

In second implementation both threads will return result of Interlocked.Increment() function. Which will be different in each thread (6 and 7). In other words, in second implementation we return a copy of incremented value and that copy is not affected in other threads.