freenode/#clasp - IRC Chatlog
Search
22:20:32
drmeister
But say I expose an accessor to read an objects badge. I should be able to startup and read the badge of an arbitrary object in a script and get the same value every time.
22:21:19
Bike
yeah, i guess if the pointer isn't a factor in any case then hash tables ought to be deterministic...
22:22:48
drmeister
If running through Minecraft procedurally generated terrain for hundreds of hours has taught me anything - its that deterministic programs are deterministic.
22:23:27
Bike
you know i consulted my gamer pals about that and they weren't sure if minecraft is actually deterministic in the way you described
22:24:57
drmeister
Your gamer pals should try repeatedly generating a world off of one seed and then run in one direction for as long as they can stand it - it's the same terrain every time.
22:26:33
drmeister
I use the "Schafmeister" seed in the latest Minecraft - you start out facing a stone wall on a rocky outcrop surrounded on three sides by dense forest. There is small, stupid village to the northeast.
22:29:59
Bike
i thought what you meant was that if you took different paths each time but ended up at the same spot, the end point would still look the same
22:36:34
Bike
since the chunks would be generated in different orders, if generating a chunk advances the PRNG it would change
23:12:57
drmeister
I can't find my stupid village when I run off in one direction and then double back and look for the village in the other.
23:14:33
drmeister
For those of you watching from home. I've been talking with Bike about procedural generation of pseudo-random sequences of spiroligomers where I can alter parameters and regenerate the same sequences by seeding the RNG with the same seed.
23:15:25
drmeister
I drew an analogy to Minecraft where the world is procedurally generated and I thought it generated the same world every time by very clever programming. I may have been wrong about how clever Minecraft procedural world generation is.
23:17:30
drmeister
This seems to indicate the world is always the same based on the seed: https://minecraft.gamepedia.com/Seed_(level_generation)
23:19:22
drmeister
Hmm, Minecraft natural philosophers have different opinions. This may require more careful experimentation.
23:20:34
drmeister
Minecraft philosophers discussing the issue https://usercontent.irccloud-cdn.com/file/J5I4aMsb/image.png
23:39:42
drmeister
It may be generating the same sequence. But there may be an indeterminate number of invocations by the time it evaluates the command line argument.
23:40:34
Bike
well, then we just have some other source of indeterminancy, not that i can guess what it is
23:42:06
Bike
i mean, i would expect the same kinds of objects are made in the same order, ceteris paribus
23:45:40
karlosz
if we can stamp out enough determinism so that things like hash tables are guaranteed to work the same we'd at least know there isn't a codegen problem
23:49:30
drmeister
Guys, I was feeling good about it and then I look at the buildbot and it crashed again.
23:50:54
drmeister
I'll keep pushing rebuild - but it appears that there is an intermittent problem.
1:36:41
drmeister
I've turned on the DEBUG_MODULE_VERIFY flag and I'm building on the buildbot repeatedly.
5:42:07
drmeister
Because I've got an idea of how to figure out if it's their behavior that is the problem.
5:50:14
karlosz
cleavir-bir:instruction , cleavir-bir:datum *should* be everything stuffed in those sets
6:09:23
drmeister
I was doing an experiment. Minecraft does generate the same world no matter what direction you go when you start from the same seed.
6:14:01
drmeister
What I'd like to do is get the set hash table to hash contents using a separate pseudo random number generator.
6:15:25
drmeister
One that is dedicated only to the objects that we put in the set. It should be straightforward because we use the 'badge' slot in every object. We can set the badge for objects that are put into the sets using a custom pseudo-random number generator and the hash table will use that in the hash function.
6:16:07
drmeister
Then we set up bigmac to build all of the quicklisp using the serial compiler repeatedly with different seeds.
6:17:28
drmeister
I can have quicklisp build into different cache directories by setting XDG_CACHE_HOME
6:18:58
drmeister
All I need is to expose a function to write into the badge and we can put whatever we want in there - it will be used for hashing.
6:39:20
karlosz
drmeister: if we can ensure the serial compiler can behave deterministically with a given seed it should work okay
6:41:04
drmeister
Are by any chance, objects only added to each set once through make-set and adjoin? If not we would have to set the badge when the objects are created.
6:44:00
karlosz
what happens is that (setf (gethash ...)) can get called more than once with the same key
6:45:25
drmeister
That's not a problem. We just need to ensure that every objects badge is set only once. It would be best if we did that when objects that go into the sets are created.
6:47:32
drmeister
We can ensure that badges are initialized properly by using a few bits of the badge as a unique tag.
7:21:28
drmeister
So - we can set the badge of objects now. This is used by the hash function so we can make hash-tables deterministic now.
7:22:08
drmeister
If you set the badge to a constant - like 0 - then it turns into a complicated list-like object.
7:30:59
drmeister
::notify Bike I added a core:set-badge and core:get-badge pair of accessors. They set and get the badge of heap allocated objects. If you set the badge of an object right after it is created the badge will be used to hash the object in any hash-tables you add it to. This will let us make hash-tables deterministic.
7:40:23
drmeister
::notify Bike I'm setting up a test where the quicklisp code is compiled in 10 threads 100x each with compile-file-serial to see if I can reproduce the problem under these conditions. If it does - with core:set-badge we should be able to make the sets deterministic and controlled by a seed and then find a seed that causes the build to crash reproducibly.
7:41:37
drmeister
I have ideas how we can make it deterministic even if it's a compile-file-parallel problem.
7:51:21
drmeister
::notify Bike Minecraft does build the same world - no matter what order chunks are created. I tested it again more carefully tonight. Also - I found a cool place to build a base! Bonus!
8:16:57
no-defun-allowed
Fun fact: Minecraft generates the same bedrock pattern regardless of world seed.