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

Question

• I have an array with 250k entities (20 bytes in size) and 4 threads.
• Each stream changes ~ 100k random objects (this means that you cannot predict which entities it will touch). It can modify the same object several times.
• Each object receives changes up to ~ 10 times.
• Modification takes ~ 10 ^-6 seconds.
• Each object is modified by several threads.

Both last points are the most important facts. The 5th paragraph implies that I need a mechanism to protect my objects from damage due to simultaneous access / modification. The 4th point makes me worry about whether classic locking mechanisms, such as mutexes that block threads, will create large overheads, given the short blocking times.

I came up with two ideas:

• Using spin locks to overcome overhead (assuming my cost assumption is correct in the first place).
• Providing each thread with a local copy of the array, which it can change without interruption. After all the threads have ended, the union of all arrays into one. This is possible because I can choose a winner if there are several copies of the entity.

? - ? , ?:

• 1M
• 8
• ~ 500k
• ~ 100

#/. Net. .

(structs). - .

Answer 1

, ( - , ):-)

250K 4 , () . , , , . , . , , , .

250K ? , . - :

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

. , . , , , , , , .

Answer 2

, . - , .

.

, , ~ 10.09 . ~ 9,03 :

const int numOfPersons = 250000;
var persons = new List<Person>(numOfPersons);
for (int i = 0; i < numOfPersons; i++)
{
    persons.Add(new Person());
}

var rand = new Random();

var sw = Stopwatch.StartNew();

for (int j = 0; j < 100; j++)
{
    for (int i = 0; i < 100000; i++)
    {
        int index = rand.Next(0, numOfPersons);

        Person person = persons[index];
        lock (person)
        {
            person.Name += "a";
        }
    }
}

Console.WriteLine(sw.Elapsed);

, , , .

, ~ 1 . 100 100 000 250 000 . 1- , , .

Answer 3

, ( 20 ). , , , ?

, , 4 ( 8 64 ) ( ). . , . , , ( , , , " " ).

I have no idea what this will do with performance because you can explicitly select values ​​for an array of type instead of an array of reference type. However, it is sometimes useful to make a decision simpler than harder. This solution can also improve cache locality, as you are talking about random access to a large array. Therefore, this array will not fit into the CPU cache, and you will have many cache misses.