October 2009 - Pharo-dev - lists.pharo.org

[Pharo-project] Fwd: Adding FasterSets to Pharo: update

by StÃ©phane Ducasse

Begin forwarded message: > From: Ralph Boland <rpboland(a)gmail.com> > Date: October 30, 2009 6:44:17 AM GMT+01:00 > To: Levente Uzonyi <leves(a)elte.hu> > Cc: StÃ©phane Ducasse <stephane.ducasse(a)inria.fr> > Subject: Re: Adding FasterSets to Pharo: update > > 2009/10/29 Levente Uzonyi <leves(a)elte.hu>: >> Hi! >> >> On Thu, 29 Oct 2009, Ralph Boland wrote: >> >>> In Levente's code class WeakKeyToCollectionDictionary->rehash >>> seems to >>> be >>> missing. This appears to be a mistate to me but I will live it >>> to Levente to explain >>> it. The fix, if needed, is simple. >> >> Only Set and MethodDictionary implements #rehash in the trunk >> version. >> #rehash sends #growTo: which sends #noCheckNoGrowFillFrom: which is >> implemented by WeakKeyToCollectionDictionary. >> > > The version of rehash in WeakKeyToCollectionDictionary is different > from the > other versions. I never bothered to figure out exactly what it does > and just > left it alone. Despite what you say my opinion is still that it is > needed but I will > leave it to those making the final decision to decide. > >>> b) Levente's version does not use method scanForNilFrom: (He >>> would probably call >>> the method scanForEmptySlotFrom:). >>> I don't know why he didn't do this: it clearly cleaner. >> >> It's called #scanForEmptySlotFor:, because WeakSet has a flag for >> empty >> slots, not nil. > > This is not correct. ScanForEmptySlotFor: is analogous to > scanForNil: You did > not implement a method analogous to scanForNilFrom: and obviously > never > used it either. In my opinion the use of scanForNilFrom: makes the > code cleaner > but it is not a major issue if it is not used. >> >>> b) The improvement in performance for method add: in Levente's >>> version >>> is insignificant (appx 1%); this difference could easily >>> be made up in minor >>> changes to my code. Thus here I consider there to be no >>> difference. >> >> Don't let the garbage collector fool you. >> See http://leves.web.elte.hu/collections/DictionaryBenchmarkResults.txt >> . >> The values in the table are microseconds/element without gc time. >> The benchmark code is here >> http://leves.web.elte.hu/collections/DictionaryBenchmark.st >> A similar benchmark's result for Set: >> >> Trunk: >> Size 1000 2000 5000 10000 20000 50000 100000 >> 200000 >> 500000 >> add: (included) 0.5 0.2 0.36 0.46 0.365 0.392 0.394 >> 0.406 0.4112 >> add: (not included) 1.5 1.6 1.38 1.35 1.365 1.25 >> 1.261 1.252 1.5192 >> ... > > I don't know what these stats are about. > I am merely quoting the stats you posted for the first version of > faster sets that you released. They indicated that for class Set > your method rehash was appx 15% faster than the version in > FasterSets and > your method add: was appx 1% faster than the version in FasterSets. > >> >>> b) Levente's version does not apply the FasterSets idea to >>> MethodDictionary. >>> I am not sure why he did not do this but it may have >>> something to do with the fact that >>> mistakes can easily corrupt your image. The version in >>> FasterSets works fine though >>> it took three tries for me to get it right (mostly because >>> of carelessness). >> > > >> It would be easy to modify MethodDictionary, but it has a different >> implementation, so most methods would have to be overridden and the >> performance benefits would be insignificant, because #become: is >> much (~80x) >> slower than the actual rehash for an average sized MethodDictionary. >> Btw, MethodDictionaries are rarely grown. > > >> >>> c) I left methods intersection and nastyAddNew: out of classes >>> Set and Dictionary for >>> the initial version of FasterSets to keep the number of >>> changes to a minimum. >>> At your request I added them to the current version. >>> These methods are not in >>> Levente's version. They are public methods that provide >>> performance improvements. >>> If desired they could easily be added to Levente's >>> version. >> >> #nastyAddNew: is not really useful IMO, if you want to be nasty, >> you can use >> "private" methods: >> aSet atNewIndex: (set scanForNil: anObject) put: anObject. >> It's even faster and if you do this, you probably know what you're >> doing. >> > > I don't know whether nastyAddNew: should be added to Pharo/Squeak > or not. > I'll leave that for others to decide. However, I consider > nastyAddNew: to be > preferable to what you propose. > >> I'm not really interrested in #intersecion:, but I found it >> controversal. >> What's the intersecion of a Set and an IdentitySet? Do you check >> identity or >> equality? >> > > The current code currently supports intersection of sets/dictionaries > but it is slower than > the version in FasterSets because the FasterSets version avoids > unnecessary compares. > If you believe that intersection for sets in the current code is > controversial and should be > changed or removed fine. FasterSets is not entering this debate; it > is merely providing > faster versions of intersection than what is already in the code. > >>> I recommend that >>> >>> 1) You use Levente's version. >> >> Feel free to grab it. >> >>> 2) Sort out the issue of no rehash method for Class >>> WeakKeyToCollectionDictionary. >> >> See above. >> >>> 3) Modify his code to use method scanForNilFrom: (calling it >>> scanForEmptySlotFrom:). >> >> See above. >> >>> 4) Decide if you want to add methods intersect: and >>> nastyAddNew:. >>> I can add these if you want. >> >> See my opinion above. >> >>> 5) Release a version of Pharo with these changes. >>> 6) In the following release of Pharo add the changes to >>> MethodDictionary to use The >>> FasterSets Idea. I sugggest doing this separately from >>> everything else just because it is a >>> bit hairy. I would not leave this change out because >>> MethodDictionary is too important >>> a class not to have these improvements. >>> >> >> See above. >> >>> You can post this on the Pharo newsgroup if you like but perhaps you >>> should get Levente's >>> opinion first. >> >> Go ahead, I'm already subscribed to the pharo list because I >> couldn't stop >> myself to respond to a false statement. >> >> Cheers, >> Levente >> > > Regards, > > Ralph Boland

