It would. I'm not sure I consider the current behaviour of spending 12 minutes adding the same element so much better, though. Cheers, Henry On Jul 2, 2009, at 12:17 14PM, Andres Valloud wrote:
Also, what happens in these cases?
| set | set := Set new. bag := Bag new. bad add: 4 withOccurrences: 1000000000 "or equivalent code". set addAll: bag
I am guessing the set will fail to grow and addAll: will fail, even though it should work. Maybe it won't happen with bags, or perhaps the example needs some massaging. Is the failure to grow handled gracefully? Note that I have not looked at the code because I have not had much chance to do that yet.
Andres Valloud wrote:
Hmmm, I don't know though, usually the usage pattern with hashed collections has been to presize explicitly and then add to them... what kind of use cases are you dealing with?
Henrik Johansen wrote:
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 <rpboland@gmail.com> Date: June 25, 2009 8:30:13 PM CEDT To: Stéphane Ducasse <stephane.ducasse@inria.fr> Subject: Re: about fasterTests
2009/6/25 Stéphane Ducasse <stephane.ducasse@inria.fr>:
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 Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo- project .
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
.
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project .
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project