Hi – I can’t seem to find the answer in the docs or on Discourse (apologies if I searched badly).
To be specific: suppose the first call to a function happens more than once (say in different Julia working sessions, but on the same machine with the same Julia versions). Does Julia’s design specify or imply that the resulting machine codes are identical?
I strongly feel the answer is ‘yes’ but I can’t see how to be sure of it.
it doesn’t always, but does usually. I think the llvm side is deterministic, but type inferance can depend on the order of definitions.
I know you’re trying to fix the circumstances across different Julia sessions, but there are still circumstances that can change given what you specified. For example, const timestamp = time_ns(); foo() = timestamp has different native code depending on when it was evaluated. This is usually a bad idea, though.
Assuming you’re talking about identical instructions and static data instead of metadata, I haven’t seen a formal determinism guarantee on any level, but it’s considered undesirable in the few examples I’ve seen where compilation was affected by evaluation history leading to otherwise equivalent global states. The language itself is free to be implemented however e.g. no compiler, tiered JIT, though I haven’t seen any alternative compilers embrace non-determinism.
The answer is a resounding “NO”, on a lot of levels.
“Reproducible builds” is a major undertaking. Apart from “explicit non-reproducible” things like the example by @Benny , you have races, and you always have fun situations where you iterate over a Dict or Set, and the output order depends on hashes which depend on addresses of heap-allocated objects, which depends on pretty random libc-internal state.
A lesser requirement would be: “replays in RR”. I think we have that, yay!
Now, your “same function, different session” requirement would be even stronger. Let me give a small counter-example (run each in a fresh session):
julia> t1 = NTuple{3,Union{Int,Missing}}; t2 = Union{Tuple{Missing,Missing,Missing}, Tuple{Missing,Missing,Int}, Tuple{Missing,Int,Missing}, Tuple{Missing,Int,Int}, Tuple{Int,Missing,Missing}, Tuple{Int,Missing,Int},Tuple{Int,Int,Missing}, Tuple{Int,Int,Int}};
a=Vector{t2}(undef, 1); b= Vector{t1}(undef, 1);@show t1==t2 sizeof(a) sizeof(b);
t1 == t2 = true
sizeof(a) = 24
sizeof(b) = 24
julia> t1 = NTuple{3,Union{Int,Missing}}; t2 = Union{Tuple{Missing,Missing,Missing}, Tuple{Missing,Missing,Int}, Tuple{Missing,Int,Missing}, Tuple{Missing,Int,Int}, Tuple{Int,Missing,Missing}, Tuple{Int,Missing,Int},Tuple{Int,Int,Missing}, Tuple{Int,Int,Int}};
a=Vector{t1}(undef, 1); b= Vector{t2}(undef, 1);@show t1==t2 sizeof(a) sizeof(b);
t1 == t2 = true
sizeof(a) = 8
sizeof(b) = 8
The reason for this is that the data-layout of types is not well-defined modulo == that is independent of “julia session”. Julia can check equality of types (more or less: Types can be equal, non-equal or “type-checker does not halt”), but cannot create a reproducible canonical representation of types. Instead, the first encountered representation of a type becomes “canonical for this session”, and different representations that are encountered later get mapped to that.
You see that not even the memory layout, let alone the code, is “strongly reproducible” in the sense you want. It depends on compilation order / encounter / import order.
Just to elaborate on the order-dependent type layout, the equal t1 and t2 are (abstract) supertypes of exactly 8 concrete 24-byte Tuple types. The difference is that t1 is a direct Tuple type with 3 Union elements, while t2 is a Union of the 8 Tuple types. Abstract types don’t have direct instances for which to prescribe a memory layout, but Vectors with them as element types are concrete. Most abstract types would make the elements’ data stored separately, with the Vector’s buffer storing only pointers to them (8 bytes on 64-bit systems). Unions of a limited number of isbits types however can be optimized as storing the data directly in the Memory buffer, followed by a sequence of type tags to distinguish the elements’ concrete types.
Julia decided to use the optimization if the type Vector{t2} is made first and let the equal Vector{t1} follow suit, but not in the reverse order. The implementations are observably different, but the point is they’re both correct for programs that reached nearly equivalent global states (you could get closer by swapping a and b in the 1st case for a consistent a::Vector{t1} and b::Vector{t2}). People have complained that Julia would ideally figure out the optimization is possible in either order, but types aren’t as obvious as t1 in general. It’s bad for optimizers to run a long time, possibly forever, so heuristics save time and can be order-dependent. Order-dependent effects could often be eliminated by strengthening the circumstances to the exact same source code, but conditionals and parallelism can still vary evaluation order. Introducing time-dependence to a unified t1 vs t2 example (again, bad idea in practice):
t1 = NTuple{3,Union{Int,Missing}}
t2 = Union{Tuple{Missing,Missing,Missing},
Tuple{Missing,Missing,Int},
Tuple{Missing,Int,Missing},
Tuple{Missing,Int,Int},
Tuple{Int,Missing,Missing},
Tuple{Int,Missing,Int},
Tuple{Int,Int,Missing},
Tuple{Int,Int,Int}}
# system clock seconds determines order of evaluating Vector types
if iseven(round(Int, time()))
Vector{t1}, Vector{t2}
else
Vector{t2}, Vector{t1}
end
# order of Vector instantiation doesn't matter here
a = Vector{t1}(undef, 1)
b = Vector{t2}(undef, 1)
@show Vector{t1}==Vector{t2} sizeof(a) sizeof(b)
and a flattened CLI expression for convenient repetition across different processes:
julia -e "t1 = NTuple{3,Union{Int,Missing}}; t2 = Union{Tuple{Missing,Missing,Missing},Tuple{Missing,Missing,Int}, Tuple{Missing,Int,Missing}, Tuple{Missing,Int,Int}, Tuple{Int,Missing,Missing}, Tuple{Int,Missing,Int}, Tuple{Int,Int,Missing}, Tuple{Int,Int,Int}}; if iseven(round(Int,time())); Vector{t1}, Vector{t2}; else; Vector{t2}, Vector{t1}; end; a= Vector{t1}(undef, 1); b= Vector{t2}(undef, 1); @show Vector{t1}==Vector{t2} sizeof(a) sizeof(b)"
As for strengthening the circumstances to the exact same evaluation order of Julia objects, I don’t recall and can’t imagine an example where the instructions and static data can vary. It’s possible that it really doesn’t for us, but I have read about exotic pseudorandom heuristics, which get random seeds from the system like the time-dependent examples here getting system times.
I do have a question on my mind now though: if 2+ packages are precompiled with different representations and code for Vector{t1}, how are they reconciled in the same environment or when I import them into the same session?
This is an excellent question. I thought that this would obviously cause invalidations and depend on the load order in some inscrutable way.
So I tried it out. Follow along 5. Creating Packages · Pkg.jl with (@v1.12) pkg> generate pkgA. Go to folder,
pkgA]$ git commit -m "."
[master (root-commit) e087f05] .
2 files changed, 13 insertions(+)
create mode 100644 Project.toml
create mode 100644 src/pkgA.jl
pkgA]$ cat src/pkgA.jl
module pkgA
greet() = print("Hello World!")
T = NTuple{3, Union{Missing,Int}}
const a = T[(1,2,3)]
f(x::Vector{T}) = x[1]
const b = f(a)
const sz = sizeof(a)
end # module pkgA
Then git init ., git add Project.toml src/ andgit commit -m “init”`.
Set up a second pkgB, with
pkgB]$ cat src/pkgB.jl
module pkgB
greet() = print("Hello World!")
T = Union{Tuple{Missing,Missing,Missing},
Tuple{Missing,Missing,Int},
Tuple{Missing,Int,Missing},
Tuple{Missing,Int,Int},
Tuple{Int,Missing,Missing},
Tuple{Int,Missing,Int},
Tuple{Int,Int,Missing},
Tuple{Int,Int,Int}}
const a = T[(1,2,3)]
f(x::Vector{T}) = x[1]
const b = f(a)
const sz = sizeof(a)
end # module pkgB
Now the moment of truth:
(@v1.12) pkg> add ~/div/pkgA
(@v1.12) pkg> add ~/div/pkgB
julia> import pkgA, pkgB
julia> pkgA.sz, pkgB.sz
(8, 24)
julia> pkgA.a == pkgB.a
Unreachable reached at 0x7fbdea047a61
[610694] signal 4 (2): Illegal instruction
...
Oops!
Thanks! Very insightful, if a little disconcerting to some-one who now thinks their question a little naive …
Still, it is better to know one more reason not to rely blindly on code, however good you think it is!