Oct. 31, 2009

[Pharo-project] Fwd: Adding FasterSets to Pharo: update

by StÃ©phane Ducasse

Begin forwarded message: > From: Levente Uzonyi <leves(a)elte.hu> > Date: October 30, 2009 3:29:33 AM GMT+01:00 > To: Ralph Boland <rpboland(a)gmail.com> > Cc: StÃ©phane Ducasse <stephane.ducasse(a)inria.fr> > Subject: Re: Adding FasterSets to Pharo: update > > Hi! > > On Thu, 29 Oct 2009, Ralph Boland wrote: > >> In Levente's code class WeakKeyToCollectionDictionary->rehash >> seems to be >> missing. This appears to be a mistate to me but I will live it >> to Levente to explain >> it. The fix, if needed, is simple. > > Only Set and MethodDictionary implements #rehash in the trunk > version. #rehash sends #growTo: which sends #noCheckNoGrowFillFrom: > which is implemented by WeakKeyToCollectionDictionary. > >> b) Levente's version does not use method scanForNilFrom: (He >> would probably call >> the method scanForEmptySlotFrom:). >> I don't know why he didn't do this: it clearly cleaner. > > It's called #scanForEmptySlotFor:, because WeakSet has a flag for > empty slots, not nil. > >> b) The improvement in performance for method add: in >> Levente's version >> is insignificant (appx 1%); this difference could easily >> be made up in minor >> changes to my code. Thus here I consider there to be no >> difference. > > Don't let the garbage collector fool you. > See http://leves.web.elte.hu/collections/DictionaryBenchmarkResults.txt > . The values in the table are microseconds/element without gc time. > The benchmark code is here http://leves.web.elte.hu/collections/DictionaryBenchmark.st > A similar benchmark's result for Set: > > Trunk: > Size 1000 2000 5000 10000 20000 50000 100000 200000 500000 > add: (included) 0.5 0.2 0.36 0.46 0.365 0.392 0.394 0.406 0.4112 > add: (not included) 1.5 1.6 1.38 1.35 1.365 1.25 1.261 1.252 1.5192 > includes: (included) 0.3 0.5 0.42 0.41 0.395 0.432 0.457 0.4695 0.4442 > includes: (not included) 0.2 0.5 0.56 0.51 0.51 0.632 0.66 0.6525 > 0.5994 > like: (included) 0.5 0.4 0.4 0.36 0.345 0.37 0.393 0.4105 0.3854 > like: (not included) 0.4 0.45 0.52 0.44 0.445 0.566 0.593 0.5895 0.536 > rehash 0.5 0.4 0.32 0.33 0.33 0.338 0.342 0.326 0.3386 > remove:ifAbsent: (included) 0.7 0.95 1.02 0.99 1.015 1.228 1.238 > 1.2485 0.9282 > remove:ifAbsent: (not included) 0.4 0.5 0.58 0.54 0.575 0.686 0.699 > 0.6985 0.6586 > > Pharo: > Size 1000 2000 5000 10000 20000 50000 100000 200000 500000 > add: (included) 0.4 0.45 0.5 0.45 0.44 0.462 0.465 0.4705 0.499 > add: (not included) 2.0 2.0 1.72 1.67 1.715 1.57 1.582 1.57 2.0874 > includes: (included) 0.5 0.5 0.56 0.6 0.52 0.52 0.547 0.5335 0.5814 > includes: (not included) 0.7 0.85 0.8 1.03 0.865 0.804 0.804 0.8265 > 0.8734 > like: (included) 0.7 0.45 0.4 0.5 0.395 0.382 0.399 0.3935 0.4208 > like: (not included) 0.3 0.65 0.66 0.9 0.705 0.66 0.659 0.679 0.783 > rehash 0.9 0.6 0.64 0.69 0.63 0.604 0.615 0.6285 0.6964 > remove:ifAbsent: (included) 2.0 1.95 2.16 6.59 2.165 2.052 1.981 > 2.092 2.0544 > remove:ifAbsent: (not included) 0.9 0.85 0.92 1.05 0.9 0.84 0.878 > 0.869 1.0232 > > Pharo with Andres's hacks: > Size 1000 2000 5000 10000 20000 50000 100000 200000 500000 > add: (included) 0.5 0.5 0.46 0.49 0.475 0.466 0.458 0.4935 0.5306 > add: (not included) 1.7 2.35 2.26 2.02 2.15 2.12 2.298 2.021 2.0332 > includes: (included) 0.6 0.5 0.56 0.53 0.62 0.528 0.539 0.533 0.588 > includes: (not included) 0.8 0.8 0.74 0.77 0.745 0.7 0.694 0.706 > 0.7814 > like: (included) 0.1 0.2 0.36 0.4 0.485 0.386 0.39 0.382 0.4312 > like: (not included) 0.4 0.8 0.6 0.66 0.605 0.576 0.566 0.5835 0.6554 > rehash 0.6 0.55 0.62 0.58 0.575 0.586 0.599 0.5825 0.6044 > remove:ifAbsent: (included) 1.5 1.95 1.86 1.97 1.905 1.786 1.763 > 1.8005 1.9346 > remove:ifAbsent: (not included) 0.7 0.75 0.82 0.82 0.84 0.774 0.771 > 0.7755 0.8418 > > If you're interrested in the benchmark code, let me know. > >> b) Levente's version does not apply the FasterSets idea to >> MethodDictionary. >> I am not sure why he did not do this but it may have >> something to do with the fact that >> mistakes can easily corrupt your image. The version in >> FasterSets works fine though >> it took three tries for me to get it right (mostly because >> of carelessness). > > It would be easy to modify MethodDictionary, but it has a different > implementation, so most methods would have to be overridden and the > performance benefits would be insignificant, because #become: is > much (~80x) slower than the actual rehash for an average sized > MethodDictionary. > Btw, MethodDictionaries are rarely grown. > >> c) I left methods intersection and nastyAddNew: out of classes >> Set and Dictionary for >> the initial version of FasterSets to keep the number of >> changes to a minimum. >> At your request I added them to the current version. >> These methods are not in >> Levente's version. They are public methods that provide >> performance improvements. >> If desired they could easily be added to Levente's version. > > #nastyAddNew: is not really useful IMO, if you want to be nasty, you > can use "private" methods: > aSet atNewIndex: (set scanForNil: anObject) put: anObject. > It's even faster and if you do this, you probably know what you're > doing. > > I'm not really interrested in #intersecion:, but I found it > controversal. What's the intersecion of a Set and an IdentitySet? Do > you check identity or equality? > >> I recommend that >> >> 1) You use Levente's version. > > Feel free to grab it. > >> 2) Sort out the issue of no rehash method for Class >> WeakKeyToCollectionDictionary. > > See above. > >> 3) Modify his code to use method scanForNilFrom: (calling it >> scanForEmptySlotFrom:). > > See above. > >> 4) Decide if you want to add methods intersect: and >> nastyAddNew:. >> I can add these if you want. > > See my opinion above. > >> 5) Release a version of Pharo with these changes. >> 6) In the following release of Pharo add the changes to >> MethodDictionary to use The >> FasterSets Idea. I sugggest doing this separately from >> everything else just because it is a >> bit hairy. I would not leave this change out because >> MethodDictionary is too important >> a class not to have these improvements. >> > > See above. > >> You can post this on the Pharo newsgroup if you like but perhaps you >> should get Levente's >> opinion first. > > Go ahead, I'm already subscribed to the pharo list because I > couldn't stop myself to respond to a false statement. > > Cheers, > Levente

