Hello Val, Thanks for your thoughts.
Indeed, for single user goroutine, I think your list is more or less ok. I can reliably reproduce single goroutine performance results in my code and it is in line with your list. (rand.Seed is not necessary b/c there is a default seed of 1). There was a famous issue with floats in minisat and heuristics, so indeed that can be an issue. In practice, using 64 bit floats gave sufficient precision to make the heuristics well defined, and that is accepted as sufficiently deterministic for the sat competition, even though theoretically there could be some non-determinism. Some even made their own floating point values and operations in C structs to make it theoretically deterministic. For concurrent programs, obviously the program needs to be race-free -- no reads of data that could hold different values based on grouting scheduling of writes (using happens-before). There are also as Ergon noted OS level effects, but they are in practice mitigated for things like the sat competition where the entire OS and hardware is dedicated to a given program, and so the OS will likely schedule threads the same way every time, as they program makes exactly the same requests to the OS every time. I would also note that usage of a channel which has more than one receiver goroutine or more than one sender goroutine at any time will introduce non-determinism. It is not clear to me what is a legitimate "side effect" in your list. What is the difference between a side-effect and whether the program will generate the same output in all schedulings? What if select choice order or channel operation orderings have only performance impact and no side effects w.r.t. correctness, race-freeness, or output of the program? I would like to be able to reliably reproduce that. They are interesting constructs and it would be simpler to have 1 way of determinising their behaviour at runtime than to re-engineer, often without them, for every occasion that needs reproducibility. Scott 2016-07-17 21:25 GMT+02:00 Val <delepl...@gmail.com>: > Hello Scott > Determinism for runtime, not just builds, looks like a nice feature to > have for some problems including yours. > Sadly I don't have the solution, but it would be great to make 2 lists of > how to achieve deterministic/reproducible executions in go : > > *Sequential programs* (only 1 user goroutine) > - Use rand.Seed to tame random generators ... quite obviously. > - Not iterate on map, when iteration order has side effects. Consider > using a temporary slice to force known iteration order of the map contents. > - Not use time.Now() > - Not allow any external input (FS, network, etc.) to vary from run to > run. Reading a file is ok, if unchanged. > - Not rely on exact results of floating-points calculations (they may or > may not be deterministic, I'm not an expert on that topic but I suspect > something) > - other? > > *Concurrent programs* (multiple goroutines) > - All of the above > - Never let any event A have side effects on any instruction B, unless the > relation "A happens-before B <https://golang.org/ref/mem#tmp_2>" is > reliably proven. This looks tough and restrictive, but if you don't have it > it's easy to think of a "1s vs. 1 month" perf loss. E.g. when A is used to > cut (prune) a big calculation tree B, but A happens "sometimes after" B has > already started. In practice, I would recommend independent tasks meeting > at rendez-vous points, using WaitGroups as Egon suggested. > - Not use select{}, unless it is reliably proven that the choice order has > no side effects. > - other? > > It's an open question for me, please share your ideas! > Cheers > Val > > On Sunday, July 17, 2016 at 6:25:32 PM UTC+2, Scott Cotton wrote: >> >> Hi, >> >> I'm well aware of the benefits of non-deterministic select for many use >> cases, I don't contest that at all or the decision to have it part of >> golang. >> >> A clear and concrete problem is the following: The sat solver >> competition at satcompetition.org requires >> deterministic solvers for reproducible results. Suppose I have a >> select{...} in a go program which solves sat, >> and I want to enter it in the contest. I can't. Also, others can't >> reproduce the results. Also, the problem is hard >> and very heuristic so minor variations can cause huge differences in >> runtime (like 1s vs. 1 month). >> >> A concurrent algorithm for SAT can be interesting and maybe even give on >> average good results. But the entire thing will be rejected by the >> scientific community on the grounds that they can't reliably reproduce >> results. >> >> Best >> Scott >> >> >> >> 2016-07-17 18:12 GMT+02:00 Jesper Louis Andersen <jesper.lou...@gmail.com >> >: >> >>> >>> On Sun, Jul 17, 2016 at 6:05 PM, Scott Cotton <w...@iri-labs.com> wrote: >>> >>>> I'm looking for information/pointers for making the scheduling and >>>> select {} choices determinisable for an application domain in which >>>> non-determinism in scheduling/select causes problems. >>>> >>> >>> Out of curiosity, what is that domain? >>> >>> The reason I'm asking is that the non-deterministic select is put into >>> place in order to prevent starvation and also to prevent programmers on >>> relying on a specific order. The hope is that a concurrency error will >>> uncover itself while the system is running because the odd schedule is >>> likely to occur if at all possible. >>> >>> Also, in most concurrency systems, you have the opposite situation: the >>> system has determinism. The lamented sigh here is that you often want some >>> kind of fairness among processes to make sure you avoid starvation. >>> >>> There may be good subtle reasons for your domain, which is why I'm >>> asking what the problem is. >>> >>> -- >>> J. >>> >> >> >> >> -- >> Scott Cotton >> President, IRI France SAS >> http://www.iri-labs.com >> >> >> -- Scott Cotton President, IRI France SAS http://www.iri-labs.com -- You received this message because you are subscribed to the Google Groups "golang-nuts" group. To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
