No, no formal/full coverage stage done during compilation. Works pretty well though. Try it.

Just had a look a the github documention.

So are are verifying ONLY the code paths / code orders which are triggered by the test input?

Or is there a more formal/full coverage stage done during compilation???

I'm not saying you can't implement fork/join on top of goroutines (you can); I'm only pointing out what happens if you have shared state and you use a goroutine to access that shared state – that you eliminate data races but not race conditions, which is obvious to some but surprising to others.

I am not typically a Go apologist, but I think you've mischaracterized Go's concurrency model. Although it supports nondeterministic concurrency, it also supports deterministic concurrency. Go's synchronization is based on channels, which come in two forms: buffered and unbuffered. Unbuffered channels create a rendezvous point–a write cannot complete until the other end executes a read, and vice versa.

You can do a fork/join in Go by creating an unbuffered channel per goroutine fork. There is no question then which goroutine returned a result. If you spawn a goroutine for each iteration of a loop (the fork), then loop again to read from each channel (the join), you will get the exact same result every time. The order in which the goroutines get scheduled and actually complete may vary, but that will not be observable by your program.

Of course, you would have to do some hacking in the guts of Go in order to use your checking tools with it, but the fork/join model itself is one model that is supported by Go's primitives.

If you're the Uri that I think you are, then you know all of this all too well except for the part where it's a dynamic simple-shaped dependency DAG instead of a static arbitrarily-shaped dependency DAG :) (Which is the more general is hard to tell; qsort is better expressed with this fork/join stuff whereas task parallel graphs are better handled by the arbitrarily shaped graphs. Which is the more gnarly is obvious...)

Amazing staff. Thanks !

It's indeed generic in the sense that you can do a parallel_invoke or some such where you give N different functions instead of having an index running from 0 to N.

It's actually less generic performance-wise if you want what the paper that I cited calls "non-strict fork-join" – that is, code which can wait, not just for stuff it spawned, but for other stuff as well – as you'll be able to do with most task-based fork-join interfaces, and as you won't be able to do with just parallel_for and parallel_invoke.

Why the restriction?

Because (A) I don't believe the difference in performance due to the extra sync options is significant in real life (though I could easily come up with a contrived example where it s); and (B) because it's damn hard to verify generic dependency DAGs compared to the very simple fork-join DAGs – in fact you hit the "NP-hardness" of poset dimension.

I hope to blog about it in detail; it's actually covered not-so-badly in the old post – http://www.yosefk.com/blog/making-data-races-manifest-themselves.html – except that it spells things in terms of some other framework and it's older and I understood less back then (for instance, it says that the trouble with locks is just that you can forget to lock or that you can deadlock; in fact the biggest trouble with locks is stuff along the lines of the maze race example.)

The upshot is that I'm doing generic graphs at work but I don't think the world needs them, really; I might add them to checkedthreads in the future though.

Got it! So that's what you meant with "The upshot is that reordering every pair of independent instructions is trivial with fork/join code and very hard with raw threads.".

Your approach is generic because in this context, fork-join and parallel-for are actually interchangeable, right? A "generic" fork-join could spawn n threads, each doing a different job. The parallel-for would just be a case where n threads are spawned doing the same job, but with different data payloads.

It's true that you could reverse the outer loop(s) but there's still a boatload of orders in which inner loops can run. What the two orders I mentioned are sufficient for is just reordering every pair of independent instructions (that is, every two instructions that could run in parallel). It's a rather weak statement about the order of things – too weak to catch all the bugs in fact as I mentioned, though strong enough to catch them all together with memory interception.

As an example, consider:

i=0 { j=0 j=1 j=2 } i=1 { j=0 j=1 j=2 }

And:

i=1 { j=2 j=1 j=0 } i=0 { j=2 j=1 j=0 }

Where i is the outer index and j is the inner index. Here, if you pick two instructions belonging to two different serial code blocks that could run in parallel, then these two code blocks have now been reversed. But this is not the only way to achieve the effect, nor does it imply anything stronger about the order of things.

First of all, thank you for such good reading material, Yossi! My first visit to this blog was by following a link from Carmack's twitter feed, if I recall correctly. Ended up reading the whole shabang in almost one go!

I was inspired by http://en.wikipedia.org/wiki/Algorithmic_skeleton to write my own APIs for parallel code, and guess what? To date, the most basic one I've written was fork-join. Parallel loops are implemented using that.

I have one or two questions though. I didn't understand very well your example of the nested loops. That only two orderings are necessary. Don't all iterations of each parallel-for run concurrently? So in one run, I might have:

——–> Time
i = 0; i = 1; i = 2;

But another run might be:

——–> Time
i = 1; i = 2; i = 0;

That's different from the strict reverse ordering, right? (2; 1; 0)

Or is it that what actually matters is that, since it's fork-join, the only threads that are actually doing work are always the innermost loops, since all the remaining higher level ones are instead "waiting in parallel"?

Not sure if I rubber-ducked you :P.

Cheers!

CC0 and and especially the very short unlicense – nice stuff. I ain't fiddling with this anymore though... Maybe next time.

What annoys me about these things is that they're a virus; the first thing they require is "redistribute me when you redistribute the code". Oh well...

Yes, unfortunate though it is, you really cannot just say “do whatever you want” if you want to minimise the amount of headaches for everyone else. Sigh.

(I had been using MIT because I was not aware of 2-clause BSD until now. Thanks for finding that.)

There is also the UNLICENSE:

http://unlicense.org/

The popular sqlite database uses something similar to this.

The most permissive license is CC0:
http://creativecommons.org/publicdomain/zero/1.0/legalcode

It's lawyer-approved, and doesn't force the recipient to reproduce the copyright notice in source / binaries and whatnot.

OK; so it's FreeBSD 2-clause license... Argh.

I would, but I'm not sure it will appease the type of lawyer people are worrying about.

I'm shopping for a license now... I really don't want to uglify every file...

Just attach a copy of the WTFPL.

But all those licenses are less permissive than what I'm aiming for, actually; they specifically don't let you do whatever you want to with the code – you're obliged to carry the license with the code and sometimes give credit or whatever. I want it to be like characters that landed magically into your editor/file system – do whatever you want to with them; and I don't want to uglify every file with boilerplate crapola.

Are you seriously saying that I should use an existing license because you'd actually have to convince your company's lawyers? Does it work if the license is in the directory but not in each and every file?

It might be good enough for you, but not for any lawyer I've ever met. :)

Licenses are tricky things and whenever you come up with a new one with subtly different wording, it's likely to result in undefined behavior in some jurisdictions around the world. Just like programmers, lawyers hate undefined behavior.

The MIT license and the new style BSD license give the same effective guarantees that you're aiming for, but it'll also be a hell of a lot easier to convince my company's lawyers that we can use and contribute to software under those licenses.

I say that you're free to do anything you want to at no charge, and without any warranty, in README.md; isn't that good enough?