Keep in mind that growing on addAll: before the duplicates are filtered out may require significantly more memory than necessary. For example,
Set new addAll: "all instances of string" I am sure there is an example than illustrates the issue better than the above one. While Set new addAll: "consecutive integers" may run faster, I think doing (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
