Here's a quick POC for using atomics. I tested it not at all and it likely has some flaws, but hopefully it illustrates how you can use atomics instead of mutex.
3 Likes
Thanks a lot for your help, I ended up with this trimming function. I learned a lot just from trying to implement trimming in parallel.
1 Like
@quinedot @H2CO3 After implementing my project in both safe and unsafe (with benign race conditions) rust, I created a report where I compare it with the C implementation of the same algorithm. Only the unsafe rust, where I'm doing some pointer arithmetics, was able to compete with the performance of C.
The coloring algorithm for finding Strongly Connected Components presented by this paper has in mind the race conditions that occur but it's structured in a way that they don't affect the result. That's why I wanted to know how to make rust let me have a race condition (which is good that is hard, in case you don't know what you are doing).
Anyway thank you both for your help.
I'm not going to point out all your unidiomatic usage (which resulting slightly long running time) because I'm lazy. But your color_scc_par function has logic error in it. After fixing the logic error, running time of safe implementation is within +10% of unsafe implementation (on wikipedia-20070206). I believe after fixing all unnecessary clone, it would be basically on-par with unsafe implementation.
3 Likes
Thanks for the suggestion, removing the old_colors vector and producing the color_changed flag by reducing in parallel improves the performance a lot. Do you have any other suggestion to make the safe rust implementation go faster? (I don't know a lot of things that you can do with rust, it's only been a week since I started writing)
It's not actually a logic error because the coloring loop will run again if the color_changed flag turned true by any thread. That's why you even get correct result when you intentionally allow a race condition to happen.
See page 5 in the 'Coloring' Section of this paper
We place the parent in the queue to avoid explicit locking.
It is possible that two parents will have higher colors than
a shared child, creating a race condition. Both parents will
once again examine their children in the next iteration to
make sure that either the color that was given by them,
or a higher one, has been placed. Additionally, since only
a higher color can be assigned, we can ignore the race
condition created if a parent has their own color overwritten
before they assign their previous one to the child.
You can't. It's UB. It was UB in C as well, and the paper's authors are simply and plainly wrong in thinking that they can get away with it.
1 Like
Theoretically, they can model their algorithm under a different computation model than C/Rust, where racing write same value is not UB. I didn't read the actual paper, but I guess that's the case, and C implementation just happened to behave correctly.
Maybe it's worth noting that a "race condition" in regard to non-atomics is undefined behavior (UB) (in C and in Rust), and to explain what UB is:
It isn't just a "data race" in regard to the value written or read, but the program can misbehave in any other way (even if it sometimes doesn't and you are "lucky"; but you still must not rely on that, neither in C nor in Rust).
2 Likes
This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.