[Cuis-dev] allSubclasses and withAllSubclasses improvement

Andres Valloud ten at smallinteger.com
Wed Aug 21 12:29:53 PDT 2019


What do you see as "ugly"?

One detail I don't see mentioned here: the old code filled the ordered 
collection breadth first (before the set conversion), and so it has 
limited execution stack depth.  The current code fills the collection 
depth first, so its execution stack depth is as deep as the hierarchy tree.

Maybe there was a reason why the users of allSubclasses were better off 
with breadth first, before someone put in asSet.  Or perhaps asSet was 
always there, I don't see why that was beneficial.

In any case, I tried both the recursive and (properly implemented) 
iterative methods: breadth first is >20% faster.

On 8/21/19 05:44, Juan Vuletich via Cuis-dev wrote:
> Wow, thanks. The old code was slow and ugly!
> 
> Integrating it.
> 
> Cheers,
> 
> -- 
> Juan Vuletich
> www.cuis-smalltalk.org
> https://github.com/Cuis-Smalltalk/Cuis-Smalltalk-Dev
> https://github.com/jvuletich
> https://www.linkedin.com/in/juan-vuletich-75611b3
> @JuanVuletich
> 
> 
> On 8/21/2019 9:26 AM, Hernan Wilkinson via Cuis-dev wrote:
>> Hi,
>>  attached is a cs that changes the implementation of #allSubclasses 
>> and #withAllSubclasses and generates performance improvement drastically.
>>  Just as a quick example, with the current implementation:
>>  Time millisecondsToRun: [ 100 timesRepeat: [Behavior 
>> withAllSubclasses ]] 1140 .
>>  With the proposed change:
>>  Time millisecondsToRun: [ 100 timesRepeat: [Behavior 
>> withAllSubclasses2 ]]  . 73
>>
>>  In the type checker of LiveTyping, checking Behavior goes from 9.5 
>> seconds to 5 seconds only with that change.
>>  One difference between the current and proposed version, is that the 
>> current returns a Set while the proposed version returns an 
>> OrderedCollection.
>>  I looked carefully if that could break something and it does not. 
>> I've been using the image with this new implementation and everything 
>> works fine.
>>
>>  Juan, please take a look at it and integrate it if you think it is 
>> useful.
>>  Hernan.
>>
>> -- 
>> *Hernán Wilkinson
>> Agile Software Development, Teaching & Coaching*
>> *Phone: +54-011*-4893-2057
>> *Twitter: @HernanWilkinson*
>> *site: http://www.10Pines.com <http://www.10pines.com/>*
>> Address: Alem 896, Floor 6, Buenos Aires, Argentina
> 
-------------- next part --------------
'From Cuis 4.2 of 25 July 2013 [latest update: #2595] on 21 August 2019 at 12:28:40.349111 pm'!

!Behavior methodsFor: 'accessing class hierarchy' stamp: 'sqr 8/21/2019 12:27'!
allSubclassesBreadthFirst

	| answer finger fingerLimit each |
	answer := OrderedCollection withAll: self subclasses.
	finger := 0.
	fingerLimit := answer size.
	[finger < fingerLimit] whileTrue:
		[
			finger + 1 to: fingerLimit do:
				[:index |
					each := answer at: index.
					answer addAll: each subclasses
				].
			finger := fingerLimit.
			fingerLimit := answer size.
		].
	^answer! !
-------------- next part --------------
'From Cuis 4.2 of 25 July 2013 [latest update: #2595] on 21 August 2019 at 12:28:42.885529 pm'!

!Behavior methodsFor: 'accessing class hierarchy' stamp: 'sqr 8/21/2019 12:16'!
allSubclassesDepthFirst

	| answer |
	answer := OrderedCollection new.
	self allSubclassesDepthFirstAddTo: answer.
	^answer! !
-------------- next part --------------
'From Cuis 4.2 of 25 July 2013 [latest update: #2595] on 21 August 2019 at 12:28:45.366881 pm'!

!Behavior methodsFor: 'accessing class hierarchy' stamp: 'sqr 8/21/2019 12:16'!
allSubclassesDepthFirstAddTo: aCollection

	self subclasses do:
		[:each |
			aCollection add: each.
			each allSubclassesDepthFirstAddTo: aCollection
		]! !


More information about the Cuis-dev mailing list