Mantis Bugtracker

Viewing Issue Simple Details Jump to Notes ] View Advanced ] Issue History ] Print ]
ID Category Severity Reproducibility Date Submitted Last Update
0003474 [Squeak] Collections tweak always 04-16-06 02:52 02-06-11 23:48
Reporter rpboland View Status public  
Assigned To nicolas cellier
Priority normal Resolution fixed  
Status closed   Product Version 3.8
Summary 0003474: Sets do unnecessary compares during add: operation
Description 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

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.
Additional Information
Attached Files  wrod.tar.gz [^] (6,055 bytes) 04-16-06 02:52

- Relationships

- Notes
(0013838 - 73 - 73 - 73 - 73 - 73 - 73)
nicolas cellier
08-21-10 16:02

This has been fixed in trunk by using the message #noCheckNoGrowFillFrom:

- Issue History
Date Modified Username Field Change
04-16-06 02:52 rpboland New Issue
04-16-06 02:52 rpboland File Added: wrod.tar.gz
08-21-10 16:02 nicolas cellier Status new => resolved
08-21-10 16:02 nicolas cellier Fixed in Version  => 4.1
08-21-10 16:02 nicolas cellier Resolution open => fixed
08-21-10 16:02 nicolas cellier Assigned To  => nicolas cellier
08-21-10 16:02 nicolas cellier Note Added: 0013838
02-06-11 23:48 leves Status resolved => closed

Mantis 1.0.8[^]
Copyright © 2000 - 2007 Mantis Group
40 total queries executed.
32 unique queries executed.
Powered by Mantis Bugtracker