StabilizedMemoization Fork

Feb 11, 2012 at 12:17 AM
Edited Feb 11, 2012 at 12:18 AM

Hi Justin,

I apologize for the time it has taken to get this in; TR was pretty demanding this week.

I created the fork and checked in my changes. The unit tests seem to run in about the same time as the current trunk.

What's in it:

* I created a compiler constant, FLATTEN_HASHCODES, that will causes the Positions to return 1 for their hash code. This was the best test I could come up with for detecting memoization collisions. When it is set, the unit tests will >30mins to run, but if they will fail if there are are any collisions where incorrect positions are return from the memo table. Perhaps a secondary build project on your build server could run the tests with this constant set?

* Positions are now IEquatable. Using the constant above, I found that even the patch I sent was insufficent, since it was using IComparable.Compare == 0 as a test for equality (valid for sorting, but not for identity in this case). Please verify that the comparisons I used are valid in the context of the memo table.

* I buffed the Position hashcodes up a bit for better randomness. Since the unit tests seem to run about the same as the trunk right now, I am not sure whether the dedicated hashcode strategy is any better than the ToString() hashcode strategy you were using originally...

I think the FLATTEN_HASHCODES test is much stronger than any input stream I could come up with (as that stream would be overly sensitive to the hashcode algorithm).

Thoughts? Any changes you would like me to make before requesting a pull?

Next week should be calmer, so if you would like to discuss in person, maybe we could grab lunch or coffee.


Feb 11, 2012 at 4:00 PM
Edited Feb 11, 2012 at 4:01 PM

The tests look good and all of the other changes, I don't think we need the FLATTEN_HASHCODES directive, it's an interesting experiment but if we know that equality for those memokeys is what we really need and assume hash collisions are going to take place then it seems ok it just have unit tests that test for equality like you have. We could probably stand to have more but they can evolve. The rest seems fine though.

Feb 14, 2012 at 1:22 AM

Well, it's always something. I got rid of the FLATTEN_HASHCODES (I agree it doesn't test much) and then started writing some unit tests for the MemoKey and Position hierarchy. ValuePosition failed its tests, since the INode it holds is not equatable; ValuePositions => are never equal, which could be causing some of the current performance degradation. Adding IEquatable to INode affects a lot of code. Any thoughts?

Feb 15, 2012 at 9:12 PM

Ah, good point. I think you're right it would be better to just implement IEquatable and call that instead of the CompareTo. The CompareTo is used mostly for the case of Direct Left Recursion where you need to Grow the rule and see if a re-parse goes further or not. The equals comparison is specifically for finding the correct memo. I don't know if ValuePositions ever end up in the memo directly... but it probably wouldn't be bad to make sure they're covered.