FasterSets

> From: Ralph Boland <[hidden email]>
> Date: June 25, 2009 8:30:13 PM CEDT
> To: Stéphane Ducasse <[hidden email]>
> Subject: Re: about fasterTests
>
> 2009/6/25 Stéphane Ducasse <[hidden email]>:
>> 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

>
> On Thu, Jun 25, 2009 at 5:55 PM, Stéphane Ducasse <[hidden email]
> > wrote:
> I would really like to assess FasterSets for Pharo1.1
>
> are all of these things stored somewhere apart from this mailing  
> list ?
>
> I saw http://code.google.com/p/pharo/wiki/Milestones
>
> but it is quite old
>
> Mariano
>
>
>
> Begin forwarded message:
>
> > From: Ralph Boland <[hidden email]>
> > Date: June 25, 2009 8:30:13 PM CEDT
> > To: Stéphane Ducasse <[hidden email]>
> > Subject: Re: about fasterTests
> >
> > 2009/6/25 Stéphane Ducasse <[hidden email]>:
> >> 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
> [hidden email]
> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
>
> _______________________________________________
> Pharo-project mailing list
> [hidden email]
> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

> I would really like to assess FasterSets for Pharo1.1
>
> Begin forwarded message:
>
>> From: Ralph Boland <[hidden email]>
>> Date: June 25, 2009 8:30:13 PM CEDT
>> To: Stéphane Ducasse <[hidden email]>
>> Subject: Re: about fasterTests
>>
>> 2009/6/25 Stéphane Ducasse <[hidden email]>:
>>> 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
> [hidden email]
> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
>

> 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 <[hidden email]>
>>> Date: June 25, 2009 8:30:13 PM CEDT
>>> To: Stéphane Ducasse <[hidden email]>
>>> Subject: Re: about fasterTests
>>>
>>> 2009/6/25 Stéphane Ducasse <[hidden email]>:
>>>> 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
>> [hidden email]
>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
>>
>
>
> _______________________________________________
> Pharo-project mailing list
> [hidden email]
> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

> 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 <[hidden email]>
>>>> Date: June 25, 2009 8:30:13 PM CEDT
>>>> To: Stéphane Ducasse <[hidden email]>
>>>> Subject: Re: about fasterTests
>>>>
>>>> 2009/6/25 Stéphane Ducasse <[hidden email]>:
>>>>        
>>>>> 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
>>> [hidden email]
>>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
>>>
>>>      
>> _______________________________________________
>> Pharo-project mailing list
>> [hidden email]
>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
>>    
>
>
> _______________________________________________
> Pharo-project mailing list
> [hidden email]
> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
> .
>
>  

