freenode/#clasp - IRC Chatlog
Search
18:09:06
drmeister
I've seen it crash twice now - once a few days ago - but it was a confusing build for a couple of reasons.
18:10:44
drmeister
Then just now the buildbot crashed in iterate. I've learned to read the tea leaves and escalate it as a potential problem.
18:13:13
drmeister
It failed on the buildbot at 1:01 - so it will be an hour before I can report back on that.
18:23:44
Bike
might help to make cleavir use the list implementation of sets instead of hashes... hashes cause the indeterminancy and i'm not even sure it goes faster
19:54:14
karlosz
i'm going to look at metaevaluation again tomorrow (i.e. the "s-expression" simplifier)
19:56:19
karlosz
so we can just make that bottom up and use a worklist; i just want to be able to query (foldablep ...) and then do (funcall (foldable-function <name>) <constant-args>)
19:56:47
karlosz
my intuition is that just doing basic stuff like the arithmetic operators and the list operators will actually give measurable gains
19:58:19
karlosz
simplification on the expression tree are easily made into simplifications of the flow graph if you just turn the algorithm "inside out"
19:58:49
karlosz
so if you look at how Python does "local type propagation" it matches how you'd do it on the expression tree
19:59:30
karlosz
(abstract-type '(if <e> <f> <g>)) = (union-type (abstract-type <f>) (abstract-type <g>))
20:00:13
karlosz
so then the Python local type prop algorithm is part of the "metaevaluator" (ir1opt) which is just the corresponding flow graph algorithm to that expression tree algorithm
20:00:57
karlosz
that's why they do type propagation and constant propagation and all that stuff at the same time, because you can group those all into one "graph walk" (corresponding to the tree walk you'd do)
20:01:47
karlosz
another name for this (which i think guile and some other scheme implementations call it) is "partial evaluation"
20:02:05
karlosz
basically just as if you were interpreting a sexp but you didn't have access to the concrete values, only the abstract ones
20:03:10
karlosz
so yeah i'm just imagining one BIR pass called metaevaluation which does all the partial evaluator algorithms you'd expect on an expression tree
20:04:16
karlosz
a backward flow algorithm (like deleting unused expressions/computations) corresponds to partial evaluating the tree top down to find those useless things
20:04:37
karlosz
anyway, i'll try and tackle constant folding tomorrow so i guess i'll just add a foldable attribute to the stuff in setup.lisp
20:08:40
drmeister
So there may still be an intermittent problem with the BIR compiler. The buildbot worked when I restarted it.
20:11:40
drmeister
What kind of keys do you use for the compiler hash-tables that may be causing the problem here?
20:14:20
drmeister
Or how about this? Add the list implementation under control of a debug flag and set things up so that they both get used and we test the hash-table result against the list result?
20:17:03
Bike
the impelmentation choice is pretty nearly a debug flag already, could just be a feature to specify
20:27:48
Bike
https://github.com/s-expressionists/Cleavir/blob/master/Set/set.lisp#L3-L4 just gotta flip this
20:31:12
drmeister
The problem with flipping it is that if it fails rarely with :hashset and fails never with :listset - we still don't have a smoking gun. If you add :hashset-listset-match and use them both side-by-side and constantly cross check the result that you get out of both of them. If there is a mismatch - then we have a smoking gun.
20:32:01
Bike
we can't compare them within the set code itself, because we expect iterations to occur in different orders
20:35:24
drmeister
What is the most likely problem? Can different order of iteration lead to a problem? Or does it need to be something more serious - like pairs in the data structure not coming up in the iteration?
21:09:08
drmeister
Right - you could iterate through both objects and cross check each pair against the other object.
21:10:28
drmeister
Like (mapset (lambda (key value) ...) set-object) and set-object contains a hashset and a listset and first you iterate over one of them and check it against the other and then iterate over the second object and do the same?
21:58:17
Bike
might still not work, we can have dosets that return early, and with different iteration orders that could mean elements being iterated over in one and notht eother
22:02:47
drmeister
Why do you guys zero in on hash-tables and order of traversal right away when we talk about a potential intermittent problem?
22:03:28
drmeister
I'm not accusing - I'm just trying to understand why you think it's an obvious source of compiler bugs.
22:15:54
Bike
i don't remember how the badges work. is the prng state the same every time the image starts?
22:19:05
drmeister
I've built :iterate 9 times now - no problems. Restarting icando-boehm each time.
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