Oct. 31, 2009

[Pharo-project] Fwd: Adding FasterSets to Pharo: update

by StÃ©phane Ducasse

Thanks. I push the discussion to pharo since lot of people are interested. Stef Begin forwarded message: > From: Ralph Boland <rpboland(a)gmail.com> > Date: October 29, 2009 11:43:04 PM GMT+01:00 > To: StÃ©phane Ducasse <stephane.ducasse(a)inria.fr> > Cc: Levente Uzonyi <leves(a)elte.hu> > Subject: Adding FasterSets to Pharo: update > > I took a look at FasterSets and Levente Uzonyi's version. > I compared the two versions as of the first release of Levente's > version to Squeak. Note that he has released additional > changes since then. > Here is my report. > > 1) Bugs: > > FasterSets has two problems: > a) KeyedIdentitySet is missing method ScanForNil: > b) PluggableSet is missing method NoCompareOrGrowAddAll: > Both cases should cause failure. Note that I have been using > this code for years without problem. I assume that is because > the subset > of Squeak that I used doesn't include using these classes. > These problems are easily fixed. > > In Levente's code class WeakKeyToCollectionDictionary->rehash > seems to be > missing. This appears to be a mistate to me but I will live it > to Levente to explain > it. The fix, if needed, is simple. > > 2) Code quality: > For me the code quality is about the same but Levente considers > his version to be better. > In any case changes in one version is easily ported to the other > so it would be easy to > perform any cleanup you might want. Three notes in particular. > a) Levente's version of rehash is cleaner and should be used > instead of mine. > b) Levente's version does not use method scanForNilFrom: (He > would probably call > the method scanForEmptySlotFrom:). > I don't know why he didn't do this: it clearly cleaner. > > 3 Performance. > a) According to Levente's stats rehash is clearly faster in > his version than mine. I see > no reason no not prefer his version to mine. > > b) The improvement in performance for method add: in > Levente's version > is insignificant (appx 1%); this difference could easily > be made up in minor > changes to my code. Thus here I consider there to be no > difference. > > b) Levente's version does not apply the FasterSets idea to > MethodDictionary. > I am not sure why he did not do this but it may have > something to do with the fact that > mistakes can easily corrupt your image. The version in > FasterSets works fine though > it took three tries for me to get it right (mostly because > of carelessness). > > c) I left methods intersection and nastyAddNew: out of classes > Set and Dictionary for > the initial version of FasterSets to keep the number of > changes to a minimum. > At your request I added them to the current version. > These methods are not in > Levente's version. They are public methods that provide > performance improvements. > If desired they could easily be added to Levente's version. > > > Based on the above I would say that there is not a great deal of > difference between Levente's version and mine but what difference > there is favors his version. > > I recommend that > > 1) You use Levente's version. > 2) Sort out the issue of no rehash method for Class > WeakKeyToCollectionDictionary. > 3) Modify his code to use method scanForNilFrom: (calling it > scanForEmptySlotFrom:). > 4) Decide if you want to add methods intersect: and > nastyAddNew:. > I can add these if you want. > 5) Release a version of Pharo with these changes. > 6) In the following release of Pharo add the changes to > MethodDictionary to use The > FasterSets Idea. I sugggest doing this separately from > everything else just because it is a > bit hairy. I would not leave this change out because > MethodDictionary is too important > a class not to have these improvements. > > > One final comment. If you really want to make the Set hierarchy > better I would suggest that > you move the Dictionary hierarchy out of the Set hierarchy > altogether. This means some > duplication of code but makes for a much cleaner implementation. For > example you get to > avoid the mess with MethodDictionary. Of the three implementations > of Smalltalk that I > have looked at Squeak/Pharo is the only version that uses one > hierarchy. > This is probably too major a change to make but at least you now know > my opinion on the > matter. > > > You can post this on the Pharo newsgroup if you like but perhaps you > should get Levente's > opinion first. > > Regards > > Ralph Boland

