Eliot Miranda uploaded a new version of KernelTests to project The Trunk:
http://source.squeak.org/trunk/KernelTests-eem.224.mcz ==================== Summary ==================== Name: KernelTests-eem.224 Author: eem Time: 27 May 2012, 3:16:16.618 pm UUID: 2d674fd0-22e3-4b5c-82ae-af5642c9614f Ancestors: KernelTests-nice.223 Add a long test case for CompiledMethod = & hash =============== Diff against KernelTests-nice.223 =============== Item was added: + LongTestCase subclass: #CompiledMethodComparisonTest + instanceVariableNames: '' + classVariableNames: '' + poolDictionaries: '' + category: 'KernelTests-Methods'! Item was added: + ----- Method: CompiledMethodComparisonTest>>testHash (in category 'tests') ----- + testHash + | ai | + ai := CompiledMethod allInstances. + ai do: + [:a| + ai do: + [:b| + a = b ifTrue: [self assert: a hash = b hash]]]! |
On 27 May 2012 23:16, <[hidden email]> wrote:
> Eliot Miranda uploaded a new version of KernelTests to project The Trunk: > http://source.squeak.org/trunk/KernelTests-eem.224.mcz > > ==================== Summary ==================== > > Name: KernelTests-eem.224 > Author: eem > Time: 27 May 2012, 3:16:16.618 pm > UUID: 2d674fd0-22e3-4b5c-82ae-af5642c9614f > Ancestors: KernelTests-nice.223 > > Add a long test case for CompiledMethod = & hash > > =============== Diff against KernelTests-nice.223 =============== > > Item was added: > + LongTestCase subclass: #CompiledMethodComparisonTest > + instanceVariableNames: '' > + classVariableNames: '' > + poolDictionaries: '' > + category: 'KernelTests-Methods'! > > Item was added: > + ----- Method: CompiledMethodComparisonTest>>testHash (in category 'tests') ----- > + testHash > + | ai | > + ai := CompiledMethod allInstances. > + ai do: > + [:a| > + ai do: > + [:b| > + a = b ifTrue: [self assert: a hash = b hash]]]! > > Not necessarily here, but it'd be good to see that (a = b) ifFalse: [self deny: a hash = b hash] holds. frank |
On Mon, 28 May 2012, Frank Shearar wrote:
> On 27 May 2012 23:16, <[hidden email]> wrote: >> Eliot Miranda uploaded a new version of KernelTests to project The Trunk: >> http://source.squeak.org/trunk/KernelTests-eem.224.mcz >> >> ==================== Summary ==================== >> >> Name: KernelTests-eem.224 >> Author: eem >> Time: 27 May 2012, 3:16:16.618 pm >> UUID: 2d674fd0-22e3-4b5c-82ae-af5642c9614f >> Ancestors: KernelTests-nice.223 >> >> Add a long test case for CompiledMethod = & hash >> >> =============== Diff against KernelTests-nice.223 =============== >> >> Item was added: >> + LongTestCase subclass: #CompiledMethodComparisonTest >> + instanceVariableNames: '' >> + classVariableNames: '' >> + poolDictionaries: '' >> + category: 'KernelTests-Methods'! >> >> Item was added: >> + ----- Method: CompiledMethodComparisonTest>>testHash (in category 'tests') ----- >> + testHash >> + | ai | >> + ai := CompiledMethod allInstances. >> + ai do: >> + [:a| >> + ai do: >> + [:b| >> + a = b ifTrue: [self assert: a hash = b hash]]]! >> >> > > Not necessarily here, but it'd be good to see that (a = b) ifFalse: > [self deny: a hash = b hash] holds. they were, then either the codomain would be too large (not SmallInteger in our case, which makes hashing impractical) or there were no need for the use of hashing at all, since there were no collisions. Levente > > frank > > |
On 28 May 2012 14:33, Levente Uzonyi <[hidden email]> wrote:
> On Mon, 28 May 2012, Frank Shearar wrote: > >> On 27 May 2012 23:16, <[hidden email]> wrote: >>> >>> Eliot Miranda uploaded a new version of KernelTests to project The Trunk: >>> http://source.squeak.org/trunk/KernelTests-eem.224.mcz >>> >>> ==================== Summary ==================== >>> >>> Name: KernelTests-eem.224 >>> Author: eem >>> Time: 27 May 2012, 3:16:16.618 pm >>> UUID: 2d674fd0-22e3-4b5c-82ae-af5642c9614f >>> Ancestors: KernelTests-nice.223 >>> >>> Add a long test case for CompiledMethod = & hash >>> >>> =============== Diff against KernelTests-nice.223 =============== >>> >>> Item was added: >>> + LongTestCase subclass: #CompiledMethodComparisonTest >>> + instanceVariableNames: '' >>> + classVariableNames: '' >>> + poolDictionaries: '' >>> + category: 'KernelTests-Methods'! >>> >>> Item was added: >>> + ----- Method: CompiledMethodComparisonTest>>testHash (in category >>> 'tests') ----- >>> + testHash >>> + | ai | >>> + ai := CompiledMethod allInstances. >>> + ai do: >>> + [:a| >>> + ai do: >>> + [:b| >>> + a = b ifTrue: [self assert: a hash = b hash]]]! >>> >>> >> >> Not necessarily here, but it'd be good to see that (a = b) ifFalse: >> [self deny: a hash = b hash] holds. > > > That would be a nice property, but hash functions are not injective. If they > were, then either the codomain would be too large (not SmallInteger in our > case, which makes hashing impractical) or there were no need for the use of > hashing at all, since there were no collisions. Sure, collisions mean that you can have a ~= b and yet a hash = b hash. Nevertheless, CompiledMethod define: #hash as: [^ 1] satisfies the above test, so on its own it's insufficient. I wouldn't ask for testing CM x CM - {CompiledMethods whose hashes collide} ! frank > Levente > >> >> frank >> > > > |
On 2012-05-28, at 7:59 AM, Frank Shearar wrote: >> That would be a nice property, but hash functions are not injective. If they >> were, then either the codomain would be too large (not SmallInteger in our >> case, which makes hashing impractical) or there were no need for the use of >> hashing at all, since there were no collisions. > > Sure, collisions mean that you can have a ~= b and yet a hash = b > hash. Nevertheless, CompiledMethod define: #hash as: [^ 1] satisfies > the above test, so on its own it's insufficient. I wouldn't ask for > testing CM x CM - {CompiledMethods whose hashes collide} ! So, essentially, you want a test that ensures that we have a high-quality hash function. That would be nice, but I'm not sure it fits into the structure of a unit test. Porting Andres' hash function tools to Squeak would probably be the best way to do that. Short of that, I'd suggest a simple smoke test - say, asserting that there are few collisions between the methods of TestCase or something like that. Colin |
On 28 May 2012 17:43, Colin Putney <[hidden email]> wrote:
> > On 2012-05-28, at 7:59 AM, Frank Shearar wrote: > >>> That would be a nice property, but hash functions are not injective. If they >>> were, then either the codomain would be too large (not SmallInteger in our >>> case, which makes hashing impractical) or there were no need for the use of >>> hashing at all, since there were no collisions. >> >> Sure, collisions mean that you can have a ~= b and yet a hash = b >> hash. Nevertheless, CompiledMethod define: #hash as: [^ 1] satisfies >> the above test, so on its own it's insufficient. I wouldn't ask for >> testing CM x CM - {CompiledMethods whose hashes collide} ! > > So, essentially, you want a test that ensures that we have a high-quality hash function. That would be nice, but I'm not sure it fits into the structure of a unit test. Porting Andres' hash function tools to Squeak would probably be the best way to do that. Short of that, I'd suggest a simple smoke test - say, asserting that there are few collisions between the methods of TestCase or something like that. I just want a test demonstrating that, even if it's just for carefully constructed CompiledMethods, sometime cmA hash ~= cmB hash when cmA ~= cmB. At the moment the test thoroughly demonstrates half of the hash's behaviour - when things are =, their hashes are =. I agree that demonstrating the collision rate of the hash function is beyond the scope of a unit test. frank > > Colin |
On Mon, May 28, 2012 at 11:13 PM, Frank Shearar <[hidden email]> wrote: --
How about adding a count that e.g. demands that the number of distinct hashes is better than half the number of distinct CompiledMethods. e.g. testHash | ai | ai := CompiledMethod allInstances.
ai do: [:a| ai do:
[:b| a = b ifTrue: [self assert: a hash = b hash]]]. self assert: (ai collect: [:cm| cm hash]) asSet size * 2 >= ai asSet size
best, Eliot |
Free forum by Nabble | Edit this page |