The Trunk: Collections-ul.668.mcz
Locked
 
|
Levente Uzonyi uploaded a new version of Collections to project The Trunk:
http://source.squeak.org/trunk/Collections-ul.668.mcz ==================== Summary ==================== Name: Collections-ul.668 Author: ul Time: 13 October 2015, 1:07:48.216 am UUID: 8abfa05a-70c6-4e38-bc00-7d665183106c Ancestors: Collections-ul.667 In Dictionary >> #=, make sure that the dictionaries agree on what the common keys are. This way the behaviour of #= will be symmetric when the two dictionaries implement key equality differently. =============== Diff against Collections-ul.667 =============== Item was changed: ----- Method: Dictionary>>= (in category 'comparing') ----- + = anObject - = aDictionary "Two dictionaries are equal if (a) they are the same 'kind' of thing. (b) they have the same set of keys. (c) for each (common) key, they have the same value" + self == anObject ifTrue: [ ^true ]. + anObject isDictionary ifFalse: [ ^false ]. + self size = anObject size ifFalse: [ ^false ]. + self associationsDo: [ :association | + (anObject at: association key ifAbsent: [ ^false ]) = association value + ifFalse: [ ^false ] ]. + "The two dictionaries may have different ideas about equal keys, so check both ways to avoid any inconsistency." + anObject associationsDo: [ :association | + (self at: association key ifAbsent: [ ^false ]) = association value + ifFalse: [ ^false ] ]. + ^true! - self == aDictionary ifTrue: [ ^ true ]. - aDictionary isDictionary ifFalse: [^false]. - self size = aDictionary size ifFalse: [^false]. - self associationsDo: [:assoc| - (aDictionary at: assoc key ifAbsent: [^false]) = assoc value - ifFalse: [^false]]. - ^true - - ! |
Re: The Trunk: Collections-ul.668.mcz
|
|
This extra check halves the speed of Dictionary>>= when they are equal, for all cases which consider equivalence symmetrical. If a=b, then it should be able to be assumed that b=a. What case is it not? On Mon, Oct 12, 2015 at 7:02 PM, <[hidden email]> wrote: Levente Uzonyi uploaded a new version of Collections to project The Trunk: |
Re: The Trunk: Collections-ul.668.mcz
|
|
I'm guessing | ed id | ed := Dictionary with: 'a' -> $a. id := IdentityDictionary with: 'a' copy -> $a. { ed = id. id = ed } _,,,^..^,,,_ (phone)
|
Re: The Trunk: Collections-ul.668.mcz
|
|
Exactly. It can happen with other kind of dictionaries as well. And class
checks would not enough: d1 := PluggableDictionary new. d2 := PluggableDictionary new equalBlock: #==. d1 at: 'test' copy put: 4. d2 at: 'test' put: 4. {d1 = d2. d2 = d1} So, performance goes down in some cases, but I guess we agree on #= has to be symmetric. We can speed up some cases if the dictionaries can tell if #= is guaranteed to be symmetric when they have the same class. Levente On Mon, 12 Oct 2015, Eliot Miranda wrote: > I'm guessing > > | ed id | > ed := Dictionary with: 'a' -> $a. > id := IdentityDictionary with: 'a' copy -> $a. > { ed = id. id = ed } > > _,,,^..^,,,_ (phone) > > On Oct 12, 2015, at 5:14 PM, Chris Muller <[hidden email]> wrote: > > This extra check halves the speed of Dictionary>>= when they are equal, for all cases which consider equivalence symmetrical. If a=b, > then it should be able to be assumed that b=a. What case is it not? > > On Mon, Oct 12, 2015 at 7:02 PM, <[hidden email]> wrote: > Levente Uzonyi uploaded a new version of Collections to project The Trunk: > http://source.squeak.org/trunk/Collections-ul.668.mcz > > ==================== Summary ==================== > > Name: Collections-ul.668 > Author: ul > Time: 13 October 2015, 1:07:48.216 am > UUID: 8abfa05a-70c6-4e38-bc00-7d665183106c > Ancestors: Collections-ul.667 > > In Dictionary >> #=, make sure that the dictionaries agree on what the common keys are. This way the behaviour of #= will be > symmetric when the two dictionaries implement key equality differently. > > =============== Diff against Collections-ul.667 =============== > > Item was changed: > ----- Method: Dictionary>>= (in category 'comparing') ----- > + = anObject > - = aDictionary > "Two dictionaries are equal if > (a) they are the same 'kind' of thing. > (b) they have the same set of keys. > (c) for each (common) key, they have the same value" > > + self == anObject ifTrue: [ ^true ]. > + anObject isDictionary ifFalse: [ ^false ]. > + self size = anObject size ifFalse: [ ^false ]. > + self associationsDo: [ :association | > + (anObject at: association key ifAbsent: [ ^false ]) = association value > + ifFalse: [ ^false ] ]. > + "The two dictionaries may have different ideas about equal keys, so check both ways to avoid any inconsistency." > + anObject associationsDo: [ :association | > + (self at: association key ifAbsent: [ ^false ]) = association value > + ifFalse: [ ^false ] ]. > + ^true! > - self == aDictionary ifTrue: [ ^ true ]. > - aDictionary isDictionary ifFalse: [^false]. > - self size = aDictionary size ifFalse: [^false]. > - self associationsDo: [:assoc| > - (aDictionary at: assoc key ifAbsent: [^false]) = assoc value > - ifFalse: [^false]]. > - ^true > - > - ! > > > > > > |
Re: The Trunk: Collections-ul.668.mcz
|
|
> d1 := PluggableDictionary new.
> d2 := PluggableDictionary new equalBlock: #==. > d1 at: 'test' copy put: 4. > d2 at: 'test' put: 4. > {d1 = d2. > d2 = d1} But does it always make sense to say that two dictionaries are equal even though they do not have the same equalBlock ? It seems to me there are different semantics for dictionary equality here: one testing if the associations are equal, one testing if the expected behavior (at large) of the dictionaries are equal. The single #= test is overload at the moment. Stef |
Re: The Trunk: Collections-ul.668.mcz
|
|
In reply to this post by Levente Uzonyi-2
2015-10-13 3:37 GMT+02:00 Levente Uzonyi <[hidden email]>: Exactly. It can happen with other kind of dictionaries as well. And class checks would not enough: But #hash still uses species, that means, we can have a Dictionary and an IdentityDictionary to be equal, but with different hash. s := 'a' ed := Dictionary with: s -> $a. id := IdentityDictionary with: s -> $a. { ed = id. id = ed. ed hash = id hash } "-> #(true true false)"
|
Re: The Trunk: Collections-ul.668.mcz
|
|
>> Exactly. It can happen with other kind of dictionaries as well. And class checks would not enough:
>> >> d1 := PluggableDictionary new. >> d2 := PluggableDictionary new equalBlock: #==. >> d1 at: 'test' copy put: 4. >> d2 at: 'test' put: 4. >> {d1 = d2. >> d2 = d1} >> >> So, performance goes down in some cases, but I guess we agree on #= has to be symmetric. For simple value types, yes, we should be able to make that assumption, but symmetry of equivalence starts to break down for objects as complex as a Dictionary.. > We can speed up some cases if the dictionaries can tell if #= is guaranteed to be symmetric > when they have the same class. > > But #hash still uses species, that means, we can have a Dictionary and an IdentityDictionary to be equal, but with different hash. > > s := 'a' > ed := Dictionary with: s -> $a. > id := IdentityDictionary with: s -> $a. > { ed = id. id = ed. ed hash = id hash } "-> #(true true false)" Equivalence of complex objects is always a "loose" definition, of which there can be several. Additional API like #hasEqualElements: (of SequenceableCollection) could be added as needed to accomodate other application needs, but we only get ONE particular implementation which can also be suitable for use in HashedCollections, because they send #=. Changing it should be really scrutinized. I'm wondering if Levente could get by with an app-specific equivalence check without needing it for use in HashedCllections? Seems like a lot of the #= in the system require class or species equivalence, a few allow isKindOf:, but only one or two allow #is message response. I'm wondering now if those last kind are ill-advised... BTW, with this change, I guess we're now somewhat inconsistent with Set, | ed id | ed := Set with: 'a' copy. id := IdentitySet with: 'a'. { ed = id. id = ed } " #(false true)" My production app is going to be punished by Levente's change, unnecessarily. I think we should consider an alternative like adding #hasEqualElements: for your app... |
Re: The Trunk: Collections-ul.668.mcz
|
|
What we can do is to use class (or species) checks. That way we can be
consistent with the current hash implementation, and ensure symmetry, but different dictionaries holding the same pairs will not be equivalent. PluggableDictionary needs its own implementation of course. And Sets can use the same kind of check as well. Levente On Tue, 13 Oct 2015, Chris Muller wrote: >>> Exactly. It can happen with other kind of dictionaries as well. And class checks would not enough: >>> >>> d1 := PluggableDictionary new. >>> d2 := PluggableDictionary new equalBlock: #==. >>> d1 at: 'test' copy put: 4. >>> d2 at: 'test' put: 4. >>> {d1 = d2. >>> d2 = d1} >>> >>> So, performance goes down in some cases, but I guess we agree on #= has to be symmetric. > > For simple value types, yes, we should be able to make that > assumption, but symmetry of equivalence starts to break down for > objects as complex as a Dictionary.. > >> We can speed up some cases if the dictionaries can tell if #= is guaranteed to be symmetric >> when they have the same class. >> >> But #hash still uses species, that means, we can have a Dictionary and an IdentityDictionary to be equal, but with different hash. >> >> s := 'a' >> ed := Dictionary with: s -> $a. >> id := IdentityDictionary with: s -> $a. >> { ed = id. id = ed. ed hash = id hash } "-> #(true true false)" > > Equivalence of complex objects is always a "loose" definition, of > which there can be several. Additional API like #hasEqualElements: > (of SequenceableCollection) could be added as needed to accomodate > other application needs, but we only get ONE particular implementation > which can also be suitable for use in HashedCollections, because they > send #=. Changing it should be really scrutinized. > > I'm wondering if Levente could get by with an app-specific equivalence > check without needing it for use in HashedCllections? Seems like a > lot of the #= in the system require class or species equivalence, a > few allow isKindOf:, but only one or two allow #is message response. > I'm wondering now if those last kind are ill-advised... > > BTW, with this change, I guess we're now somewhat inconsistent with Set, > > | ed id | > ed := Set with: 'a' copy. > id := IdentitySet with: 'a'. > { ed = id. id = ed } " #(false true)" > > My production app is going to be punished by Levente's change, > unnecessarily. I think we should consider an alternative like adding > #hasEqualElements: for your app... > |
Re: The Trunk: Collections-ul.668.mcz
|
|
Okay if you do would you please use a species rather than class check?
#class checks create problems for Magma or any systems which use proxies, because such tests produce a different result depending on whether the proxy is materialized or not because #class is a inlined message which cannot be detected by the proxy. Thanks. On Tue, Oct 13, 2015 at 1:05 PM, Levente Uzonyi <[hidden email]> wrote: > What we can do is to use class (or species) checks. That way we can be > consistent with the current hash implementation, and ensure symmetry, but > different dictionaries holding the same pairs will not be equivalent. > PluggableDictionary needs its own implementation of course. > And Sets can use the same kind of check as well. > > Levente > > > On Tue, 13 Oct 2015, Chris Muller wrote: > >>>> Exactly. It can happen with other kind of dictionaries as well. And >>>> class checks would not enough: >>>> >>>> d1 := PluggableDictionary new. >>>> d2 := PluggableDictionary new equalBlock: #==. >>>> d1 at: 'test' copy put: 4. >>>> d2 at: 'test' put: 4. >>>> {d1 = d2. >>>> d2 = d1} >>>> >>>> So, performance goes down in some cases, but I guess we agree on #= has >>>> to be symmetric. >> >> >> For simple value types, yes, we should be able to make that >> assumption, but symmetry of equivalence starts to break down for >> objects as complex as a Dictionary.. >> >>> We can speed up some cases if the dictionaries can tell if #= is >>> guaranteed to be symmetric >>> when they have the same class. >>> >>> But #hash still uses species, that means, we can have a Dictionary and an >>> IdentityDictionary to be equal, but with different hash. >>> >>> s := 'a' >>> ed := Dictionary with: s -> $a. >>> id := IdentityDictionary with: s -> $a. >>> { ed = id. id = ed. ed hash = id hash } "-> #(true true false)" >> >> >> Equivalence of complex objects is always a "loose" definition, of >> which there can be several. Additional API like #hasEqualElements: >> (of SequenceableCollection) could be added as needed to accomodate >> other application needs, but we only get ONE particular implementation >> which can also be suitable for use in HashedCollections, because they >> send #=. Changing it should be really scrutinized. >> >> I'm wondering if Levente could get by with an app-specific equivalence >> check without needing it for use in HashedCllections? Seems like a >> lot of the #= in the system require class or species equivalence, a >> few allow isKindOf:, but only one or two allow #is message response. >> I'm wondering now if those last kind are ill-advised... >> >> BTW, with this change, I guess we're now somewhat inconsistent with Set, >> >> | ed id | >> ed := Set with: 'a' copy. >> id := IdentitySet with: 'a'. >> { ed = id. id = ed } " #(false true)" >> >> My production app is going to be punished by Levente's change, >> unnecessarily. I think we should consider an alternative like adding >> #hasEqualElements: for your app... >> > |
«
Return to Squeak - Dev
|
1 view|%1 views
| Free forum by Nabble | Edit this page |