Faster set add: operations

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

Faster set add: operations

Ralph Boland
I have implemented an improvement to the Set class and its many subclasses. 
For the class Set this improvement reduces the number of (elements of S) compares
done during an 'add:' operation by  8-20% with an average of about 14%.  
For the many subclasses of class Set the  level of improvement should be about the same.
Since I don't even know what all of the subclasses of Set are for,
I cannot claim to have properly tested all of my changes but
they appear to work properly in Squeak 3.6, 3.7, and 3.8 for a large project I am working on.
(I do seem to be having performance problems with Squeak 3.8 after porting my project
from Squeak 3.6 but I do not see why this is related to my Set improvement code.)

I would like to forward my code to someone who has the knowledge to test the code thouroughly
and the authority to then incorporate the improvement into Squeak 3.9.
Could the powers that be designate someone who I can forward this code to.

The improvement I have made is described below:

During a grow operation a set  S  assigns a local variable (oldElements)
to the instance variable  'array'  containing the elements of  S
and then reassigns array to a new Array object
larger (occasionally smaller) than (oldElements size). 
This makes  S  temporarily an empty set. 
Then  S  performs an 'add:' operation on itself for each element in oldElements
(In Sqeuak 3.8 the 'add:' operation is replaced by a 'noCheckAdd:'  operation;
an improvement but no cigar).

This 'add:' ('noCheckAdd:') operation is inefficient
in that it does compares with elements already in  S
(from the 'add:' operations done by  S  on itself since the beginning of the grow operation).
These comparisons always return that the objects are different since, if they were
the same, the set  S  would have corrupt data.
Thus these compares are always unnecessary.

I have replaced this 'add:' operation by a  'noCompareAdd:' operation which adds an element
to a set without doing any comparisions. 
I consider this method private; to be used only during grow operations.
Admittedly, if you are sure that the element you are adding to a set is not already there
and you are insane,
then you could use this method as a public method to save some time.
Actually, even this is not true because 'noCompareAdd:' makes no allowance for
the set to grow!  Of course, this could be changed to accommadate the insane.

There are actually quite a few changes since 'noCompareAdd:'  is implemented for
many subclasses of class Set and some further clean up of code became necessary.

If someone could point out the versions of Smalltalk for which this improvement could also
be made that would also be appreciated.

Thanks, 

Ralph Boland


Reply | Threaded
Open this post in threaded view
|

Re: Faster set add: operations

Zulq Alam
Please could we have a "for the insane" method category for such methods? ;)

Ralph Boland wrote:

Admittedly, if you are sure that the element you are adding to a set is not already there
and you are insane,
then you could use this method as a public method to save some time.



Reply | Threaded
Open this post in threaded view
|

Re: Faster set add: operations

Damien Cassou-3
In reply to this post by Ralph Boland
Ralph Boland a écrit :
> I have implemented an improvement to the Set class and its many
> subclasses.

Very good idea. I think you should post your code to http://bugs.impara.de.

>From Ken Causey:
"Whether it's one line or 1,000 it always goes to the same place:
http://bugs.impara.de/ .

Ken

P.S.  Prefereably as a well filled out report specifying the category
based on the top-level class category of the relevant class and
including a clear explanation and a gzipped changeset."


Bye

--
Damien Cassou