Oct. 31, 2009

Re: [Pharo-project] dictionary value is an array?

by Nicolas Cellier

2009/10/31 StÃ©phane Ducasse <stephane.ducasse(a)inria.fr>: > > Hi nicolas > > If I remember you proposed fixes to have dictionary values -> array? > Is it correct? > > I was wondering why? > Because a set makes more sense to me since > Â Â Â Â - the order of the elements in values is not useful (because they > come from a dict) > Â Â Â Â - the occurrences not really either > Â Â Â Â - we cannot add to the results so we should create another collection > > May be I'm totally wrong with the changes but I think that values > should be set while keys an array. > I would be interested in discussion on that. > > Stef > > Dictionary values is already an Array... I proposed to change keys accordingly. Historically, they were a Bag and a Set because they were unordered. But very few or no sender expect a behavior specific to a Bag or a Set. Most just do: select: collect: asArray asSortedCollection etc... That's where an Array outperforms a Set or a Bag. So we are paying the price of a Set or a Bag almost for nothing... And that is why you can see a #fasterKeys. The drawback is that a few senders will add: to or remove: from keys. My estimation is around 5%. Inside the image, no problem, it is easy to fix, just write (someDictionary keys asSet). But that put a load on package maintainers. Nicolas > > > > _______________________________________________ > Pharo-project mailing list > Pharo-project(a)lists.gforge.inria.fr > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >

