Having spent a fair deal of time (in VisualWorks) worrying about my intial Set sizes, writing functions to precompute sane sizes for arbitrary inputs and adding changeCapacityTo: calls before addAll: operations due to performance issues on a case-by-case basis (Squeak/ Pharo doesn't even HAVE a changeCapacityTo: ), I have to strongly disagree.
I'd rather spend my time thinking about my problem domain, and know the Set implementation handles the nitty-gritty details in a sufficiently smart way. Whether that means growing once to accomedate the worst case, then shrinking afterwards, or doing a grow check every X added items, in the unlikely event that what you're adding is a 3 million element Array with 10 unique objects, I don't really care. Cheers, Henry On Jul 2, 2009, at 7:38 10AM, Andres Valloud wrote: > > (Set new: desiredCapacity) addAll: "consecutive integers" > > may be a better compromise. > > Andres. > > > Stéphane Ducasse wrote: >> Thanks this is really good. >> We will probably integrate these changes really fast >> >> On Jul 1, 2009, at 1:03 PM, Henrik Johansen wrote: >> >> >>> I took some time to check this yesterday, my comments on the code >>> itself are basically the same as what Lucas posted in the issue >>> tracker. >>> Works as advertised, but should probably clean out the "gunk" >>> which is >>> unused after it's integrated. >>> >>> Some feedback on possible improvements: >>> - What it does, is basically speed up the adds to the new array in a >>> grow that might happen Why not take this all to the logical >>> conclusion, and instead optimize an addAll: method to be used in >>> grow, >>> that assumes elements are not in set (and themselves are not >>> duplicates)? F.ex. it could also add to tally just once, instead of >>> one increase per element as the noCompareAdd: does. (an add method >>> with no tally add, no = object check, and no growCheck). >>> >>> - The usual addAll: method can be sped up in a similar way, by >>> performing one grow operation before adding elements if necessary >>> (pessimistically assuming all elements are unique), then use an add >>> method which does not check for grow need at all. (an add method >>> with >>> tally add and = object check, but no growCheck) >>> If desirable, you could also shrink the capacity after adds are >>> done, to match the real amount of new elements. >>> >>> Adding (1 to: 1200000) to a new Set with such an addAll: method took >>> 1/2 to 1/3rd the time of the regular addAll: method, even with the >>> lower grow cost of FasterSets. (Lower gains if Set is presized, >>> and if >>> hash-calculation is bigger part of cost) >>> >>> Note: If you want to stay ANSI-compatible, one tricky point in >>> such an >>> optimization is adding all objects in collection up to a nil >>> element, >>> then raising an error. (ie: must produce equivalent results to add: >>> performed of each of collections elements in sequence ) >>> >>> Cheers, >>> Henry >>> >>> >>> On Jun 25, 2009, at 8:55 03PM, Stéphane Ducasse wrote: >>> >>> >>>> I would really like to assess FasterSets for Pharo1.1 >>>> >>>> Begin forwarded message: >>>> >>>> >>>>> From: Ralph Boland <[email protected]> >>>>> Date: June 25, 2009 8:30:13 PM CEDT >>>>> To: Stéphane Ducasse <[email protected]> >>>>> Subject: Re: about fasterTests >>>>> >>>>> 2009/6/25 Stéphane Ducasse <[email protected]>: >>>>> >>>>>> we are interest to get better libraries in pharo. >>>>>> If you want to join and help making sure that your code in >>>>>> integrated in >>>>>> pharo1.1 >>>>>> please say it and may be join the pharo mailing-list. >>>>>> >>>>>> Stef >>>>>> >>>>>> >>>>> Yes, I would like my code 'FasterSets' added to Pharo. >>>>> I joined the pharo mailing list. >>>>> Today I will mail you my MIT license release. >>>>> Probably will take a couple of weeks (From Calgary, Canada) to get >>>>> there. >>>>> Once I am added as a contributer I will release my code to Pharo >>>>> for >>>>> verification. >>>>> In the meantime if any Squeakers try out my code and report bugs I >>>>> will fix them >>>>> before releasing to Pharo. >>>>> >>>>> Some comments: >>>>> >>>>> 1) Since FasterSets modifies low level methods in class Set and >>>>> its >>>>> subclasses it >>>>> may be incompatible with packages that create subclasses of Set >>>>> and then >>>>> override low level methods. If someone could send me a list of >>>>> package add-ons >>>>> to Pharo that do this then I can download them and make any >>>>> modifications >>>>> necessary for them to run with FasterSets and make these changes >>>>> part of my >>>>> release. Note that it is no more difficult to subclass from Set >>>>> with FasterSets >>>>> than without; it is just different and only different if you do >>>>> low level things. >>>>> >>>>> 2) FasterSets uses a method 'noCompareOrGrowAdd:' which adds >>>>> an element to a set without doing compares or growing the set. >>>>> Needless to say it is a private method. >>>>> I also have a public method 'nastyAddNew:' which, like >>>>> 'noCompareOrGrowAdd:' adds an element to a set without checking >>>>> if the >>>>> element is already there but does do a grow if needed. >>>>> This is useful (i.e. faster) in situations where you KNOW the >>>>> object >>>>> you are adding to a set is not there already. >>>>> However if the object IS already there then you now have two >>>>> of them in your set; i.e. you now have a subtle bug. >>>>> I use 'nastyAddNew:' in my code but never made it a part of >>>>> FasterSets >>>>> because it is questionable whether or not such a method should be >>>>> available generally. However, if I can decide I like the >>>>> 'nastyAddNew:' >>>>> method and am willing to use it despite its risks so can others >>>>> so there >>>>> is an argument for it being added. >>>>> While my expectation is that you don't want 'nastyAddNew:' in >>>>> Pharo >>>>> I thought you should at least be aware of it. >>>>> >>>>> Regards, >>>>> >>>>> Ralph Boland >>>>> >>>> _______________________________________________ >>>> Pharo-project mailing list >>>> [email protected] >>>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >>>> >>>> >>> _______________________________________________ >>> Pharo-project mailing list >>> [email protected] >>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >>> >> >> >> _______________________________________________ >> Pharo-project mailing list >> [email protected] >> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >> . >> >> > > _______________________________________________ > Pharo-project mailing list > [email protected] > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project > _______________________________________________ Pharo-project mailing list [email protected] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
