I determined this morning that the cause was a bad hash code for my generic hashes/sets. I use an injection from the value space into the natural numbers by assigning atoms prime numbers (thanks math/number-theory for next-prime!), and I multiply them together to produce the encoding of sets (I check divisibility before multiplying, so I always have a <=1 multiplicity). I use Cantor's injection for producing the number of pairs, so I can make a set of pairs encode finite functions (hashes). The result should be that equal numbers imply equal values, so I hashed on the numbers for hash-proc and hash2-proc instead of the values. I still compare equality only using the numbers since it's 3 orders of magnitude faster. I changed the hash-proc to hash on the values instead and got consistent results for the analysis. I'm perplexed by this, so I'm trying to write a smaller example that demonstrates the problem.
I only use hasheq for seen checks when traversing through a hash that has circular references, and I never change the hash during these traversals, and the result is a set. The order doesn't matter. I also changed all hasheqs in my code to hashes to see if that was a problem. It wasn't. -Ian ----- Original Message ----- From: "Carl Eastlund" <c...@ccs.neu.edu> To: "J. Ian Johnson" <i...@ccs.neu.edu> Cc: "Matthew Flatt" <mfl...@cs.utah.edu>, "dev" <dev@racket-lang.org> Sent: Wednesday, August 28, 2013 12:34:08 PM GMT -05:00 US/Canada Eastern Subject: Re: [racket-dev] Output value of program changes depending on whether I pretty-print an opaque struct value Is it possible your analysis is depending on the order of graph traversal? That is, do you ever use in-hash on the hasheq, and if so is it possible the results of your analysis would change if in-hash produced hash table entries in a different order? Same for in-hash-keys or in-hash-values, obviously. Carl Eastlund On Tue, Aug 27, 2013 at 6:58 PM, J. Ian Johnson < i...@ccs.neu.edu > wrote: Weird you can't repro. I only use hasheq when I know the keys are symbols, or the table is local and only used for a graph traversal (where the graph is not changing during traversal). -Ian ----- Original Message ----- From: "Matthew Flatt" < mfl...@cs.utah.edu > To: "J. Ian Johnson" < i...@ccs.neu.edu > Cc: "dev" < dev@racket-lang.org > Sent: Tuesday, August 27, 2013 6:33:02 PM GMT -05:00 US/Canada Eastern Subject: Re: [racket-dev] Output value of program changes depending on whether I pretty-print an opaque struct value I haven't been able to get a different result by changing printing. One thing that printing might do, however, is assign `eq?`-based hash codes to objects that did not already have them. That assignment, in turn, could affect the order in which objects appear later in a hash table. I hacked Racket to make the internal hash-code generator count down instead of up, and I was able to get a different result that way. Are you using `eq?`-based hashing at all? Could there be some dependency on the order of values within a hash table (or hash set)? At Tue, 27 Aug 2013 14:02:50 -0400 (EDT), "J. Ian Johnson" wrote: > This is mostly an mflatt-only problem. > > My analysis framework is now using a generic dictionary for its abstract > heap, > and depending on whether or not I pretty-print this heap before continuing on > analyzing, the result of the analysis changes (sound versus unsound). I found > the problem doing some printf debugging, and when fixed, I tried removing the > print statements. The answer changed. There must be some problem in the C > code > somewhere, because this is just bonkers. > > (Note: I've had previous bugs where rewriting a (begin (void) e) => e caused > a > similar value-changing bug. Updating the compiler to head fixed it at that > point. I'm running yesterday's HEAD now, though.) > > https://github.com/dvanhorn/oaam/tree/thocon > > See the ;; mflatt: comment in code/kcfa.rkt > > To see the problem, > racket code/run-benchmark.rkt --lcg benchmarks/temp-c/sort2.sch > > Thanks, > -Ian > _________________________ > Racket Developers list: > http://lists.racket-lang.org/dev _________________________ Racket Developers list: http://lists.racket-lang.org/dev _________________________ Racket Developers list: http://lists.racket-lang.org/dev