Oct. 31, 2009

Re: [Pharo-project] Bitten by MethodReference

by Igor Stasenko

2009/10/29 StÃ©phane Ducasse <stephane.ducasse(a)inria.fr>: > Hi > > just to share a ugly design point with MethodReference > > MethodReference are created using > > MethodReference class: aClass symbol: aSymbol > > however they store the class ***name*** > > and after when you query the class using either actualClass or > methodClass > you get the class that is in Smalltalk. > > So if like me you copied the class then you will get another version > of your class > even if this is the right one you use to create the MethodReference.... > > One of these days we will have to check that > Yes, i wondering myself, what is the point to reference the methods in such style. The way, how actual class & its method get resolved makes it impossible to reference a method in arbitrary class object, especially one which is not installed into system dictionary. I think its lacking additional form of indirection, which should be an environment object who is responsible for delivering the method's source code along with resolving the class by its name. Without such indirection, i see no point in having a MethodReference per se, because you can always do the same thing by yourself , i.e. (Smalltalk at: #SomeClass) methodDict at: #someSelector. Without that, i see no point why i would want to use it, because it always points to same thing, no matter where i using the MethodReference. > Stef > > _______________________________________________ > Pharo-project mailing list > Pharo-project(a)lists.gforge.inria.fr > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project > -- Best regards, Igor Stasenko AKA sig.

