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@elte.hu> To: squeak-dev@lists.squeakfoundation.org, pharo-users@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. 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