Deterministic execution

[mpartel]

In some domains, such as games networked with the "lockstep" strategy, it's useful to have a guarantee that a subset of the program has exactly the same outputs and effects on multiple runs and across multiple platforms.

V seems to be quite close to being able to offer this.

Here are things that tend to break this guarantee in other languages, in order of descending error-proneness:

1. Using on object addresses as numerical values (usually as hash keys). This makes hashmap iteration order non-deterministic.
2. Floating point calculations (unless compiled very carefully and probably inefficiently)
3. Concurrency
4. Unsafe code and I/O (ASM, calls to C, syscalls, ...)
5. Stuff V doesn't have: global state and GC finalization order (though I wonder how V frees cyclic things).

I'm making this issue in the hopes that V is developed with the above pitfalls, especially (1), in mind, and to suggest that eventually V (or its linter) could allow opting out of unsafe and non-deterministic features on a per-project or per-module basis.

Related: #3090

[dumblob]

Hm, all the points are definitely wanted and needed in V. Lockstep generally doesn't require these guarantees, but just a small subset in a very specific bounded scenario which can be easily achieved manually.

Much of the stuff in your points can't also be implement efficiently if guaranteed deterministic.

What is the motivation behind this request (besides Lockstep which as I wrote doesn't seem to apply)?

[mpartel]

Hm, all the points are definitely wanted and needed in V. [..]
Much of the stuff in your points can't also be implement efficiently if guaranteed deterministic.

Yes, that's why I suggested banning these features would be optional per-project/module, and perhaps best done in a linter instead of the compiler (unless one wants a "deterministic floats" compiler flag).

Lockstep generally doesn't require these guarantees, but just a small subset in a very specific bounded scenario which can be easily achieved manually.

It's indeed unlikely you'll accidentally misuse 3-5 in lockstep code, but 1 and 2 (especially 1) are easier to forget about, and the resulting bugs can be difficult to reproduce and track down.

What is the motivation behind this request (besides Lockstep which as I wrote doesn't seem to apply)?

The only other problem domain I can think of is replicated or log-structured databases, but there are probably more.

Opting out of dangerous features like this is useful (but non-essential) the same way opt-in mutability is useful (but non-essential). It makes code easier to reason about ("this module is deterministic" is useful documentation) and certain classes of bugs are excluded.

One could argue (as #3090 does) that "pure" functions should ban some or all of these features (with escape hatches).

[dumblob]

The only other problem domain I can think of is replicated or log-structured databases, but there are probably more.

Yeah, sure. But all these use cases are more easily (and transparently) handled explicitly in the code and not by compilation/linter/any_external_pre_or_post_processing. So I'd say having any compiler/linter/... flag (disregarding granularity - i.e. per-module, per-app, per-directory, per-function, per-structure, you name it) is not a good idea.

One could argue (as #3090 does) that "pure" functions should ban some or all of these features (with escape hatches).

I don't think this applies here as there is "pure functions written in the language" (i.e. silently assuming the language itself is pure and then everything on top is function argument) and then "pure functions in general including everything within the language itself" (i.e. counting the language itself to the purity of my function written in the language).

These two worlds get mixed more often than not and I think V targets the first case (i.e. the language itself is not pure, but anything created in/using the language is by default pure).

[mpartel]

But all these use cases are more easily (and transparently) handled explicitly in the code

Sorry I don't follow. What do you mean by "handled explicitly in the code" when it's about avoiding bugs in the code?

I think V targets the first case (i.e. the language itself is not pure, but anything created in/using the language is by default pure).

Yeah, V has opt-out purity, and that's all good. I'm suggesting opt-in determinism, not universal determinism.

Purity and determinism are orthogonal. You can have deterministic functions that mutate their parameters.

It might be nice if "pure" would imply "deterministic", but (as Alex's #3090 (comment) suggests) that might be deemed too restrictive. Hence this suggestion to have separate opt-in determinism checks.

I fully understand that this is a somewhat niche feature that might not be a priority any time soon, or ever.

[dumblob]

But all these use cases are more easily (and transparently) handled explicitly in the code

Sorry I don't follow. What do you mean by "handled explicitly in the code" when it's about avoiding bugs in the code?

Don't use built-in hashmap in the deterministic sections of your code, but use your own (btw. note, that non-deterministic iteration over hashmap is a needed security feature).

Regarding floating-point it's actually non-deterministic in practice (it's only deterministic on the same machine with an identical FPU & software/os initialization including turning off some stuff like "statistical rounding up/down in hardware" - i.e. without any intervention of operating system nor anything else in between) - see related discussion (I have an almost finished comment for that discussion listing some of the non-deterministic behaviors of FPUs and software around - believe me it's impossible to have it guaranteed deterministic in any other case than on same machine with identical initialization).

Concurrency - again, don't use built-ins, but your own deterministic libraries (e.g. no threads, but just CSP-like stuff).

Same holds for unsafe stuff, I/O, RNGs, etc.

Purity and determinism are orthogonal. You can have deterministic functions that mutate their parameters.

Sure, I just reacted to "pure" (not determinism) in that paragraph 😉.

[mpartel]

Ok, makes sense. I think we're mostly on the same page now.

About hashmaps: thanks, I had forgotten about HashDoS. I don't know the subject well, but the creator of that issue suggests insertion order could be safely preserved. There's probably a performance penalty so maybe it's not a good default, depending on V's goals.

About floats: again I don't know the subject very deeply, but I saw that Unity seems to think they can pull it off (though perhaps unsurprisingly, they haven't actually delivered so far). I'd be happy with just an opt-in ban on floats.

Anyway, feel free to close this if you feel this doesn't align with V's goals. Nothing wrong at all with not being interested in a particular niche.

[dumblob]

About floats: again I don't know the subject very deeply, but I saw that Unity seems to think they can pull it off (though perhaps unsurprisingly, they haven't actually delivered so far).

Hm, that's very interesting 😮. I know Unity guys are very smart (definitely much much smarter than me) though I have to admit I simply don't believe them if with determinism they mean "running the same code on any two different available platforms which implement some floating point arithmetic will result in exactly the same output (i.e. running in lockstep)".

Don't get me wrong though - I think with huge tolerances (e.g. several magnitudes at least - on both input & output) for every function Unity provides while at the same time supporting only a modestly narrow carefully chosen subset of existing hardware this could be achievable.

I really need to publish my comment in that thread 😉.

I'd be happy with just an opt-in ban on floats.

That actually doesn't sound that bad to me - how would you envision the granularity? Per-app? Per-module?

[mpartel]

I think systems that need determinism usually need it in at least module-sized portions of the system, so I'd go with per-app/library and/or per-module. You could then have function-granularity or smaller escape hatches like "assume this function is deterministic even though I'm using ".