Oct. 31, 2009

[Pharo-project] dictionary value is an array?

by StÃ©phane Ducasse

Hi nicolas If I remember you proposed fixes to have dictionary values -> array? Is it correct? I was wondering why? Because a set makes more sense to me since - the order of the elements in values is not useful (because they come from a dict) - the occurrences not really either - we cannot add to the results so we should create another collection May be I'm totally wrong with the changes but I think that values should be set while keys an array. I would be interested in discussion on that. Stef

Oct. 31, 2009

Re: [Pharo-project] Hashed collection improvements: Some code

by Nicolas Cellier

2009/10/29 StÃ©phane Ducasse <stephane.ducasse(a)inria.fr>: > Nicolas > > I do not internet now so I cannot check (hospital bed no wifi :)). > But yes we want to move on. We waited too long to invent the future :) > > Stef > > On Oct 29, 2009, at 10:39 AM, Nicolas Cellier wrote: > Smalltalk apart, I wish you a healthy future. >>> Note that this is closely related to >>> http://bugs.squeak.org/view.php?id=1876 and >>> http://code.google.com/p/pharo/issues/detail?id=213 >>> Amazing the issue is still there when workarounds are known for so >>> long... So please do something! >> > > > _______________________________________________ > Pharo-project mailing list > Pharo-project(a)lists.gforge.inria.fr > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >

Oct. 31, 2009

Re: [Pharo-project] Hashed collection changes, the performance graphs

by StÃ©phane Ducasse

