Mantis Bugtracker

Viewing Issue Advanced Details Jump to Notes ] View Simple ] 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 Platform
Status closed   OS
Projection none   OS Version
ETA none Fixed in Version 4.1 Product Version 3.8
  Product Build
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.
Steps To Reproduce
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