[squeak-dev] #hasBindingThatBeginsWith:, Shout, E/OCompletion
Levente Uzonyi
leves at elte.hu
Fri Oct 8 21:14:02 UTC 2010
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.
Pros:
- very simple addition
- covers the most common cases
Cons:
- 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 only)).
Pros:
- covers all cases with good performance
- the new cache can be used to speed up other methods (like #allTraits)
Cons:
- modifies SystemDictionary
I'd go with the second solution. What do you think?
Cheers,
Levente
More information about the Squeak-dev
mailing list
|