thanks for this cool mail! On Oct 29, 2009, at 12:51 AM, Andres Valloud wrote: > Stephane et al, > > Martin and I discussed this yesterday night at the PDX Smalltalk user > group meeting. Mostly we agree, with perhaps one small exception. In > order to make hashed collections simpler and identity hash handling > more > straightforward, hashed collections should get a small integer range > identity hash value. Something between 0 and SmallInteger maxVal, for > example. The issue is how to get that. > > Martin's approach is to change identityHash itself, and provide > primIdentityHash to access the existing identityHash implementation > (primitive 75). My approach is to leave identityHash as is, and > provide > a new message called scaledIdentityHash. Note that in both Martin's > and > my implementation, the new identity hash values are identical. In > other > words, whereas Martin's changes implement > > identityHash > > ^self primIdentityHash bitShift: 18 > > > my changes implement > > scaledIdentityHash > > ^self identityHash bitShift: 18 > > > So, really, this is an issue of how to implement the *same* behavior, > with the *same* goals. Now, there are advantages and disadvantages > for > both. I'll try to explain. Martin, please feel free to correct what > follows if I miss something. > > There are two kinds of senders of identityHash. Some (most) do not > care > whether the answer is well distributed or not. Typically, these are > implementors of #hash, for example: > > SomeObject>>hash > > ^self someInstanceVariable identityHash > > > If, on one hand, we change identityHash, then the behavior of these > hash > methods improve because the values they answer would be distributed > more > uniformly. Nevertheless, precisely because they send identityHash, it > could be argued that these hash methods were implemented assuming > there > would be just a few of these objects in hashed collections. If this > turns out not to be the case, then performance could be much better by > implementing a better hash method. > > Some (a few) other senders of identityHash assume that the answer > has a > particular distribution (in Squeak's/Pharo's case, 0 through 4095). > Consequently, the senders may do things like this: > > SomeObject>>hash > > ^(self variableA identityHash bitShift: 12) + self variableB > identityHash > > > Also, there may be hashed collections which use identityHash to index > hash buckets (e.g.: GemStone's own 32 bit object cache for > VisualWorks, > which uses identityHash to access hash buckets). So, if we change > identityHash, these senders which required special care to write would > break, requiring them to be written like this: > > SomeObject>>hash > > ^(self variableA primIdentityHash bitShift: 12) + self variableB > primIdentityHash > > > If, on the other hand, we provide a new scaledIdentityHash method, > then > all senders of identityHash keep behaving the same way as they do now. > Hashed collections, which currently send identityHash, would need to > change so that they send scaledIdentityHash instead. Furthermore, any > implementor of hash such as > > SomeObject>>hash > > ^self someInstanceVariable identityHash > > > would need to be rewritten as > > SomeObject>>hash > > ^self someInstanceVariable scaledIdentityHash > > > if hashed collections are expected to contain numerous instances of > SomeObject. If these are not rewritten, then they would continue to > have the same performance characteristics they have today (which may > be > adequate to begin with). Clever hacks such as > > SomeObject>>hash > > ^(self variableA identityHash bitShift: 12) + self variableB > identityHash > > > would also remain undisturbed. Finally, I do not know of any > Smalltalk > in which identityHash does not answer the actual object header bits > for > the identity hash. If we change identityHash, then AFAIK Pharo would > become the only Smalltalk in which identityHash does not answer > consecutive values between 0 and (2^k)-1 (k=12 for Squeak/Pharo, k=14 > for VisualWorks 32 bits, k=20 for VisualWorks 64 bits, IIRC k=15 for > VA > and VisualSmalltalk). Moreover, AFAIK, identityHash has had this > behavior for decades. Is it a good idea to change it? I am not so > sure > on that one. Also, I wouldn't want to break clever hacks that assume > identityHash behaves the way it currently does, and I wouldn't want to > make Pharo different gratuitously. > > So that's where we stand. I think I understand where Martin is coming > from, and I think Martin understands where I am coming from. One > way or > the other, we also agree that something should be done to make hashed > collections faster in Pharo. > > Andres. > > > StÃ©phane Ducasse wrote: >> Martin >> >> so what you are saying is that we can gain speed. And that these >> changes are beneficial for simple default. >> >> >> >>> The test code, a variant of the test from the HashTable SqueakSource >>> wiki, is at the bottom of this message. Basically, it adds a bunch >>> of instances of Object to a Dictionary and sees how much time it >>> takes to look them up again. >>> >>> From the graphs in the previous message, you can see that >>> performance for sizes > 4000 is greatly improved. For size = 10000, >>> #at: is 1000 times faster, 2-3 microseconds vs. >2 milliseconds. At >>> size=10000, #at:put: is about 200 times faster, ~10 microseconds vs. >>> >>>> 2 milliseconds, and the large spikes for growing the collection are >>>> >>> 21 milliseconds vs. > 4 seconds, again a factor of about 200. >>> >>> Performance for dictionary sizes < 4000 is essentially the same as >>> before, so these collections can serve as general-purpose >>> collections over a wide range of sizes. I've attached the graphs for >>> sizes <4000 to this message so you can see that more clearly than on >>> the previous graphs. >>> >>> These results should hold for any object that inherits #hash from >>> Object, in other words uses its identity hash as its equality hash. >>> Other objects with better hashes did not have as serious a problem, >>> but will probably show increased performance as well due to using >>> prime table sizes. >>> >>> These changes are in Set, so should improve Set's subclasses as >>> well. IdentityDictionary, IdentitySet, and WeakIdentityKeyDictionary >>> did not have as serious a problem, but should see some improvement. >>> MethodDictionaries have been left alone on the assumption that the >>> VM depends on the hashing of those. >>> >> >> So where are these changes :) >> Should we integrate them? >> Andres and other hash freaks what are your point of view? >> >> >>> Since there are still only 4K possible values of identity hash, >>> collisions are inevitable in large collections, and the number of >>> collisions will grow linearly with collection size. So how well does >>> the spread hash / prime table size do at even larger sizes? I ran >>> the same test at sizes of one million. As expected, access was quite >>> a bit slower than it had been at 10000. Time for #at: was ~250 >>> microseconds, and #at:put: was about the same. Note, however, that >>> this is still ten times faster than Dictionary previously was at a >>> size of 10000; 100 times larger yet 10 times faster. >>> >>> I had a lot of fun doing this. This is better results than I >>> expected, for a fairly minor (though deep) code change. >>> >> >> So where are these changes :) >> Should we integrate them? >> Andres and other hash freaks what are your point of view? >> >> >> >>> | test ord | >>> Transcript cr. >>> test := Dictionary new. >>> [ test size >= 10000] whileFalse: [ >>> ord := OrderedCollection new: 100. >>> Transcript show: >>> [ >>> 100 timesRepeat: [ >>> test at: ( ord add: Object new ) put: nil ]. >>> ] timeToRun asString. >>> Transcript tab; >>> show: test size asString; >>> tab. >>> Transcript show: >>> [ >>> 1000 timesRepeat: [ >>> ord do: [ :each | test at: each ] ] >>> ] timeToRun asString. >>> Transcript tab; show: >>> [ >>> 1000 timesRepeat: [ >>> ord do: [ :each | ] ] >>> ] timeToRun asString. >>> Transcript cr ] >>> >>> < >>> SmallDictPerformanceGraphs1 >>> .png>_______________________________________________ >>> Pharo-project mailing list >>> Pharo-project(a)lists.gforge.inria.fr >>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >>> >> >> >> _______________________________________________ >> Pharo-project mailing list >> Pharo-project(a)lists.gforge.inria.fr >> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >> . >> >> > > _______________________________________________ > Pharo-project mailing list > Pharo-project(a)lists.gforge.inria.fr > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

