Fascinating! Glad I’m not a betting person. It depends on what you’re hashing; but this isn’t even guaranteed to be the same between restarts, let alone versions (ref). You could try using an ordered dictionary.
8 Likes
Sounds like your code could try different random partitioning schemes to see which one works best, like a Monte Carlo search.
1 Like
Not so.
You always need to debug.
You refer to:
The hash value may change when a new Julia process is started.
It’s allowed, though I do not see it actually changing across restarts or Julia versions.
I didn’t look into to confirm for Dicts, only the docs:
Dict{K,V}() constructs a hash table
So it’s implied that hash is used and the order could change. Maybe the docs should be explicit on that, and recommend OrderedDict.
You’re assuming what you see if part of the contract, despite the contract telling you that’s not the case, which is a great way to become a victim of the Hyrum’s Law.
6 Likes
No, I’m not assuming, I’m just stating I didn’t see it happening (yet), also I looked at the code, and can’t see it happening (at least for the types, like Int, I checked), I was just implying this isn’t the cause. @jameson I see this maybe has never happened: Make type hashing `:total` by Seelengrab · Pull Request #52427 · JuliaLang/julia · GitHub
I thought the hash of data types could change between runs
That was fixed on master recently, so we should remove that documentation
@Palli, the amount of unsubstantiated conjecture is just out of control. This does happen — and does so with regularity. Those quotes are only about hashing of Types themselves. Here are two really simple objects that show the hash changing between restart and version:
▶ julia +1.10 -E 'hash(Ref(1)), hash(+)'
(0xbdcfb76821d76c23, 0x76519d57b640328b)
▶ julia +1.10 -E 'hash(Ref(1)), hash(+)'
(0xe4446a14eb42a20e, 0x76519d57b640328b)
▶ julia +1.11 -E 'hash(Ref(1)), hash(+)'
(0xc665e625b972c4a7, 0x86bb13ad0fb74bdb)
▶ julia +1.11 -E 'hash(Ref(1)), hash(+)'
(0xe122b7a2ac285a53, 0x86bb13ad0fb74bdb)
9 Likes
If this was a case of hashing different across restarts, then @PetrKryslUCSD would likely have hit the bug already in the older version?! I’m only trying to help here (as always), I can easily just stop doing that, maybe I will, or let it be up to him.
I never said hashing would for sure be stable, let alone for pointers, that would of course never happen i.e. for different pointers, as you showed. [I don’t think hash(+) is showing anything very meaningful.]
I recently switched from Python 2.7 to Python 3.3, and it seems that while in Python 2 the ordering of dictionary keys was arbitrary but consistent
What we apparently need is more randomization (and a way to turn it off), like in Python:
-R
Turn on hash randomization. This option only has an effect if the
PYTHONHASHSEEDenvironment variable is set to0, since hash randomization is enabled by default.
[…]Hash randomization is intended to provide protection against a denial-of-service caused by carefully chosen inputs that exploit the worst case performance of a dict construction, O(n^2) complexity. See oCERT archive for details.
[Note, Python has changed to ordered dicts by default, what I’ve also proposed as a default for Julia… so then there’s no randomization in order. I assume O(n^2) denial-of-service attack still not possible.]
The point is that hash can change, so dict orderings can change. It can change between restarts and/or it can change between versions. It can also not change. If you don’t find the hash(+) example compelling, you can try hash(Some(1)).
An open issue suggesting Julia use hash randomization is julia#37166.
2 Likes
Isn’t it conceivable that different LLVM versions (15 in 1.10.7, 16 in 1.11.2) can be responsible for subtle differences in optimization of floating point operations?
We don’t let LLVM change floating point results unless the user explicitly gives permission (e.g. via @fastmath/@simd/muladd).
5 Likes
Random number generation is not guaranteed to be identical between different Julia versions; that would effectively stop any improvements from happening in that area. This is documented at Random Numbers · The Julia Language :
Warning
Because the precise way in which random numbers are generated is considered an implementation detail, bug fixes and speed improvements may change the stream of numbers that are generated after a version change. Relying on a specific seed or generated stream of numbers during unit testing is thus discouraged - consider testing properties of the methods in question instead.
If you want to have fixed random number sequences in your tests you should use a generator from the StableRNGs package and set a fixed seed.
10 Likes
Right because, you will get a random seed in Julia for the default RNG when starting, and thus a different sequence.
That said, I doubt this alone is the reason for your changed result, because shouldn’t you then have gotten it on 1.10.5 too, after a few resets? This might be part of the reason explaining 1.11 change.
If you want to keep this [EDIT: rand in at least single-threaded] constant [but NOT shuffle, so it might be your problem in 1.11] you can do:
using Random; Random.seed!(1234);
julia> rand() # now reproducable across 1.10 and 1.11, and down to only 1.7:
0.32597672886359486
The currently used RNG, that I proposed adopting (at the time, now also in the current LTS, not the old one), and was adopted in 1.7, could of course be changed again later, so don’t rely on it not changing. But for a quick test might be helpful for you. I’m not actually sure what happens with many threads, then they will get different streams usually, and probably still with my suggestion, so also run with just one thread.
I realized even Libc.malloc, because of e.g. glibc, uses random, and it’s used for huge allocations, to get then random locations for them in memory. Julia takes over for smaller allocations, then doesn’t call malloc for each one, but would still be affected, since Julia needed malloc to initialize memory pools. The location of allocations doesn’t matter in any sense for correctness (usually… unless your code is sensitive to the locations or hashing of them), but yes, it affects hashing of pointers, and Ref then as @mbauman showed. It’s probably very hard to get allocations deterministic (from within Julia), since Julia relies on glibc, that does the randomization. I don’t think C has an API to allow bypassing it, since this is a security feature.
But you could try:
If the variation is caused by address space layout randomization, then, according to this page, you can disable it with:
echo 0 | sudo tee /proc/sys/kernel/randomize_va_spaceThis should be done only temporarily for debugging purposes.
@Palli, no. None of that is relevant and again there are a number of inaccuracies.
Even with seeding, even if the RNG itself didn’t substantively change, the ways in which Random uses the RNG may change. I’m guessing it may be this change — or if not, it’s something of the same category:
▶ julia +1.10 -E 'using Random; Random.seed!(0); shuffle(1:4)'
[2, 4, 1, 3]
▶ julia +1.11 -E 'using Random; Random.seed!(0); shuffle(1:4)'
[4, 1, 3, 2]
7 Likes
I tracked down to seemingly this change (for shuffle at least):
It’s apparently very hard to get all randomization effects to be the same. All code depending on rand or similar needs to be the same, which it isn’t across versions (nor guaranteed to be).
You can try restoring the old shuffle in 1.11, from 1.10:
import Random.shuffle!
function shuffle!(r::AbstractRNG, a::AbstractArray) # I only added needed Base.
Base.require_one_based_indexing(a)
n = length(a)
n <= 1 && return a # nextpow below won't work with n == 0
@assert n <= Int64(2)^52
mask = nextpow(2, n) - 1
for i = n:-1:2
(mask >> 1) == i && (mask >>= 1)
j = 1 + rand(r, Base.ltm52(i, mask))
a[i], a[j] = a[j], a[i]
end
return a
end
I can’t guarantee that’s the only change in 1.11 affecting your code…
julia/stdlib/Random/src/Random.jl at v1.11.2 · JuliaLang/julia · GitHub is a stdlib, is it upgradable? I.e. can you use Random from 1.11 in 1.10? And vice versa?
Isn’t it easier to detect sensitivity to RNG by just reseeding the working old version with several different seeds and looking at the effect?
My guess the randomization is not the critical difference. It may be exposing a Heisenbug (Heisenbug - Wikipedia) somewhere else e.g. rounding error picking different branch in some conditional, like 0.999999 not being >=1. If the bad behaviour is consistently repeatable, then the bug should be defeatable.
Randomness tracked down to the Metis graph partitioning library.
12 Likes