>
> (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 <[hidden email]>
>>>>> Date: June 25, 2009 8:30:13 PM CEDT
>>>>> To: Stéphane Ducasse <[hidden email]>
>>>>> Subject: Re: about fasterTests
>>>>>
>>>>> 2009/6/25 Stéphane Ducasse <[hidden email]>:
>>>>>
>>>>>> 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
>>>> [hidden email]
>>>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
>>>>
>>>>
>>> _______________________________________________
>>> Pharo-project mailing list
>>> [hidden email]
>>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
>>>
>>
>>
>> _______________________________________________
>> Pharo-project mailing list
>> [hidden email]
>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
>> .
>>
>>
>
> _______________________________________________
> Pharo-project mailing list
> [hidden email]
> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
>

> 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 <[hidden email]>
>>>>>> Date: June 25, 2009 8:30:13 PM CEDT
>>>>>> To: Stéphane Ducasse <[hidden email]>
>>>>>> Subject: Re: about fasterTests
>>>>>>
>>>>>> 2009/6/25 Stéphane Ducasse <[hidden email]>:
>>>>>>
>>>>>>            
>>>>>>> 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
>>>>> [hidden email]
>>>>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
>>>>>
>>>>>
>>>>>          
>>>> _______________________________________________
>>>> Pharo-project mailing list
>>>> [hidden email]
>>>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
>>>>
>>>>        
>>> _______________________________________________
>>> Pharo-project mailing list
>>> [hidden email]
>>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
>>> .
>>>
>>>
>>>      
>> _______________________________________________
>> Pharo-project mailing list
>> [hidden email]
>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
>>
>>    
>
> .
>
>  

> 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 <[hidden email]>
>>>>>>> Date: June 25, 2009 8:30:13 PM CEDT
>>>>>>> To: Stéphane Ducasse <[hidden email]>
>>>>>>> Subject: Re: about fasterTests
>>>>>>>
>>>>>>> 2009/6/25 Stéphane Ducasse <[hidden email]>:
>>>>>>>
>>>>>>>
>>>>>>>              
>>>>>>>> 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
>>>>>> [hidden email]
>>>>>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
>>>>>>
>>>>>>
>>>>>>
>>>>>>            
>>>>> _______________________________________________
>>>>> Pharo-project mailing list
>>>>> [hidden email]
>>>>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
>>>>>
>>>>>
>>>>>          
>>>> _______________________________________________
>>>> Pharo-project mailing list
>>>> [hidden email]
>>>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
>>>> .
>>>>
>>>>
>>>>
>>>>        
>>> _______________________________________________
>>> Pharo-project mailing list
>>> [hidden email]
>>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
>>>
>>>
>>>      
>> .
>>
>>
>>    
>
> _______________________________________________
> Pharo-project mailing list
> [hidden email]
> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
> .
>
>  

> 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 <[hidden email]>
>>>>>>> Date: June 25, 2009 8:30:13 PM CEDT
>>>>>>> To: Stéphane Ducasse <[hidden email]>
>>>>>>> Subject: Re: about fasterTests
>>>>>>>
>>>>>>> 2009/6/25 Stéphane Ducasse <[hidden email]>:
>>>>>>>
>>>>>>>
>>>>>>>> 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
>>>>>> [hidden email]
>>>>>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
>>>>>>
>>>>>>
>>>>>>
>>>>> _______________________________________________
>>>>> Pharo-project mailing list
>>>>> [hidden email]
>>>>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo- 
>>>>> project
>>>>>
>>>>>
>>>> _______________________________________________
>>>> Pharo-project mailing list
>>>> [hidden email]
>>>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
>>>> .
>>>>
>>>>
>>>>
>>> _______________________________________________
>>> Pharo-project mailing list
>>> [hidden email]
>>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
>>>
>>>
>>
>> .
>>
>>
>
> _______________________________________________
> Pharo-project mailing list
> [hidden email]
> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
>

> 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 <[hidden email]>
>>>>>>>> Date: June 25, 2009 8:30:13 PM CEDT
>>>>>>>> To: Stéphane Ducasse <[hidden email]>
>>>>>>>> Subject: Re: about fasterTests
>>>>>>>>
>>>>>>>> 2009/6/25 Stéphane Ducasse <[hidden email]>:
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>> 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
>>>>>>> [hidden email]
>>>>>>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>> _______________________________________________
>>>>>> Pharo-project mailing list
>>>>>> [hidden email]
>>>>>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
>>>>>>
>>>>>>
>>>>>>
>>>>> _______________________________________________
>>>>> Pharo-project mailing list
>>>>> [hidden email]
>>>>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo- 
>>>>> project
>>>>> .
>>>>>
>>>>>
>>>>>
>>>>>
>>>> _______________________________________________
>>>> Pharo-project mailing list
>>>> [hidden email]
>>>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
>>>>
>>>>
>>>>
>>> .
>>>
>>>
>>>
>>
>> _______________________________________________
>> Pharo-project mailing list
>> [hidden email]
>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
>> .
>>
>>
>
> _______________________________________________
> Pharo-project mailing list
> [hidden email]
> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
>

> 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 <[hidden email]>
>>>>>>>>> Date: June 25, 2009 8:30:13 PM CEDT
>>>>>>>>> To: Stéphane Ducasse <[hidden email]>
>>>>>>>>> Subject: Re: about fasterTests
>>>>>>>>>
>>>>>>>>> 2009/6/25 Stéphane Ducasse <[hidden email]>:
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>                  
>>>>>>>>>> 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
>>>>>>>> [hidden email]
>>>>>>>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>                
>>>>>>> _______________________________________________
>>>>>>> Pharo-project mailing list
>>>>>>> [hidden email]
>>>>>>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>              
>>>>>> _______________________________________________
>>>>>> Pharo-project mailing list
>>>>>> [hidden email]
>>>>>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-
>>>>>> project
>>>>>> .
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>>            
>>>>> _______________________________________________
>>>>> Pharo-project mailing list
>>>>> [hidden email]
>>>>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
>>>>>
>>>>>
>>>>>
>>>>>          
>>>> .
>>>>
>>>>
>>>>
>>>>        
>>> _______________________________________________
>>> Pharo-project mailing list
>>> [hidden email]
>>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
>>> .
>>>
>>>
>>>      
>> _______________________________________________
>> Pharo-project mailing list
>> [hidden email]
>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
>>
>>    
>
> .
>
>  

> However, handling the growth failure wouldn't crash the program...
>
> Henrik Johansen wrote:
>> 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 <[hidden email]>
>>>>>>>>>> Date: June 25, 2009 8:30:13 PM CEDT
>>>>>>>>>> To: Stéphane Ducasse <[hidden email]>
>>>>>>>>>> Subject: Re: about fasterTests
>>>>>>>>>>
>>>>>>>>>> 2009/6/25 Stéphane Ducasse <[hidden email]>:
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>> 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
>>>>>>>>> [hidden email]
>>>>>>>>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>> _______________________________________________
>>>>>>>> Pharo-project mailing list
>>>>>>>> [hidden email]
>>>>>>>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>> _______________________________________________
>>>>>>> Pharo-project mailing list
>>>>>>> [hidden email]
>>>>>>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-
>>>>>>> project
>>>>>>> .
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>> _______________________________________________
>>>>>> Pharo-project mailing list
>>>>>> [hidden email]
>>>>>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>> .
>>>>>
>>>>>
>>>>>
>>>>>
>>>> _______________________________________________
>>>> Pharo-project mailing list
>>>> [hidden email]
>>>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
>>>> .
>>>>
>>>>
>>>>
>>> _______________________________________________
>>> Pharo-project mailing list
>>> [hidden email]
>>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
>>>
>>>
>>
>> .
>>
>>
>
> _______________________________________________
> Pharo-project mailing list
> [hidden email]
> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
>