Oct. 31, 2009

[Pharo-project] vm on ubuntu

by Tudor Girba

Hi, What is the preferred way to install a Pharo vm on Ubuntu? Cheers, Doru -- www.tudorgirba.com "From an abstract enough point of view, any two things are similar."

Oct. 31, 2009

Re: [Pharo-project] Question about deepCopy,

by Stan Shepherd

I meant to say, maybe deepCopy should just be deprecated? Stan Shepherd wrote: > > > arnaud Jean Baptiste wrote: >> >> >> I don't suggest to rename #deepCopy, i suggest to replace the behavior >> of #deepCopy by #veryDeepCopy behavior. >> > > From my observation, the two do not have identical behaviour. In my own > case, I need the behaviour of deepCopy to avoid copying a very large > object unnecessarily; for now I have a specific method for the object > copyWithoutCircularity. > > There are 44 senders of deepCopy, which would need testing. > > Another solution is to rewrite deepCopy like veryDeepCopy, to have a > copier object. This needs another method on Object, deepCopyWith: > > I'm happy to implement a solution, given a consensus on the best way to do > this. > > I have created a general test case for this situation, attached to issue > 521 > > http://pharo.googlecode.com/issues/attachment?aid=7298911011553982520&name=… > > ...Stan > -- View this message in context: http://n2.nabble.com/Question-about-deepCopy-tp3859147p3923589.html Sent from the Pharo Smalltalk mailing list archive at Nabble.com.

Oct. 31, 2009