Large array and multiple threads - spinlocks or local buffers or something else?

Question

• I have an array with 250k entities (with a size of 20 bytes) and 4 threads.
• Each thread modifies ~100k random entities (that means, you can't predict which entities it will touch). It can modify the same entity multiple times.
• Each entity gets modified up to ~10 times.
• The modification takes ~10^-6 seconds.
• Each entity gets modified by multiple threads

The both last points are the most important facts. The 5th point implies that I need a mechanism to protect my entities from getting corrupted due to concurrent access/modification. The 4th point makes me worry whether classical locking mechanisms like mutexes, which block threads, create to much overhead considering the short timespan a lock would be acquired for.

I've come up with two ideas:

• Using spinlocks to overcome the overhead (presupposing my assumption about the overhead is correct in the first place).
• Giving each thread a local copy of the array it can modify without interruptions. After all threads have finished, merging all arrays into one. This is possible because I'm able to pick a winner, if there are multiple copies of an entity.

What do You recommend? Do You agree on one of my ideas or do You recommend something else? Does Your recommendation change if I change the numbers to?:

• 1M entities
• 8 threads
• ~500k random accesses
• ~100 modifications per entity

Please also point me towards implementations in C#/.Net. Thanks in advance.

Additional Informations
The entities are value types (structs). I can not afford to create new objects for each write operation - only modify existing primitives.

Answer 1

As they say, there's more than one way to skin a cat (though why anybody wants skinned cat is another question) :-)

With 250K objects and 4 threads, you'd have to guess that conflicts will be (relatively) rare. That doesn't mean that we can ignore them, but it may affect how we look for them. Testing a critical section is very fast, unless there is actually a conflict. That means that it might be feasible to check a critical section for every transaction, in the knowledge that relatively few checks will take more that a few CPU ticks.

Is it feasible to create 250K critical sections? Maybe, I'm not sure. You can create a very lightweight spinlock with:

while (0 != ::InterlockedExchange(&nFlag, 1)) {};
DoStuff();
nFlag = 0;

An alternate approach might to partition the dataset and have each thread work on a unique set of objects. That makes conflicts impossible so no locking is needed. Depending on the nature of the problem, you might achieve this by having each thread operate on a range of data, or possibly by operating a queue for each worker thread and have one or more scanning threads identify objects needing processing and pushing them onto the appropriate processing queue.