Faster set add: operations

Ralph Boland rpboland at gmail.com
Thu Apr 13 14:35:39 UTC 2006


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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.squeakfoundation.org/pipermail/squeak-dev/attachments/20060413/bc6080fc/attachment.htm


More information about the Squeak-dev mailing list