2009/7/1 Henrik Johansen <henrik.s.johansen@veloxit.no>:
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)
I considered this when I created FasterSets. I didn't do this because I was being conservative. I didn't want FasterSets rejected because it did things that weren't wanted. I am surprised though at the amount of performance gain you see. As things stand I see no reason for not including FasterSets other than the potential of breaking packages that subclass Set and then override methods crucial to FasterSets. My vote is obviously for fixing any packages that get broken rather than rejecting FasterSets.
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
I created FasterSets for adding to Squeak and did not consider Pharo but of course am delighted to have it considered for Pharo. You can of course make whatever improvements you want. I encourage though that you create a FasterSets2 containing all the improvements and leave the original FasterSets alone. I am still interested in having FasterSets included in Squeak and I do not know if the powers that be will want the additional improvements or not so I prefer that both versions exist. One thing that I have in my code is a method called nastyAddNew: which adds an element to a set without checking if the element is already there. If the element is already there of course it gets added again and your set contains two copies of the element; thus your set is corrupted. This problem explains the 'nasty' part of the name nastyAddNew. I also have a method addNew: which reports an error if the object is already in the set. nastyAddNew: can be used in set operations such as copy and intersection making these operations faster and can also be used externally by brave users. If improvements to FasterSets are being contemplated then I suggest that adding methods addNew: and nastyAddNew: be considered. If nastyAddNew: is added I see no point in making it private because some users will use it anyway. I am not necessarily voting for their inclusion because we are then giving the user the opportunity to corrupt his data. Of course I do use them in my current project. thus, for my current project at least, I am a brave user. Regards, Ralph Boland