3 ms·

>In a fork/join program, you need just two orders: run all loops from 0 to N. run them all backwards, from N to 0. Does this hold for the following code: for

by zeteo 14y ago

>In a fork/join program, you need just two orders: run all loops from 0 to N. run them all backwards, from N to 0. Does this hold for the following code: for (j = 0; j < 3; j++) a = j % 2; In both forward (0, 1, 2) and backward (2, 1, 0) order, the final value of a is 0. But with the j==1 loop running last, a becomes 1 instead.

_yosefk 14y ago
Depending on how you look at it :) * It does work in the sense of reordering every pair of instructions that could ever run in parallel. * It doesn't work in the sense that results aren't changed; this is true for a lot of more likely programs - for instance, a+=arr[j], and many others. Reordering every pair of independent instructions doesn't guarantee that you'll find all the races; that's why checkedthreads has the Valgrind tool. It does find a whole lot of bugs very quickly, and it's also needed for the Valgrind tool to actually cover all the races - but it's not sufficient by itself. To find all the bugs using just event reordering, you'd need to try something closer to all possible way to interleave independent instructions and that's a boatload of orders...
- zeteo 14y ago
  More generally the issue seems to be that if two different loop counter values j1 and j2 write the same thing to shared memory, then all the writes made by values between j1 and j2 are masked from this kind of testing. This seems like a potentially common case, especially with long loops and / or few possible values to write (e.g. booleans).
  - _yosefk 14y ago
    Well, yeah. The reason such reordering is worth mentioning is because it's necessary for instrumentation to do its thing, and because in practice, we've found that this finds a load of bugs by itself; which is good because instrumentation is slow. (A compiler pass could be better than runtime instrumentation perhaps, but then you'd have problems with bugs involving compiled libraries.) You can, of course, run with more schedules (checkedthreads lets you do this using env CT_SCHED=shuffle CT_RAND_SEED=654 or some other number) and then more bugs would be found, but you quickly reach diminishing returns compared to just running instrumentation (especially because a lot of bugs are not found by such coarse-grain reordering at all, for example, anything involving accumulators, counters, thread-unsafe allocators, the settings of bits in bit masks, etc.)

by zeteo 14y ago

_yosefk 14y ago

Depending on how you look at it :) * It does work in the sense of reordering every pair of instructions that could ever run in parallel. * It doesn't work in the sense that results aren't changed; this is true for a lot of more likely programs - for instance, a+=arr[j], and many others. Reordering every pair of independent instructions doesn't guarantee that you'll find all the races; that's why checkedthreads has the Valgrind tool. It does find a whole lot of bugs very quickly, and it's also needed for the Valgrind tool to actually cover all the races - but it's not sufficient by itself. To find all the bugs using just event reordering, you'd need to try something closer to all possible way to interleave independent instructions and that's a boatload of orders...

zeteo 14y ago
More generally the issue seems to be that if two different loop counter values j1 and j2 write the same thing to shared memory, then all the writes made by values between j1 and j2 are masked from this kind of testing. This seems like a potentially common case, especially with long loops and / or few possible values to write (e.g. booleans).
- _yosefk 14y ago
  Well, yeah. The reason such reordering is worth mentioning is because it's necessary for instrumentation to do its thing, and because in practice, we've found that this finds a load of bugs by itself; which is good because instrumentation is slow. (A compiler pass could be better than runtime instrumentation perhaps, but then you'd have problems with bugs involving compiled libraries.) You can, of course, run with more schedules (checkedthreads lets you do this using env CT_SCHED=shuffle CT_RAND_SEED=654 or some other number) and then more bugs would be found, but you quickly reach diminishing returns compared to just running instrumentation (especially because a lot of bugs are not found by such coarse-grain reordering at all, for example, anything involving accumulators, counters, thread-unsafe allocators, the settings of bits in bit masks, etc.)