Mantis - Squeak
Viewing Issue Advanced Details
3474 Collections tweak always 04-16-06 02:52 02-06-11 23:48
rpboland  
nicolas cellier  
normal  
closed 3.8  
fixed  
none    
none 4.1  
0003474: Sets do unnecessary compares during add: operation
I have implemented an improvement to the Set class and its many subclasses.
I have place the code here in the hope that it can be incorporated into
Squeak. The code is in the form of a gzipped tar file of
a set of .st files and a README file.
Unfortunately it is not possible to file in all the
changes as a single .cs file.
If there are problems please email me at rpboland@gmail.com

For the class Set my 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.)

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 formany subclasses of class Set
and some further clean up of code became necessary.
 wrod.tar.gz [^] (6,055 bytes) 04-16-06 02:52

Notes
(0013838)
nicolas cellier   
08-21-10 16:02   
This has been fixed in trunk by using the message #noCheckNoGrowFillFrom: