Jump to page: 1 2
Thread overview
associative array with Parallel
Jul 22, 2021
seany
Jul 22, 2021
jfondren
Jul 22, 2021
frame
Jul 22, 2021
Ali Çehreli
Jul 22, 2021
frame
Jul 22, 2021
seany
Jul 22, 2021
jfondren
Jul 22, 2021
seany
Jul 22, 2021
jfondren
Jul 22, 2021
seany
Jul 23, 2021
seany
July 22, 2021

Consider :

int [] ii;
foreach(i,dummy; parallel(somearray)) {
  ii ~= somefunc(dummy);
}

This is not safe, because all threads are accessing the same array and trying to add values and leading to collision.

But :

int [] ii;
ii.length = somearray.length;
foreach(i,dummy; parallel(somearray)) {
  ii[i] ~= somefunc(dummy);
}

This is safe. In this case, threads are accessing an unique memory location each.

But what about this :

int [ string ] ii;
ii.length = somearray.length;
foreach(i,dummy; parallel(somearray)) {
  string j = generateUniqueString(i);
  ii[j] ~= somefunc(dummy);
}

Is this also guaranteed thread safe?

In my 5 runs, I did not see any problems, but I'd like to confirm. Thank you.

July 22, 2021

On Thursday, 22 July 2021 at 05:46:25 UTC, seany wrote:

>

But what about this :

int [ string ] ii;
ii.length = somearray.length;
foreach(i,dummy; parallel(somearray)) {
  string j = generateUniqueString(i);
  ii[j] ~= somefunc(dummy);
}

Is this also guaranteed thread safe?

No. Consider https://programming.guide/hash-tables-open-vs-closed-addressing.html

In the open-addressing case, one thread may be searching the backing array while another thread is modifying it. In the closed-addressing case, one thread may be modifying a linked list while another thread is searching it.

July 22, 2021

On Thursday, 22 July 2021 at 05:53:01 UTC, jfondren wrote:

>

On Thursday, 22 July 2021 at 05:46:25 UTC, seany wrote:

>

But what about this :

int [ string ] ii;
ii.length = somearray.length;
foreach(i,dummy; parallel(somearray)) {
  string j = generateUniqueString(i);
  ii[j] ~= somefunc(dummy);
}

Is this also guaranteed thread safe?

No. Consider https://programming.guide/hash-tables-open-vs-closed-addressing.html

In the open-addressing case, one thread may be searching the backing array while another thread is modifying it. In the closed-addressing case, one thread may be modifying a linked list while another thread is searching it.

This is another parallel foreach body conversion question.
Isn't the compiler clever enough to put a synchronized block here?

July 21, 2021
On 7/21/21 11:01 PM, frame wrote:

> This is another parallel foreach body conversion question.
> Isn't the compiler clever enough to put a synchronized block here?

parallel is a *function* (not a D feature). So, the compiler might have to analyze the entire code to suspect race conditions. No, D does not have such features.

But even if it did, we wouldn't want synchronized blocks in parallelization because a synchronized block would run a single thread at a time and nothing would be running in parallel anymore.

Ali

July 22, 2021

On Thursday, 22 July 2021 at 05:53:01 UTC, jfondren wrote:

>

No. Consider https://programming.guide/hash-tables-open-vs-closed-addressing.html

The page says :

> >

A key is always stored in the bucket it's hashed to.

What if my keys are always unique?

July 22, 2021

On Thursday, 22 July 2021 at 07:23:36 UTC, seany wrote:

>

On Thursday, 22 July 2021 at 05:53:01 UTC, jfondren wrote:

>

No. Consider https://programming.guide/hash-tables-open-vs-closed-addressing.html

The page says :

> >

A key is always stored in the bucket it's hashed to.

What if my keys are always unique?

That has no bearing on the problem. Two of your unique keys might map to the same bucket.

July 22, 2021

On Thursday, 22 July 2021 at 07:27:52 UTC, jfondren wrote:

>

On Thursday, 22 July 2021 at 07:23:36 UTC, seany wrote:

>

On Thursday, 22 July 2021 at 05:53:01 UTC, jfondren wrote:

>

No. Consider https://programming.guide/hash-tables-open-vs-closed-addressing.html

The page says :

> >

A key is always stored in the bucket it's hashed to.

What if my keys are always unique?

That has no bearing on the problem. Two of your unique keys might map to the same bucket.

OK.
Sorry for the bad question : what if i pregenerate every possible key, and fill the associative array where each such key contains some invalid number, say -1 ?

Then in process, the parallel code can grab the specific key locations. Will that also create the same problem ?

July 22, 2021
On Thursday, 22 July 2021 at 06:47:52 UTC, Ali Çehreli wrote:

> But even if it did, we wouldn't want synchronized blocks in parallelization because a synchronized block would run a single thread at a time and nothing would be running in parallel anymore.

But it only affects the block, the other code could still run in parallel till this point is reached from any thread.

Well, I just have assumed that the compiler does a conversion here knowing the parallel stuff. Of course there is no room for such a feature if the compiler only converts the foreach body as a delegate for the opApply() method. Thanks for clarification.


July 22, 2021

On Thursday, 22 July 2021 at 07:51:04 UTC, seany wrote:

>

OK.
Sorry for the bad question : what if i pregenerate every possible key, and fill the associative array where each such key contains some invalid number, say -1 ?

You mean where each value contains some invalid number, and the AA's keys are never changed during the parallel code? Yeah, that should work.

July 22, 2021

On Thursday, 22 July 2021 at 09:02:56 UTC, jfondren wrote:

>

On Thursday, 22 July 2021 at 07:51:04 UTC, seany wrote:

>

OK.
Sorry for the bad question : what if i pregenerate every possible key, and fill the associative array where each such key contains some invalid number, say -1 ?

You mean where each value contains some invalid number, and the AA's keys are never changed during the parallel code? Yeah, that should work.

Yes, the keys are never changed during the parallel code execution. keys are pre-generated.

« First   ‹ Prev
1 2