[Pharo-project] #hasBindingThatBeginsWith:, Shout, E/OCompletion (fwd)

Levente Uzonyi leves at elte.hu
Fri Oct 8 17:48:01 EDT 2010

I accidentally sent this to the pharo-users list...

---------- Forwarded message ----------
Date: Fri, 8 Oct 2010 23:14:02 +0200 (CEST)
From: Levente Uzonyi <leves at elte.hu>
To: squeak-dev at lists.squeakfoundation.org, pharo-users at lists.gforge.inria.fr
Subject: #hasBindingThatBeginsWith:, Shout, E/OCompletion

Hi folks,

there's a method called #hasBindingThatBeginsWith: which seems to be used
only by Shout. If that's true, then it would be better to add it to the 
Shout/ShoutCore package if possible.
Also this method is responsible for the slowdown of Shout's parser when there 
are undefined variables in the code. Actually only SystemDictionary 
>> #hasBindingsThatBeginsWith: is responsible for the slowdown which uses 
Dictionary's implementation which checks all keys.
There's already an issue on Pharo's tracker (with some useful, but with
some wrong info too): http://code.google.com/p/pharo/issues/detail?id=1452 . 
The slowdown affects E/OCompletion more, because those invoke Shout's parser 
after every keystroke, while Shout uses a background process for parsing.
I propose two possible solutions here:

1) Add the following method (+2-3 other, see below):

SystemDictionary >> hasBindingThatBeginsWith: aString

 	| className |
 	aString isEmpty ifTrue: [ ^false ].
 	(self class fastBindingPrefixSearch and: [
 		aString first isLowercase ])
 			ifTrue: [ ^false ].
 	className := self classNames
 		findBinary: [ :element |
 			(element beginsWith: aString)
 				ifTrue: [ 0 ]
 				ifFalse: [
 					aString < element
 						ifTrue: [ -1 ]
 						ifFalse: [ 1 ] ] ]
 		ifNone: nil.
 	className ifNotNil: [ ^true ].
 	^super hasBindingThatBeginsWith: aString

How does it work?
There are two optimizations. The first checks if the argument's first letter is 
lowercase. If it's a lowercase letter, then it returns false instead of 
checking the dictionary. This is the most common case when you're typing 
methods with undefined local/instance variables. Since this optimization breaks 
Shout's highlighting when the argument is a prefix of a global that begins with 
a lowercase letter, there's a boolean preference/setting that enables/disables 
this optimization (SystemDictionary class >> #fastBindingPrefixSearch).
The other optimization uses binary search on SystemDictionary's cached class 
names, which is a SortedCollection with all the classnames in the system. This 
helps when you're typing the name of an existing class. Since Shout uses a 
background process, this is mostly useful for E/OCompletion. When none of these 
optimizations are usable, the method simply falls back to scanning all keys.

- very simple addition
- covers the most common cases
- it doesn't work for all cases
- it breaks Shout highlighting a bit

2) Add a new instance variable to SystemDictionary to hold the name of 
non-class globals, use binary search on both sorted collections:

SystemDictionary >> hasBindingThatBeginsWith: aString

 	| name searchBlock |
 	searchBlock := [ :element |
 		(element beginsWith: aString)
 			ifTrue: [ 0 ]
 			ifFalse: [
 				aString < element
 					ifTrue: [ -1 ]
 					ifFalse: [ 1 ] ] ].
 	name := self classNames
 		findBinary: searchBlock
 		ifNone: nil.
 	name ifNotNil: [ ^true ].
 	name := self nonClassNames
 		findBinary: searchBlock
 		ifNone: nil.
 	^name notNil

(for the rest see System-ul.384 in the Inbox for Squeak and 
http://leves.web.elte.hu/squeak/SystemDictionary.ul.1.cs for Pharo)

How does it work?
It's just two binary search, one on the class names and one on the non-clas 
names. This covers all globals (except those which are not in memory (Squeak 

- covers all cases with good performance
- the new cache can be used to speed up other methods (like #allTraits)
- modifies SystemDictionary

I'd go with the second solution. What do you think?


More information about the Pharo-dev mailing list