|Anonymous | Login||11-24-2020 12:35 UTC|
|Main | My View | View Issues | Change Log | Docs|
|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|
|Assigned To||nicolas cellier|
|Summary||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 firstname.lastname@example.org
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.
|Attached Files||wrod.tar.gz [^] (6,055 bytes) 04-16-06 02:52|
(0013838 - 73 - 73 - 73 - 73 - 73 - 73)
|This has been fixed in trunk by using the message #noCheckNoGrowFillFrom:|
|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.